ABC 401-500/ABC457C - Long Sequence - 競技プログラミング用 知識集積所

---

問題

ABC457C

必要知識

B以下レベルの内容は省略

• 特になし

考え方

愚直に数列Bを作っていくと、時間もメモリも足りない。
そこで、該当位置がある区間以外は真面目にやる必要がないことを利用して高速化する。

例えば長さ3の数列を5回作る場合、数列を15個構成することになる。
この長さを前から順に和を取っていくか、kの値から引いていくことで、該当がない区間を高速に進んでいく。

次に構成する個数で該当位置を超えそうな場合、数列の中身を少し真面目に見る。
1回にくっつける数列の長さで割った余りを見れば、該当位置が数列の何番目の要素に当たるかを求められる。
剰余をそのまま利用するために、0-indexに統一して扱うと実装しやすい。

解答例

解答例

注意点

別解