ABCコンテストの過去問を埋めました（上の画像は AtCoder Problems 様 のもの）。
第126回以降は、参加者として埋めたため、別に感想記事があります。そちらを参照してください。
全問題にコメントすることはしませんが、難しかった問題や、上手くコードが書けたものなどについて少しずつ言及したいと思います。
C問題
ABC 018-C 菱形カウント
別記事で取り上げました。類題がAGC-Aにあり、こちらは実行制限が甘い版という感じです。同時にPython+PyPyでの最短実行時間になりました。
ABC 020-C 壁抜け
C問題最上位のひとつ？距離の計算は、グラフを作ってscipyに投げる方針での実装です。
マス目をグラフ化するのが下手かも。何かライブラリにあったりしないのかな
ABC 021-C 正直者の高橋くん
グラフ上を頂点 $A$ から頂点 $B$ に $n$ 回で移動する方法は、接続行列の $n$ 乗として計算することができる。というのが思い浮かんだのでそう解いた。計算量的には無駄をしています。
ABC 023-C 収集王
分布集計をさらに集計する。別記事で解説した、np.bincountにより綺麗に実装できた。
ABC 027-C 倍々ゲーム
考察がC問題では最上位付近に感じました。
こういうのは基本的には、ゲーム終了間際から決めていくのがセオリー。
[left, right] 上で win / lose になるという情報を、$N$ に近い側から計算していった。
解説PDFを見たけど、自分の解法の方が素直で易しい発想だと思う。
ABC 072-C Together
難しい問題ではないですが、別記事にしたやつです。
ABC 077-C Snuke Festival
pythonで連続的な二分探索を行う場合、np.searchsortedを使うと簡潔かつ高速に計算できます。Python+PyPyでの実行時間最短を実現しています。近日、パフォーマンスや計算量も含めて、別記事にしたいと思います。
ABC 091-C 2D Plane 2N Points
簡単な解法もあるのですが、すぐに思いついた解法
・二部グラフの最大マッチング問題 → 最大フローで解く
という方法で。最大フローの実装はほとんど経験がないので、良い練習に。残余グラフで始点から終点までの「パスを1つ見つける」ところは、scipyからdijkstraを呼んで最短路をとってきました。どちらも最悪計算量では、全ての辺を1度ずつ見ることになると思うので、大きな損はしていないと思いますが、もう少し適した方法があるのではないかとも思います。課題。
なお、pythonで最大フロー問題を解く場合、networkx を使うという方法も標準的な方法のひとつに思われます。これはAtCoder環境下では利用できません。
問題D
ABC 010-D 浮気予防
多分初めて、最大流問題を実装しました。いかにも最小カットという問題文ですね。
フローは競プロでも強力だと聞いたことがありますが、ABCコンテスト過去問の範囲では、フローが学べたのは、上述の[ABC 091-C]と本問題の2問だけだったのがやや残念でした。
ABC 012-D バスと避けられない運命
グラフの任意頂点間の距離を計算する問題。scipy.sparse.floyd_warshall を利用できます。Python + PyPyで最短実行時間を実現しています。昔のコンテストのC, D問題にはグラフ最短路メソッドを呼ぶ練習ができる問題が多いです。
ABC 014-D 閉路
考察も実装も重めでかなり悩んだ。全距離を持とうとすると無理なので、2べきだけメモ。
LCAという有名アルゴリズムらしい。初見だった気がするけれど、アリ本に載っていたので私の勉強の精度が低いだけだった。
ABC 025-D 25個の整数
実装重め。Pythonだと実行制限時間がつらめ。PyPyで通したあと、Pythonでもこちょこちょ簡単な最適化をやってたらACにはなった。2019/06/22現在で、Pythonで唯一のACになっています → ■ 。
ABC 032-D ナップサック問題
1つ1つがC～Dという感じのものを3問一気に実装しないといけないので、難易度高めだと思います。いざ実装してみると2, 3個目は易しい。numpyでさっと書ける。Python + PyPyで最短実行時間を実現しています。ここのnumpyの用法自体は、コードも短く極めて基本的で分かりやすいと思いますので、興味のある人は確認してみてください。
ABC 033-D 三角形の分類
考察もDにしては重め？実装も、はじめは下手な尺取法を書いて、PythonでTLEをしていました。
np.searchsortedを利用することで、簡潔かつ速いコードになりました。PythonでのACが3人しか居ない問題ですが、実行制限時間に余裕を持って間に合っています。
ABC 037-D 経路
実行時間制限が厳し目の問題です。PyPyで通しました。
ABC過去問では、2019/06/22時点で、PythonでのAC者が存在しない唯一の問題です。
（Pythonから他言語を実行するという方法でのAC者は存在するようです。）
ABC 065-D 連結 / Connectivity
グラフの連結性は、scipy.sparse.csgraph.connected_components で計算できます。
グラフの接続行列は、疎行列になるので、csr_matrix として作りましょう。
Python + PyPyで最短実行時間を実現しています。
ABC 091-D Two Sequences
考察部分も結構難しいと思います。あるbitより下だけ見て、和が適切な範囲になる組み合わせを抽出。例によってnp.searchsortedで高速化して、Python + PyPyでの最短実行時間を実現。
ABC 099-D Snuke Numbers
解説PDFも割とわかりにくい気もする。考察で絞る。微妙な計算ミスが怖いので多めに生成。
計算式が苦手な人は、小さい方を全探索してみると良さそう。厳密に規則が追えなくても十分に探索空間を小さくできる必要条件を見つけるだけでよい。
ABC 107-D Median of Medians
ABCコンテスト過去問の中で、個人的には最難だと思いました。
解説PDFでは、問題を何度も言い換えた挙句、最後は「転倒数なので、典型」で締められています。問題を書き換えるところも、他の手段もありそうなところでやや非自明。そして「転倒数なので、典型」ですらABCコンテスト過去問の最強クラスだと思います。転倒数のアルゴリズムはBITやマージソートが代表的のようですが、どちらもABCコンテストでは、実装する機会が一度もありません。
本問題の場合は転倒数といっても、$|a_{n+1} – a_n| = 1$を満たす数列のそれです。その特性を利用すると、転倒数を求める部分を $O(n\log n)$ から $O(n)$ にできますし、必要な予備知識も下がりそうです。実行制限時間も厳し目で、Pythonではここの$\log n$ 倍まで削減しないとTLEになりやすいかもしれません。
