初心者必見！ABC303Pytohn参加（A〜D）

初めに

AtCoderに参加した記録を残します。どのような考察をしながら問題に取り組んだかを記録していますので、必ずしも教育的なコードとは限りません。
始めたばかりの人など、どなたかの助けになれば嬉しいです。
コメントなどいただけると嬉しいです！！

成績

ABC303 3冠。
A問題読み間違えて3WAも出してしまった...。問題しっかり読もう。

目次

A - Similar String
B - Discord
C - Dash
D - Shift vs. CapsLock

A - Similar String

問題ページ
入力される文字列が条件を満たすか判定する問題。

コンテスト中の考察

この問題では、S, Tの任意の i 番目の文字x, yに関して、以下の条件を満たすかを判定すれば良い。

同じ文字のペア or {1, l}のペア or {0, o}のペア

　注意に示す内容を勘違いしていてWA大量生産した。

注意
・入力数字は（おそらく）0,1だけじゃない。
・「任意の文字」=「すべての文字」。特定の文字の場合は「ある文字」と表記される。

コンテスト中のコード

a.py

import string

N = int(input())
S = input().replace('l', '1').replace('o', '0')
T = input().replace('l', '1').replace('o', '0')
lc = list(string.ascii_lowercase)
for i in range(N):
    if S[i] == T[i]:
        continue
    elif S[i] in lc or T[i] in lc:
        if S[i] == T[i] == "w":
            continue
        else:
            print('No')
            exit()
    elif S[i] in {'0', '1'} and T[i] in {'0', '1'}:
        if not(int(S[i])^int(T[i])):
            continue
        else:
            print('No')
            exit()
print('Yes')

改善点

着想面

最初の着想悪すぎて提出解がめちゃくちゃになっていた。よくわからないけどテストケースに過学習したコード含まれてるし笑
最終的な解法としてはlを1に、oを0に変換し、先頭からi文字目がTとSで一致しているかをみていけば良い。条件は、同じ文字 or 似た文字なので、似た文字を同じ文字にしてしまえば同じ文字かどうかの判定をするだけで済む。

コード面

a_fix.py

import string

N = int(input())
S = input().replace('l', '1').replace('o', '0')
T = input().replace('l', '1').replace('o', '0')
lc = list(string.ascii_lowercase)
for i in range(N):
    if not(S[i] == T[i]):
        print('No')
        exit()
print('Yes')

B - Discord

問題ページ
1〜Nまでの数を一つずつ含む数列AがM個与えられ、どの数列Aにおいても隣り合わないような数の組み合わせの数を答える問題。

注意
・(i, j)と(j, i)は区別しない

コンテスト中の考察

隣り合う組み合わせの列挙は先頭から順番に列挙していくことで可能。
あとは注意点に気をつければ良いのだが、0<i<j<Nと決めてやれば、重複することなく組み合わせを列挙することができる。
具体的な会報としては、N*Nの隣り合い記録用のリストLをFalseで初期化し、それぞれの数列Aを先頭から見ていき、L[A[ i ]][A[ i+1 ]]とL[A[ i+1 ]][A[ i ]]にTrueを代入する。組み合わせをカウントする場合は0<i<N, i<j<N でFalseのものをcntしていけば重複なくカウントできる。

コンテスト中のコード

b.py

N, M = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(M)]
ans = [[False]*N for _ in range(N)]

for P in A:
    for i in range(N-1):
        ans[P[i]-1][P[i+1]-1] = True
        ans[P[i+1]-1][P[i]-1] = True

cnt = 0
for i in range(N):
    for j in range(i+1, N):
        if not(ans[i][j]):
            cnt += 1

print(cnt)

改善点

特になし

C - Dash

問題ページ
移動ごとに体力を消費するグリッドにおいてN回の操作が可能か判定する問題。特定のマスにはアイテムがあり、体力が一定以下の場合はアイテムを消費し、体力を回復することができる。

コンテスト中の考察

解法としてはそのままシミュレートするだけ。ただし、下記に注意。

注意
・アイテムは各場所につき一度しか使用できないので注意。

コンテスト中のコード

c.py

N, M, H, K = map(int, input().split())
S = input()
item = set()
act = {'R': (1, 0), 'L': (-1, 0), 'U': (0, 1), 'D': (0, -1)}
for _ in range(M):
    x, y = map(int, input().split())
    item.add((x,y))

x = 0
y = 0
for s in S:
    if H == 0:
        print('No')
        exit()
    dx, dy = act[s]
    x += dx
    y += dy
    H -= 1
    if (x, y) in item:
        if H < K:
            H = K
            item.discard((x, y))
