Scala
Problem 100ラストです。 合計のディスクの枚数をn、青いディスクの枚数をbとすると、 (b/n)( (b-1)/(n-1)) = 1/2 です。変形していくと次のようになります。 (2n - 1)2 - 2(2b - 1)2 = -1 これはPell方程式ですね。 x2 - 2y2 = -1 の解は、 x + y√2 = (1 + …
Problem 99logを取るだけで十分です。
Problem 98アナグラムは次のように探します。例えば、CAREをアルファベット順に並べるとACERになります。RACEも同じです。こうして同じになったものがアナグラムです。まずそうやって全ての単語を調べます。groupByを使うと簡単ですね。ScalaのgroupByはソー…
Problem 97これはシェルピンスキー数というものを調べているときに発見された巨大素数らしいです。 多倍長整数を使えば、 println (((BigInt(1) << 7830457) * 28433 + 1) % 1e10.toLong) これだけです。 しかし、いくらなんでもこれでは芸が無いので、64ビ…
Problem 96数独は深さ優先探索で簡単に解けます。左上から空欄に順番に数字を埋めて、縦横正方形で重複が無ければ隣に移ります。ダメなら次の数字、それでもダメなら元に戻ります。
Problem 94等辺以外の辺の長さは偶数です。奇数だとすると三角形を対称軸で半分に割った三角形の各辺を2倍した直角三角形の斜辺は偶数で、別の辺は奇数です。そうするともう一つの辺の平方は4の剰余が3となって矛盾です。そこで先ほどの辺を2bとして等辺をa…
Problem 93四則演算の関数を定義しておくとリストにできて書きやすくなります。
Problem 92よく考えたら、これは長い多項式の掛け算だからKaratsuba法が使えますね。Scalaは多倍長整数の掛け算が遅いので特に効果が大きいはずです。 これくらい速くなりました。 1050 0.6s -> 0.12s 10100 3.4s -> 0.5s 10200 28s -> 2.4s
Problem 92母関数を使うと圧倒的に速くなります。 1桁の場合母関数を次のように表します。 P1(x) = 1 + x + x4 + x9 + ... + x81 これは、各桁の平方和が0, 1, 4, 9, ..., 81になる場合が一つずつあり他は0ということを意味しています。2桁の場合は、 P2(x) …
Problem 92数字が入れ替わっても次は同じです。例えば23 -> 22 + 32 = 13、32 -> 32 + 22 = 13です。こういうときは重複組合せですね。なのですが、場合の数を計算しやすいように、 1 1 1 2 2 3 4とするところを、 (1, 3) (2, 2) (3, 1) (4, 1)としました。 …
Problem 92107までなので、チェーンの次は92*7以下になります。だからそれ以下をあらかじめ1か89のどちらに帰着するかを調べておきます。
Problem 91前回の3を効率よくします。Pを固定してQをPが直角になるように配置します。例えば、L = 10として、P(4, 6)としましょう。OPと直交するベクトルは(6, -4) = 2(3, -2)だから、Qは(4 + 3t, 6 - 2t)と書けます。Qのx座標は10以下だからt L = 10000で10…
Problem 91直角三角形を3通りに分けて考えます。 Pがy軸上でQがx軸上のもの Pがy軸上でQはその右、またはQがx軸上でPはその上 P、Qは軸上にないもの 上の2つは簡単です。L = 50として、最初の場合はL^2個、次の場合は2L^2個あります。 3番目は、図のようにP…
Problem 90全探索でOKです。
Problem 89ローマ数字をIntに直してさらにローマ数字に変換するだけですね。
Problem 88これも素直に解きます。pを積、sを1以外の和、nを1以外の項数とすると項数lは l = p - s + n となります。これは1以外の項を追加すると常に大きくなるので（1の項は積と和が等しくなるように個数を調整する）、12000以下になるように列挙できます…
Problem 87これは素直に解くしか無さそうです。同じ和でも別として数えるのならやり方もありそうですが。
Problem 86(a, b) = (3, 4)のとき、3を分割する場合の数は1で、4を分割する場合の数は2です。相似の三角形を考えると、M = 20として、前者は(15, 20)まで、後者は(18, 24)まであります。それぞれの個数は、 1 + 3 + 4 + 6 + 7 = 21 2 + 3 + 4 + 5 + 6 + 7 = …
Problem 86直方体の3辺の長さをp, q, r(p < q < r)としてp + qとrが直角を成す三角形の斜辺が整数になる場合を求めるのでしたが、逆にピタゴラス数(a, b, c)(a < b < c)が先に与えられた場合を考えます。例えば、(3, 4, 5)というピタゴラス数を考えます。斜…
Problem 87単に1分以内に収めたいだけなら次のようにすればよいです。最大の辺が1, 2, 3, 4, …となる直方体の数を数えていけばよいです。47秒でした。 ただ、この方法は発展性が無いんですよね。
Problem 86直方体の3辺の長さをp, q, r(p < q < r)とすると、距離の自乗は (p + q)2 + r2 なのでこれが平方数ならば最短経路が整数になります。直方体の数を求める最も簡単な方法はp, q, rを列挙することです。これはO(M3)かかります。これでは箸にも棒にも…
Problem 85前々回の方法だと計算量はだいたいO(N1/4)になります。だから、1032くらいが視野に入ってきます。ScalaはBigIntを使うと遅くなるので、型を決めるのは重要です。mはIntで十分です。nはLongが必要です。それから、sqrtですが、これは引数が大きくな…
Problem 85別の方法もあります。簡単のために長方形の数を100とします。三角数を並べます。 1 3 6 10 15 21 28 36 45 55 66 78 91 105これとこの逆の並び、 105 91 78 66 55 45 36 28 21 15 10 6 3 1とでマージ法を使います。先頭の1と105の積は105です。こ…
Problem 85m×nの長方形はm(m + 1)n(n + 1) / 4個の長方形を含みます。目標の長方形の個数をNとしてmを固定すると、 n2 + n + 1 = 4N / m(m + 1) となります。これを解いて、 n = (-1 + √(1 + 16N / m(m + 1))) / 2 これは一般に実数ではないので、[ n ]と[n +…
Problem 83まずマスiからマスjへの遷移確率を求めます。（これが難しいのですが。Pythonなら書きやすいのに） その遷移確率行列Aは各マスに止まる確率をvとして次が成り立ちます。 Av = v すなわち、これは固有ベクトルを求める問題です。 ただ、固有ベクト…
Problem 83ダイクストラ法への道 第3弾です。いよいよダイクストラ法を使います。 131 673 234 103 18 201 96 342 965 150 630 803 746 422 111 537 699 497 121 956 805 732 524 37 331最後は右と左と下と上の隣のマスへ進めます。まず左上のマスは確定です…
Problem 82ダイクストラ法への道 第2弾です。 131 673 234 103 18 201 96 342 965 150 630 803 746 422 111 537 699 497 121 956 805 732 524 37 331今度は右と下と上の隣のマスへ進めます。左の列から順に考えていきます。最も左の列は上から下への経路しか…
Problem 81ダイクストラ法への道 第1弾です。 問題に載っている例で考えてみましょう。 131 673 234 103 18 201 96 342 965 150 630 803 746 422 111 537 699 497 121 956 805 732 524 37 331左上をスタートして動けるのは右と下だけです。左上から各マスへ…
Problem 80この問題は整数で考えるとよいです。すなわち、2ならこれに0を198個つけた整数200…00の平方根を整数で考えます。そうするとそれはちょうど100桁になり各桁を足し合わせればよいことになります。平方根を整数で考えるというのは例えば24なら4、25な…
Problem 793桁のキーの前後の数字を関係付けます。例えば319なら、3 → 1、1 → 9という辺をグラフに加えます。そうしたときに、グラフの辺の始点側になっていない点が一つあります。これが元の数の最も右の数字です。そして、この数字を終点とする辺をすべて…
