AtCoder 令和ABC(?)D問題をpython, pypyで全部解いたのでコメントを残す。

令和ABC(?)D問題を全部解いた。解いた順番は適当だがコメントは開催順になっている。 Dレベルだと解法がわかるのに5分以上かかったのはあまりなかった気がする。例外処理・実装が主な詰まりポイント。実装で苦手なのは二分探索や尺取り法や優先度つきキューなど。解法一瞬から60分くらい実装にかかることも普通にあるのでレートが上がらないのも最もだと実感する。コードは適当に探せば(id:nehan_der_thal)、見つかると思うのでpython勢の参考になれば。レートも上で実装も綺麗な人たくさんいるので参考にならなさそう。

ABC126-D Even Relation

木構造の探索は再帰は遅い。pypyではTLE, pythonではAC。非再帰に落とすのは今回は楽だけど、思い違いがあったときに再帰の方が改変が楽なので捨てがたい。機械的に再帰を非再帰に直せる方法を確立したい。また辺情報の持たせ方は以下が自然。以前はd[tuple(sorted([u,v]))]=pとかやってた。まあそんなに変わらないか。

d = [set() for _ in range(N+1)]
for _ in range(N-1):
    u, v, p = map(int, input().split())
    d[u].add((v, p))
    d[v].add((u, p))

ABC127-D Integers

Asの数字が1つずつ、BがCずつあると考えて、As, Bsの和集合の大きいものを貪欲に足していけばいい。簡単だったけど脳死で解くには至らない。（Fastest ACは3分台）

N, M = map(int, input().split())
A = list(map(int, input().split()))
X = []
for _ in range(M):
    b, c = map(int, input().split())
    X.append((b, c))
X = sorted(X, key=lambda x: -x[1])
Y = []
for i in range(M):
    ly = len(Y)
    b, c = X[i]
    if ly + b < N:
        Y += [c] * b
    else:
        Y += [c] * (N-ly)
Z=A+Y 
print(sum(sorted(Z)[-N:]))

ABC128-D equeue

左と右からいいものを取ってマイナスを捨てる。添字などで混乱して実装に苦戦したので復習したい。

ABC129-D Lamp

TLEにて苦戦。O(N)のはずなのに、だめ。列ごとの処理を以下のように二重ループを使うとダメだった。

H, W = map(int, input().split())
d = []
d2 = []
d3 = []
for h in range(H):
    s = input().strip() + "#"
    d.append(s)
    d2.append(sc(s))

for i in range(W):
    s = ""
    for j in range(H):
        s += d[j][i]
    s += "#"
    d3.append(sc(s))

結局、l = list(zip(*l))のように転置してAC。(1793ms) 大人しくnumpyを使う方がいいのかもしれない。

ABC130-D Enough Array

二部探索と尺取り法どちらでも解けるがコードを比較してどちらが良いか比較。二部探索が慣れれば早い気がする。

N, K = map(int, input().split())
As = [0] + list(map(int, input().split()))
from itertools import accumulate
As = list(accumulate(As))
M = len(As)
j = 0
r = 0
for i in range(M):
    a = As[i]
    while True:
        if j == M:
            break
        if a + K <= As[j]:
            break
        j += 1
    r += M - j
print(r)

N, K = map(int, input().split())
As = [0] + list(map(int, input().split()))
from itertools import accumulate

def bsearch(target, min_i, max_i, func):
    # func(index) <= target < func(index+1) となるindexを返す
    if func(max_i) < target:
        return max_i
    if target <= func(min_i):
        return None
    index = (max_i + min_i)//2
    while True:
        if func(index) < target:
            if target <= func(index+1):
                return index
            index, min_i = (index+1 + max_i)//2, index+1
            continue
        index, max_i = (index-1 + min_i)//2, index-1

As = list(accumulate(As))
r = 0
for a in As:
    idx = bsearch(a+K,0,len(As)-1,lambda x:As[x])
    r += len(As) - (idx+1)
print(r)

ABC131-D Megalomania

ソートするだけ。流石に簡単。

ABC132-D Blue and Red Balls

簡単だが脳死では解けなかった。青と赤を交互に並べて2*i-1の列を作って残りの青赤球を同じ色のところにくっつける場合の数。式で書いてもH(K-i, i)*H(N-K-i+1, i+1)だけ。

ABC133-D Rain Flows into Dams

簡単と思う。a1-a2+a3..-x1 =x1からx1を計算。そのあと、x1から順にxn=a{n-1}*2-x{n-1}を計算。

ABC134-D Even Relation

大きい方から決めるだけでいい。sum(1/i)がlogN程度になることがポイント？

ABC135-D Digits Parade

