# 問題 さからっしゅくんは一発ドッカン型の魔法使いです。 魔法を使うと魔力を使い果たしてしまいますが、魔力は毎日溜まっていきます。具体的には最後に魔法を使った日から数えて$k$日目の魔力は$M_k$だけ溜まっています。 いま、さからっしゅくんは$N$つの国を旅して自分の村に帰ってきました。頑張って$1$日に$1$つの国を巡ったので旅は$N$日間で終わりました。 訪れたどの国にもダンジョンがあり、$i$番目の国では強さ$P_i$の魔物が宝物を守っていました。強さ$p$の魔物は魔力が$p$以上溜まっていれば魔法を使って倒すことができます。さからっしゅくんはマメな性格をしているので、倒せる魔物は全て倒しましたが、一方でサバサバした性格をしているので、倒せない魔物には挑まず、そのまま次の国に向かいました。ただし旅を始めてしばらくの間は、レベルが足りず、ダンジョンに入れてもらうことすらできませんでした。 旅の途中、さからっしゅくんは気まぐれに、ある期間だけ日記をつけました。村に帰ってから日記を読み返すと、1ページ目に「今日初めて魔物を倒した。今日から日記をつけることにしよう」と書いてあり、残りは「今日は$d_t$日ぶりに魔物を倒した」と書いてあるページが20ページあるだけでした。 さて、この日記を付け始めたのは何番目の国だったでしょうか? ただしこの日記からでは1つだけに絞れないかもしれないので、候補となる国をすべて見つけ出してください。 なお、さからっしゅくんの記憶は曖昧なので、日記に書いてある「$d_i$日ぶり」という記述は、実際の間隔と最大5日ズレている可能性があります。 ### 入力 - 国の個数を表す整数$N$ - 魔力の溜まり方を表す実数列$(M_k)_{1\leq t \leq 85}$ - 魔物の強さを表す実数列$(P_i)_{1\leq i \leq N}$ - 日記の記述を表す整数列$(d_t)_{1\leq t \leq 20}$ ### 制約 $20 \leq N \leq 10^8$ $20 \leq d_1+d_2+\cdots+d_{20} \leq N$ $0 \leq P_i < 1$ $(M_k)$は広義単調増加で, $M_{85} = 1$. ### その他 - 日記をつけている間、魔物を倒した日には必ず日記を書いていた。 - 旅を始めた時点でさからっしゅくんの魔力は最大まで溜まっていた。
×
Sign in
Email
Password
Forgot password
or
By clicking below, you agree to our
terms of service
.
Sign in via Facebook
Sign in via Twitter
Sign in via GitHub
Sign in via Dropbox
Sign in with Wallet
Wallet (
)
Connect another wallet
New to HackMD?
Sign up