問題
4
4
コイン集め 2 (Coin Collecting 2)
解説担当：米田優峻
## 注意 この解説では，上から $i$ 行目，左から $j$ 列目に置かれているコインを，**コイン $(i, j)$** と呼ぶことにします。
## 小課題 1（累計 2 点） この小課題の制約は $H=1, W=1$ ですので，ゲームの流れとしては「葵が 1 行目を選び，凛が 1 列目を選ぶ」しかありません。 したがって，$S_{1,1}$ が `#` のとき `1 0` が答えになり，$S_{1,1}$ が `.` のとき `0 1` が答えとなります。 あとは if 文などで適切に場合分けすると，正解が得られます。
## 小課題 2（累計 10 点） この小課題の制約は $H=1$ ですので，葵は 1 行目を選ぶしかありません。 したがって，葵が操作を行った後における，凛のあり得る動きを全探索して，凛の得点が最も高くなるものを調べれば答えが分かります。 例として，次のようなケースを考えてみましょう。 ~~~ 1 3 ##. ~~~ このとき，葵が 1 行目を選んでコインの向きを反転させた後の盤面は，次のようになります。 ~~~ ..# ~~~ それでは，凛は何列目を反転させるのが最適なのでしょうか。 まず 1 列目を選ぶと，裏のコインの枚数が 1 枚になります。 次に 2 列目を選ぶと，裏のコインの枚数が 1 枚になります。 そして 3 列目を選ぶと，裏のコインの枚数が 2 枚になります。 したがって，凛は 3 列目を選ぶのが最適であり，答えは「葵が 1 枚，凛が 2 枚」となります。
## 小課題 3（累計 19 点） この小課題の制約は $W=1$ ですので，凛の動きは 1 通りしかありません。 そのため，葵の動きを全探索して，葵の得点が最も高くなるようなものを選べば正解となります。 例として，次のようなケースを考えましょう。 ~~~ 3 1 # . # ~~~ もし葵が 1 行目を選べば，盤面は次のようになります。 このとき，凛が 1 列目のコインをすべて反転させると，獲得できるコインの枚数は「葵が 2 枚，凛が 1 枚」となります。 ~~~ . . # ~~~ もし葵が 2 行目を選べば，盤面は次のようになります。 このとき，凛が 1 列目のコインをすべて反転させると，獲得できるコインの枚数は「葵が 0 枚，凛が 3 枚」となります。 ~~~ # # # ~~~ もし葵が 3 行目を選べば，盤面は次のようになります。 このとき，凛が 1 列目のコインをすべて反転させると，獲得できるコインの枚数は「葵が 2 枚，凛が 1 枚」となります。 ~~~ # . . ~~~ したがって，葵は 1 行目または 3 行目を選ぶのが最適であり，答えは「葵が 2 枚，凛が 1 枚」となります。
## 小課題 4（累計 33 点） この小課題は $H=2, W=2$ であるため，あり得る入力は全部で $16$ 通りしかありません。 ですので，すべての場合の答えを手で計算して，if 文で場合分けすれば正解となります。
## 小課題 5/6（累計 74 点） ここからは少し難しいです。まずは例として，以下のようなケースを考えましょう。 葵と凛は，どのように動くのが最適なのでしょうか。 ~~~ 3 3 ##. .## #.. ~~~ ### 葵が 1 行目を選んだ場合 もし先手の葵が 1 行目を選べば，盤面は次のようになります。 ~~~ ..# .## #.. ~~~ 後手の凛は **表面のコインの枚数が最も多い列を反転させるのが最適** ですので，3 列目を選びます。 すると盤面は次のようになり，獲得できるコインの枚数は「葵が 3 枚，凛が 6 枚」となります。 ~~~ ... .#. #.# ~~~ ### 葵が 2 行目を選んだ場合 もし先手の葵が 2 行目を選べば，盤面は次のようになります。 ~~~ ##. #.. #.. ~~~ 後手の凛は表面のコインの枚数が最も多い列を反転させるのが最適ですので，1 列目を選びます。 すると盤面は次のようになり，獲得できるコインの枚数は「葵が 1 枚，凛が 8 枚」となります。 ~~~ .#. ... ... ~~~ ### 葵が 3 行目を選んだ場合 もし先手の葵が 3 行目を選べば，盤面は次のようになります。 ~~~ ##. .## .## ~~~ 後手の凛は表面のコインの枚数が最も多い列を反転させるのが最適ですので，2 列目を選びます。 すると盤面は次のようになり，獲得できるコインの枚数は「葵が 3 枚，凛が 6 枚」となります。 ~~~ #.. ..# ..# ~~~ ### 解法のまとめ & 一般のケース 先程の例では，葵がそれぞれの行を選んだ場合に獲得できるコインの枚数は次のようになりました。 したがって，葵は 1 行目または 3 行目を選ぶのが最適となり，答えは「葵が 3 枚，凛が 6 枚」となります。 * **葵が 1 行目を選ぶ：**葵が 3 枚，凛が 6 枚 * **葵が 2 行目を選ぶ：**葵が 1 枚，凛が 8 枚 * **葵が 3 行目を選ぶ：**葵が 3 枚，凛が 6 枚 一般のケースでも同じように，（凛が最適に動く，すなわち表面のコインの枚数が最も多い列を選ぶという前提のもと）で葵の選ぶ行を全探索すれば，答えが求まります。 最後にプログラムの計算量を評価しましょう。 葵の打てる手は $H$ 通り存在し，それぞれについてコインの枚数を数えるのに計算量 $O(HW)$ かかるので，全体の計算量は $O(H^2 \times W)$ となります。 この小課題の制約は $H, W \leq 300$ ですので，実行時間制限の 2 秒には余裕をもって間に合います。 なお，実装は少し難しいですが，次のように関数を活用したり，適宜コメントを入れたりするなどのコツを使うと，実装がしやすくなります。（JOI のホームページで上手く表示させる都合上，include 部分を削除しています） ~~~cpp // 変数 int H, W; char c[309][309]; char d[309][309]; // 葵のターン：行 px を反転させる void FlipAOI(int px) { for (int i = 1; i <= W; i++) { if (c[px][i] == '.') c[px][i] = '#'; else c[px][i] = '.'; } } // 凛のターン：列 py を反転させる void FlipRIN(int py) { for (int i = 1; i <= H; i++) { if (c[i][py] == '.') c[i][py] = '#'; else c[i][py] = '.'; } } // 表になっているコインの枚数を数える int CountAOICoins() { int cnt = 0; for (int i = 1; i <= H; i++) { for (int j = 1; j <= W; j++) { if (c[i][j] == '#') cnt++; } } return cnt; } // もし葵が行 px を選び，凛が最適に動いた場合，コインの枚数は何枚になるか？ int Simulation(int px) { // 葵のターンを行う FlipAOI(px); // 凛がどの行を選ぶのが良いかを調べる int Max_Omote = -1; int Max_Index = -1; for (int j = 1; j <= W; j++) { int sum = 0; for (int i = 1; i <= H; i++) { if (c[i][j] == '#') sum += 1; } if (Max_Omote < sum) { Max_Omote = sum; Max_Index = j; } } // 凛のターンを行う FlipRIN(Max_Index); // 枚数を返す return CountAOICoins(); } int main() { // 入力 cin >> H >> W; for (int i = 1; i <= H; i++) { for (int j = 1; j <= W; j++) cin >> c[i][j]; } // 初期化用の配列をコピー for (int i = 1; i <= H; i++) { for (int j = 1; j <= W; j++) d[i][j] = c[i][j]; } // 葵が選ぶ列を全探索 int Answer = 0; for (int i = 1; i <= H; i++) { // 配列の初期化 for (int j = 1; j <= H; j++) { for (int k = 1; k <= W; k++) c[j][k] = d[j][k]; } // シミュレーション Answer = max(Answer, Simulation(i)); } // 出力 cout << Answer << " " << H * W - Answer << endl; return 0; } ~~~
## 小課題 7（累計 100 点） 先程の解法の計算量は $O(H^2 \times W)$ でした。 しかし，本小課題の制約は $H \times W \leq 500000$ であるため，$H=250000, W=2$ のようなケースでは残念ながら TLE となってしまいます。 そこで，**各列における表のコインの枚数 `cnt[1], cnt[2], ..., cnt[W]` を前もって計算しておく** というアイデアを使うことで，アルゴリズムを高速化することができます。 例として，次のようなテストケースを考えましょう。 ~~~ 3 3 ##. .## #.. ~~~ このとき，初期状態における各列のコインの枚数は `cnt = [2, 2, 1]` となります。 ここで，葵がそれぞれの行を選んだ場合のスコアをどうやって計算するかを実際に見ていきましょう。 ### 葵が 1 行目を選んだ場合 まず，先手の葵が 1 行目を選んだ場合，コイン (1, 1) と (1, 2) が表から裏に変わり，コイン (1, 3) が裏から表に変わります。 したがって，`cnt = [1, 1, 2]` に変化します。ここまでの計算処理は $O(W)$ 時間で行うことができます。 続いて，後手の凛は表のコインが最も多い列，すなわち `cnt[i]` が最も大きい列を選ぶのが最適ですので，$3$ 列目を選びます。 したがって，`cnt = [1, 1, 1]` に変化します。この計算処理も $O(W)$ 時間で行うことができます。 最後に，葵のコインの枚数は `cnt[i]` の合計値ですので，結果は「葵が 3 枚，凛が 6 枚」だと分かります。 ### 葵が 2 行目を選んだ場合 まず，先手の葵が 2 行目を選んだ場合，コイン (2, 2) と (2, 3) が表から裏に変わり，コイン (2, 1) が裏から表に変わります。 したがって，`cnt = [3, 1, 0]` に変化します。ここまでの計算処理は $O(W)$ 時間で行うことができます。 続いて，後手の凛は表のコインが最も多い列，すなわち `cnt[i]` が最も大きい列を選ぶのが最適ですので，$1$ 列目を選びます。 したがって，`cnt = [0, 1, 0]` に変化します。この計算処理も $O(W)$ 時間で行うことができます。 最後に，葵のコインの枚数は `cnt[i]` の合計値ですので，結果は「葵が 1 枚，凛が 8 枚」だと分かります。 ### 葵が 3 行目を選んだ場合 まず，先手の葵が 3 行目を選んだ場合，コイン (3, 1) が表から裏に変わり，コイン (3, 2) と (3, 3) が裏から表に変わります。 したがって，`cnt = [1, 3, 2]` に変化します。ここまでの計算処理は $O(W)$ 時間で行うことができます。 続いて，後手の凛は表のコインが最も多い列，すなわち `cnt[i]` が最も大きい列を選ぶのが最適ですので，$2$ 列目を選びます。 したがって，`cnt = [1, 0, 2]` に変化します。この計算処理も $O(W)$ 時間で行うことができます。 最後に，葵のコインの枚数は `cnt[i]` の合計値ですので，結果は「葵が 3 枚，凛が 6 枚」だと分かります。 ### 解法のまとめ このように，各列のコインの枚数 `cnt[i]` を記録するというアイデアを使うと， 葵が各行を選んだときの最終的な結果を $O(W)$ 時間で求めることができます。 葵の選択肢は $H$ 通りあるので，プログラム全体の計算量は $O(HW)$ まで削減されます。 本問題の制約は $H, W \leq 500000$ と大きいですが，競技プログラミングでは 1 秒間に 1 億回以上の計算ができることが多いので， 実行時間制限には余裕をもって間に合います。 最後に，C++ のサンプルコードは以下のようになります。（JOI のホームページで上手く表示させる都合上，include 部分を削除しています） ~~~cpp // 変数 int H, W; int cnt[500009]; int cnt_init[500009]; string c[500009]; // もし葵が行 px を選び，凛が最適に動いた場合，コインの枚数は何枚になるか？ int Simulation(int px) { // 葵のターンを行う for (int i = 0; i < W; i++) { if (c[px][i] == '#') cnt[i] -= 1; if (c[px][i] == '.') cnt[i] += 1; } // 凛がどの行を選ぶのが良いかを調べる int Max_Omote = -1; int Max_Index = -1; for (int j = 0; j < W; j++) { if (Max_Omote < cnt[j]) { Max_Omote = cnt[j]; Max_Index = j; } } // 凛のターンを行う cnt[Max_Index] = H - cnt[Max_Index]; // 枚数を返す int Return = 0; for (int j = 0; j < W; j++) Return += cnt[j]; return Return; } int main() { // 入力 cin >> H >> W; for (int i = 0; i < H; i++) cin >> c[i]; // cnt の値を計算する（cnt_init は初期化用の配列） for (int j = 0; j < W; j++) { cnt[j] = 0; for (int i = 0; i < H; i++) { if (c[i][j] == '#') cnt[j] += 1; } cnt_init[j] = cnt[j]; } // 葵が選ぶ列を全探索 int Answer = 0; for (int i = 0; i < H; i++) { // 配列の初期化 for (int j = 0; j < W; j++) cnt[j] = cnt_init[j]; // シミュレーション Answer = max(Answer, Simulation(i)); } // 出力 cout << Answer << " " << H * W - Answer << endl; return 0; } ~~~
## 想定誤答例 最後に，よくある誤答例として，次のようなものがあります。（つまり一手読みです） * 葵は，葵のターンが終わった後の表のコインの枚数が最大になるような手を打つ * 凛は，凛のターンが終わった後の裏のコインの枚数が最大になるような手を打つ この解法は，小課題 1・2・4 の制約を満たすテストケースにはすべて通りますが， 入力例 5（以下を参照）のようなケースで間違った答えを出力してしまいます。 ~~~ 5 5 .###. ...## ..##. .##.. ##... ~~~ このケースでは葵が 1 行目を選択するのが最適であり，このとき葵は 11 枚のコインを獲得できます。 しかし，先程の解法では 2～5 行目のいずれかを選択することになり，凛が最適な動きをすると 9 枚のコインしか獲得することができません。 以下に，2 行目を選択した場合の例を示します。 ~~~ .###. .###. .#.#. ...## ###.. ##... ..##. -> ..##. -> ...#. .##.. .##.. .#... ##... ##... ###.. ~~~
## 注意 この解説では，上から $i$ 行目，左から $j$ 列目に置かれているコインを，**コイン $(i, j)$** と呼ぶことにします。
## 小課題 1（累計 2 点） この小課題の制約は $H=1, W=1$ ですので，ゲームの流れとしては「葵が 1 行目を選び，凛が 1 列目を選ぶ」しかありません。 したがって，$S_{1,1}$ が `#` のとき `1 0` が答えになり，$S_{1,1}$ が `.` のとき `0 1` が答えとなります。 あとは if 文などで適切に場合分けすると，正解が得られます。
## 小課題 2（累計 10 点） この小課題の制約は $H=1$ ですので，葵は 1 行目を選ぶしかありません。 したがって，葵が操作を行った後における，凛のあり得る動きを全探索して，凛の得点が最も高くなるものを調べれば答えが分かります。 例として，次のようなケースを考えてみましょう。 ~~~ 1 3 ##. ~~~ このとき，葵が 1 行目を選んでコインの向きを反転させた後の盤面は，次のようになります。 ~~~ ..# ~~~ それでは，凛は何列目を反転させるのが最適なのでしょうか。 まず 1 列目を選ぶと，裏のコインの枚数が 1 枚になります。 次に 2 列目を選ぶと，裏のコインの枚数が 1 枚になります。 そして 3 列目を選ぶと，裏のコインの枚数が 2 枚になります。 したがって，凛は 3 列目を選ぶのが最適であり，答えは「葵が 1 枚，凛が 2 枚」となります。
## 小課題 3（累計 19 点） この小課題の制約は $W=1$ ですので，凛の動きは 1 通りしかありません。 そのため，葵の動きを全探索して，葵の得点が最も高くなるようなものを選べば正解となります。 例として，次のようなケースを考えましょう。 ~~~ 3 1 # . # ~~~ もし葵が 1 行目を選べば，盤面は次のようになります。 このとき，凛が 1 列目のコインをすべて反転させると，獲得できるコインの枚数は「葵が 2 枚，凛が 1 枚」となります。 ~~~ . . # ~~~ もし葵が 2 行目を選べば，盤面は次のようになります。 このとき，凛が 1 列目のコインをすべて反転させると，獲得できるコインの枚数は「葵が 0 枚，凛が 3 枚」となります。 ~~~ # # # ~~~ もし葵が 3 行目を選べば，盤面は次のようになります。 このとき，凛が 1 列目のコインをすべて反転させると，獲得できるコインの枚数は「葵が 2 枚，凛が 1 枚」となります。 ~~~ # . . ~~~ したがって，葵は 1 行目または 3 行目を選ぶのが最適であり，答えは「葵が 2 枚，凛が 1 枚」となります。
## 小課題 4（累計 33 点） この小課題は $H=2, W=2$ であるため，あり得る入力は全部で $16$ 通りしかありません。 ですので，すべての場合の答えを手で計算して，if 文で場合分けすれば正解となります。
## 小課題 5/6（累計 74 点） ここからは少し難しいです。まずは例として，以下のようなケースを考えましょう。 葵と凛は，どのように動くのが最適なのでしょうか。 ~~~ 3 3 ##. .## #.. ~~~ ### 葵が 1 行目を選んだ場合 もし先手の葵が 1 行目を選べば，盤面は次のようになります。 ~~~ ..# .## #.. ~~~ 後手の凛は **表面のコインの枚数が最も多い列を反転させるのが最適** ですので，3 列目を選びます。 すると盤面は次のようになり，獲得できるコインの枚数は「葵が 3 枚，凛が 6 枚」となります。 ~~~ ... .#. #.# ~~~ ### 葵が 2 行目を選んだ場合 もし先手の葵が 2 行目を選べば，盤面は次のようになります。 ~~~ ##. #.. #.. ~~~ 後手の凛は表面のコインの枚数が最も多い列を反転させるのが最適ですので，1 列目を選びます。 すると盤面は次のようになり，獲得できるコインの枚数は「葵が 1 枚，凛が 8 枚」となります。 ~~~ .#. ... ... ~~~ ### 葵が 3 行目を選んだ場合 もし先手の葵が 3 行目を選べば，盤面は次のようになります。 ~~~ ##. .## .## ~~~ 後手の凛は表面のコインの枚数が最も多い列を反転させるのが最適ですので，2 列目を選びます。 すると盤面は次のようになり，獲得できるコインの枚数は「葵が 3 枚，凛が 6 枚」となります。 ~~~ #.. ..# ..# ~~~ ### 解法のまとめ & 一般のケース 先程の例では，葵がそれぞれの行を選んだ場合に獲得できるコインの枚数は次のようになりました。 したがって，葵は 1 行目または 3 行目を選ぶのが最適となり，答えは「葵が 3 枚，凛が 6 枚」となります。 * **葵が 1 行目を選ぶ：**葵が 3 枚，凛が 6 枚 * **葵が 2 行目を選ぶ：**葵が 1 枚，凛が 8 枚 * **葵が 3 行目を選ぶ：**葵が 3 枚，凛が 6 枚 一般のケースでも同じように，（凛が最適に動く，すなわち表面のコインの枚数が最も多い列を選ぶという前提のもと）で葵の選ぶ行を全探索すれば，答えが求まります。 最後にプログラムの計算量を評価しましょう。 葵の打てる手は $H$ 通り存在し，それぞれについてコインの枚数を数えるのに計算量 $O(HW)$ かかるので，全体の計算量は $O(H^2 \times W)$ となります。 この小課題の制約は $H, W \leq 300$ ですので，実行時間制限の 2 秒には余裕をもって間に合います。 なお，実装は少し難しいですが，次のように関数を活用したり，適宜コメントを入れたりするなどのコツを使うと，実装がしやすくなります。（JOI のホームページで上手く表示させる都合上，include 部分を削除しています） ~~~cpp // 変数 int H, W; char c[309][309]; char d[309][309]; // 葵のターン：行 px を反転させる void FlipAOI(int px) { for (int i = 1; i <= W; i++) { if (c[px][i] == '.') c[px][i] = '#'; else c[px][i] = '.'; } } // 凛のターン：列 py を反転させる void FlipRIN(int py) { for (int i = 1; i <= H; i++) { if (c[i][py] == '.') c[i][py] = '#'; else c[i][py] = '.'; } } // 表になっているコインの枚数を数える int CountAOICoins() { int cnt = 0; for (int i = 1; i <= H; i++) { for (int j = 1; j <= W; j++) { if (c[i][j] == '#') cnt++; } } return cnt; } // もし葵が行 px を選び，凛が最適に動いた場合，コインの枚数は何枚になるか？ int Simulation(int px) { // 葵のターンを行う FlipAOI(px); // 凛がどの行を選ぶのが良いかを調べる int Max_Omote = -1; int Max_Index = -1; for (int j = 1; j <= W; j++) { int sum = 0; for (int i = 1; i <= H; i++) { if (c[i][j] == '#') sum += 1; } if (Max_Omote < sum) { Max_Omote = sum; Max_Index = j; } } // 凛のターンを行う FlipRIN(Max_Index); // 枚数を返す return CountAOICoins(); } int main() { // 入力 cin >> H >> W; for (int i = 1; i <= H; i++) { for (int j = 1; j <= W; j++) cin >> c[i][j]; } // 初期化用の配列をコピー for (int i = 1; i <= H; i++) { for (int j = 1; j <= W; j++) d[i][j] = c[i][j]; } // 葵が選ぶ列を全探索 int Answer = 0; for (int i = 1; i <= H; i++) { // 配列の初期化 for (int j = 1; j <= H; j++) { for (int k = 1; k <= W; k++) c[j][k] = d[j][k]; } // シミュレーション Answer = max(Answer, Simulation(i)); } // 出力 cout << Answer << " " << H * W - Answer << endl; return 0; } ~~~
## 小課題 7（累計 100 点） 先程の解法の計算量は $O(H^2 \times W)$ でした。 しかし，本小課題の制約は $H \times W \leq 500000$ であるため，$H=250000, W=2$ のようなケースでは残念ながら TLE となってしまいます。 そこで，**各列における表のコインの枚数 `cnt[1], cnt[2], ..., cnt[W]` を前もって計算しておく** というアイデアを使うことで，アルゴリズムを高速化することができます。 例として，次のようなテストケースを考えましょう。 ~~~ 3 3 ##. .## #.. ~~~ このとき，初期状態における各列のコインの枚数は `cnt = [2, 2, 1]` となります。 ここで，葵がそれぞれの行を選んだ場合のスコアをどうやって計算するかを実際に見ていきましょう。 ### 葵が 1 行目を選んだ場合 まず，先手の葵が 1 行目を選んだ場合，コイン (1, 1) と (1, 2) が表から裏に変わり，コイン (1, 3) が裏から表に変わります。 したがって，`cnt = [1, 1, 2]` に変化します。ここまでの計算処理は $O(W)$ 時間で行うことができます。 続いて，後手の凛は表のコインが最も多い列，すなわち `cnt[i]` が最も大きい列を選ぶのが最適ですので，$3$ 列目を選びます。 したがって，`cnt = [1, 1, 1]` に変化します。この計算処理も $O(W)$ 時間で行うことができます。 最後に，葵のコインの枚数は `cnt[i]` の合計値ですので，結果は「葵が 3 枚，凛が 6 枚」だと分かります。 ### 葵が 2 行目を選んだ場合 まず，先手の葵が 2 行目を選んだ場合，コイン (2, 2) と (2, 3) が表から裏に変わり，コイン (2, 1) が裏から表に変わります。 したがって，`cnt = [3, 1, 0]` に変化します。ここまでの計算処理は $O(W)$ 時間で行うことができます。 続いて，後手の凛は表のコインが最も多い列，すなわち `cnt[i]` が最も大きい列を選ぶのが最適ですので，$1$ 列目を選びます。 したがって，`cnt = [0, 1, 0]` に変化します。この計算処理も $O(W)$ 時間で行うことができます。 最後に，葵のコインの枚数は `cnt[i]` の合計値ですので，結果は「葵が 1 枚，凛が 8 枚」だと分かります。 ### 葵が 3 行目を選んだ場合 まず，先手の葵が 3 行目を選んだ場合，コイン (3, 1) が表から裏に変わり，コイン (3, 2) と (3, 3) が裏から表に変わります。 したがって，`cnt = [1, 3, 2]` に変化します。ここまでの計算処理は $O(W)$ 時間で行うことができます。 続いて，後手の凛は表のコインが最も多い列，すなわち `cnt[i]` が最も大きい列を選ぶのが最適ですので，$2$ 列目を選びます。 したがって，`cnt = [1, 0, 2]` に変化します。この計算処理も $O(W)$ 時間で行うことができます。 最後に，葵のコインの枚数は `cnt[i]` の合計値ですので，結果は「葵が 3 枚，凛が 6 枚」だと分かります。 ### 解法のまとめ このように，各列のコインの枚数 `cnt[i]` を記録するというアイデアを使うと， 葵が各行を選んだときの最終的な結果を $O(W)$ 時間で求めることができます。 葵の選択肢は $H$ 通りあるので，プログラム全体の計算量は $O(HW)$ まで削減されます。 本問題の制約は $H, W \leq 500000$ と大きいですが，競技プログラミングでは 1 秒間に 1 億回以上の計算ができることが多いので， 実行時間制限には余裕をもって間に合います。 最後に，C++ のサンプルコードは以下のようになります。（JOI のホームページで上手く表示させる都合上，include 部分を削除しています） ~~~cpp // 変数 int H, W; int cnt[500009]; int cnt_init[500009]; string c[500009]; // もし葵が行 px を選び，凛が最適に動いた場合，コインの枚数は何枚になるか？ int Simulation(int px) { // 葵のターンを行う for (int i = 0; i < W; i++) { if (c[px][i] == '#') cnt[i] -= 1; if (c[px][i] == '.') cnt[i] += 1; } // 凛がどの行を選ぶのが良いかを調べる int Max_Omote = -1; int Max_Index = -1; for (int j = 0; j < W; j++) { if (Max_Omote < cnt[j]) { Max_Omote = cnt[j]; Max_Index = j; } } // 凛のターンを行う cnt[Max_Index] = H - cnt[Max_Index]; // 枚数を返す int Return = 0; for (int j = 0; j < W; j++) Return += cnt[j]; return Return; } int main() { // 入力 cin >> H >> W; for (int i = 0; i < H; i++) cin >> c[i]; // cnt の値を計算する（cnt_init は初期化用の配列） for (int j = 0; j < W; j++) { cnt[j] = 0; for (int i = 0; i < H; i++) { if (c[i][j] == '#') cnt[j] += 1; } cnt_init[j] = cnt[j]; } // 葵が選ぶ列を全探索 int Answer = 0; for (int i = 0; i < H; i++) { // 配列の初期化 for (int j = 0; j < W; j++) cnt[j] = cnt_init[j]; // シミュレーション Answer = max(Answer, Simulation(i)); } // 出力 cout << Answer << " " << H * W - Answer << endl; return 0; } ~~~
## 想定誤答例 最後に，よくある誤答例として，次のようなものがあります。（つまり一手読みです） * 葵は，葵のターンが終わった後の表のコインの枚数が最大になるような手を打つ * 凛は，凛のターンが終わった後の裏のコインの枚数が最大になるような手を打つ この解法は，小課題 1・2・4 の制約を満たすテストケースにはすべて通りますが， 入力例 5（以下を参照）のようなケースで間違った答えを出力してしまいます。 ~~~ 5 5 .###. ...## ..##. .##.. ##... ~~~ このケースでは葵が 1 行目を選択するのが最適であり，このとき葵は 11 枚のコインを獲得できます。 しかし，先程の解法では 2～5 行目のいずれかを選択することになり，凛が最適な動きをすると 9 枚のコインしか獲得することができません。 以下に，2 行目を選択した場合の例を示します。 ~~~ .###. .###. .#.#. ...## ###.. ##... ..##. -> ..##. -> ...#. .##.. .##.. .#... ##... ##... ###.. ~~~