【参加ログ】Google Code Jam 2019: Qualification Round

Google Code Jam 2019のQualification Roundに参加したのでその記録です。

Google Code Jamとは

Googleが主催しているプログラミングコンテストです。今年は予選から3回戦まではオンライン、決勝は1つの会場で行われます (今年はカリフォルニアのGoogleオフィス)。

codingcompetitions.withgoogle.com

今年のスケジュール

フェーズ	開始 (JST)	終了 (JST)	制限時間	通過条件
Qualification Round	4/6 08:00	4/7 11:00	27hrs	30pts取得
Round 1A	4/13 10:00	4/13 12:30	2.5hrs	上位1500位まで
Round 1B	4/29 01:00	4/29 03:30	2.5hrs	上位1500位まで
Round 1C	5/4 18:00	5/4 20:30	2.5hrs	上位1500位まで
Round 2	5/18 23:00	5/19 01:30	2.5hrs	上位1000位まで
Round 3	6/8 23:00	6/9 01:30	2.5hrs	上位25位まで
World Finals	8/9 4:30	8/9 08:30	4hrs

※Round1はA/B/Cのどれかで通過すればOKです (全部参加でき、A~Cで合わせて4500名が通過)

※決勝はCAの現地会場で実施されます。

スケジュールへのリンク

出題形式

今年のQualification Roundでは4種類の問題が与えられ、問題に対して課された制約ごとに、ポイントが与えられます。

今回の配点はこんな感じです。

問題	Test set1	Test set2	Test set3
Foregone Solution	6pts	10pts	1pts
You Can Go Your Own Way	5pts	9pts	10pts
Cryptopangrams	10pts	15pts
Dat Bae	14pts	20pts

例えば、N桁の整数に関する問題に対して、計算量でテストセットの難易度別にポイントが加算されるといった具合です。

Test set1 (6pts): 1 < N < 10⁵
Test set2 (10pts): 1 < N < 10⁵
Test set3 (1pts): 1 < N < 10¹⁰⁰

ちなみにテストセットにはVisible/Hiddenの2種類があり、 Visibleは解答を送信した時点で正否がわかりますが、Hiddenはコンテスト期間が終わって初めて正否が公開されます。

それでは今回自分が解いた問題 (2問目まで) について書いていきます。

1問目: Foregone Solution (6pts, 10pts, 1pts)

問題

100桁以下のNが与えられる
- Nの全桁のうち、最低1つに4が含まれる
a + b = N
- a, bはどの桁にも4を含まない整数

問題へのリンク

制約

Test set1: 1 < N < 10⁵
Test set2: 1 < N < 10⁹
Test set3: 1 < N < 10¹⁰⁰

考えたこと

まずはコンテストの形式に慣れるため、最初から全テストを通すことは狙わずにサブミットしていこうと考えました。そのため、最初はNをシンプルに1ずつずらしていくという力技の処理で書いてみました。案の定Test set2でランタイムエラーとなったため、4を検知したら1と3に分けるよう決め打ちするように変更したところパスしました。

自分の解答

1回目

def separator(num)
  a = 1
  while
    b = num - a
    if !include_digit_four?(a) && !include_digit_four?(b)
      break
    end
    a += 1
  end
  return a, b
end

def include_digit_four?(num)
  /4/ =~ num.to_s
end

t = gets.chomp.to_i

t.times do |i|
  n = gets.chomp.to_i
  a, b = separator(n)
  puts "Case ##{i + 1}: #{a} #{b}"
  # Case #x: A B
end

最終版

def include_digit_four?(num)
  /4/ =~ num.to_s
end

def find_index_of_four(num) # 中身が同じメソッドを書いてしまった　汗
  /4/ =~ num.to_s
end

def one_digit_separator(arr, num)
  index = find_index_of_four(arr[0])
  b = arr[1] + 10 ** (arr[0].to_s.size - index - 1)
  a = num - b
  return a, b
end

def separator(num)
  arr = [num, 0]
  while
    arr = one_digit_separator(arr, num)
    if !include_digit_four?(arr[0]) && !include_digit_four?(arr[1])
      break
    end
  end
  return arr[0], arr[1]
end

t = gets.chomp.to_i

t.times do |i|
  n = gets.chomp.to_i
  a, b = separator(n)
  puts "Case ##{i + 1}: #{a} #{b}"
end

2問目: You Can Go Your Own Way (5pts, 9pts, 10pts)

問題

問題へのリンク

N x Nのマス目が与えられる
- 北西 (左上) の最頂点がスタート、南東 (右下) の最頂点がゴール
- 東 (右) か南 (下) 方向にのみ進める
ライバルの道順が与えられる (例：SEEESSES)
- マス間の移動で、ライバル同じ進み方をすることが出来ない (同じマスに止まることはできるが、そこから同じ方向に進めない)。

制約

Test set1 (6pts): 2 ≤ N ≤ 10
Test set2 (10pts): 2 ≤ N ≤ 10³
Test set3: (1pts) 1 < N < 10⁴

考えたこと

紙に書きながら動き方を考えたところ、常にライバルと違う方向に進めば良さそうなことに気づきました (要はスタートからゴールまでの対角線に対して、反転させた経路を通れば良い)。

実装中はゴールから逆順に経路を決めていくイメージで実装を進めていたので、かなり冗長な書き方になってますが、本当は簡単なループでいけますね。。

雑だけどこんなイメージ

route = ''
(1..N.size).each do |letter|
  if N[letter] == 'E'
     route << 'S'
  else
     route << 'E'
  end
end

自分の解答

def route_choice(str)
  route = ''
  rival_route = str
  while
  if check_last_motion(rival_route) == 'S'
    route.insert(0, 'E')
  else
    route.insert(0, 'S')
  end
    rival_route.chop!
    if rival_route == ''
      break
    end
  end
  route
end

def check_last_motion(str)
  str[-1]
end

def add_motion(route, motion)
  route.insert(0, motion)
end

t = gets.chomp.to_i

t.times do |i|
  n = gets.chomp.to_i
  str = gets.chomp
  route = route_choice(str)
  puts "Case ##{i + 1}: #{route}"
end

結果

1, 2問目ともTest set3までパスしていて、41ptsで予選通過となりました。

振り返り

今回事前の準備なしで取り組んだのですが、色々詰まりつつも結構楽しかったです。普段のノリでメソッドの意味合いを考えつつ進めていたのですが、競技的には余分で削ぎ落とすべき要素なのかもしれません。

さっそくアップされていた競プロの先輩達の振り返り記事を読んでみると、実装の仕方や観点が違い勉強になります。

GCJ 2019 Qual A - Foregone Solution - けんちょんの競プロ精進記録

GCJ 2019 Qual B - You Can Go Your Own Way - けんちょんの競プロ精進記録

Google Code Jam 2019 Qualification Round : A. Foregone Solution, B. You Can Go Your Own Way - kmjp's blog

渡り鳥の旅路

元半導体系エンジニア、今Webエンジニアの雑記

【参加ログ】Google Code Jam 2019: Qualification Round

Google Code Jamとは

今年のスケジュール

出題形式

1問目: Foregone Solution (6pts, 10pts, 1pts)

問題

制約

考えたこと

自分の解答

1回目

最終版

2問目: You Can Go Your Own Way (5pts, 9pts, 10pts)

問題

制約

考えたこと

自分の解答

結果

振り返り