AtCoder Regular Contest 175

　二完でまた青に落ちてしまった。

コンテストへのリンク

コンテスト後のツイート

AtCoder Regular Contest 175 C詰め切れず。
A 全員左のを取るか全員右のを取るしかない。自分の順番のときに選択肢がない人が何人いるか調べる。
B 変更する貪欲か、同じ個数まで変更した上で、入れ替える貪欲か。入れ替えるときは、累積和が負になったところで一番の右の"("と入れ替える。

— titia (@titia_til) March 24, 2024

C - Jumping Through Intervals

　多少解法ツイートを参考したけど、概ね自力でAC。コンテスト後、一時間以上かかってしまった。難しい。

　LR[i]とLR[i+1]の位置関係を考える。x, y=LR[i],  z, w=LR[i+1]とし、y<wのとき、LR[i+1][1]=max(y, z)として良い。w>yのとき、LR[i][1]=max(w, x)として良い。まずこのように更新しておく。

　この更新で値が決まる箇所がある。i, j(i<j)の値が決まり、その間が決まっていなかったとする。このとき、ANS[i]<ANS[j]ならi+1の値を、ANS[j]<ANS[i]ならj-1の値をLRの値との大小を比較することで決めることができる。

　区間の片方しか決まっていない場合も似たようにやる。一つの値も決まらない場合はずっとある値を取り続けられるということなので、そのような最小値を探す。

D - LIS on Tree 2

　解説AC。

　難しかった。

　f(P)の最大値は分かるが、そこまでの値全てを取るのか？　またどうやって構成すれば良いかが難しい。根から構成するのか、子から構成するのか、（Pについて）大きい数字から考えるのか、小さい数字から考えるのか、があり悩ましい。

　結局、根から考え、その頂点により、「自分を含む部分木の大きさ」の分だけ増やせる、と考えるのが正しかった。ただ、この見方もなかなか理解できなかった。

　コンテスト中にこの問題を解けていた気はあまりしないので、Cに行ったのは正しかったか。