競プロで WA を軽減したい

問題： Aizu Competitive Programming Camp 2021 Day 1 C – 橋作り ( https://onlinejudge.u-aizu.ac.jp/services/room.html#ACPC2021Day1/problems/C )

$N-1 \leq M \leq \mathrm{min}(\frac{N(N-1)}{2} , N )$

(辺数) $\leq$ (頂点数) で連結なので、グラフは木またはなもりです。

問題： yukicoder contest 309 F – Travel in Mitaru city 2 ( https://yukicoder.me/problems/no/1647 )

行番号に $x$ 、列番号に $y$ が用いられています。図を描いて考えると、求める数列の条件にある”行”と”列”を逆にして実装してしまう場合があります。

リンク先の記事ではハンガリアン法の実装例が紹介されていますが、 step2 で二部グラフの完全マッチングの存在を判定するときに正しくない貪欲法を用いているため、実装全体が正しくなくなっています。

verify が $1 \geq n$ でのみ行われていました (verify用問題) 。現在は修正され、この問題は無くなっています ( commit 履歴の該当箇所 ) 。

AtCoder Beginner Contest 212 H – Nim Counting 解説

等比数列の部分和の公式を知っていますか？私は知っています。 $r=1$ の場合分けに気を付けましょう。（解説のコード中では関数 func が該当箇所です。）

（動画右上に表示されているチャットを見ると状況を理解しやすいです。）この問題では入力が $N \times N$ の配列で与えられており、動画ではプログラムの一部でその $2$ つの添え字が入れ替わっていたため、いくつかのテストケースで WA となっています。入力を受けた変数 a の意味は問題文で確認できますが、変数 array の意味は簡単に確認できないため、見つけにくいバグを発生させたと考えられます。

動画中の考察メモの”操作回数の期待値”はあいまいです。この後の実装過程は、貰う・配るや遷移方向を逆向きにして書き換えて実行を試すなど、アドリブ的で非効率的です。対策として、どこからどこまでの操作回数なのか、さらに期待値の表現（全体に対する寄与なのか条件を満たすことを仮定して導かれるものなのか）を一旦決めてから考察します。そのとき初めて解法の正当性を確認したり、適切な漸化式を求めたりできるようになります。

kyopro_friends さんによる解説では次のように定義されています。

$dp[c1][c2][c3]=($1個の皿が$c1$枚、2個の皿が$c2$枚、3個の皿が$c3$枚あるとき、全て食べるまでの操作回数の期待値$)$

https://kyopro-friends.hatenablog.com/entry/2019/01/12/231000

テーブルの定義に従って、寿司 $1$ 個の皿が $c1$ 枚、寿司 $2$ 個の皿が $c2$ 枚、寿司 $3$ 個の皿が $c3$ 枚ある状態を状態 $(c1,c2,c3)$ と表します。すると、

• 状態 $(c1,c2,c3)$ $(1 \leq c1+c2+c3)$ から操作を始めると、次の操作で
  • $c1\neq 0$ の場合のみ、 $\frac{c1}{N}$ の確率で状態 $(c1-1,c2,c3)$ へ遷移し、それ以降は状態 $(c1-1,c2,c3)$ から操作を始める場合と同じである
  • $c2\neq 0$ の場合のみ、 $\frac{c2}{N}$ の確率で状態 $(c1+1,c2-1,c3)$ へ遷移し、それ以降は状態 $(c1+1,c2-1,c3)$ から操作を始める場合と同じである
  • $c3\neq 0$ の場合のみ、 $\frac{c3}{N}$ の確率で状態 $(c1,c2+1,c3-1)$ へ遷移し、それ以降は状態 $(c1,c2+1,c3-1)$ から操作を始める場合と同じである
  • $\frac{N-c1-c2-c3}{N}$ の確率で状態 $(c1,c2,c3)$ へ遷移し（留まり）、それ以降は状態 $(c1,c2,c3)$ から操作を始める場合と同じである
• つまり、 $$\left. \begin{array}{l} dp[c1][c2][c3]=1&+&\frac{c1}{N}\cdot dp[c1-1][c2][c3]\\&+&\frac{c2}{N}\cdot dp[c1+1][c2-1][c3]\\&+&\frac{c3}{N}\cdot dp[c1][c2+1][c3-1]\\&+&\frac{N-c1-c2-c3}{N}\cdot dp[c1][c2][c3] \end{array} \right. (1 \leq c1+c2+c3)$$

と考察でき、正しい漸化式を導出しやすいと思います。

一方で、例えば $dp[c1][c2][c3]$ を初期状態つまり状態 $(X,Y,Z)$ から状態 $(c1,c2,c3)$ までの操作回数の期待値としようとすると、初期状態から操作を始めて状態 $(c1,c2,c3)$ を通らない場合があるため、テーブルを厳密に定義するのが難しくなります。しかし、例えば次のようにテーブルを定義すると漸化式を立てられます。

• $prob[c1][c2][c3]=($ 初期状態から操作を繰り返して状態 $(c1,c2,c3)$ に至る確率 $)$
• $e[c1][c2][c3]=($ 初期状態から操作を繰り返したときの次の値の期待値 $)$
  • 状態 $(c1,c2,c3)$ に至らない場合 $0$
  • 状態 $(c1,c2,c3)$ に至る場合、状態 $(c1,c2,c3)$ に至るまでの操作回数

AC コード

• $prob[c1][c2][c3]=($ 初期状態から操作を繰り返して状態 $(c1,c2,c3)$ に至る確率 $)$
• 状態 $(c1,c2,c3)$ から抜けるための操作回数の期待値が求まるので、その値に $prob[c1][c2][c3]$ を掛けたものの総和が答え

AC コード

サイシードプログラミングコンテスト2021（AtCoder Beginner Contest 219） H – Candles : Nachia によるユーザー解説

すると、計算量はともかく、$\mathrm{dpL}[l][r],\mathrm{dpR}[l][r]$ は $r-l$ の大きい順に求めることができます。

https://atcoder.jp/contests/abc219/editorial/2669

私が書いたものではありますが、動的計画法のテーブルを定義した後に考察を進める様子の例です。

yukicoder contest 315 F – Badugi の AC コード

これよりも上で述べた作戦では改善が難しい例です。解答の方針は、条件を満たす二部グラフを列挙し、それぞれについて同型なグラフの個数を二項係数などの積で表現し、足し合わせることです（コード中のコメントによる図は頂点と辺の関係が逆になっています）。各グラフについての計算式を ( $1$ つ以上の辺が隣接する頂点の選び方の個数 ) $\times$ ( グラフ中での役割の割り当て方の個数 ) $\times$ ( 辺の張り方の個数 ) の形式で表し、 $3$ 行で書かれているため、デバッグ中に式の意味を理解しやすくなっています。さらにコメントで図が添えられているため、どのような場合を考えているのかすぐに確認できます。