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が使えたので、それで満足です。 (えっ?