AtCoder Beginner Contest 258 B問題 Number Box

Number Box### 問題 atcoder.jp

提出解答

atcoder.jp

問題の概要

$N$ 行 $N$ 列のマス目がある. $i$ 行 $j$ 列目の各マス目には数字 $A_{i,j}$ が書かれている.

最初に上下左右斜めの8個の向きから1つの向きを決め, 好きなマスからその決めた方向に $(N-1)$ 回進む. ただし, 上端と下端, 左端と右端もそれぞれ隣接しているとする.

このとき, $N$ 個のマスを通ることになるが, 通ったマスに書かれている数字を左から書き, 書いた数字の列を $N$ 桁の整数をみなした時, 可能な整数の最大値を求めよ.

制約

$1 \leq N \leq 10$
$1 \leq A_{i,j} \leq 9$

解法

開始となるマスの候補が $N^2$ 通り, 向きの候補が $8$ 通りなので, 計 $8N^2$ 通りである. 従って, 各候補ごとに実際の結果をシミュレーションすることにより, 1候補につき $N$ ステップで計算できるので, 全ての候補における結果を定数 $T$ を用いて $8TN^3$ ステップ程度で計算できる.