昨日の夕方の話。 普段通り大学での講義が終わり、日課であるキャンパスでの猫への餌付けを済ませた後、家に帰り着くと、作業着を着た人たちが僕の家の扉を取り替える工事をしていた。 それだけなら特に僕の頭痛の種を増やすような出来事ではないのだが、取り外されて去っていく慣れ親しんだ鍵とレバーがついている茶色の扉が非常に平凡であるのに対して、今からまさに取り付けられようとしている黒色の扉が非常に奇妙なもので、ああこれはまたうちの親父が何かを思いついてしまったのだなと容易に想像がついてしまうのであった。 その偏屈親父が言うには、鍵は無くす可能性があるので信用することが出来ない。手元に鍵があったとしても、目を離している隙に鍵の複製が作られてしまったかもしれない。物にセキュリティーを頼る時代はもう終わりだ。これからはパスワードを家族の各人が覚え、そうすることによって世界征服を目論む悪の科学者から我輩の発明品を守るのだ、ということらしい。 新しく設置された扉には縦にN個ずつ、横にN個ずつの正方形をかたちどるように、縦にN+1本、横にN+1本の線が薄青色で引かれていた。 一行目の正方形の左にはA、二行目の正方形の左にはB、というように、ご丁寧に行番号が書かれている。 一列目の正方形の上には1、二列目の正方形の上には2、と、列番号はどうやら数字のようだ。 N2個の正方形には各々スイッチが一つずつ配置されており、OFFの状態だと真っ黒だが、ONの状態だと赤い丸が浮かび上がる、というセキュリティーを考えるならもう少しやりようがあるだろうというギミックが付いている。 そして全てのスイッチのON/OFFを正しく合わせたときのみ、扉が開く、という派手好きの親父が大満足な仕様となっているようだ。
さて、ここでの僕の問題は、このパスワードをきちんと覚えられる自信が無い、ということだ。 自分で言うのも何なのだが、僕は頭がそんなに悪くないつもりなので、パスワードの大体は覚えていられるだろうと思うのだが、機械という物は融通が効かないものだからほんのちょっと間違っただけで、寒空の下で夜を過ごすことになりかねない。 しかし、パスワードを書き写して持ち運べば、親父に見つかったときに小遣い抜きなどの理不尽な制裁が加えられることが予想される。 そこで僕はある作戦を思いついたんだ。 各行、各列の正方形に含まれる赤丸の個数をメモしてそれを持ち運ぼう。 一行目のN個の正方形に含まれる赤丸の個数、二行目のN個の....、 一列目のN個の正方形に含まれる赤丸の個数、二行目のN個の....、 という風に2N個の数字をメモしておけば、もし他の人に見られてもただの数字の羅列だ。何が何だかきっと分からないだろう。
やあわざわざここまで読んでくれた君。 ああそうだ、この作戦にはもしかしたら致命的な欠陥があるかもしれない。 複数のパスワードが、同じメモになってしまうかもしれないのだ。 そうなると、寒空(略)ということになりかねない。我が身の健康を揺るがす一大問題だ。 そこで君には、このメモの数字を入力すると、復元可能なパスワードが一つに定まるかどうかを判定するプログラムを書いてほしい。 一つに定まるなら、Yes、そうでないなら、Noと出力するだけのプログラムさ。簡単だろう？ もしかしたらメモをとった時に赤丸を数え間違ったかもしれない。その場合は復元できるパスワードが1つも存在しないかもしれないが、その時は迷わずNoと返してくれ。 ああそうそう、間違っても僕の家に勝手に入ろうとはしないでくれよ。親父の趣味の危ない機械や罠が並んでいるから、命の保証が出来ないからね。
N 1行目の和 2行目の和 ... 1列目の和 2列目の和 ...ただし、N は 1 ≤ N ≤ 10000 を満たす整数である。
2 1 2 2 1
Yes
3 2 1 2 2 1 2
No
10 0 1 1 2 5 5 5 8 8 9 0 1 3 3 3 6 6 6 7 9
Yes