🐈

Atcoder - ABC341 A - E まで復習解説

2024/02/18に公開

競技プログラミング

AtCoder

tech

ABC341 A - E を復習してまとめてみました。初学者の方の参考になれば幸いです。

A - Print 341

問題文
正整数 $N$ が与えられるので、 $N$ 個の $0$ と $N+1$ 個の $1$ からなる、 $0$ と $1$ が交互に並んだ文字列を出力してください。

Python の場合文字列を "abc" * 3 のようにかけ算の式をあたえると "abcabcabc" のように 3 回連続することができます。今回の問題の場合は $0$ と $1$ の数が違うので $N + 1$ 倍して末尾の $0$ を含まず出力しました。
(逆に $N$ 倍して $1$ 足して出力してもOKです)

N = int(input())

ans = "10" * (N + 1)
ans = ans[:-1]
print(ans)

B - Foreign Exchange

最初読んだ時に実世界同様すべての通貨の間で変換可能と勘違いして、めちゃくちゃ難しくない？と思ってしまいましたが、国 $i$ と国 $i + 1$ の間のみ変換が可能でした。

であれば、いわゆる貪欲法として国 $1$ , $2$ , ..., $N - 1$ から順に可能な限り通貨を交換しておけば国 $N$ の通貨の枚数が最大になります。

N = int(input())
A = list(map(int, input().split()))

for i in range(N - 1):
    s, t = map(int, input().split())
    div, mod = divmod(A[i], s)
    A[i] = mod
    A[i + 1] += t * div

print(A[-1])

C - Takahashi Gets Lost

$3 \le H, W \le 500$ , $1 \le N \le 500$ という制約からすべてのマスで「経路 $T$ で移動できますか？」というのを全探索しても、計算量が $O(H\timesW\timesN)$ = $500^{3} = 1.25 × 10^{8}$ であり、２秒で計算できる計算量の指標である $10^{8}$ を超えますが、制限時間が３秒なので PyPy で提出すれば AC します。
(とはいいつつ、私はコンテスト中 Python で提出した後 TLE になってしまい「 $10^{8}$ を超えているからよく考えたら全探索ではできないな」と勘違いしハマってしまいました)

H, W, N = map(int, input().split())
T = list(input())
S = [list(input()) for _ in range(H)]

def f(h, w):
    # h, w から移動していってすべて . なら 1 を返す
    i, j = h, w
    for t in T:
        match t:
            case "L":
                j -= 1
            case "R":
                j += 1
            case "U":
                i -= 1
            case "D":
                i += 1
        if S[i][j] == "#":
            return 0
    return 1

ans = 0
for h in range(H):
    for w in range(W):
        if S[h][w] == ".":
            ans += f(h, w)
print(ans)

D - Only one of two

「一方のみの倍数」や「両方の倍数」を満たすような個数を求める問題は包除原理を用いることが多いです。

今回求めたい「値 $x$ までの $N$ , $M$ の一方のみの倍数の数」は

$(N, M の一方のみの倍数の数) = (N の倍数の数) + (M の倍数の数) - 2 \times (N と M の最小公倍数の倍数の数)$

と表すことができます。(最後の項に $２\times$ がないなら和集合を求める時の式ですね)

あとは $x$ の値を $1$ , $2$ , ... と増やしていき「値 $x$ までの $N$ , $M$ の一方のみの倍数の数」が $K$ となる時の $x$ を求めればよいですが、入力例３を見るとわかるように $x$ は非常に大きい数になることがあるので、愚直にしてしまうと TLE になってしまいます。

そこで倍数の数は単調増加していくことを利用して「値 $x$ までの $N$ , $M$ の一方のみの倍数の数が $K$ 以上であるなら True そうでなければ False を返す」関数 $f(x)$ を定義して二分探索で最小の $x$ を見つけましょう。

ちなみに私はなまじ入力例の $N$ , $M$ がすべて互いに素であったためにはじめうっかり最小公倍数ではなく $N \times M$ の倍数を用いてしまったため WA となってしまいました。

N, M, K = map(int, input().split())

def f(x):
    # 整数 x までで (N でのみ割れるもの + M でのみ割れるもの) の個数が K 個以上あるか
    lcm_ = lcm(N, M)
    return x // N + x // M - x // lcm_ * 2 >= K

ng = -1
ok = 10 ** 60
while ok - ng > 1:
    mid = (ok + ng) // 2
    if f(mid):
        ok = mid
    else:
        ng = mid

print(ok)

E - Alternating String

高速に区間を更新する必要があるので前回同様 Lazy Segment Tree で XOR を管理するのかなーと最初思ってしまいコンテスト本番では解けませんでした。以下、解答 AC です。

まず反転させることで 良い文字列 であるかどうかがどう変わっているか考えます。
(コンテストではこの辺の考察が抜けていたので次回は頑張りたいです)

例えば、 $10\textcolor{red}{1}101010$ は $\textcolor{red}{1}1$ が連続しておりここを含むと 良い文字列 ではないです。(以下、文字列が連続している箇所の前の文字をわかりやすくするため赤色にします)
次に $10\textcolor{red}{1}101010$ を以下の３通りで反転し観察してみます。

前から５番目から８番目を反転する $10\textcolor{red}{1}1[0101]0$ → $10\textcolor{red}{11}[101\textcolor{red}{0}]0$
前から２番目から６番目を反転する $1[0\textcolor{red}{1}101]010$ → $\textcolor{red}{1}[1\textcolor{red}{0}01\textcolor{red}{0}]010$
前から４番目のみ６番目を反転する $10\textcolor{red}{1}[101]010$ → $101[01\textcolor{red}{0}]010$

こうしてみると、赤かったのが黒になったり新たに黒が赤くなっているのがカッコの前のみということから

反転する先頭 $l$ がもともと良かったら悪く、悪かったら良くなる
同様に末尾 $r$ がもともと良かったら悪く、悪かったら良くなる
その間は元の状態から全部一斉に反転するので変化しない

ということがわかります。

そこで、そもそも $S$ の隣り合っている要素の値が連続しているかを保存するリスト $T$ を定義し

クエリ $1$ の場合： $A[l - 1]$ , $A[r]$ の要素を 0 なら 1 に、 1 なら 0 にする ( $l - 1$ なのは上の実験で言うカッコの前に合わせるためです)
クエリ $2$ の場合：区間 $A[l] - A[r]$ の間に一つも $1$ がなければ 良い文字列 とする

とすれば OK です。一点更新、区間取得なので Lazy Segment Tree ではなく Segment Tree でも十分実装が可能です。

Python の AtCoder 環境は公式の C++ ライブラリを Python に移植していただいている https://github.com/not522/ac-library-python がインストールされていますので Segment Tree を import して使えます。

from atcoder.segtree import SegTree

def op(a, b):
    return a + b

e = 0

N, Q = map(int, input().split())
S = list(map(int, list(input())))

# 1-indexed してたほうが計算が簡単です
T = [0] * (N + 1)
for i in range(1, N):
    if S[i - 1] == S[i]:
        T[i] = 1

segtree = SegTree(op, e, T)

for _ in range(Q):
    t, l, r = map(int, input().split())
    match t:
        case 1:
            l -= 1
            segtree.set(l, segtree.get(l) ^ 1)
            segtree.set(r, segtree.get(r) ^ 1)
        case 2:
            ans = "Yes" if segtree.prod(l, r) == 0 else "No"
            print(ans)