ABC345 A-D問題の解説（Python）

はじめに

AtCoder Beginner Contest（略称：ABC）とは、AtCoderが週末に開催している、競技プログラミングコンテストのことです。

A-D問題について、自身の復習も兼ねて説明できればと思います。誤った記述やより良い解法などあれば、コメントをいただけると幸いです。

ABC345

A – Leftrightarrow

問題

A問題

< と = と > のみからなる文字列が与えられます。その文字列が、双方向矢印型の文字列であるか判定する問題です。双方向矢印型とは、<===>のようなもののことを言います。

思考の筋道

問題文の条件通りに素直に分岐処理を書きましょう。

繰り返し文で、文字列を一文字ずつチェックしていくのでもOKです。

コード

S = input()

if S == "<" + "=" * (len(S) - 2) + ">":
    print("Yes")
else:
    print("No")

B – Integer Division Returns

問題

B問題

整数 X を 10 で割り、小数点以下を切り上げた値を求める問題です。

思考の筋道

Pythonでは切り上げが行える math.ceil 関数があります。しかし、math.ceil(x / 10) では、計算誤差の影響を受けるため、x / 10ではなく x // 10 を使う方法を考えましょう。

xが10で割り切れるかどうかで場合分けします。割り切れる場合は、商が答えになります。割り切れない場合は、商に1足したものが答えになります。これで、切り上げの処理を表現できています。

x = 30のとき
30÷10=3
割り切れるので、そのまま3

x = 35のとき
35÷10=3余り5
余りが発生しているので、3+1=4

なお、別解として、(x + 9)を10で割った商を答えとする方法もあります。この解法だと、場合分けが不要になります。

コード

X = int(input())
if X % 10 == 0:
    print(X // 10)
else:
    print(X // 10 + 1)

C – One Time Swap

問題

C問題

文字列Sが与えられます。一度だけ、Sのいずれかの位置の2文字を交換します。この操作で起こり得る文字列が何通りあるか求める問題です。

思考の筋道

S内に同じ文字が存在しないケース（例：”abcde”）から考えましょう。

この場合はどの2文字を交換しても、それぞれ異なる文字列となります。全文字数 n から 2 文字を選ぶ組合せの数がそのまま答えになります。

\({}_5 \mathrm{ C }_2 = 10\)

次にS内に同じ文字が存在するケース（例：”aabbc”）を考えましょう。

a と a など同じ文字を交換しても、交換の前後で変化がありません。これらの組合せを全体から引きましょう。そのためにはS内で各アルファベットが何回登場するのか事前に調べておく必要があります。

なお、交換前と同じ文字列も1通りとしてカウントできるため、最後にプラス1することを忘れないようにしましょう。

\({}_5 \mathrm{ C }_2 – {}_2 \mathrm{ C }_2 – {}_2 \mathrm{ C }_2 + 1 = 9\)

コード

import string
S = input()
n = len(S)

d = {i: 0 for i in string.ascii_lowercase}
for char in S:
    d[char] += 1

count = n * (n - 1) // 2
flg = False
for char in d:
    if d[char] >= 2:
        count -= (d[char] * (d[char] - 1)) // 2
        flg = True
if flg:
    count += 1

print(count)

D – Tiling

問題

D問題

H行W列のマス目とN枚の長方形タイルがあります。これらの長方形タイルで全てのマス目を埋めることができるかを判定する問題です。使用しないタイルがあってもよいです。タイル同士が重なってはいけません。

思考の筋道

Nは7以下、HとWは10以下と値が非常に小さいです。地道に配置していきましょう。しかしその実装が大変でした。

以下の流れで考えます。

使うタイルの組を決定する
使うタイルの組を決定します。なお、選んだタイルの面積の合計が、マスの面積の合計HWと等しくなければ、その時点でアウトなので、次の組にいきましょう。
タイルを使う順番を決定する
組の中で、タイルを使う順番を決定します。なぜ順番を決める必要があるかというと、その順番に基づいて、左上から詰めるようにタイルを配置していくためです。
左上のマスから調べ、どこに空きマスか調べる
はじめに見つけた空きマスを、これから置くタイルの左上の角として考えます。
タイルを配置する
タイルを配置する際、そのタイルが盤からはみ出してしまったり、別のタイルと重なってしまう場合は、その順番では配置できないということです。諦めて次のケースにいきましょう。タイルが配置できた場合は、それが最後のタイルであれば配置完了です。まだ次のタイルがあれば、3のステップに戻ります（再帰処理）。

配置完了するケースが 1 つでもあればYesを出力し、1つもなければNoを出力しましょう。

下のコードはこの流れを実装したものですが、もっと上手く書けるかもしれません。

コード

from itertools import combinations, permutations

N, H, W = map(int, input().split())
blocks = [list(map(int, input().split())) for _ in range(N)]

def can_place(idx, muki):
    if idx == len(chosen_order):
        return True

    h, w = blocks[chosen_order[idx]]
    if muki:
        h, w = w, h
    start_i, start_j = 0, 0
    flg = False
    for i in range(H):
        for j in range(W):
            if m[i][j] == 0:
                start_i, start_j = i, j
                flg = True
                break
        if flg:
            break
    for di in range(h):
        for dj in range(w):
            if start_i + di >= H or start_j + dj >= W or m[start_i + di][start_j + dj] == 1:
                return False
    for di in range(h):
        for dj in range(w):
            m[start_i + di][start_j + dj] = 1
    idx += 1
    for muki in range(2):
        if can_place(idx, muki):
            return True

for i in range(1, N + 1):
    for chosen_blocks in combinations(range(N), i):
        if sum([blocks[x][0] * blocks[x][1] for x in chosen_blocks]) != H * W:
            continue
        for chosen_order in permutations(chosen_blocks):
            for muki in range(2):
                m = [[0] * W for _ in range(H)]
                idx = 0

                if can_place(idx, muki):
                    print("Yes")
                    exit()
print("No")