「今週のお題：最速のポスティング」問題解答 ( CodeIQ )

はじめに

CodeIQという所で週次で出題される「今週のお題」シリーズに解答しましたので、ネタバレです。

codeiq.jp

問題

格子状に配置されたポストへの投函順序が何通りあるか数えて出力する…、なのですが「最速」という制約が付きます。なので、

*縦・横の隣接移動のみで全ポストを1度ずつ通るやり方

と考えることができます。開始地点は任意です。

なお、ポストの縦・横は、カンマ区切り1行で入力として与えられます。

解答

コード

提出解は、以下のRubyでした。下の解説にある通り、当初はもう少し簡略なコードにしていたのですが、TLEの対策のためにちょっと変更しました。

def f_sup(a,r,d,i)
# a: boolean array
# r: remained posts
# d: distance in up/down move
# i: current post index
  t=0
  r-=1
  a[i]=false
  if r==1
    t=1 if [-d,-1,1,d].any?{|j|a[i+j]}
  else
    [-d,-1,1,d].each do |j|
      next unless a[i+j]
      t+=f_sup(a,r,d,i+j)
    end
  end
  a[i]=true
  t
end

def f(r,c)
# r: row
# c: column
  a=[false]*(c+1)+([true]*c+[false])*r+[false]*(c+1)
  t=0
  (r/2).times do|i|
    (c/2).times do|j|
      t+=f_sup(a,r*c,c+1,(c+1)*(i+1)+j)*4
    end
    if c%2==1
      j=c/2
      t+=f_sup(a,r*c,c+1,(c+1)*(i+1)+j)*2
    end
  end
  if r%2==1
    i=r/2
    (c/2).times do|j|
      t+=f_sup(a,r*c,c+1,(c+1)*(i+1)+j)*2
    end
    if c%2==1
      j=c/2
      t+=f_sup(a,r*c,c+1,(c+1)*(i+1)+c/2)
    end
  end
  t
end

puts f(*gets.split(?,).map(&:to_i))
__END__

解説

まあ、特に変なことはしていないので提出時のコメントで。

方針:
素直にしらみつぶしを行います。 boolean配列 a をポストの一覧と見立て、空きを true とし、順々に投函を試します。 最後まで投函できれば1通りとしてカウントし、途中で不可能になれば断念します。

ただ、端の処理が面倒なので、ガード領域 ( 上下および各行の間 ) を設け、1次元的に処理します。 すなわち、左右に進む場合は -1,+1、上下に進む場合は、-(列数+1),+(列数+1) の移動と扱うということになります。

なお、当初は全てを開始地点として試していましたが、処理時間がかかりすぎるため、対称性を利用して、約1/4に抑えるようにしました。

終わりに

なんか速い/上手い方法、あるんでしょうかねえ…?