週に一回は書きますよ 月に4つ記事を書けばノルマは満たされます。
上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

前回があまりにもひどかったので、まじめに復習して次回に備えることにしました。

しかし75分で解けたのは250点と500点だけ。両方ともSystem Testは通りました。1000点は時間内にテストケースを通すことができませんでした。まだSystem Testを通すプログラムができていません。

250点は瞬殺で242.16点。500点は解けたはずなのにはまりました。メモ化して探索するのですが、

int search_impl(args) {
  if (outOfDomain())
    return 0;
  // snip;
}
int search(args) {
  int& memo = table[args];
  if (memo<0)
    memo = search_impl(args);
  return memo;
}
と書いて、tableが配列で、argsにoutOfDomainとなる負の値を入れて領域外アクセスをしてしまいました。テストケースが通らないので気付きましたが。

1000点は本番ではスルーした最大流問題です。解きかたは上位の解答を見て把握したものの、最大流なんてしばらく書いていないので酷いことになりました。 そもそもICPC現役のときも最大流はChunにまかせていたような気もしますが。 いまだに計算時間が遅く、もっとも大きいテストケースでこけます。

追記:計算量の問題ではありませんでした。よく調べたらdfsがバグって無限ループしていました。

ところで、Practice roomの1000点解答があまりに酷いので撃墜しておきました > shinhさん

スポンサーサイト
コメント
この記事へのコメント
あ、あれはさすがに通らないのはよく知っていてというか、SRMの最中に投稿したまさにあまりにひどい解答だったわけですが、終わったあとにてっとり早く落ちるテストケースを教えてもらうために practice にそのまま submit して system test した、というような。
2008/04/28(月) 08:31 | URL | shinh #-[ 編集]
なるほど。というかtopcoderの練習所においてある他の人のプログラムって良くかんがえたらそういうレベルのものもあるはずですね。ぜんぜんあたまがまわっていない。
ところで500点問題は一応DPのサンプルな気がするのでやってみてはどうでしょう。あんまり良いサンプルではないですが。
2008/04/28(月) 08:42 | URL | Gus #-[ 編集]
やりますやります。教えていただいてどうもです。
2008/04/28(月) 13:54 | URL | shinh #-[ 編集]
コメントを投稿する
URL:
Comment:
Pass:
秘密: 管理者にだけ表示を許可する
 
トラックバック
この記事のトラックバックURL
http://gusmachine.blog49.fc2.com/tb.php/334-4a222fc0
この記事にトラックバックする(FC2ブログユーザー)
この記事へのトラックバック
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。