情報自炊

情報を血肉にしたい

【Ruby】AtCoder Beginner Contest 129のA〜D問題振り返り

結果はA, B, CがAC。DがTLE。

f:id:hoshitostar:20190609224735p:plain

C問題のREは全部の積を求めてから余りを求めていたから。この手のREは初めてだったので次回から余りを出力する問題では気をつける。

問題一覧

atcoder.jp

提出

A問題

提出日時:2019-06-09 21:01:52

p,q,r=gets.chomp.split(" ").map(&:to_i)

puts [p+q, r+p, q+r].min

A問題にしてはちょっと難しいと思った。

B問題

提出日時:2019-06-09 21:09:14

n=gets.chomp.to_i
w_arr=gets.chomp.split(" ").map(&:to_i)

min = 100000000

(0..(n-1)).each do |t|
  abs = w_arr[0..t].inject(&:+).to_i - w_arr[(t+1)..-1].inject(&:+).to_i
  abs *= -1 if abs < 0
  min = abs if abs < min
end

puts min

ここで時間を食ったのが痛かった。添字と、配列が空だとinjectの戻り値がnilになる考慮が足りずに確認が思った以上にかかった。

C問題

提出日時:2019-06-09 21:35:34

n,m = gets.chomp.split(" ").map(&:to_i)

a_arr = []
m.times do |i|
  a_arr << gets.chomp.to_i
end
a_arr << n+1

fib = [1, 1]
100000.times do |i|
  fib[2+i] = fib[2+(i-1)] + fib[2+(i-2)]
end

arr = []
step = 0
prev = -1
a_arr.each do |a|
  if a - prev == 1 then
    puts 0
    exit
  end
  count = a - step - 1
  #puts count
  if count > 0 then
    arr << fib[count]
  end
  step = a + 1
  prev = a
end

result = 1
arr.each do |a|
  result *= a
  result = result % 1000000007
end

puts result

読みながらだと方針が全然分からなかった。壊れている床までの連続したstep数によって組み合わせが決まって、しかもその組み合わせは前のものに依存しているのかなあくらいの印象。

こういう場合は手を動かして簡単な例から作っていくのが良く、step:1 ,2, 3, ... と実際に数えてみた。1, 2, 3, 5, 8と出てきたのでフィボナッチ数列と予想が付き、1段上りと2段上りがあるからstep(i) = step(i-1) + step(i-2)の形になるのは納得だなあ(証明というよりは感覚)と考えたところで実装。

問題はフィボナッチ数列をどう実装するか。前の結果を利用していくタイプだとかなり難しいなと焦りそうになったが、Nの上限が10の5乗であることからあらかじめ全部求めても問題ないと判断して割とゴリ押し気味に実装。手元での確認で結果が出るまでにワンテンポ遅れるので不安だったがなんとか大丈夫だった。

D問題

提出日時:2019-06-09 22:22:46

何回かTLE出しましたが基本方針は変わらず。

h,w = gets.chomp.split(" ").map(&:to_i)

arr = []
h.times do |i|
  tmp_arr = []
  input = gets.chomp
  (0..(input.length-1)).each do |j|
    tmp_arr << (input[j] == "#")
  end
  tmp_arr << true
  arr << tmp_arr
end

tmp_arr = []
w.times do |i|
  tmp_arr << true
end
tmp_arr << true
arr << tmp_arr

h_pos = []
h_tmp_count = []
w.times do |i|
  h_pos << -1
  h_tmp_count << -1
end

max = 0

(0..(h-1)).each do |i|
  w_pos = -1
  w_tmp_count = -1
  (0..(w-1)).each do |j|
    bool = arr[i][j]
    next if bool


    w_count = 0
    if j < w_pos then
      w_count = w_tmp_count
    else
      ((j+1)..(w)).each do |j2|
        bool_j2 = arr[i][j2]
        if bool_j2 then
          w_pos = j2
          w_tmp_count = w_count
          break
        else
          w_count += 1
        end
      end
    end

    h_count = 0
    if i < h_pos[j]
      h_count = h_tmp_count[j]
    else
      ((i+1)..(h)).each do |i2|
        bool_i2 = arr[i2][j]
        if bool_i2 then
          h_pos[j] = i2
          h_tmp_count[j] = h_count
          break
        else
          h_count += 1
        end
      end
    end

    count = h_count + w_count + 1
    max = count if count > max
  end
end

puts max

これこそは前の結果を利用していくタイプだと思って実装。

4 6
#..#..
.....#
....#.
#.#...

こういう入力があって(0,1)の座標に明かりを設置したとき「右方向に1の明かり + 下方向に3の明かり + 自身」で5マスになるのだが、このとき(0,2)の座標では横方向の明かりの数が、(1,1), (2,1), (3,1)の座標では縦方向の明かりの数が、それぞれ流用できる。この流用していくアルゴリズムでいけるのかなと思ったがダメだった。

そしてここを書いているタイミングで解説が公表されたので読んでみると…

上下左右方向だと…!?

障害物が存在しないときに最悪計算量が O(HW(H + W)) となってしまい、これでは時間内に答えを求めることができません。

これは確かに。私の提出だとi2とj2のためのループでH + Wの時間が発生してしまいO(HW(H + W))となっている。

例えば、L[i][j] の要素は次のように計算できます。

RとDとUはそれぞれi, jとプラス1するかマイナス1するかの違いで求められるってことか。勉強になる。

A, B, C問題の解説もそれぞれ勉強になる。

A問題の3つの和から最大数を引くってのはかなりトリッキー。

B問題はO(N)でも解くことができる。

C問題はフィボナッチ数列を求める過程で、壊れた床をスキップする処理を書けること。

ベストなコードに近づくのは難しいがこれがまた別の形で役に立つと思う。