EAFP

~ Easier to Ask for Forgiveness than Permission ~

Atcoder-ABC223をpythonで解いてみた

目的

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

A問題

atcoder.jp

考察

  • 問題文通りに解けば良い
  • X=0があるので、100で割った余りが1以上であることも条件に含める必要がある

実装

X = int(input())

if X / 100 >= 1 and X % 100 == 0:
    print("Yes")
else:
    print("No")

結果

B問題

atcoder.jp

考察

  • 右シフトでも左シフトでも、続けて行った結果できる文字列は同じであることに気づく
  • なので、1文字づつどちらか好きな方にshiftして、全パターンの文字列を作成する
  • Sは1000文字以下なので十分処理的には間に合う
  • 作成した文字列をpythonの組み込みsort(O(NlogN))で並び替える
    • defaultで、辞書順に並び替えてくれる

docs.python.org

実装

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問題

atcoder.jp

考察

  • 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) を足せば良い

実装

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問題

atcoder.jp

考察

トポロジカルソートは早速思いついたが、どのように辞書順にするか思いつかず時間切れ

ta7uw.hatenablog.com

  • ただ、これで解くと、辞書順にはならない

    • 例えば、例1でいくと [2, 3, 1, 4] のようになってしまう
    • これは、トポロジカルソート自体は、通常のsortと違って一意に決まらないことによるもの
  • そのため、事前に i -> i + 1 で辺を貼り、今回与えられる制約があれば、そちらを優先するということを考えた

    • ただ、i -> i + 1 or 与えられる辺の情報を、効率よく探索し、かつsortして保持する方法がないので、諦めた
      f:id:kazu_0716:20211018184312p:plain
      ABC223 Dメモ
  • 結論としては、 heapq を使えば良い

    • 元のトポロジカルソートでは、 deque で保持してる部分を、heapqで書き換えることで、小さいものから並べることができる

docs.python.org

実装

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は上がった

f:id:kazu_0716:20211018184728p:plain
ABC223の結果

  • D問題はトポロジカルソートを深く理解できてなかったことにあるのかなーと思っており、ちょっと変形されると解けなかったのが敗因だと思ってる
    • D埋めも結構進んできたので、諦めず1日1AC続けて、次こそD問題解くぞ!