深さ優先探索

問題方針

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

深さ ...

問題方針

\( 8 \) クイーン問題です。深さ優先探索によって解答します。初期値が当てられたとき、配置が可能かに注意します。

コード#include <bits/stdc++.h>using namespace std;t ...

問題方針

全ての数列のパターンに対して得点を求めます。どのように数列を生成するかですが、深さ優先探索を行います。条件を満たす数列が \( i \) 番目まで決まっているとき、\( A_{i + 1} \) の値は、\( A_{i} \l ...

問題方針

深さ優先探索を使うらしい。

コード#include <bits/stdc++.h>using namespace std;typedef long long ll;int N;void dfs(string s) ...

問題方針

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

問題方針

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

コード#include < ...

問題方針

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

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

問題方針素因数分解

\( N \) を素数 \( p_i \) と 正の整数 \( a_i \) を用いて、 \( N = p_1^{a_1}p_2^{a_2} \cdots p_n^{a_n} \) と表すと、

\ ...

問題方針各マスに番号を割り振る

\( H \) 行 \( W \) 列のマスを持つグリッドにおける \( i \) 行 \( j \) 列目のマスの番号を \( i \times W + j \) とします。このようにマスの番号を割り当 ...

問題方針制約から考える

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