EAFP

~ Easier to Ask for Forgiveness than Permission ~

Atcoder-ABC212をpythonで問題を解いてみた

目的

最近、ブログに書くのサボってましたがまた再開しようと思う

  • Atcoderで上を目指すべく頑張っている中でABC212を解いたので、解説してみる
    • pypy7.3を使って解いている

A問題

atcoder.jp

考察

  • 問題文通りに解けば良い

実装

A, B = map(int, input().split())
if A > 0 and B == 0:
    print("Gold")
elif A == 0 and B > 0:
    print("Silver")
elif A > 0 and B > 0:
    print("Alloy")

結果

B問題

atcoder.jp

考察

  • 4桁が同じ数字は、inputのstrをcountすれば良さそう

    • あまりよろしくなく、O(n) で重い処理だが、 n=4 なので問題ないと判断
  • 次の数字の処理だけ、少しだけ注意

    • 基本、差をとって1になるかを考えれば良い
    • 9が来た時だけ、次の数が0になってないか判定する
  • なぜか、 コンテスト中血迷った のか、絶対値で考えて、 WA を出してしまったw

    • これだと 0101Weak になってしまう・・・
for i in range(len(X)-1):
    x1, x2 = int(X[i]), int(X[i+1])
    if abs(x1 - x2) == 1 or abs(x1-x2) == 9:
        cnt += 1

実装

X = list(input())

flag = True

if X.count(X[0]) == 4:
    flag = False
else:
    cnt = 0
    for i in range(len(X)-1):
        x1, x2 = int(X[i]), int(X[i+1])
        if x2 - x1 == 1 or (x1 == 9 and x2 == 0):
            cnt += 1
    if cnt == 3:
        flag = False

if flag:
    print("Strong")
else:
    print("Weak")

結果

C問題

atcoder.jp

考察

  • max(N, M) = 2*105 なので、 O(n2) だと TLE になるため、愚直な全探索は不可

    • なるべく、 O(n) に近くでやりたく、ループは1回に抑えたい
  • 「2つの値の差の最小値 」を考えるので、A, Bのどちらかの数列に着目し、残りをsortして、2分探索し、近しい数値で計算すれば良さそう

    • この場合、 O(nlogn) になるので、なんとかなりそう
  • bisect_left を使うが、いくつかポイントがありそう

    • 基本的に、2つの数値の間に入るので、その場合はどちらも利用し、計算する必要がありそう
    • 探索した値が、一番小さい、一番大きい場合は、1つの数値を利用すれば良い
      • 探索対象の数列内で一番大きくなる場合、 out of index になるため、 idx -1 が必要になる
  • コンテスト中に、問題文を読み間違え、 ansの値を小さくしWA をしてしまい焦った

    • アプローチが間違ってると思い、多くの時間を使ってしまった・・・

実装

from bisect import bisect_left

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

B.sort()

ans = pow(10, 10)

for i in range(N):
    a = A[i]
    idx = bisect_left(B, a)
    if idx == 0:
        b = B[idx]
        ans = min(ans, abs(a-b))
    elif idx == M:
        b = B[idx-1]
        ans = min(ans, abs(a-b))
    else:
        b1, b2 = B[idx-1], B[idx]
        ans = min(ans, abs(a-b1), abs(a-b2))

print(ans)

結果

D問題

優先度付きqueueを知らない and query 2 の扱いを誤認しており解けず・・・

atcoder.jp

考察

  • max(Q)=2*105 のため、処理を愚直に記述した際は確実に TLE するので、効率的に計算する方法を考える

  • 操作 1 普通に数値を、追加するが、 操作3 で取り出すことを考えると sort して挿入すると嬉しそう

    • 既存のlistを2分探索し、isertすればいいと思ったが、pythonのlist(linked list)のinsertはO(n)のためすごく遅くなりそう・・・
    • コンテスト中は知らなかったが、 heapq.heappush というものがあり、sortを加味しながら O(logn) で処理できるものがある

qiita.com

  • 操作 2 は都度、全ての袋の中の数を更新してると、計算量的に無理だと思い、別変数でcountし、 操作3 で取り出す際に足せばいいと考えた
    • ここで、考慮に漏れてたのが、操作2はその時に袋の中にある値のみを更新し、操作2後に入った値は更新されないという点
    • そのため、累積和を用いて考える必要がある、取り出すときには操作2の累積値を足すが、操作1の際には、その時点でのcount値を引いて、格納する必要がある
      • この際の操作1で加わる値は、過去の操作2の影響を受けてないため、すでにある値より小さくなる

qiita.com

  • 操作3 は最小値を取り出すが、その時点の最小値であるため、事前に値を全て格納し、sortして処理することは不可
    • 今回の例だとそれでも通ってしまうので、勘違いしてしまう場合もありそう
    • heapq.heappop が非常に有効な働きをする(pythonのpop(n)はO(n)になってしまうので・・・)

実装

from heapq import heapify, heappop, heappush

Q = int(input())

bag, ans = [], []
cnt = 0
heapify(bag)

for _ in range(Q):
    query = list(map(int, input().split()))
    if query[0] == 1:
        heappush(bag, query[1]-cnt)
    elif query[0] == 2:
        cnt += query[1]
    else:
        ans.append(heappop(bag)+cnt)

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

結果

E問題

全然取り組めず解説見ながら解いた

atcoder.jp

考察

  • パッと見た感じ、経路問題なので、 dfsダイクストラ法 が頭に浮かぶが、ちょっと毛色が違う
  • 通れる経路でなく、通れない経路が与えられる

  • なんとなく、動的計画法ぽい感じで、 (すべての経路でいける場合) - (いけない経路の場合) で考えれば良さそう

    • 基本すべての街に行く経路はあるので、そこの計算は複雑ではなさそう
  • dp[i][j] で考え、 i日目において、 j番目の街に行く場合の数を考えていけば良さそう

    • 基本的に、すべての街の経路があるので、 dp[i][j]=sum(dp[i-1]) - dp[i-1][j] で考えれば良さそう
      • 自己回帰の経路はないため、自分自身に戻る場合を除いている
    • 使えない経路があるため、その場合を除く必要がある
      • dp[i][j] に対して、 経路のない街k の d[i-1][k] を除く必要がある

実装

modをとることに注意して計算する

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

graph = [[] for _ in range(N)]
dp = [[0] * N for _ in range(K+1)]
mod = 998244353

for _ in range(M):
    u, v = map(int, input().split())
    graph[u-1].append(v-1)
    graph[v-1].append(u-1)

dp[0][0] = 1

for i in range(1, K+1):
    s = sum(dp[i-1])
    for j in range(N):
        cnt = 0
        for k in graph[j]:
            cnt = (cnt + dp[i-1][k]) % mod
        dp[i][j] = (s - dp[i-1][j] - cnt) % mod

print(dp[K][0])

結果

まとめ

  • 優先度付きqueueは利用したことなかったので、しっかり覚えたい(内部実装も含め)

ja.wikipedia.org

  • D問題は茶色diffだったが、解けなかった・・・が、8問体制になりD問題が易化する期待が持てる

    • 茶色コーダにとっては嬉しい
  • 水色以下の問題は、今後も復習し、解けるようにしていく

    • 定型90問も解き続けているので、合わせて続けていく
    • ABCのC問題までの早解きも続けていく