競技プログラミング用 知識集積所
ABC401C - K-bonacci
最終更新：
sport_programming
-
view
問題
必要知識
B以下レベルの内容は省略
考え方
一見、
- 自分より前にが項がk個未満しか場合は、値は1
- 自分より前にが項がk個以上ある場合は、値は直前k個の合計
- n番目（人間的にはn+1番目）を10億で割ったあまりはいくつか？
を愚直に実装すればよさそうに見える。
しかし、それでは2つの問題が発生する。
しかし、それでは2つの問題が発生する。
1つめは、実行時間がかかりすぎる問題。
kが50万、nが100万であれば、50万項の足し算を50万回ループで、2500億回の計算が必要で間に合わない。
そこで、sliding window法を用いてループ内の計算を高速で終わらせる。
kが50万、nが100万であれば、50万項の足し算を50万回ループで、2500億回の計算が必要で間に合わない。
そこで、sliding window法を用いてループ内の計算を高速で終わらせる。
2つめは、値が大きすぎる問題。
k=3くらいで最初の20項くらいを求めてみるとわかるが、この数列の値は指数関数的に増えていく。
ということは、最終的には値が数万桁を優に超えると予想され、まともに扱うことができない。
しかし、仮にまともに計算した場合に和と差しか行わない点、最後に10億で割った値だけ答えればよい点から、剰余類環の計算で済ませればint型の範囲で処理することができる。
k=3くらいで最初の20項くらいを求めてみるとわかるが、この数列の値は指数関数的に増えていく。
ということは、最終的には値が数万桁を優に超えると予想され、まともに扱うことができない。
しかし、仮にまともに計算した場合に和と差しか行わない点、最後に10億で割った値だけ答えればよい点から、剰余類環の計算で済ませればint型の範囲で処理することができる。
この2点を工夫しながら、「条件通りの数列の各項を10億で割ったあまりの数列」を再現し、n+1項以上になったところで該当の項を出力すればよい。
解答例
注意点
C++の剰余計算に注意
C++では、負数の剰余は負数で返ってくる。
sliding window法の都合で差をとった結果負数になる可能性がないとは言い切れないので、解答しようとした数値が負数の場合は10億を加えてから答えること。
sliding window法の都合で差をとった結果負数になる可能性がないとは言い切れないので、解答しようとした数値が負数の場合は10億を加えてから答えること。
intの桁あふれに注意
最大10億-1の計算を行うため、値を同時に3つ足し引きするとオーバーフローを起こす可能性がある。
和や差を1回行うたびに丁寧に%10億するか、面倒ならlong long型を使うこと。
和や差を1回行うたびに丁寧に%10億するか、面倒ならlong long型を使うこと。
