2019-09-25

2019年9月25日

学習記録

『現場で使える Ruby on Rails 5速習実践ガイド』×2
『プログラマのためのDocker教科書』×2
『キタミ式イラストIT塾 ITパスポート』×1
求人票回答×1

『現場で使える Ruby on Rails 5速習実践ガイド』2ポモドーロ。インストールやGitなど諸々の作業に時間を取られ、実装はあまり進まなかった。スピードアップしないと。あとやっぱり、Gitをもっと自信を持って使いたい。なにか本を買って読もう。
— ティーコリ (@tkori19) September 25, 2019

『プログラマのためのDocker教科書』2ポモドーロ。進捗は遅いが、手を動かしているおかげで、だんだん意図通りにコマンドを操れるようになってきている。
— ティーコリ (@tkori19) September 25, 2019

『キタミ式イラストIT塾 ITパスポート』1ポモドーロ。寝不足が祟って睡魔が…。1時間ほど休憩を入れてから始めたがダメだ。30分くらい仮眠しよう。
— ティーコリ (@tkori19) September 25, 2019

「求人票コメント」約1ポモドーロ。1社のみだったのでサクッと。少し就活の書き物に慣れてきた。プレッシャーを抱え込まず、気楽にやったらいいんだ。
— ティーコリ (@tkori19) September 25, 2019

振り返り

昨夜はなかなか寝付けず、3時間くらいしか眠れなかった。
それでも午前中から来て学習できたのはよかった。
結局、こうやって生活リズムを築いていくのが一番学習効率が高い。

しかし午後には睡魔がやってきたので仮眠しようと思ったら、ちょうど同期がやってきてエラー解決を手伝うことになった。
そしたらあっという間に18:00。
まあ楽しく話しながらやって、しっかりエラーも解決できたので良い気分転換になった。

最後に、きょう新たに送られてきた求人票に対するコメントを書いて最低限のことは済ませた。
Pythonの学習を今日はできなかったのは心残りだけど、また明日がんばろう。

2019-09-24

2019年9月24日

学習記録

『みるみる英語力がアップする音読パッケージトレーニング』×1（通学時）
『現場で使える Ruby on Rails 5速習実践ガイド』×2
『プログラマのためのDocker教科書』×2
『キタミ式イラストIT塾 ITパスポート』×1
「Python チュートリアル」×2

『現場で使える Ruby on Rails 5速習実践ガイド』2ポモドーロ。テスト導入の前まで読み進んだ。今日はメモに書き留めるのを止めたおかげで進捗がよかった。当初の予定を変更して次からは、ここまで読んできた部分の実装を先にやってしまおうと思う。
— ティーコリ (@tkori19) September 24, 2019

『プログラマのためのDocker教科書』2ポモドーロ。dockerコマンドを一通り動かす部分なので退屈だが、ここで手を動かすのは大切だろうからしっかりやっておこう。
— ティーコリ (@tkori19) September 24, 2019

『キタミ式イラストIT塾 ITパスポート』1ポモドーロ。相対的に軽い学習なので気分転換になる。うまいこと時間割に組み込めたらいい。この調子で毎日ちょっとずつ進めて行きたい。
— ティーコリ (@tkori19) September 24, 2019

「Python チュートリアル」2ポモドーロ。理解は粗いけどゴールが見えてきた。ここは手早く終わらせよう。
— ティーコリ (@tkori19) September 24, 2019

振り返り

今日は午後からの学習だった割には充実した勉強ができた。
いま5つほど並行して学習しているが、他にもやりたいことが差し迫っていて困る。

面接対策のアプローチを考えていろいろ準備したいし、paizaの問題も解いていきたいし、TOEIC受験のためにとりあえず現状の力試しをしたいし、「低レイヤを知りたい人のためのCコンパイラ作成入門」を読みたいし、保留状態のiOS アプリ開発を始めたいし（Androidユーザーなので実機がない問題があるが）、React.jsの勉強もしたいし、カリキュラムの復習をまとめて記事にしたいし…。

まあ、今は時間的に少し余裕があるし、焦らずにいま取り組んでいることにまずは集中していこう。

時間というと、通学中に『みるみる英語力がアップする音読パッケージトレーニング』のリスニングをしてみたが、乗車時間で1周できそうということがわかった。
これで片道は英語リスニング、片道はKindle読み上げによる読書に充てられる計算だ。

『音読パッケージトレーニング』については、何度か繰り返しているので聴き取りにほとんど問題はないが、全ての単語を完璧に聴き取れるレベルまでブラッシュアップするまで使っていきたいと思っている。

