Codeforces Round #712のupsolve中。

Div2 Cがeditorial見てもなかなか腑に落ちない所があって、twitterを見て解決した。

まず、開く数と閉じる数は同じ数で無ければいけないという当たり前のことに本番中気付けなかったのはあかんやろって思った。これに気付けると、$s_i=0$の時$a_i$と$b_i$がどっちかしら'(‘でもう片方が’)’になるのでとりあえず0が奇数だとダメそうだなということが分かる。全体も偶数で無ければならないので、1も偶数である必要があることがわかる。

$s_1=0$もしくは$s_n=0$だと死ぬのは流石に見えたが、それをなんか端っこ以外にも拡張していって全体を考えられるみたいな話かと思っていた。editorialの解だと、端っこだけそれで保証したあとは中は別のやり方をやっていく感じだった。端でのチェック事項を無理に全体に適用してもドツボにはまるだけかもしれない。構築系問題では気を付けた方が良い気がする。

$s_i=1$の箇所ではab共に(((…((()))…)))にして、$s_i=0$の箇所ではaとbで()()()()()と)()()()()(をそれぞれすると勝つ。れたすさんの解説ツイートがめちゃめちゃ簡潔で分かりやすかった。ここまで分けて考えるとなぜそれで良いのか非常に分かりやすい。'(‘を1の上昇・’)’を1の下降で表すグラフで考えると、1の箇所は自明で、0の箇所は1個以上の下げ幅が無いので端っこでさえなければ問題ない。面倒な干渉が起きるやつではないので混ぜれば解になる。天才。

本番中は「初めにaを(((…))))の形で準備して、sの情報を元にaを加工したbを作る」みたいな思考回路にハマってしまっていた。というより、完全にaの世界とbの世界で分ける頭になってて、sの方を$s_i=0$な部分と$s_i=1$な部分で分けて考えるのは思いつかなかった。タテではなくヨコでというか、それぞれの数列ごとではなく1つの数列の中で部分集合ごとに分けて考える思考回路を身に付けたい。

Div2 Eは「全部回る必要あるから最短経路系のアルゴは使えないな」と思っていたので解説でダイクストラの名前が出てて吹いた。ええ…

$max(c_i, a_j-a_i)=max(0,a_j-a_i-c_i)$という式変形をしていた。これは自分もやった。

ぐるっと回る経路を求めたいので特にどこをスタートとして考えても問題ないらしい。確かにコストは移動元と移動先だけで決まっていて、何回目の移動であるかにはよらないんだから、ゴールからスタートに戻るところさえちゃんと加えればどこがスタートでどこがゴールでも変わらない。なーるほど。単純だけど気付かなかった。巡回路を求める問題ならとりあえずこれを疑ってみていいかもしれん。

editorialでは$a_i$でソートしてた。ここまでは自分もやってる。しかし昇順でソートして1番目からn番目までの道のりを求めてたので、「え、それだとコストかかるじゃん」と思ったのだが、こっからがすごかった。「どうせn番目まで行けばノーコストで残り全部に行けるので、どうしてもかかるコストの部分を計算する」というそういう話だった。天才過ぎる…なるほど。

巡回するのでどうせどっかしらの時点で最低の$a_i$から最高の$a_i$まで移動する必要はある。だから「え、それだとコストかかるじゃん」はまったく的外れな考えだったわけだ。恥ずかしい。

そっから先はまあ、そうだろうなみたいな感じだった。後ろ方向に0パス張ってー、$a_i+c_i$以下の最大$a_j$に0パス張ってー、どうしてもコストがかかる最小$a_j$にパス張ってー、$a_1 \rightarrow a_n$のコスト計って終わり。これ自分で思いつけてたらすーごい気持ちよかっただろうなー。悔しい。

これ以上詰め込む頭の余力はないのでDiv2 Fはまた今度。

---

このはカレンダーめくった。3月バージョンの絵好きなので躊躇してたけど観念した。新学期だし。

めっちゃ太ももに目が行く絵だった。えっちなのはいけないと思います。えー、露骨にあざといのは個人的にはあんまり望んでない。このはちゃんはきゃるーんてしてるときよりもフンガーってなってるときが一番かわいいと思ってるから…

あーでもずっと眺めてたらこれもかわいいなって思えてきた。何やってもかわいいや。