【うぃんじー Advent Calendar 2016】部内JOI予選対策コンテスト3問目
この記事はうぃんじーAdventCalendarの7日目の記事として書かれています
6日目の記事で言っていた、作問を担当した3問目の問題の解説です。
随分と時が流れた気がしますね。
問題文
仲の良いスライム
スライム達が段ピラミッドを構成しようとしています.
各スライムは色0～2の3色のうちどれかの色を持っています. また, 各色のスライムは無限にいます.
ただし, 色が同じスライムどうしは仲が良すぎるため、隣り合うと嬉しくて消えてしまいます. これではピラミッドが崩壊するのでまずいです.
※「隣り合う」とは, スライムの6近傍(ピラミッド状であるため)のどこかに相手のスライムがいる状態を指します.
そんな複雑な事情にも関わらず, 芸術家のらてまるた様はピラミッドにいくつかの注文を言いつけてきました.
ピラミッドの個の位置について, そこに置くスライムの色を指定してきたのです.
あまりに難しい注文に見えるため, あなたはらてまるた様が無理難題を言っていないか調べることにしました.
入力
...
最初にデータセットの数Tが与えられます.
各データセット毎に, 整数N, Qが与えられます.
各注文を表すは, 最上段を0段目として数えて
段目の, 左端のスライムを0匹目として数えて
匹目の位置は, 色
でなければならないことを示しています.
出力
各データセットについて, ピラミッドが構成可能ならば"OK"を, そうでないなら"NG"を1行に出力してください.
制約
解法
まずピラミッドの1番上のスライムの色を決めてみる。
すると、その下2つのスライムの色の組み合わせが2通りになる。
試してみると分かるが、そうして合計6通りの上3つのスライムの色の組み合わせを決めてしまうと、残りのスライムの色が一意的に決まってしまう。
つまり全体の色の組み合わせも6通りしかなくて、容易に全探索できる。
また、そうして定まったピラミッドは、3方向のどの方向についてもスライムの色が規則的に変化している。(1ずつ減るか増えている)
そこで、ある位置のスライムの色については式を書いてで計算でき、つまり、Q個の注文を満たしているかを
で知ることが出来る。
よって、全体としてもである。
感想
6日目の記事を見れば分かるが、序盤の問題であるにも関わらず2人しか解かなかったので反省している。
明らかにJOIに出なさそうな問題なのに、思いついて楽しかったのでねじ込んでしまった。
しかも発想問は作問者にとって簡単に見えるという罠にはまってしまい、3問目という序盤にぶち込んでしまった。完全に1年生キラーになってしまい、ごめんなさい。
