CodeTON Round 6 (Div. 1 + Div. 2, Rated, Prizes!)

　遅解き四完。前半で苦労したのが響きレート-115。Eを解けなかったのはまあまあ仕方ないが……。最近、序盤のミスが目立つなぁ。

コンテストへのリンク

コンテスト後のツイート

CodeTON Round 6 (Div. 1 + Div. 2, Rated, Prizes!) Dまで四完。Eが分からないし、すんなり解けた問題がCしかなくてひどい。
A 0,1,...,k-1まで並べて、その後、x=kならx-1を違うならxを並べる。最初、MEXをxorと誤読して時間を浪費。

— titia (@titia_til) September 18, 2023

E. Another MEX Problem

　解法ツイートを見てAC。

　DPを考えたのだが、区間DPを考えたのが失敗。左から順に作っていけば良かった。その上で、考えるべき遷移の個数が抑えられることが難しい。

　DP。左から作っていったとき最速でその数字を作れるかを判定していけば良い。

　遷移に使う[l, r]は、[l, r]が最も短いものを選べば良い。この個数はO(n)個に抑えられる。