EAFP

~ Easier to Ask for Forgiveness than Permission ~

Atcoder-ABC217をpythonで解いてみた

目的

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

A問題

atcoder.jp

考察

  • 問題文通りに解けば良い
  • pythonのsortを使うと、文字列を辞書順に並べてくれる(大文字、小文字が含まれる場合は、大文字優先になる)
    • ASCIIbetical order のため

www.learnbyexample.org

実装

S, T = input().split()

ans = [S, T]
ans.sort()

if ans[0] == S:
    print("Yes")
else:
    print("No")

結果

B問題

atcoder.jp

考察

  • 問題文通りに解けば良い
  • "ABC", "ARC", "AGC", "AHC" のlistをforで回して、入力で受け取ったものでないものがあれば、それを出力する
  • 効率悪そうだけど、入力が非常に少ないので、スピード優先した

実装

contests = [input() for _ in range(3)]

for contest in ("ABC", "ARC", "AGC", "AHC"):
    if contest not in contests:
        print(contest)
        break

結果

C問題

atcoder.jp

考察

ここ最近で一番簡単なC問題だったような気がする

  • 問題文通りに解けば良い
  • 0-indexedか1-indexedに気をつけること

実装

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

q = [0] * N

for i in range(N):
    v = i + 1
    q[P[i] - 1] = v

print(*q)

結果

D問題

atcoder.jp

考察

解法が思いついたが実装が思いつかなかった、listだと時間かかってTLE取れずに終了した

  • 長さL = max(109) に着目すると計算が終わらないので、木の分割点を記録し、それらを利用して解く
    • c=1 の時は、分割点を管理するlistに値を追加
    • c=2 の時は、与えられたxを使って、list(ex. splitsとする)を二分探索で探索する(-> 結果をidxとする)
      • 長さ = splits[idx] - splits[idx-1] となる

f:id:kazu_0716:20210906233842p:plain
ABC217 D問題メモ

  • ここでいくつかの問題にぶつかる
    • splitsをsortする必要があるが、都度sortしていると時間が足らない
    • べき論で言えば、appendする際に、sortして入れられると良いのだが、そのような方法もない
      • pythonのlistのinsortはO(n)で非常に遅いので、使うと厳しいと思った
    • heapqでは、最小値はO(logn)取り出せるが、searchができず、中間の値を取ることはできない
      • heapfyされたlistは、listでいうsortの順では格納されておらず、bisectが使えない

arrayは早いらしいと聞いてtryした

  • listだとダメ

    • insortが遅いので、1問TLEする
  • arrayだと、insertの速度がlistより改善されているよう

    • なぜだかは分からなかった(調査中)

実装

from array import array
from bisect import bisect_left, insort_left

L, Q = map(int, input().split())

splits = array("I", [0, L])
ans = []

for _ in range(Q):
    c, x = map(int, input().split())
    if c == 1:
        insort_left(splits, x)
    else:
        idx = bisect_left(splits, x)
        ans.append(splits[idx] - splits[idx-1])

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

結果

E問題

atcoder.jp

考察

D問題と同じく、array頼みでやるも、deleteが遅くてTLEする

heapqとdequeを組み合わせて解く

  • 公式解説だとわかりにくかったが 、下記のように自分は理解した
    • deque/ heapqをそれぞれ用意する
    • sort前は、dequeに値を入れて、そこから取り出す
    • sort時は、dequeを毎回sortすると時間かかるので、dequeの中身をheapqに入れる
      • heapqは取り出すときに最小値をO(logn)でpopできる
    • その後は、下記の要領で値を取り出す
      • heapqの中身がある時は、そこから取り出す
      • heapqが空になったら、dequeから取り出す

f:id:kazu_0716:20210907222648p:plain
ABC217 Eメモ

  • 上記を繰り返すことで解けた
    • dequeからpopして、heapqに入れるところが重そうだけど、最大でもO(nlogn)なので、なんとかなるという理解

実装

from collections import deque
from heapq import heappop, heappush

Q = int(input())

queue = deque([])
heap = []
ans = []

for _ in range(Q):
    q = input().split()
    q[0] = int(q[0])
    if q[0] == 1:
        x = int(q[1])
        queue.append(x)
    elif q[0] == 2:
        if heap:
            ans.append(heappop(heap))
        else:
            ans.append(queue.popleft())
    else:
        while queue:
            heappush(heap, queue.pop())

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

結果

まとめ

  • 今回もC止まりで、圧倒的に伸び悩んでいる
    • 腐らず、D埋め(一部Eも)を続ける

f:id:kazu_0716:20210907223235p:plain
ABC217の結果

  • arrayは今後も使えそうなので覚えておくと良さそう
  • Binary Tree等で必要なlibraryはこれを機にコツコツ作っておくと良さそう