僕のIT革命

問題 原文 How many different ways can £2 be made using any number of coins? 日本語訳 いくらかの硬貨を使って2ポンドを作る方法はいくつあるでしょうか? 解答 ポンドとペンスを別々に扱うのは面倒と無駄以外の何者でもないので、単位をペンスに統一します。よって問題は合計が200ペンスとなるコインの組み合わせは何通りあるかです。 コインを昇順にC i (i = 0, 1, 2, ..., 7)と番号づけることにします。 合計nペンスとなるC k 以下のコインを使った組み合わせをcc(n, k)と表すと、次のようになります： cc(0, k) = 1 cc(n, 1) = 1 cc(n, k) = Σ(cc(n - iC k , k - 1))、ただしi ∈ { 0 , 1, 2, ..., floor(n / C k ) } 副問題は同じものが何度も出てくるのでメモ化しています。 #!/usr/bin/env perl use strict; use warnings; use feature qw/say state/; use List::Util qw/sum/; sub coin_comb($;$); { my @coins = (1, 2, 5, 10, 20, 50, 100, 200); sub coin_comb($;$) { state %memos; my ($currency, $coin_idx) = @_; $coin_idx //= $#coins; return $memos{$currency, $coin_idx} if exists $memos{$currency, $coin_idx}; return 1 if $currency == 0; return 1 if $coin_idx == 0; use integer; $memos{$currency, $coin_idx} = sum map { coin_comb($currency - $coins[$coin_idx] * $_, $coin_idx...

問題 原文 Find the sum of all the numbers that can be written as the sum of fifth powers of their digits. 日本語訳 各桁を5乗した和が元の数と一致するような数の総和を求めよ. 解答 まず探索範囲の上限を定める必要があります。n桁の最大の整数a n = 9 n-1 9 n-2 ...9 0 を考えると、その各桁の5乗の和はb n = 9 5 nと表せます。 a n+1 = 10a n + 9 b n+1 = b n + 9 5 ですから、桁数nが大きくなるにつれてaがbよりも急激に大きくなるのが分かります。ある桁数n max を超えると、常にa n max > b n max が成立するので、両者が等しくなることはなくなります。 実際に調べるとn max は6なので、探索範囲は高々0から999,999までとなります。 各桁の乗数の和は、桁の並びに関わらず各桁の数のみによって決まります。例えば2501、5012、(0)215のいずれも同じb n を持つので、これを別々に計算するのは時間の無駄です。 そこで、このような数をすべて同値と見なす正規化を考えます。手っ取り早く桁の並べ替えで良いでしょう。各桁を昇順に並べ替え、その上で先頭に1個以上0があったら取り除くという処理です。先ほどの例に挙げた数字をこの方法で正規化すると、いずれも125となります。 この正規化された数のみを走査すれば良いわけですから、（0を含まない）n桁の数1つにつき同じ値をn!通り計算していたところが、1通りで済むことになります。 処理の手順をまとめると次のようになります： 全ての正規化された数に対してb n を計算し、連想配列に格納しておく。 連想配列に格納された値を1つ取り出し、a n とする。 a n を正規化して連想配列から対応するb n を引く。 a n = b n であれば解に加える。 連想配列の値を全て走査するまで2.に戻って繰り返す。 下記のコードでは初期化の都合上、桁数ごとに連想配列を分けていますがアルゴリズム自体に違いはありません。 #!/usr/bin/env perl ...

こんばんはSekia the Liarです。更新頻度についての釈明はさておきえーとP.E. 29でしたね。はい、すいません。 問題 原文 Consider all integer combinations of a^(b) for 2 ≤ a ≤ 5 and 2 ≤ b ≤ 5: （引用者による省略） How many distinct terms are in the sequence generated by a b for 2 ≤ a ≤ 100 and 2 ≤ b ≤ 100? 日本語訳 2 ≤ a ≤ 5 と 2 ≤ b ≤ 5について, abを全て考えてみよう: （引用者による省略） 2 ≤ a ≤ 100, 2 ≤ b ≤ 100 で同じことをしたときいくつの異なる項が存在するか? 解答 値の重複を取り除くにはハッシュを使うのが定石です。 use strict; use warnings; use feature qw/say/; use Math::BigInt; my %pows; for my $n (2 .. 100) { for my $i (2 .. 100) { $pows{ Math::BigInt->new($n) ** $i } = 1; } } say scalar keys %pows; しかしPerlのメソッド解決オーバヘッドは結構でかいので、10,000個のMath::BigIntインスタンス生成は割と時間を食います。毎回Math::BigIntというのも芸がないし、少し頭を使って解いてみることにしました。 a b = (a n ) b/n であることに着目しましょう。これは中学だか高校だかで習った通りです。ただし問題の範囲は整数なので、指数は2 ≤ b/n ≤ 100なる整数でなければなりません。つまりnはbの約数（ただしb自身を除く）です。 この等号で結ばれたべき乗は同じ（つまり重複した）値を持ちます。 例えば2 12 = 4(=2 2 ) 6 = 8(=2 3 ) 4 = 16(=2 4 ) 3 = 64(=2 6 ) 2 = 4,096であり、他に4,096となるようなべき乗は整数の範囲ではなさそう...