Hatena::Grouptopcoder

yehara のTopCoder日記

 | 

2009-05-28

SRM441 Div1

15:18 | SRM441 Div1 - yehara のTopCoder日記 を含むブックマーク はてなブックマーク - SRM441 Div1 - yehara のTopCoder日記

なんかトラブルがあったらしく、つながりにくくて困った。開始が15分遅れていたのだけど、それでもようやくログインできたときにはすでに始まっていた。1〜2 分のロス。

Level 1

与えられた順列から、ポインタを順番にたどってすべての要素を通過する順列に変換するために、何カ所数字を変更すればよいかという問題。

不完全な状態だと、あるところからポインタをたどりはじめても部分集合だけでループが完結してしまう。このようなループを形成するグループが何個あるかが解に関係ありそう。1つしかなければすでに完全な状態なの解は0だ。グループが2つなら1組の数字を入れ替えてグループ同士を行き来できるようにすれば良いので解は2になる。以降、グループ数だけ数字を入れ替えるとうまくいくはず。

というわけでこの方針で実装。グループ数が1のときだけ特別というところに多少の違和感を感じつつ提出したが、正解だった。

Level 2

与えられたグラフを全域木にするためには、枝の置換操作を何回行えばよいかを求める問題。

良い方針が思いつかず、愚直な幅優先探索を書いて死亡。一応動くつもりのものを書いたがテストケースが1つ通らなかった。おそらくちゃんと動いていたとしても最悪ケースでは TLE か OutOfMemory だっただろうが・・・。

ほかの人の解をみて Level 1 との共通性に気づいて驚愕した。これも部分木が何個あるかで簡単に解が求まるのだ。

解が存在することの必要(かつ十分)条件として、

  • 枝の数 >= 節の数-1 であること
  • 枝が1つも接続されていない節がないこと

が言える。まずこのチェックを行い、これを満たさない場合は即座に -1 を返す。

この条件を満たしつつ、かつ全域木になっていないということは、すくなくとも1つの部分木はその部分木において最小全域木ではなく冗長な枝をもっているはず。その枝を別の部分木の枝と置換すると部分木同士を連結することができる。

したがって求める解は部分木の数 - 1 となる。どの枝を交換するとか考えず、単に最初の状態で部分木の数だけを数えれば良いだけなのだ(もちろん最初に解の存在性のチェックは必要だが)。

うーん、これはくやしい。ちゃんと考えれば良いスコアでクリアできた問題だ。

Level 3

開くこともできず。

チャレンジフェーズ

なにもできず。

まとめ

1問正解の 198.22 で rating 1525 -> 1542。やはり Level 1 を確実にクリアすることが黄色の最低条件である模様。次回こそは Level 2 もクリアしたい。

補足(2009/5/29)

上の説明で、部分木とか全域木とかの表現を使ってるけど、ちょっと正確な表現ではありませんでした。閉路があると木ではないので。部分木->枝で接続された部分グラフ、全域木->任意の節点間の経路が存在するグラフ、とでも読み替えてください。

トラックバック - http://topcoder.g.hatena.ne.jp/yehara/20090528
 |