Submission #1176890
Source Code Expand
# encoding: utf-8 #入力 temp=input().split() H=int(temp[0]) W=int(temp[1]) K=int(temp[2]) s=[[int(i) for i in input()]for i in range(H)] """ このプログラムでは、まず7~9という大きな数字を核として、それぞれが最大値になるように隣接の最大を結合して拡大していく。 上手く行けば、隣の隣まで計算したうえでの最大値が取れる拡大方法を考える。 注意:実行時間に応じて、核にする数字の下限を変化させること。 手順 まず、大きな数字がどこにあるかをexistHighをTrueにすることで示す。 次に、それぞれに応じて9個になるまで拡大して、獲得できる点数pointに、その組み合わせをplaceとして、placeをpointに、 [点数,[組み合わせ]]の形式でappendする。 後はsortして、逆順にansに組み合わせをappendしていく。 随時その組み合わせの要素がusedにてFalseであることを確認してから、used=Trueにすることで、 被ったときはansに組み込まないようにする。 """ #点数と場所のデータ tempAns=[] #答え ans=[] #7~9の存在を考える existHigh=[[False for i in range(W)] for j in range(H)] for i in range(H): for j in range(W): if s[i][j]>6: existHigh[i][j]=True #実行 for i1 in range(H): for j1 in range(W): #高い数字である かつ 使用していない if existHigh[i1][j1]==True: #今回のピースで使うマスと点数(i,j)<=(H,W) tempPiece=[[i1,j1]] tempPoint=s[i1][j1] #使用済みか否か tempUsed=[[False for i in range(W)] for j in range(H)] #使用を宣言 tempUsed[i1][j1]=True #K-1個追加していきます for temp0 in range(K-1): #隣接しているマスの最大値とその場所 tempMax=-1 tempMaxSquare=[-1,-1] for tempSquare in tempPiece: #前回が2個同時進めの場合 #上端でない場合 if 0<tempSquare[0]: if s[tempSquare[0]-1][tempSquare[1]]>tempMax and tempUsed[tempSquare[0]-1][tempSquare[1]]==False: tempMax=s[tempSquare[0]-1][tempSquare[1]] tempMaxSquare=[tempSquare[0]-1,tempSquare[1]] #下端でない場合 if tempSquare[0]<H-1: if s[tempSquare[0]+1][tempSquare[1]]>tempMax and tempUsed[tempSquare[0]+1][tempSquare[1]]==False: tempMax=s[tempSquare[0]+1][tempSquare[1]] tempMaxSquare=[tempSquare[0]+1,tempSquare[1]] #左端でない場合 if 0<tempSquare[1]: if s[tempSquare[0]][tempSquare[1]-1]>tempMax and tempUsed[tempSquare[0]][tempSquare[1]-1]==False: tempMax=s[tempSquare[0]][tempSquare[1]-1] tempMaxSquare=[tempSquare[0],tempSquare[1]-1] #右端でない場合 if tempSquare[1]<W-1: if s[tempSquare[0]][tempSquare[1]+1]>tempMax and tempUsed[tempSquare[0]][tempSquare[1]+1]==False: tempMax=s[tempSquare[0]][tempSquare[1]+1] tempMaxSquare=[tempSquare[0],tempSquare[1]+1] #周囲が0しかない場合 if tempMax<1: break #pointとplaceの更新(1つ場所を追加) tempUsed[tempMaxSquare[0]][tempMaxSquare[1]]=True tempPoint*=s[tempMaxSquare[0]][tempMaxSquare[1]] tempPiece.append(tempMaxSquare) #データを代入 else: tempAns.append([tempPoint,tempPiece]) #点数順にする(ただし昇順) tempAns.sort() #点数の高い方から使っていく。 #もしused=Trueの場所があったらスキップ #全部Falseなら、ans候補に入れて全部True used=[[False for i in range(W)] for j in range(H)] #print(tempAns) while len(tempAns)>1: #print(len(tempAns)) #print(len(ans)) data=tempAns.pop() piece=data[1] for square in piece: if used[square[0]][square[1]]: break else: ans.append(piece) for square in piece: used[square[0]][square[1]]=True continue #被っていた場合、再度pieceを作ってtempAnsに入れる。 for square in piece: if used[square[0]][square[1]]==False and s[square[0]][square[1]]>6: tempPiece=[[square[0],square[1]]] break else: continue #使用済みか否か tempUsed=[[False for i in range(W)] for j in range(H)] #使用を宣言 tempUsed[tempPiece[0][0]][tempPiece[0][1]]=True tempPoint=s[tempPiece[0][0]][tempPiece[0][1]] #K-1個追加していきます for temp0 in range(K-1): #隣接しているマスの最大値とその場所 tempMax=-1 tempMaxSquare=[-1,-1] for tempSquare in tempPiece: #前回が2個同時進めの場合 #上端でない場合 if 0<tempSquare[0]: if s[tempSquare[0]-1][tempSquare[1]]>tempMax and tempUsed[tempSquare[0]-1][tempSquare[1]]==False and used[tempSquare[0]-1][tempSquare[1]]==False: tempMax=s[tempSquare[0]-1][tempSquare[1]] tempMaxSquare=[tempSquare[0]-1,tempSquare[1]] #下端でない場合 if tempSquare[0]<H-1: if s[tempSquare[0]+1][tempSquare[1]]>tempMax and tempUsed[tempSquare[0]+1][tempSquare[1]]==False and used[tempSquare[0]+1][tempSquare[1]]==False: tempMax=s[tempSquare[0]+1][tempSquare[1]] tempMaxSquare=[tempSquare[0]+1,tempSquare[1]] #左端でない場合 if 0<tempSquare[1]: if s[tempSquare[0]][tempSquare[1]-1]>tempMax and tempUsed[tempSquare[0]][tempSquare[1]-1]==False and used[tempSquare[0]][tempSquare[1]-1]==False: tempMax=s[tempSquare[0]][tempSquare[1]-1] tempMaxSquare=[tempSquare[0],tempSquare[1]-1] #右端でない場合 if tempSquare[1]<W-1: if s[tempSquare[0]][tempSquare[1]+1]>tempMax and tempUsed[tempSquare[0]][tempSquare[1]+1]==False and used[tempSquare[0]][tempSquare[1]+1]==False: tempMax=s[tempSquare[0]][tempSquare[1]+1] tempMaxSquare=[tempSquare[0],tempSquare[1]+1] #周囲が0しかない場合 if tempMax<1: break #pointとplaceの更新(1つ場所を追加) tempUsed[tempMaxSquare[0]][tempMaxSquare[1]]=True tempPoint*=s[tempMaxSquare[0]][tempMaxSquare[1]] tempPiece.append(tempMaxSquare) #データを代入 else: tempAns.append([tempPoint,tempPiece]) tempAns.sort() #RE対策。ちゃんと答えの形式になってるかの確認 #Kマスの塊の数 temp=len(ans) #使用した場所が被ってないか再度見る used=[[False for i in range(W)] for j in range(H)] #失敗時のindex確認 badlist=[] for i in range(temp): #要素がちゃんと8個あるかどうか if len(ans[i])!=8: badlist.append(i) continue #場所が被ってないか for j in range(K): if used[ans[i][j][0]][ans[i][j][1]]==False: used[ans[i][j][0]][ans[i][j][1]]=True else: badlist.append(i) break bad=len(badlist) #結局いくつ塊が出来たのか print(temp-bad) #順番に書いてく for i in range(temp): #失敗時はスキップ if not i in badlist: for j in range(K): sent=str(ans[i][j][0]+1) sent+=" " sent+=str(ans[i][j][1]+1) print(sent)
Submission Info
Submission Time | |
---|---|
Task | A - Multiple Pieces |
User | toma25 |
Language | Python (3.4.3) |
Score | 925329 |
Code Size | 7024 Byte |
Status | AC |
Exec Time | 300 ms |
Memory | 4316 KB |
Judge Result
Set Name | test_01 | test_02 | test_03 | test_04 | test_05 | test_06 | test_07 | test_08 | test_09 | test_10 | ||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 93338 / 1343058 | 87992 / 1343058 | 95266 / 1343058 | 87799 / 1343058 | 99716 / 1343058 | 89195 / 1343058 | 95265 / 1343058 | 85468 / 1343058 | 96580 / 1343058 | 94710 / 1343058 | ||||||||||||||||||||
Status |
|
|
|
|
|
|
|
|
|
|
Set Name | Test Cases |
---|---|
test_01 | subtask_01_01.txt |
test_02 | subtask_01_02.txt |
test_03 | subtask_01_03.txt |
test_04 | subtask_01_04.txt |
test_05 | subtask_01_05.txt |
test_06 | subtask_01_06.txt |
test_07 | subtask_01_07.txt |
test_08 | subtask_01_08.txt |
test_09 | subtask_01_09.txt |
test_10 | subtask_01_10.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
subtask_01_01.txt | AC | 290 ms | 4188 KB |
subtask_01_02.txt | AC | 258 ms | 4188 KB |
subtask_01_03.txt | AC | 300 ms | 4188 KB |
subtask_01_04.txt | AC | 268 ms | 4188 KB |
subtask_01_05.txt | AC | 299 ms | 4188 KB |
subtask_01_06.txt | AC | 261 ms | 4188 KB |
subtask_01_07.txt | AC | 289 ms | 4316 KB |
subtask_01_08.txt | AC | 253 ms | 4188 KB |
subtask_01_09.txt | AC | 266 ms | 4188 KB |
subtask_01_10.txt | AC | 289 ms | 4188 KB |