배열과 gcd 문제 링크 난이도가 P3보다 높아져야 하는 문제라고 생각한다. 풀이 더보기 $\mathrm{let\ }b_i=C_{i-1},\ G_i=C_i,\ b_i=B_i\times G_i.$ $\mathrm{let\ }x_i=X_i\times G_i.$ 만약 $G_i\nmid b_i$였다면 $0$을 출력하고 프로그램을 종료한다. 그러면 문제는 각 $i(\ge 2)$에 대해 $\left [1,\lfloor \frac {num} {G_i}\rfloor \right ]$ 속의 $B_i$와 서로소인 $X_i$의 개수를 구해서 전부 곱하는 문제로 바뀐다. (가능한 모든 $X_i$에 대해 $x_i$는 $a_i$로 가능한 모든 값들이다.) euler totient 함수를 변형해보겠다는 생각도 해볼 수 있지만 힘들..

링크 Cow Curling FJ의 농장에서 컬링 대회가 열렸다. 이 컬링 대회의 규칙은 일반 대회와는 조금 다르다. 겨루는 두 팀에게는 각각 $N$개의 돌이 주어진다. 만약, 한 팀의 세 개의 돌이 이루는 삼각형 내부에 상대 팀의 돌이 들어있다면, 이 돌은 포획되었다고 한다. (선분 위에 올라간 경우도 포함한다.) 각 팀의 점수는 상대 팀의 포획된 돌의 수로 계산된다. 두 팀의 돌의 배치가 2차원 평면 상의 좌표로 주어질 때, 각 팀의 점수를 계산하여라. 풀이 더보기 아이디어는 굉장히 쉽다. 그냥 각 팀의 convex hull을 각각 만들고, 상대 팀의 돌이 몇 개 들어가는지를 계산하면 된다. 이때, 볼록다각형의 내/외부점 판별 알고리즘을 이용하면 된다. 이 문제의 경우, 각 점에 대해서 따로따로 판별할..

The 22th Japanese Olympiad in Informatics Final Round Online ContestThe 22th Japanese Olympiad in Informatics Final Round Online Contest Home / The 22th Japanese Olympiad in Informatics Final Round Online Contest Overview Japanese version is available here. The 22th Japanese Olympiad in Informatics Final Round Online Contecontests.ioi-jp.org중국의 csy2005(Codeforces, AtCoder)라는 분이 500점으로 OC 1등을 차지했..

문제가 요구하는 바가 상당히 단순하다. 자력으로 푼 어려운 테크닉이 없는 첫 다이아 4 문제이다! Ob.1 ) 리프 노드는 노끈의 시작점이다. Ob.2 ) $($간선 수 - $\sum_v \left \lfloor \frac {\deg(v)}2 \right \rfloor)$가 최소 노끈 개수이다. 각 노드에서 어떻게 연결되는지를 주목하면 알 수 있는 부분. 사용할 노끈의 개수가 고정되었으니, 최소 노끈 길이만 구해주면 된다. 각 서브트리에서 어떤 노끈을 부모 노드에서 더 고려할지 같은 것들을 정해주기 위해 트리 DP를 하면 된다. 근데 이 부분을 그냥 풀 수는 없다는 것을 알 수 있고, 최대 노끈 길이를 파라메트릭 서치를 통해 고정하고서 결정 문제를 풀면 된다. 자식 노드들을 매번 정렬해주면서 풀어야 하므..

문제 링크 문제 요약 prefix와 suffix를 잡는데, prefix length + suffix length s) return true; Mp = max(Mp,p[i]); } return false; } int main() ..

문제 링크 적당히 타격감있는 기댓값 DP 문제다. divide by zero 예외를 놓치면 틀릴 수 있다. #include using namespace std; using ii = pair; using ll = long long; #define rep(i,a,b) for (auto i = (a); i = (a); --i) #define all(x) begin(x), end(x) #define siz(x) int((x).size()) #define Mup(x,y) x = max(x,y) #define mup(x,y) x = min(x,y) #define fi first #define se second #define dbg(...) fprintf(stderr,__VA_ARGS__) using ld = lon..

좋은 라운드는 아니었던 것 같습니다. 하지만 안 좋은 대회임에도 다행히 좋은 퍼포먼스를 내어서 Candidate Master로 올라갈 수 있었습니다 :) 타임 스탬프 00:04:34 A: Accepted 00:44:05 B: Accepted 01:19:37 C: Wrong answer on pretest 6 01:20:18 C: Accepted 01:49:20 D: Accepted A. Flip Flop Sum 그냥 A번 문제입니다. 코드 보기 #include using namespace std; using ii = pair; using ll = long long; #define rep(i,a,b) for (auto i = (a); i = (a); --i) #define all(x) begin(x), e..

Contest link A, B는 쉬우니 생략한다. C는 출제자의 풀이에 오류가 있었다. 그래서 contest가 unrated 되었는데, 그걸 모르고 끝까지 열심히 풀어버렸다. unrated와는 별개로 D, E, F는 마음에 들었다. 안일하게 증명 없이 셋팅한 것도 아니고, 나름대로 증명을 했다는데... 안쓰럽다. 퍼포먼스가 오렌지가 떴는데, 이걸 오렌지 퍼포먼스를 내는 데 성공했다고 봐야 할 지 모르겠다... Bit Guessing Game 최대 질의 횟수가 30이라는 점을 통해 binary notation에서 한 자리씩 찾아내면 되겠다는 생각이 든다. 만약 $1\cdots 1_{(2)}-1$을 한다면, 그 사이 digit들이 무엇이던 상관없이 $\mathrm{cnt}$가 $1$ 감소한다. 그렇지 않다..