2完。コンテスト時間が短すぎる。前菜食べたら終わってる。まあシンプルに頭が悪い。ABにこのくらい時間かかるのは仕方ないと思うけどCはなあ。Aもダメか。しかしいくら頭が悪いからって、Dを考えることもなく終わるって酷すぎる仕打ち。悲しい。
（追記）コンテスト終盤、考えようとしても集中できなかったな。もう新規ACが不可能に近い時間になると、（ACできない焦りとは別に）むしろホッとしていた。考えなくて済むので。夜中で大声出せなくてつらい。なんでこんなこともできないんだ。
A - Spoon Taking Problem
人P_1が行動した時点で「全員がスプーンを取るなら、全員についてどちら側を取るかが決まっている」と気づくのに時間がかかった。そこから、全員が同じ側のを取ると気づくのにも時間がかかった。あとは、初手を左と右に固定してそれぞれを解く。N個のスプーンそれぞれが残っているかを管理しておく。両方残っているとき違う側に置くしかないなら0倍に、そうでないときは片方だけ残っていて（同じ側を取っているので常に1個は残っている）'?'であればどっちでもいいので2倍にする。最初の人の行動は場合分けしなくていい（書き上がってからわかった）。
左右を0,1にするか-1,1にするかでかなり迷った（実装を2回書き換えた）。左右のスプーンの位置を、現在の人の位置を基準として-1,+1としていたが、正しくは0,+1だった（mod Nとるので差が1なら何でもいい）。
B - Parenthesis Arrangement
個数が合っていて、累積和が負にならなければよい。できるだけ外側から置き換えれば、そこより内側全部の累積和が+2されるので得。「'('が足りない場合、できるだけ左の')'を置換して損しないように思う」ところまで行ってから、')'が足りないとき右の'('からやっていいと気づくまでにもタイムラグがある。入れ替え操作は、置き換え操作と組み合わせても意味がなさそう（同じ文字を入れ替えるのは意味がなくて、どちらかを置き換えた場合そうなる）。ということで、まず個数が合わない分を外側から貪欲に置き換え、次に累積和の最小値が負である間（外側からやれば1回の入れ替え操作で常に+2されるはず）置き換え2回か入れ替え1回の安いほう（個数を合わせたあとで奇数回の置き換え操作が必要になることはなさそう）で操作することを外側から繰り返す。
昨日のABCのFでバグらせた経験から、assertみたいなの（if (ないはずの状態) throw;）をたくさん置いた。これがたくさん引っかかって大変だった。文字を-1,1に置き換える操作を2回していて破滅していた（都度置き換えるのではなく最初にやっておこうとコピペしたときに消し忘れた）。操作1回で累積和が1しか変化しないように書いていた（実際は2）。累積和の最小値は偶数と限らないことに気づいていなかった。
C - Jumping Through Intervals
難しいのでとりあえず辞書順の条件は外して考える。横に直進できるだけして、できなくなったら上下に動く。スタートを決めるのが難しいので、ゴールからやってみる（今考えると辞書順の条件がないなら対称なんだよな）。直進できるだけして上に行くか下に行くかで場合分け。辞書順も考慮して、一番下から始めてあとから必要なら引っ張り上げる感じ。上に行くのは簡単で、しかし実装が終わったとき簡単な側だったことに絶望した。下に行くのは、仮に一番下へ行くとしてmaxをとって下に張り付きながら（ゴール方向へ）戻る。しかし、上に行ってコストが増加しないケースとそうでないケースがあると気づき、前回が上に行ったか下に行ったかも記録して場合分けが必要。また、最後まで直進できたときの調整も難しい。いつの間にか非常に複雑な実装をしていたことに気づかなかった。気づいたときには残り時間がない。
（追記）自力で未証明ACした。0を初期値とし、LRでstd::clampしながら暫定解を作る。これにより真の解の末尾がわかることを期待している。今度はその末尾から逆向きに同じことをやる。これにより真の解の先頭がわかることを期待している。あとは、先頭からLRではなくLと暫定解（末尾が合っていることが重要）でclampしていき（値を大きくするのをできるだけ後回しにしている）、これが真の解になっていることを期待する。
D - LIS on Tree 2
（追記）1時間くらいでAC。作れる最小と最大は簡単にわかる。その間は全部できそう。部分木で稼げるぶんを引けるだけ引いて部分木の問題に帰着させる方針を考えていたが、ちょっと違いそう。LISについての理解の浅さが気になるが、とりあえず根以外の各頂点のオンオフを決めることに。部分木のサイズを求めておき、その頂点をオンにすることでそのサイズぶんだけ稼げるとする。サイズが大きい順にオンオフを決めれば確実だが、DFSの順に決めても大丈夫そうだ（部分木のサイズのぶんだけ子孫がいるのでわりと何でも作れる）。KがN未満のときはNo、全部引いても残っていたらNo。根の寄与Nは先に引いておいてDFSの中では処理しない（サンプルが合わなかった）。あとは、オンオフを具体的な順序に変える。深さdを持ち、根を基準の0としてオンならd、オフなら-dとして、これでLISの長さは根からのパス上のオンの個数以上になり、またオンの個数より大きくはならないだろう。これで順序が決まった。これを順列に変換するのが難しいと思っていたが、少し考えると単にこの順序を保てばいいだけなので、インデックス付きでソートしてソートされた順に1から割り当てるだけでよかった。順序が重要なのは根からのパス上でだけなので兄弟とかは気にしなくていい。
