AtCoder Beginner Contest 147 （ABC147）

4完2WAでパフォ1372で無事水復帰した〜
色々事故ってレート100位落としたけど一回水タッチしてたら戻せるね、また落としたくないけど

ただいま水色
Bondo416さんのAtCoder Beginner Contest 147での成績：907位
パフォーマンス：1372相当
レーティング：1196→1215 (+19) :)
Highestを更新しました！#AtCoder https://t.co/EzjKqNdGqW pic.twitter.com/8rXAyqh3VK

— ボンド@競プロ (@bond_cmprog) 2019年12月8日

A - Blackjack

sum >= 22ならbust それ以外はwin
ところで、Text(cat)で提出して1WAしました（ええ…）
提出コード

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int sum = 0;
    REP(i,3){
        int a;
        cin >> a;
        sum += a;
    }
    if(sum >= 22) cout << "bust" << endl;
    else cout << "win" << endl;
}

B - Palindrome-philia

N/2までS[i]とS[N-1-i]が一致しているかどうかを見ていく
提出コード

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    string S;
    cin >> S;
    int n = S.size();
    int cnt = 0;
    for(int i=0;i<n/2;i++){
        if(S[i] != S[n-1-i]) cnt++;
    }
    cout << cnt << endl;
}

C - HonestOrUnkind2

読解に少し手間取った
ある人が正直者かどうかを仮定して、矛盾が出なければOKという風に考える
Nが15までなのでこれはbit全探索で全ての場合について列挙出来る
後は、bit全探索で立っているbitを正直者として判定を行っていく
最初不親切な人は嘘をついていると思ってました
提出コード

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    vector<vector<pair<int,int>>> A(N);
    REP(i,N){
        int a;
        cin >> a;
        REP(j,a){
            int x, y;
            cin >> x >> y;
            --x;
            A[i].emplace_back(x,y);
        }
    }
    int ans = 0;
    for(int i=0;i<(1<<N);i++){
        int tmp = 0;
        bool ok = true;
        REP(j,N){
            if((i>>j) & 1){
                tmp++;
                REP(k,A[j].size()){
                    int x = A[j][k].first;
                    int y = A[j][k].second;
                    if((i>>x) & 1){
                        if(y == 0){
                            ok = false;
                            break;
                        }
                    }
                    else{
                        if(y == 1){
                            ok = false;
                            break;
                        }
                    }
                }
            }
        }
        //cout << i << " " << tmp << " " << ok << endl;
        if(ok) chmax(ans, tmp);
    }
    cout << ans << endl;
}

D - Xor Sum 4

問題名でビビり、問題文でビビる
XORの問題では各桁を独立に考えられるので、まずそうしてみる
XORをする時、両方ともbitが立っていれば0、そうでなければ1になるので、各桁のbitが何個立っているかを予め持っておけば、計算量を削減できる
予め各桁のbitの個数を求めておき、前から順に総和を求めていき、見た数字のbitを引いていく
提出コード

ll mod_pow(ll x, ll n, ll mod){
    ll res = 1;
    while(n > 0){
        if(n & 1) res = res * x % mod;
        x = x * x % mod;
        n >>= 1;
    }
    return res;
}

int bit[60];
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    vector<ll> a(n);
    for(int i=0;i<n;i++){
        cin >> a[i];
        REP(j,60){
            if((a[i]>>j) & 1) bit[j]++;
        }
    }

    ll ans = 0;
    int rest = n-1;
    //REP(j,60) cout << bit[j] << " ";
    //cout << endl;
    REP(i,n){
        REP(j,60){
            if((a[i]>>j) & 1){
                bit[j]--;
                ans += (mod_pow(2, j, MOD) * (rest - bit[j]));
                ans %= MOD;
            }
            else{
                if(bit[j] > 0){
                    ans += (mod_pow(2, j, MOD) * bit[j]);
                    ans %= MOD;
                }
            }
        }
        rest--;
    }
    cout << ans << endl;

}

E - Balanced Path

時間使いすぎてコンテスト中に解けなかった
ぱっと見こういうのはDPなんだろうなーと思う
ぐっと睨むと差の絶対値を取ると良さそうとなる
その後DPがどっかに行き最短経路っぽいなーと思いながら最短経路と復元を頑張るもサンプルが合わず終了
全然最短経路ではなく、DPで出来る
ほぼ解説の通りで、（i, j)に来たときに偏りがkになるかどうかをbool値で持ってDPしてあげればいい
やっている事自体はそこまで難しくなかったので、本番中通したかったね
提出コード

bool dp[88][88][2*80*88];

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int H, W;
    cin >> H >> W;
    vector<vector<int>> a(H, vector<int>(W)), b(H, vector<int>(W));
    REP(i,H) REP(j,W) cin >> a[i][j];
    REP(i,H) REP(j,W) cin >> b[i][j];
    dp[0][0][abs(a[0][0] - b[0][0])] = true;

    REP(i,H) REP(j,W){
        REP(k,2*80*88){
            if(i>0){
                if(dp[i-1][j][k]){
                    dp[i][j][k+abs(a[i][j]-b[i][j])] = true;
                    dp[i][j][abs(k-abs(a[i][j]-b[i][j]))] = true;
                }
            }
            if(j>0){
                if(dp[i][j-1][k]){
                    dp[i][j][k+abs(a[i][j]-b[i][j])] = true;
                    dp[i][j][abs(k-abs(a[i][j]-b[i][j]))] = true;
                }
            }
        }
    }

    REP(i,2*80*88){
        if(dp[H-1][W-1][i]){
            cout << i << endl;
            return 0;
        }
    }
}

制約が結構きついのでbitsetを使うと良いらしい
使ってみたら240msが22msになってめちゃくちゃ早いね
提出コード

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int H, W;
    cin >> H >> W;
    vector<vector<int>> a(H, vector<int>(W));
    vector<vector<int>> b(H, vector<int>(W));
    REP(i,H) REP(j,W) cin >> a[i][j];
    REP(i,H) REP(j,W) cin >> b[i][j];
    vector<vector<bitset<2*80*88>>> dp(H, vector<bitset<2*80*88>>(W));
    dp[0][0][abs(a[0][0]-b[0][0])+6400] = 1;
    REP(i,H) REP(j,W){
        if(i > 0){
            dp[i][j] |= (dp[i-1][j] << abs(a[i][j] - b[i][j]));
            dp[i][j] |= (dp[i-1][j] >> abs(a[i][j] - b[i][j]));
        }
        if(j > 0){
            dp[i][j] |= (dp[i][j-1] << abs(a[i][j] - b[i][j]));
            dp[i][j] |= (dp[i][j-1] >> abs(a[i][j] - b[i][j]));
        }
    }
    int ans = INF;
    REP(i,2*80*88){
        if(dp[H-1][W-1][i]){
            chmin(ans, abs(6400-i));
        }
    }
    cout << ans << endl;
}

おわりに

Cでちょっと焦って、Dも苦手意識多くて解けないかと思ったけどなんとか通せてよかった
ただ、Eは解けないといけない問題だったと思うのでそこは反省
無事水色復帰できたので、このまま水色真ん中までは伸ばしたいね