それから、きのう久々にpaizaに挑戦したが、競技プログラミング問題へのブランクを感じた。

今日は解けなかったが、毎日1問は解いて慣れていきたいと思っている。
paizaは復習には不向きなので、AtCoderの過去問を解いていきたいが、そうするとRubyではなくPythonで挑戦したい。そう思ってPythonの勉強をしている。

とにかく時間が足りない！

2017-08-27

AtCoder Beginner Contest 005

AtCoder Ruby

とりあえずソースコードだけ記しておく。

abc005.contest.atcoder.jp

AtCoder Beginner Contest 005 解説 from AtCoder Inc.

www.slideshare.net

A - おいしいたこ焼きの作り方

x, y = gets.split.map(&:to_i)
puts y / x

B - おいしいたこ焼きの食べ方

n = gets.to_i
t = []
n.times { t << gets.to_i }
puts t.min

C - おいしいたこ焼きの売り方

t = gets.to_i
n = gets.to_i
a = gets.split.map(&:to_i)
m = gets.to_i
b = gets.split.map(&:to_i)
if n < m
  puts 'no'
  exit
end
res = 0
b.each do |_b|
  a.each_with_index do |_a, i|
    if _a <= _b && _b - t <= _a
      res += 1
      a.slice!(0..i)
      break
    end
  end
end
puts res == m ? 'yes' : 'no'

D - おいしいたこ焼きの焼き方

def maximize_score
    # 各マスの右下までの面積を求める
    (@N - 1).downto(0) {|x|
        (@N - 1).downto(0) {|y|
            @to_bottom_right[y][x] = @D[y][x] + @to_bottom_right[y][x + 1] \
            + @to_bottom_right[y + 1][x] - @to_bottom_right[y + 1][x + 1]
        }
    }
    # 幅・高さ・x座標・y座標ごとに定めた長方形内の合計値を求める
    1.upto(@N) {|w|
        1.upto(@N) {|h|
            0.upto(@N - 1) {|x|
                break if x + w > @N 
                0.upto(@N - 1) {|y|
                    break if y + h > @N 
                    tmp = @to_bottom_right[y][x] - @to_bottom_right[y + h][x] \
                    - @to_bottom_right[y][x + w] + @to_bottom_right[y + h][x + w]
                    @max_each_area[h * w] = [tmp, @max_each_area[h * w]].max
                }
            }
        }
    }
end
 
@N = gets.to_i
@D = []
@N.times{ @D << gets.split.map(&:to_i) }
@Q = gets.to_i
@P = []
@Q.times{ @P << gets.to_i }
 
@max_each_area = Array.new(@N * @N + 1, 0)
@to_bottom_right = Array.new(@N + 1){ Array.new(@N + 1, 0) }
 
maximize_score
@P.each {|p| puts @max_each_area[0..p].max }

2016-02-08

AtCoder Beginner Contest 004

AtCoder Ruby

テキストだけで考え方を表現するのは難しいので、今回から図表を導入する。
さしあたって、ツールはdraw.ioを使ってみる。

abc004.contest.atcoder.jp

AtCoder Beginner Contest 004 解説 from AtCoder Inc.

www.slideshare.net

A - 流行

puts gets.to_i * 2

B - 回転

result = []
4.times { result.unshift(gets.split.reverse.join(' ')) }
puts result.join("\n")

f:id:tkori:20160208100237p:plain

上図のように変換すればいいので、行ごとに逆順にし、それをLIFO（後入れ先出し）で出力すればOK。
行で考えずに入力全体を逆順に出力する方法（puts $stdin.read.chomp.reverse）でもいける。

C - 入れ替え

cards = [*1..6]
n = gets.to_i % 30
n.times { |i| cards[i%5], cards[i%5+1] = cards[i%5+1], cards[i%5] }
puts cards.join

f:id:tkori:20160208104045p:plain

(i mod 5)+1番目のカードと(i mod 5)+2番目のカードを入れ替える操作を繰り返していくだけだが、数が増えていくと、計算量が増えて時間が足りなくなる。
しかし、操作を繰り返していくうちに法則が見えてくる。
初期配置からカードを30回操作すると、再び初期配置に戻ってくるのだ。
つまり、カードの配置は30回周期なので、入力された数を30で割った余りを求めてから、その数だけ操作を行えばいい。

D - マーブル

def calc(left, right)
  (left..right).reduce(0) { |a, e| a + e.abs }
end
 
R, G, B = gets.split.map(&:to_i)
result = 1_000_000_000
 
