yukicoder #359: 門松行列

本番で１時間くらい頑張って書いたけど力尽きた。
解説読んで「あーなるほど！」と思ったけど一発で通せなかった。なかなかに悔しい問題。

問題

No.359 門松行列 - yukicoder
２つ歯抜けになっている3*3のマス目がある。
タテ・ヨコ・ナナメがすべて門松列になるように長さLの末を２分割して配置したい。分割方法の数を答えよ

考えたこと (コンテスト時。筋の悪い思考)

ひとまず歯抜けのマス目以外で門松列とならない部分があれば問答無用で解は0である。
以下３通りを考える。
(1) 歯抜けのマスが真ん中だった時
　歯抜けのマスに入るべき数値は「両端のマスの最大値より大きい or 両端のマスの最小値より小さい」
(2) 歯抜けのマスが端であり、真ん中のマスの値＞逆端のマスの値の時
　歯抜けのマスに入るべき数値は「逆端のマス以外 and 真ん中のマスより小さい」
(3) 歯抜けのマスが端であり、真ん中のマスの値＜逆端のマスの値の時
　歯抜けのマスに入るべき数値は「逆端のマス以外 and 真ん中のマスより大きい」
この条件のもとにそれぞれのマスに入りうる長さの区間を更新すれば良い。
区間更新方法は
「(1)ある区間[l,r:を禁止する」「((2),(3)の前半)ある値pを禁止する 」「((2)後半)ある値pより小さい 」「((3)後半)ある値pより大きい」で、
これらに加えて「となる区間の計算」と、区間のマージを実装すれば良い。

……まで、一通り実装し、example 1が正しい答えを返す所まで来て、
この考え方だと２つ歯抜けとなってる列の処理で大変なことになることに気付いた（ここで心が折れた）。

解説を読んで

yukicoder
なるほど！と思った。
要するに、(1),(2),(3)をみるとうっすら見えるように、マス目に入るべき数値の境界線は既存のますの数値±１に（ほぼ）限られる
この考えのもとに歯抜けのマスの数値として検証すべき区間を算出し、各区間それぞれが題意を満たすかをシミュレートすればよい。

……ただし、これだけ実装して提出すると、以下の時にWAを出す。

要するに、２つ歯抜けとなっている列の処理が必要ということである。

改めて条件を書いてみると
(4)両端が歯抜けの場合
「歯抜けの値２つはそれぞれ異なり、共に中央の値より大きい or 小さい」
(5)真ん中と端が歯抜けの場合
　(5-a) 真ん中の歯抜け＞端の歯抜けの場合：「端の歯抜け！＝逆端の値 and 真ん中の歯抜け＞逆端の値」
(5-b) 真ん中の歯抜け＜端の歯抜けの場合：「端の歯抜け！＝逆端の値 and 真ん中の歯抜け＜逆端の値」
と言えるが、(4),(5)どちらとも、２つの歯抜けの大小関係が異なるポイント（L/2)が境界条件として必要であることがわかる。

コード

def rangesplit(L,p):
    ret=[]
    for l,r in L:
        if r<p:
            ret.append((l,r))
        elif p<l:
            ret.append((l,r))
        else:
            if l<=p-1 :
                ret.append((l,p-1))
            if p+1<=r :
                ret.append((p+1,r))
            ret.append((p,p))
    return ret
def isKadomatsu(A):
    if A[0]==A[1] or A[1]==A[2] or A[0]==A[2]:
        return False
    elif A[0]<A[1] and A[1]>A[2]:
        return True
    elif A[0]>A[1] and A[1]<A[2]:
        return True
    return False


T=int(raw_input())
for ti in range(T):
    L=int(raw_input())
    A=[map(int,raw_input().split()) for i in range(3)]
    # l is too short
    if L==1:
        print 0
        continue 

    # set where is blankpoint
    blank=[]
    ranges=[(1,L-1)]
    ranges=rangesplit(ranges,L/2)
    for i in range(3):
        for j in range(3):
            if A[i][j]==0:
                blank.append((i,j))
            else:
                if A[i][j]< L:
                    ranges=rangesplit(ranges,A[i][j])
                    ranges=rangesplit(ranges,L-A[i][j])
    checkList=[[(0,0),(0,1),(0,2)],
               [(1,0),(1,1),(1,2)],
               [(2,0),(2,1),(2,2)],
               [(0,0),(1,0),(2,0)],
               [(0,1),(1,1),(2,1)],
               [(0,2),(1,2),(2,2)],
               [(0,0),(1,1),(2,2)],
               [(0,2),(1,1),(2,0)]]
    
    ans=0
    for l,r in ranges:
        Btmp=A
        Btmp[blank[0][0]][blank[0][1]]=l
        Btmp[blank[1][0]][blank[1][1]]=L-l
        ok=True
        for line in checkList:
            for (p,q) in line:
                B=[A[p][q] for (p,q) in line]
                if not isKadomatsu(B):
                    ok=False
                    break
        if ok:
            ans+=r-l+1
    print ans

……日数置いてから「うん？」と思ったけど、これBtmp作った意味が全く無かったというか、
その後でB=[A[p][q]...]と書いてる時点で、本来意図した動きを実現するコードではなかった。

c++でvectorの=が要素のコピーだからうっかりこう言う書き方しちゃったけど、pythonでのlistの代入は参照渡しなので、
Btmpの値を書き換える=>Aの値も書き換えられる=> B=[A[p][q]...]と書いても書き換えた値が参照される、という形で動いてしまった様子。
今回のケースは各Btmpの書き換え操作が「歯抜けますに値を代入する」という相互に悪影響のない操作だったためにこれでも通ってしまった、というオチである。
Btmpを全部Aに書き換えたほうがスマートでしたね