おじい研究所

主にプログラミングの話題です

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

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

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

問題本文はこちら

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

◆解説

a3 + b3 = c3 + d3…(1)を満たすa, b, c, dについてすべての場合を総当たりで解こうとすると、入力の最大値が1000ですので大雑把に計算量を見積もると、約1000の4重ループで10004近い計算を行うことになります。このままでは制限時間を超えてしまいますので、ループ回数をもう少し抑える工夫をしてみます。 x3 + y3 = 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

こっちは古い版