私のプログラム
Rubyで解答しています。
#!/usr/bin/ruby
# 0 1 2 3 4 5 6 7
UP = [6, 5, 4, 2, 3, nil, 7, 0]
RIGHT = [1, 2, 0, 7, 6, 4, 5, nil]
DOWN = [7, nil, 3, 4, 2, 1, 0, 6]
LEFT = [2, 0, 1, nil, 5, 6, 4, 3]
DIR = {"u" => UP, "r" => RIGHT, "d" => DOWN, "l" => LEFT}
# 0 1 2 3 4 5 6 7
HAVE_U = [false, false, false, true, true, true, true, true]
HAVE_R = [true, true, false, false, false, true, true, true]
HAVE_D = [true, true, true, true, false, false, false, true]
HAVE_L = [false, true, true, true, true, true, false, false]
HAVE = {"u" => HAVE_U, "r" => HAVE_R, "d" => HAVE_D, "l" => HAVE_L}
def getPos(n)
ret = []
loop{
r = n % 8
n = n / 8
ret << r
break if n == 0
}
return ret
end
def isEdge(pos, have)
e = false
for v in pos
e |= have[v]
end
return !e
end
def getSide(pos, d)
# 左上の1〜8だけ特別な処理
if pos.size == 1 then
if d == "r" then
if pos[0] == 2 then return 9
elsif pos[0] == 3 then return 16
elsif pos[0] == 4 then return 15
end
elsif d == "d"
if pos[0] == 4 then return 59
elsif pos[0] == 5 then return 58
elsif pos[0] == 6 then return 57
end
end
end
dir = DIR[d]
have = HAVE[d]
ret = 1
# 境界線のチェック
# 境界線の内側にある値に対しては特殊な処理が必要
edge = isEdge(pos, have)
# 一番上か一番左の場合、その外側はnilを返す
if (d=="u") || (d=="l") then
return nil if edge
end
for i in 0...pos.size
s = dir[pos[i]]
return nil if s == nil
pow = 8**i
ret += pow * s
h = have[pos[i]]
if h then
for j in (i+1)...pos.size
pow = 8**j
ret += pow * pos[j]
end
return ret
end
end
# 右端か最下段の場合、その外側の値を加算する
if (d=="r") && edge then ret += 8**pos.size
elsif (d=="d") && edge then ret += (8**pos.size * 7)
end
return ret
end
def solve(n)
n = n-1
pos = getPos(n)
ret = []
ret << getSide(pos, "u")
ret << getSide(pos, "r")
ret << getSide(pos, "d")
ret << getSide(pos, "l")
return ret.compact.sort
end
# main
while line = gets
line.strip!
next if line.empty?
puts solve(line.to_i).join(",")
end
解説
かなり難しいと思います。★★★ですし。
Wikipediaの記事はそれほど役に立たないと思います。
考え方
入力値が1,000,000と大きいのであらかじめマップを作るのは時間的に無理と思います。なので、計算だけで求められる様にしなければなりません。
ポイントは座標の捉え方です。
具体例を先に挙げます。
2は[1]
30は[3,5]
468は[3, 2, 7]
となります。
これは次の様に数えます。
まず、3×3の領域を左上から次の様に数えます。
同様に9×9の領域もその中の3×3の領域を一かたまりとして時計回りに番号を振ります。
以降、27×27、81×81、…と同様に左上から時計回りに0〜7の番号とします。
これで具体例を見ると次の様になります。
2は3×3の領域にあり、座標1なので[1]です。
30は3×3の領域では座標3、9×9の領域では座標5なので[3,5]です。
468は3×3の領域では座標3、9×9の領域では座標2、27×27の領域では座標7なので[3,2,7]です。
これを計算で求めるのは簡単です。
(入力値n-1)を8で割って余りを座標とします。商が0でなければその商を再度8で割って余りを座標にする、を商が0になるまで繰り返すことで求めることができます。
例えば、468の場合、
(468-1)/8 = 58 余り 3
58/8 = 7 余り 2
7/8 = 0 余り 7
よって[3,2,7]です。
次は座標から隣接する値を求める方法です。
入力値と同じ3×3の領域にある値の場合は単純に求められます。例えば座標7にある場合、上と下には連続する値があるのでそれを求めれば良いわけです。右側は空欄ですがこれも固定的にわかります。
問題は466の上側の様に連続しない値をどの様に求めるかです。
そのため、0〜7の座標に対して上下左右に隣接する値があるかと、隣接する場合にその座標は幾つになるかのテーブルを用意します。
例えば座標0の場合、右と下には値があり、隣接する座標は上6、右1、下7、左2です。
座標3の場合は上下左に値があり（空欄は値ありとして扱います）、隣接する座標は上2、右7、下4、左空欄です。
これを使うことで座標を計算できます。
例えば入力値467の場合で考えてみます。
467の座標は[2,2,7]です。
左の座標は3×3の領域の座標が2なので1があります。なので1+2*8+6*8
2=465です。
下も同様に3+2*8+7*8
2=467です。
上を考えます。まず、3×3の領域には座標2の上には値がありません。しかし、どこかで隣接した場合には4なので4を保持します。次に9×9の領域を見ます。これも座標2なので上には値がなく、隣接する座標は4なので4を保持します。27×27の領域の座標は7なので隣接する座標があり0です。よって4+4*8+0*8
2=36が上に隣接する座標となります。
つまりどういうことかというと、3×3の座標から9×9、27×27、…と隣接する値があるサイズまで探索し、隣接する値がなければそれぞれのサイズの座標で隣接する座標の値を保持し、隣接する値があればその座標を求め、それ以上のサイズの領域は同じ座標として計算します。各サイズの座標は3×3をx=0、9×9をx=1、27×27をx=2、…として座標×8
xを足し合わせたものを求めれば良いわけです。
次に右側の様に空欄の場合ですが、これも上の場合と同じ様に3×3から順に探索します。この場合、27×27の座標が7で右は空欄になります。この様にどこかで空欄になった場合、そこは空欄として扱います。
基本的にはこれだけですが、3〜5、19〜21,27〜29,35〜37の右、5〜7、37〜39,45〜47,53〜55の下、一番上の行の上、一番左の列の左は正しく計算できません。
これらは3×3、9×9、27×27、…、の領域の外側になる場所のためうまく計算できないのです。なのでこれらは特別にチェックする必要があります。
まず、これら境界線に接する座標は最上位の領域まで隣接する値なしになります。
そして、隣接する値なししかなかった時、求めようとしている値が上か左なら値なしになります。
求めようとしている値が右側の場合、通常通り計算した値に8
座標の要素数を加えます。
求めようとしている値が下の場合は、通常通り計算した値に7*8
座標の要素数を加えます。
右と下がなぜこうなるかというと、一段階大きな領域で座標0の右側（座標1）と下（座標7）の値を求めることになるからです。
最終的に、この様にして求めた値に+1したものが答えになります。
main
入力値を数値にしてsolve()に渡し、結果をコンマで連結した文字列を印字します。
UP、RIGHT、DOWN、LEFTは座標に対して隣接する座標のマップでnilは空欄を表します。UPは現在の上、RIGHTは右、DOWNは下、LEFTは左を求める時に使用します。
HAVE_U、HAVE_R、HAVE_D、HAVE_Lは座標に対して上右下左に値があるかどうかを示します。trueは値がある、falseは値なしを示します。考え方に書いた通り空欄は値ありです。
solve(n)
問題を解きます。
入力値n-1からgetPos()で座標を求め、getSide()で上右下左の値を求めます。
結果からnilを除いてソートして返却します。
getPos(n)
入力値-1を座標に変換します。
考え方に書いた通り、商が0になるまで繰り返し8で割り、あまりを座標として配列に保持します。
isEdge(pos, have)
領域の境界にある値かどうかを判断します。
引数posはgetPos()で求めた座標、haveは定数HAVE_U、HAVE_R、HAVE_D、HAVE_Lのどれかで、現在求めている方向のものが渡されます。
考え方に書いた通り、境界にある座標の場合、最小から最大の領域までHAVE_?がfalseなので結果がfalseになります。どこかでtrueになった場合は境界上にないことになります。
結果、境界上にある場合はtrue、なければfalseを返します（returnでtrue/falseを反転している）。
getSide(pos, d)
引数posはgetPos()で求めた座標、dは上'u'、右'r'、下'd'、左'l'が渡され、求める値の方向を示します。
40〜53行目は消し忘れです。最初、特殊な処理（境界の扱い）は3×3の領域だけかと思って試行錯誤していた時に書いた処理です。無くても問題ないはずです。
dirは定数DIRから、haveはHAVEから指定された方向のテーブルを取得します。
retは返却値で計算で求めた値+1になるので初期値を1にしています。
61行目で境界かどうかをチェックします。
64〜66行目は境界で左か上の場合で、この場合は値なしが確定するのでnilを返却して終わります。
68〜83行目で指定された方向の値を求めます。
考え方に書いた通りで、隣接する値ありになるまで隣接する座標を求めつつ8iを加算し、隣接する値があった時点で（75〜82行目）それ以降は同じ座標として値を加算します。
86行目は隣接する値が境界の右側の場合、87行目は境界の下側の場合です。
retに求める場所の値が入っているのでretを返却します。