こんにちは。製品企画室の土井です。
先日PG BATTLE 2019が開催されました。昨年と比べて参加人数が大幅に伸び、今年は444チーム1,332名が参加するビッグイベントになりました。参加者の皆さん、ありがとうございます。
PG BATTLEは当社のサービス『TOPSIC』を利用して受験します。そのため、TOPSICチームに所属する私は、ここ数日間PG BATTLEの準備をしていました。事前準備の中には、出題する問題の確認作業なども含まれていたので、イベントには参加しませんでした。（ズルになるので）
今回は確認作業の際に、私が実際に回答したもののひとつを紹介したいと思います。難易度「ましゅまろ」で出題された「スライドボウリング」という問題です。問題の詳細についてはこちらをご覧ください。そして、私の回答が以下になります。言語はRubyを使用しました。
n, m = gets.split.map(&:to_i)
pin = Array.new(m, 0)
(1..n).each do |j|
a, b = gets.split.map(&:to_i)
t = a+b
if 1+t <= j && j <= m+t
pin[j-(1+t)] = 1
end
end
print pin.inject(:+)
まず全ての値を0で埋めた長さmの配列pinを用意しました。
pin = Array.new(m, 0)
次にn人分の投球を行い、ピンが倒れた場合は値を1に変更していきます。
(1..n).each do |j|
a, b = gets.split.map(&:to_i)
t = a+b
if 1+t <= j && j <= m+t
pin[j-(1+t)] = 1
end
end
全ての投球処理が終わったら、配列pinの合計値が倒れたピンの合計数になります。
print pin.inject(:+)
大まかな流れは以上です。
問題なのは、ボールがどのピンを倒したかを判断することでした。ここで、j番目のレーンで投球する人について考えます。j番目の人は開始からa秒後に投球し、更にレーンの先に辿り着くまでb秒掛かります。つまり、t = a+bとすると、開始からt秒後にj番レーン上にピンがあればヒットすることになります。
a, b = gets.split.map(&:to_i) t = a+b
では、実際にt秒後にj番レーン上にピンはあるのでしょうか? 問題文より、開始からt秒後の場合、i番ピンは(t+i)番レーン上にあります。つまり先頭の1番ピンは(1+t)番レーン、最後のm番ピンは(m+t)番レーンにあります。今投球した人はj番レーンにいるので、1+t <= j <= m+tが成り立てば、どれかしらのピン(既に倒れているものも含む)にヒットすることになります。
if 1+t <= j && j <= m+t pin[j-(1+t)] = 1 end
最後に何番目のピンにヒットしたかを調べます。先頭のピンは(1+t)番レーン、投球したのはj番レーンなので、その差分からヒットしたピンの位置を求めると{j-(1+t)+1}番ピンになります。(配列の添え字は0からスタートするため、コード上では1をひいて{j-(1+t)}としています)
pin[j-(1+t)] = 1
以上の処理をn人分繰り返すことで倒れたピンの総数を求めるというのが私の回答でした。(模範解答については、こちらをご覧ください)
こちらの問題は難易度3であり、丁寧にロジックを考えれば、処理時間オーバーで引っかかるようなことはないと思います。難易度が4以降になると、計算量を減らす工夫をしないと通過しない問題が多くなります。(多重ループを使用すると高確率で落とされます)
今回PG BATTLEで出題された12問全てに挑戦しましたが、残念ながら今の私では、難易度5以上の問題になると全く歯が立ちませんでした。特に木構造を使った考え方や探索系のアルゴリズムを理解するのが今後の課題となりそうです。
来年のPG BATTLE 2020までには、アルゴリズムに関する知識をもっと増やしておこうと思います。
今後ともTOPSICとPG BATTLEをよろしくお願いします。