(-300..300).each do |g_left|
  g_right = g_left + G - 1
  b_left = 100 - (B - 1) / 2
  b_left = g_right + 1 if g_right >= b_left
  b_right = b_left + B - 1
  r_right = -100 + (R - 1) / 2
  r_right = g_left - 1 if r_right >= g_left
  r_left = r_right - R + 1
  
  r_left += 100; r_right += 100
  b_left -= 100; b_right -= 100
  tmp = calc(r_left, r_right) + calc(g_left, g_right) + calc(b_left, b_right)
  result = [result, tmp].min
end
 
puts result

えらく難儀した。
今はこの問題について書く気力がないので手短に（笑）

緑のマーブルの左端を起点にして、赤と青のマーブルの配置を定めていく。
起点の位置を-300から300の位置で走査していき、最小の操作回数になるものを求める。

最終的には他の人の解答を見てすっきり書くことができたが、こういう探索問題の考え方は身に付いていないなと実感。

2015-12-16

AtCoder Beginner Contest 003

AtCoder Ruby

abc003.contest.atcoder.jp

AtCoder Beginner Contest 003 解説 from AtCoder Inc.

www.slideshare.net

A - AtCoder社の給料

n = gets.to_i
puts (1..n).reduce(0) { |a, e| a + 10_000 * e * (1.0 / n) }

上記のようにイテレーションを使って律儀に計算するのではなく、解説にあるように期待値の和から求めれば計算量が少なくて済む。
具体的には、 $10000 \times (n + 1) \times \frac{1}{2}$ となるので、puts 5000 * (gets.to_i + 1)だけで片付いてしまう。

B - AtCoderトランプ

s = gets.chomp
t = gets.chomp
 
s.size.times do |i|
  unless s[i] == t[i]
    next if s[i] == '@' && t[i] =~ /[atcoder]/
    next if s[i] =~ /[atcoder]/ && t[i] == '@'
    puts 'You will lose'
    exit
  end
end
puts 'You can win'

スッキリ書けたかな。

C - AtCoderプログラミング講座

n, k = gets.split.map(&:to_i)
ratings = gets.split.map(&:to_i)
 
puts ratings.sort[-k..-1].reduce(0) { |a, e| (a + e) / 2.0 }

最大レートを達成するためには、N個の動画をレーティング順にソートして、高レーティングなK個の動画をチョイスしなければならない。
加えて、高レーティングなK個の動画の中で、レーティングの低い順に見ていく必要がある（後から見た動画の方がレーティングに与える影響が大きいため）。

D - AtCoder社の冬

# n個からk個を選ぶ組み合わせの数を求める
def c(n, k)
  (1..n).reduce(1, :*) / ((1..n-k).reduce(1, :*) * (1..k).reduce(1, :*))
end

# x行y列の区画におけるデスクとラックの配置パターン数を求める
def alloc(x, y)
  return 0 if x < 0 || y < 0
  return 0 if x * y < ::D + ::L
  c(x * y, ::D) * c(x * y - ::D, ::L)
end

R, C = gets.split.map(&:to_i)
X, Y = gets.split.map(&:to_i)
D, L = gets.split.map(&:to_i)

# 壁で囲まれた区画の配置パターン数
walled_area = (R - X + 1) * (C - Y + 1)

# デスクとラックの配置パターン数
desk_rack_area = alloc(X, Y)
# 以下、包除原理を用いて最上[下左右]列が全て空きスペースのパターンを排除
desk_rack_area -= alloc(X - 1, Y) * 2 + alloc(X, Y - 1) * 2
desk_rack_area += alloc(X - 1, Y - 1) * 4 + alloc(X - 2, Y) + alloc(X, Y - 2) 
desk_rack_area -= alloc(X - 1, Y - 2) * 2 + alloc(X - 2, Y - 1) * 2 
desk_rack_area += alloc(X - 2, Y - 2)

puts walled_area * desk_rack_area % 1_000_000_007

とても苦労した。
一難去ってまた一難という感じで、完答できるまでだいぶ時間が掛かってしまった。

復習も兼ねて、手順を追って解答を見ていく。

まずは、R行C列の社員室において、X行Y列の壁で囲まれた領域を設けるパターン数を求める。
行について考えてみると、例えばR = 3のとき、X = 1ならば3パターン、X = 2ならば2パターン、X = 3ならば1パターンといった具合になる。
よって、行の設置パターン数はR - X + 1。同様に、列はC - Y + 1。
つまり、壁で囲まれた領域の設置パターン数は、
$(R - X + 1) \times (C - Y + 1) \cdots ①$
になる。