以前なら苦労していた気がするがさらっとかけた...と見せかけてTLE地獄にはまった。10**i%13の計算(i<=10**5)をしていたことに気付いてなかった。 10ずつかけながら10**i%13を計算していく方法に変更してAC。解法がO(10**7)なのでコーディングの問題でのTLEかも？と思ってしまったのがハマった原因。指数のところでミスるのは前もあったので注意したい。課題は注意力。

ABC136-D Gathering Children

連続する文字の数を数える部分を簡単に書きたい。いつもは適当に書く、以下みたいに。基準を決めてしまいたい。

S = input().strip()
b = "R"
r = 1
xs = []
for c in S[1:]:
    if c == b:
        r += 1
    else:
        xs.append(r)
        r = 1
    b = c
xs.append(r)

ABC137-D Summer Vacation

過去、WAになって放置していた記録が残っていたが割とすんなりACできた。このようなことは増えてきている気がするがレートは横ばいである。 heapqを使う頻度は少ないので毎度ググっている。heapqには複数同じ要素が入れられることも毎度確認しているが入れられる。

from heapq import heappush, heappop
h = []
heappush(h, 5)
heappush(h, 2)
heappush(h, 7)
heappush(h, 5)
rs = []
for _ in range(3):
    rs.append(heappop(h))
print(*rs)
# Output : 2 5 5

ABC138-D Ki

親から順にカウンターの値を足しながら探索すればいい。簡単だが当時（これは結構前に解いたのを思い出して書いている）20分以上かかった記録がある。今なら早く解けるだろうか。10分くらいで実装まで終えていたい。

ABC139-D ModSum

素直に実装しても2行で終わってしまう。サンプルからも予測できる解答だが証明も容易。

x=int(input())
print(x*(x-1)//2)

ABC140-D Face Produces Unhappiness

ある範囲の人を反転させて、同じ方向を向いている人を多くする。同時に増やせる同じ方向を向いている人の数は最大2人(範囲の境界の人だけ)。ほとんどの時2人増やせる、1人しか増やせないのはLLLLRRRRRみたいな形の時だけ。簡単だった覚えがあるけど20分くらいかかっている。なんで？

ABC141-D Powerful Discount Tickets

実装に苦しむ。a_iを計K回//2してから総和を最小化する。貪欲に一番大きいやつを//2すれば良さそうだが優先度つきキューに慣れていないので、あらかじめどれに何度//2すれば良いか計算した。優先度つきキューが解説解法なのでこちらでもACしておきたい。

ABC142-D Disjoint Set of Common Divisors

最大公約数を素因数分解して素数の数を数える。素因数分解関数をコピペしたら2行。要ライブラリ追加。

ABC143-D Triangles

Difficultyが低いわりに実装に詰まる。二部探索とか尺取り法とかで苦戦しがちな気がする。１つの配列に対してi, jと２つの添え字を同時に考えるときに混乱している。 1つは二部探索の自分の実装法がダメで混乱しがちなことが原因。もう１つは単に慣れ。要復習。

ABC144-D Water Bottles

math.atanを使う。0徐算で1RE。場合分けもある。実装は実質2行程度だし、簡単だが紙がないと解けない。

ABC145-D Knight

私にしてはかなり早くACしていた形跡がある(7分くらい) (i,j)から(i+1,j+2)か(i+2,j+1)に移動を繰り返す。x+yは3ずつ増えるのでx+y%3==0でないとだめ。移動回数cは(x+y)//3になるし、x=x-c, y=y-cと置きかえれば、i+=1, j+=1を繰り返して、(0,0)から(x,y)に移動する問題になる。答えはC(x+y, c)

ABC146-D Coloring Edges on Tree

色が辺なのか頂点なのか読み違えた。木について早く... 各ノードについて、親から出ている辺以外の色で子から孫に伸びる辺の色を適当に決めればいい。10分以内で解きたい。

ABC147-D Xor Sum 4

XORに苦手意識があったが解いてみると簡単だった。紙が必要だけど。XORに慣れ親めば紙なしで解けるだろうか。

ABC148-D Brick Creek

左から1.2.3と数えるだけ。あまりにも簡単なので読み違いがないか確認した。

ABC149-D Prediction and Restriction

貪欲に解いて簡単に解けた。 K回前に出した手は出せないじゃんけんだが、K回前に出した手を出したいときは諦めて違う手を出すだけでいい。 twitterなどで強い人たちをみると何も考えずにdpしたらしい。何も考えずにdpが書けないので仕方がないが、要dp練習。

少ない学びをせめて記録する

技術記録、競プロメモ、その他調べたことを書く @京都, twitter : @nehan_der_thal