AtCoder Beginner Contest 175 感想 - スコルの知恵袋

atcoder.jp

ひっさしぶりの温まり！
scolさんのAtCoder Beginner Contest 175での成績：326位
パフォーマンス：1961相当
レーティング：1478→1537 (+59) :)#AtCoder #ABC175 https://t.co/fdEjhCyq4g
— scol (@scol_kp) 2020年8月15日

久しぶりあたたまった。やったね！

AtCoderは7月の中旬からレート減少streakが続いていてほんとうにつらかった。

A - Rainy Season

提出コード

リンク： https://atcoder.jp/contests/abc175/submissions/15908798

void solve() {
    string S;
    cin >> S;
    ll ans = 0;
    ll cnt = 0;
    for (ll i = 0; i < 3; i++) {
        if (S[i] == 'R') {
            ++cnt;
        }
        else {
            ans = max(ans, cnt);
            cnt = 0;
        }
    }
    if (cnt) {
        ans = max(ans, cnt);
    }
    prints()(ans);
}

B - Making Triangle

三角形の成立条件の問題流行ってんな。この前のこどふぉでも出た。

提出コード

リンク： https://atcoder.jp/contests/abc175/submissions/15916015

void solve() {
    ll N;
    cin >> N;
    Vl L(N);
    for (ll i = 0; i < N; i++) {
        cin >> L[i];
    }
    ll ans = 0;
    for (ll i = 0; i < N; i++) {
        for (ll j = i + 1; j < N; j++) {
            for (ll k = j + 1; k < N; k++) {
                if (L[i] != L[j] && L[j] != L[k] && L[k] != L[i]) {
                    if (L[i] + L[j] > L[k] && L[j] + L[k] > L[i] && L[k] + L[i] > L[j]) {
                        ++ans;
                    }
                }
            }
        }
    }
    prints()(ans);
}

C - Walking Takahashi

こどふぉDiv.2のAかBに出てきそうな問題。

$X$ が負の時は $X \leftarrow -X$ と符号を反転してやると実装が楽。

提出コード

リンク： https://atcoder.jp/contests/abc175/submissions/15920941

void solve() {
    ll X, K, D;
    cin >> X >> K >> D;
    if (X < 0) X = -X;
    ll a = X / D;
    if (K < a) {
        prints()(X - K * D);
    }
    else {
        if ((K - a) & 1) {
            prints()((a + 1) * D - X);
        }
        else {
            prints()(X - a * D);
        }
    }
}

D - Moving Piece

ループを全列挙してその中で「どの位置からスタートするか」を動かしながら全探索する。

ループとスタート位置を固定したとき：

ループ一周のスコアの和が0以下のときはをループ長として以下のいずれかが最適：
- スタート地点から $1$ 番目 or $2$ 番目 or ... or $K\%m$ 番目まで動く
ループ一周のスコアの和が正のときはをループ長として以下のいずれかが最適：
- $\left(\left\lfloor \frac{K}{m} \right\rfloor - 1\right)$ 周 + スタート地点から $(K\%m + 1)$ 番目 or $(K\%m + 2)$ 番目 or ... or $m$ 番目まで動く
- $\left\lfloor \frac{K}{m} \right\rfloor$ 周 + スタート地点から $1$ 番目 or $2$ 番目 or ... or $K\%m$ 番目まで動く

計算量は $O(N^2)$ 。

ループ一周のスコアの和が正のときの場合分けが不十分でWAを1回出してしまった。もったいない......。

ループ内の部分和とかを管理するにはループ1周分の配列を2つ繋げたものを使うのが便利だね。

それにしても実装ぐっちゃぐちゃで草。

提出コード

リンク： https://atcoder.jp/contests/abc175/submissions/15940223

