EAFP

~ Easier to Ask for Forgiveness than Permission ~

Atcoder-ABC218をpythonで解いてみた

目的

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

A問題

atcoder.jp

考察

  • 問題文通りに解けば良い

実装

N = int(input())
S = input()

if S[N-1] == "o":
    print("Yes")
else:
    print("No")

結果

B問題

atcoder.jp

考察

  • 問題文通りに解けば良い
  • ACSIIコードを利用する(a=97, b=98, ... となる)

qiita.com

実装

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

ans = []

for i in range(len(P)):
    ans.append(chr(P[i]+96))

print(*ans,sep="")

結果

C問題

atcoder.jp

考察

  • 各図形をトリミングして考えれば良さそう
  • 平行移動に関しては、トリミング結果と同一であれば良い
  • 90度回転を3度行い、基の図形と同様になるかを確認する

  • トリミングは、図形の左上詰で考える

    • # が含むx, y座標の最小値、最大値をそれぞれ取得し、座標を変換する

f:id:kazu_0716:20210916012344p:plain
トリミングのイメージ

実装

提出したコードをリファクタしたもの

N = int(input())
S, T = [], []


def set_points(l):
    min_x, max_x, min_y, max_y = 300, -1, 300, -1
    for i in range(N):
        s = list(input())
        for j in range(len(s)):
            if s[j] == "#":
                l.append([j, i])
                min_x = min(min_x, j)
                max_x = max(max_x, j)
                min_y = min(min_y, i)
                max_y = max(max_y, i)
    return min_x, max_x, min_y, max_y


def convert(l, min_x, max_x, min_y, max_y):
    shape = [[0] * (max_x - min_x + 1)
             for _ in range((max_y - min_y + 1))]
    for x, y in l:
        x -= min_x
        y -= min_y
        shape[y][x] = 1
    return shape


min_xs, max_xs, min_ys, max_ys = set_points(S)
min_xt, max_xt, min_yt, max_yt = set_points(T)

s = convert(S, min_xs, max_xs, min_ys, max_ys)
t = convert(T, min_xt, max_xt, min_yt, max_yt)

flag = False
for _ in range(4):
    if s == t:
        flag = True
        break
    s = list(map(list, zip(*s[::-1])))

if flag:
    print("Yes")
else:
    print("No")

結果

D問題

atcoder.jp

考察

解説では、対角線上の2点を求めていたが、別のアプローチを取った

  • 長方形の左下の点(P1)を定める
  • P1のx座標の中のどれかが、同じ点がP2となる
  • P1のy座標の中のどれかが、同じ点がP3となる
  • P4 = (P3x, P2y)が、存在するか確認し、あればcountする

f:id:kazu_0716:20210916013306p:plain
ABC218 Dのメモ

実装

from itertools import combinations

N = int(input())
X, Y = {}, {}

ans = 0

for _ in range(N):
    x, y = map(int, input().split())
    if x in X:
        X[x].add((x, y))
    else:
        X[x] = set([(x, y)])
    if y in Y:
        Y[y].add((x, y))
    else:
        Y[y] = set([(x, y)])

for x in X:
    xset = X[x]
    for p1, p2 in combinations(xset, 2):
        yset = Y[p1[1]]
        yset -= set([p1, p2])
        for p3 in yset:
            if (p3[0], p2[1]) in Y[p2[1]]:
                ans += 1

print(ans)

結果

E問題

atcoder.jp

考察

本番中は時間なくて解けなかった

  • 最小全域木問題であり、クラスカル法で解くことを考える
  • UnionFind-Treeを使うことは分かったが、どのように結合していくかが分からなかった

dai1741.github.io

  • 今回は、コストの小さい順に各nodeをUninFind-Treeで結合していく
    • 経路がマイナスなものは、結合する
    • それぞれのnodeの親が違う場合も結合する
    • それ以外の場合は、edgeを切っても良いので、コストとして加算する
      • 結合しない

実装

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def same(self, x, y):
        return self.find(x) == self.find(y)


N, M = map(int, input().split())
uf = UnionFind(N)

