Hatena::Grouptopcoder

Gus@topcoder

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

2009-07-08

久しぶりすぎてはてな記法がわかりません。ここはどこですか。

SRM 444

23:44

  • 250 165.19
  • 500 Challenged
  • 1000 Opened

500の撃墜例を作ったら自分が落ちてしまったの巻。

250 pts.

書くだけ。「あるマスを頂点として作れる三角形のうち最大のもののサイズ」を返す関数を書いてそれを全域でループ。

一回y0とyとを間違える的なミスをしてSIGSEGVして、それを見付けるのに手間取ってこの有様でした。

500 pts.

書くだけ。いつかのICPC予選を彷彿とさせます。

  • function maxpts:
  • for(;;)
    • maxscore = score
    • 4が入らないところに1を埋める
    • 4を置ける場所tx, tyを見つける。ないならreturn maxscore
    • maxscore = max(maxscore, maxpts( (tx, ty)に4を置いたとき))
    • tx, tyに1を置く。

とりあえず最大ケースがすぐ終了することを確認。

と思ったら再帰しているところでボードをコピーするのを忘れていたため、greedyな解しか出なくなってました。

1000 pts

行列計算。途中を抜くのが分からず、また残り10分程度だったので無視して500 ptsで遊んでました。

Challenge phase

トップの人が次々500を撃墜。ここでやっと貪欲アルゴリズムが多数提出されていることに気づきました。

よく見ると実はトップの人も貪欲アルゴリズム。

手元で例を作って撃墜しようとするものの入力中に他の人に先を越されてしまいました。残念。

ついでに自分のコードにも欠陥があることが発覚。

しまいには皆平等に撃墜されました。

感想

練習重要。

  • 入力例で文字列を入力するときについダブルクオートを入れてしまう。
  • テンプレートで30 % 警告が出まくる。
  • TZTesterがマクロをつかっているので入力を足したいときにインデントが揃わない。
  • Javaテンプレートを作っていない。

次回までになんとかしましょう。

 |