数え上げ

\(\def \set #1#2{\{ #1 \ \vert \ #2 \}}\) \(\def \order #1{\lvert {#1} \rvert}\) 問題概要 \(N\) 頂点の tree \(G\) が与えられる． \begin{align} U &:= \set{(i,j,k) \in V(G)}{ i,j,k \text{は相異なる} }, \\ L &:= \set{(i,j,k) \in U}{i,j,k \text{は一直線状に並ぶ}} \end{align} とおく． ここで，\(i,j,k\) が一直線上に並ぶとは， 次のいずれかが成り立つことである． \(k \i…

yukicoder 1962の解説の解説 - メモ これが読みづらいということではないのですが、最初読んだ時意味が分からず自分で考えてみたら納得できた、ということがあったので、その過程を書いておきます。以下色々なものを未定義なまま書き進めます。 正規表現とか 突然ですが、正規表現と形式的冪級数を同一視します。以下のように対応関係を定めます。 正規表現 x は形式的冪級数 x に対応する。 正規表現 R と S について、R|S を R または S にマッチする正規表現とし、形式的冪級数 R + S に対応させる。 正規表現 R と S について、RS を R にマッチする文字列と S にマッチ…

ABC214F 最後に使う文字を全探索する． 今 \(i \in N\) 文字目を見ているとする． \(j \leq i\) の範囲を，\(j\) を小さくしながら調べる． 初めて \(s_{j} \neq s_{i}\) となる直前までの \(j\) に対して， \(dp_{i} += dp_{j}\). 実装2文字前からスタートしたいため， dp テーブルは \(s\) の index より +2 する． \(s\) から 1文字以上使わないといけないので， \(s\) から丁度 1文字 (\(s_{i}\)とする) とるということを， \(s_{i}\) と -2 文字目 をとるという扱…

ABC166E 相異なる \(i,j \in N\) の組を数える． これは典型で，\(i < j\) として \(j\) の方を全探索する． それにより，今 \(j\) を探索しているとき，すでに \(i < j\) については すべて調べ終わった状態になるため． abs(j-i) = a[i] + a[j] より， j-i = a[i] + a[j]． これを i,j の式に分離すると， j - a[j] = i + a[i] \(\cdots (*)\). よって，ans = {(i,j) \(\in N \times N\) | i < j かつ j-i = a[i] + a[j]} …

算数・数学で「場合の数」というのがあります。

ABC295E ソートはしないで個数を数える． \(1\) から \(m\) を動く確率変数 \(x\) に対して，\(x\) の期待値は \begin{align} e_{x} & = & \sum_{i = 1}^{m} \ i \cdot p_{x = i} \\ & = & \sum_{i = 1}^{m} \ p_{x \geq i}. \end{align} \(p_{x \geq i}\) は，ソートをしないで \(j \in a_{j} \geq i\) となる \(j\) の個数を数えれば求まる．\(a\) における \(0\) の個数を \(z\) とおく．\(for \ …

ARC143B 条件を満たす場合の性質，必要条件条件を満たさないマスを悪いマスと呼ぶ． 悪いマスは高々1個． 2つ以上存在すると仮定して，それらのうち異なる2つを\(x,y\ (x \neq y)\) とする． このとき， \begin{align} a && \cdots &&y \\ \vdots && && \vdots \\ x && \cdots && b \end{align} の形になる． よって， \(x > a > y\) かつ \(x < b < y\) となって矛盾． 数え上げ悪いマスを全探索する代わりに， 悪いマスを含む行と列の選び方を全探索する． その様な行と列に使わ…