Contest info
| Title | AtCoder Begginer Contest 429 |
| Division | Beginner |
| Official | Rated |
| Rank | 1114 |
| Performance | 1436 |
| Rating | 1200 (+29) |
Problems
| # | Name | Solved |
|---|---|---|
| A | Too Many Requests | solved |
| B | N - 1 | solved |
| C | Odd One Subsequence | solved |
| D | On AtCoder Conference | solved |
| E | Hit and Away | solved |
| F | Shortest Path Query | |
| G | Sum of Pow of Mod of Linear |
Solution
A. Too Many Requests
요약
n개의 line에 i가 1~n까지 m보다 작거나 같으면 OK, 아니면 Too Many Requests 출력
풀이
for문으로 i와 m을 비교하면서 출력
B. N - 1
요약
N개의 숫자가 들어있는 배열에서 1개를 뺀 나머지의 합이 M이 되도록 만들 수 있는지
풀이
전체합-M인 요소가 있는지 확인
C. Odd One Subsequence
요약
N개의 숫자가 있는 배열 A에서, $1 \leq i < j < k leq N$인 $(i, j, k)$중 ‘$A_i, A_j, A_k$중 2개가 같고 하나가 다른’ 조합의 수를 구해라
풀이
배열에 들어있는 각 숫자별로 xC2에 그 숫자가 아닌 나머지수를 곱하면 됨.
C. Odd One Subsequence
요약
N개의 숫자가 있는 배열 A에서, $1 \leq i < j < k leq N$인 $(i, j, k)$중 ‘$A_i, A_j, A_k$중 2개가 같고 하나가 다른’ 조합의 수를 구해라
풀이
배열에 들어있는 각 숫자별로 xC2에 그 숫자가 아닌 나머지수를 곱하면 됨.
D. On AtCoder Conference
요약
원 둘레 M, 사람 N명 $x$는 연못의 둘레를 따라 시계방향으로 숫자매긴거 $i$번째 사람은 $A_i$에 있음 (한곳에 여러명이 있을 수 있음)
각 $i = 0, 1, …, M-1$별로 $X_i$는 다음과 같음
- $(i+0.5)$에서 춟라하여 시계방향으로 만난 사람이 C명 이상이 될 때 까지 이동할때, 만나는 사람 수
- 이때 모든 $X_i$의 합
풀이
N개의 사람마다 x순으로 정렬했을 때 $x_{i-1}+1~x_{i}$까지는 답이 같음. N번의 연산만에 풀이가능
E. Hit and Away
요약
N개의 노드와 M개의 엣지를 가지는 그래프 G 각 노드는 Safe와 Dangerous로 나뉘어져 있음 각 Dangerous 노드별로 한 Safe노드부터 해당 Dangerous노드를 거쳐 다른 Safe노드까지 가는 최소경로
풀이
각 Safe노드에서부터 BFS를 돌림. 각 노드는 2번까지 방문가능. 방문한 2번의 최소경로를 더한값이 정답