Codeforces Round 1056 (Div. 2)

　Bまで二完。Cを考えていたら睡魔に襲われた。

コンテストへのリンク

C. The Ancient Wizards' Capes

　解説AC。
　実は答えが少ないのでは？　とはコンテスト中も思ったのだが、どうしてそうなるかが分からなかった。

　コンテスト中、寝る直前に思ったことが正解で、式にしてみると良かった。

　右に立っている人を1、そうでない人を0とし、各A_iについて式を立てると、A_i-A_{i+1}を考えることで、i番目とi+1番目の関係性が出てくる。それを使えば、一番目が決まれば他全て決まることが分かる。

　として解けたけど、やっぱり結構難しく感じる。あまり速く解けるビジョンが湧かない。