Hatena::Grouptopcoder

TopCoder煮ブログ

本家ブログはこっち → http://d.hatena.ne.jp/nitoyon/

2008-11-01

表記変更

13:04 | 表記変更 - TopCoder煮ブログ を含むブックマーク はてなブックマーク - 表記変更 - TopCoder煮ブログ

いままでは「SRM 423」のように書いてたけど、「SRM423」(SRM と数字の間にスペースを入れない)ほうが一般的なようなので、そっちに書き換えた。

TheEasyChase (SRM423 DIV1 Medium)

| 13:04 | TheEasyChase (SRM423 DIV1 Medium) - TopCoder煮ブログ を含むブックマーク はてなブックマーク - TheEasyChase (SRM423 DIV1 Medium) - TopCoder煮ブログ

最初は再帰で書いてたけどおそらくオーバーフロー。いろいろ考えたが方針が見えず、C++ 一位の人の回答を見る。解けた場所からスタートして行って、順番に移動量を逆算していってる。どちらが勝つ場合も同じアルゴリズムでいけてしまうようだ。そういわれてみればそういう気もするが理由がしっくり来ない。

復習

20:25 | 復習 - TopCoder煮ブログ を含むブックマーク はてなブックマーク - 復習 - TopCoder煮ブログ

SentenceDecomposition (SRM411 DIV1 Easy)を再度解いてみる。そのまま解いてもダメだろうと思ってしばらく悩んで思い出した。復習しやすいように問題の記録をとっておくとよいんだろな。

AddElectricalWires (SRM410 DIV1 Easy)

| 23:06 | AddElectricalWires (SRM410 DIV1 Easy) - TopCoder煮ブログ を含むブックマーク はてなブックマーク - AddElectricalWires (SRM410 DIV1 Easy) - TopCoder煮ブログ

時間はかかったが System Test OK。部分グラフを完全グラフにするまでに必要な枝数をカウントすればよい。gridConnections を含まない部分グラフはノード数が最大の部分グラフに併合する。C++1位の人の答えで答えあわせしたところ、順番に足していっていた。自分の回答は完成図の枝数から最初の枝数を引いていたが、1位の人のほうがスマートだ。あと、グループ分けするときに、自分の回答では幅優先探索していたが、1位の人は頂点の数だけループを回して浸透させていく方式を使っていた。時間が問題にならないのならこっちのほうがシンプルに書ける。