REAPERメモ
https://www.reaper.fm/download.php
Download
https://github.com/Phroneris/ReaperJPN-Phroneris/wiki
日本語化。
音が出ない:Actions→Options: Preferences→Audio SystemをPluseAudioに
Ruby でモナドの一例
m-hiyama.hatenablog.comこれを Ruby でやってみる。
countup_monad.rb
class Countup def initialize(value, countup = 0) @value = value @countup = countup end attr_reader :value, :countup def fmap c = yield @value if c.instance_of?(Countup) Countup.new(Countup.new(c.value, @countup + c.countup)) else Countup.new(c, @countup) end end def bind(&bk) fmap(&bk).join end def join value end end def sum_countup5(x, y) Countup.new(x + y, 5) end def length_countup(str) len = str.length Countup.new(len, len) end def countup(n) Countup.new(nil, n) end def minus_count8(n) Countup.new(-n, 8) end
あるいは
class Countup def fmap(&bk) Countup.new(bind(&bk), @countup) end def bind c = yield @value if c.instance_of?(Countup) Countup.new(c.value, @countup + c.countup) else c end end end
実行例。
$ irb irb(main):001:0> require_relative "countup_monad" => true irb(main):002:0> length_countup("Hello, world!").bind { |n| Countup.new(n) } => #<Countup:0x0000556c80efea88 @value=13, @countup=13> irb(main):003:0> Countup.new("Hello, world!").bind { |n| length_countup(n) } => #<Countup:0x0000556c81244238 @value=13, @countup=13> irb(main):004:0> l = length_countup("Hello, world!") => #<Countup:0x0000556c8116e020 @value=13, @countup=13> irb(main):005:0> m = l.bind { |n| sum_countup5(n, 10) } => #<Countup:0x0000556c8100aa80 @value=23, @countup=18> irb(main):006:0> m.bind { countup(2) } => #<Countup:0x0000556c8124c320 @value=nil, @countup=20> irb(main):007:0> l.bind { |n| sum_countup5(n, 10).bind { countup(2)} } => #<Countup:0x0000556c81254e08 @value=nil, @countup=20>
第1例と第2例がそれぞれ右単位元、左単位元。残りが結合法則。
$ irb irb(main):001:0> require_relative "countup_monad" => true irb(main):002:0> a = Countup.new(-8) => #<Countup:0x0000560f814cebe0 @value=-8, @countup=0> irb(main):003:0> b = a.bind(&method(:minus_count8)) => #<Countup:0x0000560f8175a350 @value=8, @countup=8> irb(main):004:0> b.fmap { |n| n ** 2 } => #<Countup:0x0000560f81722ae0 @value=64, @countup=8>
元記事のnoeffect
乃至unit
がCountup.new
に、ext
がbind
に対応している。(元記事の「モナド」の定義はじつはクライスリトリプルの定義だと思う。)
副作用@countup
を隠蔽している。
qiita.comこれにはモナドの遅延評価が実装されている。
kentutorialbook.github.io
ここでの自己関手TはCountupクラス、圏Cは全オブジェクト、自然変換ηはCountup.new
、自然変換μはjoin
に対応する。
ただし、本当はメソッドはすべて「ファーストクラス化」しないといけないのだろうけれど。
IOモナド
io_monad.rb
class IOMonad def initialize(val = nil) @val = val end def self.gets new($stdin.gets) end def self.puts(str) new($stdout.puts(str)) end def fmap IOMonad.new(yield @val) end def bind(&bk) fmap(&bk).join end def join @val end def inspect "IO" end end def reverse(str) IOMonad.new(str.reverse) end
実行例。
$ irb irb(main):001:0> require_relative "io_monad" => true irb(main):002:0> x = IOMonad.gets tokyo => IO irb(main):003:0> y = x.fmap { _1.chomp.upcase } => IO irb(main):004:0> z = y.bind { reverse(_1) } => IO irb(main):005:0> z.bind { IOMonad.puts(_1) } OYKOT => IO irb(main):006:0> y.bind { |str| reverse(str).bind { IOMonad.puts(_1) } } OYKOT => IO
ファーストクラス化してみる。
$ irb irb(main):001:0> require_relative "io_monad" => true irb(main):002:0> reverse = method(:reverse) irb(main):003:0> puts = IOMonad.method(:puts) irb(main):004:0> x = IOMonad.gets tokyo => IO irb(main):005:0> y = x.fmap { _1.chomp.upcase } => IO irb(main):006:0> y.bind(&reverse).bind(&puts) OYKOT => IO irb(main):007:0> y.bind { reverse.(_1).bind(&puts) } OYKOT => IO irb(main):008:0> join = :join.to_proc irb(main):009:0> y.bind(&reverse >> join >> puts) OYKOT => IO
Haskell の「関数型問題解決法」を Ruby で
- 作者:Miran Lipovača
- 発売日: 2012/05/23
- メディア: 単行本(ソフトカバー)
ほぼ忠実な移植。
heathrow_to_London = [ [50, 10, 30], [5, 90, 20], [40, 2, 25], [10, 8, 0] ] make_section = ->(ary) {%i(A B C).zip(ary).to_h} t_sum = ->(path) {path.sum {_1.values[0]}} road_step = ->((path_a, path_b), sct) { time_a = t_sum.(path_a) time_b = t_sum.(path_b) foward_time_to_a = time_a + sct[:A] foward_time_to_b = time_b + sct[:B] cross_time_to_a = time_b + sct[:B] + sct[:C] cross_time_to_b = time_a + sct[:A] + sct[:C] new_path_to_a = if foward_time_to_a <= cross_time_to_a path_a + [{A: sct[:A]}] else path_b + [{B: sct[:B]}, {C: sct[:C]}] end new_path_to_b = if foward_time_to_b <= cross_time_to_b path_b + [{B: sct[:B]}] else path_a + [{A: sct[:A]}, {C: sct[:C]}] end [new_path_to_a, new_path_to_b] } optimal_path = ->(road_system) { best_path_a, best_path_b = road_system.inject([[], []], &road_step) t_sum.(best_path_a) <= t_sum.(best_path_b) ? best_path_a : best_path_b } path = optimal_path.(heathrow_to_London.map(&make_section)) path_string = path.map {_1.keys[0]}.join path_time = t_sum.(path) puts "The best path to take is: " + path_string puts "Time taken: #{path_time}"
結果。
The best path to take is: BCACBBC Time taken: 75
これを見ていると、ここでの関数型プログラミングというのはそれほど特別なものではないな。inject
を使っているくらいか。Ruby でも充分に記述できる。ただ、Haskell の強力な型記述で(ある意味では)自然な書き方になっているのはそうかな。
ちなみに、
heathrow_to_London.map(&make_section) #=>[{:A=>50, :B=>10, :C=>30}, {:A=>5, :B=>90, :C=>20}, {:A=>40, :B=>2, :C=>25}, {:A=>10, :B=>8, :C=>0}] path #=>[{:B=>10}, {:C=>30}, {:A=>5}, {:C=>20}, {:B=>2}, {:B=>8}, {:C=>0}]
である。Haskell のSection
を Hash で表している。
別解
深さ優先探索(DFS)で総当り。
heathrow_to_London = [ [50, 10, 30], [5, 90, 20], [40, 2, 25], [10, 8, 0] ] result = ["", Float::INFINITY] go = ->(from, sections, path = "", time = 0) { if sections.empty? p_re, t_re = result result = [path, time] if t_re > time else (a, b, c), *rest = sections case from when "A" go.("A", rest, path + "A", time + a) go.("B", rest, path + "AC", time + a + c) when "B" go.("A", rest, path + "BC", time + b + c) go.("B", rest, path + "B", time + b) end end } go.("A", heathrow_to_London) go.("B", heathrow_to_London) puts "The best path to take is: " + result[0] puts "Time taken: #{result[1]}"
ABC184
https://atcoder.jp/contests/abc184
A: Determinant
a, b, c, d = readlines.join.split.map(&:to_i)
puts a * d - b * c
B: Quizzes
n, x = gets.split.map(&:to_i) str = gets.chomp str.each_char do |s| case s when "o" x += 1 else x -= 1 if x.nonzero? end end puts x
どう書く
オフラインリアルタイムどう書くの 会場や問題のリスト - 鍋あり谷あり
ポーカー
https://qiita.com/Nabetani/items/cbc3af152ee3f50a822f
Suit = %W(S H D C) Rank = %W(2 3 4 5 6 7 8 9 10 J Q K A) def cards Suit.flat_map {|s| Rank.map {|r| s + r} }.sample(5).join end t = Regexp.compile("[#{Suit.join}]") counted = cards.chars.slice_before(t).map {|a, *b| b.join} .tally.values.sort.reverse ans = if counted[0] == 4 "4K" elsif counted[0] == 3 && counted[1] == 2 "FH" elsif counted[0] == 3 "3K" elsif counted[0] == 2 && counted[1] == 2 "2P" elsif counted[0] == 2 "1P" else "--" end puts ans
別解。
Suit = %W(S H D C) Rank = %W(2 3 4 5 6 7 8 9 10 J Q K A) def cards Suit.flat_map {|s| Rank.map {|r| s + r} }.sample(5).join end t = Regexp.compile("[#{Suit.join}]") counted = cards.chars.slice_before(t).map {|a, *b| b.join} .tally.values.sort.reverse.join ["4", "32", "3", "22", "2", "1"].zip(%W(4K FH 3K 2P 1P --)).each do |c, h| if counted.start_with?(c) puts h break end end
Tick-Tack-Toe
http://nabetani.sakura.ne.jp/hena/1/
class TickTackToe WinPattern = %W(123 456 789 147 258 369 159 357) def initialize(input) @input = input.chars.map(&:to_i) @field = Array.new(10) @turn = 0 #o @ptns = WinPattern.map {|pt| pt.chars.map(&:to_i)} end def solve @input.each do |i| if @field[i] return "Foul : #{output_turn(false)} won." else @field[i] = @turn if settle? return "#{output_turn} won." elsif @field[1..9].all? return "Draw game." else @turn = 1 - @turn end end end end def settle? @ptns.any? do |pt| a = pt.map {|i| @field[i]}.join a == "000" || a == "111" end end def output_turn(t = true) %W(o x)[t ? @turn : 1 - @turn] end def self.solve(input) new(input).solve end end if $0 == __FILE__ data = [79538246, 35497162193, 61978543, 254961323121, 6134278187, 4319581, 9625663381, 7975662, 2368799597, 18652368566, 965715, 38745796, 371929, 758698769, 42683953, 618843927, 36535224, 882973, 653675681, 9729934662, 972651483927, 5439126787, 142583697, 42198637563, 657391482] data.each do |d| puts TickTackToe.solve(d.to_s) end end
二値画像の回転
https://qiita.com/Nabetani/items/9d80de41903775296ca6
class BinaryImageRotation def initialize(input) l, @binary = input.split(":") @l = l.to_i end def solve n = (@l ** 2 / 4.0).ceil * 4 ans = @binary.chars.map {|c| c.to_i(16).to_s(2).rjust(4, "0")} .join[0, @l ** 2].chars.map(&:to_i).each_slice(@l) .to_a.reverse.transpose .join.ljust(n, "0").chars.each_slice(4) .map {|ary| ary.join.to_i(2).to_s(16)}.join "#{@l}:" + ans end def self.exec(input) new(input).solve end end if __FILE__ == $0 require 'minitest/autorun' describe 'BinaryImageRotation' do [ ["3:5b8", "3:de0"], ["1:8", "1:8"], ["2:8", "2:4"], ["2:4", "2:1"], ["2:1", "2:2"], ["3:5d0", "3:5d0"], ["4:1234", "4:0865"], ["5:22a2a20", "5:22a2a20"], ["5:1234567", "5:25b0540"], ["6:123456789", "6:09cc196a6"], ["7:123456789abcd", "7:f1a206734b258"], ["7:fffffffffffff", "7:ffffffffffff8"], ["7:fdfbf7efdfbf0", "7:ffffffffffc00"], ["8:123456789abcdef1", "8:f0ccaaff78665580"], ["9:112233445566778899aab", "9:b23da9011d22daf005d40"] ].each do |input, expect| it input do assert_equal BinaryImageRotation.exec(input), expect end end end end
Bit Tetris
http://nabetani.sakura.ne.jp/hena/ord2/
module BitTetris module_function def solve(input) field = input.split("-").map { _1.to_i(16) } to_be_erased = to_a(field.inject(:&)) field.map { "%02x" % erase(_1, to_be_erased) }.join("-") end def erase(i, to_be_erased) to_a(i).zip(to_be_erased).map { |s, t| t == "1" ? "" : s }.join.to_i(2) end def to_a(i) sprintf("%08b", i).chars end end if __FILE__ == $0 require 'minitest/autorun' describe 'BitTetris' do [ ["ff-2f-23-f3-77-7f-3b", "1f-03-00-1c-0d-0f-06"], ["01", "00"], ["00", "00"], ["7a-4e", "0c-02"], ["56-b6", "08-14"], ["12-12-12", "00-00-00"], ["de-ff-7b", "0a-0f-05"], ["95-be-d0", "05-1e-20"], ["7c-b0-bb", "1c-20-2b"], ["7a-b6-31-6a", "3a-56-11-2a"], ["32-0e-23-82", "18-06-11-40"], ["ff-7f-bf-df-ef", "0f-07-0b-0d-0e"], ["75-df-dc-6e-42", "35-5f-5c-2e-02"], ["62-51-ef-c7-f8", "22-11-6f-47-78"], ["0c-47-8e-dd-5d-17", "04-23-46-6d-2d-0b"], ["aa-58-5b-6d-9f-1f", "52-28-2b-35-4f-0f"], ["ff-55-d5-75-5d-57", "0f-00-08-04-02-01"], ["fe-fd-fb-f7-ef-df-bf", "7e-7d-7b-77-6f-5f-3f"], ["fd-fb-f7-ef-df-bf-7f", "7e-7d-7b-77-6f-5f-3f"], ["d9-15-b5-d7-1b-9f-de", "69-05-55-67-0b-4f-6e"], ["38-15-fd-50-10-96-ba", "18-05-7d-20-00-46-5a"], ["fe-fd-fb-f7-ef-df-bf-7f", "fe-fd-fb-f7-ef-df-bf-7f"] ].each do |input, expect| it input do assert_equal BitTetris.solve(input), expect end end end end
ボールカウント(野球)
https://qiita.com/Nabetani/items/ebd8a56b41711ba459f9
module BallCount def self.solve(input) out = strike = ball = 0 sb_zero = ->{ strike = ball = 0 } input.each_char.map {|c| case c when "s" strike += 1 if strike == 3 sb_zero.() out += 1 end when "b" ball += 1 sb_zero.() if ball == 4 when "h" sb_zero.() when "p" out += 1 sb_zero.() when "f" strike += 1 if strike <= 1 end out = strike = ball = 0 if out == 3 "#{out}#{strike}#{ball}" }.join(",") end end if __FILE__ == $0 require 'minitest/autorun' describe 'BallCount' do [ ["s", "010"], ["sss", "010,020,100"], ["bbbb", "001,002,003,000"], ["ssbbbb", "010,020,021,022,023,000"], ["hsbhfhbh", "000,010,011,000,010,000,001,000"], ["psbpfpbp", "100,110,111,200,210,000,001,100"], ["ppp", "100,200,000"], ["ffffs", "010,020,020,020,100"], ["ssspfffs", "010,020,100,200,210,220,220,000"], ["bbbsfbppp", "001,002,003,013,023,000,100,200,000"], ["sssbbbbsbhsbppp", "010,020,100,101,102,103,100,110,111,100,110,111,200,000,100"], ["ssffpffssp", "010,020,020,020,100,110,120,200,210,000"] ].each do |input, expect| it input do assert_equal BallCount.solve(input), expect end end end end
Y字路巡り
http://nabetani.sakura.ne.jp/hena/ord3ynode/
module YshapedRoadTour Graph = {"A"=>"DCB", "B"=>"CEA", "C"=>"FBA", "D"=>"EFA", "E"=>"DBF", "F"=>"ECD"} def self.solve(input) input = input.each_char result = "" go = ->(s, e) { result << e idx = Graph[e].index(s) case input.next when "b" go.(e, s) when "r" i = (idx - 1) % 3 when "l" i = (idx + 1) % 3 end go.(e, Graph[e][i]) } go.("B", "A") rescue StopIteration result end end if __FILE__ == $0 require 'minitest/autorun' describe 'YshapedRoadTour' do [ ["b", "AB"], ["l", "AD"], ["r", "AC"], ["bbb", "ABAB"], ["rrr", "ACBA"], ["blll", "ABCAB"], ["llll", "ADEBA"], ["rbrl", "ACADE"], ["brrrr", "ABEDAB"], ["llrrr", "ADEFDE"], ["lrlll", "ADFEDF"], ["lrrrr", "ADFCAD"], ["rllll", "ACFDAC"], ["blrrrr", "ABCFEBC"], ["brllll", "ABEFCBE"], ["bbbrrlrl", "ABABEDFCB"], ["rbllrrrr", "ACABCFEBC"], ["lbrlrrblr", "ADABCFEFCA"], ["rlbrrrrbl", "ACFCADFCFD"], ["bllrlrbrrb", "ABCADEFEBCB"], ["rllrllllbb", "ACFDEBADEDE"], ["blblrlrrlbr", "ABCBEDFCABAC"], ["lrlrrrrrbrb", "ADFEBCFEBEDE"], ["rblllrlrrlrr", "ACABCADEFDABE"], ["rbrrlrblrllb", "ACADFEBEFDACA"], ["lrrrlrllrrllr", "ADFCABEFCADEBC"], ["rrlblllrrlrrb", "ACBEBADEFDABEB"], ["brbllrrbbrlrll", "ABEBADFCFCABEFC"], ["rrrbbrlbrlblrb", "ACBABACFCABADFD"], ["lllllllllllblrr", "ADEBADEBADEBEFDE"], ["llllllrllrlbrrr", "ADEBADEFCBADABED"] ].each do |input, expect| it input do assert_equal YshapedRoadTour.solve(input), expect end end end end
フカシギの通行止め
https://qiita.com/Nabetani/items/9c514267214d3917edf2
ループによる実装。
module CountFukashigi n = 5 Goal = n * n - 1 Pathes = n.times.flat_map {|i| n.times.map {|j| a = i * n + j [a - 1, a - n, a + n, a + 1] } } Pathes[0...n].map! { _1.delete_at(1) } Pathes[-n..-1].map! { _1.delete_at(2) } 0.step(by: n, to: Goal) { |i| Pathes[i].delete_at(0) } (n - 1).step(by: n, to: Goal) { |i| Pathes[i].delete_at(-1) } def self.solve(input) table = Pathes.map(&:dup) input.split.each do |str| a, b = str.bytes.map { _1 - 97 } table[a].delete(b) table[b].delete(a) end result = 0 stack = [[0]] loop do road = stack.pop break result unless road table[road[-1]].each do |nxt| next if road.include?(nxt) if nxt == Goal result += 1 else stack << road + [nxt] end end end end end if __FILE__ == $0 require 'minitest/autorun' describe 'CountFukashigi' do [ ["", 8512], ["af", 4256], ["xy", 4256], ["pq qr rs st di in ns sx", 184], ["af pq qr rs st di in ns sx", 92], ["bg ch di ij no st", 185], ["bc af ch di no kp mr ns ot pu rs", 16], ["ab af", 0], ["ty xy", 0], ["bg ch ej gh lm lq mr ot rs sx", 11], ["ty ch hi mn kp mr rs sx", 18], ["xy ch hi mn kp mr rs sx", 32], ["ch hi mn kp mr rs sx", 50], ["ab cd uv wx", 621], ["gh mn st lq qr", 685], ["fg gl lm mr rs", 171] ].each do |input, expect| it input do assert_equal CountFukashigi.solve(input), expect end end end end
結果。
Finished in 0.332796s, 48.0774 runs/s, 48.0774 assertions/s. 16 runs, 16 assertions, 0 failures, 0 errors, 0 skips
別解。再帰を使う。
module CountFukashigi n = 5 Goal = n * n - 1 Pathes = n.times.flat_map {|i| n.times.map {|j| a = i * n + j [a - 1, a - n, a + n, a + 1] } } Pathes[0...n].map! { _1.delete_at(1) } Pathes[-n..-1].map! { _1.delete_at(2) } 0.step(by: n, to: Goal) { |i| Pathes[i].delete_at(0) } (n - 1).step(by: n, to: Goal) { |i| Pathes[i].delete_at(-1) } def self.solve(input) table = Pathes.map(&:dup) input.split.each do |str| a, b = str.bytes.map { _1 - 97 } table[a].delete(b) table[b].delete(a) end result = 0 field = Array.new(Goal + 1) field[0] = true go = ->(now) { table[now].each do |nxt| if nxt == Goal result += 1 else next if field[nxt] field[nxt] = true go.(nxt) field[nxt] = nil end end } go.(0) result end end
結果。ループよりこちらの方が速い。
Finished in 0.135252s, 118.2977 runs/s, 118.2977 assertions/s. 16 runs, 16 assertions, 0 failures, 0 errors, 0 skips
テトロミノ認識
http://nabetani.sakura.ne.jp/hena/ord4tetroid/
module FindTetromino t = [[:L, 4, ["111", "100"]], [:L, 4, ["111", "001"]], [:T, 4, ["111", "010"]], [:I, 2, ["1111"]], [:S, 2, ["110", "011"]], [:S, 2, ["011", "110"]], [:O, 1, ["11", "11"]]] Tetrominos = t.map {|s, n, pt| pt = pt.map { _1.chars.map(&:to_i) } a = n.times.map { tmp = pt pt = pt.reverse.transpose tmp }.map {|blk| blk.flat_map.with_index {|row, y| row.filter_map.with_index { |b, x| [x, y] if b == 1 } } } [s.to_s] + a } N = 10 module_function def each_tetromino Tetrominos.each do |name, *pts| pts.each { |pt| yield(name, pt) } end end def do(input) field = Array.new(N) { Array.new(N) } input.split(",").each do |str| str.chars.map(&:to_i).tap { |x, y| field[y][x] = true } end answer = "-" N.times do |y| N.times do |x| each_tetromino do |name, pattern| f = pattern.all? {|dx, dy| x1 = x + dx y1 = y + dy next if x1 < 0 || x1 >= N next if y1 < 0 || y1 >= N field[y1][x1] } answer = name if f end end end answer end end if __FILE__ == $0 require 'minitest/autorun' describe 'FindTetromino' do [ ["55,55,55,55", "-"], ["39,28,27,29", "L"], ["63,62,43,53", "L"], ["32,42,43,44", "L"], ["81,72,91,71", "L"], ["62,64,72,63", "L"], ["45,25,35,24", "L"], ["12,20,22,21", "L"], ["66,46,67,56", "L"], ["44,46,45,43", "I"], ["04,24,14,34", "I"], ["43,42,41,40", "I"], ["48,38,58,68", "I"], ["31,20,22,21", "T"], ["69,79,78,89", "T"], ["42,33,44,43", "T"], ["16,25,05,15", "T"], ["27,37,28,38", "O"], ["13,24,23,14", "O"], ["63,72,62,73", "O"], ["73,63,62,74", "S"], ["56,57,47,66", "S"], ["88,99,98,87", "S"], ["62,43,52,53", "S"], ["86,95,87,96", "S"], ["84,83,73,94", "S"], ["32,33,41,42", "S"], ["86,85,75,96", "S"], ["97,76,96,77", "-"], ["53,55,45,43", "-"], ["73,93,94,84", "-"], ["31,33,41,42", "-"], ["21,32,11,12", "-"], ["73,75,65,64", "-"], ["64,65,45,54", "-"], ["12,00,01,10", "-"], ["94,85,75,74", "-"], ["87,86,77,75", "-"], ["56,56,56,56", "-"], ["41,42,41,52", "-"], ["61,60,63,61", "-"], ["03,13,33,13", "-"], ["92,96,94,93", "-"], ["15,25,55,45", "-"], ["17,14,16,13", "-"], ["72,83,83,92", "-"], ["40,40,42,51", "-"], ["81,80,93,82", "-"], ["51,61,30,41", "-"], ["17,37,35,15", "-"] ].each do |input, expect| it input do assert_equal FindTetromino.do(input), expect end end end end
Rails on Tiles
http://nabetani.sakura.ne.jp/hena/ord5railsontiles/
module RailsOnTiles Tiles = [[2, 3, 0, 1], [1, 0, 3, 2], [3, 2, 1, 0]] Dirs = [[0, -1], [1, 0], [0, 1], [-1, 0]] module_function def go(input) field = input.chars.map(&:to_i).each_slice(3).to_a solve(field).map { |i| ("A".."I").to_a[i] }.join end def solve(field, x=1, y=-1, dir=2, route=[]) dx, dy = Dirs[dir] x += dx y += dy return route if x < 0 || x > 2 || y < 0 || y > 2 rev = Tiles[0][dir] nxt = Tiles[field[y][x]][rev] tile_num = y * 3 + x solve(field, x, y, nxt, route + [tile_num]) end end if __FILE__ == $0 require 'minitest/autorun' describe 'RailsOnTiles' do [ ["101221102", "BEDGHIFEH"], ["000000000", "BEH"], ["111111111", "BCF"], ["222222222", "BAD"], ["000211112", "BEFIHEDGH"], ["221011102", "BADGHIFEBCF"], ["201100112", "BEHIFCBADEF"], ["000111222", "BEFIH"], ["012012012", "BC"], ["201120111", "BEDABCFI"], ["220111122", "BADEHGD"], ["221011022", "BADG"], ["111000112", "BCFIHEBA"], ["001211001", "BEFI"], ["111222012", "BCFEHIF"], ["220111211", "BADEHI"], ["211212212", "BCFEBAD"], ["002112210", "BEFC"], ["001010221", "BEF"], ["100211002", "BEFIHG"], ["201212121", "BEFCBAD"] ].each do |input, expect| it input do assert_equal RailsOnTiles.go(input), expect end end end end
大貧民
http://nabetani.sakura.ne.jp/hena/ord5dahimi/
class Card Rank = %W(3 4 5 6 7 8 9 T J Q K A 2) def initialize(str) @value = str @rank = (str == "Jo") ? 13 : Rank.index(str[1]) end attr_reader :value, :rank alias to_s value end module Daihinmin module_function def play(input) table, hand = input.split(",") return "-" unless hand hand = hand.scan(/../).map { |c| Card.new(c) } joker = hand.find {|c| c.value == "Jo"} table = table.scan(/../).map { |c| Card.new(c) } t_rank = table.map(&:rank).min t_num = table.size cs = hand.group_by(&:rank).select { |k, v| k > t_rank }.values result = cs.select { |ary| ary.size >= t_num } .flat_map { |ary| ary.combination(t_num).to_a } if joker && t_num >= 2 result += cs.select { |ary| ary.size >= t_num - 1 && ary[0] != joker } .flat_map {|ary| ary.combination(t_num - 1).map { |cards| cards + [joker] } } end result.empty? ? "-" : result.map(&:join).join(",") end end if __FILE__ == $0 def same?(input, expect) inputs = input.split(",") expects = expect.split(",") return false unless inputs.size == expects.size equal = ->(a, b) { a == b || a.scan(/../).sort == b.scan(/../).sort } is_found = ->(ans) { s = expects.find { |e| equal.(e, ans) } return false unless s expects.delete(s) true } inputs.all?(&is_found) end [ ["DJ,", "-"], ["H7,HK", "HK"], ["S3,D4D2", "D4,D2"], ["S9,C8H4", "-"], ["S6,S7STCK", "CK,ST,S7"], ["H4,SAS8CKH6S4", "S8,CK,H6,SA"], ["ST,D6S8JoC7HQHAC2CK", "Jo,C2,CK,HA,HQ"], ["SA,HAD6S8S6D3C4H2C5D4CKHQS7D5", "H2"], ["S2,D8C9D6HQS7H4C6DTS5S6C7HAD4SQ", "-"], ["Jo,HAC8DJSJDTH2", "-"], ["S4Jo,CQS6C9DQH9S2D6S3", "DQCQ,D6S6,H9C9"], ["CTDT,S9C2D9D3JoC6DASJS4", "JoC2,SJJo,DAJo"], ["H3D3,DQS2D6H9HAHTD7S6S7Jo", "JoHA,JoD6,JoH9,D6S6,D7S7,JoS6,HTJo,JoDQ,S2Jo,JoD7,JoS7"], ["D5Jo,CQDAH8C6C9DQH7S2SJCKH5", "CQDQ"], ["C7H7,S7CTH8D5HACQS8JoD6SJS5H4", "HAJo,JoSJ,H8S8,H8Jo,CQJo,CTJo,JoS8"], ["SAHA,S7SKCTS3H9DJHJH7S5H2DKDQS4", "-"], ["JoC8,H6D7C5S9CQH9STDTCAD9S5DAS2CT", "CTDT,H9D9,S9D9,DACA,CTST,H9S9,DTST"], ["HTST,SJHJDJCJJoS3D2", "DJCJ,SJDJ,JoHJ,CJHJ,SJJo,HJSJ,DJJo,JoCJ,JoD2,SJCJ,DJHJ"], ["C7D7,S8D8JoCTDTD4CJ", "D8S8,JoS8,CTJo,DTJo,JoCJ,CTDT,D8Jo"], ["DJSJ,DTDKDQHQJoC2", "JoDK,HQDQ,DQJo,C2Jo,JoHQ"], ["C3H3D3,CKH2DTD5H6S4CJS5C6H5S9CA", "S5H5D5"], ["D8H8S8,CQHJCJJoHQ", "JoCQHQ,JoHJCJ"], ["H6D6S6,H8S8D8C8JoD2H2", "D2H2Jo,D8JoS8,D8S8C8,C8D8H8,JoC8S8,H8JoC8,S8H8C8,JoS8H8,C8JoD8,D8H8S8,D8JoH8"], ["JoD4H4,D3H3S3C3CADASAD2", "DACASA"], ["DJHJSJ,SQDQJoHQCQC2CA", "SQJoCQ,DQCQJo,JoSQHQ,SQCQHQ,DQHQSQ,HQDQCQ,HQDQJo,SQDQCQ,CQJoHQ,SQJoDQ"], ["H3D3Jo,D4SKH6CTS8SAS2CQH4HAC5DADKD9", "HASADA"], ["C3JoH3D3,S2S3H7HQCACTC2CKC6S7H5C7", "-"], ["H5C5S5D5,C7S6D6C3H7HAH6H4C6HQC9", "C6D6S6H6"], ["H7S7C7D7,S5SAH5HAD5DAC5CA", "SADACAHA"], ["D4H4S4C4,S6SAH6HAD6DAC6CAJo", "C6H6S6D6,SAJoDACA,S6H6C6Jo,SACAJoHA,HADASAJo,HADAJoCA,CADAHASA,D6C6JoH6,S6D6C6Jo,H6JoS6D6"], ["DTCTSTHT,S3SQH3HQD3DQC3CQJo", "HQSQJoDQ,SQCQDQJo,DQCQHQJo,SQHQJoCQ,CQDQHQSQ"], ["JoS8D8H8,S9DTH9CTD9STC9CAC2", "H9C9D9S9"], ].each do |input, expect| p same? Daihinmin.play(input), expect end end
続柄
http://nabetani.sakura.ne.jp/hena/ord6kinship/
module Relationship module_function def solve(start, goal) tree = Hash.new { |h, k| h[k] = [] } (1..40).each do |i| tree[i] << (i + 1) / 3 if i != 1 (i*3-1..i*3+1).each { |j| tree[i] << j } if i < 14 end result = move(tree, start, goal) table = {""=>:me, "-"=>:mo, "+"=>:da, "-+"=>:si, "--+"=>:au, "-++"=>:ni, "--++"=>:co} table.default = :- table[result] end def move(tree, start, goal, before=0, route="") return route if start == goal (tree[start] - [before]).each do |nxt| next_route = route + (nxt < start ? "-" : "+") return next_route if nxt == goal a = move(tree, nxt, goal, start, next_route) return a if a end nil end end if __FILE__ == $0 require 'minitest/autorun' describe 'Relationship' do [ [[5, 2], :mo], [[28, 10], :au], [[1, 1], :me], [[40, 40], :me], [[27, 27], :me], [[7, 2], :mo], [[40, 13], :mo], [[9, 3], :mo], [[4, 1], :mo], [[1, 3], :da], [[12, 35], :da], [[3, 8], :da], [[6, 19], :da], [[38, 40], :si], [[9, 8], :si], [[4, 2], :si], [[15, 16], :si], [[40, 12], :au], [[10, 4], :au], [[21, 5], :au], [[8, 2], :au], [[3, 5], :ni], [[11, 39], :ni], [[2, 13], :ni], [[13, 32], :ni], [[14, 22], :co], [[40, 34], :co], [[5, 8], :co], [[12, 10], :co], [[1, 27], :-], [[8, 1], :-], [[12, 22], :-], [[2, 40], :-], [[32, 31], :-], [[13, 14], :-], ].each do |input, expect| it input do assert_equal Relationship.solve(*input), expect end end end end
ABC179
https://atcoder.jp/contests/abc179
A: Plural Form
str = gets.chomp puts str + (str[-1] == "s" ? "es" : "s")
B: Go to Jail
n = gets.to_i dice = n.times.map {gets.split.map(&:to_i)} f = dice.each_cons(3).any? {|d1, d2, d3| d1[0] == d1[1] && d2[0] == d2[1] && d3[0] == d3[1] } puts f ? "Yes" : "No"
C: A x B + C
提出していないけれど、これはたぶん TLE。
require "prime" n = gets.to_i puts (1..n - 1).sum {|c| (n - c).prime_division.inject(1) {|acc, (a, b)| acc * (b + 1)} }
できた。484ms。
総当りで、仮に a ≦ b とすれば、a は高々 √n 個で済む。
n = gets.to_i x = Integer.sqrt(n) ans = 0 (1..x).each do |a| (a..n / a).each do |b| c = n - a * b next if c < 1 if a == b ans += 1 else ans += 2 end end end puts ans
上を圧縮。466ms。
n = gets.to_i ans = 0 (1..Integer.sqrt(n)).each do |a| (a..n / a).each do |b| next if n - a * b < 1 ans += (a == b) ? 1 : 2 end end puts ans
さらに改良。64ms。わーい、いまのところ Ruby で最速!
b のループをせずに計算で済ませている。
n = gets.to_i x = Integer.sqrt(n) ans = 0 (1..x).each do |a| bn = n / a - a bn -= 1 if (n % a).zero? ans += bn * 2 + 1 end ans += 1 if x * x == n puts ans
D: Leaping Tak
TLEまちがいなし。
n, k = gets.split.map(&:to_i) lrs = k.times.map {gets.split.map(&:to_i)} s = (1..n).select {|i| lrs.any? {|l, r| (l..r).cover?(i)} } count = 0 try = ->(x) { if x == n count += 1 else s.each do |jump| nxt = x + jump break if nxt > n try.(nxt) end end } try.(1) puts count % 998244353
TLEだが、悪くない。メモ化。でも、s をすべて求めているのがいけないのだな。
n, k = gets.split.map(&:to_i) lrs = k.times.map {gets.split.map(&:to_i)} s = (1..n).select {|i| lrs.any? {|l, r| (l..r).cover?(i)} } memo = {} try = ->(x) { return memo[x] if memo[x] count = 0 s.each do |i| a = x + i if a > n break elsif a == n count += 1 else count += try.(a) end end memo[x] = count } puts try.(1) % 998244353
公式解説の解法。わからんぞ。
n, k = gets.split.map(&:to_i) lrs = k.times.map {gets.split.map(&:to_i)}.sort MOD = 998244353 dp = Array.new(n, 0) ans, dp[0], dp[1] = 0, 1, -1 (0...n).each do |i| ans = (ans + dp[i]) % MOD lrs.each do |l, r| break unless i + l < n dp[i + l] = (dp[i + l] + ans) % MOD next unless i + r + 1 < n dp[i + r + 1] = (dp[i + r + 1] - ans) % MOD end end puts ans
ABC181
https://atcoder.jp/contests/abc181
A: Heavy Rotation
n = gets.to_i puts n.even? ? "White" : "Black"
B: Trapezoid Sum
n = gets.to_i abs = n.times.map {gets.split.map(&:to_i)} puts abs.map {|a, b| (b - a + 1) * (a + b) / 2}.sum
C: Collinearity
n = gets.to_i xys = n.times.map {gets.split.map(&:to_i)} f = xys.combination(3).any? {|p1, p2, p3| v1x = p2[0] - p1[0] v1y = p2[1] - p1[1] v2x = p3[0] - p1[0] v2y = p3[1] - p1[1] v1x * v2y == v1y * v2x } puts f ? "Yes" : "No"
D: Hachi
与えられた文字列str
が 3桁以下の場合は、順列による総当り。
そうでない場合は、8で割り切れる数は下3桁で決まることを使う。但しここでは 0 を含んではいけないことに注意。そのような 3桁の数をすべて求め、使う数字の個数の一覧を登録しておく(変数table
)。また、同様にstr
で使う数字のそれぞれの個数も調べる(変数tmp
)。あとは、table
に含まれるcnt
の中に、「条件」を満たすものがひとつでもあればよい。「条件」とは、tmp
がうまくcnt
を「含んで」いること。
table = (100..999).map {|i| next if (i % 8).nonzero? ds = i.digits next if ds.include?(0) count = Array.new(9, 0) ds.each {|n| count[n - 1] += 1} count }.compact str = gets.chomp if str.size <= 3 f = str.chars.permutation.any? {|cs| (cs.join.to_i % 8).zero? } else tmp = Array.new(9, 0) str.each_char {|c| tmp[c.to_i - 1] += 1} f = table.any? {|cnt| sum = 0 cnt.zip(tmp).each {|a, b| sum += a if b >= a} sum == 3 } end puts f ? "Yes" : "No"
E: Transformable Teacher
n, m = gets.split.map(&:to_i) hs = gets.split.map(&:to_i).sort ws = gets.split.map(&:to_i).sort s = t = 0 dp1 = [0] + hs.each_slice(2).map {|a, b| s += (b || 0) - a} dp2 = [0] + hs.reverse.each_slice(2).map {|a, b| t += a - (b || 0)} j = 0 ans = (0..n / 2).map {|i| h = hs[2 * i] j += 1 while j + 1 < m && (ws[j + 1] - h).abs <= (ws[j] - h).abs dp1[i] + dp2[n / 2 - i] + (h - ws[j]).abs }.min puts ans
これはこの解答をパクった。いまひとつわからない。
ABC180
https://atcoder.jp/contests/abc180
A: box
n, a, b = gets.split.map(&:to_i)
puts n - a + b
B: Various distances
gets xs = gets.split.map(&:to_i) puts xs.map {_1.abs}.sum puts Math.sqrt(xs.map {_1 * _1}.sum) puts xs.map {_1.abs}.max
C: Cream puff
require "prime" n = gets.to_i table = n.prime_division.map {|a, b| (b + 1).times.map {|i| a ** i} } table = [[1]] if table.empty? puts table[0].product(*table[1..-1]).map {|ary| ary.inject(:*)}.uniq.sort
D: Takahashi Unevolved
x, y, a, b = gets.split.map(&:to_i) ex = 0 loop do if (tmp = x * a) > x + b ex += (y - 1 - x) / b break else x = tmp end break if x >= y ex += 1 end puts ex
ABC175
https://atcoder.jp/contests/abc175
過去問。
A: Rainy Season
puts gets.chomp.each_char.chunk {|e| e == "R"} .map {|b, ary| b ? ary.size : 0}.max
B: Making Triangle
n = gets.to_i ls = gets.split.map(&:to_i) puts ls.combination(3).count {|li, lj, lk| li != lj && lj != lk && lk != li && li + lj > lk && lj + lk > li && lk + li > lj }
C: Walking Takahashi
x, k, d = gets.split.map(&:to_i) x = x.abs result = if x < k * d if k.even? n = x / (2 * d) a = x - n * 2 * d b = a - 2 * d [a.abs, b.abs].min else if x <= d (x - d).abs else x -= d n = x / (2 * d) a = x - n * 2 * d b = a - 2 * d [a.abs, b.abs].min end end else x - k * d end puts result
ひどいタイポをしていた。まちがったコードをここにコピペして気づいた。
ABC174
https://atcoder.jp/contests/abc174
過去問。
B: Distance
n, d = gets.split.map(&:to_i) coordinates = n.times.map {gets.split.map(&:to_i)} puts coordinates.count {|x, y| x * x + y * y <= d * d}