배열과 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등을 차지했..
좋은 라운드는 아니었던 것 같습니다. 하지만 안 좋은 대회임에도 다행히 좋은 퍼포먼스를 내어서 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$ 감소한다. 그렇지 않다..
질문은 언제나 환영입니다. 어제 제 2회 곰곰컵에 참가했다. 치킨댄스를 추는 곰곰이를 본 임스 2 문제 링크 매번 D-?에서 ?만 따내서 90 이하인지 판단하여 총 개수를 구하면 된다. 더보기 #include using namespace std; #define rep(i,a,b) for (auto i = (a); i > n; rep(i,1,n) { string s; cin >> s; s = s.substr(2,siz(s)-2); if (stoi(s) > s >> t; if (st.count(s) or st.count(t)) { st.insert(s), st.insert(t); } } cout > a >> b >> c >> x >> y >> z; t = min(a,x); a -= t, x -= t; ans..
사실 지난 주에 4주차가 있었다. 지난 주는 워낙 바빴고, 주말에 갑자기 감기가 걸리는 바람에 4주차를 까먹고 안 풀었다... ㅠㅠ 5주차는 방금 풀고 왔는데, 어렵기보단 시간을 좀 잡아먹는다. 코딩 테스트처럼. 자세한 이야기는 5주차 블로그를 적게 되면 그때 하도록 하고... 아무튼 3주차 풀이! 1. 0커플 그냥 이진 탐색으로 풀었는데, 문제의 조건을 생각하면 단순 합을 통해서 구할 수도 있다. 하지만, 어떤 조건이 와도 범용적으로 사용할 수 있는 이진 탐색도 꼭 알아두면 좋겠다. 2. 폴더 폰 자판 각 버튼마다 갖는 목록을 std::string으로 잡아주면 구현이 편리하다. 각 string의 길이로 나눈 나머지를 이용하면 여러번 눌러 원래대로 돌아오는 성질도 포괄할 수 있다. 이처럼 순환되는 목록..
Contest 링크 아니 5솔을 했는데 왜 떨어져?? 기껏 C1, C2 풀고 D로 넘어간 게 억울하고, E를 아깝게 못 낸 게 슬프다. A. Technical Support 어떤 Q에 대응되는 A가 나올 때마다 Q가 해결되는 것이다. 따라서 남은 Q의 개수를 관리하면서 풀면 된다. 그냥 Q의 총 개수와 A의 총 개수를 비교하면 되는 줄 알고 풀었다가 그대로 WA... 어림도 없지... void solution(int tc) { int n; string s; cin >> n >> s; int q = 0; for (char c : s) { if (c =='Q') q++; else if (q > 0) q--; } cout > n; if (n%2) { rep(i,1,n/2+1) { cout
