yukicoder No.710 - チーム戦

問題

蟻本の復習みたいな感じ。

まずはじめに思いつくDPは以下のようなもの。

DP定義

dp[i][j][k] = 真偽値

• i : 解いた問題の数
• j : 雪男くんの解いた問題の合計秒数
• k : 雪女さんの解いた問題の合計秒数

初期値

• dp[0][0][0] = true
• dp[i][j][k] = false (i != 0 || j != 0 || k != 0)

遷移

• dp[i][j][k] = falseなら遷移しない
• dp[i + 1][j + A[i]][k] = true
• dp[i + 1][j][k + B[i]] = true

答え

• dp[N][j][k] = trueを満たす(j, k)でのmax(j, k)の最小値

DP定義終わり

しかしこれだと状態数が10¹²になって間に合わない。

ここで、DPの値が真偽値であることに注目する。真偽値の場合、DPの状態のどれかを値のほうに移動させることが可能。ということで、「雪女さんの解いた問題の合計秒数」を値のほうに移動させる。

この移動作業はほぼ機械的作業。数学の式変形みたいな感じ。

DP定義

dp[i][j] = 雪女さんの解いた問題の合計秒数の最小値

• i : 解いた問題の数
• j : 雪男くんの解いた問題の合計秒数

初期値

• dp[0][0] = 0
• dp[i][j] = INF (i != 0 || j != 0)

遷移

• dp[i][j][k] = INFなら遷移しない
• chmin(dp[i + 1][j + A[i]], dp[i][j])
• chmin(dp[i + 1][j], dp[i][j] + B[i])

答え

• dp[N][j] != INFを満たすjでのmax(j, dp[N][j])の最小値

DP定義終わり

これで状態数が10⁷になって間に合う。

終わりに

いきなり難しいほうのDP定義を考えようとすると頭の中が死ぬ（「max(j, dp[N][j])の最小値」ってけっこうヤバイ）ので、最初に簡単なほうのDP定義をしてから、それを機械的に書き換えていくのがいいと思う。