edges = [tuple(map(int, input().split())) for _ in range(M)]
edges.sort(key=lambda x: x[2])
ans = 0

for a, b, c in edges:
    if c < 0 or not uf.same(a-1, b-1):
        uf.union(a-1, b-1)
    else:
        ans += c

print(ans)

結果

まとめ

  • 今回は、D問題まで解けた!次も頑張るぞ!
    • 人生2度目のD問題解くのに成功し、非常に嬉しい

f:id:kazu_0716:20210916014044p:plain
ABC218の結果

  • E問題は最小全域木問題で、典型問題だったが、勉強不足で解けなかった
    • 今回クラスカル法も勉強でき、UninonFindの使い方も学べてよかった(目的に応じ、特定順序でsortしたのちに、結合していく)

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はこれを機にコツコツ作っておくと良さそう

Atcoder-ABC215をpythonで解いてみた

目的

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

A問題

atcoder.jp

考察

  • 問題文通りに解けば良い

実装

S = input()

if S == "Hello,World!":
    print("AC")
else:
    print("WA")

結果

B問題

atcoder.jp

考察

  • logを使って解いたが、数値誤差により WA を出した
  • 本番時は、厳密に原因まで分からなかったが、for文で回す方法にshiftし、無事解けた(2**60程度まで計算すれば良いことはlog使ってた際にわかっていたので)
  • pow(2,60) とかにどの程度時間がかかるか不明だったが、ローカルで実行して高速だったのでいけると判断した

  • なるべく小数を使わないようにするという基本を学び直した

atcoder.jp

実装

N = int(input())

ans = 0

for i in range(0, 60):
    if pow(2, i) <= N:
        ans = i
    else:
        break

print(ans)

結果

C問題

atcoder.jp

考察

並べ替えで作成可能な文字列作成に関して

  • Sの長さが、最大8なので、順列(permutation)や組み合わせ(combination)が使えると思った
    • そのため、itertools.permutations を利用した
    • 同じ文字列がSに含まれる場合、重複するのでsetで重複した文字列を取り除いた
      • 8!=40320 なので、そこそこ思い処理してもTLEにはならないと思って雑に解いた部分もある

sortに関して

  • pythonのsortが文字列をアルファベット順にsortしてくれるので、それを利用した
    • 通常のsortは O(nlogn) であるが、事前に各文字列のscoreを求めるので通常の数値比較より重い処理になるはず
      • 文字列をasciiコードに変換し、上位の桁になるほど重くなる(ex. n桁の場合、10n-1 で評価する)とかでスコアを決めてるのではないかと思っている
    • これも、高々 40320 個の文字列しかないはずなので、なんとかなると思って利用した
