AOJ,グラフ理論,二部グラフ

問題方針

2部マッチングの解説は、二部マッチングの解説を参照してください。二部グラフの最大マッチングを求めるアルゴリズムについては、蟻本の p. 197 のコードを利用します。

\( X \) の頂点と \( Y \) の頂 ...

AtCoder,数学

問題方針連立方程式

問題文より、次の連立方程式が得られます。

\

\この連立方程式は、\( a_i + b_j = c_ {i, j}\) から得られます。この連立方程式が解を持つための条件は、係数行列 \( A \) ...

AtCoder,動的計画法

問題方針動的計画法

\( dp \) をマス \( (i, j)\) におけるアメの所持数の最大値とします。マスの移動は右か下に行くかだけなので、下に行くことができるのは \( 1 \) 回だけとなります。したがって、

\ ...

AtCoder,ビット全探索,探索

問題方針ビット全探索

ある曜日のどの時間帯に店を営業するかどうかで利益が変わり、\( 5 \) つの曜日と午前・午後を考えれば良いので、\( 2^{10} \) 通りのビット全探索を行えば良いことが分かります。

店の営業情報は \ ...

AtCoder,累積和

問題方針最終的な形を考える

\( K \) 回までの指示をした時の文字列において、最大何個の 1 が連続して並んでいるかを問われているので、指示の順番を考慮する必要がないことが分かります。つまり、最終的な形がどのようになるかを考えればよ ...

AtCoder,数学

問題方針\( n \) 回目で操作が終了する確率

ある試行で操作が終了する確率は、

\

となります。また、ある試行で操作が終了しない確率は、\( q = 1 – p\) となります。\( n \) 回 ...

CSA,幅優先探索,探索

問題問題の意図

頂点数が \( N \) 個で辺の数が \( M \) 本の無向グラフが与えられます。始点 \( S \) から終点 \(A, B \) への最短経路において、同じ辺を通る長さの最大値を答えます。また、辺の重みは \( ...

AtCoder,ビット全探索,動的計画法,探索

問題方針ある高さの正しい横棒の配置

ある高さの横棒の配置のパターンを考えます。横棒は縦棒の間に置くことができるので、縦棒の本数 \( W \) が \( W = 1 \) のときは横棒を置くことができません。そうではないとき、縦棒の間に ...

AtCoder,貪欲法

問題方針最適な水やりの方法

水やりの操作回数を最小化するには、連続した区間 \( \) が大きくなるように水をやる必要があります。つまり、連続して水やりをできる区間は一回の操作で高さを \( 1 \) 上げるというようにします。 ...

AtCoder,区間系

問題方針いもす法

区間の最大被覆数を求める問題なので、いもす法が思い浮かぶと思います。実際に、いもす法の解説においてもこの問題が取り上げられています。

優先度付きキューを用いる方法

いもす法では値が大きくなると計算量がその分増 ...