【ABC359】緑コーダーの競プロ参加記録 #25

igasu_7

2024年6月23日 14:00

今回はAtCoder Beginner Contest 359。使用言語はPythonです。

A問題 - Count Takahashi

コンテスト中の提出
https://atcoder.jp/contests/abc359/submissions/54790935

$${N}$$個の文字列が与えられる。
文字列 'Takahashi' の個数を出力してね。

入力をリストで受け取ることで、 count メソッドを利用できます。

"""　count メソッドを使う """
N = int(input())
S = [input() for _ in range(N)]
ans = S.count("Takahashi")
print(ans)

for ループを使ってひとつずつ数えてもよいです。

""" for ループで数える """
N = int(input())
ans = 0
for i in range(N):
    S = input()
    if S == "Takahashi":
        ans += 1
print(ans)

B問題 - Couples

コンテスト中の提出
https://atcoder.jp/contests/abc359/submissions/54797177

$${2N}$$人が一列に並んでいる。
人$${i}$$は色$${A_i}$$の服を着ており、同じ色の服は$${2}$$枚だけ。
同じ色に挟まれている人が何人いるか出力してね。

ある1人を挟んでいる両端の2人のうち、同じ色の服を着ている2人を全探索すればよいです。

つまり、$${A_i = A_{i+2}}$$である$${i}$$の個数を数えます。

""" AC コード """
N = int(input())
A = list(map(int, input().split()))
ans = 0
for i in range(2 * N - 2):
    if A[i] == A[i + 2]:
        ans += 1
print(ans)

C問題 - Tile Distance 2

コンテスト中の提出
https://atcoder.jp/contests/abc359/submissions/54817442

ヨコ$${2}$$、タテ$${1}$$の大きさのタイルが規則的に並んでいる。
別のタイルに移動するときにコスト$${1}$$がかかる。
$${(S_x, S_y)}$$から$${(T_x, T_y)}$$に移動するための最小コストを出力してね。

タイルはこんな感じで並んでいます。

まず、レンガのタテ幅は$${1}$$なので$${y}$$軸方向にはどう頑張っても$${|S_y - T_y|}$$だけコストがかかります。
ここでは、$${y}$$軸方向の移動量を$${dy}$$とします。

$$
dy = |S_y - T_y|
$$

$${S_x = T_x}$$であれば、コスト$${dy}$$で移動できます。

""" 入力を受け取る """
sx, sy = map(int, input().split())
tx, ty = map(int, input().split())

""" x 座標が同じなら、上下に移動するだけでOK """
dy = abs(sy - ty)
if sx == tx:
    print(dy)

それ以外のケースについて考えてみます。

入力例1 の図を眺めてみると、マス$${(x, y)}$$の左上のマス$${(x -1, y + 1)}$$にはコスト$${1}$$で移動できることが分かります。

左上方向に限らず、斜め方向であればコスト$${1}$$で移動できます。
これは、マス$${(x,y)}$$がタイルの左側か右側かにも影響されません。

よって、斜め移動ベースで考えてみることにします。

$${y}$$軸方向の移動量$${dy}$$に対し、$${x}$$軸方向の移動量を$${dx}$$とします。

$$
dx = |S_x - T_x|\\dy = |S_y - T_y|
$$

斜め移動でゴールと x 座標を合わせられる場合

$${dx \le dy}$$の場合、斜め移動のみをくり返すことで現在位置とゴールの$${x}$$座標が先に一致します。

残りの$${y}$$軸方向の移動は全てコスト$${1}$$で可能です。

また、斜め移動をしている間も$${y}$$軸方向に$${1}$$ずつ移動し続けています。

よって、トータルでコスト$${dy}$$でゴールに到達できます。

斜め移動でゴールと x 座標を合わせられない場合

$${dx > dy}$$の場合、斜め移動のみをくり返すことで現在位置とゴールの$${y}$$座標が先に一致します。

残りの$${x}$$方向の移動を考えるのが少し難しいです。
現在位置がタイルの左側なのか右側なのかでコストの考え方が変わります。

ここでは、ゴールに近い方の側にいることにします。

そうすることで、現在の$${x}$$座標を$${x'}$$とすると、追加でコスト$${\bigg\lceil{\Large\frac{|x' - T_x|}{2}}\bigg\rceil}$$を払ってゴールに到達できます。

ゴールが左方向にある場合$${x' = S_x - dy}$$、ゴールが右方向にある場合$${x' = S_x + dy}$$です。

