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
AC × 4
AC × 82
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