次に、X行Y列の領域において、D個のデスクとL個のサーバーラックを配置するパターン数を求める。
ここでは、デスクもラックもない空きスペースの存在も考慮しなければいけない。
すると、求めるパターン数は、 $_{X \times Y}C_{D+L} \ \times \ _{X \times Y-D}C_L$ になる。
この式は、この後も繰り返し使われるので、allocという名前でメソッド化しておく。
なお、allocメソッドに毎回、定数D, Lを渡すのは面倒なので、::を使ってトップレベル定数にアクセスすることにした。

さて、実際にデスクとラックの配置パターン数を求めるわけだが、X行Y列の区画はデスクとラックの位置に沿って決められている。
よって、X行Y列の領域の最上[下左右]列のいずれかにデスクかラックが置かれていなければならない。
つまり、「X行Y列の領域の最上[下左右]列が全て空きスペースのパターン」を取り除かないと、正しいパターン数を求めることができない。

「最上[下左右]列が全て空きスペースのパターン」は、上下が空きスペース列、左右下が空きスペース列など、空きスペース列が重複するパターンも含まれる。
ここで、最上列が空きスペース列のパターンを集合Tとして、同様に最下列をB、最左列をL、最右列をRとすると、取り除くべきパターン数は、
$T \vee B \vee L \vee R \cdots ②$
ということになる。

これを包除原理を利用して変形すると、
$T + B + L + R - (T \wedge B) - (T \wedge L) - (T \wedge R) - (B \wedge L) - (B \wedge R) \\ - (L \wedge R) + (T \wedge B \wedge L) + (T \wedge B \wedge R) + (B \wedge L \wedge R) - (T \wedge B \wedge L \wedge R)$
となる。
要するに、それぞれの集合を足して、2集合の積集合を引いて、3集合の積集合を足して、4集合の積集合を引く。
集合の数を増やす毎に、足して引いてを変えながら繰り返していく。

ここまで来れば、あとはallocメソッドを使ってこれを再現していけばいい。
TやBは上下の空きスペース列が増えるということだから、Xを減らしていけばいいし、LやRならYを減らしていけばいい。
注意しなければいけないのは、行や列を減らして考えて処理するので、XやYが負の値を取ったり、X × Y が D + Lより少なくなってしまうケースが発生してしまうことだ。
条件に合わないそのようなケースを無視するために、allocメソッドに条件式を書いて該当ケースを弾いている。

最後に、① × ②で全てのパターンを求めてから余りを出せば終わり。

2015-12-02

AtCoder Beginner Contest 002

AtCoder Ruby

abc002.contest.atcoder.jp

AtCoder Beginner Contest 002 解説 from AtCoder Inc.

www.slideshare.net

A - 正直者

nums = gets.split.map(&:to_i)
puts nums.max

B - 罠

str = gets.chomp
puts str.gsub(/[aiueo]/, '')

C - 直訴

xa, ya, xb, yb, xc, yc = gets.split.map(&:to_i)
puts ((xb - xa) * (yc - ya) - (yb - ya) * (xc - xa)).abs / 2.0

解説にあるように、符号付面積の公式を使う。
(0, 0), (a, b), (c, d)の3点が与えられたとき、求める面積Sは、 $S = \frac{|ad - bc|}{2}$ となる。
(0, 0)に座標点がない場合でも、1点を(0, 0)と考えて残りの2点を平行移動して考えればよい。
(a, b), (c, d), (e, f)であれば、座標点を(0, 0), (c-a, d-b), (e-a, f-b)と設定する。

上記の公式を適用するなら、変数名はa, b, c, d, e, fを割り当てた方がわかりやすい
ヘロンの公式を使う方法もあったか

D - 派閥

n, m = gets.split.map(&:to_i)
if m.zero?
  puts 1
  exit
end
relations = []
m.times { relations << gets.split.map(&:to_i) }
n.downto(2) do |i|
  [*1..n].combination(i).each do |c|
    if c.combination(2).all? { |pair| relations.include? pair }
      puts i
      exit
    end
  end
end

まず、M個の人間関係（知り合い関係）を全て配列に格納する。
N人いる場合、N, N-1, … , 2と多人数の派閥から検証していく。
派閥の成立条件は、派閥内の全ペアが知り合いであることなので、全ペアが配列に含まれているかを確かめればいい。
最大派閥の議員数を求めればよいので、多人数の派閥が見つかり次第、プログラムを終了する。

