接着剤の精進日記

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

トップ > AtCoderBeginnerContest > AtCoder Beginner Contest 237（ABC237）

AtCoder Beginner Contest 237（ABC237）

AtCoderBeginnerContest AtCoderBeginnerContest237 ABC ABC237

atcoder.jp

A - Not Overflow

実際に比較する

提出コード

void solve(){
    ll N;
    cin >> N;
    const ll lower = -(1LL << 31);
    const ll upper = 1LL << 31;
    if(lower <= N and N < upper) cout << "Yes" << endl;
    else cout << "No" << endl;
}

B - Matrix Transposition

$ B_{i,j} = A_{j,i} $ となるのでこれを出力する

提出コード

void solve(){
    int H, W;
    cin >> H >> W;
    vector<vector<int>> mat(H, vector<int>(W));
    REP(i,H) REP(j,W) cin >> mat[i][j];
    REP(i,W){
        REP(j,H) cout << mat[j][i] << " ";
        cout << endl;
    }
}

C - kasaka

先頭と末尾の a が一致している間それらを削除し、削除後の文字列 $ T $ を考える
この時点で回文ならばYes
そうでない場合、$ T $ の末尾の aの数だけ先頭にaを追加し、その文字列が回文ならばYes、そうでないならNoとなる

提出コード

void solve(){
    string S;
    cin >> S;
    int N = S.size();
    int cnt = 0;
    REP(i,N){
        if(S[i] == 'a' and S[N-i-1] == 'a') cnt++;
        else break;
    }
    string T = "";
    for(int i = cnt;i < N - cnt;i++) T += S[i];
    string U = T;
    reverse(ALL(U));
    if(T == U){
        cout << "Yes" << endl;
        return;
    }
    int cnt2 = 0;
    for(int i=(int)T.size()-1;i>=0;i--){
        if(T[i] == 'a') cnt2++;
        else break;
    }
    U = string(cnt2, 'a') + T;
    string V = U;
    reverse(ALL(V));
    if(U == V) cout << "Yes" << endl;
    else cout << "No" << endl;

D - LR insertion

$ i $ の左側にある数と右側にある数を配列で管理をする
$ i $ を挿入する際には、$ i $ の挿入する位置の左にある数と右にある数のみなので、挿入するたびにその分を更新していく

提出コード

void solve(){
    int N;
    cin >> N;
    string S;
    cin >> S;
    vector<pair<int, int>> vp(N+1, {-1, -1});
    REP(i,N){
        char c = S[i];
        if(c == 'L'){
            int l = vp[i].first;
            if(l == -1){
                vp[i].first = i+1;
                vp[i+1].second = i;
            }
            else{
                vp[i+1].first = l;
                vp[i+1].second = i;
                vp[l].second = i+1;
                vp[i].first = i+1;
            }
        }
        else{
            int r = vp[i].second;
            if(r == -1){
                vp[i].second = i+1;
                vp[i+1].first = i;
            }
            else{
                vp[i+1].second = r;
                vp[i+1].first = i;
                vp[r].first = i+1;
                vp[i].second = i+1;
            }
        }
    }
    int start = -1;
    REP(i,N+1) if(vp[i].first == -1) start = i;
    int nxt = start;
    while(nxt != -1){
        cout << nxt << " ";
        nxt = vp[nxt].second;
    }
    cout << endl;
}

E - Skiing

楽しさの $ -1 $ 倍したものをコストとしたグラフでのダイクストラを行うことを考える
このグラフ上では、$ H_i \lt H_j $ のとき、コストは $ H_i - H_j \lt 0 $ と負になる場合がある
そのため、ポテンシャルを用いてダイクストラを適用できるようにする
$ i \rightarrow j $ に移動するときのコストを元のコスト $ c $ を用いて $ c’ = c + (H_i - H_j) $ とすると、$ H_i \gt H_j $ のとき、$ i \rightarrow j $ の辺はコスト $ 0 $、 $ j \rightarrow i $ の辺はコスト $ H_i - H_j $ となるので負の辺がないこのグラフ上でダイクストラを行う

提出コード

void solve(){
    int N, M;
    cin >> N >> M;
    vector<ll> H(N);
    REP(i,N) cin >> H[i];
    vector<vector<int>> g(N);
    REP(i,M){
        int u, v;
        cin >> u >> v;
        g[--u].emplace_back(--v);
        g[v].emplace_back(u);
    }
    priority_queue<LP, vector<LP>, greater<LP>> pq;
    vector<ll> dist(N, LINF);
    dist[0] = 0;
    pq.emplace(0, 0);
    while(!pq.empty()){
        auto [d, v] = pq.top(); pq.pop();
        if(d < dist[v]) continue;
        for(auto nv : g[v]){
            ll nxt = max(H[nv] - H[v], 0LL);
            if(chmin(dist[nv], dist[v] + nxt)){
                pq.emplace(dist[nv], nv);
            }
        }
    }
    ll ans = 0;
    REP(i,N) chmax(ans, H[0] - H[i] - dist[i]);
    cout << ans << endl;
}

F - |LIS| = 3

長さ3のLISを求める際のDP配列をキーとしてDPを行えばよい
$ dp[i][j][k][l] := i $ まで見た時に、長さ1、2、3の増加部分列の右端になるものの最小値がそれぞれ$ j, k, l $ のときの数列の個数としてDPを行う

提出コード

void solve(){
    int N, M;
    cin >> N >> M;
    vector dp(N+1, vector(M+1, vector(M+1, vector<mint>(M+1, 0))));
    dp[0][M][M][M] = 1;
    REP(i,N) REP(j,M+1) REP(k,M+1) REP(l,M+1){
        REP(x,M){
            if(x <= j) dp[i+1][x][k][l] += dp[i][j][k][l];
            else if(x <= k) dp[i+1][j][x][l] += dp[i][j][k][l];
            else if(x <= l) dp[i+1][j][k][x] += dp[i][j][k][l];
        }
    }
    mint ans = 0;
    REP(i,M) REP(j,i+1,M) REP(k,j+1,M) ans += dp[N][i][j][k];
    cout << ans << endl;
}