AtCoder Grand Contest 022 C 「Remainder Game」

問題文

C - Remainder Game

 

kとして選ぶ数の集合だけが重要で、順序はどうでもいいという気付きと(それはすぐわかるけど)、2^x>2^0+2^1+...+2^(x-1)という性質から、xを選ばないで済むなら選ばない方がいいという気付きが本質っぽい。辞書順最小は貪欲法というアレ。

 

kとして選ぶ数の集合をSとする(明らかに、kは大きい方から選んでいくべきなので、順序は気にしなくていい)。

2^x>2^0+2^1+...+2^(x-1)なので、1以上x-1以下の数からkを選んで目的を達成できるなら、xは選ばなくていい。逆に、達成できないならxは絶対に選ばなければならない。

そこで、「すでに選んでいる数の集合Sの要素と、1以上x-1以下の数だけをkとして選ぶとき、目的を達成できるか?」を判定できればいいということがわかる。

これは、i%x==jとなるようなkとして選べる数xが存在するとき、頂点iから頂点jに有向辺を張った有向グラフを作って、a[i]からb[i]に行けるかどうかを調べることで判定できる。

なお、そもそもaからbに出来ないのは、a[i]≠b[i]かつb[i]≧a[i]/2を満たすiが存在するとき(x>yのときxをyで割った余りはx/2未満であるため)。逆に、このようなiが存在しないときは、a[i]≠b[i]となるiについてa[i]をa[i]-b[i]で割ってやれば余りはb[i]になるので目的は達成できる。