geam1113’s diary

主にAtcoderのコンテストの備忘録を書きます。AtCoder緑と水色を行ったり来たりしています。

AtCoder Biginner Contest 258 参加記録

コンテスト中AC:A〜D
コンテスト後にEを自力AC。コンテスト中に漠然とした解法まで思い浮かんでましたが、実装間に合わず。
A〜Dは特に書くことがないので、Eについて書きます。

2022/07/08追記
Eの実装中の同値類などは誤りなので、無視してください。

E - Packing Potatoes

説明のため、じゃがいもは円環に並んでおり、N-1番目のじゃがいもまで行ったら0番目に戻るものとします。

1\leq i\leq Nの各iについて、空の状態の箱にi番目のじゃがいもから箱詰めを開始したとします。この箱の箱詰めを終了し、次の箱の箱詰めをA_i番目から開始するとします。
i\rightarrow A_iという関係性を有向辺とみなしてグラフ化します(この関係性は一定です)。

頂点0から出発して有向辺を辿ることを繰り返すと、鳩の巣原理により高々N回で1回訪問済みの頂点に辿りつき、以後ループします。

有向辺を1回辿るということと、箱詰めが1回終了したことが対応します。従って、K回目の箱詰めを始めたじゃがいもの番号は、有向辺をK-1回辿って、辿り着いた頂点番号に対応します。

K-1回でどこの頂点番号に辿り着くかというのは、まず、ループ前の非ループ部とループ部に分けて配列に記録しておきます。非ループ部ならそのままその頂点番号を返し、ループ部に辿り着くなら、ループに属する頂点数をループのサイズとして、ループサイズでmodを取ることでO(1)で求められます。

以上から、i番目のじゃがいもから始めた時に箱に詰めることになるじゃがいもの個数B_iを予め計算しておけば、各クエリにO(1)で答えられます。

過去にもこのような構造をもつ問題は何度か出題されており、構造体Loopとして計算できるようにしてあります。
結構出題されるので、計算方法の詳細は別記事にまとめてみたいと思います。

次に、A_i,\ B_iの求め方です。愚直にX以上となるまで足し続けることは計算量的にできません。まずは円環で並ぶWを何周するか求めます。これは、Wの和をSとすると、\lfloor \frac{X}{S} \rfloor周する必要があります。これをQとしておきます。

残りはX\ mod\ S必要です。これをRとします。残りは一周未満であることが確定します。

合計がR以上となるのに残り何個のじゃがいもが必要かを求める方法としては、Wを2つ繋げたW'を用意し、累積和Sを求めます。
i番目のじゃがいもについて、R+S_{i-1}をキーとしてSを二分探索することで求めることができます。 (但し、i=0の時S_{i-1}=0)

二分探索した結果、W_i + W_{i+1} + \cdots + W_j\geq R となる、jが求まったとします。
すると、
A_i \leftarrow (j+1)\ mod\ N
B_i \leftarrow N\times Q + j-i+1
となります(実装では累積和を取る時にインデックスがずれて計算がおかしくなったので、注意)。
Submission #32991116 - AtCoder Beginner Contest 258