2019-01-01から1年間の記事一覧

Project Euler 688

150着。易しい。伝統的な解法。projecteuler.net

Project Euler 687

119着。 これも単純。 https://projecteuler.net/problem=687

Project Euler 686

269着。 これはやさしい。https://projecteuler.net/problem=686

Project Euler 683

https://projecteuler.net/problem=683115着。 特に難しいことは無い。 sが累積だったら多少難しくなるかもしれないが。

Project Euler 681

https://projecteuler.net/problem=681107着。フォーラムで解けなかった問題、らしい。記憶になかった。 SymPyを使いながら計算をしたら、きれいな形になった。 それを工夫して組んでみたらやけに遅かったので、素直に組んだらPyPyで4分くらいだった。 どう…

[プログラミング]Project Euler 659https://projecteuler.net/problem=659517着。これはすぐに分かる。懐かしい問題に帰着する。 昔この問題の解法を思いついた時、感動したものだったが。

Project Euler 679

https://projecteuler.net/problem=679298着。フォーラムではを提案していたのだが、なぜかになってしまった。簡単すぎる。

JuliaでC++のtemplateのようなものを実現する

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…

Project Euler 678

https://projecteuler.net/problem=678夏休み明けで久しぶりの自作問題。 数学寄りの問題で、アルゴリズムを問う場面は無かったと思う。 場合分けが必要。

AtCoder Beginner Contest 138 E

https://atcoder.jp/contests/abc138/tasks/abc138_eなんということもない問題だ。この位置にいる時に、この文字は次にどこにあるかをテーブルにしておけばよい。 しかし、Pythonでどうしても時間切れになる。PyPyでもなぜか速くならない。 じゃあC++で、と…

PythonとPyPyで文字を追加する速度が全然違う

AlignmentのBacktrackのときに、文字を前に追加しなければならないが、当然後ろに追加して最後に文字列を逆にする方が速いと思える。しかし、このようなコードで、 import sys import time def f_add_to_head(N): s = '' for _ in range(N): s = 'c' + s ret…

Project Euler 669

https://projecteuler.net/problem=669203着。 久しぶりにやった。 変わった問題だが、すぐになんとなくわかる。 でも、そこからは怪しい。解けるんだけど、本当にこれでいいのか。 きっちり検証すれば正しいかどうかわかるが、そうしなくてもなんとなく解け…

秀丸で開いたファイルのフォルダにUbuntuを開いて移動する

これは、昔からコマンドプロンプトでよくやっていた。例えばPythonのコードを書いて、さあ実行しようという時に、コマンドプロンプトを起動して、Change Directoryする。しかし、わざわざ分かっているディレクトリに手動で移動するのは面倒ではないか。コマ…

JuliaでProject Euler(22)

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 ==…

JuliaでProject Euler(21)

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

JuliaでProject Euler(20)

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) …

JuliaでProject Euler(19)

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')+…

JuliaでProject Euler(18)

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…

JuliaでProject Euler(17)

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]) …

JuliaでProject Euler(16)

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…

JuliaでProject Euler(15)

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…

JuliaでProject Euler(14)

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…

JuliaでProject Euler(13)

Problem 13 https://projecteuler.net/problem=13多倍長整数を自作してもいいが、ここではBigIntを用いる。 function make_big_numbers() a = [ "37107287533902102798797998220837590246510135740250", "4637693767749000971264812489697007805041701826053…

JuliaでProject Euler(12)

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…

JuliaでProject Euler(11)

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…

JuliaでProject Euler(10)

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…

JuliaでProject Euler(9)

Problem 9 https://projecteuler.net/problem=9ピタゴラス数は一般に、と書ける(mとnは互いに素でどちらかが偶数で、)て、直角三角形の周囲の長さはとなるので、周囲の長さ/2を2つの約数に分けて、さらにその一方を2つの約数に分ける必要があるが、mとm+n…

JuliaでProject Euler(8)

Problem 8 https://projecteuler.net/problem=8 function make_table() a = [ "73167176531330624919225119674426574742355349194934", "96983520312774506326239578318016984801869478851843", "85861560789112949495459501737958331952853208805511", "125…

JuliaでProject Euler(7)

Problem 7 https://projecteuler.net/problem=7このあと単純にエラトステネスの篩を使う問題があるので、この問題はナイーブに素数判定するのが正しいと思われる。Pythonでこう書く。 from itertools import * import sys def e007(N): primes = [2] def is_…

JuliaでProject Euler(6)

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を^に充てていた…