AtCoder Regular Contest 215

　Cまで三完。良い成績とはいえないが、ARCで黄パフォを出せたのは久しぶり。

コンテストへのリンク

コンテスト後のツイート

B 各数字を0と1で塗り分け、数字が異なる間に仕切りを入れる。できるだけ同じ色にしたいので貪欲。
C (x,y,z)と(a,b,c)についてa>=x or b>=y or c>=zなら勝敗が付かないのでUnion-findでくっつける。くっつけたあと、(min(x,a),min(y,b),min(z,c))にして良い。x,y,zについてソートし大きい方から処理。

— titia (@titia_til) February 22, 2026

D - cresc.

　解法ツイートを参考にAC。

　Aの一つおきの配列が広義単調増加になることはコンテスト中に気付いていた。しかし、それだけだと重複があってダメ。

　じゃあ、重複をなくすためどこか固定・場合分けすればいいのでは？　と考えるのが重要。

　A[0]=0とした場合、A[1],A[3],...は全ての広義単調増加列を取りうる。

　それ以外の場合、A[奇数]の最後の値がMにならなくてはダメ。なぜなら、A[偶数]を全てｰ1したものが同じ配列を作るから。

　これで重複なく全て数えられているので、二項係数を使って計算できる。

　初項を固定・場合分けする発想がもてれば決して難しくないし、重複をなくすためにどこか固定してみようと考えるのは自然。

　今見ると難しくない気がする。

　また、二項係数の何か（積か和か）になりそうなことはコンテスト中から見当がついていたし、実験コードも書いていた。

　それで解けないのは、こういう二項係数を使う数え上げに苦手意識があるのかなぁ、と思ってしまう……。