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$ 감소한다. 그렇지 않다..
질문은 언제나 환영입니다. 어제 제 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
