naoya_t@hatenablog

いわゆるチラシノウラであります

SRM732

日本時間10am〜の回。Div I参加登録者153名。
TopCoderの時代は終わったなあと思うんだけど経験値を稼ぎに出てみる

Easy (250) TileFlippingGame

二部グラフ作って
最長距離で…?
いやその半分?
どういう取り方が最適なのかイメージできなくて距離路線を諦めて

Greedyに(一番沢山繋がってるノードを)flipしていく作戦とか…
いやそれだと(サンプルケースの説明にあるように)サンプル4が通らない

ああでもないこうでもない、と実装ゲーに陥って
Atomで久々にC++を書いて、エディタの挙動(インデントとか括弧対応とか自動文法チェックとか)が手になじまず苦戦。
結局サンプルケースを通せるコードすら書けずに沈没。

〜〜

すべてのノードについて、そのノードが中心だとしたら全ノードを同じ色にするまでに何flipかかるか(+最後何色になるか)を調べて、それが最小になるノード(とflip数と色)を得る。例えば最短手が5手で最後白になるとしたら、白にするための最短手は5、黒にするための最短手は6になる。
いくつかの島に別れていたりするのでunion-findしてグループごとに求める。
ゴールを白にする場合と黒にする場合でそれぞれ集計して、少ないほうが答え。(AC)

// 同じノードをずっとflipし続けることになるのだけれど、それが最適解なはずがない(例外がありうる)と考えて脇道に逸れたのが敗因。

Medium (500)

開いてない
通してたの2人だけ(あとは撃墜なりSystem Testなりで落ちてた)* Hard (800)

Hard (800)

開いてない
通してたの2人だけ(あとは撃墜なりSystem Testなりで落ちてた)

〜〜

x-- 0pt; 1478 -> 1467(レートと経験値の等価交換)