$ python
Python 3.6.9 (1608da62bfc7, Dec 23 2019, 10:50:17)
[PyPy 7.3.0 with GCC 4.2.1 Compatible Apple LLVM 10.0.0 (clang-1000.11.45.5)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>>> test = ["zz","aaa", "aab", "cacs","baas" ]
>>>> test.sort()
>>>> print(test)
['aaa', 'aab', 'baas', 'cacs', 'zz']

実装

from itertools import permutations

S, K = input().split()
K = int(K)

ans = set()

for p in permutations(S):
    s = "".join(p)
    ans.add(s)

ans = list(ans)
ans.sort()
print(ans[K-1])

結果

D問題

中々筋のいい方針が立たずに、時間ばかり経って解けなかった

atcoder.jp

考察

試験中考えてたこと

  • N,M=105 なので、O(NlogN), O(N√N) 以内で解く必要がありそうだと考えた

    • 愚直にやるとO(NM)なので、間に合わない
  • 何となく素数を列挙して足りないものを足せば良さそうだと思った

    • ここで見たような気がするなーと思い、コピペして利用した

ja.wikipedia.org

  • ただ、素数列挙するだけではダメで、素数でないけど、数列Aとは互いに素になるものも、あるはずで、それをどうしたら見つかるか?が分からず終わった

f:id:kazu_0716:20210822022504p:plain
ABC215D メモ

解説を見た後

  • ちょっと考えたが、事前にM以下の数字の数列を用意し、不要なものを消すと言うのは、なんだか計算量多くなりそうでやめたが、そっちで行けばよかった
    • 素因数分解するとできそうだと思ったけど、出した素因数をどう使っていくのか(解説だと倍数を消していく)と言う部分の発想がなかった

atcoder.jp

qiita.com

  • setの利用
    • pythonのlistだと、特定の数値を含んでいるのか、その数値をlistから削除するのもO(n)なので利用できないと思った
      • 2分探索で、数値を含んでるかどうかはある程度高速で判定できるが、削除はどうしようもないと思った
    • dictかsetで考えたが、今回は数値のみ扱えればいいのでsetを使った(理由は下記の通り)
      • 要素探索がaverageでO(1)
      • 要素削除がaverageでO(1)

wiki.python.org

  • エラトステネスの篩の理解
    • 下記で、ざっくり理解した
    • 今回は、素因数分解で求めた、素因数の定数倍のものを、M以下の整数列から削除していけば良い

manabitimes.jp

実装

N, M = map(int, input().split())
A = tuple(map(int, input().split()))

s = set(range(1, M+1))
p = set()

for i in range(N):
    a, j = A[i], 2
    while pow(j, 2) <= a:
        if a % j == 0:
            p.add(j)
            p.add(a//j)
        j += 1
    if a != 1:
        p.add(a)

for prime in p:
    i = 1
    while prime * i <= M:
        if prime * i in s:
            s.discard(prime * i)
        i += 1

print(len(s))
print(*s, sep="\n")

結果

まとめ

  • 今回もD問題解けなかった(diff的には茶色だが)

    • 整数問題系の演習量が足りてないと思う部分もあるので、今回を気に増やしていく
    • 高速な素因数分解や、素数列挙の方法等を学んだので、より理解を深めていきたい
  • setをあまり使ってこなかったが、今回計算量なども学べて、構造の理解も深まりよかった

  • 引き続き、D問題の過去問を進め、D問題がコンテスト中に解けるように、頑張っていきたい

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

目的

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

A問題

atcoder.jp

考察

  • 問題文通りに解けば良い

実装

N = int(input())

if 1 <= N and N <= 125:
    print(4)
elif 126 <= N and N <= 211:
    print(6)
else:
    print(8)

結果

B問題

atcoder.jp

考察

  • S<=100, T<=10000 なので、a, b, cを100以下にして全文探索すれば良さそう
  • 1003 = 106 なので、時間内に終わると考えた
  • 愚直に3重ループを書く

  • 一瞬、数式に着目して賢く解けるんじゃないか?とも思ったけど、早く解くことを優先した

    • 実際、3変数なのでそんなもんないw

実装

S, T = map(int, input().split())

ans = 0

for a in range(101):
    for b in range(101):
        for c in range(101):
            if a + b + c <= S and a * b * c <= T:
                ans += 1

print(ans)

結果

C問題

atcoder.jp

考察

  • N<=200,000 なので、2重ループは無理そう
  • せいぜいO(NlogN)以内で解かなければなれないと思った

  • i, i+1の間には2つの関係性がありそう(dp[i], dp[i+1]をそれぞれi番目のすぬけ君が初めて宝石をもらう時刻とする)

    • dp[i+1] = dp[i] + Si
    • dp[i+1] = T[i+1]
      • どちらか小さい方になる

f:id:kazu_0716:20210815021853p:plain
dp[i], dp[i+1] の遷移に関して

実装

N = int(input())
S = list(map(int, input().split()))
T = list(map(int, input().split()))

dp = [0] * N
dp[0] = T[0]

for i in range(1, N):
    dp[i] = min(dp[i - 1] + S[i - 1], T[i])

dp[0] = min(dp[0], dp[N - 1] + S[N - 1])

for i in range(1, N):
    dp[i] = min(dp[i - 1] + S[i - 1], T[i])

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

結果

D問題

BFSとかで、f(i, j) は求められても、馬鹿正直に計算するとO(N2)なので、どうしようと思っていて終わった

atcoder.jp

考察

  • 最初は何も考えず、前に解いたダイクストラのコードをコピペした

    • これ、経路の長さじゃなくて、到達点までに通った経路の最大値の総和を求めることに気づく
  • DFSとかBFSで経路を探索しながら、f(u, v) の総和を出すにはどうすればいいか悩む(O(N2)では確実にTLEなので)

    • 多分、f(u, v)は同じものがあるので、賢く数え上げるんだろーなーくらいには思ったけど、どうすればいいかわからず時間切れ
    • DFSした上で、その計算するのも厳しそうだなーと思い、多分発想が間違ってるんだろうなと思って多くの時間を過ごしたw

f:id:kazu_0716:20210815023023p:plain
214D解いたときのメモ

解説を見てUnion Findを使って解くことを知る

note.nkmk.me

  • 正直、公式解説読んでも全く分からなかったw

    • 解説動画を見て「なるほど、非常に賢い!」と思ったw
  • 辺に着目したときに、それぞれの辺の先の要素数の掛け算と、辺の重みで計算できる

    • ここで、Union Findを使って、辺で繋がれる先々の要素数をグルーピングする
    • 繋ぐときは、unionで同じグループとする
  • その上で、小さいコスト順にsortした上で、上記を実行する
    • 辺の最大値を求めるので、小さい順に処理すれば、前の処理に遡って更新する必要がないため
      • 正直、sortするっていうのは、全く発想になくて、賢くて震えたのと、水色までの距離を感じた(今回のD問題は水色diff)

f:id:kazu_0716:20210815023454p:plain
214D 解説理解のメモ

実装

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]


N = int(input())
uf = UnionFind(N)
ans = 0
edges = []

for _ in range(N-1):
    u, v, w = map(int, input().split())
    edges.append((u-1, v-1, w))

edges.sort(key=lambda x: x[2])

for u, v, w in edges:
    size1 = uf.size(u)
    size2 = uf.size(v)
    uf.union(u, v)
    ans += size1 * size2 * w

print(ans)

結果

まとめ

  • 今回のD問題は難しく、手が出なかった感じがした

    • UnionFindは汎用性高そうなので、関連する類題を解こうと思った
  • 前回もC問題で、WAしてしまったので、1回で解けるようにしたい

    • 今回は気合入れてメモ書いてからやったが、WA出してしまったので、まだまだだと感じている

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)

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

