Codeforces, 全探索, 探索

問題方針

\( n \) 階建てビルの \( s \) 階から一番近いレストランを探します。フロア \( a_i \) のレストランは閉店しているので、\( s – k \) から \( s + k \) の範囲を全探索を行 ...

yukicoder, 探索, 深さ優先探索

問題方針

全探索を行って和了しているかを調べます。また、七対子は特殊な形なので、\( 7 \) 種類の対子があるのかを調べます。他の手は、\( 4 \) 面子 \( 1 \) 雀頭の形をしているかをチェックすれば良いので、まず初めに雀頭 ...

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

問題方針

良くある迷路の探索のアルゴリズムを使って、全探索を行います。ここでは、全ての道となっているマスから幅優先探索を行い、到達可能なマスの最短距離を求めます。

コード

 

AOJ, 実装, 探索, 深さ優先探索

問題方針

パズルは最大でも \( 8 \) 回の操作で解くことができるので、\( 4^7 \) 通りのパターンを調べれば良いです。したがって、深さ優先探索を行い、実際にシミュレーションを行います。

コード

 

AOJ, 全探索, 探索, 整列

問題方針

買い物をする駅の番号の順番を変えても影響がないので、\( d_i \) を昇順に整列させます。ここで、\( d_i < p \) を満たす最大の \( d_i \) を \( l \) とし、\( d_i > p ...

AtCoder, 二分探索, 探索, 累積和, 貪欲法

問題方針

一般ゲストの並びを変えても影響がないので、降順に並び替えます。つまり、\( A_{i}\geq A_{i + 1} \ (0 \leq i \leq N – 2)\) を満たすとします。

最終的な幸福度が最大 ...

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

問題方針

各生徒をノードに見立てて、隣接リストを構築します。生徒 \( i \) が所属している部活動を \( g_i \) とし、所属が未確定のときを \( g_i = 0 \) とします。生徒 \( a, b \) が同じ部活動に所 ...

AOJ, 全探索, 探索

問題方針

両端のパンケーキは \( 1 \) 枚だけ裏返すことができることに着目します。左端のパンケーキは単独で裏返す回数を \( k \) とすると、最小値を達成するためには、\( 0 \leq k \leq p_1 \) であること ...

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

問題方針

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

\

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

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

問題方針

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