🚋

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

2024/02/25に公開

競技プログラミング

AtCoder

tech

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

A - Yay!

問題文
英小文字からなる文字列 $S$ が与えられます。ここで $S$ の長さは $3$ 以上 $100$ 以下です。
$S$ はある $1$ 文字を除いて全て同じ文字で構成されています。
他のどの文字とも異なる文字は前から何文字目でしょうか。

Python では count method を用いることで文字列中にある文字 $x$ が何文字あるかカウントすることができます。
そこで文字列 $S$ を一文字ずつ前から調べ count が $1$ となるものを見つけたら出力してあげましょう。

S = input()
for i, c in enumerate(S, start=1):
    if S.count(c) == 1:
        print(i)

B - Which is ahead?

$1 \ge N \ge 100$ , $1 \ge Q \ge 100$ と配列が非常に小さいので二重ループをしても計算量は $O(N\timesQ) = 10000$ であり、毎回整数 $A_{i}$ , $B{i}$ がどこにあるか調べても十分間に合います。

または $「X[i] := 整数 i が前から何番目にあるか」$ という情報を保存しているリスト $X$ を定義しそちらで毎回比較することもできます。こちらなら前計算が $O(N)$ 、比較は $O(Q)$ となり計算量は $O(N + Q)$ となります。 $N$ と $Q$ が大きい場合はこちらのほうがよさそうです。(計算量を意識しないと解けないので出題されるならC問題ぐらいでしょうか？)

後者のコードは以下のようになります。

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

X = [0] * (N + 1)
for i, p in enumerate(P):
    X[p] = i

Q = int(input())
for _ in range(Q):
    a, b = map(int, input().split())
    if X[a] < X[b]:
        print(a)
    else:
        print(b)

C - Many Replacement

何度も $S$ に含まれる文字が変化していくのを愚直に毎回反映する場合の計算量を考えてみます。
計算量が一番最悪なパターンは $S = aaaaaa...aaa$ と $a$ が $N = 2 × 10^{5}$ 個並んでおり $a$ → $b$ → $a$ と $Q = 2 × 10^{5}$ 回書き換える場合です。この場合計算量は $O(N × Q) = 4 × 10^{10}$ となり TLE となってしまいます。

そこで、毎回愚直に反映するのをやめて「現在 $a$ である文字は $b$ に置き換わりました」その後さらに「現在 $b$ である文字は $a$ に置き換わりました」という情報だけを $「X[c] := スタート時に文字 c であった文字の現在の文字」$ として辞書 $X$ に保存しておきましょう。

最後に $X$ に基づいて文字を一度だけ変換させれば OK です。

計算量は途中の $X$ の更新がアルファベットが 26 文字なので $O(N \times 26)$ 、最後の変換が $O(N)$ でできるので計算量は $O(N)$ です。

アルファベット 26 文字の列挙は手入力し TYPO をして WA をしてしまうともったいないので string.ascii_lowercase を用いるとよいです。

N: Final = int(input())
S = input()
X = {c: c for c in string.ascii_lowercase}

Q = int(input())
for _ in range(Q):
    c, d = input().split()
    for k, v in X.items():
        if v == c:
            X[k] = d

T = []
for s in S:
    T.append(X[s])

ans = "".join(T)
print(ans)

D - Square Pair

まずはノートに入力例１、２のケースや計算量 $O(N^{2})$ の以下の愚直解を実装して表示されるものを見たりしていました。

愚直解

N = 8
A = list(map(int, "2 2 4 6 3 100 100 25".split(" ")))

print(f"{N=}")
print(f"{A=}")

X = [i * i for i in range(101)]

for i in range(N):
    for j in range(i + 1, N):
        if A[i] * A[j] in X:
            print(f"{i=}, {j=}, {A[i]=}, {A[j]=}")

実行結果

N=8
A=[2, 2, 4, 6, 3, 100, 100, 25]
i=0, j=1, A[i]=2, A[j]=2
i=2, j=5, A[i]=4, A[j]=100
i=2, j=6, A[i]=4, A[j]=100
i=2, j=7, A[i]=4, A[j]=25
i=5, j=6, A[i]=100, A[j]=100
i=5, j=7, A[i]=100, A[j]=25
i=6, j=7, A[i]=100, A[j]=25

そうすると

どちらかが $0$ だと積が $0$ = $0^{2}$ になるので平方数となる
すでに平方数同士の値は積も平方数となる
平方数同士でないものも $2 \times 2$ など同じ数字同士をかけると平方数となる
また $2 \times 8$ なども平方数となる

ということがわかってきました。特に最後の情報から

素因数分解して奇数となる素数が等しければ (つまり $2 = 2^{1}, 8 = 2^{3}$ の場合など)、それらは同じ値とみなせる

といえます。

以上のことから、各 $A_{i}$ を素因数分解し $「各因数を 2 で割った後の積」$ を key とし、その数を value とした辞書 $B$ で保存していきます。

求める答えは $A_{i}$ に $0$ を含む場合少しややこしく

