AtCoder,動的計画法,累積和

問題方針

まず、壁がない場合を考えます。

\( d(i, j) \) をマス \( (1, 1)\) から マス \( (i, j) \) への移動方法の数とします。\( d(i, j) \) は、\( n = \min ( ...

AtCoder,いもす法

問題方針

ある時間において使用される水の最大値が \( W \) を超えなければ良いので、いもす法を使います。

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

AtCoder,全探索

問題方針

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

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

AtCoder,数学

問題方針

点 \( (S_x, S_y) \) と 点 \( (x, 0) \) を通る直線の傾きを \( a_1\) とし、点 \( (G_x, G_y) \) と 点 \( (x, 0) \) を を通る直線の傾きを \( a_2\ ...

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,数学

問題方針

自然数 \( x \) が \( 3 \) の倍数であるとき、各桁の和である数字和も \( 3 \) の倍数となります。\( i \) 桁目の数字を \( x_i \) とすると、消す可能性のある数字は、\( x_i \bmo ...

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) ...