JOI難易度６ JOI紋章

問題原文

atcoder.jp

問題要旨

J, O, I で構成される 縦 マス、横 マスの大グリッドに、2×2の同じく J, O, I で構成される小グリッドを重ねることを考える。
大グリッドの１マスを好きな文字に変更してよいとき（変えなくてもよい）、大グリッドの全ての2×2の範囲について、小グリッドと同じものを最大でいくつ作ることができるか？

• 

解法

ある１マスを変えた時、大グリッドの全ての2×2の範囲について計算していると間に合わない。
しかし実際に影響があるのは、変化したマスを X とすると、「Xが左上」「Xが右上」「Xが左下」「Xが右下」とするような2×2の範囲だけである。

よって最初の状態において小グリッドと同じものがいくつあるかを数えておいて、全てのマスについて J, O, I に変えた場合の変化量を周囲４パターンのみについて計算して、結果を得れば良い。

実装

TLが１秒とすごい厳しい。
numpyを使う、あるいはPyPy2で限界高速化をすると間に合う。
PyPy2限界高速化をすると通るけど999msなのでうーんwという感じ

def main():
    import sys
    H, W = map(int, sys.stdin.readline().split())
    G = [list(sys.stdin.readline().strip()) for _ in range(H)]
    F = ''.join([sys.stdin.readline().strip() for _ in range(2)])

    match_cnt = 0
    for h in range(H - 1):
        for w in range(W - 1):
            s = G[h][w] + G[h][w + 1] + G[h + 1][w] + G[h + 1][w + 1]
            if F == s:
                match_cnt += 1

    ans = match_cnt
    for to in ['J', 'O', 'I']:
        for hy in range(H):
            for wx in range(W):
                tmp_cnt = 0
                # a b c
                # d e f
                # g h i
                a = G[hy - 1][wx - 1] if ((hy - 1 >= 0) and (wx - 1 >= 0)) else ''
                b = G[hy - 1][wx] if hy - 1 >= 0 else ''
                c = G[hy - 1][wx + 1] if ((hy - 1 >= 0) and (wx + 1 < W)) else ''
                d = G[hy][wx - 1] if (wx - 1 >= 0) else ''
                e = G[hy][wx]
                f = G[hy][wx + 1] if (wx + 1 < W) else ''
                g = G[hy + 1][wx - 1] if ((hy + 1 < H) and (wx - 1 >= 0)) else ''
                h = G[hy + 1][wx] if (hy + 1 < H) else ''
                i = G[hy + 1][wx + 1] if ((hy + 1 < H) and (wx + 1 < W)) else ''

                tmp_cnt -= (F == e + f + h + i)
                tmp_cnt += (F == to + f + h + i)

                tmp_cnt -= (F == d + e + g + h)
                tmp_cnt += (F == d + to + g + h)

                tmp_cnt -= (F == b + c + e + f)
                tmp_cnt += (F == b + c + to + f)

                tmp_cnt -= (F == a + b + d + e)
                tmp_cnt += (F == a + b + d + to)

                ans = max(ans, match_cnt + tmp_cnt)

    print(ans)


if __name__ == '__main__':
    main()

感想

JOIはPythonにやさしいTLにして