AtCoder Beginner Contest 175（ABC175）

atcoder.jp

E通して命拾いした
Bondo416さんのAtCoder Beginner Contest 175での成績：839位
パフォーマンス：1576相当
レーティング：1332→1359 (+27) :)#AtCoder #ABC175 https://t.co/cHYFuVvI2b

— ボンド@競プロ (@bond_cmprog) August 15, 2020

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

こどふぉにありそう、頭壊れる
から移動して座標が最小になる移動回数はとなる
のとき、全て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をする
提出コード

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;
}