AtCoder Beginner Contest 005

1年超の間を空けて取り組んだD問題がやっと解けたので、とりあえずソースコードだけ記しておきます。

abc005.contest.atcoder.jp

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 }

AtCoder Beginner Contest 004

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

abc004.contest.atcoder.jp

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の位置で走査していき、最小の操作回数になるものを求める。

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

AtCoder Beginner Contest 003

abc003.contest.atcoder.jp

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メソッドに条件式を書いて該当ケースを弾いている。

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

AtCoder Beginner Contest 002

abc002.contest.atcoder.jp

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と多人数の派閥から検証していく。
派閥の成立条件は、派閥内の全ペアが知り合いであることなので、全ペアが配列に含まれているかを確かめればいい。
最大派閥の議員数を求めればよいので、多人数の派閥が見つかり次第、プログラムを終了する。

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

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

AtCoder Beginner Contest 001

abc001.contest.atcoder.jp

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.sizeself.compact

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

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

はじめてのあっとこーだー

プログラミングの問題が解けて、復習ができて、それをブログに書けて。
そんな目的に一番合うのはAtCoderかなと思ったので、始めてみる。

AtCoder

さしあたって、AtCoder Beginner Contestの過去問に取り組んでみようと思う。
解説もあるし、他の人のコードを見ることができるし、ブログに書くこともできるし、勉強するにはうってつけだ。

さて、取り掛かる前に、practice contestでソースコードの提出を練習してみよう。

practice.contest.atcoder.jp

A - はじめてのあっとこーだー

a = gets.to_i
b, c = gets.split.map(&:to_i)
s = gets.chomp
puts "#{a+b+c} #{s}"

何度目かのRailsチュートリアル 覚え書き

今回、取り組んだバージョンは第2版(Rails 4.0)
総作業時間は1810分(約30時間)

railstutorial.jp

スキップ

不要と判断した部分は読み飛ばした。
PostgreSQL導入は難しかったのでやめた。

  • 3.5.3(演習:ローカル環境にPostgreSQL導入)
  • 3.6(Guard, Spork導入など)
  • 8.3(Cucumber導入)
  • 8.5.2(演習:Cucumber関連)

覚え書き

  • full_titleメソッドはapp/helpers/application_helper.rbに置く。

  • ビューからrender 'layouts/xxx'でパーシャルを指定すると、app/views/layouts/_xxx.html.erbを参照する。

  • RSpecのヘルパーメソッドは、spec/support/utilities.rbに定義する。

  • spec/support/utilities.rbに定義したfull_titleメソッド(以下、テスト用メソッド)は、app/helpers/application_helper.rbのfull_titleメソッド(以下、オリジナルメソッド)と重複しているので解消する。

    1. オリジナルメソッドをテストして、その正当性を確保する(テストはspec/helpers/application_helper_spec.rbに記述)
    2. テストでもオリジナルメソッドを使うために、spec/support/utilities.rbにinclude ApplicationHelperと書いてインクルードする
    3. テスト用メソッドは不要になったので削除する
  • メールアドレスの一意性を確保するために、モデルとデータベースの二段階で重複をチェックする。
    具体的には、モデルではvalidatesメソッドのuniquenessオプション、データベースではインデックスの一意性検証が機能する。

  • has_secure_passwordメソッドは非常に強力。
    データベースにpassword_digestカラムを置けば、様々な属性の追加から認証まで一手に引き受けてくれる。
    ソースコードrails/secure_password.rb at master · rails/rails · GitHub

  • gravatar_forメソッドは、Usersコントローラに関連するものなので、app/helpers/users_helper.rbに置く。

  • 複数のコントローラにまたがるパーシャルビューはapp/views/sharedディレクトリに配置する。

  • ユーザー登録後、コントローラがflash変数にメッセージを格納して、登録したユーザーページへリダイレクトする。
    このとき、redirect_to user_url(@user)とする必要はなく、単にredirect_to @userと書けばよい。

  • ユーザー登録フォームとは違い、サインインフォームには(Session)モデルがなく、@userのようなインスタンス変数がないので、form_for(:session, url: sessions_path)としてヘルパーに情報を渡す。

  • flash変数にメッセージを代入した後に、render 'xxx'とビューを描画するのはリクエストではないので、次のリクエストにもflashメッセージが残ってしまう。
    これを回避するためには、flashではなくflash.nowを用いる。

  • サインインに関するメソッドはapp/helpers/sessions_helper.rbに書く。
    ヘルパーメソッドはビューだけでしか使えないので、Applicationコントローラにインクルードしてコントローラでも使えるようにする。

  • form_forはモデルを基にしたフォーム、form_tagはモデルに関わらないフォームを作るときに使用する。
    (参考:【Rails】form_for/form_tagの違い・使い分けをまとめた - Qiita

  • FactoryGirl.create(:user)はモデルを作成してデータベースへの保存まで行う。
    FactoryGirl.build(:user)はモデルを作成するだけでデータベースへの保存は行わない。

  • render @usersだけで、Railsは自動的に@usersをUserオブジェクトのリストであると推測し、app/views/users/_user.html.erbパーシャルを参照してリストの要素を全て出力してくれる。

  • ユーザー削除時に付随したマイクロポストの削除を確認するテスト。
    @user.microposts.to_aでマイクロポスト配列を作ってからユーザーを削除する。
    配列それ自体は存在し続けるので、配列要素である各マイクロポストがないことを確認することで検証される。

  • Usersコントローラにあるsigned_in_userメソッドを、Micropostsコントローラでも使用するために、app/helpers/sessions_helper.rbに移動する。
    セッションヘルパーは既にApplicationコントローラにインクルードされているので、コントローラでも使用可能になる。

参照

後半の演習で参考にしたもの
最後の3つは著者の解答例(英語)