Submission #51436284
Source Code Expand
""" <方針> - 公式解説通りです. - 一旦`N`個のタイルをどの順番で並べるかを全パターン考える.(`O(N!)`) - さらに,タイルが正方形で無い時を考慮し,縦向きか横向きかの`2`パターンの置き方を考える.(`O(2^N)`) - そのタイルを左上のマスから順番に置いていく.この時に,隙間が出ないように置いていく. - タイルを隙間なく置くために,次のタイルをどこに置くかを記録しておく. - タイルは全て使い切らなくても良いことに注意して,タイルを置いている途中で全てタイルが埋まったら早期リターンする. """ import itertools N, H, W = map(int, input().split()) AB = [list(map(int, input().split())) for i in range(N)] # `N`個のタイルをどの順番で並べるか for order in itertools.permutations(range(N)): # タイルが正方形で無い時を考慮し,縦向き横向きの`2`パターンの置き方 for dire in range(1<<N): # タイルが置かれていると要素がTrueになる二次元配列 S = [[0]*H for i in range(W)] # 次のタイルをどこにおくかを記録するtuple now = (0, 0) # 早期リターンする時にTrueになるboolean check = False # タイルが条件を満たすように置けなくなったと判断した時にTrueになるboolean bad = False # タイルを順番に並べていく. for ind in order: # タイルの縦横の長さを取得 a, b = AB[ind] # タイルを縦向きでおくか横向きでおくか if(dire&1<<ind): a, b = b, a # タイルを埋めていく for i in range(a): for j in range(b): x = now[0]+i y = now[1]+j # タイルが右にはみ出してしまう. if(x>=W): check = True bad = True break # タイルが下にはみ出してしまう. if(y>=H): check = True bad = True break # 既にタイルが置かれているのに,タイルを2重に重ねてしまう. if(S[x][y]): check = True bad = True break S[x][y] = True # 次のタイルをどこに置き始めるかを決める # なるべく上から埋めていき,その次に左から順に埋めていくイメージ while True: # タイルが置かれていないところを発見 if(not S[now[0]][now[1]]):break # タイルの位置 x, y = now # 一個右にずらす x += 1 # 右が満タンになったら if(x==W): # 一番左に戻して,一個下に進む(CR/LF のイメージ) x = 0 y += 1 # 一番下まで辿りついたら if(y==H): # タイルを綺麗に埋め尽くした可能性があるので,早期リターンする. check = True break now = (x, y) # 早期リターン if(check):break # マスをタイルで覆われていないところがあったら,badをTrueにする. for i in range(W): for j in range(H): if(not S[i][j]): bad = True break # 問題がなければYesとする. if(not bad): print("Yes") exit() print("No")
Submission Info
Submission Time | |
---|---|
Task | D - Tiling |
User | mattsunkun |
Language | Python (PyPy 3.10-v7.3.12) |
Score | 450 |
Code Size | 3681 Byte |
Status | AC |
Exec Time | 1180 ms |
Memory | 84784 KiB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 450 / 450 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | example_00.txt, example_01.txt, example_02.txt, example_03.txt |
All | example_00.txt, example_01.txt, example_02.txt, example_03.txt, hand_00.txt, hand_01.txt, hand_02.txt, hand_03.txt, hand_04.txt, hand_05.txt, hand_06.txt, hand_07.txt, hand_08.txt, hand_09.txt, hand_10.txt, hand_11.txt, hand_12.txt, hand_13.txt, hand_14.txt, hand_15.txt, hand_16.txt, hand_17.txt, hand_18.txt, hand_19.txt, hand_20.txt, hand_21.txt, hand_22.txt, hand_23.txt, hand_24.txt, hand_25.txt, hand_26.txt, hand_27.txt, hand_28.txt, hand_29.txt, hand_30.txt, hand_31.txt, hand_32.txt, hand_33.txt, hand_34.txt, hand_35.txt, random2_00.txt, random2_01.txt, random2_02.txt, random2_03.txt, random2_04.txt, random2_05.txt, random_00.txt, random_01.txt, random_02.txt, random_03.txt, random_04.txt, random_05.txt, random_06.txt, random_07.txt, random_08.txt, random_09.txt, random_10.txt, random_11.txt, random_12.txt, random_13.txt, random_14.txt, random_15.txt, random_16.txt, random_17.txt, random_18.txt, random_19.txt, random_20.txt, random_21.txt, random_22.txt, random_23.txt, random_24.txt, random_25.txt, random_26.txt, random_27.txt, random_28.txt, random_29.txt, random_30.txt, random_31.txt, random_32.txt, random_33.txt, random_34.txt, random_35.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
example_00.txt | AC | 87 ms | 83496 KiB |
example_01.txt | AC | 56 ms | 76696 KiB |
example_02.txt | AC | 55 ms | 76964 KiB |
example_03.txt | AC | 88 ms | 83528 KiB |
hand_00.txt | AC | 103 ms | 83568 KiB |
hand_01.txt | AC | 56 ms | 76696 KiB |
hand_02.txt | AC | 153 ms | 83524 KiB |
hand_03.txt | AC | 55 ms | 76540 KiB |
hand_04.txt | AC | 56 ms | 76760 KiB |
hand_05.txt | AC | 885 ms | 84444 KiB |
hand_06.txt | AC | 56 ms | 77000 KiB |
hand_07.txt | AC | 272 ms | 83948 KiB |
hand_08.txt | AC | 104 ms | 83816 KiB |
hand_09.txt | AC | 61 ms | 82236 KiB |
hand_10.txt | AC | 104 ms | 83088 KiB |
hand_11.txt | AC | 251 ms | 83760 KiB |
hand_12.txt | AC | 145 ms | 84460 KiB |
hand_13.txt | AC | 270 ms | 84112 KiB |
hand_14.txt | AC | 296 ms | 84176 KiB |
hand_15.txt | AC | 57 ms | 76616 KiB |
hand_16.txt | AC | 1180 ms | 83760 KiB |
hand_17.txt | AC | 89 ms | 83524 KiB |
hand_18.txt | AC | 930 ms | 84136 KiB |
hand_19.txt | AC | 55 ms | 76748 KiB |
hand_20.txt | AC | 758 ms | 84088 KiB |
hand_21.txt | AC | 91 ms | 83092 KiB |
hand_22.txt | AC | 336 ms | 84220 KiB |
hand_23.txt | AC | 522 ms | 84652 KiB |
hand_24.txt | AC | 663 ms | 84108 KiB |
hand_25.txt | AC | 57 ms | 77008 KiB |
hand_26.txt | AC | 1115 ms | 84324 KiB |
hand_27.txt | AC | 57 ms | 76616 KiB |
hand_28.txt | AC | 1111 ms | 84008 KiB |
hand_29.txt | AC | 209 ms | 84408 KiB |
hand_30.txt | AC | 1060 ms | 84260 KiB |
hand_31.txt | AC | 1052 ms | 84784 KiB |
hand_32.txt | AC | 495 ms | 83964 KiB |
hand_33.txt | AC | 868 ms | 84072 KiB |
hand_34.txt | AC | 628 ms | 84208 KiB |
hand_35.txt | AC | 637 ms | 83880 KiB |
random2_00.txt | AC | 58 ms | 76712 KiB |
random2_01.txt | AC | 59 ms | 76648 KiB |
random2_02.txt | AC | 59 ms | 76560 KiB |
random2_03.txt | AC | 97 ms | 83532 KiB |
random2_04.txt | AC | 59 ms | 76648 KiB |
random2_05.txt | AC | 106 ms | 83792 KiB |
random_00.txt | AC | 59 ms | 76700 KiB |
random_01.txt | AC | 59 ms | 76676 KiB |
random_02.txt | AC | 59 ms | 76784 KiB |
random_03.txt | AC | 61 ms | 76616 KiB |
random_04.txt | AC | 59 ms | 76620 KiB |
random_05.txt | AC | 128 ms | 84768 KiB |
random_06.txt | AC | 58 ms | 76548 KiB |
random_07.txt | AC | 77 ms | 82536 KiB |
random_08.txt | AC | 166 ms | 84204 KiB |
random_09.txt | AC | 95 ms | 83556 KiB |
random_10.txt | AC | 58 ms | 76632 KiB |
random_11.txt | AC | 85 ms | 83524 KiB |
random_12.txt | AC | 59 ms | 76616 KiB |
random_13.txt | AC | 265 ms | 84020 KiB |
random_14.txt | AC | 647 ms | 83416 KiB |
random_15.txt | AC | 87 ms | 83568 KiB |
random_16.txt | AC | 57 ms | 76576 KiB |
random_17.txt | AC | 57 ms | 76680 KiB |
random_18.txt | AC | 58 ms | 76672 KiB |
random_19.txt | AC | 120 ms | 83832 KiB |
random_20.txt | AC | 654 ms | 83640 KiB |
random_21.txt | AC | 109 ms | 83596 KiB |
random_22.txt | AC | 57 ms | 76452 KiB |
random_23.txt | AC | 135 ms | 83468 KiB |
random_24.txt | AC | 100 ms | 83156 KiB |
random_25.txt | AC | 103 ms | 83896 KiB |
random_26.txt | AC | 80 ms | 82800 KiB |
random_27.txt | AC | 122 ms | 83956 KiB |
random_28.txt | AC | 199 ms | 84012 KiB |
random_29.txt | AC | 1001 ms | 84400 KiB |
random_30.txt | AC | 101 ms | 83472 KiB |
random_31.txt | AC | 59 ms | 76576 KiB |
random_32.txt | AC | 105 ms | 83980 KiB |
random_33.txt | AC | 100 ms | 83588 KiB |
random_34.txt | AC | 200 ms | 84644 KiB |
random_35.txt | AC | 108 ms | 83288 KiB |