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までとしました．(ごめんねぇ)