Atcoder-ABC212をpythonで問題を解いてみた
目的
最近、ブログに書くのサボってましたがまた再開しようと思う
- Atcoderで上を目指すべく頑張っている中でABC212を解いたので、解説してみる
- pypy7.3を使って解いている
A問題
考察
- 問題文通りに解けば良い
実装
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問題
考察
4桁が同じ数字は、inputのstrをcountすれば良さそう
- あまりよろしくなく、O(n) で重い処理だが、 n=4 なので問題ないと判断
次の数字の処理だけ、少しだけ注意
- 基本、差をとって1になるかを考えれば良い
- 9が来た時だけ、次の数が0になってないか判定する
なぜか、 コンテスト中血迷った のか、絶対値で考えて、
WA
を出してしまったw- これだと
0101
もWeak
になってしまう・・・
- これだと
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問題
考察
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 の扱いを誤認しており解けず・・・
考察
max(Q)=2*105 のため、処理を愚直に記述した際は確実に
TLE
するので、効率的に計算する方法を考える操作 1
普通に数値を、追加するが、操作3
で取り出すことを考えるとsort
して挿入すると嬉しそう- 既存のlistを2分探索し、isertすればいいと思ったが、pythonのlist(linked list)のinsertはO(n)のためすごく遅くなりそう・・・
- コンテスト中は知らなかったが、
heapq.heappush
というものがあり、sortを加味しながら O(logn) で処理できるものがある- 普通にlistにappendもできるが、その場合はsortされないため、間違った答えになる
操作 2
は都度、全ての袋の中の数を更新してると、計算量的に無理だと思い、別変数でcountし、操作3
で取り出す際に足せばいいと考えた- ここで、考慮に漏れてたのが、操作2はその時に袋の中にある値のみを更新し、操作2後に入った値は更新されないという点
- そのため、累積和を用いて考える必要がある、取り出すときには操作2の累積値を足すが、操作1の際には、その時点でのcount値を引いて、格納する必要がある
- この際の操作1で加わる値は、過去の操作2の影響を受けてないため、すでにある値より小さくなる
操作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問題
全然取り組めず解説見ながら解いた
考察
- パッと見た感じ、経路問題なので、
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] を除く必要がある
- dp[i][j] に対して、
- 基本的に、すべての街の経路があるので、
実装
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は利用したことなかったので、しっかり覚えたい(内部実装も含め)
D問題は茶色diffだったが、解けなかった・・・が、8問体制になりD問題が易化する期待が持てる
- 茶色コーダにとっては嬉しい
水色以下の問題は、今後も復習し、解けるようにしていく
- 定型90問も解き続けているので、合わせて続けていく
- ABCのC問題までの早解きも続けていく