Unkoder #05 D: N-tuple Reach

だいぶ手こずってしまった。

問題はこちら。

問題

N行 M列のマス目からなるビンゴゲームをしている。
穴が空いてないマスと開いてるマスをそれぞれ.と#で表す。
リーチの行および列が合わせてちょうど K 個であるようなマス目をひとつ答えよ。
そのようなマス目がなければ"Impossible"と答えよ。

解法

簡単のために N ≦ M になるようにしておく。
まず、K == 1のときのみ場合分けする。
このときは1列だけリーチになるようなマス目を出力する。

それ以外のときは、すべてのマスが#の状態を用意する。
まず1行目の左から#を.に置き換える。これによりリーチが1ずつ増えていく。
（K == 1のときを場合分けしたのは1列だけ.に置き換えるとリーチが2個になってしまうから）
リーチ数がKに到達したら置き換えをやめる。

1行目のすべての列を.に置き換えてもリーチ数がKに到達しない場合は、行に.を１つだけ残して他の.を次の行に移すことを繰り返していく。（下図参照）
1度の移し替えでリーチが1つ増える（ただしN == Mのときは最後の移し替えでリーチが2つ増える）

....        .###        .###        .###
####        #...        #.##        #.##
####   ->   ####   ->   ##..   ->   ##.#
####        ####        ####        ###.

最後に作り上げたマスのリーチ数を数えてKに一致するかどうかを確認する。 NとMを入れ替えていたらマスの行と列を入れ替えることも忘れない。

N, M, K = map(int, raw_input().split())
if K == 1:
    print "#" * (M - 1) + "."
    for i in xrange(N - 1):
        print "." * M
    exit()
    
flip = False    
if N > M:
    N, M = M, N
    flip = True

k = K    
A = [["#"] * M for i in xrange(N)]
for i in xrange(M):
    if k == 0: break
    A[0][i] = "."
    k -= 1

for i in xrange(1, N):
    if k == 0: break
    A[i-1][i:] = "#" * (M - i)
    A[i][i:] = "." * (M - i)
    k -= 1

cnt = 0
for i in xrange(N):
    if A[i].count(".") == 1: cnt += 1
for i in xrange(M):
    if [A[j][i] for j in xrange(N)].count(".") == 1: cnt += 1
if cnt != K:
    print "Impossible"
    exit()
        
if flip:
    A = [[A[i][j] for i in xrange(N)] for j in xrange(M)]
for line in A:
    print "".join(line)

まとめ

N == Mのとき2*N-1個のリーチが作れないのは知らなかった。