🔌

[ABC264] AtCoder Beginner Contest 264（A-F 問題 Python）

2022/08/15に公開

Python

競技プログラミング

AtCoder

tech

AtCoder Beginner Contest 264 の復習記録です。難易度が青色レベル以下の、A問題からF問題までをやります。使用言語はPythonです。

A問題

考え方

indexの始まりを気にして実装するだけです。pythonは 0-indexedなので $-1$ します。
終わりの文字は、その文字まで出力対象なので $+1$ するため、打ち消しあいます。

提出コード

S = "atcoder"
L,R = map(int,input().split())
ans = S[L-1:R]
print(ans)

B問題

考え方

チェビシェフ距離（チェス盤距離）を用いることに気付ければ、軽く実装することができます。
チェビシェフ距離は、チェス盤上での駒(キング)の移動に必要な回数です。キングは斜め移動ができるため、チェビシェフ距離が一定のマスは、正方形の形になります。

$(Cs,Rs)$ 、 $(Ct,Rt)$ のチェビシェフ距離は、

max(|Rt-Rs|+|Ct-Cs|)

と表せます。今回の問題は、中心の $(8,8)$ からのチェビシェフ距離が、偶数のマスは「白」、奇数のマスは「黒」となっています。

提出コード

R,C = map(int,input().split())
dist = max(abs(R-8),abs(C-8))
if dist % 2 == 0:
    print("white")
else:
    print("black")

C問題

考え方

行列Aの行・列から、いくつかを削除して、行列Bと一致させられるかという問題です。制約が小さいので、全探索しても計算量は間に合いそうです。

入力例1では、Aの4行5列を、Bの2行3列にするので、4→2行、5→3列への全探索なので、

\large _4C_2・_5C_3 = 60

の60通り程度です。
制約は $N\leq10$ ですので、最も計算量が多くなっても、

\large _{10}C_5・_{10}C_5 = 63504

ですので大丈夫そうです。

提出コード

公式解答では、bit全探索を用いていましたが、Iteratorを用いて実装しても大丈夫でした。

h1,w1 = map(int,input().split())
A = [list(map(int,input().split())) for _ in range(h1)]
h2,w2 = map(int,input().split())
B = [list(map(int,input().split())) for _ in range(h2)]

from itertools import combinations
iter1 = list(combinations(range(h1),h2))
iter2 = list(combinations(range(w1),w2))

行と列の1つの選び方について、行列Bとの一致を判定する関数を準備します。

def check(i1,i2):
    for x,h in enumerate(i1):
        for y,w in enumerate(i2):
            if A[h][w] != B[x][y]:
                return False
    return True

条件を満たす場合には、satisfied=True となり、breakでループから外れるように実装しました。

satisfied = False
for i1 in iter1:
    if satisfied == True:
        break

    for i2 in iter2:
        if check(i1,i2):
            satisfied = True
            break

if satisfied == True:
    print("Yes")
else:
    print("No")

D問題

考え方

スワップ・転倒数に関する典型問題です。
入力例1の「catredo」を隣接交換で正しい順序「atcoder」に並び替えるとき、交換回数は交換前後の位置同士を線で結んだときの交点の数と同じになります。

これは、atcoderを位置番号に変換し、前から順番に見ていったとき、既出の数のうち、自分自身より大きな数を数えていけば良いです。転倒数と同じです。

提出コード

S = input()
a = list("atcoder")

ans = 0
for i in range(7):
    n = a.index(S[i])
    for k in S[:i]:
        if a.index(k) > n:
            ans += 1

print(ans)

E問題

考え方

順番に電線を切っていくという操作を逆に考えるのがポイントです。電線をつなぎながら、電気の通っている都市の数を数えていきます。

手順

クエリを先に全てチェックして、電線を「切断予定のあるもの」と「切断予定のないもの」に分けます。
切断予定のない電線は、先に全てつないでしまいます。
切断予定のある電線を、最後のものから順番に繋いでいきます。その途中経過で、電気の通っている都市数をカウントして記録しておきます。
記録した通電した都市数を、反対から見れば正しい出力が得られます。

