読者です 読者をやめる 読者になる 読者になる

CF Round 372 div2 & SRM 698 div1

反省点のみ。
CF

using i64 = long long;
    for(int i : _in(2, N + 1)) {
        i64& res = ans[i - 1];
        i64 aim = i * (i + 1);
        i64 a = aim / i;
        res = a * aim - cur / i;
        cur = aim;
    }

うっかりint型を混ぜないように気をつける。
これで40分と4WAを消費してしまった…。

ただ、僕はそもそもがかなり抜けてるほうなので気をつけると言っても限度がある。今後もこういうミスが続くなら、Rustなどコンパイラの型チェックが厳しい言語に乗り換えることも検討したほうがいいかも。

追記

    for(i64 i : _in(2, N + 1)) {
        i64& res = ans[i - 1];
        i64 aim = i * (i + 1);
        i64 a = aim / i;
        res = a * aim - cur / i;
        cur = aim;
    }

これでもコンパイルが通った。_inクラスが保持するイテレータの内部表現はintなんだけど勝手にキャストしてくれるらしい。いいのか悪いのか微妙なところではあるが、まあ宣言する型を変えれば勝手にキャストしてくれるのは覚えておいたほうが良さそう。

TC
とりあえずdiv1 easyのみ
1.二つの文字列に分割する方法を全探索し、
2.編集距離DPをする
というかなり簡単な問題だったが、2.で最長共通部分列問題を解き始めるという謎なことをしてしまい死んだ。

今考えると本番中はトチ狂っていたとしか思えない。なぜ編集距離を求める問題なのに最長共通部分列問題を解き始めるんだ?

考察しているうちに自分の頭のなかで問題がすり替わっている/必要以上に複雑になっている ことがある。
詰まったら一度冷静になって問題文を読み返そう。

いちおうコード

int calc(const string& s1, const string& s2) {
    int N = s1.size(), M = s2.size();
    vector<vector<int>> dp(N + 1, vector<int>(M + 1, 0));
    for(int i : _in(N + 1)) dp[i][0] = i;
    for(int j : _in(M + 1)) dp[0][j] = j;
    for(int i : _in(N)) for(int j : _in(M)) {
        dp[i + 1][j + 1] = dp[i][j];
        if(s1[i] != s2[j]) ++dp[i + 1][j + 1];
        int temp = min(dp[i][j + 1] + 1, dp[i + 1][j] + 1);
        dp[i + 1][j + 1] = min(dp[i + 1][j + 1], temp);
    }
    return dp[N][M];
}

class RepeatString {
    public:
    int minimalModify(string s) {
        int N = s.size();
        int mi = 1000;
        for(int len : _in(1, N)) {
            string s1 = s.substr(0, len);
            string s2 = s.substr(len, N - len);
            mi = min(mi, calc(s1, s2));
        }
        if(N == 1) mi = 1;
        return mi;
    }
};

なんか編集距離DPが他の人のより汚い気がする。むう……。

それにしても、絶対に解ける問題だったと思うので、悔しい。