探索

問題方針

\( n + 1 \) の長さの丸太を切断することを考えます。

\

を満たす最大の \( m \) を求めると、\( n + 1 – m \) 本の丸太を買えば良いです。

コード#in ...

問題方針

整数計画法である 0-1 ナップサック問題を線形計画法で解くことを考えます。線形計画法では、重さ当たりの価値が大きいものから取っていけば良いです。ここで、荷物を重さ当たりの価値の降順になるように並び替えます。

深さ ...

問題方針半分全列挙

\( n = \min(20, N) \) として、問題を \( n \) と \( N – n \) 個に分けて考えます。前半の問題の集合を \( A \) とし、後半を \( B \) とします。\( ...

問題方針

文字列 ‘a’ のマスのリストを \( a \) とし、マス ‘S’ からマス \( p \) の最短距離を \( d(p) \) とします。探索は迷路で使われるような幅優先探索 ...

問題方針

問題を解く順番は関係ないので、コンプリートする問題を全探索します。これは、ビット全探索で解くことはできます。コンプリートした問題の集合を \( 2 \) 進数で表し、点数が \( G \) 未満ならば、コンプリートしていない問 ...

問題方針

\( N \) 個の順列の中で先頭が \( 1 \) であるものを探索します。したがって、順列を生成して全探索します。

コードnext_permutation#include <bits/stdc++.h>usin ...

問題方針

\( H \) 行 \( W \) 列の情報を \( g(i, j) \) とします。\( g(i, j) = 1 \) のとき電球があり、\( g(i, j) = 2 \) のとき壁があるとします。ここで、\( g(i, j ...

問題方針

\( A \) の累積和を \( b \) とし、\( b \) の累積和を \( c \) とすると、

\begin{eqnarray}
b_i &=& A_1 + A_2 + \cdot ...

問題方針

\( H, W \) を昇順に並び替えても一般性は失われないので、昇順に並び替えます。例えば、\( 2n \) 人の児童の最適なペアは

\

であると考えられます。これを問題に当てはめて考えると、\( N ...

問題方針

\( |S| \geq 3 \) のときを考えます。自然数 \( n \) が \( 8 \) の倍数である条件は、下 \( 3 \) 桁が \( 8 \) の倍数であることと同値なので、\( 3 \) 桁の \( 8 \) ...