青木です。paizaラーニング担当のエンジニアです。
paizaで公開しているプログラミングゲーム『エンジニアが死滅シタ世界〜アンドロイドとふたりぼっちで生きろ〜』、みなさんチャレンジしていただけましたでしょうか？
先日すべての問題の解答コードを公開しましたが、今回はこの中でもっとも難易度の高い「有名なプールサイド [MISSION LEVEL: A]」の問題の概要と解法について図解で解説します。
「とりあえずどんな問題か知りたい」「やってみたけど解けなかった」といった方の参考になればと思います。
ちなみに、こちらの問題はランキング問題となっており、上位スコア獲得者はランキングに掲載されます。
後半ではより効率的な解き方でスコアを高めていく方法についても解説しますので、「とりあえず正解はできるけどスコアが伸びない」「もっといい感じの解き方が知りたい」という方はぜひごらんださい。
※今回はPyhtonで解いていますが、Javaで解いたときの解答コードもリンクを貼っていきます。
有名なプールサイド [MISSION LEVEL: A]の問題文
問題文は以下ですが、今回は要点をかいつまんで図解で説明するので、読み飛ばしても大丈夫です（長いし…）。
詳しい制約が気になったときや、ヒントだけ知れたらあとは自力で解きたいという方などは、必要に応じて問題文に戻って確認してください。
あなたは今度新しくできる町のデザインを任されました。
町は南北に H、東西に W の広さで、計 H × W 個の区画からなっています。
また、それぞれの区画には、次の図のように座標が割り当てられているものとします。
町に建設したい建物のリストが与えられます。
どの建物も長方形の形をしており、ただ一つの扉を持っています。リストにはたくさんの建物が含まれているため、リストに載っているすべての建物を建設することができるとは限りません。
そこで、町のどこにどの建物を建設するかを決めるのがあなたの仕事です。建物を建設する場所を決める際には、次の 3 つのルールを守らなくてはいけません。
1. どの 2 つの建物も重なってはいけない。
2. 建設する建物の向きはリストに与えられたとおりでないといけない (建物を回転して配置してはいけない)。
3. どの 2 つの建物についても、それらの扉の間を「建物がない区画」を通って移動できる。
ルール 3 を正確に述べると、次のようになります： すべての建設する建物の組に対して、それらの扉の座標を P, Q とするとき、 以下の条件 (i)-(iii) を満たすような座標の列 (r_1, c_1), (r_2, c_2), ..., (r_m, c_m) が存在する (m は 0 以上の整数)。(i) 1 ≦ r_i ≦ H, 1 ≦ c_i ≦ W が成り立つ (1 ≦ i ≦ m)。
(ii) 座標 (r_i, c_i) にはどの建物も建設されていない (1 ≦ i ≦ m)。
(iii) 座標 (r_i, c_i) と (r_{i+1}, c_{i+1}) は上下左右のいずれかで隣接している (0 ≦ i ≦ m)。ただし、P = (r_0, c_0), Q = (r_{m+1}, c_{m+1}) とする。次の図は条件 (i)-(iii) が守られている建物の配置と守られていない配置の例を表しています。
灰色の建物と緑の建物については、それらの扉の間を「建物がない区画」を通って移動することができます。
一方、灰色の建物と青の建物については、そのような移動方法は存在しません。
町の区画 X 個分の大きさの建物は、X 万円の利益を生み出します。建物が生み出す利益の合計ができるだけ多くなるような、建物の配置を求めるプログラムを書いてください。
最低1個以上の利益を生み出す建物を配置することで正解となり、建物の面積がスコアとして計算されます。
この問題の要点は、以下の二点です。
- 二次元平面に長方形の建物をたくさん敷き詰めます。
- 敷き詰めた建物の合計面積が大きいほどスコアが高くなります。
図にすると、こんなイメージです。以下のように、たくさんの候補の中から建物を選んで配置します。
また、この図のように、配置した建物の合計面積が大きいほどスコアが高くなります。（※この問題はランキング問題のため、スコアが高い人はランキングに掲載されます）
敷き詰め方には制約がありますが、ひとまず「建物を1つだけ」置く単純な解法では、この制約を気にする必要はありません。まずは建物を1つだけ置くコードを書いてみましょう。
建物を1つだけ置く
さっそく建物を1つだけ置く解法を考えましょう。前回の記事でも掲載されている単純な解き方です。
※Javaで解いたときのコードはこちら
長方形を1つしか使わないので、提出したときのスコアはめちゃくちゃ低くて189でしたが、まぁ間違いではありません。
ただ、これだけでは簡単すぎるので、もう少し高いスコアを狙っていきましょう。
建物の敷き詰め方の制約
ひとつだけじゃ話にならないので、複数の建物を敷き詰めてみたいと思います。
ただ前述の通り、2つ以上の建物を敷き詰めるなら、次の制約を守らなければなりません。
- 建物が重なってはならない
- 各建物の外周上の1マスには入り口があり、各入り口は互いに「建物がない区画」を通してつながっている
建物の重なりについては、下図のような場合はOKですが…
下図のような場合はNGです。
あと、それぞれの建物には「入口」があります。
下図の場合、入口は互いにつながっていますが…
下図のような場合、入口は互いにつながっていないのでNGです。建物によって盤面が2つの領域に分断されてしまい、入口がそれぞれ別の領域に面しているからです。
また、下図のような盤面の外だけに面している入口も、ほかの入口につなげることができていないのでNGです。
斜め方向には通過できないので、以下のような場合も入口はつながらないということでNGです。
建物の周囲を1マス空ける
では、上記の制約を満たしつつ、複数の建物を置くにはどのような戦略をとるのがよいでしょうか？
まずは「建物の周囲は必ず1マス空ける」という戦略でやってみましょうかね。
図にするとこんなイメージです。こうすれば、入り口は必ず建物ではないマスに隣接させられて、分断もなく、ほかのすべての建物の入り口とつなげることができそうですね。
1マス空けて縦に並べる
実際に並べていきましょう。
いきなり縦横両方で考えると大変なので、まずは下図のように、縦のみ並べていくことを考えてみましょうかね。
※Javaで解いたときのコードはこちら
提出するとスコアは3739でした。
1マス空けて横にも並べる
縦ができたので、横にも並べてみましょうかね。
※Javaで解いたときのコードはこちら
意外と少しの修正で、横並びにも対応させることができましたね。この段階のコードを提出すると、スコアは18856でした。一気に上がりましたね。
いつでも1マス空けるのは無駄？
というわけで、ここまではつねに1マス空けてきましたが、この隙間が無駄になってしまうこともありますよね。
例えば、入り口がない側面同士の建物の間に、通路は必要ありません。
ただ、これらの隙間を全部詰めてしまうと、領域が分断されて入口のつながりが切断されるかもしれないんですよね。
柔毛状に並べる
「建物の周囲は必ず1マス空ける」戦略から離れて、領域が分断されないことを保証しつつ、建物同士の余計な空間を減らす別の戦略を考えてみましょう。
「建物を柔毛状に並べる」という戦略はどうでしょうか？
（いきなり「柔毛」という馴染みのない言葉が出てきましたが、柔毛とは、下図のような腸にたくさん生えているひだ状の突起です。柔毛の表面積はテニスコート1枚分もあり、栄養を効率よく吸収することができるようになっています。きもい絵を見せて申し訳ないですが、実物はもっとあれなので、画像検索しないようにしてください）(※1)
柔毛は突起から突起が生え、表面は同じ領域(小腸)に面し、たくさん敷き詰められています。同じ要領で、建物から建物が生え、表面は同じ領域に面しているような状態で、たくさん敷き詰める方法を考えていきましょう。(※2)
図にするとこんなイメージですね。
新しく建物を配置するときに、いずれか1つの建物(または盤面の端)とだけつながるようにして、入り口は盤面内に面するようにしておきましょう。こうすると、柔毛の表面が腸内に面するのと同じ要領で、すべての入口が同じ盤面内の同じ領域に面することができて、なおかつ入口同士がつながることも保証できます。
※Javaで解いたときのコードはこちら
このコードを提出すると、スコアは19396になりました。常に1マスあけていたときよりもよいですね。
さらに1マス空けて並べるのも許しちゃう
上記の建物を柔毛状に配置する戦略だと、必ず1つの建物(または盤面の端)から建物を生やさなければなりません。ただ、この制約があると、入口に囲まれるようなスペースには、建物を配置できない場合が発生しますよね。
下図のような場合は、1マス空けると赤の点線部分に追加の配置が可能になるので、置けるようにしたいですねぇ。
前述のコードを修正して、1マス空けて置くこともできるようにしてみましょう。
※Javaで解いたときのコードはこちら
前のコードとの差分は、意外とこの部分だけなんですね〜。
< if self.count_continuous_object_on_outer_edge(building, x, y) != 1: --- > if self.count_continuous_object_on_outer_edge(building, x, y) >= 2:
これだけで、さらに建物をたくさん配置できるようになって、スコアを20112まで上げることができました。
まとめ
というわけで、『エンジニアが死滅シタ世界〜アンドロイドとふたりぼっちで生きろ〜』のランキング問題「有名なプールサイド [MISSION LEVEL: A]」の解き方を解説しました。
まずは、1マスずつ余裕を持たせて配置することで、確実に入り口が同じ領域に隣接するようにする。次に、建物を柔毛状に配置して、建物を必ず隣接させつつ、隣接する数を制限することで、余分な領域を減らしながら、入り口が同じ領域に面するようにする。ということで、最初に簡単な方法を考えて、そこからさらに工夫ができないか？という方向性で考えてみました。(※3)
もちろん、今回紹介した解き方以外にもいろいろな工夫が考えられます。問題にはいつでもオンライン上で挑戦・実行して採点結果を見ることができますので、ぜひいろいろ試してスコアアップを目指してください。
注釈
(※1)正確には輪状ヒダから腸絨毛が生えていて、さらに腸絨毛から微絨毛が生えているそうです。
(※2)樹状や木構造、森…などの言い方もあったかもしれませんが、アルゴリズムを考えたときのイメージに柔毛が一番しっくりきたので、きもくて申し訳ないですが、あえて柔毛を使って説明しています。
(※3)今回の2つの戦略は、いずれも新しく建物を置くときは盤面の全体を眺めずに、新しい建物の周囲だけを確認すればよい…とする解き方です。入口のつながりの判定をその都度おこないながら、入口がつながる配置だけを採用していくという方法も考えられます…が、何の工夫もせずにつながりを判定しようとすると、判定する都度盤面の全体を読むことになって、計算に結構時間がかかってしまうので今回はやっていません。
「paizaラーニング」では、未経験者でもブラウザさえあれば、今すぐプログラミングの基礎が動画で学べるレッスンを多数公開しております。
詳しくはこちら
そしてpaizaでは、Webサービス開発企業などで求められるコーディング力や、テストケースを想定する力などが問われるプログラミングスキルチェック問題も提供しています。
スキルチェックに挑戦した人は、その結果によってS・A・B・C・D・Eの6段階のランクを取得できます。必要なスキルランクを取得すれば、書類選考なしで企業の求人に応募することも可能です。「自分のプログラミングスキルを客観的に知りたい」「スキルを使って転職したい」という方は、ぜひチャレンジしてみてください。
詳しくはこちら
