yukicoder,二分探索,探索,累積和

問題方針

コーヒー豆のおいしさ度の候補は、累積和の数だけあるので、\( N \) 通りあることがわかります。ここで、累積和を

\

とします。おいしさ度を \( s_i \) と固定したとき、条件を満たすような分割 ...

AtCoder,グラフ理論,幅優先探索,探索

問題方針

必要な色の数は、頂点の最大次数となるので、任意の頂点から幅優先探索を行い、色を振り分けていきます。辺の色を順番に出力する必要があるので、マップを使って管理します。また、色を分けるときに使用できない色を管理するためにセットを使い ...

AOJ,ビット全探索,探索,数え上げ

問題方針

参加するメンバーの組み合わせは \( 2^{N} – 1\) 通りあるので、ビット全探索を行います。周期が同じメンバーが増えても必ず同じ公演に参加することになるので、参加するメンバーの組み合わせが増えることはありま ...

AtCoder,ビット全探索,探索

問題方針ビット全探索

ある人は正直者か不親切な人かの \( 2 \) 通りなので、全体で \( 2^N \) のパターンがあります。なので、ビット全探索を行います。人 \( i \) が正直者としたとき、その証言が現在のビットの状態と同 ...

AtCoder,データ構造,全探索,探索

問題方針

長さが \( N \) の文字列から \( 3 \) 文字取り出すことを考えると、計算量は \( {}_{N} \mathrm{ C }_{3}\) となってしまうので、別の方法を考えます。考えられる文字列は \( 1000 ...

AtCoder,二分探索,探索

問題方針

\( f(N) = AN + Bd(N)\) とすると、\( f(N) \) は増加関数なので、二分探索を行います。整数の桁数は、対数を使うよりも、数値を文字列に変換してから長さを得る方が良いと思います。

コード#inc ...

AtCoder,探索,深さ優先探索

問題方針

順列を生成して距離を計算します。

コード#include <bits/stdc++.h>using namespace std;typedef long long ll;int a;bool flag;dou ...

AtCoder,グラフ理論,幅優先探索,探索

問題方針

座標間の距離が与えられるので、相対的な位置が分かります。したがって、ある座標の値を \( x_i = 0 \) として、\( M \) 個の情報に誤りがあるかどうかを調べます。

グラフ

各座標をグラフの頂点として、\ ...

AtCoder,二分探索,探索

問題方針最適な食べ物の配置

証明ができなかったので、予想を立てて考えます。おそらく、修行前の最適なコストは、次のようになります。配列 \( A, F\) を

\

\

と整列させます。このときのコストを ...

AtCoder,二分探索,探索

問題方針

全てのパターンについて調べると計算量が \( O(N^3) \) となるので間に合いません。なので、\( 2 \) 本を固定して考えます。

二分探索

\( a \leq b \leq c \) として、\( b, c ...