ABC 030を解いた - 電波ビーチ

ウデマエがクソなので日々の鍛錬として。

A 勝率計算

試合数と勝利数が2チーム分与えられるからそれぞれの勝率を比較しその結果によって出力を分岐する。勝率は当然勝利数 / 試合数で求まるのでそのまま計算する。intではなくfloatとして数値計算する。

a, b, c, d = gets.chomp.split.map(&:to_f)
if b/a < d/c
  puts "AOKI"
elsif d/c < b/a
  puts "TAKAHASHI"
else
  puts "DRAW"
end

B 時計盤

アナログ時計n時m分としてn, mが与えられるからnとmのなす角のうち小さいほうを求める問題。三角関数以前。長針は60分で360度回るので1分だと6度、短針は12時間=720分で360度回るので1分だと0.5度進む。1時間だと30度。これを利用して計算する。短針と長針のなす角度のうち小さい方を読み飛ばしていて、というか考慮することすら頭になくてWAを食らったがみんなは真似しちゃだめだぞ

n, m = gets.chomp.split.map(&:to_f)
n = (n%12)*30+(m*0.5)
m = m*6
puts [(m-n).abs, 360-(m-n).abs].min

C 飛行機乗り

ABC030で最も難しい（個人の感想）。普通に解説読んだ。次に乗れる便を探すのに二分探索を使う（N⁵、M⁵とかででかいので愚直にやると間に合わない）。よくある最大値のうちの最小値を読み替えたxを越える最初の数、ではなく、x『以上』となる最初の数を求めるようにカスタマイズする。あと『往復の回数』である点に注意してカウントする

n, m = gets.chomp.split.map(&:to_i)
x, y = gets.chomp.split.map(&:to_i)
a_lis = gets.chomp.split.map(&:to_i)
b_lis = gets.chomp.split.map(&:to_i)
ans = 0
now = 0
def lower_bound(arr, x)
  # arrのうちx以上となる最小の値
  l, r = -1, arr.size
  loop do
    mid = (r + l)/2
    return mid if r - l < 1
    if x <= arr[mid]  # ここで大なりイコールしているので、x以上、が保たれる
      r = mid
    else
      l = mid + 1
    end
  end
end
 
loop do
  # aからbに向かうことにする
  lb = lower_bound(a_lis, now)
  if lb == -1 # n - 1の場合 泥臭い
    lb = 0
  end
  break if lb >= n
  now = x + a_lis[lb]
  # bからaに向かうことにする
  lb = lower_bound(b_lis, now)
  if lb == -1
    lb = 0
  end
  break if lb >= m
  now = y + b_lis[lb]
  ans += 1
end
 
puts ans

D へんてこ辞書

小学生向けの問題でアルゴリズムとか知らなくても剰余がわかっていれば解ける（戒め）。少なくともCよりは簡単だと思う。試行回数Kに対して配列の数Nが圧倒的に小さいのと、1≦bi≦Nの制約により、K（≦N）回の試行中に必ず既に一度参照済みの数値に向かう機会がある。一度参照した数値からはまた同じように参照済みの数値へと向かうことになり、これは無限に循環する。これを利用して、循環する配列を抽出して、その時点での残り試行回数を配列の長さで割った余りを求めてやる。循環する配列は、とりあえず最初から数値を積んでいき、既に存在する数値を確認したらそれ以前の要素は省くことで抽出した。

n, a = gets.chomp.split.map(&:to_i)
k = gets.to_i
arr = gets.chomp.split.map(&:to_i)
# 循環に入ったらそこまでの回数を引いたものを循環の長さで割って余りを求め、循環の配列から値を求める
cnt = 0
circular = []
while k > cnt
  cnt += 1
  if circular.include?(a)
    circular = circular[circular.index(a)..-1]
    idx = (k-cnt) % circular.size
    a = arr[circular[idx]-1]
    break
  else
    circular << a
  end
  a = arr[a-1]
end
puts a