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分で埋めるとかしていたので。

 |