問題の説明

ゲーム開発者「Jordy」はクレーン型の抽出機をモバイルゲームに変えようとしている.
ゲームの面白さを高めるために、「Jordie」は画面レイアウトとルールをゲームロジックに反映し、以下のようにします.
ゲーム画面は「1 x 1」サイズのセルからなる「NxN」サイズの正斜角メッシュで、上部にクレーン、右側にバスケットがあります.(上の図は、サイズが「5 x 5」の例を示しています).各格子間には様々なぬいぐるみがあり、ぬいぐるみのない格子は空いています.すべての人形は「1 x 1」の大きさのメッシュを占め、メッシュの一番下から順番に積み上げられます.ゲームユーザーはクレーンを左右に動かし、停止した位置から一番上の人形を持ち上げることができる.拾った人形はかごの中に積み上げられ、かごの一番下の格子から人形は順番にかごの中に積み上げられます.下の図は[1番、5番、3番の位置で人形を順番にかごに入れる様子を示しています.
同じ形の2人の人形が連続してかごに積まれると、2人の人形が爆発してかごから消えてしまいます.上の状態で、次に[5番]の位置で人形をかごに積み上げると、同じ形の人形が2つ消えてしまいます.

クレーンが作動すると、人形が挟まないことはありませんが、人形がないところでクレーンを起動すれば、何も起こりません.また、バスケットが十分大きく、すべての人形を収容できると仮定します.(図中、スクリーン表示制限は5コマのみ表示)
ゲーム画面上の格子状態の2次元配列板と人形を挟むために、起動クレーンの位置を含む配列動作をパラメータとして指定した場合、solution関数を完了し、クレーンをすべて起動させ、爆発して消えた人形の個数を返します.

せいげんじょうけん

board配列は2次元配列であり、サイズは「5 x 5」または「30 x 30」より大きい.
boardの各セルには、0または100より大きい整数が含まれています.
0はスペースです.
1から100の数字はそれぞれ異なる人形の形を表し、同じ数字は同じ形の人形を表す.
moves配列のサイズは1000を超えない.
moves配列の各要素の値は1より大きく、board配列の水平サイズよりも自然数です.

問題を解く

入力値boardは2 Dリスト配列から構成されます.
上記の問題の説明では、図に示す各スキームを使用してクレーンゲームを表示できます.
board配列では、「0」に相当する位置は人形がいないことを意味します.
逆に、人形の種類が異なる数字で表現されていることが確認できます.
なお、制限事項ではクレーンの移動は板配列内でのみ行うことができる.
このときクレーンは常に左右に移動します.
クレーンが降りる時だけ人形がある場合、スタックで問題に近づくと、少し近づきやすいです.

解法

まず、人形を入れたバスケットをbucketという空のリストに実装します.
また、爆発で消えた人形を追加するため、答え値を0にします.

bucket = []
answer = 0

その後、クレーンの移動状況に応じて、人形をバケツに入れて考えます.

1.クレーンが降りるところに人形がいない場合

for i in moves:
	for k in range(len(board)):
  		if board[k][i-1] == 0:
        		continue
# moves의 요소값은 인덱스를 표현하지 않으므로 i-1을 통해 인덱스값으로 치환해준다.

2.クレーンが降りるところに人形がいる場合

for i in moves:
	for k in range(len(board)):
  		if board[k][i-1] != 0:
        		bucket.append(board[i][i-1])    # 바구니에 인형을 담는다.
                	board[k][i-1] = 0    # 인형이 빠졌으므로 0 값으로 변환

2-1. もしかごの中の人形がなくなったら。

if bucket[-1:] == bucket[-2:-1]:
	answer += 2    # 같은 인형이 2개가 쌓였을 경우 터져서 사라지기 때문에 그 갯수만큼 더해준다.
    	bucket = bucket[:-2]    # 바구니에 남은 인형만 구현
break

上のコードは一度に以下のように表現されます.

def solution(board, moves):
    bucket = []
    answer = 0
    for i in moves:
        for k in range(len(board)):
            if board[k][i-1] == 0:
                continue
            elif board[k][i-1] != 0:
                bucket.append(board[k][i-1])
                board[k][i-1] = 0
                if bucket[-1:] == bucket[-2:-1]:
                    answer += 2
                    bucket = bucket[:-2]
                break
    return answer

実行結果

採点結果