ABC214

結果

A

B

C

ノーペナ完で，パフォは，rating変動はででした．

考察

A問題

ならを出力．

ならを出力．

ならを出力．

B問題

は非負整数なので，を満たすは，です．

の最大はなので，で全探索できます．

C問題

番目の人の出力結果をで初期化しておきます．

番目の人から反時計回りに宝石を渡し続けていき，渡す時刻が最適であれば更新し，そうでなければ番目の人に移ります．

一見二重ループですが，渡す時刻が更新されるのは高々2回(多分？)なので問題ありません．

例えば内側のループで番目の人まで渡す時刻を更新し続けたとすると，外側のループでは番目の人から番目の人までは見る必要はありません．(実装的には，内側のループは1回目で脱出します．)このときの内側のループの更新では，明らかに番目の外側のループと同じ更新をすることになるためです．

よって，続きは番目の人から見ればよく，計算量は線型です．

外側のループで最後に見る人が最適な時刻を持っていた時が最悪で，このときは最後に全ての時刻を更新することになります．(この時が更新回数が最大で2回？)

感想

1か月ぶりのABCでしたが，ほとんど冷えなくてよかったです．

仕事が落ち着いてきたので(?)少しずつ復帰したいです．