コンテスト中AC:A〜D
コンテスト後にEを自力AC。コンテスト中に漠然とした解法まで思い浮かんでましたが、実装間に合わず。
A〜Dは特に書くことがないので、Eについて書きます。
2022/07/08追記
Eの実装中の同値類などは誤りなので、無視してください。
E - Packing Potatoes
説明のため、じゃがいもは円環に並んでおり、番目のじゃがいもまで行ったら
番目に戻るものとします。
の各
について、空の状態の箱に
番目のじゃがいもから箱詰めを開始したとします。この箱の箱詰めを終了し、次の箱の箱詰めを
番目から開始するとします。
という関係性を有向辺とみなしてグラフ化します(この関係性は一定です)。
頂点から出発して有向辺を辿ることを繰り返すと、鳩の巣原理により高々
回で1回訪問済みの頂点に辿りつき、以後ループします。
有向辺を1回辿るということと、箱詰めが1回終了したことが対応します。従って、回目の箱詰めを始めたじゃがいもの番号は、有向辺を
回辿って、辿り着いた頂点番号に対応します。
回でどこの頂点番号に辿り着くかというのは、まず、ループ前の非ループ部とループ部に分けて配列に記録しておきます。非ループ部ならそのままその頂点番号を返し、ループ部に辿り着くなら、ループに属する頂点数をループのサイズとして、ループサイズでmodを取ることで
で求められます。
以上から、番目のじゃがいもから始めた時に箱に詰めることになるじゃがいもの個数
を予め計算しておけば、各クエリに
で答えられます。
過去にもこのような構造をもつ問題は何度か出題されており、構造体Loopとして計算できるようにしてあります。
結構出題されるので、計算方法の詳細は別記事にまとめてみたいと思います。
次に、の求め方です。愚直に
以上となるまで足し続けることは計算量的にできません。まずは円環で並ぶ
を何周するか求めます。これは、
の和を
とすると、
周する必要があります。これを
としておきます。
残りは必要です。これを
とします。残りは一周未満であることが確定します。
合計が以上となるのに残り何個のじゃがいもが必要かを求める方法としては、
を2つ繋げた
を用意し、累積和
を求めます。
番目のじゃがいもについて、
をキーとして
を二分探索することで求めることができます。 (但し、
の時
)
二分探索した結果、となる、
が求まったとします。
すると、
となります(実装では累積和を取る時にインデックスがずれて計算がおかしくなったので、注意)。
Submission #32991116 - AtCoder Beginner Contest 258