公式のユーザー解答で紹介されていましたが、発電所は全て同一と見なせます。
また、都市間の接続は Union-Find で管理して、接続グループのサイズから、電気が通うようになった都市数を得るようにします。

提出コード

入力を受け取る際に、発電所は全て同じ番号 $N$ としてしまいます。

N,M,E = map(int,input().split())
edge = []
for _ in range(E):
    U,V = map(int,input().split())
    U-=1; V-=1
    if U>=N: U=N
    if V>=N: V=N
    edge.append((U,V))

クエリをチェックして、電線の切断予定の有無を記録します。

NonCut = [True] * E
queue = []

Q = int(input())
for _ in range(Q):
    X = int(input())
    X -= 1
    queue.append(X)
    NonCut[X] = False

Union-Findの準備です。
普段と違い、番号の大きいものを親ノードになるようにします。発電所の番号は $N$ なので、親ノードが $N$ となるなら、通電していることを表します。また、グループが合わさるときには、接続グループのサイズを更新するようにします。

root = [i for i in range(N+1)]
size = [1]*(N+1)

def find(x):
    if root[x]==x:
        return x
    root[x] = find(root[x])
    return root[x]

def unite(x,y):
    rx = find(x)
    ry = find(y)
    if rx == ry:
        return
    elif rx > ry:
        root[ry] = rx
        size[rx] += size[ry]
        size[ry] = 0
        return
    else:
        root[rx] = ry
        size[ry] += size[rx]
        size[rx] = 0
        return

def same(x,y):
    if find(x) == find(y):
        return True
    else:
        return False

電気が通っている都市数を $cnt$ として、まずは、切断予定のない電線を全てつなぎます。電気が通っていない都市グループに、電気が通るときには、グループのサイズを $cnt$ に加算します。

cnt = 0
for i in range(E):
    if NonCut[i] == False:
        continue

    u,v = edge[i]
    if same(u,v):
        continue
    if find(u)==N and find(v)<N:
        cnt += size[find(v)]
    elif find(v)==N and find(u)<N:
        cnt += size[find(u)]
    unite(u,v)

クエリを逆順にして、切断予定のある電線を後ろからつないでいきます。つなぐ前に $cnt$ （通電都市数）を $ans$ （出力用リスト）に記録していきます。最後に $ans$ を後ろから出力すれば、正しい出力となります。

ans = []
queue.reverse()

for i in queue:
    ans.append(cnt)

    u,v = edge[i]
    if same(u,v):
        continue
    if find(u)==N and find(v)<N:
        cnt += size[find(v)]
    elif find(v)==N and find(u)<N:
        cnt += size[find(u)]
    unite(u,v)

ans.reverse()
print(*ans,sep="\n")

F問題

考え方

なんとかして $(i,j)$ まで到達した後、
$(i,j)$ から下方向に $(i+1,j)$ へ移動することを考えます。

この2つのマス $(i,j)$ と $(i+1,j)$ の色を比較して、

(a) 同じ色のとき
移動コストは $0$ で $(i+1,j)$ へ移動できます。

(b) 異なる色のとき
行の反転コスト $H_{i+1}$ を支払い $i+1$ 行目を反転すれば $(i+1,j)$ へ移動できます。

これを下方向、右方向について調べていくのが、基本的な考え方です。
この2つのマスの色の一致を判定するためには $(i,j)$ マスについて行・列の反転がされたかどうかの情報が必要となります。そこで $i$ 行目の反転の有無を $x$ , $j$ 列目の反転の有無を $y$ とおきます。ここで $x,y$ は $0$ は反転なし $1$ は反転ありと考えます。

$(i,j)$ に移動するための必要コストの最小値を $DP$ [ $i\timesW+j$ ][ $x$ ][ $y$ ] とおいてDP遷移を考えて実装すれば良いです。下方向への移動を考える際には $x$ のみ考慮すれば十分で、 $y$ については考える必要はありません。列反転は縦に並んだ2つのマスを両方ともを巻き込むため、色の一致を調べる際には影響しないからです。右方向への移動については、同様に $y$ のみを考慮し $x$ については考えなくて良いです。

