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, 区間系

問題方針いもす法

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

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

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

AtCoder, 二分探索, 探索

問題方針二分探索

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

AtCoder, 探索, 深さ優先探索

問題方針制約から考える

竹の本数 \( N \) は最大で \( 8 \) 本であることに注目すると、合成魔法を基準に考えていけばよいことが思いつきます。ある竹 \( i \) について、合成魔法を適用できる竹は \( 3 \) 通りで ...