最大の攻撃を繰り出せ！【解説】

• 本稿はCodeIQで出題された 第1回プロコン：【鬼】最大値をたたき出す攻撃を繰り出して鬼を倒そう という問題の解答例と簡単な解説です。

• 本稿におけるコードは単なる解答の1例に過ぎません。「もっと良い解法があるよ！」とか、「こう書いた方がわかりやすいよ！」とか、「他の言語で書いてみたよ！」という場合は、自由にコメントに書いていただいても、個人のブログ等で公開していただいても結構です。

問題本文はこちら

最大の攻撃を繰り出せ！【解説】

◆解説

a³ + b³ = c³ + d³…(1)を満たすa, b, c, dについてすべての場合を総当たりで解こうとすると、入力の最大値が1000ですので大雑把に計算量を見積もると、約1000の4重ループで1000⁴近い計算を行うことになります。このままでは制限時間を超えてしまいますので、ループ回数をもう少し抑える工夫をしてみます。 x³ + y³ = k (ただしx < y)とすると、この等式を満たすx, yが2通り以上あれば、(1)を満たすa, b, c, dが存在すると言えます。そこでkをキーとしたハッシュマップを用いて、取り得るkの値をすべて記録していきます。ハッシュマップをhとすると、xとyの組み合わせに重複が無いように列挙すれば、あるx, yについて、h[k]が存在しなければh[k]を登録し、もしすでに存在していれば、それはx, yの組み合わせが少なくとも2種類は存在するという意味になります。この時のkの値の中から最大のものを見つけることで解が得られます。

◆解答例

#!ruby

n = STDIN.gets.to_i
h = Hash.new
m = 0
(1..n-1).each{|x|
  (x+1..n).each{|y|
    k = x*x*x + y*y*y
    if h[k]
      m = k if k > m
    else
      h[k] = true
    end
  }
}
puts m