Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Beginner Contest 258 E問題 Packing Potatoes

AtCoder ABC ABC258 E問題 500 pts

問題

atcoder.jp

提出解答

atcoder.jp

問題の概要

10^{100} 個からなるじゃがいもの列がある. 先頭から i 番目のじゃがいもの重さは W_{(i-1) \pmod{N}} である.

このじゃがいも達を次のルールによって箱に詰めていく.

  • 空の箱を用意する.
  • じゃがいもがある限り以下の操作を続ける.
    • その時点での先頭のじゃがいもを箱に入れる.
    • 箱に入っているじゃがいもの重さの総和が X 以上ならば, 箱には蓋をして新たな空の箱を用意する.

このとき, 次の Q 個の問に答えよ.

  • K_q 番目に蓋をした箱に入っているじゃがいもの個数を求めよ.

制約

  • 1 \leq N,Q \leq 2 \times 10^5
  • 1 \leq X \leq 10^9
  • 1 \leq W_i \leq 10^9
  • 1 \leq K_q \leq 10^{12}

解法1

以降では説明のため, i 番目のじゃがいもが色 (i-1) \pmod{N} であるとする. このとき, 色が同じじゃがいもの重さは等しい.

ここで, 空の箱の状態から最初に箱に入れるじゃがいもの色が同じならば, 必ず最終的に箱に入っているじゃがいもの数は等しくなることに着目すると, 次の2つが (高速に) 求められればよいことがわかる.

  • 各 c=0,1,2 \dots, N-1 に対して, 空の箱の状態から最初に箱に入れるじゃがいもの色が c であるときの最終的に箱に入っているじゃがいもの数 T_c.
  • k 個目の空の箱に入れられる最初のじゃがいもの色 C_k.

このとき, K_q 番目に蓋をした箱に入っているじゃがいもの個数は T_{C_{K_q}} である.

解法2

T_c を求めることにする. このとき, \displaystyle W_{{\rm sum}}:=\sum_{i=0}^{N-1} W_i とすると, どの色から初めても色が R:=\left \lfloor \dfrac{X}{W_{{\rm sum}}} \right \rfloor 周する. このことから, 仮に X が X \pmod{W_{{\rm sum}}} であった場合における空の箱の状態から最初に箱に入れるじゃがいもの色が c であるときの最終的に箱に入っているじゃがいもの数を T'_c とすると, T_c=RN+T'_c である.

T'_c について, 0 \leq T'_c \lt N であることに注意すると, T'_c は二分探索や尺取法で求めることにより, T'_0, \dots, T'_{N-1} をそれぞれ O(N \log N) 時間, O(N) 時間で求められる.

解法3

C_k を求めることにする. ここで, S:=\{0,1, \dots, N-1\} に対して, 写像 f: S \to S を c \in S に対して, f(c) を以下で定義する.

  • 空の箱の状態から最初に箱に入れるじゃがいもの色が c であるとき, 次の空の箱の状態から最初に箱に入れるじゃがいもの色 (つまり, 最後に入れたじゃがいもの色の次の色).

実はこの f(c) は T_c を用いることにより, f(c)=(c+T_c) \pmod{N} となる.

このとき, C_k=f^{(k)}(0) である. ただし, 非負整数 x と c \in S に対して,

f^{(k)}(c)=\begin{cases} c & (k=0) \\ f \left(f^{(k-1)}(c) \right) & (k \geq 1) \end{cases}

と定義する.

このとき, f^{(k)}(0) を愚直に求めようとすると, O(k) 時間かかり, 到底間に合わないが, ダブリングを利用することによって, O(\log k) 時間で求めることができる.

具体的には次のようにして求めることができる.

  • K_{{\rm max}}=\max(K_1, \dots, K_Q) とする.
  • t=0,1, \dots, \left \lfloor \log_2 K_{{\rm max}} \right \rfloor に対して, 次のようにして f^{(2^t)}(c)~(c=0,1, \dots, N-1) を求める.
f^{(2^t)}(c)=\begin{cases} f(c) & (t=0) \\ f^{(2^{t-1})} \left(f^{(2^{t-1})}(c) \right) & (t \geq 1) \end{cases}
  • 各 K_q に対して, K_q=2^{b_{q,1}}+\dots+2^{b_{q,m_q}}~(0 \lt b_{q,1} \lt \dots \lt b_{q,m_q} \leq \left \lfloor \log_2 K_{{\rm max}} \right \rfloor) となる (b_{q,1}, \dots, b_{q,m_q}) が (唯一) 存在する. このとき,
C_{K_q}=f^{(K_q)}(0)=f^{(2^{b_{q,m_q}})} \left(\dots \left(f^{(2^{b_{q,1}})} (0) \right) \dots \right)

である.

これによって, C_{K_1}, \dots, C_{K_Q} を O((N+Q)\log K_{{\rm max}}) 時間で求めることができる.

解法4

以上から求められた T_0, \dots, T_{N-1} 及び, C_{K_1}, \dots, C_{K_Q} から T_{C_{K_1}}, \dots, T_{C_{K_Q}} を出力すれば良い. 合計の計算量は O(N \log N+(N+Q)\log K_{{\rm max}}) 時間や O((N+Q)\log K_{{\rm max}}) 時間である.