Hatena::Grouptopcoder

Gus@topcoder

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

2010-04-04

SRM 466

11:23

x o opened - failx2 : 416.18 pts.

  • 250 challenge succeeded.
  • 500 466.18 pts
  • 1000 opened. あと数分?
  • 2 チャレンジミス

250で盛大に方針を間違えました。この類いの失敗は練習不足です。250がこんなに難しいわけがない。

250

探索しようとして爆死。42分もかかってできたものは探索が深くなるとTLEするしろものでした。わざわざTLEしないように適当なA*法を使ったのですが無駄なあがきであることに終了後に気づきました。

  • 上位の桁だけきめる。下の桁は上の桁から自動的にきまる。
  • 上位の桁を固定したときの、下の桁の平方数までの距離をA* potentialにとる。

終了後に9999999999でTLEすることに気づきました。

500

組みあわせ数え上げ。プログラムというより数学。

くじの番号はシャッフルしないで、上から順番についているとする。で、それのなかからランダムに5つ正解が選ばれるとする。正解のパターンは以下のとおり。

  • 同列に5つ
  • 同列に4つ、他にひとつ。
  • 同列に3つ、他にふたつ。
      • 3-2, 3-1-1に分けましたが、分けなくてもいいことに気づきました。

1000

解きおわっていません。これ安直にDPだけだとTLEするのでしょうか?

Challenge

とりあえず青い人の250の早めの解にchallengeして返りうち。

そのあとその人の解を見て正しい解法を知りました。

そのあともう一人challengeするも失敗。

結論。

もうすこし冷静になりましょう。250に40分かかった後500を6分で埋めるとかしていたので。

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使う以前のアルゴリズムレベルの話です。

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

ゲスト



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