paizaハッカソンの問題(ペアプロ)

土曜日の夜、こんなものを見つけました。

女子大生とペアプロするだけの簡単なお仕事です!|paizaオンラインハッカソンVol.2

彼女はスマフォアプリでも作ってるのでしょうか。それならば、CやJavaが良いのでしょうが、僕はpythonでやってみました。

if __name__ == "__main__":
    H, W = map(int, raw_input().split())
    mat = [map(int, raw_input()) for i in xrange(H)]
    
    for i in xrange(input()):
        S, T = map(int, raw_input().split())
        pat = [[0]*S]*T

        HS = H + 1 - S
        WT = W + 1 - T

        mat1 = [mat[i:i+S] for i in xrange(HS)]

        tmp1 = []
        for mat2 in mat1:
            tmp2 = [list(mat3) for mat3 in zip(*mat2)]
            tmp1  += [tmp2[i:i+T] for i in xrange(WT)]

        N = sum(1 if pat == i else 0 for i in tmp1)

        print N

*1

キャンペーン終了してるので速度は測ってませんが。まーいいや。

この問題を解いていて面白かったのは、パターン認識の基本となるような問題であると思えた点です。(いやいや、こんなに簡単なものはコードパズルであって、パターン認識ではないという理解が普通か。。。)簡単なお題でありながら、結構骨が折れました。
パターン認識 - Wikipedia
動的計画法など別の解法はこちらへ(↓)
http://paiza.jp/poh/code_index

*1:python2で記述されています