探索

問題方針

点 \( A, B , C \) が順序を問わずに一直線上にある条件は、

\

を満たす \( t \) が存在することです。ここで、\( \overrightarrow{AB} = (x_1, y_1) ...

問題方針

指数の発散は早いので、\( A, B \) を全探索します。また、オーバーフローに注意します。

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

問題方針

人数が \( N \) の約数であるとき平等に分けることができるので、約数の列挙を行います。 \( N \bmod x = 0 \) であるとき、\( x \) は \( N \) の約数となるので、\( 1 \leq x \ ...

問題方針Union-Find

グラフが連結かどうかを調べるには Union-Find を使えば良いので、ライブラリの dsu を使います。グループの数から \( 1 \) を引いた値が必要な道路の本数です。グループの数は、groups( ...

問題方針

長方形の和は二次元の累積和を使うことで高速に求めることができるので、全ての長方形のパターンを計算し、\( i \) 個のたこ焼きを焼くときの最大値 \( d(i) \) を求めます。\( d(j) > d(i) \ (j ...

問題方針\( A, B \) を全探索

\( A, B \) を全探索します。\( A \) を固定した時、\( A \times b \geq N \) となるような \( b \) より大きいものを探索する必要はありません。 ...

問題方針

ショートカットは冗長に選んだとしても \( 4^4 \) 通りなので、全てのショートカットの組み合わせに対して必要なボタンの入力回数を求めます。ここで、\( d(i, 0) \) を \( i \) 文字をショートカットを使わ ...

問題方針

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

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

問題方針

中心座標の候補は最大でも \( 10000 \) 個なので、中心座標に関して全探索します。\( h_i \neq 0 \) であるとき、

\begin{eqnarray}
h_i &=& H ...

問題方針非負整数解の個数

非負整数 \( x, y, z \) が

\

を満たすとき、\( x, y, z \) の組み合わせは、\( {}_{n} \mathrm{ H }_{2} = {}_{n + 1} \ ...