Atcoder-ABC223をpythonで解いてみた
目的
- Atcoderで上を目指すべく頑張っている中でABC223を解いたので、解説してみる
- pypy7.3を使って解いている
A問題
考察
- 問題文通りに解けば良い
- X=0があるので、100で割った余りが1以上であることも条件に含める必要がある
実装
X = int(input()) if X / 100 >= 1 and X % 100 == 0: print("Yes") else: print("No")
結果
B問題
考察
- 右シフトでも左シフトでも、続けて行った結果できる文字列は同じであることに気づく
- なので、1文字づつどちらか好きな方にshiftして、全パターンの文字列を作成する
- Sは1000文字以下なので十分処理的には間に合う
- 作成した文字列をpythonの組み込みsort(O(NlogN))で並び替える
- defaultで、辞書順に並び替えてくれる
実装
from collections import deque S = deque(input()) strings = ["".join(S)] for _ in range(len(S)): s = S.popleft() S.append(s) strings.append("".join(S)) strings.sort() print(strings[0]) print(strings[-1])
結果
C問題
考察
A/B
で、その導線が燃え尽きる時間がわかる導火線は長さが A cm で、 1 秒あたりB cm の一定の速さで燃えます
とあるので- そのため、A/Bの和(=Tとする)を求めることで、導線を片方から燃やし尽くすまでの時間がわかる
- N<=105 なので、O(N) なら間に合う
- T/2で、左端からどれだけ進むかを計算すれば良い
以下で場合分けをして考える
- 導線1本燃やし尽くす場合(残り時間時間 >= A/B)
- 長さAを足せば良い
- 途中までしか燃やさない場合(残り時間時間 < A/B)
- 速さB(cm/s) * 残り時間(s) を足せば良い
- 導線1本燃やし尽くす場合(残り時間時間 >= A/B)
実装
N = int(input()) line = [] T = 0.0 for _ in range(N): A, B = map(int, input().split()) line.append((A, B)) T += A/B T /= 2 ans = 0.0 for i in range(N): A, B = line[i] if T >= A/B: ans += A T -= A/B else: ans += B*T break print(ans)
結果
D問題
考察
トポロジカルソートは早速思いついたが、どのように辞書順にするか思いつかず時間切れ
ただ、これで解くと、辞書順にはならない
- 例えば、例1でいくと
[2, 3, 1, 4]
のようになってしまう - これは、トポロジカルソート自体は、通常のsortと違って一意に決まらないことによるもの
- 例えば、例1でいくと
そのため、事前に i -> i + 1 で辺を貼り、今回与えられる制約があれば、そちらを優先するということを考えた
- ただ、i -> i + 1 or 与えられる辺の情報を、効率よく探索し、かつsortして保持する方法がないので、諦めた
結論としては、
heapq
を使えば良い- 元のトポロジカルソートでは、
deque
で保持してる部分を、heapqで書き換えることで、小さいものから並べることができる
- 元のトポロジカルソートでは、
実装
from heapq import heappop, heappush N, M = map(int, input().split()) edge = [[] for _ in range(N)] cnt = [0] * N for _ in range(M): A, B = map(int, input().split()) edge[A-1].append(B-1) cnt[B-1] += 1 heap = [] for i in range(N): if cnt[i] == 0: heappush(heap, i) ans = [] while heap: cur = heappop(heap) ans.append(cur+1) for nxt in edge[cur]: cnt[nxt] -= 1 if cnt[nxt] == 0: heappush(heap, nxt) if len(ans) < N: print(-1) else: print(*ans)
結果
まとめ
- 今回もD問題解けなかったが、C問題まで順調に解けたので、rateは上がった
- D問題はトポロジカルソートを深く理解できてなかったことにあるのかなーと思っており、ちょっと変形されると解けなかったのが敗因だと思ってる
- D埋めも結構進んできたので、諦めず1日1AC続けて、次こそD問題解くぞ!
今日も1日1AC
— オ-℃ (@kazu_kun0716) 2021年10月16日
単に長い、RとかLを貪欲にひっくり返せばいいのかと思ったけど、そもそもの戦略が違った
AtCoder Beginner Contest 140 Dhttps://t.co/scxK7CxOQm