DISCO presents ディスカバリーチャンネル プログラミングコンテスト2016 予選 B問題 ディスコ社内ツアー - あったこといろいろ

コンテスト中に解法を思いつけなかったので、AtCoderの解説とTwitteを参考に解きました。 問題 B: ディスコ社内ツアー - DISCO presents ディスカバリーチャンネル プログラミングコンテスト2016 予選 | AtCoder 面白さがそれぞれA_iの部屋が環状にならんでいて、面白さが広義単調増加となるように部屋を回る。 1番目の部屋を出発点としたとき何周する必要があるかをもとめる。 みたいな問題 解法 実際にぐるぐるまわる単純なシュミレーションを書くとO(N^2)になり部分点の20点が得られます。 満点解法もぐるぐるまわるシュミレーションなのですが、面白さが等しい部屋をまとめて管理することで高速化でき、O(N)で解くことができます。 まわる部屋はかならず広義単調増加になっているため、面白さが等しい部屋は必ず続けて通ることになります(例 : 2 1 3 2 2 2 -