$v = B[0]$ の時、以下の２通り
- $0$ から $2$ つ選ぶ： ${}_v C_2$
- $0$ から $1$ つ選び、残り $N - v$ から選ぶ： $v \times (N - v)$
$v = B[0以外の値]$ の時、以下の１通り
- $x$ から $2$ つ選ぶ： ${}_v C_2$

となります。

少し込み入った計算をするためか計算量が高いため Python では TLE となってしまいます。 PyPy で提出しましょう。

from collections import defaultdict

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

def prime_factors(N):
    v = N
    p = defaultdict(int)
    for i in range(2, N):
        if i * i > N:
            break
        while v % i == 0:
            p[i] += 1
            v //= i
    if v != 1:
        p[v] += 1
    return p


# 素因数分解して奇数個の素数だけ残してグループにする各グループの NC2 の和が答え
# 0 だけ特別扱いする

B = defaultdict(int)
for a in A:
    factors_ = prime_factors(a)
    # 各因数を 2 で割る
    factors = {}
    for k, v in factors_.items():
        if v % 2 == 1:
            factors[k] = 1
    # Python は dict はキーにできないので tuple に変換する
    B[tuple(sorted(factors.items()))] += 1

ans = 0
for k, v in B.items():
    if k == ((0, 1),):
        # 0 は他のすべての値とペアになる
        ans += v * (v - 1) // 2 + v * (N - v)
    else:
        # それ以外はそのまま NC2
        ans += v * (v - 1) // 2

print(ans)

E - Last Train

経路探索の問題です。ダイクストラ法を使う場合はある点 $x$ を始点とし、 $x$ からグラフ上のすべての点までの距離を $O(M \times logN)$ で求めることができます。なので、今回の場合 $N$ を始点としたいです。

そこで、電車の路線がすべて逆に向かっているとしましょう。すなわち $i$ 番目の電車の路線は $c_{i}$ 分かけて $A_{i}$ から $B_{i}$ に行くのではなく $-c_{i}$ 分かけて $B_{i}$ から $A_{i}$ に行くと考えます。

「負の値を含まないこと」という制約がダイクストラ法を学ぶ時に出てくると思いますが、この制約はあくまで経路のコストが負と正のものが同時に存在すると閉路をグルグル回れば回るほどコストが減るみたいな経路が存在する場合正しい解を得られないことがあるのが問題でした。

今回の場合、もともとすべてコストは正であるため、逆に考えた場合のコストはすべて負であり、求めるものは最もコストが大きくなるものであり、コストと求めたいものがすべて逆になっているため問題なくダイクストラ法が利用できます。

そこでヒープキューに $(-到着予定時刻, 利用する予定の M 番目の路線)$ という情報を保存し、小さい値 (マイナスをかけているのですなわち到着予定時刻が大きいもの) から確定し、続けてその駅から乗ることのできる路線をヒープキューにいれるという作業を繰り返しましょう。

その駅から乗ることのできる路線を入れる際に、その路線の何番目に発車する電車に乗るべきかもついでに考える必要があります。

到着予定時刻より後にその路線の始発電車が出る場合：その路線を利用することはできない
到着予定時刻より前にその路線の終発電車が出る場合：終発電車にのり移動後到着予定時刻まで待機する
それ以外：可能な限り遅い電車に乗りたい。 $(到着予定時刻 - l - c)$ を $d$ で割ることでどの電車に乗ればよいかわかる

と場合分けをしましょう。

import heapq

N, M = map(int, input().split())
G = [[] for _ in range(N)]
trains = []
for i in range(M):
    l, d, k, c, a, b = map(int, input().split())
    a, b = a - 1, b - 1
    trains.append((l, d, k, c, a, b))
    G[b].append(i)

INF = float("inf")
dist = [INF] * N
# N - 1 を探索済みとみなすために INF より小さいが、得られる答えより大きな値を入れておく
dist[-1] = 10**18

queue = []
for i in range(M):
    # N - 1 と別の駅をつないでいる路線で、その路線番号と最終列車の出発時刻を queue に追加
    l, d, k, c, a, b = trains[i]
    if b == N - 1:
        queue.append((-(l + (k - 1) * d), i))
heapq.heapify(queue)

while queue:
    time, i = heapq.heappop(queue)
    time *= -1
    l_, d_, k_, c_, a, b_ = trains[i]
    if dist[a] != INF:
        continue
    dist[a] = time
    # 駅 a から利用できる路線を利用できるのであれば queue に追加
    for j in G[a]:
        l, d, k, c, na, _ = trains[j]
        # すでに探索済みか N であればスキップ
        if dist[na] != INF:
            continue
        """
        路線 j の何番目の電車に乗るべきか調べる
        time - l - c が非常に大きい場合は最終列車に乗ればよく、time - l - c が負の場合はどの列車も乗れない
        """
        v = min((time - l - c) // d, k - 1)
        if 0 <= v:
            # 路線 j の v 番目の電車に乗る
            new_time = l + v * d
            heapq.heappush(queue, (-new_time, j))

for d in dist[: N - 1]:
    if d == INF:
        print("Unreachable")
    else:
        print(d)