Google Code Jam 2017: Qualification Round

以前にAOJを始めたものの情けないことに結局2週間くらいで止まってしまい、それ以来ずっとこれ系からは離れてしまっていたけど、Code Jamは何故か毎年チャレンジしている(毎回すぐ予選落ちしてるけど)ので、今年も挑戦してみた。

Qualification Roundは27時間のオンライン予選。その時間中に4問のうち幾つかを解いて25pt以上獲得すれば次に進める、というもの。

土曜の夜に時間を見つけて取り組んでみた。 C++でやりたかったけど、色々と思い出せる気がしなかったので全部Rubyでやった。

A. Oversized Pancake Flipper

長さSのパンケーキ列を与えられて、長さKのflipperを使ってすべてを表面にするための最低操作回数、もしくは不可能であるか、を求める

sample input:

3
---+-++- 3
+++++ 4
-+-+- 4

sample output:

Case #1: 3
Case #2: 0
Case #3: IMPOSSIBLE

とにかく端から順番に見ていって、裏(-)があればそこを起点にK個ひっくり返しカウントし、逆端まで到達する位置まで行ったら最後に全部表(+)になっているかどうか判定すれば答えは出せるはず、ループ回数もせいぜいS * Kでたいしたことない。

こんな感じで

t = gets.to_i
t.times do |i|
  s, k = gets.split(' ')
  s = s.split('').map { |c| c == '+' }
  a = 0
  (s.size - k.to_i + 1).times do |m|
    next if s[m]
    k.to_i.times do |n|
      s[m + n] = !s[m + n]
    end
    a += 1
  end
  ok = true
  k.to_i.times do |m|
    next if s[s.size - m - 1]
    ok = false
    break
  end
  puts "Case ##{i + 1}: #{ok ? a : 'IMPOSSIBLE'}"
end

普通にrangeを書いてeachを使うべきか…？

B. Tidy Numbers

与えられたN以下の数のうち最大の、「数字が左から昇順に並ぶ数」を求める。

sample input:

4
132
1000
7
111111111111111110

sample output:

Case #1: 129
Case #2: 999
Case #3: 7
Case #4: 99999999999999999

Nからスタートして順番にデクリメントしていって一つ一つ昇順になっているかどうか判定していってもいいけど、そうすると10^18になるlarge datasetで詰むのは目に見えている。

もう最初から数値だと思わずに、法則に従う数字の列だと思って操作していけばいいか、と。132は129になる。1325だと1299になるし 13246だと12999が答えになるはず、とか考えると「右から降順になっているかチェックして、違反していたらその桁の値を1つ小さくしてそこから右を全部9にする」を繰り返せば解に辿り着きそう。最上位桁が0になったら削る。計算量も桁数 * 9回程度だから一瞬で出る。

ということで

t = gets.to_i
t.times do |i|
  n = gets.strip.split('').map(&:to_i)
  loop do
    ok = true
    (n.size - 1).times do |j|
      next unless n[j] > n[j + 1]
      ok = false
      n[j] = n[j].to_i - 1
      ((j + 1)..(n.size - 1)).each do |k|
        n[k] = 9
      end
      n.slice!(0) if n[0] == 0
      break
    end
    break if ok
  end
  puts "Case ##{i + 1}: #{n.join}"
end

C. Bathroom Stalls

問題を理解するのに時間かかった…。要するに並んでいる長さNのstallの列を選択によって分割したときの右と左ができるだけ長い列になるよう埋めていく、という法則に従ってK人が使用したときの最大値と最小値を求める、ということになる

sample input:

sample output:

Case #1: 1 0
Case #2: 1 0
Case #3: 1 1
Case #4: 0 0
Case #5: 500 499

1000だったら1人目によって500と499に分割され、次は2人目によって500が分割され250と249になる、そうすると3人目は499を249と249で真っ二つに、…という感じの流れになる。対象が奇数のときは(n-1)/2が2つに分けられるけど、偶数のときはn/2とn/2-1と違う長さに分けられることに気をつけないといけない。

最初は[N]の1要素配列から始めてshiftした値を分割してそれを降順で後ろに突っ込むqueueみたいな形でK回操作を繰り返せば答えが出るのでは？と思ったけど、偶数の同じ値が続いたときに124, 124 -> 62, 61, 62, 61のように降順に並ばないことに気付き、苦し紛れに操作のたびにqueueをsort!するという暴挙に出たところsmall datasets 1はどうにか通ったけど、10^6くらいのdatasetだと当然のように計算が終わらなくて死ぬ。

同じ値が何度も登場することに気付いたのでそれぞれの出現回数を持って操作していけばいいのか！とすぐに気付いて{ N => 1 }から始まるHashを用意。keys.maxを取り出して、対応するvalueを key: (m-1)/2 や key: m/2-1 などに加える。というのを繰り返せばよい。取り出したvalueの総計がKを超えたら既にK人が使用した、ということでそのときの値が答えになる。

t = gets.to_i
t.times do |i|
  n, k = gets.strip.split(' ').map(&:to_i)
  a = { n => 1 }
  y = z = n
  total = 0
  loop do
    m = a.keys.max
    v = a.delete(m)
    y = m / 2
    z = m.even? ? m / 2 - 1 : m / 2
    a[y] = 0 unless a.include?(y)
    a[y] += v
    a[z] = 0 unless a.include?(z)
    a[z] += v
    total += v
    break if total >= k
  end
  puts "Case ##{i + 1}: #{y} #{z}"
end

問題文からはこういう形になることが全然想像つかなかったので、解いていて面白かった。

D. Fashion Show

一応問題は読んだけど、ちょっと時間があまり無かったのと確実に解けるような気がしなかったので捨てた…

結果

A, B, C でlarge datasetまで正答で65ptで終了。