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

令和ABC(?)E問題を全部解いた。解いた順番は適当だがコメントは開催順になっている。 Eレベルはセグ木・グラフアルゴリズム・文字列アルゴリズムなど知識を求められるものが多い印象。蟻本などは未履修なので辛かった。勉強してライブラリを作っていきたい。 コードは適当に探せば(id:nehan_der_thal)、見つかると思うのでpython勢の参考になれば。

ABC126 1 or 2

Xi Yi Zi が与えられるがZは関係なくてXiとYiに辺を貼って連結成分の数を数えるだけでいい。E問題は簡単方針なのかと思っていたら次回以降難易度が上がった。 UnionFindを使うと楽だけど使わなくてもいいようだ。使わないバージョンはTODO

ABC127 Cell Distance

任意の２つのセルについて|xi-xj|の平均値はm/3になる。（ここの計算は面倒だったが愚直にやったら出た。面倒じゃなく導出できそう。nによらないのが非直感的だった。） 全体の場合の数とかければいい。 C(n*m,k)*C(k,2)*(n+m)/3

ABC128 Roadwork

解法は素直。信じられないほど解くのに時間がかかった。TLE地獄。 セグ木で集合minを管理したが、もっと適当なアルゴリズムがありそう。（追記 : pythonの標準ライブラリである heapqを使えば最大・最小を取り出すことができました。どちらにせよTLEしがちなので実装に注意） 木関連はどこかで整理しないと。 sort時にkeyを設定しないとTLEした。忘れがちなこととしてメモ。

import sys
input = sys.stdin.readline
n,Q=map(int,input().split())
b_num = 2**(n-1).bit_length()
mx = 10**9
segl=[mx]*2*b_num 
def update(k, x):
    k += b_num-1
    segl[k] = x
    while k+1:
        k = (k-1)//2
        segl[k] = min(segl[k*2+1],segl[k*2+2])
if __name__ == '__main__':
    xs = []
    for i in range(n):
        s,t,x=map(int,input().split())
        xs += [(s-x,True,x,i), (t-x,False,x,i)]
    qs = []
    for _ in range(Q):
        qs.append(int(input()))
    xs.sort(key=lambda x:x[0])
    j = 0
    for x in xs:
        while Q-j and qs[j] < x[0]:
            print(segl[0] if segl[0]!= mx else -1)
            j += 1
        update(x[3], x[2] if x[1] else mx)
    while Q-j:
        print(-1)
        j+=1

ABC129 Sum Equals Xor

a xor b == a+bとなるのは各ビットがともに1にならないとき、普通のdpで計算できる。更新式

r, l = 3*r % mod, (r+2*l) % mod if int(c) else l

rはある桁までのa,bの各ビットを(1,0)(0,0)(0,1)のいずれかにした時の場合の数 lはrのうちLのある桁までの数字以下となるようなa+bの場合の数。 ある桁が1のときはli=r{i-1}+2*l{i-1}となる。該当桁が(1,0)(0,1)の時はi-1桁以下はl_{i-1}に依存、(0,0)の時はr_{i-1}に依存を表している。

ABC130 Common Subsequence

入力数列s, tに対してd[i][j]をs[1...i], t[1...j]を用いてできる部分列の数とする。 s[i]!=t[i]の時はd[i+1][j+1]=d[i][j+1] + d[i+1][j] - d[i][j] s[i]=t[i]の時はこれにd[i][j]を加える。（∵s[1..i]とt[1...j]を用いてできる部分列に最後の数をくっつけたものも部分列となる） 解説ではさらに+1が必要になっているがこれは空集合を考慮するかどうかで、初期化の際に空集合を考えてd[0][:],d[:][0]を1としたので私の実装ではつけなかった。 更新式は以下のように小さく書ける。

d[i+1][j+1] = d[i][j+1] + d[i+1][j] - (s[i] != t[j])*d[i][j]

ABC131 Friendship

二点間の最短距離が2になるペアの数がKであるグラフを構築する問題 スターグラフの二点を繋いでいけば、1ずつペア数は減っていく。 簡単だったが、なぜか繋ぐともっと減るとしばらく勘違いしていて時間がかかった。

ABC132 Hopscotch Addict

けんけんぱでグラフを移動する。というのは一度に距離3離れたノードに移動する。 グラフ上のゴールまで最短で行く方法を求める問題。 簡単そうで解けなかった。解説AC。以下のようにN*3のグラフを作ればいい。なるほどと感じたが割と典型らしい？

d = [set() for _ in range(3*N+1)]
for _ in range(M):
    a, b = [int(x) for x in input().split()]
    d[a].add(N+b)
    d[N+a].add(2*N+b)
    d[2*N+a].add(b)

ABC133 Virus Tree 2

