SRM 643 Div1 Med, TheKingsArmyDiv1
コーナーケースに気をつけて慎重に戦略を考える問題（もしくはDP解法）. 本番では題意を微妙に取り違えていて, なぜか pretest 通ってしまい, 呆気無く撃墜された.
問題
http://community.topcoder.com/stat?c=problem_statement&pm=13526&rd=16086
2N 人の兵士が 2 行 N 列に並んでいる. 各兵士は Happy/Sad のどちらかの状態を持っている. 兵士 X が兵士 Y に話しかけると, 兵士 Y の状態が兵士 X と同じになる. あなたは次の命令ができる.
- 一人の兵士を選び, 隣（上下左右）の誰かに話しかけさせる.
- ある行の隣り合う 2 人以上の兵士を選び, 同列他行の兵士に話しかけさせる.
- ある列の兵士（2人）を選び, 隣の列の兵士に話しかけさせる.
全員を Happy にするための最小命令回数を求めよ. 不可能な場合は -1 を出力する.
方針
基本的に 2. の命令が最も効率的なので, 2. を使う戦略を考える.
上下の状態が全て異なる場合
HHSSHHSSHH SSHHSSHHSS
上記の場合, 次の 3 命令で全員 Happy にできる.
- 1 行 2~3 列の兵士に 2. を命令
- 1 行 6~7 列の兵士に 2. を命令
- 0 行 0~9 列の兵士に 2. を命令
よって, 横に状態が等しい隣接ブロックの数を B とすると, 命令回数は B/2 + 1 回となる.
上下どちらも Happy のペアがいる場合
HHH SHS
上記の場合, 0 行 0~2 列の兵士に 2. を命令すれば良い. すなわち, 上下 Happy のペアを無視して, 前述の上下が全て異なる場合と同じ計算を適用できる.
上下どちらも Sad のペアがいる場合
HSH SSS
この場合もまず, 0 行 0~2 列の兵士に 2. を命令する. 次に, 0 列の兵士に右隣に話しかけさせれば良い（命令 3）. すなわち, 上下 Sad のペアを無視して, 最後に命令 3. を上下 Sad の個数だけ行う.
まとめ
次の計算で最小命令数が計算できる
- 上下どちらも Happy なペアを除外する.
- 上下どちらも Sad なペアを除外し, その数だけ ans++ する.
- 隣接ブロックの数 B を計算し, ans += B/2 + 1 とする.
あとは, 全員 Sad の場合と, 上下が全て等しい場合だけ分岐すれば OK.
解答
class TheKingsArmyDiv1 { public: int getNumber (vector <string> state) { int N = state[0].length(); if (state[0] == string(N, 'S') && state[1] == string(N, 'S')) return -1; int ans = 0; string different; for (int i = 0; i < N; i++) { if (state[0][i] != state[1][i]) { different.push_back(state[0][i]); } else if (state[0][i] == 'S') ans++; } int M = different.length(); if (M == 0) return ans; int blocks = 1; for (int i = 0; i < M-1; i++) if (different[i] != different[i+1]) blocks++; return ans + blocks/2 + 1; } };
(おまけ) 区間 DP 解法
区間 [l, r) について, 配列 dp(l, r, k) を次のように持つ.
- 0 行目を全て H にする手数 (k = 0)
- 1 行目を全て H にする手数 (k = 1)
- 全て H にする手数 (k = 2)
幅 (r-l) を 1 から N まで更新しながら, dp を埋めていく.
class TheKingsArmyDiv1 { public: int getNumber (vector <string> state) { int N = state[0].length(); int dp[201][201][3]; fill(dp[0][0], dp[200][200]+3, INF); // 幅 1 の初期値 for (int i = 0; i < N; i++) { if (state[0][i] == 'H') dp[i][i+1][0] = 0; // HS or HH if (state[1][i] == 'H') dp[i][i+1][1] = 0; // SH or HH if (state[0][i] == 'H' && state[1][i] == 'H') dp[i][i+1][2] = 0; // HH } for (int w = 1; w <= N; w++) { for (int l = 0; l+w <= N; l++) { for (int k = l+1; k <= l+w; k++) { int r = l+w; // 区間[l,r) // HS or HH にするコスト dp[l][r][0] = min({ dp[l][r][0], dp[l][k][0] + dp[k][r][0], dp[l][k][0] + r-k, k-l + dp[k][r][0]}); // SH or HH にするコスト dp[l][r][1] = min({ dp[l][r][1], dp[l][k][1] + dp[k][r][1], dp[l][k][1] + r-k, k-l + dp[k][r][1]}); // HH にするコスト dp[l][r][2] = min({ dp[l][r][2], dp[l][k][2] + dp[k][r][2], min(dp[l][r][0], dp[l][r][1]) + 1, dp[l][k][2] + r-k, k-l + dp[k][r][2]}); dp[l][r][0] = min(dp[l][r][0], dp[l][r][2]); dp[l][r][1] = min(dp[l][r][1], dp[l][r][2]); } } } return dp[0][N][2] >= INF ? -1 : dp[0][N][2]; } };
