DDCC2017 本戦 C - グラフいじり 解説

解説 Advent Calendar 2017

これは解説 Advent Calendar 2017 の 1日めの記事です。
adventar.org
全然埋まってないので助けてください。

（1日目から遅刻したので、これより先にnmさんの2日目の記事が公開されました）

解説（？）

りあんちゃん「で、今日やる問題ってどんな問題なの？」
たくぼくん「今日の問題はこれ。DDCC2017 本戦 の C 問題 だよ。」
りあんちゃん「それじゃあ問題を読んでみるね。有向グラフが与えられて、一つ以下の辺の長さを変えて、全てのサイクルの長さを 0 にできるかどうか…？ なんかもう何を言っているのか全然わかんないよ……」
たくぼくん「うーん、確かにそうだね。じゃあまずは『全てのサイクルの長さが 0 である』というのがどういう状態なのか、どうやれば判定ができるかを考えてみようか。」
りあんちゃん「全てのサイクルの長さが 0…。うーん、そもそもどういう状況なのか全然よくわからないよ……。」
たくぼくん「そうだね。じゃあ少し言い換えて、『どの頂点からどんな経路をたどってその頂点に戻ってきても、必ず距離が 0 になる』と言い換えてみようか。」
りあんちゃん「えっと……なるほど！ 確かにそう言い換えられるね！ でもそれってどういうことなんだろ……」
たくぼくん「一応そこまで言い換えられれば十分ではあるんだけど、じゃあもう少し言い換えようか。マイナスの距離、とかは少し考えづらいから、距離じゃなくて何か別のパラメータが上下していると考えてみようか。例えば……高さとか。」
りあんちゃん「つまり、各頂点に高さを設定して、プラスの辺はその分高い、マイナスの辺はその分低い……ってこと？」
たくぼくん「そう！ それじゃあそのとき、条件はどう言い表せる？」
りあんちゃん「えっと、距離が 0 ってことは高さの変位がないってことだから、それじゃあ一周してきても高さが変わらない、ってことだ！」
たくぼくん「そういうこと！ つまり全ての点の高さが矛盾なく定まることと同値なんだ。」
りあんちゃん「じゃあ適当な頂点の高さを適当に決めて、全ての頂点が矛盾なく決まればおっけーってことか！」
たくぼくん「今回は強連結であることが保証されているからそれで大丈夫。強連結でない場合も逆辺が簡単に張れるから同様にできるはずだよ。」
りあんちゃん「これでやっと判定はできたけど、長さを変えてこうなるかどうか、はどう判定すればいいの……こんなのできるの？」
たくぼくん「実は長さを変える場合、長さをいくつにすればいいのか、というのはさっきの高さの話を考えるとわかるよ。」
りあんちゃん「あ、そっか！ 2 点の高さがわかっていれば、その間の辺の距離は高さの差分である必要があるんだね。」
たくぼくん「つまり、その辺の本来の長さ、というのは、その辺を除いたグラフで各頂点の高さを求めてやればわかるんだ。」
りあんちゃん「なるほど〜！ 計算量的にも間に合いそうだし、これが答えだね！」
たくぼくん「残念ながらこれだと TLE するんだ。内部の高さを求めるところが O(N) じゃなくて O(M) かかるからね。」
りあんちゃん「え〜〜〜！ じゃあどうすればいいの？」
たくぼくん「ここまでくればあともう少しだよ。内部の高さを求めるところの計算量は落ちなさそうだし、消す辺を選ぶところをどうにかして O(N) にできないかな？」
りあんちゃん「え、何言ってるのそんなの無理でしょ。」
たくぼくん「そう言わずに……。消す辺は 1 本ずつじゃなくて、とある頂点が終点であるような辺全てを一気に消しても大丈夫なんだ。」
りあんちゃん「うーん…？？？ ちょっとわかんなくなってきた。どういうことなの？」
たくぼくん「なんかだんだん受け答えが雑になってきたなぁ…。つまりどういうことをするかというと、ある頂点からスタートして、その頂点に帰ってくる辺以外に対して高さを計算する。その時点ですでに矛盾があったら NG だけど、そうじゃない場合は最後にその頂点に帰ってくる辺全てを見て、それらが繋いでいる2点の高さとその辺の長さとの矛盾をチェックして、矛盾の数が 1 つ以下なら ok、ってことになるんだ。」
りあんちゃん「うーん。つまり、始点に戻ってくる辺っていうのは、高さを計算するのに関係ないから、互いに影響しないからまとめて矛盾をチェックできる、ってこと？」
たくぼくん「そういうこと！（台本棒読みだけど……）」
りあんちゃん「まぁなんとなくわかったような気がしなくもないけど、でもこんなのコンテスト中に思いつくの？」
たくぼくん「コンテスト中はこんなちゃんと理路整然と考えられてはいないけど、でも考察をしていればいずれ近いところまでは十分思いつけるとは思うよ。やっぱり『全てのサイクルの長さが 0 である』って条件をどう自分にとってわかりやすい言葉に言い換えられるかがポイントだったのかな。」
りあんちゃん「ふーん……。」
たくぼくん「（もう飽きちゃってる……）」

あとがたり

この問題は、予選を勝ち上がったメンバーで行われる本戦という舞台でけっこう虐殺が行われたのと、公式解説がなんやねん、と（個人的には）思ったので自分の解法を書きました。
まぁコード祭りもありましたしもう忘れている人が多そう…。
公式解説、なんやねんとは思いましたがあちらの方が汎用性が高そうで、こういう問題を安定して通すには多分公式解説の方法がさっとできると良いのだろうと思います。まぁ800点問題に取り組む人はこれくらい常識でいてほしい、ということなのでしょうか（つらいにゃあ）。

さて、上の方でも書きましたが解説アドベントカレンダーの埋まり具合があまりよろしくないです。
1日目から遅刻していることからも分かる通り、自分には残りの日を埋めるパワーはないので、ぜひみなさん助けてください！