Hatena::Grouptopcoder

yehara のTopCoder日記

 | 

2009-09-24

SRM 449 Div1

11:21 |  SRM 449 Div1 - yehara のTopCoder日記 を含むブックマーク はてなブックマーク -  SRM 449 Div1 - yehara のTopCoder日記

Level 1 (250)

三角形の頂点が格子点上にあり、2辺の長さ(の平方数)が与えられたとき、この制約上で取り得る三角形の最大面積を求める問題。

長さが与えられた2辺が接する頂点を原点に固定して考えると、他の頂点の取り得る場所は数個〜数十個程度に限られるはずなので、取り得る x, y とそれらの回転を組み合わせて最大値を求めるだけ。

それだけの問題なのだが、System Test で落ちた。辺の長さを2つの平方数の和に分割しなきゃと思って実装していて、1つの平方数のケース(頂点が X/Y 軸上にあるケース)を見落としていた。

Level 2 (550)

問題を理解するのに時間がかかった。「大戦略」風の六角形のフィールド(障害物がある)を2マスつながったタイルで敷き詰めるときに、敷き詰め方が何通りあるかを求める問題。

どう考えても DP なんだけど、書いたコードでは最大ケースで TLE。もっと改良が必要そうだが、時間が足りなかった。

Level 3 (950)

見ただけ。

まとめ

Level 1 を取りこぼしてるようではダメだ。0 点で当然の青落ち(1550->1460)。最近、青黄ラインを行き来している。

TopCoder 部内では naoya_t さん (g:topcoder:id:n4_t:20090924) とほぼ同じレベルか。思考の過程も似ている気がする。お互いもっと上を目指して頑張りましょう。

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