はじめに

ABC336に参加しました。
今回、A~Dの4問完答できたのでD問題までメモしていきたいと思います。

A - Long Loong

Longのoを指定の数だけ結合する問題。

文字列結合ができれば良いので特に問題はない。強いて言えば、文字をn個繋げる処理をどう実装するか、が問題になるが、RubyにはString#*が定義されているので難しくない。

自分の回答

puts "L#{"o" * gets.to_i}ng"

B - CTZ

整数を2進数表記したときに、末尾に連続する0の数を求める問題。

色々定義されているが、2進数表記に直して末尾から0の個数を数えるだけで良い。

自分の回答

楽に実装したかったので、2進数表記にした後に正規表現で末尾の0を取得する方針で実装した。

puts gets.to_i.to_s(2).match(/0*$/)[0].length

B問題別解

今回の問題は２進数の末尾が0かどうかをチェックするだけなのでビットシフト(右シフト)しながら1桁目の数値をチェックすることで同じことができる。
こちらだと文字列の生成等が不要になるので上の回答よりは高速に処理ができるので参考として記載しておく。

右シフトを利用した回答

n = gets.to_i
c = 0
# 1桁目が0の間、カウントアップして右シフトする
while (n & 1) == 0
  n = n >> 1
  c += 1
end
puts c

C - Even Digits

偶数のみからなる整数群のうち、小さいものからn番目の整数を求める問題。

各桁の取りうる値は0, 2, 4, 6, 8の5つであり、8の次は桁上がりして0に戻る。つまり5進数の特殊(数値が0~4ではない)なパターンと見ることができる。
そのため、5進数と0, 2, 4, 6, 8を0=>0, 1=>2, 2=>4, 3=>6, 4=>8のように対応させると、10進数でのnを5進数に変換した値の各桁を対応表にそって変換した値が答えになる。
m進数のi桁目の値は10進数のnに対して、(n / m^(i-1)) % mで求められるので、あとはコードに落とし込むだけでよい。

自分の回答

# 1番目の値が0なのでずらしておく
n = gets.to_i - 1
# 5進数との対応表
arr = %w[0 2 4 6 8]

# 0は自明なので事前に処理する
if n == 0
  puts 0
  exit
end

ans = []
while n > 0
  ans << arr[n % 5]
  n /= 5
end
puts ans.reverse.join("")

C問題別解

今回の問題は偶数からなる値のため、5進数との対応がそれぞれ2倍にしたものと対応する。
そのため、5進数に直した値を2倍すれば解答になるため実装をよりシンプルにすることができる。

5進数での値を2倍する実装

puts (gets.to_i - 1).to_s(5).to_i * 2

D - Pyramid

与えられた数列の中に含まれるピラミッド数列の最大値を求める問題。

まず、与えられた数列の大きさによって、生成されうるピラミッド数列の理論値が決まる。具体的には配列の長さnに対して(n + 1) / 2(少数切り捨て)となる。
その場合の数列の各要素の最大値はi番目の要素aiに対してai = MIN(i, n - i)となる。
※先頭と末尾はピラミッドの端になるため1になり、そこから1つピラミッドの内側に入るたびに1増加するため。
※Nが奇数の時は中央が最大となる1つのピラミッドのみだが、Nが偶数の時は最大のピラミッドは2つ選び方がある。

与えられた数列の要素のうち上で求めた理論値未満となる値がある場合は、そこがピラミッドの間の谷(または谷に続く道)となり取りうるピラミッドの高さを下げる要因となる。
ピラミッド数列は隣接する要素との差は1となるため、周囲より低い要素から左右に1段ずつ高くするように要素を更新していくことを全ての要素で行えば出来上がった配列の最大値が答えとなる。
ただし、この処理はn個の要素に対し左右n個の要素の更新処理が入るため、O(N^2)の計算量になり得るので効率化する必要がある。

やりたいことは低い位置から1段ずつ増えていく階段を作りたいだけなので、先頭と末尾からそれぞれ一つ前の高さより高い場合は一つ前の高さ+1に更新する処理をかけてあげると求めたい配列が得られる。
得られた配列の中で最大の値が答えとなる。

自分の回答

n = gets.to_i
arr = gets.split.map(&:to_i)
# 最大のピラミッド数列の場合の値に調整
# ※先頭・末尾から計算する際に1から上書きする処理が入っているためこの処理は不要
arr.each_with_index do |a, i|
  arr[i] = [a, i + 1, n - i].min
end

# 先頭から登る
ba = 0
arr.each_with_index do |a, i|
  if a > ba
    ba += 1
    arr[i] = ba
  else
    ba = a
  end
end

# 末尾から登る
ba = 0
arr.reverse.each_with_index do |a, i|
  if a > ba
    ba += 1
    arr[-i - 1] = ba
  else
    ba = a
  end
end

puts arr.max

最後に

C問題で凡ミスして2ペナもらったけどD問題までちゃんと解けてよかったです。
E問題も挑戦してみましたが今回は全く手が出なかったです。解説を軽くみていると桁DBというものを使うらしいので後で確認して理解を進めておきたいですね。

参考リンク

AtCoder Beginner Contest 336