最強最速アルゴリズマー養成講座：細かすぎて伝わりにくいTopCoderのコーディングスキル向上マジック (2/3)

今回の問題

　このところ難しい問題が続いていましたので、今回は少し難易度を落としてみました。SRM452 Div1Easy／Div2Mediumの問題です。

Bob has a width x height rectangular board divided into 1 x 1 cells. Rows of the board are numbered 0 to height-1 and columns are numbered 0 to width-1.

Each cell can contain at most one stone, and the Euclidean distance between each pair of stones must not equal 2. The Euclidean distance between cell in row x1, column y1 and cell in row x2, column y2 is defined as the square root from （x1-x2） * （x1-x2） + （y1-y2） * （y1-y2）.

Return the maximal number of stones he can place on the board.

Constraints

- width will be between 1 and 1000, inclusive.

- height will be between 1 and 1000, inclusive.

　いつものように大意がつかめるレベルで日本語に訳してみると以下のようになります。問題文が英語だという部分で腰が引けてしまう方もおられると思いますが、筆者にしても本番では時間短縮のためにYahoo!翻訳を利用しています。厳密な訳ではなく、大意さえつかめればよいので、あまり難しく考えないようにしましょう。

縦の長さがheight、横の長さがwidthのマス目で構成された盤面があります。このマス目の中に適当に石を置きます。この時、石を入れたマス目の中心の距離がちょうど2マス分だけ離れたマスに石を置くことはできません。このルールに従うとき、この盤面に最大いくつの石を置くことができるでしょうか？

　ルールが少しだけ分かりにくいので、図を交えて説明しましょう。ここでは5×5の盤面で考えてみます。まず、盤面の真ん中に石を置きます。すると、ちょうど距離が2マス分のマス、つまり、上下左右2マス離れたマスに石を置くことができなくなります（下図左）。こうして石を連続して置いていくと、下図右のように置く場所がなくなります。

問題を簡略化して5×5の盤面で考えてみます。盤面の真ん中に石を置くと（左図）、問題の条件から上下左右2マス離れたマスには石が置けなくなりますので右図のようになります

　ここでは適当に石を並べただけですので、この図が最も良い置き方であるかどうかは分かりません。こうして石を置いていったときに、置ける石の個数をできるだけ多くしたいというのが今回の問題です。なお、盤面の大きさは、縦横ともに1000以下とします。

　今回も、問題に取り組みやすいように問題挑戦用のソースコードを用意しました。問題側で設定されたサンプルデータが前半に5つと、本当に正しいかどうかを検証するための凶悪なデータの後半5つを自動でチェック可能になっていますので、気軽に問題に挑戦していただけます。C++、C#、Javaの3種類を用意しましたので、好きな言語で挑戦してください。

ヒント

　これまでの連載で取り扱った問題と比べると、かなりとっつきやすいのではないでしょうか。少し慣れている人であれば、すぐに方針が見いだせるかと思います。そうした方は、もう一段掘り下げて、どの様にコーディングすれば早く美しいものになるかを考えてみてほしいと思います。

　方針が立たない？　それは残念ですが、そんな場合でもまずは手を動かしてみてはいかがでしょうか。問題が分からないときの対処法は人それぞれですが、筆者の場合は、

• 紙の上でシミュレートして、どんな風になるか試してみる
• それでもダメならコンピュータを使ってシミュレートして試してみる

といった方法を取ることが多いです。まずは頭を使って考えるのは非常に大切ですが、考えてもすぐに見つからない場合は、この手の問題の場合、手を動かしてみることで新たな規則性などを見つけることが可能となる場合が多いです。ひとたび規則性が見つかれば、案外簡単に解答にたどり着けるでしょう。