木の距離2以下のノード対が別色になるようなK色塗り分けの場合の数 親から塗る。各ノードの子供達を親と祖父以外の色で塗ればいい。子供の数をmとすると(K-2)P(m)、Pは順列、根の子供は祖父がいないので(K-1)P(m）。 DFSしながら塗ればACできるが、上式を見ると子供の数だけが必要なので探索しなくても各頂点の次数viに対してSum{(K-2)P(vi-1)}*(K-1)*Kを計算するだけで答えが出る。

ABC134 Sequence Decomposing

広義最長減少列を見つける問題に落ちる。広義最長減少列に落ちることに気づくのは自明と感じなかった。要復習。解説にはDilworthの定理なども書いていて勉強になる。 最長減少列はセグ木を使って求めたが素直な方法も勉強しておきたい。セグ木を使った方法抜粋

n = int(input())
xs = [int(input()) for _ in range(n)]
d = {}
for i, x in enumerate(sorted(xs)):
    d[x] = i
segtree = SegTree([0]*n, max)
r = 0
for x in xs:
    xi = d[x]
    y = segtree.query(xi, n)
    segtree.update(xi, y+1)
    r = max(r, y+1)
print(r)

ABC135 Golf

DifficultyがE最高だったが、意外と簡単？ 実装が大変だからかな。当然本番は解けず。 要復習

ABC136 Max GCD

難しかった。後で書く

ABC137 Coins Respawn

Bellman-Ford法。解説AC。 拾ってきた関数を使った。閉路に対応していないので少し改変しないとならなかった。

Submission #8913809 - AtCoder Beginner Contest 137

scipyにも関数があるらしい。こちらを使ってACは今後の課題。

ABC138 Strings of Impurity

結構簡単だった。二分探索でtの各文字がsのどこにあるかを計算していくだけ。

ABC139 League

単なる貪欲だが実装に苦労してる内にAC、解説ではグラフがどうだとか書いているので解説解法ACがTODO

Submission #7287116 - AtCoder Beginner Contest 139

ABC140 Second Sum

要追記。一番大きいのを集合から取ってきたい。当時方法を知らなかったが、segmen treeなどで簡単。 令和ABCでは「知っていればすぐ」な問題が割と出ている。

ABC141 Who Says a Pun

解説AC、ググったらいろんな解法が出てくる。 文字列検索アルゴリズムをどれか知っていたら簡単っぽい。 要ライブラリ化。知らなくても数行で解けるけど。

ABC142 Get Everything

宝箱の数n<12という制約が与えられる。nが少ないときは全探索を疑うのがセオリーらしいがこれもセオリー通り。自力AC。 更新式：dp[i|d] = min(dp[i|d], dp[i] + a) は単純。これを解いたのちにbitset高速化を知ったがこれもそう？

ABC143 Travel by Car

ワーシャルフロイド法が何をするものかは知っていたが、具体的な方法を知らなかったので調べてAC。 以下コード

#ds[i][j] はiからjの距離。隣接ノードi,jの重みで初期化。
for k in range(1, N+1):
    for i in range(1, N+1):
        for j in range(i+1, N+1):
            ds[i][j] = min(
                    ds[i][j],
                    ds[min(i, k)][max(i, k)] + ds[min(k, j)][max(k, j)]
                    )
            if ds[i][j] <= L:
                bs[i][j] = 1

でもライブラリがあるらしい。こちらを使ったACはTODO

参考 : scipyのFloyd-WarshallとDijkstraのすすめ　Python 競技プログラミング

ABC144

覚えてないけど難しかった。要復習。

ABC145

自力AC、無限に時間がかかった。ナップサックぽいので実装して最後の１つを調整しないといけない。なぜかWA、いろいろ変えたらAC。何が何だかわからないままになっているので要復習

ABC146

mod式変形で謎詰まり後、解説AC。これくらいは自力ACしたかった気がする。mod式変形に慣れる必要がある。

ABC147

N<80の盤制約、A<80の値制約だが、どう見ても2*804~=108以上かかりそうで諦めた。bitset高速化を知る。解れば簡単に感じる。実装も楽。 ただし、bitsetでマイナスを取り扱えないので実装に工夫が必要。他の人のコードが参考になる。

ABC148 Double Factorial

とても簡単だった。5, 52, 53, で割れる数を数えればok。証明も簡単。

ABC149 HandShake

解説AC、一目簡単そうだったが難しかった。 二分探索時に単調減少の関数を取り扱うと求まるidxはどこなのか頭がバグりがちなのでもう少し慣れが必要と感じた。また、X以上の幸福度を得る方法の場合の数を求めるときに左手を固定して、右手で握手できる人を数えるところは累積和で解けるらしいがC以上のパワーを持つ人数をあらかじめ数えておくことで実装してしまった。max(A)が大きいときこれでは対応できないので想定解法の復習が必要。FFT解法も解説pdfにあったのでこちらも要復習

類題らしい : C - 億マス計算