「『ルート・パワー』問題」とは

CodeIQ「『ルート・パワー』問題」の掲載期間が終わり、提出コードを公開してよいとのことなので、その流れに乗りたいと思います。問題の内容や出題者の@riverplusさんによる解説が後日CodeIQMagazineあたりに公開される――はず(前例にならえば)なので、そのときに覚えていればここにリンクを張り付ける予定です。

2015/12/25追記:
公開されたコードを出題者の@riverplusさんみずからTogetterにまとめて下さっております。この記事よりよっぽどいいコードが集まっているので、ご参考のほどを。わたしもまだまだですね(´・ω・`)

2015/12/25追記:
今日二度目の追記。予想通り(?)出題者による解説記事が公開されておりました。わたしは今から精読します(´・ω・`)

提出コード

使用した言語はRuby。おそらく4-5回目ぐらいで全問通った記憶があります。

# a + b * s(2) + c * s(3) + d * s(5) + e * s(6) + f * s(10) + g * s(15) + h * s(30)
# ただしa,b,c,d,e,f,g,hはすべて0以上の整数。
class H

    @@BIG = 10 ** 7

    def initialize(a, b, c, d, e, f, g, h)
        @a, @b, @c, @d, @e, @f, @g, @h = a, b, c, d, e, f, g, h
    end

    attr_accessor :a, :b, :c, :d, :e, :f, :g, :h

    def *(other)
        H.new(
            (@a * other.a + 2 * @b * other.b + 3 * @c * other.c + 5 * @d * other.d + 6 * @e * other.e + 10 * @f * other.f + 15 * @g * other.g + 30 * @h * other.h) % @@BIG,
            (@a * other.b + @b * other.a + 3 * @e * other.c + 5 * @f * other.d + 3 * @c * other.e + 5 * @d * other.f + 15 * @h * other.g + 15 * @g * other.h) % @@BIG,
            (@c * other.a + 2 * @e * other.b + @a * other.c + 5 * @g * other.d + 2 * @b * other.e + 10 * @h * other.f + 5 * @d * other.g + 10 * @f * other.h) % @@BIG,
            (@d * other.a + 2 * @f * other.b + 3 * @g * other.c + @a * other.d + 6 * @h * other.e + 2 * @b * other.f + 3 * @c * other.g + 6 * @e * other.h) % @@BIG,
            (@e * other.a + @c * other.b + @b * other.c + 5 * @h * other.d + @a * other.e + 5 * @g * other.f + 5 * @f * other.g + 5 * @d * other.h) % @@BIG,
            (@f * other.a + @d * other.b + 3 * @h * other.c + @b * other.d + 3 * @g * other.e + @a * other.f + 3 * @e * other.g + 3 * @c * other.h) % @@BIG,
            (@g * other.a + 2 * @h * other.b + @d * other.c + @c * other.d + 2 * @f * other.e + 2 * @e * other.f + @a * other.g + 2 * @b * other.h) % @@BIG,
            (@h * other.a + @g * other.b + @f * other.c + @e * other.d + @d * other.e + @c * other.f + @b * other.g + @a * other.h) % @@BIG,
        )
    end

    def **(n)
        return H.new(1, 0, 0, 0, 0, 0, 0, 0) if n == 0
        n.odd? ? self ** (n - 1) * self : (self * self) ** (n / 2)
    end
end

# == main ==
h = H.new(1, 1, 1, 1, 0, 0, 0, 0)
n = gets.to_i
p (h ** n).a

反省会

問題の内容はおおざっぱに言うと「$1 + \sqrt{2} + \sqrt{3} + \sqrt{5}$のべき乗を求めよ」というもので、これはかならず次のようになるはずです(ただしa, b, c, d, e, f, g, hはすべて0以上の整数)。

H=a+b\sqrt{2}+c\sqrt{3}+d\sqrt{5}+e\sqrt{6}+f\sqrt{10}+g\sqrt{15}+h\sqrt{30}

あとはもう明らかですよね。「Hのようなもの」どうしの掛け算がどのように展開されるかが分かれば当然掛け算が定義でき、掛け算が定義できればいうまでもなくべき乗は定義できるということになります。

――が、こういう解法は非推奨というか、はっきりいえば「だめ」でしょう。まずもってスマートではない。おそらく行列計算とか多項定理とかあるいは規則性とかを利用するのでしょうが、筆者はさっぱり思い浮かばず、強引な手法で解いてしまいました。まあ一応こういう解き方もできるよというサンプル程度に。

(ちなみに展開は紙に書いて行ったのですが、すごい時間がかかりました。しかもそれを間違いなくソースコードに写し取るのにも時間がとられ、結局1時間以上かかった記憶があります……)

注意としては「オーバーフローに気を付けろ」。最初はC言語で実装していたのですが――まずintでだめ、次にlongでもだめで、思考停止のunsigned long long intでもオーバーフローを起こし、心が折れてしまいました(´・ω・`)。そしてRubyで実装提出し、無事合格になったのでした。動的言語万歳! ただし7桁の整数を掛け合わせて、それを最大8つも足し合わせるような計算をするので、オーバーフローするのは当たり前といえば当たり前ですが……。

CodeIQ「『ルート・パワー』問題」に参加しました。

「『ルート・パワー』問題」とは

提出コード

反省会