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

問題方針二部マッチング問題

基本的には、 GRL_7_A Bipartite Matchingと同じようにして解くことができます。

頂点は与えられますが、辺がどのようになっているかは自分で実装しなければいけません。赤い点のラ ...

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 \) 回 ...

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

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

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

AtCoder, 貪欲法

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

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

AtCoder, 区間系

問題方針いもす法

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

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

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

AtCoder, 二分探索, 探索

問題方針二分探索

整列された配列に対してある値より大きいまたは小さいものの個数を求めるには、二分探索を使って求めることができます。C++ には “lower_bound” と “upper_bound ...