🚚

Atcoder - ABC345 A - D まで復習解説

2024/03/17に公開

競技プログラミング

AtCoder

abc345

tech

ABC345 A - D を復習してまとめてみました。初学者の方の参考になれば幸いです。

A - Leftrightarrow

問題文
<, =, > のみからなる文字列 $S$ が与えられます。 $S$ が双方向矢印型の文字列であるか判定してください。ただし、文字列 $S$ が双方向矢印型の文字列であるとは、ある正整数
$k$ が存在して、 $S$ が 1 個の < 、 $k$ 個の = 、1 個の > をこの順に連結した長さ
$(k+2)$ の文字列であることをいいます。

<=> や <======> みたいな矢印に見える文字かどうかを判定してくださいという問題です。

いくつかザッと解き方を考えてみます。

1. for 文で前からチェックする

S = list(input() と $S$ をリストとして管理します。

先頭の S[0] が <
末尾の S[-1] が <
それ以外が =

であるかを前から for でチェックしていきます。 $S$ の長さは 3 以上 100 以下という制約があるので文字が１文字しかなく先頭と末尾がどちらも $0$ であるみたいなことを考慮しなくて良いので楽です。

たくさん判定条件がある場合は条件を満たさないのが判明した瞬間 No を出力して exit したほうが実装が楽なのでそうしてみました。

S = list(input())
N = len(S)

if S[0] != "<":
    print("No")
    exit()

if S[-1] != ">":
    print("No")
    exit()

for i in range(1, N - 1):
    if S[i] != "=":
        print("No")
        exit()

print("Yes")

2. 考えられる双方向矢印型のいずれかと一致するかチェックする

$S$ の長さは 3 以上 100 以下という制約より 双方向矢印型 として考えられる文字列は <=>, <==>, <===...100個並ぶ...===> のいずれかです。
従って $S$ がこのいずれかであるか判定しそうであれば Yes を、そうでなければ No を出力しましょう。

S = input()

for i in range(1, 101):
    T = f"<{'=' * i}>"
    if S == T:
        print("Yes")
        exit()

print("No")

3. 正規表現を用いる

今回のような「= が１つ以上」というような条件の場合、正規表現を用いることもできます。
今回の正規表現は "^<={1,}>$" です。この辺は ChatGPT なども得意なので ChatGPT に質問しちゃうのが早いかもです。

import re

S = input()
pattern = r"^<={1,}>$"
if bool(re.match(pattern, S)):
    print("Yes")
else:
    print("No")

B - Integer Division Returns

10 で割った後に切り上げる問題です。単純に 10 で割ってしまうと一旦小数になってしまいますが、小数は誤差を含むことがあります。例えば 10 ÷ 10 = 1.000000001 となり切り上げると 2 になってしまうということがあります。

このようなことがあるので競技プログラミングではできる限り小数を含む計算を行わないようにするのがセオリーです。

例えば、今回のような $a$ を $b$ で割るような切り上げの問題の場合、先に $b - 1$ を $a$ に足して $b$ で割る、すなわち $(a + (b - 1)) / b$ を切り上げとみなして行うのがセオリーです。(Python の場合は (a + (b - 1)) // b とし整数解が得られるようにしましょう)

なぜこの式で切り上げになるのか考えます。

切り上げの場合分けを考えてみると

$a$ が $b$ で割り切れる → 切り上げを行う必要がない。
$a$ が $b$ で割り切れない → 切り上げを行う必要がある。すなわち $a$ を $b$ で割った商に１足す必要がある

と「 $a$ が $b$ で割り切れるか」でいちいち場合分けをする必要があり面倒です。

ここで $a$ を $b$ で割った時の商を $c$ とし、それぞれのケースで $a$ に $b - 1$ を足した後に $b$ で割った時の商を考えます。

$a$ が $b$ で割り切れる → $(a + (b - 1)) / b = a / b + (b - 1) / b$ と考えると、前者の商は $c$ で、後者は $b - 1$ 割る $b$ は必ず $0$ より小さいので期待通り切り上げができていると言えます。
$a$ が $b$ で割り切れない → $a = c \times d + e$ とおくと $e$ は必ず $1$ 以上です。なぜなら $0$ だと $a$ が $b$ で割り切れてしまい矛盾するからです。そこに $b - 1$ を足すと $e$ は必ず $1$ 以上なので $e + b - 1$ は $b$ より大きくなります。したがって $(a + (b - 1)) / b$ の商は必ず $c$ + 1 となり、これは期待通り切り上げができていると言えます。

以上より、 $(a + (b - 1)) / b$ は整数で情報を扱いつつ上記の切り上げの場合分けを自動で行ってくれます。非常に便利ですね。

一度理解したら簡単に利用できるので知らなかった方はぜひ覚えておいてください。

X = int(input())
ans = (X + (10 - 1)) // 10
print(ans)

C- One Time Swap

これ結構難しいなと思いました。最初は計算量が $O(N^{2})$ となる愚直解を実装し手元で適当なデータを入力とし出力される答えを観察していました。

S = list(input())
N = len(S)

T = set([])
for i in range(N):
    for j in range(i + 1, N):
        S[i], S[j] = S[j], S[i]
        T.add("".join(S))
        S[i], S[j] = S[j], S[i]

ans = len(T)
print(ans)

例えば abbbcdeef の時は 33 と値が返ってきます。
サンプルデータが単純すぎたり少なすぎたりする場合はこのような愚直解を作ってサンプルデータとその答えを得ておくと考察が捗ることがあります。

そしたら

同じ文字がある場合はそこをひとまとめにしその間の swap は同じ文字列になると言える
別の文字同士の swap は必ず異なる文字列になる
同じ文字が２つ以上ある場合は元の文字列のままになることがある (これ最後まで気づかなかったです)

特に最後が罠で、例えば aabbc の場合２つの a 同士の swap と b 同士の swap はどちらも aabbc と元の文字列と同じになってしまいます。どっちも同じ文字列ができるとみなされるのでカウントの仕方が難しかったです。

なので

あり得る swap するペアの選び方を求める (すなわち ${}_N C_{2}$ )
各アルファベットごとに重複している組み合わせを求める
「どの文字でもよいので同じ文字が２つ以上ある」なら最初の文字列を +1 とカウントする

とし、答えを求めました。最初に各アルファベットをカウントする必要があるので計算量は $O(N)$ です。

from collections import *

S = input()
N = len(S)
counts = Counter(S)

# はじめにペアの総数を求める
ans = N * (N - 1) // 2

is_duplicated = False
for count in counts.values():
    if count >= 2:
        # 同じ文字のペアの総数を引く
        ans -= count * (count - 1) // 2
        # 同じ文字のペアが一度でも存在しているなら is_duplicated を True にする
        is_duplicated = True

if is_duplicated:
    # 最初の文字列が swap 後の文字列になるので 1 足す
    ans += 1

print(ans)

D - Tiling

$1 \ge N \ge N$ なので全探索できそうだなーと最初に思いました。実際その通りでしたがコンテスト中に考えた実装ではちょっとイケてなくて TLE がコンテスト終了まで AC にできませんでした。

その後なんとか工夫して AC にできたので解法を紹介しておきます。

現在の空いているマスで一番左上のマスを調べる
そこに残っているタイルからいずれかを選び
そのタイルが他のタイルに重ならずかつはみ出さずに置けるかチェックする
置けるならそのタイルを置いて 1 - 3 を繰り返す

以上の 1 - 4 を深さ優先探索で繰り返し、すべてのマスが埋まったら Yes を、すべての探索が終わってもマスを埋めることができなかったら No を出力しました。

空いているマスを残し続けているとすべてのマスを埋めることができないので、貪欲に左上から埋めていくということができるのがミソですね。

また 1 で左上のマスを調べる時に、どのマスも空いていなければ座標として $(-1, -1)$ を返すようにし、 $(-1, -1)$ が返り値であるならすべてのマスが埋まっているとみなすことで、空いているマスを探すのとマスが埋まっているかの判定も同時に行うことができました。

残っているタイルはすべてのタイルを始め S = set(range(N)) として管理しました。

また、計算コストを下げるためにマスの情報はバックトラックと呼ばれる手法で１つの２次元配列で管理し、計算コストが重くなる deepcopy を避けるようにしました。この辺の工夫をしない場合は Python だとカツカツなので　C++ に書き換えるなどの工夫が別途必要かなと思います。

def find_first_empty_position() -> tuple[int, int]:
    """一番左上の空いているマスを探します"""
    for i in range(H):
        for j in range(W):
            if not grid[i][j]:
                return i, j
    return -1, -1


def can_place_tile(h: int, w: int, a: int, b: int) -> bool:
    """マス (h, w) を四角形の左上として高さ a 幅 b の四角形を置けるかチェックします"""
    if h + a > H or w + b > W:
        return False  # Tile goes out of bounds.
    for i in range(h, h + a):
        for j in range(w, w + b):
            if grid[i][j] != 0:
                return False  # Tile overlaps with an already placed tile.
    return True


def place_tile(h: int, w: int, a: int, b: int, val: int) -> None:
    """マス (h, w) を四角形の左上として高さ a 幅 b の四角形を val = 1なら置き、 val = 0なら取り除きます"""
    for i in range(h, h + a):
        for j in range(w, w + b):
            grid[i][j] = val


def dfs(S) -> None:  # type: ignore
    """バックトラックしつつ深さ優先探索でグリッド全てを埋めることができるか調べます"""
    h, w = find_first_empty_position()
    if h == w == -1:
        print("Yes")
        exit()

    for idx in S:
        a, b = tiles[idx]
        # そのまま配置する場合と回転している場合を考慮します。
        for da, db in [(a, b), (b, a)]:
            if can_place_tile(h, w, da, db):
                # タイルを配置します。
                place_tile(h, w, da, db, 1)
                dfs(S - {idx})
                # タイルを取り除きます(バックトラック)。
                place_tile(h, w, da, db, 0)


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

grid = [[0] * W for _ in range(H)]
S = set(range(N))
dfs(S)

print("No")

*コード内ではマスをグリッドという名前で管理しています