EAFP

~ Easier to Ask for Forgiveness than Permission ~

Atcoder-ABC213をpythonで問題を解いてみた

目的

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

A問題

atcoder.jp

考察

  • 問題文通りに解けば良い
    • pythonのbit演算に関しては下記の通り

www.javadrive.jp

実装

A, B = map(int, input().split())

for i in range(2**8):
    if A ^ i == B:
        print(i)
        break

結果

B問題

atcoder.jp

考察

  • 選手のスコアを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問題

atcoder.jp

考察

  • H,W=109 になりうることから、格子全体を扱うことをまず諦める

    • N=105 であるため、与えられた点のみを用いてループを回しても1回 * logNな作業くらいなイメージ
  • 数のない行/列を削除して詰めていくと、x,y の値の大小で座標が決まりそうだな〜と思った

    • x=[1,3,5,8..] -> 1,2,3,4... みたいな
  • そのため、与えられたカードの座標を下記の3通りの方法で保持した

    1. x座標のみのlist
    2. y座標のみのlist
    3. カードの座標情報
  • あとは、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)

結果

D問題

DFSで、戻る経路の扱いを間違い時間内に解けなかった・・・

atcoder.jp

考察

  • N個の都市と、N-1の経路があり、基本的にDFSを使って経路を探索すれば良さそうだと思った

    • 都市のうち番号が最も小さい都市へ移動する を見て、ABC212で学んだ heapq を使えば良さそうだと思った
    • 直前にいた都市へ移動がちょっと厄介だなーと思った
  • 以前解いた、DFSを改造していく中で色々迷走してしまった・・・

  • 再帰で解くけど、再帰での処理を追いきれず解けず

  • 解答見て、再帰で解いてるの見るけどもうちょっと自分の方法で解けないか考えた

  • コンテスト後時進めるに当たって気をつけた点

    • 元いた地点に戻る場合の処理をちゃんと考えた
      • 戻る場合は、他にいく経路がない場合のみに限定する
    • 出力するための値の処理をどうするか?

実装

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) の後)
$ 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)