Contest info
| Title | AtCoder Begginer Contest 430 |
| Division | Beginner |
| Official | Rated |
| Rank | 1864 |
| Performance | 1081 |
| Rating | 1189 (-11) |
Problems
| # | Name | Solved |
|---|---|---|
| A | Candy Cookie Law | solved |
| B | Count Subgrid | solved |
| C | Truck Driver | solved |
| D | Neighbor Distance | solved |
| E | Shift String | upsolved |
| F | ||
| G |
Solution
A. Too Many Requests
요약
캔디가 A개 이상 있으면 B개 이상의 쿠키를 가지고 있어야 한다. 현재 캔디 C, 쿠키 D
풀이
비교 출력
B. Count Subgrid
요약
NxN공간에 검은색,흰색으로 칠해져있음. MxM짜리 서로 다른 패턴 개수
풀이
완전탐색, SET
C. Truck Driver
요약
A분 이상 운전하려면 최소 B분 휴식해야함 string S: [a, b] l, r 사이에 a가 A개 이상이고, b가 B개 미만인 pair 수
풀이
3포인터(?) 사용. p1: l p2: min a p3: max b
D. Neighbor Distance
요약
기본상태: 좌표0에 사람0이 서있음 N명의 사람이 순서대로 들어옴. X_i: i번째 사람 양옆의 거리 중 짧은거 각 사람이 들어올때마다 X_i의 합을 구해라
풀이
어떤 사람이 들어올때, 영향을 받는 사람은 새로 들어온 사람이 끼어든 양옆의사람임. 순서를 보존하기위해 Map사용 업데이트 마다 양옆의 사람의 최소간격을 업데이트 해줌.
E. Shift String
요약
각 테스트케이스마다 0, 1로 구성된 string A, B A의’첫번째 char을 맨뒤로 옮기는’ 작업을 0번이상 반복할 때 A=B로 만드는 최소한의 작업을 출력. 불가능하면 -1
풀이
각 테스트케이스마다, A+A에 대하여 KMP 사용