deq notes

Get Many Persimmon Trees 解説

• 問題名：Get Many Persimmon Trees (PKU)
• 出典：Problem B, ACM/ICPC Japan Domestic, 2003-10-03
• 難易度：☆
• 問題の種類：探索
• 解法：全探索
• 解答ソースコード：
  • 2029-deq.cpp

アルゴリズムの概略と計算量

四角形によって内包できる点の数の最大値を求めるというもの。 0 < W, H < 100 なので，フィールドに対して4重ループの全探索をしても最大でも O(100⁴) = O(100,000,000) 程度。 少し大きいかと思いますが，実際は S = T = 50 周辺のときに計算量が（おそらく）最大になって 50⁴ = 6,250,000 = 6M 程度の計算量にしかならず， ループの内側はカウントだけ（数クロック程度）なので1GHzのCPUでも1つのデータセットが0.01秒程度で終了します。 よって，4重ループの全探索でこの問題は解けます。

アルゴリズムの実装

特に難しいところはありませんが，ループの境界条件（ループ変数の開始値と終了値）をしっかりと間違わずにコーディングできるようになりましょう。 このような細かいところが正確に速く書けるようになることが大切です。

$Id: index.shtml 1335 2007-03-01 09:06:39Z SYSTEM $