RangeをArrayに変換するには、Range#to_aではなく[*Range]を使うほうが簡便
最大クリーク問題

【参照】Rubyでの順列、組み合わせ。 - simanのブログ

2015-11-23

AtCoder Beginner Contest 001

AtCoder Ruby

abc001.contest.atcoder.jp

ABC001 解説 from AtCoder Inc.

www.slideshare.net

A - 積雪深差

h1 = gets.to_i
h2 = gets.to_i
puts h1 - h2

puts gets.to_i - gets.to_iでもよし。

B - 視程の通報

m = gets.to_i
if m < 100
  puts "00"
elsif m.between?(100, 5000)
  vv = m * 10 / 1000
  puts vv < 10 ? "0#{vv}" : vv
elsif m.between?(6000, 30000)
  puts m / 1000 + 50
elsif m.between?(35000, 70000)
  puts (m / 1000 - 30) / 5 + 80
elsif m > 70000
  puts 89
end

2番目の条件節では、この後の問題Dでも使用するString#%を使ってもよかった
最後のputs 89は、puts "89"の方が明確で一貫性があった
8行目で「interpreted as grouped expression」と警告メッセージが出たので、putsの引数が長いときには、カッコを付けるか、変数に格納してから出力するべき

mをkmに変換するときに数値を浮動小数点数にするべきか迷ったが、この問題においては整数のままでも問題にならないので、整数のまま処理した。

C - 風力観測

class Float
  def direction
    degree_table = [11.25...33.75, 33.75...56.25, 56.25...78.75, 78.75...101.25,
                    101.25...123.75, 123.75...146.25, 146.25...168.75, 168.75...191.25,
                    191.25...213.75, 213.75...236.25, 236.25...258.75, 258.75...281.25,
                    281.25...303.75, 303.75...326.25, 326.25...348.75, 0.0..360.0]
    direction_table = %w(NNE NE ENE E ESE SE SSE S SSW SW WSW W WNW NW NNW N)
    degree_table.each_with_index do |direction, i|
      return direction_table[i] if direction.include? self
    end
  end
  
  def wind_force
    wind_table = [0.0..0.2, 0.3..1.5, 1.6..3.3, 3.4..5.4, 5.5..7.9,
                  8.0..10.7, 10.8..13.8, 13.9..17.1, 17.2..20.7, 20.8..24.4,
                  24.5..28.4, 28.5..32.6, 32.7..200.0]
    wind_table.each_with_index {|wind, i| return i if wind.include? self }
  end
end
 
# deg(整数)を引数に取ってdir(文字列)を返す
def deg_to_dir(deg)
  dir = (deg / 10.0).direction
end
 
# dis(整数)を引数に取ってw(整数)を返す
def dis_to_w(dis)
  w = (dis / 60.0).round(1).wind_force
end
 
deg, dis = gets.split.map(&:to_i)
dir = deg_to_dir(deg)
w = dis_to_w(dis)
dir = 'C' if w == 0
puts "#{dir} #{w}"

Float#directionにおけるブロック変数名directionが、メソッド名と同じなので変えるべき
deg_to_dirメソッド、dis_to_wメソッドは値を返すだけなので、わざわざ変数を用いる必要はない

D - 感雨時刻の整理

class Array
  def round
    s, e = self
    s -= s % 5 unless s % 5 == 0
    e += 5 - e % 5 unless e % 5 == 0
    e += 40 if e.to_s =~ /60\z/
    [s, e]
  end
  
  def merge
    return self if self.size <= 1
    (self.size - 1).times do |i|
      if self[i+1][0] <= self[i][1] && self[i][0] <= self[i+1][1]
        self[i+1] = [[self[i][0], self[i+1][0]].min, [self[i][1], self[i+1][1]].max]
        self[i] = nil
      end
    end
    self.compact
  end
end
 
n = gets.to_i
rainfall_times = []
n.times { rainfall_times << gets.split('-').map(&:to_i) }
rainfall_times.map(&:round).sort_by(&:first).merge.each do |rainfall_time|
  puts "%04d-%04d" % [rainfall_time[0], rainfall_time[1]]
end

時間を丸めるために、分数が60になったときに40を足して処理するのは、機転が利いていてよかった
Array#roundにおけるいくつかのselfは省略できる（self.sizeとself.compact）

Array#mergeにおいてcompactではなくcompact!を使っていたことで、Runtime Errorを発生させてしまい、ドツボにはまった。

【参照】2つの期間が重なり合うかどうかを判定する。 - こせきの技術日記