接着剤の精進日記

競プロでの精進や研究に関係したことを書いていきます。

AtCoder Grand Contest 043

atcoder.jp

AGCで微増は大勝利!

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を引いて考える
そうすると、a_iが答えに寄与する回数は _{N-1} C _iで求められる
あとは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みたいなの出してくれないかなー
競プロやってるだけで無限に数学知識増えるの楽しい