🐈

AtCoder ABC219 個人的メモ

5 min read

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"として...と言った具合に扱って欲しい。
というわけで以下のように実装すればおk。

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

D - Strange Lunchbox

たこ焼きだけの場合で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個のたい焼きを手に入れる場合の弁当の最小個数)とすればお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の配列があればおkなことから省略
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

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

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

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

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

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

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

https://atcoder.jp/contests/joi2012yo/tasks/joi2012yo_e
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)

参考

https://atcoder.jp/contests/abc219/editorial/2652

Discussion

ログインするとコメントできます