NIKKEI Programming Contest 2019 予選

A - Subscribers

瞬殺ではあるけど、Aなのに考察が入る。難しいので時間がかかる。

B - Touitsu

編集距離を思わせてめちゃくちゃ難しそう。違ってるところだけ直せばいいからそこをなんとか数えられないかと考えて、各位置の文字を独立に考えられることに気づく。あとはやるだけ。やはり時間がかかる。

C - Different Strokes

幸福になりたいんじゃなくて、相手と比べて幸福になりたい。ややこしい。だから差が重要でA-Bの値だけが重要なのでは?しかし、サンプル1が早速反例だ。確信してた仮説は間違いでした。地道にサイズ1から考えていく。N=1は自明。N=2は、a bとc dの料理があるとして、a-dとc-bを比較して選ぶ。自分の幸せと相手の不幸が同じことなので、足すか(ずっと前こんな感じの問題が出たとき、何かでソートするだけって聞いた)。なんと、a-d>c-bを変形するとa+b>c+dになる!証明は全くしていないが、これは正しいとしか思えないし、間違っていてもペナルティの5分より証明を考える時間のがずっと長い。ということで提出。WAだったが、小さい順にしていたので不等号を逆にして提出、AC。なんだこのムーブは。

D - Restore the Tree

B_iに現れない唯一の頂点が根。とりあえず根からDFSしたい。深さを持って親候補を更新していくイメージ。しかし反例がありそう。同じ頂点に何回も訪れると経路が多くなってTLEするだろうし、そんな中でどうやればいいのか。あれ、単にトポロジカルソートすればよくない?というわけで、根からDFSしてトポロジカルソートする。最近やったから思考停止Wikipedia見て実装をしたけど、どこでやったのか全く思い出せない。名前の付いた新しいものを書いたときは記録しておいたほうがいいな。さて、あとは最も近い親を親とするだけ。トポロジカルソートの結果を上手く参照する必要がありコーディングのための思考が複雑だった。REとなったが、まあこれは辺のループをiで回してたのに頂点のループもiで回したのが敗因ですね。とはいえ、普段はmain関数で辺のループは入力のみ。同じiで通常は問題なかったのだ。今回は辺の数が変だったし、ここを(常に)バグらせない書き方は難しい問題だなあ(用心しすぎると普段のコストが無駄に上がる)。

終わってみれば確かに500点で簡単だった。けっこう時間をかけてしまった。

E - Weights on Vertices and Edges

辺が減ると条件を満たしにくくなる。最終手段として全削除で条件を満たす。O(N)で小さい問題に帰着できたら?N段必要かもしれない。橋について調べていたが、どうも違う気がしてくる。連結成分の情報と頂点の重みの合計を更新しながら辺を除いていけないか。無理。二分探索を思いつくが、連結成分毎に状況は違ってくる。辺を付け足す?付け足せるなら付け足せるけど、付け足せなくてもまとめてなら付け足せる場合がある。この問題のそういう断絶にずっと悩んでたんだ。ただ、二分探索でギリギリの図を作りそこから貪欲で?色々考えたがどうも。足すのはダメだし引くのも時間かかる。可能な重み合計最大の連結成分(の一つ)を考える。その合計重みと比べて、他の連結成分に含まれる辺の重みは同じか小さい。

こういう理不尽に難しいEは久しぶりな気が。全体として、1年前のAtCoderを思わせる構成だった。解きやすい(なじみがある)(解けるとは言っていない)。

(追記)上にある当時の文章を読んだりして色々考えたが、結局、最初の方法に戻ってきた。条件を満たさない辺は消す必要がある(どんな辺の消し方をしてもその連結成分の頂点の重みの総和が増えることはない)ので、各連結成分が条件を満たすようになるまで重みが大きい順に削除していく(重みが同じのときの順番はどうやってもいい)。計算量を考えなければ答えが求まるので、これをどうにか高速化できないか考える。逆から考えればUnionFindが使える。mergeする、あるいはmergeされないけど辺を追加したという様子を、木で表したものを考える(辺を追加したら新しい親ができて最終的に森が木になる(各頂点はその辺を追加した時点でのその辺を含む連結成分を表す感じ))。削除する辺は常に連結成分の中で重みが最大のものなので、全体で見れば正しくないかもしれない順番でも、さっきの木で見れば正しい順番(根に近い順に削除していく)になっている。木を根からDFSしていって、条件を満たす連結成分になっている場所へは行かないようにすると、訪れた頂点(辺を1個削除することに対応)の個数が答えじゃないかな。実際それらの辺を削除すれば条件を満たすし、削除しないものが1個でもあったらその祖先にあたる辺の削除を1個以上やめないかぎり条件を満たさないし祖先はどれも条件を満たさない連結成分になっている。実装は、全部UnionFindの内部でやるのが楽だった。mergeするときに頂点の重みの合計と削除する辺の個数も合体させる(条件を満たしたら削除する辺の個数は0にする)。結果的にmergeしなくても追加した辺が条件を満たさないなら削除する辺の個数はインクリメントする。辺の重みは昇順にやっているので、連結成分内の全ての辺が条件を満たすかの判定をするには追加した辺だけを見ればいい。逆からやるだけっていう単純な解法なのにめちゃくちゃ難しくてすごいと思った。違う連結成分を見ると操作の順番が正しいとはかぎらないから見えづらいのかな。