AtCoder：ABC139の振り返り

ABC139に参加したのでその振り返りです．今回はE問題まで解くことができました！ゴリゴリの競プロ的な問題ではなかったのがよかったのかな？？と思います．まだまだ典型的なアルゴリズムや基本的な発想が身についていないので，今回のD問題やE問題のような数学的な問題の方が解きやすく感じます．

A問題

単純に３文字を比較するだけでした．

#include <iostream>
#include <vector>
#include <cmath>
#include <iomanip>
#include <string>

using namespace std;

typedef long long ll;

int main() {
    string s, t; cin >> s >> t;
    int res = 0;
    if (s[0] == t[0]) res++;
    if (s[1] == t[1]) res++;
    if (s[2] == t[2]) res++;
    cout << res << endl;
}

B問題

最初，１口のときを考えていなくてWAが出てしまいました．もったいない！
場合分けしない方が良いと思いますが，へんに書き直すより場合分けで追加した方が良いかなと思ったのでこんな感じのコードになりました．

#include <iostream>
#include <vector>
#include <cmath>
#include <iomanip>

using namespace std;

typedef long long ll;

int main() {
    int a, b; cin >> a >> b;
    if (b == 1) {
        cout << 0 << endl;
        return 0;
    }
    int tap = a, res = 1;

    while (tap < b) {
        tap += a - 1;
        res++;
    }
    cout << res << endl;
    return 0;
}

C問題

一つ右の階段での最大移動回数がわかれば，今の最大移動回数がわかるので（高さが右以上であれば+1，右より下であれば0）後ろからDPみたいな感じで回していけばO(N)，その中で最大のものを探索してもO(N)だと思ってその方針で行きました．比較的すんなり解けて，この問題終わった時点で15分くらいだったので，次以降の問題につながったと思います．

#include <iostream>
#include <vector>
#include <cmath>
#include <iomanip>

using namespace std;

typedef long long ll;

int main() {
    int N; cin >> N;
    vector<int> v(N);
    for (int i = 0; i < N; i++) cin >> v[i];

    int dp[N];
    for (int i = 0; i < N; i++) dp[i] = 0;

    for (int i = N-2; i >= 0; i--) {
        if (v[i] >= v[i+1]) dp[i] = dp[i+1] + 1;
    }
    
    int res = 0;
    for (int i = 0; i < N; i++) {
        if (dp[i] > res) res = dp[i];
    }
    
    cout << res << endl;
}

D問題

もはや数学．．．？競プロはこんな数学の問題もでるんですね．．．コードが最終的な計算式かくだけで謎の罪悪感に包まれました．

を求めたいのですが，はi以下でありより小さいので，はnよりだいぶ小さい値になるなーというのを出発点にして考えました．そうなるとできるだけ以下の組み合わせについて最大化したくて，ひとつずつ考えていくと例えばを最大化するのはでになります．このように後ろから見ていくとiより１大きい数をとして選べば，で最大化されるのかな？？と思って実装したらACでした．

正直厳密な証明に裏付けされた答えじゃなくて，直感に基づく実装だったので実力かと言われると微妙ですが．．．

#include <iostream>
#include <vector>
#include <cmath>
#include <iomanip>

using namespace std;

typedef long long ll;

int main() {
    ll N; cin >> N;
    cout << (N-1) * N / ll(2)<< endl;
}

E問題

Dまでで３０分くらいだったので，E問題も解いて見たら意外と解けました．

1. 各選手の試合順が決まっているので，各試合における最短日数は一意にきまりそう（本当にそうなのかは不明）
2. しかも各試合の最短日数は，出場選手が前の試合を行った日にのみ依存しそう（その前にしなければならない試合があれば，その試合の最短日数が決まるまで待てば良い）
3. あれ？？でもそれだとforで各選手を回して，その外側にwhile回さないといけない？？時間足りる？？
4. あ，でも最短日の更新はたかだか試合数分しか起こらないから大丈夫かな？更新がなくなってwhile抜ければ問題なさそう

みたいな思考回路でDPで解きました．実装にもわりと時間がかかって，入力は列が試合順のインデックスにしてるのに，dpは選手のインデックスでこんがらがったりしてました．

#include <iostream>
#include <vector>
#include <cmath>
#include <iomanip>

using namespace std;

typedef long long ll;

int dp[1005][1005];

int main() {
    int N; cin >> N;
    int A[N][N-1];
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N-1; j++) {
            cin >> A[i][j];
            A[i][j]--;
        }
    }
    int next[N];
    for (int i = 0; i < N; i++) next[i] = 0;

    bool flag = false;

    while (!flag) {
        for (int i = 0; i < N; i++) {
            int idx = A[i][next[i]];
            if (next[i] >= N-1 || next[idx] >= N-1) continue;
            int prev_i, prev_idx;
            if (next[i] > 0) prev_i = A[i][next[i]-1]+1;
            else prev_i = 0;

            if (next[idx] > 0) prev_idx = A[idx][next[idx]-1]+1;
            else prev_idx = 0;

            if (A[idx][next[idx]] == i) {
                dp[i+1][idx+1] = dp[idx+1][i+1] = max(dp[i+1][prev_i], dp[idx+1][prev_idx]) + 1;
                next[i]++;
                next[idx]++;
                flag = true;
            }
        }
        flag = !flag;
    }

    int res = 0;

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (i != j && dp[i+1][j+1] == 0) {
                cout << -1 << endl;
                return 0;
            } else if (i != j) {
                res = max(res, dp[i+1][j+1]);
            }
        }
    }

    cout << res << endl;
    return 0;
}

まとめ

今回は初めてE問題まで解けてかなりうれしかったです．レートもかなり上がって茶色の上の方までいきました．最初の１０回までは補正がかかるらしいので（今６回目），とりあえずレートを気にせず１０回参加することを目標に頑張りたいと思います．