ABC345(Atcoder Beginner Contest)のA~D(A,B,C,D)問題をPythonで解説(復習)

A問題

「<===========>」左に示すような文字列になっていれば良い．
最初と最後の文字を先に調べる．
後で真ん中の文字を順番に調べる．
文字列が正しく無いことを判断したら，print("No")をし，exit()を利用して，プログラムをその場で終了させることで，最後のprint("Yes")などを実行させないようにする．

A.py

"""
<方針>
- 「<===========>」左に示すような文字列になっていれば良い．
- 最初と最後の文字を先に調べる．
- 後で真ん中の文字を順番に調べる．
- 文字列が正しく無いことを判断したら，`print("No")`をし，`exit()`を利用して，プログラムをその場で終了させることで，最後の`print("Yes")`などを実行させないようにする．
"""
# 標準入力受け取り
S = input()

# 最初の文字が"<"であるかどうか
if(S[0]!="<"):
  # "<"で無いとき，
  print("No")
  exit() # これ以上先は実行させない．
  
# 最後の文字が">"であるかどうか
if(S[-1]!=">"):
  # ">"で無いとき，
  print("No")
  exit() # これ以上先は実行させない．
  
# 「最初の次の文字」〜「最後の前の文字」までを見る．
for i in range(1, len(S)-1):
  # 文字が"="であるかどうか
  if(S[i]!="="):
    # "="で無いとき，
    print("No")
    exit() # これ以上先は実行させない．
    
# 上の条件を全てクリアしたとき，
print("Yes")

B問題

とりあえず，Xを10で割った「商」と「余り」を求める．
余りがある時は，それを繰り上げる．
折角なので，Pythonの組み込み関数divmod()で「商」と「余り」を素早く手に入れよう！！

B.py

"""
<方針>
- とりあえず，`X`を`10`で割った「商」と「余り」を求める．
- 余りがある時は，それを繰り上げる．
- 折角なので，`Python`の組み込み関数`divmod()`で「商」と「余り」を素早く手に入れよう！！
"""

# 標準入力
X = int(input())

# di: 商
# mo: 余り
di, mo = divmod(X, 10)

# 余りがある時
if(mo != 0):
  print(di+1)
# 余りが無い時
else:
  print(di)

C問題

英小文字(26種類)がそれぞれ何文字あるかを数える．
異なる英小文字同士でスワップすれば，その分だけ通りがある．
最後に，自分同士の入れ替えするパターンも記録しておく．

C.py

"""
<方針>
- 英小文字(`26`種類)がそれぞれ何文字あるかを数える．
- 異なる英小文字同士でスワップすれば，その分だけ通りがある．
- 最後に，自分同士の入れ替えするパターンも記録しておく．
"""

S = input()

# それぞれの英小文字(26種類)が何文字あるかを数える．
ls = [0]*26
for s in S:
  ls[ord(s)-ord("a")] += 1
  
# この2重ループにおけるスワップする条件
# 条件1: 自分同士のすわっぷは考えない．(なぜなら，自分同士のスワップは特殊であり，後でやるから)
# 条件2: 2回スワップしないように，iとjでは必ず，i<jとなるようにする．
ans = 0
for i in range(26):
  for j in range(26):
    # 上述の条件1, 条件2より，i<jのときのみスワップする．
    if(i<j):
      # スワップするパターン分答えを増やす．
      ans += ls[i]*ls[j]
    
# 同じ英小文字が存在する時は，答えを1だけ増やす．その時は，ちょうど一回だけ増やす必要がある．
for i in range(26):
  if(ls[i]>1):
    ans += 1
    break

print(ans)

D問題

公式解説通りです．
一旦N個のタイルをどの順番で並べるかを全パターン考える．(O(N!))
さらに，タイルが正方形で無い時を考慮し，縦向きか横向きかの2パターンの置き方を考える．(O(2^N))
そのタイルを左上のマスから順番に置いていく．この時に，隙間が出ないように置いていく．
タイルを隙間なく置くために，次のタイルをどこに置くかを記録しておく．
タイルは全て使い切らなくても良いことに注意して，タイルを置いている途中で全てタイルが埋まったら早期リターンする．

D.py

"""
<方針>
- 公式解説通りです．
- 一旦`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")

補足

関係するリンク(参考文献など)

筆者について

その他

間違いを含んでいる可能性があります．
方針と言いつつ，方針ではない感想などを書いている可能性があります．
A問題から解説がだんだん省略されます．

最後に一言

最近色々サボってて，手が回らないので，黄diffはやらないってことでDまでとしました．(ごめんねぇ)