k242hd's memo

RubyとAndroidと時々TopCoder

SRM605 Div2 500をPythonで解いてみた

250に引き続き500の問題も解いてみました。

問題文はこちらから。

ざっくりと説明すると、

  • 文字列の一次元配列が渡されます(文字の行列 Board)
  • 文字列は'B'と'W'の2つの文字で構成されています。(Black and White)
  • 操作として、任意の文字列(行)の'B'と'W'を反転させることが出来ます
  • この操作はやらなくてもいいし、複数回やることも出来ます
  • 操作した後のBoardの中から、同じ文字のみからなる最大の正方形の面積を返します

うーん、分かり難くてすみません。

自分の書いたコードは以下のとおり

class AlienAndGame:
    def getNumber(self, board):
        isDiff = lambda row, left, right:\
            row[left:left+1] != row[right:right+1]      
        areaLength = 1
        for i, row in enumerate(board):
            for j, cell in enumerate(row) :
                flag = True
                shift = 1
                while flag:
                    for index in range(i, i+shift+1):
                        if index < len(board):
                            if isDiff(board[index], j, j+shift):
                                flag = False
                                break
                            if index == i+shift:
                                for columnIte in range(j+1, j+shift):
                                    if isDiff(board[index], j, columnIte):
                                        flag = False
                                        break
                        else:
                            flag = False
                    else:
                        if flag:
                            areaLength = max(areaLength, shift+1)
                            shift += 1
        return areaLength**2

かなり読みづらいですが、とりあえず解けたのでもういいやって感じです。

2重ループで基準点(正方形の左上)を決めてやって、辺の長さを1ずつ増やして条件に合うかどうか見ています。
個人的にDiv2 500の問題の中でもちょっと難しい感じがしました。

lambdaとfor~elseが使えたので、それで満足です。 (えっ?