DDCC2017 参加記

DDCC2017に参加させていただきました。

運営して下さった皆様ありがとうございました。

AB2完の51位でした。C解きたかったです。

A問題

直径200と300の円から、一辺の長さがKの正方形はそれぞれ何枚切り出せるか？

考察

制約が小さいので、全ての正方形の4点についてそれぞれ円に内包されているかを確認して全探索。問題文の図のそのまま。去年の本戦問題と似ていたらしいですが解いていなかったのでわからず。

こういう問題はパッと見つらそうですが、やはりじっくり考えてみるとそれなりに書きやすい解法が存在するのでAtCoderだなあと思いました。

B問題

gcd(X, a_i) = gcd(Y, a_i) の時X, Yは似ている。a_i (1 <= i <= n)とZが与えられた時、全ての i について、gcd(Z, a_i) = gcd(K, a_i) を満たす最小のKを求めよ。

考察

gcdって書いてあるしとりあえず全部に対してgcdをしてみると答えが1になった。

それはそうだな〜と思いサンプル1のケースの説明を見ていると、gcd(Z, a_i)の答えは当然 Zとa_iの最大公約数。

b_i = gcd(Z, a_i) とすると gcd(b_i, a_i) = gcd(Z, a_i) が成立。

すなわち K は全てのb_i の代わりになりうるもの、まあすなわちLCMを取ればいいって感じになるので、LCM, GCDしてAC。Aに時間をかけてしまったので、Bの速さの割に、、、という感じになってしまいました。

C問題

強連結な重み付き有向グラフが与えられる。グラフ上のただ1つの辺の重みを変化させる事が出来る時、グラフに含まれる全てのサイクルの重み（サイクルを形成する辺の重みの総和）を0に出来るだろうか。

考察（嘘）

問題の名前がグラフいじりだったので、グラフをいじってみる。

辺をどうにかするので、辺目線でDFSをしたいと思い、グラフを変形して辺のつながりを表すようにする。

そうしたら後はグラフ上の全てのサイクルを列挙できれば良い。当然不可能。

全頂点について、開始頂点から深さ優先探索をして開始頂点に返ってきたらそのパスを文字列にしてハッシュ値を求めてmapで管理してなんとかしようとしましたが当然WA & TLE & RE 辺数が 90000 くらいあったのでそれはそうですね。

解法（未検証）

とあるプロから聞いた解法です。僕がブログに載っけて良いのかはわかりませんね。

まず適当に重みが０でない閉路を見つけます。この閉路の辺数は高々 n です。

全ての閉路の重みを０にするのが目標なので、その閉路の重みも当然、どれか1つの辺の重みを変更して０にしなければなりません。ここで、その閉路の重みが分かっているので、変更する辺の重みは一意に定まります。そのように重みを変えた時、グラフに含まれる全ての閉路の重みは0であるかを調べます。

全ての閉路の重みが0になっているかは、とある頂点を開始頂点として、開始頂点からdfsして、開始頂点に帰ってくれば閉路なので、その時のパスの重みの総和を調べればよく、これを全ての頂点を開始頂点にして行うことで調べられます。

dfs が O(n), これを全頂点始点でやるので n がかかり、これを最大 n 辺について検証するので、O(n^3) となり時間内に解けます。すごいなあ。

ビュッフェ美味しかったです。対談では、将棋があまり分からない僕でも楽しめるような雰囲気のものだったので楽しく聞けました。競プロの問題をコンピュータに解かせる話はとても面白いような恐ろしいような複雑な気持ちになりました。

Discoの綺麗な社内を見学してまたビュッフェを食べ、記念撮影して終了。

多くの人々と交流したので、その雑記はきっと後に書きます。

ぷぇ