ライブラリを盆栽しておくと5完だった(机上の空論)
A - Arithmetic Progression
Aから初めてBになるまでDを加算し続ければよいです
B - Append
push_back()を知っていますか？はい
C - Divide and Divide
Nが10^17と大きくてビビるが、この操作は一度行うごとに値がだいたい半分になるので、メモ化再起を用いることによりO(log(N))が達成可能です。
D - Super Takahashi Bros.
ステージiからステージi+1にコストA_iの有向辺を、ステージiからステージX_iにコストB_iの有向辺を張ると、ステージ1からステージNに到達するまでの最短経路問題に帰着できるので、ダイクストラ法によりこの問題が解くことができる。
...のだけど、コンテスト中はDPだと思って処理を書き始める→後ろに戻ることがあるのでBFSで処理をする...としてTLEした。そのTLEを受けて「あ、これ時間が早い順に処理すればいいじゃん」と気づいてBinaryHeapを持ち出し、提出してからダイクストラだったことに気づいた。
考察はちゃんとしよう。i < X_iが保証されていればDPでも解けましたね。
E - Mancala 2
RAQを処理できるデータ構造を持っていますか？私は持っていません
BITを書いてACした。これ緑diffってマジですか？