🐈

AtCoder ABC219 個人的メモ

2021/09/19に公開

Python

競技プログラミング

AtCoder

tech

A - AtCoder Quiz 2

X = int(input())

if 0 <= X < 40:
    print(40 - X)
elif 40 <= X < 70:
    print(70 - X)
elif 70 <= X < 90:
    print(90 - X)
else:
    print("expert")

B - Maritozzo

S = [input() for _ in range(3)]
T = list(map(int, input()))  # 整数を入力

ans = ""
for t in T:
    ans += S[t - 1]

print(ans)

C - Neo-lexicographic Ordering

名前をソートする際に、Xの1文字目が"a"として、2文字目が"b"として...と言った具合に扱って欲しい。
というわけで以下のように実装すればおｋ。

すべての名前を上記のように変換する(Xの1文字目→"a",2文字目→"b"...)
普通にソートする
元の名前に戻す

from string import ascii_lowercase

X = input()
N = int(input())
S = [input() for i in range(N)]

# 1.
new_alphabet = {s: i for i, s in enumerate(X)}
trans = {}
new_names = []
for s in S:
    res = []
    for a in s:
        res.append(ascii_lowercase[new_alphabet[a]])
    res = "".join(res)

    new_names.append(res)
    trans[res] = s

# 2.
new_names.sort()
# 3.
print(*(trans[s] for s in new_names), sep="\n")

たこ焼きだけの場合で $N$ 個の弁当で $X$ 個以上のたこ焼きを手に入れる場合の弁当の最小個数を考えてみる。
これは $dp[i][j]:=$ ( $i$ 個目までの弁当で $j$ 個のたこ焼きを手に入れる場合の弁当の最小個数)として、このdpを解けば求まる。
遷移は $i$ 個目の弁当を買わないか買うかで $dp[i][j]=min(dp[i-1][j],\ dp[i-1][j-A[i]]+1)$ となる。

今回の問題ではたこ焼きだけでなくたい焼きもある。
なので、 $dp$ の次元を拡張して $dp[i][j][k]:=$ ( $i$ 個目までの弁当で $j$ 個のたこ焼きと $k$ 個のたい焼きを手に入れる場合の弁当の最小個数)とすればおｋ。

N = int(input())
X, Y = map(int, input().split())
bento = [list(map(int, input().split())) for _ in range(N)]  # 整数を入力
INF = 10 ** 18

# dpはi番目までの弁当でj個のたこ焼きとk個のたい焼きを手に入れる際の弁当の個数の最小値
# たこ焼きやたい焼きの個数がそれぞれX,Y以上なら一律X,Y個とする
# dp配列のiの次元は遷移の際にi-1の配列があればおｋなことから省略
dp = [[INF] * (Y + 1) for _ in range(X + 1)]
dp[0][0] = 0
for a, b in bento:
    # dp配列を使いまわしていて同じ弁当iを複数回用いれないナップサックdpなのでj,kは降順で回す
    for j in range(X, -1, -1):
        for k in range(Y, -1, -1):
            # i個目の弁当を買わない場合はdp配列を使いまわしているので遷移不要
            # 買う場合(個数がX,Y以上の場合は一律X,Y)
            nj = min(j + a, X)
            nk = min(k + b, Y)
            dp[nj][nk] = min(dp[nj][nk], dp[j][k] + 1)

ans = dp[-1][-1]
if ans == INF:
    print(-1)
else:
    print(ans)

E - Moat

堀のパターンを全探索して、それぞれの堀が条件を満たしているかを判定して答えを数える。

まず堀のパターンの全探索方法だが、公式解説と同じ様にある点が堀の内側にあるか？を全探索すればおｋ。
このときの堀はそれらの点のみを内側に含み条件4,5を満たすように建設すると点のパターンごとに1つのパターンになる。
点は $4\times4=16$ 個で全パターンは $2^{16}=65,536$ 通りなので、条件を満たしているかの判定を $O(10^3)$ くらいでできれば良さそう。

条件の判定は問題文の5つに加えて堀内部に穴が無いこと(質問で言及されてた)を加えて以下の通り

自己交差がない
堀の内側のある点からすべての他の内側の点に上下左右への移動のみで到達できるか?(連結か?)をBFSで判定。
頂点が16個、辺の個数が各頂点で4本ぐらいで $16\times 4$ 本ぐらいなので $O(4^2+4^2\times 4)\simeq O(10^2)$ (BFSの計算量は頂点数+辺の数)
内部に全ての村を含む
今のパターンの堀内部の点を集合として、すべての村がその集合に含まれるかを判定。
計算量は各頂点が集合に含まれるかを判定するので $O(4^2\times \log_24^2)\simeq O(10^2)$
すべての頂点のx座標とy座標は0以上4以下の整数
全探索するときに範囲内の点のみを考えるので必ず満たす。そのため判定不要
すべての辺はx軸とy軸のどちらかに平行
この条件を満たす様な堀のパターンのみを考えているので判定不要
それぞれの内角の大きさは90度または270度
よく分からんから無視した。条件4を満たしていれば勝手に満たすと思う。
堀の内部に穴が無い
堀の外部のマスと外周のマスが連結か?をBFSで判定。 $O(10^2)$

よって6つの条件の内の条件1,2,6のみを判定すればおｋで、いずれの判定も $O(10^2)$ 程度でできるので十分に高速となる。

堀の外側が連結かを調べる様な類題：

def is_unite(points_set: set, L: int):
    """
    points_setに含まれている点(点番号)が連結かをBFSで判定。
    Lはグリッドの辺の長さ(堀内部の連結チェック時はL=4, 堀外部の連結チェック時はL=6)
    """
    queue = [points_set.pop()]
    points_set.add(queue[0])
    seen = set()
    while queue:
        now = queue.pop()
        if now in seen:
            continue
        seen.add(now)

        # 点番号 → (i,j)の座標 に変換
        i = now // L
        j = now % L
        for di, dj in [(-1, 0), (0, 1), (1, 0), (0, -1)]:
            ni = i + di
            nj = j + dj
            if 0 <= ni < L and 0 <= nj < L:
                adjacent_point = ni * L + nj
                if adjacent_point in points_set and adjacent_point not in seen:
                    queue.append(adjacent_point)

    return seen == points_set


def is_no_pocket(points_set: set):
    """
    堀の外側のマスが連結か？(堀内部に中空の部分が無いか？)を判定
    """
    # tmpは村が無いマスと外周の点番号の集合
    M = 6
    tmp = set(x for x in range(M * M))
    for v in points_set:
        # 外周を使うので村の座標を6*6マスの座標に変換
        i, j = v // N, v % N
        i += 1
        j += 1
        # (i,j) → 点番号
        tmp.discard(i * M + j)

    return is_unite(tmp, M)


N = 4
A = [list(map(int, input().split())) for _ in range(N)]  # 整数を入力

# 各村の座標(i,j) → 点番号
vilages = []
for i in range(N):
    for j in range(N):
        if A[i][j]:
            vilages.append(i * N + j)

ans = 0
for bit in range(1 << (N * N)):
    # 2進数bit → 堀の内側に含まれる点の点番号の集合candidate に変換
    candidate = set()
    bit = f"{bit:0{N * N}b}"
    for i, is_in_ohori in enumerate(bit):
        if int(is_in_ohori):
            candidate.add(i)

    # すべての村が候補candidate内に含まれているかを判定
    if any(i not in candidate for i in vilages):
        continue

    # 全部のマスが連結になっているかと堀内部に穴が無いかを判定
    if is_unite(candidate, N) and is_no_pocket(candidate):
        ans += 1

print(ans)