2019-01-01から1年間の記事一覧
150着。易しい。伝統的な解法。projecteuler.net
119着。 これも単純。 https://projecteuler.net/problem=687
269着。 これはやさしい。https://projecteuler.net/problem=686
https://projecteuler.net/problem=683115着。 特に難しいことは無い。 sが累積だったら多少難しくなるかもしれないが。
https://projecteuler.net/problem=681107着。フォーラムで解けなかった問題、らしい。記憶になかった。 SymPyを使いながら計算をしたら、きれいな形になった。 それを工夫して組んでみたらやけに遅かったので、素直に組んだらPyPyで4分くらいだった。 どう…
[プログラミング]Project Euler 659https://projecteuler.net/problem=659517着。これはすぐに分かる。懐かしい問題に帰着する。 昔この問題の解法を思いついた時、感動したものだったが。
https://projecteuler.net/problem=679298着。フォーラムではを提案していたのだが、なぜかになってしまった。簡単すぎる。
Juliaで例えば、グラフのエッジを逆向きにするグラフを作る関数を書くとする。 function main() graph = Dict{Int,Vector{Int}}() for v in 1:3 graph[v] = collect(v+1:4) end println(graph) rev_graph = reverse_graph(graph) println(rev_graph) println…
https://projecteuler.net/problem=678夏休み明けで久しぶりの自作問題。 数学寄りの問題で、アルゴリズムを問う場面は無かったと思う。 場合分けが必要。
https://atcoder.jp/contests/abc138/tasks/abc138_eなんということもない問題だ。この位置にいる時に、この文字は次にどこにあるかをテーブルにしておけばよい。 しかし、Pythonでどうしても時間切れになる。PyPyでもなぜか速くならない。 じゃあC++で、と…
AlignmentのBacktrackのときに、文字を前に追加しなければならないが、当然後ろに追加して最後に文字列を逆にする方が速いと思える。しかし、このようなコードで、 import sys import time def f_add_to_head(N): s = '' for _ in range(N): s = 'c' + s ret…
https://projecteuler.net/problem=669203着。 久しぶりにやった。 変わった問題だが、すぐになんとなくわかる。 でも、そこからは怪しい。解けるんだけど、本当にこれでいいのか。 きっちり検証すれば正しいかどうかわかるが、そうしなくてもなんとなく解け…
これは、昔からコマンドプロンプトでよくやっていた。例えばPythonのコードを書いて、さあ実行しようという時に、コマンドプロンプトを起動して、Change Directoryする。しかし、わざわざ分かっているディレクトリに手動で移動するのは面倒ではないか。コマ…
Problem 42 https://projecteuler.net/problem=42 function read_names(path) open(path, "r") do fp for line in eachline(fp) return [ s[2:length(s)-1] for s in split(line, ",") ] end end end function is_square(n) return Int(floor(sqrt(n)))^2 ==…
Problem 33 https://projecteuler.net/problem=33分数は、次のように書く。 julia> f = 4//6 2//3 julia> typeof(f) Rational{Int64} julia> numerator(f) 2 julia> denominator(f) 3
Problem 25 https://projecteuler.net/problem=25 function add(v1, v2) if length(v1) > length(v2) return add(v2, v1) end v3::Array{Int} = [] carry = 0 for k in 1:length(v1) n = v1[k] + v2[k] + carry carry = div(n, 10) d = n % 10 push!(v3, d) …
Problem 22 https://projecteuler.net/problem=22 function read_names(path) open(path, "r") do fp for line in eachline(fp) return [ s[2:length(s)-1] for s in split(line, ",") ] end end end function name_score(name) return sum(Int(c)-Int('A')+…
Problem 20 https://projecteuler.net/problem=20Problem16とだいたい同じ。Pythonで書くと、 from itertools import * import sys def multiply(v, n): v2 = [] carry = 0 for d in v: carry, r = divmod(d*n+carry, 10) v2.append(r) while carry > 0: car…
Problem 17 https://projecteuler.net/problem=17何度も解いているが、一度も最初で正しい答えを出した記憶がない。 できるだけ再帰を使う。 function e017(N) function num_length(n) if haskey(num_letters, n) && n < 100 return length(num_letters[n]) …
Problem 16 https://projecteuler.net/problem=16本当は速い方法(メルセンヌ数を10進表示する)があるが、ここでは単に2倍ずつしていく。Pythonでは、 import sys def twice(v): v2 = [] carry = 0 for d in v: carry, r = divmod(d*2+carry, 10) v2.append(r…
Problem 15 https://projecteuler.net/problem=15DPで解く。 function e015(N) a = zeros(Int, N+1, N+1) a[1,1] = 1 for x in 2:N+1 a[1,x] = 1 end for y in 2:N+1 a[y,1] = 1 end for y in 2:N+1 for x in 2:N+1 a[y,x] = a[y,x-1] + a[y-1,x] end end re…
Problem 14 https://projecteuler.net/problem=14Collatzはこう書ける。 function Collatz_length(n) len = 1 while n != 1 if n%2 == 0 n >>= 1 else n = n*3+1 end len += 1 end return len end function e014(N::Int) max_length, max_n = maximum((Colla…
Problem 13 https://projecteuler.net/problem=13多倍長整数を自作してもいいが、ここではBigIntを用いる。 function make_big_numbers() a = [ "37107287533902102798797998220837590246510135740250", "4637693767749000971264812489697007805041701826053…
Problem 12 https://projecteuler.net/problem=12本当は速い方法があるが、ここでは愚直に順番に約数の個数を調べていく。 function factorize_naive(n) fs = [] for d in Iterators.countfrom(2) if d*d > n break elseif n%d == 0 e = 1 n = div(n, d) whi…
Problem 11 https://projecteuler.net/problem=11generatorを使うと吉。 function make_table() a = [ "08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08", "49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00", "81 49 31 73 55 7…
Problem 10 https://projecteuler.net/problem=10エラトステネスの篩を行うだけ。 function make_prime_table(N::Int64) a = [ true for n in 1:N ] for p in 2:N if p*p > N break elseif !a[p] continue end for n in p*p:p:N a[n] = false end end return…
Problem 9 https://projecteuler.net/problem=9ピタゴラス数は一般に、と書ける(mとnは互いに素でどちらかが偶数で、)て、直角三角形の周囲の長さはとなるので、周囲の長さ/2を2つの約数に分けて、さらにその一方を2つの約数に分ける必要があるが、mとm+n…
Problem 8 https://projecteuler.net/problem=8 function make_table() a = [ "73167176531330624919225119674426574742355349194934", "96983520312774506326239578318016984801869478851843", "85861560789112949495459501737958331952853208805511", "125…
Problem 7 https://projecteuler.net/problem=7このあと単純にエラトステネスの篩を使う問題があるので、この問題はナイーブに素数判定するのが正しいと思われる。Pythonでこう書く。 from itertools import * import sys def e007(N): primes = [2] def is_…
Problem 6 https://projecteuler.net/problem=6 function e006(n) return sum(1:n)^2 - sum(k*k for k in 1:n) end N = parse(Int, ARGS[1]) println(e006(N)) 内包表記はPythonと同様に使える。べき乗は、**ではなく^を使う。PythonやCはXORを^に充てていた…