Looksery Cup 2015 B. Looksery Party

こういうのどういう思考過程で思いついたのかメモしておこう。

人が n 人いて、それぞれ互いの電話番号を知っていたり知っていなかったりする。

パーティに人を呼ぶと、呼ばれた人は知っている電話番号すべてに電話をかける。自分の電話番号は知っているので自分にもかける。

数列 a1, a2, ..., an が与えられる。パーティに呼ぶ人をうまく選んで、人 i が電話をかけられた回数が ai にならないようにできるか。できる場合は呼ぶ人の集合を具体的にひとつ求めよ。

（最初、「自分の電話番号は知っているので自分にもかける」ことを読み落とす）

結局、行列 P とベクトル a があって Px と a がどの要素も異なるような x ∈ {0, 1}^n があるかを判定する問題。でもこんなの解けるはずがない。

（問題文を読み直して「自分の電話番号は知っているので自分にもかける」ことを知る）

あからさまに怪しいのでこれの意味について考える。

人 i が電話をかけられた回数が ai に一致してしまったら、人 i を呼ぶ/呼ばないをひっくり返せば、少なくとも人 i については大丈夫。

でも他の人がやばくなるかもしれない。その時は他の人もひっくり返せばいいかと思いきや、また人 i がだめになってしまって、循環するかもしれない。

落ち着いて自明なパターンから考える。誰も呼ばないと ai = 0 の人がやばい。そういう人がいたら、とりあえず呼ぶとする（他の人を呼ぶ手もあるけど、あからさまに怪しい制約を活かすとしたら、その人自身を呼ぶことにするのがよさそう）。

その結果やばい人が現れたら、その人も呼ぶことにする。とやっていくとどうなるか？いやさっきと同じで循環するのでは？

よく考えると循環はしない。最初誰も呼んでいなくてやばい人がいたらその人を呼ぶ、をやると電話された回数は増えるだけで減らない。だから、一度やばくなって呼ばれた人がまたやばくなることはない。