AtCoder Grand Contest 022 C - Remainder Game を解くときに考えたこと

背景

chokudai.hatenablog.com

こういう記事が出ました。で、ぼくが気になったのが、実際のところこの記事で言及されている問題(C - Remainder Game)を解くときに人々はどういう思考をするんだろう? ということでした。多分他の人も気になっていると思うので、先ず隗より始めよということで自分が考えたことを書きます。無駄なこともいろいろ考えてて長くなりますが、おつきあいください。

筆者について

amylase - AtCoder

これを書いているとき AtCoder Rating 2302 です。700 点問題なら時間さえあればまあ解けるんですが、コンテスト中に確実に通せるかと言われると……というのが最近の実感です。

 

では始めます。

初手の決定

(典型っぽい要素から出てきたアイデアを太字で強調します)

1回のコストは 2^k ということからいかにもビットで考えてくださいという雰囲気を感じ取り、同じ k を2回以上使う必要がないならビット列の辞書順最小なるなあとまず思います。辞書順最小には文字を先頭から小さい順に試して可能かどうか判定するという典型があるので、これに落ちると嬉しいということを意識しました。

つぎに k を選んで操作するのを繰り返すという点ですが、これについては元記事にもあるように k の順序や回数に便利な制約をつけられると嬉しい気持ちになりました。コストの部分でも言ったように2回以上使わないという制約があるといい感じですし、順番についてもいい感じの制約をつけられないか考えることにしました。

操作列に関する考察

いきなり全体で考えると頭が爆発するので、ぼくがよくやるのは部分問題について考えることです。これが解けないと話にならないし、部分問題の考察結果が活用できることはよくあります。で、今回考えた部分問題が n = 1 かつ出力が -1 かどうかのみ判定するというやつで、これについては a / 2 より大きい k を選ぶことを考えると  b が x / 2 未満であることが必要十分だとわかります。が、これだけではどうこうできる感じでもありません。

コストについても考えていきたいので、引き続き n = 1 で k の列の制約について考えます。n = 1 なので mod は必ず取るとしてよいことに留意しつつ、たとえば 2, 3, 2 の順でやることに意味はあるのか……と想像していくと、なんとなく同じやつは2回やっても無駄な感じがしますが、証明できる感じはしません。

(ここで結構考える)

具体例で色々計算しているうちに、小さい k で mod を取ったあとでそれよりと同じか大きい k を選んでも値は変化しないことに気が付きます*1 。すなわち、意味のある操作列は k_1 > k_2 > k_3 > ... を満たすということで、辞書順最小の典型に落ちることが分かりましたし、この結果を得たときにこの問題が解けそうだという感触を得ます。

判定問題

 今までに考えてわかったことをまとめると、次のようなコードを書けばいいことになります。

  • 各要素についてコスト無視で可能かどうか判定してダメなものがあれば -1 *2
  • k として max(a) から 1 まで大きい順に、「それがないとダメか判定」して必要なら入れる
  • 必要な k のコストの総和を出力

あとは「それがないとダメか判定」を詰めればいいわけです。

部分問題から考えて1個ずつ、k 未満を全部使っても b にはならないかどうか判定し、もしそうなら a を x % k で書き換えていけばいいかなと考えます。たとえば、次の入力

2

17 10

8 1

に対して、k = 9 は 17 に対して絶対必要なので使用します。

ここで気になったことが出てきて、ある k が必要だとわかったときにそれをほかの a  の要素を書き換えるのに必要かどうかは定かではないということです。先程の例だと 10 を k = 9 で 1 に書き換えれば終わりですが、これの b_2 が 1 ではなく 2 だと書き換えないほうが得です。

書き換えてループを回す戦略がうまく行かなさそうなことがわかったのでこの方針を捨て、辞書順最小の典型で判定問題を書くときに利用できるすでに決定した列の情報を利用することを考えます。

n = 1 で k の操作列が与えられたときに a を b にできるか考えると、これは部分和問題の足し算を mod k に置き換えたものだと気がつき、同じような動的計画法を実装すればいいことがわかります *3

実装

https://beta.atcoder.jp/contests/agc022/submissions/2408219

これをコードにすると上のようになり、これで AC です。a < b のケースを見落として 1 WA 食らいました……。

dp 関数が部分和問題を変形した動的計画法の部分で、ok 関数が判定問題の部分です。

最後に

他の人が解いた過程も知りたいので他の人も書いてください!!!

他の人

AGC022 とか reminder game atcoder でググって出てきた皆さんです。判定問題の部分で解説にあるようなグラフ構築でやってる人が多いです。

noimin.hatenablog.com

hamko.hatenadiary.jp

kurkur.hatenablog.com

thaim.hatenablog.jp

d.hatena.ne.jp

(22:08 追加) 各操作が最大1回ってのが見えるの速くてビビる あとぼくも時間計っておけばよかった

tozangezan.hatenablog.com

*1:これが典型に思える人だと10分ACが見えてくるのだと思います

*2:最初に考えた部分問題の結果をそのまま利用します

*3:実際にはなんか有名 DP っぽいと思ったところで実装がイメージでき、今これを書くときに部分和問題の名前を思い出しました