print('Yes')
        

改善点

特になし

D - Shift vs. CapsLock

問題ページ
大文字小文が入り混じった文字列の入力のコストを最小化する問題。

コンテスト中の考察

アルファベットのみ入力、shift+アルファベット入力、capslockをONにする、の三種類の行動が選べ、capsLockを押すかが後ろにある程度影響してくるので貪欲法では解けなさそう？と考え、最初真っ先にDPを考えたが、うまいこと独立にできなくて断念。
考え方は、capsLockがi(0or1)の時にj文字目まで入力した時のコスト。
その後大文字と小文字の区間の個数でコストを計算して貪欲法で解こうとしたがshift入力とcpasLockをうまく区別できなくて時間切れ。

コンテスト中のコード

d.py

X, Y, Z = map(int, input().split())
S = input()
dp = [[10**18]*(len(S)+1) for _ in range(2)]
dp[0][0] = 0

for j in range(len(S)):
    if S[j] == "A":
        dp[1][j+1] = min(dp[0][j]+Y, dp[0][j]+Z+X)
        dp[1][j+1] = min(dp[1][j+1], dp[1][j]+X)
        dp[1][j+1] = min(dp[1][j+1], dp[1][j]+Z+Y)
    else:
        dp[0][j+1] = min(dp[1][j]+Y, dp[1][j]+Z+X)
        dp[0][j+1] = min(dp[0][j+1], dp[0][j]+X)
        dp[0][j+1] = min(dp[0][j+1], dp[0][j]+Z+Y)

print(f"{dp=}")
print(min(dp[0][-1], dp[1][-1]))

改善点

着想面

コンテスト急の着想でほぼ合ってたっぽい。
解けなかった理由を下記に示す。

ズレていた部分

1. DPの変数の一つをCapsLockのオンオフとして扱っているつもりが、実質的にはi番目の文字が大文字か小文字かを区別する変数になっていた
2. 現在入力するべき文字（大文字or小文字）は取れる行動に寄与しているという点に気が付かなかった

まず1についてだが、着想の時点ではCapsLockの変数として考えていたのだが、実際にDPを書く時にj番目の文字が大文字だったらdp[1][j+1]にしか代入が行われないと考えてしまっていた。
続いて2についてだが、j番目の文字はDPの更新元と更新先を指定する情報である。1のように考えてしまった理由の一つに、この情報をどの様に活用すればいいかいまいち分からなかったのである。ではj番目の文字が大文字だった場合について具体的に考えていこう。まず大前提として、とりうる行動は下記に示す4種類である。

行動候補

1. X 秒かけて a キーのみを押す
2. Y 秒かけて Shift キーと a キーを同時に押す
3. Z+X 秒かけて CapsLock キーを押した上で a キーのみを押す
4. Z+Y 秒かけて CapsLock キーを押した上で Shift キーと a キーを同時に押す

大文字を入力する場合には下記のようにDP配列の更新を考える必要がある。

行動候補
・LockがONの状態で行動1を選択 → 次状態のLockはON
・LockがOFFの状態で行動2を選択 → 次状態のLockはOFF
・LockがOFFの状態で行動3を選択 → 次状態のLockはON
・LockがONの状態で行動4を選択（shiftとCapsLockでON→OFF→ONとなるため） → 次状態のLockはOFF

これらをDPに組み込むことができれば問題なく独立になっている。

コード面

d_fix.py

X, Y, Z = map(int, input().split())
S = input()
dp = [[10**18]*(len(S)+1) for _ in range(2)]
dp[0][0] = 0

for j in range(len(S)):
    if S[j] == "A":
        dp[1][j+1] = min(dp[1][j+1], dp[1][j]+X)
        dp[0][j+1] = min(dp[0][j+1], dp[0][j]+Y)
        dp[1][j+1] = min(dp[1][j+1], dp[0][j]+Z+X)
        dp[0][j+1] = min(dp[0][j+1], dp[1][j]+Z+Y)
    else:
        dp[0][j+1] = min(dp[0][j+1], dp[0][j]+X)
        dp[1][j+1] = min(dp[1][j+1], dp[1][j]+Y)
        dp[0][j+1] = min(dp[0][j+1], dp[1][j]+Z+X)
        dp[1][j+1] = min(dp[1][j+1], dp[0][j]+Z+Y)
print(min(dp[0][-1], dp[1][-1]))

終わりに

書き始めたばかりで拙い部分も多いですが、みなさんと楽しく盛り上がれたらいいなと思っていますので、今後ともよろしくお願いいたします！
いいね等していただけるととても励みになります！