ゲーム HP。
Almagest -Overture-
以下よりダウンロードする。
「Almagest -Overture-」ターン制SFシミュレーションゲーム - 窓の杜
lzh ファイルは Linux ではそのままでは解答できないので、ここでは lhasa を入れてみる。
$ sudo apt install lhasa
これで解凍できる。ver 3.04 の差分フォルダもダウンロードした場合は、手作業で差分ファイルを差し替える（参照）。
実行はふつうに
$ wine Almagest-1.exe
でよい。特にインストールとかはされない。
Linux Mint 19, wine-3.0 で動作確認。
※参考
Almagest -Overture- - Wikipedia
Almagestとは (アルマゲストとは) [単語記事] - ニコニコ大百科
Almagest Wiki - Front Page
以前に郵便局の「はがきデザインキット」を Ubuntu にインストールする記事（参照）を書いたのですが、その手順が古くなったので再挑戦です。
まずは Wine が使えるか調べます。「Wine」とは Linux で Windows のソフトを動かすためのアプリです。
$ wine --version Command 'wine' not found, but can be installed with: sudo apt install wine sudo apt install wine-development
というわけで入っていないので、表示されたとおりにやります。
$ sudo apt update $ sudo apt install wine-stable
あとで必要なのでやっておきます。
$ sudo apt install samba $ sudo apt install winbind
Wine がインストールされているか確認します。
$ wine --version wine-3.18 (Ubuntu 3.18-2)
このままだと文字化けします。なので
$ sudo apt install winetricks $ winetricks allfonts
を実行します（参照）。終了後、
$ winecfg
で文字化けがなければ OK です。これで Wine のインストールが完了しました。
つぎに Abode Air をインストールします。ここから「手順1」は「Windows」、「手順2」は「Adobe AIR 31.0 for Win64」を選択し、「今すぐダウンロード」をクリックします。念のため
$ sudo apt install mono-complete
をしておいてから、ダウンロードした exe ファイルを
$ wine AdobeAIRInstaller.exe
で実行。インストーラーがうまく働いていないように見えますが、フリーズ後に [Ctrl] + [C] をして（うまくいかなければプロセスを終了させる）上記コマンドを再実行すると、インストール済の表示が出れば OK です。
最後にここから「はがきデザインキット」をダウンロード。zip ファイルを解凍して design_kit.air を右クリック、[他のアプリケーションで開く]→[Adobe AIR Application Installer] を選択して実行すると、インストールされる筈です。お疲れ様でした！
AIZU ONLINE JUDGE: Programming Challenge
def measure(object, weight, result = []) return result.join(" ") if weight.zero? result.unshift(weight) if (object / weight).nonzero? measure(object % weight, weight / 2, result) end $<.readlines.map(&:to_i).each {|ob| puts measure(ob, 512)}
rectangle = lozenge = 0 $<.readlines.map {|l| l.split(",").map(&:to_i)}.each do |a, b, c| rectangle += 1 if a * a + b * b == c * c lozenge += 1 if a == b end puts rectangle, lozenge
def try(balls, b ,c) return 1 if balls.empty? nxt = balls.first bl = balls.drop(1) if nxt > b and nxt > c try(bl, nxt, c) + try(bl, b, nxt) elsif nxt > b try(bl, nxt, c) elsif nxt > c try(bl, b, nxt) else 0 end end $<.gets.to_i.times do balls = $<.gets.split.map(&:to_i) puts try(balls.drop(1), balls.first, 0).nonzero? ? "YES" : "NO" end
読み込みに readlines を使ったらエラーが出る。gets を使ったコードに替えたら正解になった。非本質的なところで延々と悩まされた。
$<.readlines.map {|l| l.split(",").map(&:to_i)}.each do |given| ls = given.first(10) v1, v2 = given.last(2) s = Rational(v1 * ls.sum, v1 + v2) l = 0 ls.each_with_index do |ln, i| next if s > (l += ln) puts i + 1 break end end
$<.readlines.map {|l| l.split(",").map(&:to_r)}.each do |given| f = (given + given.first(4)).each_slice(2).each_cons(3).map do |a, b, c| (c[0] - a[0]) * (b[1] - a[1]) - (c[1] - a[1]) * (b[0] - a[0]) > 0 end puts((f.all? or f.none?) ? "YES" : "NO") end
L = 8 table = [["11", "11"], ["1", "1", "1", "1"], ["1111"], ["01", "11", "10"], ["110", "011"], ["10", "11", "01"], ["011", "110"]] table.map! {|pt| [pt.size, l = pt.first.length, pt.join("0" * (L - l))]} $<.readlines.chunk {|l| !!l.match(/^\d/) || nil} .map {|a| a.last.map(&:chomp).join}.each do |field| table.each_with_index do |ary, k| y, n, pt = ary (L + 1 - y).times do |i| (L + 1 - n).times do |j| puts "ABCDEFG"[k] if field[i * L + j, pt.length] == pt end end end end
given = $<.readlines.map {|l| l.chomp.chars.map(&:to_i)} yoko = 0.step(8, 2).map {|i| given[i]} tate = 1.step(8, 2).map {|i| given[i]}.transpose dirs = "LRUD" go = nil route = "" f = false get_yoko = ->(x, y, dir) { if dir == 0 if tate[x][y] == 1 go.(x, y, 3) elsif x > 0 and yoko[y][x - 1] == 1 go.(x, y, 0) elsif y > 0 and tate[x][y - 1] == 1 go.(x, y, 2) else go.(x, y, 1) end else if y > 0 and tate[x][y - 1] == 1 go.(x, y, 2) elsif x <= 3 and yoko[y][x] == 1 go.(x, y, 1) elsif tate[x][y] == 1 go.(x, y, 3) else go.(x, y, 0) end end } get_tate = ->(x, y, dir) { if dir == 2 if x > 0 and yoko[y][x - 1] == 1 go.(x, y, 0) elsif y > 0 and tate[x][y - 1] == 1 go.(x, y, 2) elsif yoko[y][x] == 1 go.(x, y, 1) else go.(x, y, 3) end else if x <= 3 and yoko[y][x] == 1 go.(x, y, 1) elsif y <= 3 and tate[x][y] == 1 go.(x, y, 3) elsif x > 0 and yoko[y][x - 1] == 1 go.(x, y, 0) else go.(x, y, 2) end end } go = ->(x, y, dir) { return if x.zero? and y.zero? and f f = true route += dirs[dir] if dir <= 1 get_yoko.(x + dir * 2 - 1, y, dir) else get_tate.(x, y + dir * 2 - 5, dir) end } go.(0, 0, 1) puts route
何だか全然よくないコード。もっと考えたい。
def same_numbers(ary, result = []) return result.sort if ary.empty? a = ary.first co = ary.count(a) result << co if co > 1 same_numbers(ary - [a], result) end $<.readlines.map {|l| l.split(",").map(&:to_i)}.each do |hand| puts case same_numbers(hand) when [4] then "four card" when [2, 3] then "full house" when [3] then "three card" when [2, 2] then "two pair" when [2] then "one pair" else hand.sort! if hand.sum == (hand.first + 2) * 5 or hand == [1, 10, 11, 12, 13] "straight" else "null" end end end
table = {I: 1, V: 5, X: 10, L: 50, C: 100, D: 500, M: 1000, nil => 0}
count = ->(roman, number = 0) {
return number if roman.empty?
a, b = table[roman.first], table[roman[1]]
number += if a >= b
r = roman.drop(1)
a
else
r = roman.drop(2)
b - a
end
count.(r, number)
}
$<.readlines.map(&:chomp).each {|roman| puts count.(roman.chars.map(&:to_sym))}
[1] pry(main)> (1..4).map {|i| i + 3} => [4, 5, 6, 7]
これと
[2] pry(main)> (1..4).map(&->(i) {i + 3}) => [4, 5, 6, 7]
は同じ。引数での & は Proc をブロックに変換するから。（正確にはさらにそれを暗黙に .call() している。）
では、
[3] pry(main)> (1..4).map(&3) TypeError: wrong argument type Integer (expected Proc)
はもちろんエラーになるよね。でも、この &3 のとき、3 は Proc でないので、暗黙に 3 を to_proc しようとしている。それを示してみよう。
Integer クラスにこうモンキーパッチしてみる。
[4] pry(main)> class Integer [4] pry(main)* def to_proc [4] pry(main)* ->(i){i + self} [4] pry(main)* end [4] pry(main)* end => :to_proc
Integer を Proc化するのである。すると、
[5] pry(main)> (1..4).map(&3) => [4, 5, 6, 7]
おお、先ほどと同じだ。つまり、ここでは暗黙に 3 を to_proc しているのである。うーん、すごいですなあ。
つまり、オブジェクトに to_proc を定義しておくと、このような遊び（？）ができるわけです。可読性がなにですが。
AIZU ONLINE JUDGE: Programming Challenge
$<.readlines.drop(1).map {|a| a.split.map(&:to_r)}.each do |x1, y1, x2, y2, x3, y3, x4, y4| puts((x2 - x1) * (y4 - y3) == (x4 - x3) * (y2 - y1) ? "YES" : "NO") end
単純な問題なのに、自分の解き方ではどうしてもダメだったので、他の人のを参考に。to_f じゃなくて to_r がミソなのかなあ。
while (n = $<.gets.to_i).nonzero? given = (1..n).map {$<.gets.to_i} max = -Float::INFINITY n.times do |i| sum = 0 (i...n).each do |j| sum += given[j] max = sum if sum > max end end puts max end
$<.readlines.drop(1).map {|a| a.split.map(&:to_f)}.each do |xa, ya, ra, xb, yb, rb| l = Math.sqrt((xb - xa) ** 2 + (yb - ya) ** 2) r = ra - rb puts case when l < r then 2 when l < -r then -2 when l > ra + rb then 0 else 1 end end
$<.readlines.map(&:to_r).each do |v| puts((1 + 1/98r * v ** 2).ceil) end
$<.readlines.map {|a| a.split.map(&:to_i)}.each_slice(2) do |a, b| a1, b1 = [], [] hit = 0 a.each_index do |i| if a[i] == b[i] hit += 1 else a1 << a[i] b1 << b[i] end end blow = a1.size - (a1 - b1).size puts "#{hit} #{blow}" end
L = 10 table = [a = [[0, 0], [0, -1], [1, 0], [0, 1], [-1, 0]], b = a + [[1, -1], [1, 1], [-1, 1], [-1, -1]], b + [[0, -2], [2, 0], [0, 2], [-2, 0]]] field = Array.new(L) {Array.new(L, 0)} set = ->(x, y) { return if x < 0 or x >= L or y < 0 or y >= L field[y][x] += 1 } $<.readlines.map {|l| l.split(",").map(&:to_i)}.each do |x, y, s| table[s - 1].each {|dx, dy| set.(x + dx, y + dy)} end f = field.flatten puts f.count(0) puts f.max
require 'date' table = %w(Sunday Monday Tuesday Wednesday Thursday Friday Saturday) loop do month, day = $<.gets.split.map(&:to_i) break if month.zero? puts table[Date.new(2004, month, day).wday] end
field = Array.new(101, 0) $<.readlines.map(&:to_i).each {|n| field[n] += 1} m = field.max field.each_with_index {|n, i| puts i if m == n}
counts = Hash.new(0) max = [0, nil] $<.gets.split.map(&:downcase).each do |word| counts[word] += 1 l = word.length max = [l, word] if l > max.first end h = counts.invert puts "#{h[h.keys.max]} #{max.last}"
loop do n, s = $<.gets.split.map(&:to_i) break if n.zero? and s.zero? puts [*0..9].combination(n).map {|numbers| numbers.sum == s}.count(true) end
RMagick に関して次のエラーが出た。Ubuntu 18.10, Ruby 2.3.4。
/home/tomoki/.rbenv/versions/2.3.4/lib/ruby/gems/2.3.0/gems/rmagick-2.16.0/lib/rmagick_internal.rb:12:in `require': libMagickCore-6.Q16.so.3: cannot open shared object file: No such file or directory - /home/tomoki/.rbenv/versions/2.3.4/lib/ruby/gems/2.3.0/gems/rmagick-2.16.0/lib/RMagick2.so (LoadError)
ここにあるように
$ gem pristine rmagick
で直った。
AIZU ONLINE JUDGE: Programming Challenge
given = $<.readlines lines = [*0..given.first.to_i] given.drop(2).map {|x| x.split(",").map(&:to_i)}.each do |a, b| lines[a], lines[b] = lines[b], lines[a] end puts lines.drop(1)
$<.readlines.each do |l| x1, y1, x2, y2, x3, y3, xp, yp = l.split.map(&:to_f) xa, ya = xp - x1, yp - y1 xb, yb = x3 - x1, y3 - y1 xc, yc = x2 - x3, y2 - y3 r = xb * yc - xc * yb s = (yc * xa - xc * ya) / r u = (xb * ya - yb * xa) / r t = u / s puts((0 < s and s < 1 and 0 < t and t < 1) ? "YES" : "NO") end
stack = [] while (n = $<.gets) n = n.to_i if n.zero? puts stack.pop else stack << n end end
L = 600 $<.readlines.map(&:to_i).each do |d| puts (1..L / d - 1).map {|i| (i * d) ** 2 * d}.sum end
$<.readlines.drop(1).map(&:to_i).each_slice(2) do |a, b| st = (a + b).to_s puts((st.length <= 80) ? st : "overflow") end
x, y = 0, 0 θ = 90 loop do given = $<.gets.split(",").map(&:to_i) break if given == [0, 0] x += given[0] * Math.cos(Math::PI * θ / 180) y += given[0] * Math.sin(Math::PI * θ / 180) θ -= given[1] end puts x.to_i puts y.to_i
def decode(st, n) trans = ->(b) {(a = b - n) < 97 ? a + 26 : a} st.bytes.map {|b| (b.between?(97, 122) ? trans.(b) : b).chr}.join end words = %w(the this that) table = (0..25).map do |i| words.map {|w| w.bytes.map {|b| ((a = b + i) > 122 ? a - 26 : a).chr}.join} end $<.readlines.each do |st| st.chomp! n = 0 table.each_with_index do |ws, i| ws.each {|w| n = i if st.include?(w)} end puts decode(st, n) end
puts $<.gets.split.map(&:to_i).sort {|a, b| b <=> a}.join(" ")
puts (1..$<.gets.to_i).inject(&:*)
puts $<.gets.chomp.upcase
AIZU ONLINE JUDGE: Programming Challenge
9.times do |i| 9.times {|j| puts "#{x = i + 1}x#{y = j + 1}=#{x * y}"} end
puts $<.readlines.map(&:to_i).sort {|a, b| b <=> a}.take(3)
$<.readlines.each do |l| puts Math.log10(l.split.map(&:to_i).sum).to_i + 1 end
$<.readlines.drop(1).each do |l| a, b, c = l.split.map(&:to_i).sort puts((a * a + b * b == c * c) ? "YES" : "NO") end
$<.readlines.each do |l| a, b, c, d, e, f = l.split.map(&:to_i) r = a * e - b * d x = (c * e - b * f) / r.to_f y = (a * f - c * d) / r.to_f x = x.abs if x == 0 y = y.abs if y == 0 printf("%.3f %.3f\n", x, y) end
$<.readlines.each do |l| a, b = l.split.map(&:to_i) puts "#{a.gcd(b)} #{a.lcm(b)}" end
puts $<.gets.chomp.reverse
debt = 10_0000 $<.gets.to_i.times do debt = debt * 1.05 debt = (debt / 1000).ceil * 1000 end puts debt
require 'set' $<.readlines.map(&:to_i).each do |n| s = Set.new l = n / 4 l = (l < 10) ? l : 9 (0..l).each do |a| (a..9).each do |b| (b..9).each do |c| d = n - a - b - c if c <= d and d <= 9 s += [a, b, c, d].permutation.to_a end end end end puts s.size end
これで 0.28秒。
$<.readlines.map(&:to_i).each do |n| co = 0 10.times do |a| 10.times do |b| 10.times do |c| 10.times do |d| co += 1 if a + b + c + d == n end end end end puts co end
これで 0.09秒。わざわざ工夫しないほうが速かった。
$<.readlines.map(&:to_i).each do |n| ar = (0..n).to_a 2.upto(Math.sqrt(n).to_i) do |i| next if ar[i].zero? 2.upto(n / i) {|j| ar[i * j] = 0} end co = 0 ar[2..-1].each {|i| co += 1 if i.nonzero?} puts co end
4.04秒もかかってしまった。
N = 999_999 ar = [*0..N] 2.upto(Math.sqrt(N).to_i) do |i| next if ar[i].zero? 2.upto(N / i) {|j| ar[i * j] = 0} end $<.readlines.map(&:to_i).each do |n| co = 0 ar[2..-1].each do |i| break if i > n co += 1 if i.nonzero? end puts co end
よく考えたらその都度ふるいを実行することはなかった。これでも 2.5秒。
$<.readlines.drop(1).each do |l| x1, y1, x2, y2, x3, y3 = l.split.map(&:to_f) a = x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2) b1 = x1 * x1 + y1 * y1 b2 = x2 * x2 + y2 * y2 b3 = x3 * x3 + y3 * y3 x = (b1 * (y2 - y3) + b2 * (y3 - y1) + b3 * (y1 - y2)) / (2 * a) y = (b1 * (x3 - x2) + b2 * (x1 - x3) + b3 * (x2 - x1)) / (2 * a) r = Math.sqrt((x - x1) ** 2 + (y - y1) ** 2) printf("%.3f %.3f %.3f\n", x, y, r) end
marginalia.hatenablog.com
marginalia.hatenablog.com続きです。
引き続き
「コマ大数学科」に挑む
このサイトから問題を拝借いたします（ありがとうございます！）
問題：
http://www.geocities.jp/tfujisaki2006/sugaku/komadai0912.html#koma2
行列を５０個かけ合わせたとき、できる行列を求めてください。
コード。
require 'matrix' p Matrix[[1, 0.5], [0, 1]] ** 50 #=>Matrix[[1.0, 25.0], [0.0, 1.0]]
まあ素直に。
問題：
http://www.geocities.jp/tfujisaki2006/sugaku/komadai1001.html#koma4
１から１００までの数から適当に２つを選び、その数を足して１引いた数を戻す、という操作を繰り返したとき最後に残る数を答えなさい。
コード。
ar = [*1..100] ar += [ar.shift + ar.shift - 1] while ar.size > 1 puts ar.first #=>4951
これは頭で考えないとつまらないですね。
問題：
http://www.geocities.jp/tfujisaki2006/sugaku/komadai1001.html#koma5
４×４の１６マスに区切られた紙を２人に渡し、それぞれが渡された紙のマスを２つ塗りつぶす。２人の紙を表を上にしてどのように重ねても、塗りつぶされたマスが重ならない確率を求めなさい。
（紙を裏返すことはできないが回転させることはできる。また４隅は重ねるものとする。）
コード。
table = [*0..15].combination(2).to_a co = 0 rotate = ->(a) { a.map {|i| (i % 4) * 4 + 3 - i / 4} } table.repeated_permutation(2) do |p1, p2| f = true consistent = ->(a, b) {f = false unless (a & b).empty?} 4.times {consistent.(p1, p2 = rotate.(p2))} co += 1 if f end puts Rational(co, 14400) #=>89/300
なお、配列 table のサイズは 120 であり、120 × 120 = 14400 です。最初は重複組み合わせで考えていて、これだと正しい確率にならないのですね。
 問題： タケシくんは今年の３月に毎週１回ずつ合計５回デートをします。 デートの曜日は月曜が１回、水曜が２回、土曜が１回、日曜が１回です。 タケシくんがデートする日付の数の和はいくつでしょう。 右のカレンダーは２０１０年３月のカレンダー |
result = [] [*1..31].combination(5) do |days| next unless days.map {|d| d / 7}.sort == [*0..4] next unless days.map {|d| d % 7}.sort == [0, 1, 3, 3, 6] result << days.inject(&:+) end puts result.uniq #=>83
例によって brute-force です。というか、
puts 1 + 10 + 17 + 27 + 28 #=>83
でオシマイじゃね？
問題：
http://www.geocities.jp/tfujisaki2006/sugaku/komadai1006.html#koma1
各桁の数字（0でない）が相異なる３桁の正の整数ｎがある。
ｎの各数字を並べてできる、６つの数の最大公約数をｇとする。
ｇとして考えられる最大の値を求めよ。
コード。
max = 0 [*1..9].combination(3) do |nums| x = nums.permutation.map {|n| n.join.to_i}.inject(&:gcd) max = x if x > max end puts max #=>18
Ruby っぽいコードになりました。
エマープ (emirp) 素数…素数の中で数字を逆に書いても素数になる数のこと。
http://www.geocities.jp/tfujisaki2006/sugaku/komadai1010.html#koma1
たとえば「１３と３１」「３７と７３」などがエマープ素数である。
「emirp」は「prime：素数」を逆にしたもの。 ただし、逆に書いても同じになる素数（１０１など）は含まれない。
問題：３ケタのエマープ素数を３つ答えなさい。
コード。
def eratosthenes(n) ar = [*0..n] 2.upto(Math.sqrt(n).to_i) do |i| next if ar[i].zero? 2.upto(n / i) {|j| ar[i * j] = 0} end ar[2..-1].reject {|x| x.zero?} end table = eratosthenes(999).select {|x| x >= 100} result = table.map do |num| r_num = num.to_s.reverse.to_i next if num >= r_num table.include?(r_num) ? [num, r_num] : nil end.compact p result
結果。
[[107, 701], [113, 311], [149, 941], [157, 751], [167, 761], [179, 971], [199, 991], [337, 733], [347, 743], [359, 953], [389, 983], [709, 907], [739, 937], [769, 967]]
これはプログラミング向きの問題ですね。「エラトステネスの篩」で３桁の素数をすべて求めてから解いています。
問題：
http://www.geocities.jp/tfujisaki2006/sugaku/komadai1101.html#koma2
すべての自然数を順番につなげて書いていくとき、１万個目に書かれる 数字はいくつでしょう。
１，２，３，…と順番に書いていく。９までは一桁の数であるが、次の １０から２桁になるため、１０個目の数は「１」、１１個目の数は「０」 になる。
コード。
N = 10000 st = "" 1.step do |i| st += i.to_s if st.length >= N puts st[N - 1] #=>7 break end end
問題： ＡくんとＢくんが図のア～ケ９つのマスに１，３，４～１０の数字を交互に一つずつ入れていく。 ルール このとき先手のＡくんは、どのマス目にどの数字を入れると良いでしょうか。 |
|
package main import "fmt" func delete(numbers []int, n int) (result []int) { for _, x := range numbers { if x == n {continue} result = append(result, x) } return } func try(numbers []int, table []int, turn bool, f func(int, ...int)) { for _, n := range numbers { for i, _ := range table { if table[i] != 0 {continue} table[i] = n score := min_max(delete(numbers, n), table, !turn) table[i] = 0 f(score, i, n) } } } func min_max(numbers []int, table []int, turn bool) int { if len(numbers) == 0 { s1 := table[0] + table[1] + table[2] + table[6] + table[7] + table[8] s2 := table[0] + table[3] + table[6] + table[2] + table[5] + table[8] if s1 > s2 {return 1} else {return -1} } if turn { max := -10 f := func(score int, a ...int) { if score > max {max = score} } try(numbers, table, turn, f) return max } else { min := 10 f := func(score int, a ...int) { if score < min {min = score} } try(numbers, table, turn, f) return min } } func main() { f := func(score int, a ...int) {if score == 1 { fmt.Println([]int{score, a[0], a[1]}) }} try([]int{1, 3, 4, 5, 6, 7, 8, 9, 10}, make([]int, 9), true, f) }
結果。
$ go build komadai1.go $ time ./komadai1 [1 3 1] [1 5 1] real 2430m31.749s user 2472m32.886s sys 10m37.645s
つまり、ここでの回答どおり、「エまたはカに 1 を入れる」となりました。しかし Go で 40 時間もかかるとは…。
marginalia.hatenablog.com続きです。
引き続き
「コマ大数学科」に挑む
このサイトから問題を拝借いたします（ありがとうございます！）
問題：
http://www.geocities.jp/tfujisaki2006/sugaku/komadai0809.html
１ｍ間隔で一列に１３本並んだ旗をどこか１箇所の旗のところに集めたい。１度に１本の旗しか持てないときに最短の移動距離で集めるためにはどの旗に何ｍの移動距離で集めれば良いでしょう。ただし１番目の旗の場所をスタート地点とする。
コード。
N = 13 def try(i) length = i - 1 (2..N).each do |j| length += (j - i).abs * 2 end length end p (1..N).map {|i| [i, try(i)]}.sort_by(&:last).first #=>[7, 78]
これはプログラミングで解くような問題ではないですね。簡単すぎる。
 問題： 図の○の中に１から７までの数字を入れ、直線で結ばれた３つの数字の和（全部で５列ある）が全て等しくなるとき、赤い丸に入る数字と等しい和を答えなさい。 |
require 'set' table = [[4, 5, 6], [0, 1, 4], [0, 2, 5], [0, 3, 6]] answer = Set.new [*1..7].permutation.each do |nominee| sum = nominee[1] + nominee[2] + nominee[3] catch(:jump) do table.each do |positions| throw(:jump) unless positions.map {|i| nominee[i]}.inject(&:+) == sum end answer << [nominee.first, sum] end end puts answer #=>#<Set: {[4, 12]}>
これも、わざわざプログラミングで解かなくても…という感じ。いや、結構むずかしいかな。
問題：
http://www.geocities.jp/tfujisaki2006/sugaku/komadai0811.html
１から１億までの数字を書いたときに現れる数字の全ての和を求めなさい。
一見 Ruby で解くのは容易そうである。こんな風に。
answer = 0 (1..1_0000_0000).each do |n| answer += n.to_s.chars.map(&:to_i).inject(&:+) end puts answer
しかしこれは、実際は（時間がかかりすぎるので）フリーズします。なので、少し考える必要がある。n 桁以下のすべての数に現れる数字の和を sum(n) とおくと、漸化式
が sum(1) = 1 + 2 + … + 9 = 45 として成立するので（理由は考えてみよう。ヒントは最上位とそれ以外を分ける）、こんなコードが得られる。
def sum(n) return 45 if n == 1 sum(1) * 10 ** (n - 1) + 10 * sum(n - 1) end puts 1 + sum(8) #=>3600000001
つまり、答えは 36億1 ですね。これなら 100億まででも 1000兆まででも簡単である。
なお、上の漸化式は一般項を求めることができて、
となります。ヒントは漸化式の両辺を 10 の n - 1 乗で割るとよい。
問題：
１から６までのトランプ２４枚を使い、２人が交互に１枚ずつ取り、２人の取ったカードの合計を先に３１にした方が勝ち、というゲームをする。（31を超えたら負け。）このゲームで先手が勝つためには始めに何を取ればよいか。
http://www.geocities.jp/tfujisaki2006/sugaku/komadai0811.html
これはむずかしい。手作業で解くのはとてもではないがつらい。
しかしプログラミングでもかなりむずかしい感じである。「min-max 法」でやってみる。コード。
Goal = 31 initial_cards = (1..6).flat_map {|i| [i] * 4} def delete(cards, n) idx = cards.find_index(n) cards[0...idx] + cards[idx + 1..-1] end def min_max(cards, turn, sum) return (turn ? -10 : 10) if sum == Goal return (turn ? 10 : -10) if sum > Goal children = cards.uniq if turn max = -100 children.each do |ch| score = min_max(delete(cards, ch), !turn, sum + ch) max = score if score > max end max else min = 100 children.each do |ch| score = min_max(delete(cards, ch), !turn, sum + ch) min = score if score < min end min end end p (1..6).map {|i| [i, min_max(delete(initial_cards, i), false, i)]}
先手の手番で turn = true になります。勝った方に 10 ポイント、負けた方に -10 ポイントの評価をしています。最初に先手の手番を与えているので、次は後手（turn = false）になります。
結果。
$ time ruby solve.rb [[1, 10], [2, 10], [3, -10], [4, -10], [5, 10], [6, -10]] real 4m40.226s user 4m40.188s sys 0m0.004s
よって、先手が勝利するのは 1, 2, 5 のいずれかを選んだときになります。自分の環境で 4分40秒ほどかかっています。
パフォーマンスを改善してみる。新しい配列を生成しないように、データ構造を書き換えます。コード。
N = 6 Goal = 31 initial_cards = [4] * N def min_max(cards, turn, sum) return (turn ? -10 : 10) if sum == Goal return (turn ? 10 : -10) if sum > Goal if turn max = -100 N.times do |i| next if cards[i].zero? cards[i] -= 1 score = min_max(cards, !turn, sum + i + 1) cards[i] += 1 max = score if score > max end max else min = 100 N.times do |i| next if cards[i].zero? cards[i] -= 1 score = min_max(cards, !turn, sum + i + 1) cards[i] += 1 min = score if score < min end min end end result = [] N.times do |i| initial_cards[i] -= 1 result << [i + 1, min_max(initial_cards, false, i + 1)] initial_cards[i] += 1 end p result
結果。
$ time ruby solve.rb [[1, 10], [2, 10], [3, -10], [4, -10], [5, 10], [6, -10]] real 1m24.899s user 1m24.876s sys 0m0.024s
3.3 倍ほど高速化しました。
問題：
それぞれ１から８までの数字が書かれた８枚のカードをシャッフルして、次の条件で順番に赤と青の箱に入れていく。１枚目は赤の箱に入れる。
２枚目以降は
それまでで出たカードのいずれよりも大きい数字ならば赤の箱に入れる。
それ以外なら青の箱に入れる。全てのカードを入れ終えたとき、青にカードが１枚だけ入っている確率を求めよ。
http://www.geocities.jp/tfujisaki2006/sugaku/komadai0812.html#koma2
コード。
co = 0 [*1..8].permutation do |deck| red, blue = [deck.shift], [] while (card = deck.shift) if card > red.max red << card else blue << card end end co += 1 if blue.size == 1 end puts Rational(co, 40320) #=>1/1440
簡単ですね。なお、8! = 40320 です。
問題： 上の図のような４×５の十畳分の部屋に 畳を１０枚敷き詰める方法は何通りあるでしょう。 （上下、左右にひっくり返すことで変わる敷き詰め方は 別の敷き詰め方とします）
initial_room = Array.new(20, false) co = 0 try = ->(room) { i = room.find_index(false) if i if i % 4 != 3 and !room[i + 1] room[i] = room[i + 1] = true try.(room) room[i] = room[i + 1] = false end if i < 16 and !room[i + 4] room[i] = room[i + 4] = true try.(room) room[i] = room[i + 4] = false end else co += 1 end } try.(initial_room) puts co #=>95
左上隅から順に畳を敷き詰めていきます。深さ優先探索で求めています。
問題：
魔法Ａ，魔法Ｂを使える魔法使いがいます。魔法Ａは「全てのイチゴ」それぞれを「イチゴとバナナ」に変える。
魔法Ｂは「全てのバナナ」それぞれを「イチゴとバナナ」に変える。今イチゴとバナナが１個ずつある状態から魔法Ａ，魔法Ｂを何回か かけたところイチゴが１５個、バナナが８７７個になった。二つの 魔法は合計何回かけたでしょう。
http://www.geocities.jp/tfujisaki2006/sugaku/komadai0903.html#koma1
コード。
s, b = 15, 877 sn = bn = 0 A = ->{b -= s; sn += 1} B = ->{s -= b; bn += 1} until s == 1 and b == 1 (s < b) ? A.() : B.() end puts sn + bn #=>66
逆から考えるとよいですね。たとえば A の魔法をかける前は、イチゴの数だけバナナが少なくなっています（イチゴの数は変わりません）。なので、魔法をかけたあとのバナナの方がイチゴより数が大きくないと、A の魔法をかけることはできません。
問題：
左右２列に８個ずつの穴がある靴に靴ひもを通すときの最短の長さを求めよ。
ただし、それぞれの穴から必ず反対の列にひもを渡すことが必要である。（渡す穴の一方が同じ列、他方が反対の列というのでもよい。）左右の穴の間隔は２、各列の穴の間隔は１とする。また結び目までの長さも含める。
http://www.geocities.jp/tfujisaki2006/sugaku/komadai0902.html#koma2
非常にむずかしい問題で、番組で正解が出たのが驚きです。
コード。
N = 8 initial_holes = Array.new(N * 2, false) @min = Float::INFINITY def distance(a, b) a, b = b, a if a > b return b - a if (a < N and b < N) or (a >= N and b >= N) b -= N Math.sqrt(4 + (a - b) ** 2) end def try(from, before, holes, length) return if @min < length if holes.all? length += distance(@start, from) @min = length if length < @min else holes.each_index do |to| next if holes[to] or (from < N and before < N and to < N) or (from >= N and before >= N and to >= N) holes[to] = true try(to, from, holes, length + distance(from, to)) holes[to] = false end end end (0...(N * 1/2r).ceil).each do |i| initial_holes[i] = true try(@start = i, N, initial_holes, 0) initial_holes[i] = false end puts @min
結果。
$ time ruby solve.rb 25.41640786499874 real 45m24.468s user 45m24.376s sys 0m0.032s
正解が出ていますが、45分もかかりました。アルゴリズムとしてはそれほどむずかしいことをやっているわけではありません。
これは是非元記事を参照して頂きたいですね。
問題： ５枚のカードの表（白）と裏（黒）にそれぞれ０から９までの数字を一つずつかかれています。この５枚のカードを横一列に並べて以下の条件が成り立つとき、最初に見えていた（表５つ）の数字を答えなさい。
| ５枚とも表の状態 |  | 見えている５つの数字の合計は１９ |
| 左の３枚を裏返す |  | 見えている５つの数字の合計は２０ |
| 右の３枚を裏返す |  | 見えている５つの数字の合計は３５ |
| 左の４枚を裏返す |  | 見えている５つの数字の合計は１１ |
| 右の４枚を裏返す |  | 見えている５つの数字の合計は３１ |
table1 = [[0, 1, 2, 3, 4], [5, 6, 7, 3, 4], [5, 6, 2, 8, 9], [0, 1, 7, 3, 9], [0, 6, 2, 8, 4]] table2 = [19, 20, 35, 11, 31] [*0..9].permutation.each do |cards| f = table1.map.with_index do |a, i| a.map {|b| cards[b]}.inject(&:+) == table2[i] end.all? p cards[0, 5] if f end
結果。
$ time ruby solve.rb [3, 1, 9, 2, 4] real 0m23.629s user 0m23.612s sys 0m0.016s
単純な brute-force なので、時間がかかっています。
問題：
http://www.geocities.jp/tfujisaki2006/sugaku/komadai0906.html#koma1
たろうくんは１から順に１，２，３…とある数までを黒板に書きました。
じろうくんはその中の１個の数を消してしまいました。すると残りの数の平均は５９０／１７になりました。
じろうくんの消した数はいくつですか？
コード。
class Rational def integer?() (self - to_i).zero? end end 2.step do |i| x = Rational(i * (i + 1), 2) - Rational(590 * (i - 1), 17) if 0 < x and x <= i and x.integer? p [x.to_i, i] #=>[55, 69] break end end
つまり答えは 55。簡単ですね。
問題： 約数の個数が２８個ある最小の自然数ｎを求めなさい。
http://www.geocities.jp/tfujisaki2006/sugaku/komadai0906.html#koma3
コード。
def divisors(n) (1..n).select {|i| (n % i).zero?} end 1.step do |i| if divisors(i).size == 28 puts i #=>960 break end end
これも極簡単ですね。
 問題：ある区画に２５個のビルが５行５列の正方形状に並んで建っています。 右の図は真上から見たビルを表しています。 １．ビルは１～５階建てのいずれか。 ２．同じ行、同じ列でビルの階数は全て異なる。 ３．矢印の数字はその方向から見えるビルの個数。（高いビルの奥にある低いビルは見えないという意味です。） 以上の条件を満たすとき、中央のマス目のビルは何階でしょう？ |
N = 5 def product(n, f = true) result = [] [*1..N].permutation do |buildings| copied = buildings.dup buildings.reverse! unless f visible = [] loop do visible << (a = buildings.shift) break if buildings.empty? buildings = buildings.drop_while {|b| a > b} end result << copied if visible.compact.size == n end result end lines1 = product(3) lines2 = lines1 & product(2, false) lines3 = product(4) def set_field(field, n, line) setted = field.dup N.times do |i| pos = yield(n, i) return nil unless setted[pos].zero? or setted[pos] == line[i] setted[pos] = line[i] end setted end def set_col(field, n, line) set_field(field, n, line) {|n, i| n + N * i} end def set_row(field, n, line) set_field(field, n, line) {|n, i| i + N * n} end field = Array.new(N * N, 0) selected_fields = [] lines2.each do |l1| fld1 = set_col(field, 1, l1) lines1.each do |l2| next unless (fld2 = set_col(fld1, 3, l2)) lines3.each do |l3| next unless (fld3 = set_col(fld2, 4, l3.reverse)) lines3.each do |l4| next unless (fld4 = set_row(fld3, 1, l4.reverse)) selected_fields += lines3.map {|l5| set_row(fld4, 3, l5)}.compact end end end end def settable?(field, pos) check = ->(row) { s = row.reject(&:zero?) s.size == s.uniq.size } x, y = pos % N, pos / N row = field[y * N , N] col = x.step(N * N - 1, N).map {|i| field[i]} return false unless check.(row) and check.(col) return true if row.include?(0) or col.include?(0) return false if row.sort != [*1..N] return false if col.sort != [*1..N] true end def doit(field) pos = field.find_index(0) if pos new_field = field.dup N.times do |i| new_field[pos] = i + 1 doit(new_field) if settable?(new_field, pos) end else pp field.each_slice(N).to_a end end selected_fields.each {|f| doit(f)}
結果。
[[4, 1, 3, 2, 5], [5, 4, 1, 3, 2], [3, 5, 2, 1, 4], [1, 2, 4, 5, 3], [2, 3, 5, 4, 1]]
つまり答えは「2」です。プログラミングで解かない方が簡単かも知れませんね。解けるけれど、プログラミングには苦手な感じの問題です。
問題：
http://www.geocities.jp/tfujisaki2006/sugaku/komadai0907.html#koma4
３辺の長さが整数の直角三角形があります。３辺のうち２つの辺の長さが素数であり、３辺の長さの和が１３２のとき、３辺のそれぞれの長さを求めなさい。
コード。
require 'prime' L = 132 def prime_check(*args) args.combination(2) do |i, j| return true if Prime.prime?(i) and Prime.prime?(j) end false end 1.upto(L / 3) do |a| a.upto(L) do |b| c = L - a - b next unless b < c and c <= L - 2 next unless prime_check(a, b, c) p [a, b, c] if a * a + b * b == c * c #=>[11, 60, 61] end end
簡単ですね。
 問題：右の図の四角の中に１～９の数字をひとつずつ入れ、図の７つの三角形の頂点にある３つの数の和が等しくなるようにしなさい。 （赤の大きさの三角形４つと青の大きさの三角形３つ） |
table = [[0, 2, 3], [1, 4, 5], [3, 4, 6], [6, 7, 8], [0, 1, 6], [2, 4, 7], [3, 5, 8]] [*0..8].permutation do |field| sum = table[0].map {|i| field[i]}.inject(&:+) f = table[1..-1].map do |t| t.map {|i| field[i]}.inject(&:+) == sum end.all? p field if f end
結果。
[1, 6, 9, 5, 2, 7, 8, 4, 3] [1, 8, 9, 5, 4, 3, 6, 2, 7] [1, 9, 6, 8, 2, 4, 5, 7, 3] [1, 9, 8, 6, 4, 2, 5, 3, 7] [2, 7, 9, 4, 5, 3, 6, 1, 8] [2, 9, 7, 6, 5, 1, 4, 3, 8] [3, 4, 7, 5, 2, 9, 8, 6, 1] [3, 7, 4, 8, 2, 6, 5, 9, 1] [3, 7, 8, 4, 6, 2, 5, 1, 9] [3, 8, 7, 5, 6, 1, 4, 2, 9] [4, 3, 9, 2, 5, 7, 8, 1, 6] [4, 9, 3, 8, 5, 1, 2, 7, 6] [6, 1, 7, 2, 5, 9, 8, 3, 4] [6, 7, 1, 8, 5, 3, 2, 9, 4] [7, 2, 3, 5, 4, 9, 6, 8, 1] [7, 3, 2, 6, 4, 8, 5, 9, 1] [7, 3, 6, 2, 8, 4, 5, 1, 9] [7, 6, 3, 5, 8, 1, 2, 4, 9] [8, 1, 3, 4, 5, 9, 6, 7, 2] [8, 3, 1, 6, 5, 7, 4, 9, 2] [9, 1, 2, 4, 6, 8, 5, 7, 3] [9, 1, 4, 2, 8, 6, 5, 3, 7] [9, 2, 1, 5, 6, 7, 4, 8, 3] [9, 4, 1, 5, 8, 3, 2, 6, 7]
答えは 24とおりあります。これもブログラミングだと簡単ですね。単純な brute-force ですが。
問題：
http://www.geocities.jp/tfujisaki2006/sugaku/komadai0911.html#koma2
ある線分の２等分点、３等分点、４等分点と順に新しい等分点にだけ印をつけていきます。１５等分点に印を付けたとき、新たに増える印の数を答えなさい。
コード。
require 'set' set = Set.new generate = ->(n) { (1...n).map {|i| Rational(i, n)} } 2.upto(14) {|i| set += generate.(i)} n = set.size set += generate.(15) puts set.size - n #=>8
問題：
http://www.geocities.jp/tfujisaki2006/sugaku/komadai0911.html#koma4
１辺の長さ１の正方形のタイル８００枚を隙間なく並べて縦２５、横３２の長方形を作ります。
この長方形の対角線１本が通過するタイルの枚数を求めなさい。
コード。
W, H = 32, 25 def y(x) Rational(H * x, W) end def cross?(px, py) y1 = y(px) return true if py < y1 and y1 < py + 1 y1 = y(px + 1) return true if py < y1 and y1 < py + 1 false end co = 0 0.upto(H - 1) do |y| 0.upto(W - 1) do |x| co += 1 if cross?(x, y) end end puts co #=>56
Ruby が分数を標準で扱えるのが効いていますね。