この記事は 【AtCoder】初中級者が解くべき過去問精選 100 問を緑色コーダーが C++ で解いてみた の子記事です。お読みになる前に親記事をご確認ください。
92. AOJ 1193 – 連鎖消滅パズル
H \leq 10 であることから、まずは計算量を気にせずに設計します。
盤上の石の配置は整数の二次元配列で記録するようにします。問題の図とあわせて、左上が最も小さい数になるように添字を付けます。また、0 を石が無いことを表す数とします。
以下の関数を用意します。
- 石を消す関数
- 石を落とす関数
石が消えるかどうかは行のみに着目すればよいため、石を消す処理では以下の処理を行ごとに行います。
- 横 ( 1 行 ) に 0 以外の同じ数字が 3 つ以上あるかを調べます。
- 行に 3 つ以上ある数字が 3 つ以上連続に並んでいるか、調べます。
5 列しかないため、数字は一意に定まります - 数字が 3 以上連続で並んでいる場合は石を消します。(二次元配列の該当箇所に 0 を代入します)
また、消えた石の合計がスコアになるため、石を消すたびに石の数字をスコアに足します。
石は下にしか落下しないため、石を落とす処理は以下の処理では以下の処理を列ごとに行います。
- 盤を見る添字 i と盤を更新する添字 k を用意し、ともに H で初期化します。
- 以下を i が 0 になるまで繰り返します。
- もし i の位置の数字が 0 以外ならば、k の位置に i の数字を代入します。
i を i – 1, k を k – 1 に変更します。 - もし i の位置の数字が 0 のならば、i を i – 1 に変更します。
空きを埋めるため、k は変更しません。
- もし i の位置の数字が 0 以外ならば、k の位置に i の数字を代入します。
- 添字 k が 0 になるまで、以下を繰り返します。
- 添字 k の位置に 0 を代入して、k を k – 1 に変更します。( 落下した石の過去の情報を消します )
ゲームのスコアは石を消す関数に都度消した石の数字の和を返してもらい、逐次に加算すれば求まります。石を消す処理と石を落とす処理の繰り返しは石を消す関数の返り値が 0 になるときに終了します。
1 回の石を消す関数の処理が O(H), 1 回の石を落とす処理が O(H) かかり、石が消える場合は少なくとも 3 つは消えるため、繰り返しは高々、O(H) 回です。そのため、1 つのデータセットに対する計算量は O(H^2) = 10^2 程度です。いくつデータセットがあるか問題文に記載がありませんが、10 万件ぐらいまではなんとかなりそうです。
93. Square869120Contest #3 B – 石落としゲーム
問題文に K の範囲が明記されていないため、石が消えない場合 ( K \leq 0 または K > W の場合 ) は早い段階で 0 を出力してプログラムを終了します。
基本的には前の問題と同様に以下の関数を用意します。
- 石を消す関数
- 石を落とす関数
ただし、1 行の長さと石が消えるのに必要な個数が問題ごとに異なるため、石を消す処理は以下のように変更します。
- 数字 a を 1, \dots, 9 に変えながら以下を繰り返し行います。
- 数字 a が書かれた石が連続で K 個以上並んでいる場合は石を消します。
1 回の石を消す関数の処理が O(HW), 1 回の石を落とす処理が O(HW) かかります。石が消える場合は少なくとも 1 つは消え、以下の問題文の制約と得点の計算式から、繰り返しは高々 \log_{2} 10^9 \leq 30 回程度です。
- 点数は 1,000,000,000 点を超えない
最初に 1 つ消す石の選び方が HW 通りあるため、全体の計算量は O(HW) \times 30 \times HW = 10^8 程度です。実行時間制限に違反せず、解答できます。
石を消す処理で各行を連長圧縮すると 9 回の繰り返しを避けられます。
94. AOJ 1149 – ケーキカット
c++ の場合、ピースの番号の管理は vector を使うと以下のようにできます。
- カットするピースの取り出し
- vector::at で情報を取り出します。
- vector::erase で取り出したピースを削除します。
- カット後のピースの追加
- vector::push_back で小さい順にピースを追加します。
ピースをカットするためには、幅と奥行きの情報が必要です。カット後に大小比較のために面積を計算することから、面積の情報も持たせた 3 つ組をピースの情報とします。
次にケーキをカットする関数を考えます。
カットするピースの幅を w, 奥行きを d とします。与えられる s_i がピースの周囲 ( 2 w + 2 d ) よりも長い場合は s_i を 2 w + 2 d で割った余りをあらためて s_i とします。s_i について、切り出す側面で以下の 4 通りの場合分けを行います。
場合 1 s_i<w
場合 2 w<s_i<w + d
場合 3 w + d<s_i<2 w + d
場合 4 2 w + d<s_i<2 w + 2 d
1, 3 は垂直に、2, 4 は水平にカットするため、新しくできる 2 つのピースの幅と奥行きは以下の通りです。
場合 1 (s_i, d), (w – s_i, d)
場合 2 (w, s_i – w), (w, w + d – s_i)
場合 3 (s_i – w – d, d), (2 w + d – s_i, d)
場合 4 (w, s_i – 2 w – d), (w, 2 w + 2 d – s_i)
カット後に 2 つのピースの上から見た面積を比較して、小さい方から順にピースの一覧 (vector) に追加します。
最後に面積でソートして出力すれば答えとなります。
vector::erase の計算量について、cpprefjp には「削除される要素の数と同じ回数のTのデストラクタが実行される。」と記載されていますが、その記述の上に「さらに、削除された要素以降の要素の数と同じ回数のTのムーブ代入演算子が呼ばれる。」とも記載されているため、ここでは O(n) と考えます。1 回のケーキのカットと追加の計算量が O(n) です。n 回カットし、最後にソートするため、1 つのデータセットに対する計算量は O(n^2 \log n) = 10^5 程度です。データセットの件数について問題文に記述がありませんが、10^2 件程度なら実行時間制限に違反せずに解答できそうです。
