時間管理

7:40 から 8:40 まで、対拍と乱数生成の準備を行い、問題を読み込み、T1 を開始しました。40分で初回の提出を完了し、対拍で小さな誤りを見つけたため修正して再提出しました。

8:40 から 10:20 まで、T2 の解決に取り組みました。以前の模擬試験の T2 と類似点がありましたが、直接的な解法が見つからなかったため、まずは暴力解法を考えました。しかし、n ≤ 6 の場合も難しく、一部のケースは連鎖状態でしたが、適切な解法を見つけることができませんでした。その後、T3 に移りました。

10:20 から 11:10 まで、T3 の部分点について考えました。いくつかの特殊な性質を利用して解く方法を考えましたが、具体的な実装に苦労しました。dp (動的計画法) を用いて解こうとしたものの、初期のアプローチには問題があり、最終的に O(nm) の解法を完成させました。

11:10 から 11:40 まで、T4 の暴力解法を試みましたが、時間内に完成させることが難しく、結果として T4 では得点できませんでした。

試験結果

100 + 0 + 35 + 0 = 135 ポイントで、順位は 3 位でした。

試験の反省

T2 に多くの時間を費やしたため、T4 の暴力解法を書く時間が不足しました。今後は、長時間進展しない問題は他の問題に切り替えるべきです。

問題解説

T1

貪欲法を使用し、各ステップで最も大きい数を削除します。この戦略が最適であることを証明できます。連結リストとセグメントツリーを使って実装できます。

T2

前の問題（多校連携テスト Day3 T2）と類似していますが、異なる点は「すべての子の番号が i より小さい」ではなく、「少なくとも一つの子の番号が i より大きい」という条件です。状態 dp[i][j][k] を設定し、i 番目のノードまで考慮し、j 本の木があり、k 個の空き位置がある場合の解の数を表します。

for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= i; j++) {
        for (int k = 0; k <= min(n, 2 * i); k++) {
            int p = dp[i][j][k];
            for (int h = l[i + 1]; h <= r[i + 1]; h++) {
                if (h == 0) {
                    dp[i + 1][j + 1][k + h] = (dp[i + 1][j + 1][k + h] + p) % mod;
                    if (k) dp[i + 1][j][k - 1] = (dp[i + 1][j][k - 1] + (1LL * k * p) % mod) % mod;
                }
                if (h == 1) {
                    dp[i + 1][j + 1][k + h] = (dp[i + 1][j + 1][k + h] + (2LL * p) % mod) % mod;
                    dp[i + 1][j][k - 1 + h] = (dp[i + 1][j][k - 1 + h] + (2LL * k * p) % mod) % mod;
                }
                if (h == 2) {
                    dp[i + 1][j + 1][k + h] = (dp[i + 1][j + 1][k + h] + p) % mod;
                    dp[i + 1][j][k - 1 + h] = (dp[i + 1][j][k - 1 + h] + (1LL * k * p) % mod) % mod;
                    dp[i + 1][j][k + 1] = (dp[i + 1][j][k + 1] + (2LL * j * p) % mod) % mod;
                    if (j > 1) dp[i + 1][j - 1][k] = ((1LL * (1LL * p * k) % mod * (j - 1) * 2) % mod + dp[i + 1][j - 1][k]) % mod;
                }
            }
        }
    }
}

T3

n ≤ 2000 に対して、dp[i][j] を設定し、S 文字列の i 番目の文字まで考慮し、T 文字列とのマッチング長が j である最小コストを表します。初期化は非常に大きな値で、dp[0][0] は 0 です。各文字に対して、残すか削除するかの選択肢があります。s[i] が t[j] と一致する場合は残すことができます。また、t において s[i] と同じ文字が存在しない場合、s[i] を削除することができます。

LL sol() {
    memset(pre, 0, sizeof pre), memset(bac, 0, sizeof bac);
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= 26; j++) pre[i][j] = pre[i - 1][j];
        pre[i][(int)(t[i] - 'a' + 1)]++;
    }
    for (int i = m; i >= 1; i--) {
        for (int j = 1; j <= 26; j++) bac[i][j] = bac[i + 1][j];
        bac[i][(int)(t[i] - 'a' + 1)]++;
    }
    memset(dp, 0x7f, sizeof dp);
    dp[0][0] = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= min(i, m); j++) dp[i & 1][j] = 0x7f7f7f7f7f7f7f7f;
        for (int j = 0; j <= min(i, m); j++) {
            if (!j) dp[i & 1][j] = dp[(i - 1) & 1][j] + 1LL * w[i];
            if (s[i] == t[j]) dp[i & 1][j] = min(dp[i & 1][j], dp[(i - 1) & 1][j - 1]);
            if (!pre[j][(int)(s[i] - 'a' + 1)] || !bac[j + 1][(int)(s[i] - 'a' + 1)]) dp[i & 1][j] = min(dp[i & 1][j], dp[(i - 1) & 1][j] + 1LL * w[i]);
        }
    }
    return (dp[n & 1][m] == 0x7f7f7f7f7f7f7f7f ? -1 : dp[n & 1][m]);
}

T4

まだ解法を確立していません。