目的

最近、ブログに書くのサボってましたがまた再開しようと思う

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

A問題

atcoder.jp

考察

  • 問題文通りに解けば良い

実装

A, B = map(int, input().split())
if A > 0 and B == 0:
    print("Gold")
elif A == 0 and B > 0:
    print("Silver")
elif A > 0 and B > 0:
    print("Alloy")

結果

B問題

atcoder.jp

考察

  • 4桁が同じ数字は、inputのstrをcountすれば良さそう

    • あまりよろしくなく、O(n) で重い処理だが、 n=4 なので問題ないと判断
  • 次の数字の処理だけ、少しだけ注意

    • 基本、差をとって1になるかを考えれば良い
    • 9が来た時だけ、次の数が0になってないか判定する
  • なぜか、 コンテスト中血迷った のか、絶対値で考えて、 WA を出してしまったw

    • これだと 0101Weak になってしまう・・・
for i in range(len(X)-1):
    x1, x2 = int(X[i]), int(X[i+1])
    if abs(x1 - x2) == 1 or abs(x1-x2) == 9:
        cnt += 1

実装

X = list(input())

flag = True

if X.count(X[0]) == 4:
    flag = False
else:
    cnt = 0
    for i in range(len(X)-1):
        x1, x2 = int(X[i]), int(X[i+1])
        if x2 - x1 == 1 or (x1 == 9 and x2 == 0):
            cnt += 1
    if cnt == 3:
        flag = False

if flag:
    print("Strong")
else:
    print("Weak")

結果

C問題

atcoder.jp