void solve() {
    ll N, K;
    cin >> N >> K;
    Vl P(N), C(N);
    for (ll i = 0; i < N; i++) {
        cin >> P[i];
        --P[i];
    }
    for (ll i = 0; i < N; i++) {
        cin >> C[i];
    }
    vector<Vl> roops;
    Vl ts;
    vector<bool> used(N);
    for (ll i = 0; i < N; i++) {
        if (used[i]) continue;
        ts.clear();
        ll idx = i;
        while (!used[idx]) {
            ts.emplace_back(C[idx]);
            used[idx] = true;
            idx = P[idx];
        }
        roops.emplace_back(Vl());
        Vl& target = roops.back();
        target.insert(target.end(), ts.begin(), ts.end());
        target.insert(target.end(), ts.begin(), ts.end());
    }
    ll ans = -L_INF;
    Vl cum;
    for (const auto& vec : roops) {
        ll n = (ll)vec.size() / 2;
        cum.assign(n * 2 + 1, 0);
        for (ll i = 0; i < n * 2; i++) {
            cum[i + 1] = cum[i] + vec[i];
        }
        ll mx = -L_INF;
        ll b = K % n;
        ll c = K / n;
        if (b == 0) {
            b = n;
            --c;
        }
 
        for (ll i = 0; i < n; i++) {
            ll t = -L_INF;
            for (ll j = i + 1; j <= i + b; j++) {
                t = max(t, cum[j] - cum[i]);
            }
            mx = max(mx, t);
        }
        if (cum[n] > 0) {
            mx += c * cum[n];
        }
        ans = max(ans, mx);
 
        if (b != n) {
            mx = -L_INF;
            for (ll i = 0; i < n; i++) {
                ll t = -L_INF;
                for (ll j = i + b + 1; j <= i + n; j++) {
                    t = max(t, cum[j] - cum[i]);
                }
                mx = max(mx, t);
            }
            if (cum[n] > 0) {
                mx += (c - 1) * cum[n];
            }
            ans = max(ans, mx);
        }
    }
    prints()(ans);
}

E - Picking Goods

dp[i][j][k] := (マス (i, j) に居て、その行で k 個のアイテムを拾ったときのスコアの最大値)

を持ってDP。

Dより簡単に感じた。DとE逆では？？

提出コード

リンク： https://atcoder.jp/contests/abc175/submissions/15949858

ll dp[3010][3010][4];
ll cell[3010][3010];
 
void solve() {
    ll R, C, K;
    cin >> R >> C >> K;
    for (ll i = 0; i < K; i++) {
        ll a, b, c;
        cin >> a >> b >> c;
        --a, --b;
        cell[a][b] = c;
    }
 
    for (ll i = 0; i <= R; i++) {
        for (ll j = 0; j <= C; j++) {
            for (ll k = 0; k <= 3; k++) {
                dp[i][j][k] = -L_INF;
            }
        }
    }
    dp[0][1][0] = dp[1][0][0] = 0;
 
    for (ll i = 1; i <= R; i++) {
        for (ll j = 1; j <= C; j++) {
            for (ll k = 0; k <= 3; k++) {
                dp[i][j][k] = dp[i][j - 1][k];
                if (k == 0) {
                    dp[i][j][k] = max(dp[i][j][k], dp[i - 1][j][0]);
                    dp[i][j][k] = max(dp[i][j][k], dp[i - 1][j][1]);
                    dp[i][j][k] = max(dp[i][j][k], dp[i - 1][j][2]);
                    dp[i][j][k] = max(dp[i][j][k], dp[i - 1][j][3]);
                }
                if (cell[i - 1][j - 1] > 0 && k == 1) {
                    dp[i][j][k] = max(dp[i][j][k], dp[i - 1][j][0] + cell[i - 1][j - 1]);
                    dp[i][j][k] = max(dp[i][j][k], dp[i - 1][j][1] + cell[i - 1][j - 1]);
                    dp[i][j][k] = max(dp[i][j][k], dp[i - 1][j][2] + cell[i - 1][j - 1]);
                    dp[i][j][k] = max(dp[i][j][k], dp[i - 1][j][3] + cell[i - 1][j - 1]);
                }
                if (cell[i - 1][j - 1] > 0 && k > 0) {
                    dp[i][j][k] = max(dp[i][j][k], dp[i][j - 1][k - 1] + cell[i - 1][j - 1]);
                }
            }
        }
    }
 
    ll ans = 0;
    for (ll i = 0; i <= 3; i++) {
        ans = max(ans, dp[R][C][i]);
    }
    prints()(ans);
 
    // for (ll k = 0; k <= 3; k++) {
    //     for (ll i = 0; i <= R; i++) {
    //         for (ll j = 0; j <= C; j++) {
    //             cout << dp[i][j][k] << " ";
    //         }
    //         cout << "\n";
    //     }
    //     cout << "\n";
    // }
}

F - Making Palindrome

うーん、わからず。