はじめに
競プロの問題解いてて、解けなかった問題は何故解けなかったのか、何故その発想が出なかったのかを記していく自分用メモです。atcoderの400、500点くらいの問題なら、解けないなりにもボチボチ近いところまでは行けてるっていうパターンが多いので（それ以上の問題は今のところ大体歯が立たない）、あと一歩何が足りなかったのかを探って書いていきます。
ARC074-D 3N Numbers
とりあえず、境界を決めて左側の数列から大きい順にN個、右側の小さい順にN個取ればよく、後はスコアが最大になる境界位置を全探索すればよい。ただし、これだとO(N^2logN)だからTLEになる。じゃあ、どうする？優先度付きキューか？っていうところまでは発想が至った。
ということで、左側数列用優先度付きキューと右側数列用優先度付きキューを用意して、境界位置を左から順にずらし、両優先度付きキューを更新していくってことを行おうとしたところ、右側数列用優先度付きキューから指定要素を取り除く操作が出てきて、その操作には1回O(N)かかるぞ、どうすればいいんだーとなる。
境界位置探索について1回で済まそうと、左側と右側の更新を同時（同じループ内）で行おうと考えたのが間違い。
まず境界位置を左からずらして、左側数列優先度付きキューを更新していく。それが終わった後、今度は境界位置を右からずらして、右側数列の優先度付きキューを更新していく。こうすれば優先度付きキューの操作は、先頭要素取り出しと要素追加だけになるので1回の操作はO(logN)で可能。最後にどの境界位置が最適かを見ればよい。
ARC083-D Restoring Road Network
与えられている最短距離表を各頂点間を結ぶ隣接行列だとみなしてワーシャル・フロイドで解いた後、矛盾がないか探る（矛盾があれば、ワーシャルフロイドで求めた最短距離と最短距離表の値が異なる部分が出てくる）。矛盾がなければ、頂点i,j間を直接結ぶ辺が必要かを考えればよい。つまり、i,j間を直接結ばずともどこかを経由して最短距離となる経路があるかを探す。
っていうところまでは出てきたけど、ここで躓く。i, j間の最短経路で直接結ぶ以外のパスがあるかを求める方法がわからなかった（i, jを直接結ぶパスのみを削除したグラフG'を用意して、これに対してダイクストラ法でi, j間の最短距離を求め、元のグラフで求めた最短距離と変わらないかってことをやろうとしたけどTLE）。
これを求めるには、頂点kを経由して、最短距離が等しくなる経路が存在するかを調べればよい。つまり、i-k間の最短距離+k-j間の最短距離が最短距離表にあるAijと等しくなるkが存在するかみればよい。
ARC076-D Built?
x座標、y座標それぞれでソートして、隣り合う街同士にのみ道を作ることを考えればOK。x座標、y座標ごった煮にして、コストの小さい道から順に追加していけばいいってところまでは考えた。ところが、やってみると各頂点をが全て連結されているのか効率よく判断する方法がわからず、言葉だけは知っていたUnion-Findを使うのかな？って思ったところで、なんとなく敷居が高い気がして断念。
というか、ここまで来れば、まんまクラスカル法。もし、クラスカル法知らなくても、ソートして隣り合う街同士のみ考えればいいってことを鑑みると、考慮する辺数が2Vだけなので、O(VlogV)で解ける最小全域木問題だって事気付けばプリム法で解いても良かった（これ解いた時、プリム法は知ってた）。いずれにしても、問題そのものが最小全域木の典型問題にもかかわらず、ソートとか隣り合う街同士のみ考慮とか色々考えていくうちに、最小全域木問題を解くアルゴリズム使うという発想がすっぽり頭から抜けていたのが反省点。
おわりに
もう少しレベルを上げたいので、時々こういう反省ポエムも書いていきます。
