Hatena::Grouptopcoder

Gus@topcoder

topcoderのid:gusmachineの記録です。普段の日記は揺動散逸日記をどうぞ。
 | 

2010-04-04

SRM 466 1000

03:07

試したところ、単純なDP + bit encoding だけだとTLEしてしまいました。以下メモ。

  • まず、Bでないところにビットを立てた整数の配列として保存。Bで塗りつぶす作業はビットをクリアすることに相当する。
  • 上下左右の順番は意味がないので、そこを圧縮する。
  • Bでの塗りつぶしは、ビットを0にする代わりにその列を消してしまう。横列はその変数を消去。縦列はその段を消去してしまう。
    • この最適化を行うとBで塗り潰されたrowについて 0 と無しとの二つの表現ができてしまう。メモ化するために0のみのrowは削除して一意性を保つ。
  • 順序は意味がないのでソートしておく。

ここまでやっても時々TLEします。とりあえずprofilingしてみる。

  • -pgつきでコンパイル
  • ./executable
  • gprof executable gmon.out > logfile.txt

結果、std::vector<>::_M_insert_auxが多いことが判明。一回にかかる時間は短いものの呼び出し回数がひどい。

reserveをしていなかったのでしてみたところ、4.5 sec が 3.1 sec に。まだ足りません。

そもそも関数を呼ぶ回数が多すぎです。例えば状態圧縮がまだうまく機能していないということ。gprof使う以前のアルゴリズムレベルの話です。

あとは何でしょう。ビットの左右も無意味だけどここをソートするのは面倒。

 |