Atcoder-ABC217をpythonで解いてみた
目的
- Atcoderで上を目指すべく頑張っている中でABC217を解いたので、解説してみる
- pypy7.3を使って解いている
A問題
考察
- 問題文通りに解けば良い
- pythonのsortを使うと、文字列を辞書順に並べてくれる(大文字、小文字が含まれる場合は、大文字優先になる)
ASCIIbetical order
のため
実装
S, T = input().split() ans = [S, T] ans.sort() if ans[0] == S: print("Yes") else: print("No")
結果
B問題
考察
- 問題文通りに解けば良い
- "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問題
考察
ここ最近で一番簡単な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問題
考察
解法が思いついたが実装が思いつかなかった、listだと時間かかってTLE取れずに終了した
- 長さL = max(109) に着目すると計算が終わらないので、木の分割点を記録し、それらを利用して解く
- c=1 の時は、分割点を管理するlistに値を追加
- c=2 の時は、与えられたxを使って、list(ex. splitsとする)を二分探索で探索する(-> 結果をidxとする)
- 長さ = splits[idx] - splits[idx-1] となる
- ここでいくつかの問題にぶつかる
- splitsをsortする必要があるが、都度sortしていると時間が足らない
- べき論で言えば、appendする際に、sortして入れられると良いのだが、そのような方法もない
- pythonのlistのinsortはO(n)で非常に遅いので、使うと厳しいと思った
- heapqでは、最小値はO(logn)取り出せるが、searchができず、中間の値を取ることはできない
- heapfyされたlistは、listでいうsortの順では格納されておらず、bisectが使えない
arrayは早いらしいと聞いてtryした
-
- 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問題
考察
D問題と同じく、array頼みでやるも、deleteが遅くてTLEする
- pop(idx) は O(n) なので、arrayがlistよりも多少早くても間に合わない
heapqとdequeを組み合わせて解く
- 公式解説だとわかりにくかったが 、下記のように自分は理解した
- deque/ heapqをそれぞれ用意する
- sort前は、dequeに値を入れて、そこから取り出す
- sort時は、dequeを毎回sortすると時間かかるので、dequeの中身をheapqに入れる
- heapqは取り出すときに最小値をO(logn)でpopできる
- その後は、下記の要領で値を取り出す
- heapqの中身がある時は、そこから取り出す
- heapqが空になったら、dequeから取り出す
- 上記を繰り返すことで解けた
- 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も)を続ける
- arrayは今後も使えそうなので覚えておくと良さそう
- Binary Tree等で必要なlibraryはこれを機にコツコツ作っておくと良さそう