deq notes

Space Coconut Crab 解説

• 問題名：Space Coconut Crab [宇宙ヤシガニ]
• 出典：Problem A, ACM/ICPC Practice Contest for Japan Domestic, 2007-06-24
• 難易度：☆
• 問題の種類：探索
• 解法：特になし
• 解答ソースコード：
  • p0104-deq.cpp
• OB/OGの会の解説：p0104-obog.pdf

アルゴリズムの概略

与えられた e に対して，x + y² + z³ = e を満たすような x, y, z の組み合わせのうち， m = x + y + z を最小にするような m を出力せよ，という問題。 ここで e ≦ 1,000,000 です。

変数 x, y, z に対してそれぞれループを回して全探索すると計算量が最悪 1,000,000×1,000×100 = 100G になって解けません。 しかし，y, z を定めると x は x = e - y² - z³ でループを回さず求めることができるので， 変数 y, z に対してそれぞれループを回すだけでよく，その時計算量は 1,000×100 = 100K になって解けるようになります。

別解

変数 z のみに対してループを回し，残りの値 r = e - z³ の2次方程式 r = x + y² を解析的に解く方法があります。 詳細はOB/OGの会の解説を参照してください。

$Id: index.shtml 1576 2007-06-25 15:10:28Z SYSTEM $