AGCで微増は大勝利!
AGCでプラスは勝ち!w
— ボンド@競プロ (@bond_cmprog) 2020年3月21日
Bondo416さんのAtCoder Grand Contest 043での成績:1285位
パフォーマンス:1332相当
レーティング:1239→1249 (+10) :)#AtCoder https://t.co/MGALs1xYCL
A - Range Flip Find Route
これ面白い
最初誤読して1点変更だと思ってWAを吐いた(そんなド典型出ないですよね)
まず「.」から「.」の移動はコストがかからない
「.」から「#」に移動するときはコスト1がかかる
今「#」にいることを考えると「#」を辿って行ける範囲は長方形区間で色を反転させて辿ることが出来るのでコスト0と考えていい
また、「#」から「.」に出るときはコスト0と考えていい
結局今自分がいる地点の色を持たせながら、上記の「.」から「#」のときだけコスト1加えてあげればいい
これはDPとかで達成可能
提出コード
int dp[111][111]; int main(){ cin.tie(0); ios::sync_with_stdio(false); int H, W; cin >> H >> W; vector<string> fi(H); REP(i,H) cin >> fi[i]; int ans = 0; queue<tuple<int, int, char>> q; q.emplace(0, 0, fi[0][0]); memset(dp, 10101010, sizeof(dp)); if(fi[0][0] == '.') dp[0][0] = 0; else dp[0][0] = 1; while(!q.empty()){ int h, w; char cur; tie(h, w, cur) = q.front(); q.pop(); if(h == H-1 && w == W-1) break; REP(i,2){ int nh = h + dx[i], nw = w + dy[i]; if(nh < 0 || nh >= H || nw < 0 || nw >= W) continue; if(cur == fi[nh][nw]){ if(chmin(dp[nh][nw], dp[h][w])){ q.emplace(nh, nw, cur); } } else{ if(cur == '#'){ if(chmin(dp[nh][nw], dp[h][w])){ q.emplace(nh, nw, fi[nh][nw]); } } else{ if(chmin(dp[nh][nw], dp[h][w] + 1)){ q.emplace(nh, nw, fi[nh][nw]); } } } } } cout << dp[H-1][W-1] + ans << endl; }
B - 123 Triangle
これ解けなかったけど面白い
本番中は「パスカルの三角形 逆 検索」とか数列を1要素ずつ回転させて演算したら出来るなーとか考えて結局計算量削れないじゃんで終わった
解説通りだけどまず各要素から1を引いて考える
そうすると、が答えに寄与する回数はで求められる
あとはLucasの定理(初めて聞いた…)からこの偶奇を求めることが出来る
ここで答えが奇数のときは答えは1に決まる
偶数のときだけ少し考えないといけなくて、まず1が出現するときは絶対2にならない
1が出現しないときは入力が0と2だけなので入力全体を2で割って、最後出た答えに2を掛けるとこの問題に答えることが出来る
提出コード
int main(){ cin.tie(0); ios::sync_with_stdio(false); int N; string S; cin >> N >> S; vector<int> a(N); bool one = false; REP(i,N){ a[i] = S[i] - '0'; a[i]--; if(a[i] & 1) one = true; } if(!one) REP(i, N) a[i] /= 2; int ans = 0; REP(i,N){ // _(n-1)C_i の偶奇 if(a[i] == 1 && ((N-1) & i) == i) ans ^= 1; } if(!one) ans *= 2; cout << ans << endl; }
おわりに
AGCだから記事が短いね(しょうがない)
今回のA好きだしBも解けなかったけど面白いなーってなってかなり満足(Bも典型詰めれば解けそうだしね)
天才パズルがAに置かれるとかなり厳しいので毎回今回のAみたいなの出してくれないかなー
競プロやってるだけで無限に数学知識増えるの楽しい