順次追記: 競技プログラミングの知識(考察) - 文学徒が競プロをするブログ

Q. これはなに？

考察で要求された知識や考え方を雑多に書くだけのメモ帳、考察とかアドホックな考え方についてです。
僕は論理的、数学的な正しさを考えるのが苦手なので、体系化していきたい。
ちなみに僕が知ってることは省くので、網羅的ではないです。ゆるして。

式変形（数学）

まあ僕が人並みにでも式変形が出来たら、今頃阪大にいないんだよね。京大挑戦してたと思う。行けたかは知らないけど。

数列とかの数え上げで、ある1つの要素がそれぞれ何回足されるかを数えるやつ

ABC127-E Cell Distance

まずΣが入った計算式を理解するのにINF時間かかるんだけど、なに？
とりあえず問題概要は、

N行 M列のマス目があり、上からi行目、左からj列目のマスを (i, j)で表し、このうち Kマスに駒を1つずつ置く。
K個の駒がそれぞれ (x1, y1),(x2, y2), ... , (xK, yK)に置かれているとき、この配置のコストは

$\sum_{i=1}^{K-1} \sum_{j=i+1}^K (|x_i - x_j| + |y_i - y_j|)$

っていう式で表されるので、全てのKの配置について( $1 \leq K \leq N$ )の総和を求めたいと。

XとYについての処理はとりあえず分離しても良さそうなので、分離して考えましょう。
そして $\sum_{i=1}^{K-1} \sum_{j=i+1}^K$ が何を表しているかというと、全てのありうるペアの組み合わせなんですね。まず僕は初見でこれが見えませんでした、ダメすぎるだろ。

そうするとこの考え方そのままで、各ペアのマンハッタン距離がそれぞれ何回足されるかを考えればいいだけです。

ABC140-E Second Sum

なんかAGCで見た覚えがありますねえ！
まあホント考え方としてはド典型で、数列の各要素がそれぞれ何回足されるかを考えればいいんですね。

ABC151-E Max-Min Sums

ある要素 $A_i$ について、それがMaxとして何回足されるか、Minとして何回引かれるかをそれぞれ数えて、最後に合算する。

引き算の絶対値の総和の最小化といえば中央値だよねのやつ

ABC127-F Absolute Minima

「引き算の絶対値の総和の最小化」、日本語の理解力が問われるね。

問題概要は
何かクエリ毎に $|X - A_i|$ みたいなのが式に追加されて、 $|X - A| + |X - B| + |X - C| + |X - D| + |X - E| + |X - F| ...$ みたいになっていくから、その最小値をクエリ毎に答えてねという問題。

本質パートは中央値を高速に求めるところ。

ある数列の全ての要素がある数Xの倍数 = その数列の総和もXの倍数

ABC136-E Max GCD

これ難しくない？典型二段重ねって感じ。
一段階目の考察から出来なかったのでとりあえず書く。
「最大の公約数を求めろ = 全ての要素を出来るだけ大きいある数の倍数にしろ」なので、上記の通り総和もある数の倍数になる。
ここで、数列の要素は+-1されるために結局総和が変わらないことに気づくと、総和の約数を全部試せば良いということになる。

ただ約数を決め打った後に可能かどうかをシミュレーションするにもひと工夫必要で、これも思いつかなかった。要復習。

貪欲

ABC134-E Sequence Decomposing

これ毎回戸惑っちゃうんだよね、考え方で分類するとしたら貪欲かなあ......。
何か「ある数列を複数のLISに分割した時の最小個数を求めるには、multisetで管理してえい！w」程度に捉えています（LDSの数とするのでも良いんだろうね）。ある種知識ゲーというか小手先のテクと言えるかも。

グラフ

ABC131-F Must Be Rectangular!

これグラフに見える？連結成分は一瞬考えたけどわかんないになった。算数的に良い性質があるのかと考えたけど、わからず......。
けんちょんさんによると、座標を二部グラフとして管理する考え方は頻出らしい。ほえー。
てかちゃんと実験すると、最終的にはx座標とy座標どちらかを共有した点による大きな長方形が出来て、その格子点が答えであることが分かるんですね。

これグラフに分類して考えるより、「求めたいものがある条件下で規則的な性質を持つことを発見し、それを数える考え方」とした方が良さそう。
地頭！（素振り）

さて、けんちょんさんより引用すると、

この手の「グリッド上のマス」だとか「二次元平面状の座標」だとかを二部グラフで表現するのは常套手段の一つではある。
左側：登場する x 座標を並べたもの
右側：登場する y 座標を並べたもの
辺：座標 (x, y) な点があるとき、左の x と右の y とを結ぶ辺に対応させる
というグラフ。こういうグラフを考える問題は本当によくある。

だそうである。確かにこの問題的に、x座標とy座標をわけて管理するのは筋が良さそう。
で、たくさん考えると、
連結成分ごとの完全二部グラフの形 = 大きな長方形が作る格子点の数

ということがわかり、解ける。

Coins Respawn

Bellman Ford貼るだけ......かと思いきや数多の猛者たちも実は嘘で通していたことで一時期話題になった問題。
確かEのFAから6人までが実は全員嘘だったとかそんなのだったはず。実質FAがbeetさんで、おイキりになられていたのを覚えてる。

まあ正しいBellman Fordを整備しておけば良いんですが、実は頂点削除をすると普通のBFで通るんですよね。
1からNまでの経路に存在する頂点以外を消し去れば、閉路に行ってからゴールできるかなどの面倒事を考えずとも良いので、楽。
この処理は簡単なBFSで出来て、かなり汎用性の高い典型だなあと思いました。

CF1183E Subsequences

本質:
・シミュレーション

解けなかった理由:
・Kの小ささをうまくシミュレーションする方向に活かす発想が出来なかった

これを知っていると解ける:
・ある操作によって生まれたものに、また操作を施して変化させるときはDFSやBFSが最適

解の持つ性質を考えるやつ

これ苦手、できねえ

パナソニックコン2020 D-String Equivalence

言われたら秒で実装できる。

本番は何もわからず、

1. 何種類の文字をそれぞれいくつ使うか全て列挙
2. 組み合わせを全列挙して標準形になるものをsetに突っ込む

をした。組み合わせ全列挙に無駄が多く、N = 9以上でTLE......
数え上げだったら埋め込みで出せたんだが......

これ緑diffなのマジ？
誰か俺を殺してくれ。次はもう少しまともな脳味噌を持って生まれてくる。

小さくて簡単な方から実験すると、思いつきそう。
難しいものから考えようとすると、僕の頭では処理できない！（学び）