Codeforces Global Round 21 参加記

ooooo---

A問題。$z$ が大きくなることはないので、高々 $1$ 回のみ操作を行えばよい。

B問題。$l=1,r=n$ として $2$ 回操作すれば必ず達成できるので $0,1,2$ のどれかが答え。

C問題。操作 $1$ の逆操作が操作 $2$ であることに注目すると、$a,b$ にできるだけ操作 $1$ を適用したときにそれらが一致するかを確かめればよい。愚直には持てないのでランレングス圧縮して持つ。

D問題。単調増加または単調減少な連続部分列の両端以外の要素は経由しなくてもよいので削除。このとき数列の増加減少はジグザグしているため、$1$ から $n$ に向かう際に戻らなくてよいことが示せる。ここで、毎回貪欲になるべく遠くまで進んでもよいことをエスパーした。これは区間min,maxのセグ木をそれぞれ持ってセグ木上の二分探索と組み合わせることでシュミレーションできる。

E問題。二項係数の和の和になる。$\displaystyle\sum_{k=0}^{n-1} {}_{m+k}\mathrm{C}_m= {}_{m+n}\mathrm{C}_{m+1}$ を用いれば高速に求められる。$a$ が $n+1$ 要素で与えられることになかなか気づけず悲しいことに。

F問題。なにこれ、入力形式に悩まされる。考察をしてみるも何の情報も得られそうにない。結局最後まで分からず。

G問題。見てません。

H問題。見てません。