【振り返り】GCJ2019 Round 1A: Pylons

今日はGoogle Code Jamの3回あるRound1のうちの初日でした。

先週末の予選を終えてからAtcoderに登録し簡単な問題を解いてみたのですが、 流石に1週間でRound1をパスできるほど甘くなかったです^^;

マス目を埋める問題は初見だったので、"マス目 競技プログラミング"でググりつつ「DPとは。。」という気持ちになり、 これは素手じゃ戦えんなと悟りPCを閉じて走りに行きました（完）

とこれだけでは何も残らないので、競技プログラミングの先輩が公開しているコードをRubyで書き直しつつ振り返っていきます。

問題概要

• R行C列のマス目が与えられる
• 全てのマス目を1回ずつ通る道順を求める
• 次に移動するとき、今のマスから見て前後斜め直線状のマスを選ぶことはできない (チェスならクイーン、将棋なら飛車＋角行が移動できる位置)
• 実現できない場合は"IMPOSSIBLE"、できる場合は"POSSIBLE"を返し道順を出力する

制限

• 時間：20sec / テストセット
• テストセット1: T=16, 2≦R≦5, 2≦C≦5
• テストセット2: 1≦R≦100, 2≦R≦20, 2≦C≦20

コードの解析

今回もすでにけんちょんさんが記事をアップしていたので、ありがたく拝読させて頂き、まずはRubyに焼き直してみました。

GCJ 2019 Round 1A A - Pylons - けんちょんの競プロ精進記録

ちなみに今回採用すべき解法はDPではないらしく、GCJの解説によるとKnight's tourというチェスのナイトのような動き（将棋だと桂馬）を採用したアルゴリズムが１つの解のようです。

# ルート生成
def route_generator(h, w)
  # ダメなパターンを先に除外
  return false if h == 2 && w < 5
  return false if h == 3 && w < 4
  return false if h == 4 && w < 4

  # ルートを作る
  arr = route(h, w)

  # 対称なグリッド対策
  if (h % 2 == 0) && h == w
    arr = avoid_conflict(h, w, arr)
  end

  arr
end


def route(h, w)
  arr = []

  (0...w).each do |j|
    (0...h).each do |i|
      if i % 2 == 0
        arr << [i, j]
      else
        (h == 2) ? arr << [i, (j + 3) % w] : arr << [i, (j + 2) % w]
      end
    end
  end

  arr
end

def avoid_conflict(h, w, arr)
  p = arr[h*w - h]
  arr.delete_at(h*w - h)
  arr << p

  arr
end

# 解答のための形作り
def answer_formatter(h, w)
  answer = ""
  swapped = false

  if h > w
    h, w = w, h
    swapped = true
  end

  if arr = route_generator(h, w)
    answer << "POSSIBLE\n"
    arr.each do |el|
      if swapped
        el[0], el[1] = el[1], el[0]
      end

      answer << "#{el[0]+1} #{el[1]+1}\n"
    end
  else
    answer << "IMPOSSIBLE\n"
  end

  answer
end


t = gets.chomp.to_i

t.times do |i|
  h, w = gets.chomp.split(" ").map(&:to_i)
  answer = answer_formatter(h, w)
  puts "Case ##{i + 1}: #{answer}"
end

アルゴリズム

公式の解説を読むといくつかアルゴリズムが紹介されていました。 力任せ探索と乱択アルゴリズムは、時間が許せばそのうち結果が出るが、問題によっては計算量が爆増してしまうため最後のテストセットまでクリアできないことが多そうです（現実問題では札束で殴って許されるケースもありますが、、）。

• Brute-force search (力任せ探索)
• Randomized algorithm (乱択アルゴリズム)
• Dynamic Programming (DP、動的計画法)
• Greedy Algorithm (貪欲法)

動的計画法と貪欲法については、これから勉強していく予定です。

動的計画法の導入としては下記のブログで、パフォーマンス的な利点も含めてわかりやすく説明されていました。

動的計画法（Dynamic Programming）をサルでも分かるように説明する - その１（フィボナッチ数列） - ベルリンのITスタートアップで働くソフトウェアエンジニアのブログ

まとめ

さっそくアルゴリズムの壁に直面したので、下記記事を参考に修行していこうという機運が高まりました。 Round 1Bではもう少し良い結果を出せるように頑張ります。

qiita.com

また今回もC++のコードを読解したのですが、リファレンスが利用しやすくて思ったより捗りました。あとRuby書くの楽すぎるでしょ！という気持ちも高まりました笑