Atcoder-ABC213をpythonで問題を解いてみた
目的
- Atcoderで上を目指すべく頑張っている中でABC213を解いたので、解説してみる
- pypy7.3を使って解いている
A問題
考察
- 問題文通りに解けば良い
- pythonのbit演算に関しては下記の通り
実装
A, B = map(int, input().split()) for i in range(2**8): if A ^ i == B: print(i) break
結果
B問題
考察
選手のスコアをsortして、2番目に大きいものを出せばいい
- この際に出力するのは、スコアではなく、選手番号であることに注意
以下の方法を考えた
- 選手のスコアの数列Aをコピーし、数列Bをsortする
- 数列Bの中で二番目に大きいもの(=後ろから2番目)の値を取得し、元の数列Aの中で何番目にその数があるのかを確認する(= 選手番号を取得する)
- 今回、pythonのlistのindex(=O(n))を使っているが、 max(N)=2*105 のためTLEしないと判断(実装スピードを優先)
実装
N = int(input()) A = list(map(int, input().split())) B = A.copy() B.sort() print(A.index(B[-2]) + 1)
結果
C問題
考察
H,W=109 になりうることから、格子全体を扱うことをまず諦める
- N=105 であるため、与えられた点のみを用いてループを回しても1回 * logNな作業くらいなイメージ
数のない行/列を削除して詰めていくと、x,y の値の大小で座標が決まりそうだな〜と思った
- x=[1,3,5,8..] -> 1,2,3,4... みたいな
そのため、与えられたカードの座標を下記の3通りの方法で保持した
- x座標のみのlist
- y座標のみのlist
- カードの座標情報
あとは、3.の情報をループで回して、そこで得られる (x,y) の情報に関して、1./2. のlistで何番目になるのかを探索する
- 線形探索だとO(N) なので、二分探索を利用して探索する(O(logN))
- 1./2.のlistは、同じ値を含む可能性があるので、setで重複の値を削除することを忘れなく
実装
from bisect import bisect_left _, _, N = map(int, input().split()) x_list, y_list = [], [] points = [] for _ in range(N): A, B = map(int, input().split()) x_list.append(A) y_list.append(B) points.append([A, B]) x_list.sort() y_list.sort() x_list = list(set(x_list)) y_list = list(set(y_list)) for i in range(len(points)): x, y = points[i][0], points[i][1] idx_x = bisect_left(x_list, x) + 1 idx_y = bisect_left(y_list, y) + 1 print(idx_x, idx_y)
結果
- 無事に解けた
- WA後にすぐ重複漏れに気づいてよかったー^ ^;
D問題
DFSで、戻る経路の扱いを間違い時間内に解けなかった・・・
考察
N個の都市と、N-1の経路があり、基本的にDFSを使って経路を探索すれば良さそうだと思った
都市のうち番号が最も小さい都市へ移動する
を見て、ABC212で学んだheapq
を使えば良さそうだと思った- 直前にいた都市へ移動がちょっと厄介だなーと思った
以前解いた、DFSを改造していく中で色々迷走してしまった・・・
-
- whileでの実装に変えるも、時すでに遅く、heapqで戻りの経路の扱いを戸惑った結果時間切れした
コンテスト後時進めるに当たって気をつけた点
- 元いた地点に戻る場合の処理をちゃんと考えた
- 戻る場合は、他にいく経路がない場合のみに限定する
- 出力するための値の処理をどうするか?
- 通った経路自体をstackが保持してたことに気づかず、自前頑張ってた
- 無駄であるので、素直にstack(実際はlist)の値使って無事解けた
- 元いた地点に戻る場合の処理をちゃんと考えた
実装
from heapq import heappop, heappush N = int(input()) edges = [[] for _ in range(N)] for _ in range(N-1): A, B = map(int, input().split()) heappush(edges[A-1], B-1) heappush(edges[B-1], A-1) pre, stack, ans = -1, [0], [] while stack: cur = stack[-1] if not edges[cur]: ans.append(stack.pop()+1) continue next = heappop(edges[cur]) if pre == next and len(edges[cur]) > 0: tmp = next next = heappop(edges[cur]) heappush(edges[cur], tmp) stack.append(next) pre = cur print(*ans[::-1])
結果
- 無事に解けた
- 問題取り組んだ初期は、今回は解けたかなーと思ったけど、実際解ききれず...orz
まとめ
D問題が安定して解けてこないとperformance上がってこないので勉強を続ける
- コンテストにでて、解けなかった問題の復習
- 定型90問を解き進める(☆5以下のみ)
D問題の解説見てやってみて再帰を学び直した
- 再帰でreturnした場合は、呼び出し元の処理に戻る
- そのため、探索先がなくreturnした場合、元の処理で戻りの経路の処理が可能(
dfs(nxt, cur)
の後)
- そのため、探索先がなくreturnした場合、元の処理で戻りの経路の処理が可能(
- 再帰でreturnした場合は、呼び出し元の処理に戻る
$ python d_2.py 4 1 2 4 2 3 1 [[], [2, 3], [1, 4], [1], [2]] before: 1 before: 2 before: 4 after: 4 after: 2 before: 3 after: 3 after: 1 1 2 4 2 1 3 1 $ cat d_2.py import sys sys.setrecursionlimit(pow(10, 9)) N = int(input()) G = [[] for i in range(N+1)] for i in range(N-1): a, b = map(int, input().split()) G[a].append(b) G[b].append(a) for i in range(N+1): G[i].sort() ans = [] print(G) def dfs(crr, pre): ans.append(crr) print("before:", crr) for nxt in G[crr]: if nxt != pre: dfs(nxt, crr) ans.append(crr) print("after:", crr) dfs(1, -1) print(*ans)