考察

  • max(N, M) = 2*105 なので、 O(n2) だと TLE になるため、愚直な全探索は不可

    • なるべく、 O(n) に近くでやりたく、ループは1回に抑えたい
  • 「2つの値の差の最小値 」を考えるので、A, Bのどちらかの数列に着目し、残りをsortして、2分探索し、近しい数値で計算すれば良さそう

    • この場合、 O(nlogn) になるので、なんとかなりそう
  • bisect_left を使うが、いくつかポイントがありそう

    • 基本的に、2つの数値の間に入るので、その場合はどちらも利用し、計算する必要がありそう
    • 探索した値が、一番小さい、一番大きい場合は、1つの数値を利用すれば良い
      • 探索対象の数列内で一番大きくなる場合、 out of index になるため、 idx -1 が必要になる
  • コンテスト中に、問題文を読み間違え、 ansの値を小さくしWA をしてしまい焦った

    • アプローチが間違ってると思い、多くの時間を使ってしまった・・・

実装

from bisect import bisect_left

N, M = map(int, input().split())
A, B = list(map(int, input().split())), list(map(int, input().split()))

B.sort()

ans = pow(10, 10)

for i in range(N):
    a = A[i]
    idx = bisect_left(B, a)
    if idx == 0:
        b = B[idx]
        ans = min(ans, abs(a-b))
    elif idx == M:
        b = B[idx-1]
        ans = min(ans, abs(a-b))
    else:
        b1, b2 = B[idx-1], B[idx]
        ans = min(ans, abs(a-b1), abs(a-b2))

print(ans)

結果

D問題

優先度付きqueueを知らない and query 2 の扱いを誤認しており解けず・・・

atcoder.jp

考察

  • max(Q)=2*105 のため、処理を愚直に記述した際は確実に TLE するので、効率的に計算する方法を考える

  • 操作 1 普通に数値を、追加するが、 操作3 で取り出すことを考えると sort して挿入すると嬉しそう

    • 既存のlistを2分探索し、isertすればいいと思ったが、pythonのlist(linked list)のinsertはO(n)のためすごく遅くなりそう・・・
    • コンテスト中は知らなかったが、 heapq.heappush というものがあり、sortを加味しながら O(logn) で処理できるものがある

qiita.com

  • 操作 2 は都度、全ての袋の中の数を更新してると、計算量的に無理だと思い、別変数でcountし、 操作3 で取り出す際に足せばいいと考えた
    • ここで、考慮に漏れてたのが、操作2はその時に袋の中にある値のみを更新し、操作2後に入った値は更新されないという点
    • そのため、累積和を用いて考える必要がある、取り出すときには操作2の累積値を足すが、操作1の際には、その時点でのcount値を引いて、格納する必要がある
      • この際の操作1で加わる値は、過去の操作2の影響を受けてないため、すでにある値より小さくなる

qiita.com

  • 操作3 は最小値を取り出すが、その時点の最小値であるため、事前に値を全て格納し、sortして処理することは不可
    • 今回の例だとそれでも通ってしまうので、勘違いしてしまう場合もありそう
    • heapq.heappop が非常に有効な働きをする(pythonのpop(n)はO(n)になってしまうので・・・)

実装

from heapq import heapify, heappop, heappush

Q = int(input())

bag, ans = [], []
cnt = 0
heapify(bag)

for _ in range(Q):
    query = list(map(int, input().split()))
    if query[0] == 1:
        heappush(bag, query[1]-cnt)
    elif query[0] == 2:
        cnt += query[1]
    else:
        ans.append(heappop(bag)+cnt)

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

結果

E問題

全然取り組めず解説見ながら解いた

atcoder.jp