トータルのコストは$${dy + \bigg\lceil{\Large\frac{|x' - T_x|}{2}}\bigg\rceil}$$です。

「ゴールに近い方の側にいることにします。」と言いましたが、具体的にはスタート地点をコスト$${0}$$の範囲でずらしておきます。

ゴールが左方向にある、すなわち$${S_x > T_x}$$である場合、スタート位置をタイルの左側にする。
ゴールが右方向にある、すなわち$${S_x < T_x}$$である場合、スタート位置をタイルの右側にする。

問題文に、「$${i + j}$$が偶数のとき$${A_{i, j}}$$と$${A_{i+1, j}}$$は同じタイル」とあります。

これを言い換えると「$${i + j}$$が偶数のときマス$${(i, j)}$$はタイルの左側」となります。

よって、以下の操作をするとよいです。

$${S_x > T_x}$$かつ$${S_x + S_y}$$が奇数であるとき、$${S_x}$$を$${-1}$$しておく。
$${S_x < T_x}$$かつ$${S_x + S_y}$$が偶数であるとき、$${S_x}$$を$${+1}$$しておく。

問題を解く

以上を合わせると、以下のようなコードになります。

""" 入力を受け取る """
sx, sy = map(int, input().split())
tx, ty = map(int, input().split())

dy = abs(sy - ty)
if sx == tx:
    """ x 座標が同じなら、上下に移動するだけでOK """
    print(dy)
elif sx > tx:
    """ 左方向に移動するケース """
    if (sx + sy) % 2 == 1:
        sx -= 1     # 左につめる
    dx = abs(sx - tx)
    if dx <= dy:
        print(dy)
    else:
        x = sx - dy
        add = (abs(x - tx) + 1) // 2 # 切り上げ処理
        print(dy + add)
else:
    """ 右方向に移動するケース """
    if (sx + sy) % 2 == 0:
        sx += 1     # 右につめる
    dx = abs(sx - tx)
    if dx <= dy:
        print(dy)
    else:
        x = sx + dy
        add = (abs(x - tx) + 1) // 2 # 切り上げ処理
        print(dy + add)

D問題 - Avoid K Palindrome

コンテスト中の提出
https://atcoder.jp/contests/abc359/submissions/54842955

'A', 'B', '?' からなる$${N}$$文字の文字列$${S}$$と整数$${K}$$が与えられる。
長さ$${K}$$の連続する部分文字列に回文が存在しないなら「良い文字列」。
$${S}$$の '?' を 'A' または 'B' に置き換えたとき、$${S}$$が良い文字列になるパターンの個数を出力してね。$${\pmod{998244353}}$$

$${K \le 10}$$と、なにやらアヤシイ制約です。

連続する$${K}$$文字が回文でなければ「良い文字列」なので、'A', 'B' をどのように割り当てたかの情報は、$${K}$$文字分だけあればよいです。

そして、'A', 'B' からなる$${K}$$文字の文字列としてあり得るのは$${2^K}$$通りです。

'A' を 0、'B' を 1 とみなして二進数で考えるとbit全探索ができそうです。

$${i}$$文字目以降の$${K}$$文字を 'ABA + B' にしたい場合、$${i - 1}$$文字目以降の$${K}$$文字は 'A + ABA' か 'B + ABA' である必要があります。

$${i - 1}$$文字目以降が 'A + ABA' であるものと、 'B + ABA' であるものの個数がそれぞれ分かっていれば、$${i}$$文字目以降が 'ABA + B' になるものの個数も判明します。

そうすると、DPの気配を感じます。

（ 'BABAB' は全体として回文になりますが、連続$${K}$$文字が回文でなければ問題ありません。）

以上を二進数に直してみます。
bit DP になります。

$${i}$$文字目以降を 0101 (= 'ABAB' ) にしたい場合、$${i - 1}$$文字目以降は 0010 (= 'AABA' ) か 1010 (= 'BABA' ) である必要があります。

0010 / 1010 はそれぞれ「0101 を1回右シフトして、一番左の桁を 0 または 1 にしたもの」と言えます。

よって、DPの遷移は以下のようになります。

""" bit DP の遷移イメージ """
for mask in range(1 << K):
    a = mask >> 1
    b = mask >> 1 | 1 << (K - 1)
    dp[i][mask] += dp[i - 1][a] + dp[i - 1][b]

今回は「回文でない」という条件があるので、それぞれの文字の配置パターンに対してチェックします。

また、文字の配置パターンをbit 全探索するにあたり、文字列$${S}$$と矛盾しないよう注意が必要です。

def is_kaibun(s):
    """ 回文かどうか判定 """
    k = len(s)
    for i in range(k):
        if s[i] != s[k - i - 1]:
            return False
    return True

def invalid(i, mask):
    """ 
    S の i 文字目から始まる長さ K の連続部分文字列であって
    文字の配置パターンが mask であるものが S と矛盾している
    または、回文であるかどうか判定
    """
    T = []
    for j in range(K):
        if S[i + j] == "A" and (mask >> (K - j - 1)) & 1 == 1:
            return True
        if S[i + j] == "B" and (mask >> (K - j - 1)) & 1 == 0:
            return True
        if (mask >> (K - j - 1)) & 1 == 0:
            T.append("A")
        else:
            T.append("B")
    return is_kaibun(T)

文字列$${S}$$の先頭$${K}$$文字に対して以上の処理を行い、問題が無ければカウントします。
これを DP の初期状態とします。

""" 入力を受け取る """
N, K = map(int, input().split())
S = input()
mod = 998244353

"""
dp[mask]: i 文字目から始まる長さ K の連続部分文字列であって
          文字の配置パターンが mask であるものの個数
"""
dp = [0] * (1 << K)

""" 初期状態を調べる """
for mask in range(1 << K):
    if invalid(0, mask):
        continue
    dp[mask] = 1

$${S}$$の2文字目以降について、DPを行います。

$${i}$$は1つ前のものしか参照しないので、DPのリストを分割して一次元で実装しています。

""" 2文字目以降を調べる """
for i in range(1, N - K + 1):
    ndp = [0] * (1 << K)
    for mask in range(1 << K):
        if invalid(i, mask):
            continue
        a = mask >> 1
        b = mask >> 1 | 1 << (K - 1)
        ndp[mask] += dp[a] + dp[b]
        ndp[mask] %= mod
    dp = ndp

""" 答えを求める """
ans = 0
for mask in range(1 << K):
    ans += dp[mask]
    ans %= mod
print(ans)

解説用コードの全体
https://atcoder.jp/contests/abc359/submissions/54863623

E問題 - Water Tank

upsolve
https://atcoder.jp/contests/abc359/submissions/54866513

水槽に$${N}$$枚の板が立っている。
左から$${i}$$番目の板の高さは$${H_i}$$。
水槽の左端から水を注ぐとき、$${i}$$番目の区画に初めて水が入るタイミングを出力してね。

水が$${i}$$枚目の板を超えるためには、それより左側に連続する「$${H_i}$$以下の高さの板で区切られた区画」すべてを高さ$${H_i}$$の水で満たさなければなりません。

「$${H_i}$$以下の高さの板で区切られた区画」の幅の合計を$${\mathrm{width}}$$とします。

$${H_i \times \mathrm{width}}$$の範囲を水で満たせばよいですが、すでに貯まっている水を考慮する必要があります。

区画を結合していくイメージで、$${h \times w}$$のまとまった範囲をスタックで管理することで、すでに貯まっている水量を考えやすくなります。

from collections import deque
N = int(input())
H = list(map(int, input().split()))

""" 
res[i]: i番目の区画が満水になるタイミング
dq <- まとまった範囲の height, width
"""
res = [0] * N
dq = deque()
dq.append((0, 0))
total_water = 0

for i in range(N):
    width = 1

    """ h * w の範囲に、すでに貯まった水をいったん抜く """
    while dq and dq[-1][0] < H[i]:
        h, w = dq.pop()
        total_water -= h * w
        width += w

    """ H[i] * width の範囲に水を満たす """
    total_water += H[i] * width
    res[i] = total_water
    dq.append((H[i], width))

""" 満水タイミング + 1 が答え """
ans = [r + 1 for r in res]
print(*ans)

水を抜かずに、差分だけ注水する解き方でもよいです。

""" 足りない分だけ水量を加算 """
total_water += H[i]
while dq and dq[-1][0] < H[i]:
    h, w = dq.pop()
    total_water += (H[i] - h) * w

evima さんの動画の解説がとても分かりやすかったので参考にしました。

あとがき

今回は ABCD 4完 92分で 2036位、1255 perf でした。

C も D も難しくて、2完の可能性も全然あるなぁと震えていました。

E の方が解かれていますが、コンテストの翌朝に3時間くらい考えて解けなかったのでDを頑張ってよかったです。

ではまた～。

【更新履歴】
2024/06/23 (14時頃)：記事投稿。