最近ABCの復習も（特にやりたくなかったので）してなくて、競プロが楽しいと思うことがあんまりなかった。が、久々のratedコンテストで開始前から心拍数がかなり上がってくれて、問題も面白く、ABCDの4問に30分ずつくらい使ってみんな楽しめた。
結果は1完で半年ぶりの水パフォ。今は嫌な気持ちになっていない（明日が楽しみですね）し、悔しさもない（BCDで惜しいところまで行ってないからそうなるわけで、それが残念ではある）。まあ最近かなり（心の）調子が悪くて身の丈に合わないレーティングだと思っていたからな。競プロの楽しさというか、このところ何に対してもとても低い楽しさしか感じてなかったので、そこを突き破ってくれたARCに感謝。今回は順位表を（結果的に）見なかった（珍しいけど、まあAしか解けてなくて面白そうな問題がいくつも残ってると見るタイミングがないんだよな）。
（追記）全体として、解法が降りてくるのを待つしかできなかった。先週のABCもそうだった気がする。待っているときは、典型に頼るくらいしかすることがなく、そうなると余計に、発想が自由に伸びなくなる。やっぱ競プロに浸かっているときは高いパフォーマンスが出せるのかな。それで実力が伸びるわけではないにせよ浸かっている間、一時的には。
A - Copy and Paste Graph
NK*NKの図を考えるが、頂点数はNKなんだよな。抽象的な思考が要求され、時間がかかる。mod Nで考えてs,tが同じかどうかで場合分けする。違うなら、普通にN頂点のグラフで求めた最短経路（ワーシャルフロイドで前計算）が使える（経路長は1以上なのでそのどこかでしれっと移動）。同じとき、これはやや悩んだが、最初の一歩を全探索すればいい（違う場合に帰着）。
そういえばK=1のケースを考えてなかったと思ったが、mod Nで違うときは考えてなくていいし、s=tのことはないので、一応考えてはあったか。N頂点のグラフでの最短より良い経路が存在するかは考えてなかった。まあN頂点のグラフでの動きしかできないので、いいか。「自己辺」がないとは限らないのが、最初不思議に思って、あとから効いてくるのがいい味。
B - GCD Subtraction
そういえば考えたことなかったなーってなる。こういうの好き。まず愚直を書いてみる。操作していくとgcdは広義単調増加になる。というかgcdで割ってしまってもよさそう。どこで揃うかをgcdが同じ部分を飛ばしたい。変化するときは2倍以上大きくなるので、ここで10^6回の演算を行うのはギリセーフ。10^6（sqrt(max(A, B))以上の数）までの素数を列挙しておいてその素数の倍数に揃うことがあるか全部試すのは余裕で間に合う。それかなあと思って実装してみるが、実装しても全く証明を思いつかない。そこでA,Bが100以下を全部試してみると普通に反例があるし、片方が極端に小さく愚直が間に合うものを除いてもA=43, B=90などがある。いやむずい。
（追記）差の約数かー。考えてる方向が全然違ってた。簡単そうに見えてこれは難しい。実装も難しかった。差が0や1のときがだいぶ特殊でそこも難しい。差が0なら1回だし、差が1なら何回1引こうが互いに素なまま、結論自体は簡単だが、思ったよりもまとめて扱えない（感覚でわからない）。
C - Permutation Addition
不可能になる自明な条件がありそうだけどすぐに思いつかない。頑張って考えると、等しくなったとき全体の和はNの倍数になるし操作での和の変化はNの倍数だったりN/2の倍数だったりするのでそこから必要条件が出る。十分条件だったりしないかなーと貪欲（小さい数から順に大きい数を足していく）を書いて実験してみると、1 1 2 3 3というケースが貪欲ではできないっぽい（ほえー）。上手くやればできるのか、他にも条件があるのか、わからない。
コンピュータが吐いた反例を見たとき、なんかスワップっぽい雰囲気は感じてたので、そこを今考えると、1 2 3 4 5を足すところ1 2 3 5 4を足せば1を移動させたことになる。これは全部可能だ。ていうか勘違いしてたけど1 2 3 4 5と5 4 3 2 1を足せば元に戻るじゃん（なんか知らんけどN回くらいかかると思ってた）。回数も50*50くらいで済みそう。実装する。実装を考えるのが難しかったけど、最終的な実装自体は多少長いけど簡単に書けるものとなった。2操作ずつ処理する。minmax_elementして小さいところに2とN、大きいところに1とN-1を割り当てる。他は昇順降順で埋めて変化しないようにする。操作回数は余裕がある。
D - LIS 2
簡単そうに見えるが。これはchokudai speedrunでググる。LISの自分の提出を見る。狭義単調増加で追加する数列は1刻みなので、使うなら全部Lから（またはRまで）使うとしてよさそう。普通のとBIT使うのとどっちも使えそうだなあ。どっちも考えて（そこそこ時間かかる）、結局ダメだった。LとRどっちでソートするかも全然見えない。1次元に並ばないのがつらい。51-100（長さ50）と21-30（長さ10）、どっちの続きをやるのがいいかはLによる。Lでソートするのかなあという気もするけど、Lが大きくなるにつれ上限を解放していく感じの、どうやるの（そもそもできるの）。
（追記）解説を見て難しすぎると思ったけど、mapを使うほうはイメージできたのでそちらで書いた。自分にとっては実装がめちゃくちゃ難しい。区間の左端をキーとしてあと右端だけ持てばよかった（LISの長さも持つ必要があると思ってた）。lower_boundかupper_boundか決めるのに1時間かかった。upper_boundを使い、候補を高々2個に絞る。L以上の最小の数を見つけて、そこから上書きしていく。Lが区間の最初にならないときは、Lが小さかったことにする（結果は変わらず共通した処理になる）。完全に覆ったものは消して、半端は切り離す。最後にLからRまでの区間を追加。答えは区間の長さの合計。挿入回数がO(N)なので消す計算量も大丈夫。この実装は思いついてもコンテスト中には無理だったな。
