競技プログラミング用 知識集積所
ABC438E - Heavy Buckets
最終更新：
sport_programming
-
view
問題
必要知識
B以下レベルの内容は省略
考え方
特定の人が持っているバケツは、いついかなるターンからでも今後の各ターンで受ける影響が同じである。
ということは、ダブリング※の出番。
ということは、ダブリング※の出番。
- 各人が持っているバケツが、1ターン後に、誰が持っていて、重さがどれだけ増えているかの一覧を作る
- 各人が持っているバケツが、2ターン後に、誰が持っていて、重さがどれだけ増えているかの一覧を作る（1ターンの処理を2回やればわかる）
- 各人が持っているバケツが、4ターン後に、誰が持っていて、重さがどれだけ増えているかの一覧を作る（2ターンの処理を2回やればわかる）
- 各人が持っているバケツが、8ターン後に、誰が持っていて、重さがどれだけ増えているかの一覧を作る（4ターンの処理を2回やればわかる）
- 中略
- 各人が持っているバケツが、2^30ターン後に、誰が持っていて、重さがどれだけ増えているかの一覧を作る（2^29ターンの処理を2回やればわかる）
を事前に全部作っておく。
あとは、例えば27ターン目の情報が欲しければ、27のビットを見て「16ターン+8ターン+2ターン+1ターン」の経過をたどればよい。
