第三回日本最強プログラマー学生選手権 -決勝- (オープンコンテスト)

　遅刻参加してA一完。

コンテストへのリンク

コンテスト後のツイート

第三回日本最強プログラマー学生選手権 -決勝- (オープンコンテスト)　遅刻して参加したとはいえ、Aに一時間かかって辛い気持ちに。
A 大きい数字から考えると、その数字を取り除いたとき二つの連結成分に分かれるなら二項係数を掛けていけばOK。これは小さい順にUnionしていっても求められる。

— titia (@titia_til) August 28, 2022

B - Increment and Rotate

　解説AC。一応考えて分からず解説を見たのだけど、問題を誤読していた（先頭でなくても+1できる問題を考えていた）ことに気付いて愕然とした。

　また、解説の「～は有名問題で」の部分は理解できなかった。

　私は、解説のkを見つけて、B=（A[k:]+A[:k]）*2とした後、

・stackを使って、各index i に対して、j>iかつB[j]>=B[i]となる最小のjを見つける。（この配列をMAXINDと呼ぶことにする）

　とした。（これは有名問題っぽい。）

　これと累積和を使うと、x～x+Nにおけるmax($A_x$, $A_{x+1},..., $A_{x+N}$)の総和（解説で「以下の問題を解けばよいです」と書いてある部分）は、差分計算でO(N)になると思う。

　B[x]>B[x+1]のときの差分計算が一回で書けないけど、一回B[x]～B[MAXIND[x]]について足したものは二度と足されないので。

C - Not a Multiple of 3

　解説AC。

　同じ数字に注目すれば良いのか、なるほど。