第１０回日本情報オリンピック　予選３

2010年12月23日
情報オリンピック日本委員会

解説

三色のタイルがやや複雑な形に並んでいるので，それをどう処理するかが問題である． 左から a 列目，上から b 行目のタイルを (a,b) で表す．

解法１

壁画の一番左側の辺とタイル (a,b) との距離は a-1 であり， 一番右側の辺とタイル (a,b) との距離は n-a である． また，一番上の辺とタイル (a,b) との距離は b-1 であり， 一番下の辺とタイル (a,b) との距離は n-b である． タイル (a,b) の色は「a-1, n-a, b-1, n-b の最小値を 3 で割った余り」で決まる． 具体的には，余りが 0 のときは赤，余りが 1 のときは青，余りが 2 のときは黄色である．

解法２

壁画に 2 本の対角線を引いて，次のような 4 つの領域に分割して， 領域ごとに考えてもよい．

• a ≦ b,  a+b ≦ n+1 をみたす領域１
• a ≦ b,  a+b ＞ n+1 をみたす領域２
• a ＞ b,  a+b ≦ n+1 をみたす領域３
• a ＞ b,  a+b ＞ n+1 をみたす領域４

それぞれの領域ごとにタイルの色を決定することができる． 領域１ではタイル (a,b) の色は a-1 を 3 で割った余りで決まる （余りが 0 のときは赤，余りが 1 のときは青，余りが 2 のときは黄色である）． また，領域２ではタイル (a,b) の色は n-b を 3 で割った余りで決まり． 同様に，領域３ではタイル (a,b) の色は b-1 を 3 で割った余りで決まり， 領域４ではタイル (a,b) の色は n-a を 3 で割った余りで決まる．

解法３

別解として次のような方法もある． n × n の配列を用意して，壁画のどの位置にどの色のタイルがあるかを全て調べる． 多重ループを使えば， n × n の壁画データを作成するプログラムを書くのは容易である． 壁画データを作成してしまえば，どの位置のタイルが何色であるかはすぐに分かる．

この方法の方がやや直感的で，デバッグもしやすいかもしれない．

この方法の欠点は計算に無駄が多く，膨大なメモリが必要なことである． n がとても大きい場合は， メモリが足りずに n × n の配列を確保することができないかもしれない． また，仮に確保できたとしても， 壁画データの作成を競技時間内に終わらせることができない可能性が高い． この問題で満点を取るには，解法１や解法２のような効率のよいアルゴリズムを設計する必要があるだろう．