考察

  • パッと見た感じ、経路問題なので、 dfsダイクストラ法 が頭に浮かぶが、ちょっと毛色が違う
  • 通れる経路でなく、通れない経路が与えられる

  • なんとなく、動的計画法ぽい感じで、 (すべての経路でいける場合) - (いけない経路の場合) で考えれば良さそう

    • 基本すべての街に行く経路はあるので、そこの計算は複雑ではなさそう
  • dp[i][j] で考え、 i日目において、 j番目の街に行く場合の数を考えていけば良さそう

    • 基本的に、すべての街の経路があるので、 dp[i][j]=sum(dp[i-1]) - dp[i-1][j] で考えれば良さそう
      • 自己回帰の経路はないため、自分自身に戻る場合を除いている
    • 使えない経路があるため、その場合を除く必要がある
      • dp[i][j] に対して、 経路のない街k の d[i-1][k] を除く必要がある

実装

modをとることに注意して計算する

N, M, K = map(int, input().split())

graph = [[] for _ in range(N)]
dp = [[0] * N for _ in range(K+1)]
mod = 998244353

for _ in range(M):
    u, v = map(int, input().split())
    graph[u-1].append(v-1)
    graph[v-1].append(u-1)

dp[0][0] = 1

for i in range(1, K+1):
    s = sum(dp[i-1])
    for j in range(N):
        cnt = 0
        for k in graph[j]:
            cnt = (cnt + dp[i-1][k]) % mod
        dp[i][j] = (s - dp[i-1][j] - cnt) % mod

print(dp[K][0])

結果

まとめ

  • 優先度付きqueueは利用したことなかったので、しっかり覚えたい(内部実装も含め)

ja.wikipedia.org

  • D問題は茶色diffだったが、解けなかった・・・が、8問体制になりD問題が易化する期待が持てる

    • 茶色コーダにとっては嬉しい
  • 水色以下の問題は、今後も復習し、解けるようにしていく

    • 定型90問も解き続けているので、合わせて続けていく
    • ABCのC問題までの早解きも続けていく

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

目的

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

A問題

atcoder.jp

考察

  • 問題文通りに解けば良い
  • 割り算するので、誤差が気になる気もしたが大丈夫だった

実装

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

print(A*B/100)

結果

B問題

atcoder.jp

考察

  • 並び替えによって作れれば良いので、要素があるかを確認すれば良い
    • 与えられたAをsortし、Nまでの要素が全て揃っているかを確認すれば良い

実装

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

flag = True
A.sort()
for i in range(N):
    if i+1 == A[i]:
        continue
    flag = False
    break

if flag:
    print("Yes")
else:
    print("No")

結果

C問題

atcoder.jp

考察

  • 指数の性質を利用し、場合分けをする
  • Cが偶数の場合はA, Bの絶対値の比較になる(偶数乗すると正になるため)
  • Cが奇数の場合は、単純にA, Bの大丈比較で良い

実装

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

if C % 2 == 0:
    if abs(A) == abs(B):
        print("=")
    elif abs(A) > abs(B):
        print(">")
    else:
        print("<")
else:
    if A == B:
        print("=")
    elif A > B:
        print(">")
    else:
        print("<")

結果

D問題

初めてのD問題解けた!!

atcoder.jp

考察

  • max(K)=1018 のため、rangeで巨大な数列を作り、Aを除外するとTLEになるため別の方法を考える
  • N=105 のため、この範囲であればloopが回せそう
  • それぞれのKに対して、Aの要素を加味しながら何番目かを出すのが良さそう
    • kがAのうちでどこに入るのかを、2分探索で求める
      • Aも大きな数列なので、線形探索でO(n)だと間に合わない可能性があるため、二分探索で求める
    • もし、Aのうちでkが一番小さいようなら、そのまま出力する
    • もし、kがAの要素よりも大きいなら、Aの要素を除いて順番を出す必要があるので、再帰を用いて順次求めるようにする

実装

import sys
from bisect import bisect_right

sys.setrecursionlimit(pow(10, 9))

N, Q = map(int, input().split())
A = list(map(int, input().split()))

def solve(k, idx1):
    idx2 = bisect_right(A, k)
    if idx1 < idx2:
        solve(k+(idx2-idx1), idx2)
    else:
        print(k)


for _ in range(Q):
    k = int(input())
    solve(k, 0)

結果

まとめ

  • D問題が初めて解けて、自己最高のratingを叩き出せた!嬉しい