接着剤の精進日記

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

AtCoder Beginner Contest 175(ABC175)

atcoder.jp

A - Rainy Season

RLEを貼ります()
提出コード

void solve(){
    string s;
    cin >> s;
    int ans = 0;
    auto res = runLengthEncoding(s);
    for(auto [c, cnt] : res) if(c == 'R') chmax(ans, cnt);
    cout << ans << endl;
}

B - Making Triangle

重複に気をつけて3重ループで三角形が作れるかどうか判定
ソートしたほうが楽だった気がする
提出コード

void solve(){
    int N;
    cin >> N;
    vector<ll> L(N);
    REP(i,N) cin >> L[i];
    int ans = 0;
    REP(i,N) for(int j=i+1;j<N;j++) for(int k=j+1;k<N;k++){
        if(L[i] == L[j] or L[i] == L[k] or L[j] == L[k]) continue;
        ll ma = max({L[i], L[j], L[k]});
        ll t = L[i] + L[j] + L[k] - ma;
        if(t > ma) ans++;
    }
    cout << ans << endl;
}

C - Walking Takahashi

こどふぉにありそう、頭壊れる
|X|から移動して座標が最小になる移動回数はneed = \frac{|X|}{D}となる
need \gt Kのとき、全て0に近くなるように移動する
それ以外の場合、残り回数の偶奇で決まる
提出コード

void solve(){
    ll X, K, D;
    cin >> X >> K >> D;
    ll need = abs(X) / D;
    ll cur = abs(abs(X) - abs(need*D));
    if(need > K){
        cout << abs(abs(X) - abs(K * D)) << endl;
        return;
    }
    K -= need;
    if(K % 2 == 0) cout << cur << endl;
    else{
        cur -= D;
        cout << abs(cur) << endl;
    }
}

D - Moving Piece

実装で死んでしまった
最初へんてこ辞書だなーって思ってたけどサイクルにパスが生えたようなのは出来ないので全部最初からサイクルと考えてもいい(全然考えてなかった)
そうすると、始点とループの途中でやめる終点を全探索すればいい
また、ループを周回して得られるスコアが正なら周回できる分を考慮すればいい
提出コード

void solve(){
    ll N, K;
    cin >> N >> K;
    vector<int> P(N);
    vector<ll> C(N);
    REP(i,N){
        cin >> P[i];
        --P[i];
    }
    REP(i,N) cin >> C[i];
    ll ans = -LINF;
    REP(i,N){
        int cur = i;
        vector<int> loop;
        ll sum = 0;
        while(1){
            cur = P[cur];
            sum += C[cur];
            loop.emplace_back(C[cur]);
            if(cur == i) break;
        }
        ll tmp = 0;
        ll sz = size(loop);
        REP(j,sz){
            tmp += loop[j];
            if(j+1 > K) break;
            if(sum > 0){
                ll cnt = (K - (j + 1)) / sz;
                chmax(ans, sum * cnt + tmp);
            }
            chmax(ans, tmp);
        }
    }
    cout << ans << endl;
}

E - Picking Goods

dp[i][j][k]:=(i, j)に居て、i行目でk個アイテムを拾ったときの最大値
としてDPをする
提出コード

void solve(){
    int R, C, K;
    cin >> R >> C >> K;
    vector<vector<ll>> fi(R+10, vector<ll>(C+10));
    REP(i,K){
        int r, c, v;
        cin >> r >> c >> v;
        fi[r][c] = v;
    }
    vector<vector<vector<ll>>> dp(3030, vector<vector<ll>>(3030, vector<ll>(5)));

    for(int i=1;i<=R;i++) for(int j=1;j<=C;j++) REP(k,4){
        if(i < R){
            chmax(dp[i+1][j][0], dp[i][j][k]);
            if(k < 3) chmax(dp[i+1][j][0], dp[i][j][k] + fi[i][j]);
        }
        if(j < C){
            chmax(dp[i][j+1][k], dp[i][j][k]);
            if(k < 3) chmax(dp[i][j+1][k+1], dp[i][j][k] + fi[i][j]);
        }
    }
    ll ans = dp[R][C][3];
    REP(k,3) chmax(ans, dp[R][C][k] + fi[R][C]);
    cout << ans << endl;
}