전체 글 (16) 썸네일형 리스트형 Apprentice Learning Trajectory 풀이(boj 19218, NERC 2019 A번) 문제 설명 https://www.acmicpc.net/problem/19218 19218번: Apprentice Learning Trajectory The first line contains integer $n$ ($1 \le n \le 200\,000$) --- the number of masters. Each of the next $n$ lines contains three integers $a_i, b_i, t_i$ ($1 \le a_i < a_i + t_i \le b_i \le 10^{18}$) --- the start and the end time of master's work, and th www.acmicpc.net n명의 master가 있고 각 master는 [a, b] 기간동안 sword.. AtCoder ABC 174 후기 (첫 올솔브) 엣코더 15번 만에 쉬운 셋이 걸려서 처음으로 올솔브를 달성했다. (38분 3패널티) C번은 의외로 못 푸는 사람이 많았다. 매 스텝마다 증가시켜야하는 값이 7 * 10 ^ n mod K인데 다음에 증가시켜야하는 값은 10 * (7 * 10 ^ (n - 1) mod K) mod K이므로 O(1)만에 구할 수 있다. E번은 전형적인 파라매트릭 서치였는데 많이 고통 받고나니 이제 실수도 안하고 코딩하는 것도 금방이다. F번이 백준에 있는 문제랑 입력 범위를 제외하고 완전히 같아서 금방 풀어버렸는데 국내 뿐만 아니라 해외 유저에게도 꽤 잘 알려진 문제였는지 푼 사람이 1257명이나 되었다. 일본 유저에게도 다음 글로 유명했다. 나는 모스 알고리즘으로 풀었는데 푸는 방법이 2가지나 더 있다고 한다. https:.. UCPC 2020 후기 팀 구성 ICPC 팀 구성은 작년 12월에 했고 그 팀 그대로 UCPC에 참가했다. 평소에 팀원들끼리 ICPC 문제 셋을 풀어보거나 새로운 알고리즘 공부를 꾸준히 해왔는데 팀 연습은 전혀 안하고 있었고 마침 UCPC가 좋은 팀 연습 기회가 될 것이라 생각했다. UCPC 본선 진출을 목표로 참여했고 본선에 진출하면 우리팀이 어느정도의 실력인지 확인하고 싶었다. 올해 UCPC는 모두 온라인으로 진행되었다. 오프라인으로 진행됐으면 더 재밌었을텐데 조금 아쉽다. 예선 전 원래 ICPC 셋을 하나 잡아서 계속 풀어보고 있었는데 UCPC를 대비해서 예선 전 2주동안은 18/19년 예선 기출을 풀어봤다. 못 푸는 문제도 문제의 풀이, solved.ac 랭크, 스코어 보드를 보면서 난이도를 파악하고 어느정도의 수준의 .. Facebook Hacker Cup 2020 Qualification Round 후기 올해 해쉬코드, 코드잼에 이어서 해커컵에도 처음으로 참가했다. 토요일부터 3일동안 진행되었고 한 문제 이상 맞으면 예선은 통과다. A번 각 국가는 인접한 국가로만 이동할 수 있다. 각 국가에서 입국/출국이 가능한지 입력으로 주어진다. N개의 국가에 대해서 다른 국가로 이동이 가능한지 N×N 행렬로 출력하면 된다. 행렬을 채울 때 일단 모두 N으로 초기화하고 각 국가마다 자신의 국가는 Y로 채운다. 양옆으로 for문을 돌면서 현재 국가에서 출국이 가능하고 다음 국가에서 입국이 가능한지 체크한다. 가능하면 계속 Y로 채우고 불가능하면 break한다. import sys f_name = "travel_restrictions" sys.stdin = open(f_name + "_input.txt", 'r') sy.. [BOJ 2302] 극장 좌석 https://www.acmicpc.net/problem/2302 2302번: 극장 좌석 주어진 조건을 만족하면서 사람들이 좌석에 앉을 수 있는 방법의 가짓수를 출력한다. 방법의 가짓수는 2,000,000,000을 넘지 않는다. (2,000,000,000 2부터는 d - 1의 경우의 수와 d - 2의 경우의 수를 더하면 된다. (피보나치) [BOJ 15480] LCA와 쿼리 https://www.acmicpc.net/problem/15480 15480번: LCA와 쿼리 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에는 트리 T의 간선 정보 u와 v가 주어지다. u와 v는 트리의 간선을 나타내는 두 정점이다. 다음 줄에는 쿼리의 개수 M(1 ≤ M ≤ 100,000)가 주어진다. 다음 M개의 줄에는 쿼리를 나타내는 r, u, v가 주어진다. www.acmicpc.net 만약 기존에 LCA2를 풀어봤다면 딱 case만 분류하면 끝이다. while (Q--) { int u, v, r; cin >> u >> v >> r; u -= 1; v -= 1; r -= 1; int c = LCA(u, v); if (LCA(c, r) != c).. Taeko Ohnuki - 都会 その日暮らしは止めて 家へ帰ろう 一緒に [BOJ 5214] 환승 https://www.acmicpc.net/problem/5214 5214번: 환승 문제 아주 먼 미래에 사람들이 가장 많이 사용하는 대중교통은 하이퍼튜브이다. 하이퍼튜브 하나는 역 K개를 서로 연결한다. 1번역에서 N번역으로 가는데 방문하는 최소 역의 수는 몇 개일까? 입력 첫째 줄에 역의 수 N과 한 하이퍼튜브가 서로 연결하는 역의 개수 K, 하이퍼튜브의 개수 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ K, M ≤ 1000) 다음 M개 줄에는 하이퍼튜브의 정보가 한 줄에 하나씩 주어진다. 총 K개 숫자가 주어지며, 이 숫 www.acmicpc.net 역과 역 사이에 간선을 만들면 시간초과다. 왜냐하면 하이퍼큐브는 M개이고 하이퍼큐브가 연결하는 역의 갯수가 K인데 K(K-1)개의 간선을 M.. 이전 1 2 다음
