ABC218 C - Shapes から学んだ

14225 ワード
AtCoder Python AtCoderBeginnerContest Python テキストリンク

時間一杯つかったが、time out。

納得いったものをコンテスト後に入力したが WA だった。

改善点1 配列の回転に Append は不向き

rotated_bad.py
def one(S,T):
    lis = []
    for _ in range(N):
        lis.append([])

    for w in range(N):
        for h in range(N-1,-1,-1):
            lis[w].append(T[h][w])

    S = make(S)
    lis = make(lis)
    #print(S)
    #print(lis)
    try:
        if check(S,lis):
            return True
    except:
        pass

良く書いたな、俺。
append を使う場合、4 回転、それぞれの場合における
def を用意する必要があり、非効率

有識者の知恵を借りると
空欄の配列を用意し、S(orT) を 90 度回転させて代入する関数があれば
関数は一つで済む事が分かった。

rotated_good.py
def rotated(S):
    lis = [[" "] * N for _ in range(N)]
    for h in range(N):
        for w in range(N):
           lis[w][N-1-h] = S[h][w]
           #lis[i][j] = S[j][N-1-i]

    #for h in range(N):
    #    print("".join(lis[h]))
    #print()
    return lis

改善点2 平行移動と言われたら素直に平行移動しよう

当初考えたのは、
図形を含む最小の四角形を切り抜き、
S と T で行い、比較した。
しかし、Wa x 5 が残ってしまった。

平行移動のイメージ、以下の赤線の交点を左上に持っていく。
残りのセルは "." とし、N x N の構成。

とりあえず。。赤線の交点を探す。
つまり、"#" が配置されている最小の (i,j) を探す。

make.py
def make(S,T):

    s_min_i = N
    s_min_j = N
    t_min_i = N
    t_min_j = N

    for h in range(N):
        for w in range(N):
            if S[h][w] == "#":
                s_min_i = min(s_min_i,h)
                s_min_j = min(s_min_j,w)
            if T[h][w] == "#":
                t_min_i = min(t_min_i,h)
                t_min_j = min(t_min_j,w)

更に、あまり枠には "." としつつ、
T,S を比較していく。

make.py
def make(S,T):

    s_min_i = N
    s_min_j = N
    t_min_i = N
    t_min_j = N

    for h in range(N):
        for w in range(N):
            if S[h][w] == "#":
                s_min_i = min(s_min_i,h)
                s_min_j = min(s_min_j,w)
            if T[h][w] == "#":
                t_min_i = min(t_min_i,h)
                t_min_j = min(t_min_j,w)

    Schar = ""
    Tchar = ""
    for h in range(N):
        for w in range(N):
            si = s_min_i + h
            sj = s_min_j + w
            if (si < N and sj < N):
                Schar = S[si][sj]
            else:
                Schar = "."

            ti = t_min_i + h
            tj = t_min_j + w
            if (ti < N and tj < N):
                Tchar = T[ti][tj]
            else:
                Tchar = "."

            if Tchar != Schar:
                #print(False)
                return False
    return True

あとは、4回転して試すだけ

check.py
for _ in range(4):
    S = rotated(S)
    if make(S,T):
        print("Yes")
        exit()
print("No")