接着剤の精進日記

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

トップ > AtCoderBeginnerContest > AtCoder Beginner Contest 219（ABC219）

AtCoder Beginner Contest 219（ABC219）

AtCoderBeginnerContest AtCoderBeginnerContest219 ABC ABC219

atcoder.jp

A - AtCoder Quiz 2

場合分けをする
提出コード

void solve(){
    int X;
    cin >> X;
    if(X < 40) cout << 40 - X << endl;
    else if(X < 70) cout << 70 - X << endl;
    else if(X < 90) cout << 90 - X << endl;
    else cout << "expert" << endl;
}

B - Maritozzo

問題文のとおりに出力する
提出コード

void solve(){
    vector<string> s(3);
    REP(i,3) cin >> s[i];
    string T;
    cin >> T;
    for(char c : T) cout << s[c-'1'];
    cout << endl;
}

C - Neo-lexicographic Ordering

自分でソートの比較関数を定義するか、一旦通常のアルファベット順に変換しソートした後にもとに戻す
提出コード

void solve(){
    string X;
    cin >> X;
    map<char, int> mp;
    REP(i,26) mp[X[i]] = i;
    int N;
    cin >> N;
    vector<string> S(N);
    REP(i,N) cin >> S[i];
    vector<string> vs(N);
    REP(i,N){
        string t;
        REP(j,S[i].size()) t += char('a' + mp[S[i][j]]);
        vs[i] = t;
    }
    sort(vs.begin(), vs.end());
    REP(i,N){
        REP(j,vs[i].size()) cout << X[vs[i][j] - 'a'];
        cout << endl;
    }
}

D - Strange Lunchbox

$ dp[i][j] := $ たこ焼きを $ i $ 個、たい焼きを $ j $ 個にするのに必要な弁当の最小個数としてDPをする
たこ焼きとたい焼きのそれぞれで $ X, Y $ を超えるような遷移に気をつける
提出コード

void solve(){
    int N, X, Y;
    cin >> N >> X >> Y;
    vector<int> A(N), B(N);
    REP(i,N) cin >> A[i] >> B[i];
    vector dp(333, vector(333, INF));
    dp[0][0] = 0;
    REP(i,N){
        vector nxt(333, vector(333, INF));
        REP(x, 333) REP(y, 333) if(dp[x][y] < INF){
            chmin(nxt[x][y], dp[x][y]);
            chmin(nxt[min(300, x + A[i])][min(300, y + B[i])], dp[x][y] + 1);
        }
        swap(dp, nxt);
    }
    int ans = INF;
    for(int x=X;x<333;x++) for(int y=Y;y<333;y++) chmin(ans, dp[x][y]);
    cout << (ans == INF ? -1 : ans) << endl;
}

E - Moat

お堀で囲むマス目をbit全探索する
マス目を決めたときのお堀の囲み方は一意に決まるので、この囲み方が条件を満たすかをチェックする
囲まれた中に全ての村が含まれるかつ、お堀で囲まれていないところと囲まれている箇所がそれぞれ2つの領域に分かれていればいい
後者は $ A $ の周りに空白マスを加えた $ 6 \times 6 $ のマス目上で、囲まれている箇所と囲まれていない箇所で連結したとき、全体の連結成分の個数が2個になっていればいい
提出コード

void solve(){
    const int N = 4;
    const int M = 6;
    vector A(M, vector(M, 0));
    int cnt_A = 0;
    REP(i,N) REP(j,N){
        cin >> A[i+1][j+1];
        if(A[i+1][j+1] == 1) cnt_A++;
    }
    int ans = 0;
    REP(i,1<<(N*N)){
        vector B(M, vector(M, 0));
        int cnt = 0;
        REP(j,N*N) if(i >> j & 1){
            int x = j / N;
            int y = j % N;
            B[x+1][y+1] = 1;
            if(A[x+1][y+1] == 1) cnt++;
        }
        UnionFind uf(M*M);
        REP(i,M) REP(j,M){
            REP(d,4){
                int ni = i + dx[d];
                int nj = j + dy[d];
                if(ni < 0 or ni >= M or nj < 0 or nj >= M) continue;
                if(B[i][j] == B[ni][nj]) uf.unite(i * M + j, ni * M + nj);
            }
        }
        set<int> st;
        REP(i,M) REP(j,M) st.insert(uf.root(i * M + j));
        if(cnt == cnt_A and st.size() == 2) ans++;
    }
    cout << ans << endl;
}