2022-03-22 ABC241 E - Putting Candies を解いた。
ABC241 : AtCoder Beginner Contest 241（Sponsored by Panasonic） E - Putting Candies を解いた。
問題: https://atcoder.jp/contests/abc241/tasks/abc241_e
本番では D 問題のあと C に戻って解かなかったようだけど E にしては簡単な問題だった。 C を捨ててこちらを解けば良かった。
K <= 10^12 なのでシミュレートして解くことはできない。追加するアメは A_{X mod N} のものなので最大で N を周期とした繰り返しがある。初期位置である 0 から順に遷移を進めて同じ位置に来たところが周期の開始位置になる。これで周期の開始位置までの長さと周期の長さが得られる。この処理は最大でも N なので単純にシミュレートすれば良い。同様に周期で加算される数値の和をとる。
K が周期の開始位置より手前ならシミュレートすれば良い。そうでなければ周期の開始位置までの長さを取り除いて残りを周期の長さで割る。この商と余りを使って遷移せずに周期分を遷移したことにする。商と周期で加算される数値の和を掛けたものが遷移したことにした分になる。余りと周期の開始位置までの長さをシミュレートすればそれ以外の部分が求められる。それらの和が答えになる。
提出: https://atcoder.jp/contests/abc241/submissions/30351686 解説: https://atcoder.jp/contests/abc241/editorial
のどが痛い。龍角散を飲んだ。
今日のコミット。