DDCC2017 本戦 C グラフいじり(+参加後記)
問題
ddcc2017-final.contest.atcoder.jp
解法
コンテスト中の自分の思考を再現してみたので、無駄な(最終的な解法を導くのに有効でない)考察も含まれている可能性がある。考察の正当性の証明はここでは省略する。
問題文には1つの辺の長さのみ変更できると書いてあるので、まずは長さを変更する辺を固定して考える。
例えば下のグラフの場合で有向辺1→2を選んだ場合、長さを2から-1にすれば全てのサイクルの長さを0にできる(出力はYesになる)。
このケースでよく観察すると、
- 2→1の長さは1であり、つまり辺1→2の長さの符号を逆にしたものである
- 辺1→2がないものとみなした場合、残った辺で作られるサイクルは全て長さが0である
ことがわかる。
ここから膨らませると、全てのサイクルの長さを0にするには、2→1に至るあらゆる経路において、長さは1でなくてはならないこともわかる。なぜなら2→1への経路は一般には1つとか限らず、たくさんある場合もあり、それらが1→2の長さと足して常に0になるはずだからである。
さらに、与えられるグラフは強連結なので、辺1→2を無視した場合でも、点2を始点とすればそれ以外の全ての辺を訪れることができることがわかる。 この考察から、辺1→2を無視した場合にサイクルでなくなるものとサイクルが維持されるものを区別する必要はなく、点2から全ての辺を訪れるようにDFSを行い、点2から全ての点への長さを計算して、2→1の長さの符号を入れ替えたものが1→2の長さとなることがわかる。
注意として、全ての点への長さをDFSで計算する際に、点2から全ての点への長さは一意でなければいけない(*)。下のような例は2→1の長さが一意に定まらないのでだめ。
これを全ての辺に対してチェックし、1つでも(*)が満たされている辺があれば答えはYesとなる。ただし、この解法では となり、TLEしてしまう。
ここで、TLE解だと各点を始点とするDFSを何回(点が個に対して
回)も行なっていることに注目する。上の図だと始点2でDFSを行うのは辺1→2を選ぶ以外に辺4→2を選ぶ場合がある。
何とかして無駄を省くことができないか考えると、例えば始点2のDFSの場合、辺1→2と辺4→2両方を無視しても、その他全ての辺を訪れることが可能であることに気づく。TLE解法と同じようにDFSを行うと、2→1の長さと2→4の長さがわかる。それぞれにおいて無視していた辺1→2との和、辺4→2との和をとり、0であるかどうかチェックする。ここでは高々1つまでの点で和が0以外であれば、Yesとなる(0でない場合はそれに対応する辺の長さを変えれば良く、1箇所までしか変えられない) 。
この解法だと、DFSをする回数は高々頂点の数になるので、となる。
ソースコード
参加後記
学生でもないのに新卒採用の一貫として開催されるコンテストの本戦に参加する権利が与えられてしまい、DISCOさんの懐の厚さを感じました。
コンテストの内容としては開始16分でA, Bを解いた後、終了8分前にCを通し、何とか3完することができました。7, 800点台の問題はAtCoderのレーティングが導入されてからずっと鬼門に感じていて、レーティングが伸び悩む原因になっていますね...。ある程度の精進で何とかなるかもしれない希望もありつつ、実際には精進できていないという現実があります。
将棋AIの特別対談のセッションは将棋AIを自分が手がけることはないだろうな...と思いながら聞いていたのですが、興味深く聞かせていただきました。将棋AIを育てていくのにも、例えばインフラ整えたりするところでサーバ貸し出しの交渉など社会性が必要となることもあったのこと。社会性を身につけなければ。
オフィス見学は技術の紹介より福利厚生の紹介の方が多く、(競技プログラマーがどういう生き物か)わかってらっしゃるという印象でした。個人的にはウェーハ加工で実際に動作させるソースコードのサンプルが見たかったです。
懇親会は普段Twitterや順位表でしか見ない方とお話できたので、満足しています(近場の人とはまた会いたい)。一度会ったことがあるのに挨拶できなかった方すみませんでした。もっと積極的に話に入るべきでした。
そろそろ純粋な競プロ以外のアウトプットもしていきたいところではあります(最近競プロのアウトプットでさえ危ういですが)。
