AtCoder,全探索,実装

問題方針

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

AtCoder,全探索,数学,累積和

問題方針

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

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

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

問題方針

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

\

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

AtCoder,全探索,数学

問題方針

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

AtCoder,全探索,数学

問題方針

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

\

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

AtCoder,全探索,数学

問題方針

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

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

AtCoder,全探索,数学

問題方針

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

AtCoder,Union Find,幅優先探索

問題方針Union-Find

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

AtCoder,全探索,累積和

問題方針

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

AtCoder,全探索,数え上げ,数学

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

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