AtCoder Beginner Contest 157（ABC157）

atcoder.jp

レートが1300台になりました、嬉しい
青パフォがまた出ませんでした。悲しい
C提出した瞬間BがWAになってるのに気づいてそのCもWAになって心臓に悪かったね…

1300乗った～（青パフォがギリギリでてなくて泣いちゃった）
Bondo416さんのAtCoder Beginner Contest 157での成績：557位
パフォーマンス：1592相当
レーティング：1277→1313 (+36) :)
Highestを更新しました！#AtCoder https://t.co/gTp4VIW2Sv

— ボンド@競プロ (@bond_cmprog) 2020年3月1日

A - Duplex Printing

最近のA難しめな気がしてたからこれは優しい
をしてあげます
提出コード

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    cout << (N + 1) / 2 << endl;
}

B - Bingo

頑張って実装する
縦、横、斜めでやるのが一番楽そう？
提出コード

int A[3][3];
bool ok[3][3];

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    REP(i,3) REP(j,3) cin >> A[i][j];
    int N;
    cin >> N;
    REP(i,N){
        int b;
        cin >> b;
        REP(j,3) REP(k,3) if(A[j][k] == b) ok[j][k] = true;
    }
    bool bingo = false;
    REP(i,3){
        int cnt = 0;
        REP(j,3) if(ok[i][j]) cnt++;
        if(cnt >= 3) bingo = true;
    }
    REP(j,3){
        int cnt = 0;
        REP(i,3) if(ok[i][j]) cnt++;
        if(cnt >= 3) bingo = true;
    }
    int cnt = 0;
    REP(i,3) if(ok[i][i]) cnt++;
    if(cnt >= 3) bingo = true;
    cnt = 0;
    if(ok[0][2] && ok[1][1] && ok[2][0]) bingo = true;

    if(bingo) cout << "Yes" << endl;
    else cout << "No" << endl;
}

C - Guess The Number

3　ペ　ナ　生　や　し　た　笑
まずある桁に異なる値の条件が存在したら -1 になる
それ以外の場合で、の時1桁目に0の条件があれば -1
それ以外は作れるので作る
各桁に条件が指定されていればそれを出力する。
指定されてなければ、1桁目だけ1、それ以降は0を出力
ただし、 かつ のときは0を出力（3敗）
提出コード

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, M;
    cin >> N >> M;
    vector<int> v(N, -1);
    bool ok = true;
    REP(i,M){
        int s, c;
        cin >> s >> c;
        --s;
        if(v[s] == -1){
            v[s] = c;
        }
        else if(v[s] != c){
            ok = false;
        }
    }

    if(!ok) cout << -1 << endl;
    else{
        if(N == 1){
            if(M == 0) cout << 0 << endl;
            else cout << v[0] << endl;
        }
        else{
            if(v[0] == 0) cout << -1 << endl;
            else{
                REP(i,N){
                    if(v[i] != -1) cout << v[i];
                    else{
                        if(i == 0) cout << 1;
                        else cout << 0;
                    }
                }
                cout << endl;
            }
        }
    }
}

D - Friend Suggestions

読解が難しかった
よくわかってないけどこういうのはUnionFindで管理すればいけそーって言って解法ガチャしました（ごめんなさい）
友達関係にあるものをUnionFindで繋げていくと、その時点での友達候補の数は
になる（ はiの友達の数）
後はブロック関係にある人が友達候補の場合、候補から引けばそれが答え
提出コード

struct UnionFind {
    vector<int> par;
    
    UnionFind(int n) : par(n, -1) { }
    void init(int n) { par.assign(n, -1); }
    
    int root(int x) {
        if (par[x] < 0) return x;
        else return par[x] = root(par[x]);
    }
    
    bool issame(int x, int y) {
        return root(x) == root(y);
    }
    
    bool unite(int x, int y) {
        x = root(x); y = root(y);
        if (x == y) return false;
        if (par[x] > par[y]) swap(x, y);
        par[x] += par[y];
        par[y] = x;
        return true;
    }
    
    int size(int x) {
        return -par[root(x)];
    }
};

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, M, K;
    cin >> N >> M >> K;
    UnionFind uf(N);
    vector<int> ans(N);
    vector<int> friends(N);
    REP(i,M){
        int A, B;
        cin >> A >> B;
        A--, B--;
        uf.unite(A, B);
        friends[A]++;
        friends[B]++;
    }

    REP(i,N) ans[i] = uf.size(i) - 1 - friends[i];

    REP(i,K){
        int A, B;
        cin >> A >> B;
        A--, B--;
        if(uf.issame(A, B)) ans[A]--, ans[B]--;
    }

    REP(i,N) cout << ans[i] << " ";
    cout << endl;
}

E - Simple String Queries

こどふぉっぽくない？こどふぉで似たようなのあった気がする
TL見たらセグ木セグ木でびっくりしちゃった
bitで管理して持つの賢いなーってなったのでセグ木でも通しておきたい
やったこととしては、各文字ごとに出現するindexをsetで持っておく
のときは元の文字のindexをeraceして新しい文字のindexをinsertする
のときは各文字ごとににぶたんして区間に含まれるかを数えてあげる
提出コード

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, Q;
    string S;
    vector<set<int>> idx(26);
    REP(i, 26) idx[i].insert(INF);
    cin >> N >> S >> Q;
    REP(i,N) idx[S[i]-'a'].insert(i);
    while(Q--){
        int q, l, r;
        char c;
        cin >> q;
        if(q == 1){
            cin >> l >> c;
            l--;
            idx[S[l]-'a'].erase(l);
            S[l] = c;
            idx[c-'a'].insert(l);
        }
        else{
            cin >> l >> r;
            l--, r--;
            int cnt = 0;
            REP(i,26){
                auto itr = idx[i].lower_bound(l);
                if(*itr <= r) cnt++;
            }
            cout << cnt << endl;
        }
    }
}

F - Yakiniku Optimization Problem

全然わかりませんでした
半分全列挙して上手い具合にマージできるのかなーとか考えてました
解説見たら全然違ったので幾何精進しなきゃ

おわりに

C通した時30分4ペナとかだったので焦った〜
Dぱっと見わからなくてE行ってすぐ解けたので落ち着けたのは良かったかな
5完早解き勝負は全然勝てないなあ頑張らないと