提出コード (TLE)

# TLEになってしまうコード
H,W = map(int,input().split())
R = list(map(int,input().split()))
C = list(map(int,input().split()))
A = [list(map(int,list(input()))) for _ in range(H)]

INF = 10**15
# DP[Position][現在の行の反転の有無][現在の列の反転の有無]
DP = [[[INF]*2 for _ in range(2)] for __ in range(H*W)]
DP[0][0][0] = 0
DP[0][1][0] = R[0]
DP[0][0][1] = C[0]
DP[0][1][1] = R[0]+C[0]

for文を重ねて、各状態について遷移を考えます。マスの色の一致の判定では、^排他的論理和(xor)を用いて反転の有無を反映させます。

for i in range(H):
    for j in range(W):
        p = i*W+j
        for x in range(2):
            for y in range(2):
                if i < H-1:
                    if A[i][j] ^ x == A[i+1][j]:
                        DP[p+W][0][y] = min(DP[p+W][0][y], DP[p][x][y])
                    else:
                        DP[p+W][1][y] = min(DP[p+W][1][y], DP[p][x][y]+R[i+1])

                if j < W-1:
                    if A[i][j] ^ y == A[i][j+1]:
                        DP[p+1][x][0] = min(DP[p+1][x][0], DP[p][x][y])
                    else:
                        DP[p+1][x][1] = min(DP[p+1][x][1], DP[p][x][y]+C[j+1])

ans = min(DP[-1][0][0], DP[-1][0][1], DP[-1][1][0], DP[-1][1][1])
print(ans)

上記のコードは、正しい出力を返しますがTLEとなってしまいます。ほんのわずかな違いですが、DPの多次元配列の順番を $DP$ [ $x$ ][ $y$ ][ $i\timesW+j$ ]に変更するだけでACコードになります。

pythonのメモリレイアウト形式は、Row-major order方式（行優先）となっており（C系言語も同様）、各次元の要素数に偏りがある場合は、多次元配列の作り方で、ランダムアクセスとシーケンシャルアクセスの割合が変わるようです。そのためpythonでは、一番内側の要素数が大きい方が、高速になります。以下の記事では実際に速度の比較などの分析が行われていました。

下記コードは、DPテーブルの多次元配列の作り方を変更したものです。これでACになりました。

提出コード (AC)

H,W = map(int,input().split())
R = list(map(int,input().split()))
C = list(map(int,input().split()))
A = [list(map(int,list(input()))) for _ in range(H)]
INF = 10**15
# DP[現在の行の反転の有無][現在の列の反転の有無][Position]
DP = [[[INF]*(H*W) for _ in range(2)] for __ in range(2)]
DP[0][0][0] = 0
DP[1][0][0] = R[0]
DP[0][1][0] = C[0]
DP[1][1][0] = R[0]+C[0]

for h in range(H):
    for w in range(W):
        i = h*W+w
        for a in range(2):
            for b in range(2):
                if h < H-1:
                    if A[h][w] ^ a == A[h+1][w]:
                        DP[0][b][i+W] = min(DP[0][b][i+W], DP[a][b][i])
                    else:
                        DP[1][b][i+W] = min(DP[1][b][i+W], DP[a][b][i]+R[h+1])

                if w < W-1:
                    if A[h][w] ^ b == A[h][w+1]:
                        DP[a][0][i+1] = min(DP[a][0][i+1], DP[a][b][i])
                    else:
                        DP[a][1][i+1] = min(DP[a][1][i+1], DP[a][b][i]+C[w+1])

ans = min(DP[0][0][-1], DP[0][1][-1], DP[1][0][-1], DP[1][1][-1])
print(ans)

A問題

考え方

提出コード

B問題

考え方

提出コード

C問題

考え方

提出コード

D問題

考え方

提出コード

E問題

考え方

手順

提出コード

F問題

考え方

提出コード (TLE)

提出コード (AC)

Discussion