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

AtCoder 令和ABC(?)F問題も全部解いたのでコメントを残す。とても本番中には解けなさそうな問題が増えてきた。コメントはだいぶ手抜きだが後で拡充したい。歯が立たないということはなくじっくり考えれば解ける問題も多い。解法自体はすぐわかることもまあまああるし、実装力を鍛えれば本番中に解ける機会も増えるだろう。

ABC126 XOR Matching

はじめ解けなかったが、後で見ると簡単だった。パズル。

ABC127 Absolute Minima

セグ木、binary searchを正しく使えるか問われる。別記事にした。 whitman.hatenablog.com

ABC128 Frog Jump

気合いで解いたが時間が無限にかかった。要復習別記事にした。 whitman.hatenablog.com

ABC129 Takahashi's Basics in Education and Learning

Difficultyが非常に高い。解いてみると意外と簡単に方針が立ち「あれ？」となったが等比数列の和を分数なしで求めるところで無事死亡した。modが素数でないのは初めてなので学びも多かった。また、桁数がmになるsiの個数を求める時に実装に手間取った。これくらいはテストなしで書きたい。解説コメント付きのコードでACしたので貼っておく。

Submission #9296941 - AtCoder Beginner Contest 129

行列を使って解く方法もあるらしい。TODO

ABC130 Minimal Bounding Box

解法は簡単だけど実装が大変。上手くやると実装はサボれる。自分で記事も書いていた。 whitman.hatenablog.com

ABC131 Must Be Rectangular!

三点があれば4点目を足すのを繰り返す。 Unionfindで管理、辺の数を全部数える。

ABC132 Small Products

root(N)付近で取り扱いが変わるが境界が難しい。大体の方針はすぐたつが細かいところを詰めるのに苦労する。

ABC133 Colorful Tree

別記事にて紹介予定。オイラーツアーというアルゴリズムをここで知った。 ABC-Fでは最難では？と思うくらい苦戦したが、通している人数的にもそうでもないっぽい。調べると別解があるらしい。こちらも要履修

ABC134 Permutations Oddness

解説AC。本番に思いつくとは思えない。大体O(N⁴)となるような問題は難しい気がする。

ABC135 Strings of Eternity

KMP法をペタッとすると後は簡単だったが、KMP法をググってきて使い方を調べるのに大部分の時間を使った。後はグラフの最長のノード距離を調べる。非連結なので慣れておらずここでも少しバグらせてしまった。ある頂点から最も遠いノードを探索して、そのノードから再度最も遠いノードを探索する。一般のDAGに利用できるようなコードを書いてしまったが、今回は各ノードは入次数も出次数も１なのでもっと簡単にかけた。

ABC136 Enclosed Points

ある区間の最小値を高速に見つける方法を当時知らずに諦めたが、セグ木を知ったので再戦。今度はTLE地獄にハマる。BITを覚えてAC。

ABC137 Polynomial Construction

思いつかなかった。気持ちいい解法。mod Pで(P-1)!=-1になること（ウィルソンの定理）を知った。(P-1)C(k) = (-1)**k になることも気づいた。これも定理名があるのかな。

ABC138 Coincidence

桁の数字を決めていくdp。そもそも混乱しがちな設定だが、２つの数列について考えないといけないので混乱した。このようなdpに慣れてきた実感がある。

ABC139 Engines

かなり簡単だった気がする。一番いい角度を探索するだけ。実装もとても軽い

ABC140 Many Slimes

明らかに貪欲じゃないかと思って解いたらWA。間違っていることに気づいて別の貪欲を考えAC。証明が曖昧なので後でちゃんと考える。

ABC141

はきだし法。

ABC142 Pure

実装に苦労した。問題文通りに愚直にやるだけ。ループ検出してループを小さくしていく。その後実装を簡潔化できないか見ていると最小ループを見つけるだけでいいことに気づく。 pathを保存しながらdfsでループ検出、検出時には1→4→5→2→3→5などのpathが見つかるので1→4→を消したいがこれはpathを辿りながら5を見たらその後を使うだけでいい。 bfsの方が早いかも

ABC143 Distinct Numbers

別記事にも書いたが難しい。 whitman.hatenablog.com

ABC144 Fork in the Road

解けそうで解けなかった。悔しい。 [AtCoder 参加感想] 2019/10/27:ABC 144 | maspyのHP

を見てなるほどと思う。実装はシンプル。

import sys
input = sys.stdin.readline
N, M = map(int, input().split())

g = [[] for _ in range(N+1)]
ig = [[] for _ in range(N+1)]
for _ in range(M):
    x, y = map(int, input().split())
    g[x].append(y)
    ig[y].append(x)

dp1 = [0] * (N+1)
dp2 = [0] * (N+1)
dp1[1] = 1
# dp1 : iまでの到達確率
# dp2 : iからゴールへの到達距離期待値

for i in range(1, N+1):
    for j in ig[i]:
        dp1[i] += dp1[j]/len(g[j])
df = 0
for i in range(N, 0, -1):
    t = 0
    for v in g[i]:
        t += (dp2[v]+1)
    if len(g[i]) > 0:
        dp2[i] = t/len(g[i])
    if len(g[i]) == 1:
        continue
    for v in g[i]:
        pv = (t-dp2[v]-1)/(len(g[i])-1)
        # pv : i→vへのpathを削除した時の到達距離期待値
        df = max(df, dp1[i]*(dp2[i]-pv))
        # dp1[i]*(dp2[i]-pv) : iからvを削除したときに1からvの到達距離期待値がどれだけ減るか
print(dp2[1]-df)

ABC145

考えてたら解けた。数時間かかった。どこに苦労したのかは覚えていない。丁寧にdpを組み立てればいける。

ABC146

解法は簡単だったが少し前に知ったスライド最小を使おうとしてバグり無限に時間を溶かした。部分最小の高速な方法で定番を１つ決めたい。要復習

ABC147

解説AC

X%D==0なら簡単だなあと思いながらコンテストが終わった。この考察は少し惜しくてX%Dごとに処理して後から足すと良いらしい。ただX,Dは負になる上にX==0, D==0などによるコーナーケースがあり頭を悩ませる。

ABC148-F Playing Tag On tree ? A

twitter上で強い人たちになんでこんなに解かれるかわからないと言われていた。簡単に感じたが...。ところでtreeじゃなく鬼が複数ある設定での問題も考えられるのでは？と思ったが解けそうにもないので考えるのをやめた。 whitman.hatenablog.com

ABC149-F Surrounded Nodes

簡単だった(体感10~20分で答となる式を導出できた。)。本番中にACできなかったのが悔やまれる。本番中にACできなかった理由は1つはEに時間を取られたからだが、もう１つは累乗の計算の実装がだめでTLE。2**i%mod を0<i<Nあらかじめ計算しておくことで通った。また-2の逆元も必要になった。この辺りのライブラリを整える必要がある。二分累乗法のアルゴリズムをどこかからコピペした結果のTLEなのでこちらちゃんと中身を知っておかないといけない。

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

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