数学的知識を必要とする問題や、数学に関するカテゴリーです。

AtCoder, 数学

問題方針

\( (r_1, c_1)\) から \(( r_2, c_2) \) への移動は、\( x = |r_2 – r_1| \)、\( y = |c_2 – c_1| \) として、\( (0, 0)\) ...

AtCoder, 数学

問題方針

\( xy = P\) となるような \( x, y \) を全探索します。このとき、探索は \( x \) についてだけでよく、\( 1 \leq x \leq \sqrt{P} \) の範囲で十分です。

コード

yukicoder, 数え上げ

問題方針

\( x^2 + y^2 \) の頻度をあらかじめ計算しておき、\( z^2 – w^2 + D \) が存在するかを調べます。また、定数倍高速化をすることで、\( N^3 \) のコードもギリギリ通りました。

AtCoder, 区間系, 数学

問題方針

自然数 \( m \) を

\

とします。

\( N \) が奇数のとき

中央値の最小値は \( A \) を昇順に並べた時の \( A_{m} \) となり、最大値は \( B \) を昇順 ...

AtCoder, 数学

問題方針

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

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, 全探索, 数学

問題方針

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

AtCoder, 全探索, 数学

問題方針

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

\

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

AtCoder, Union Find, 数え上げ

問題方針

例えば、\( 1 \) 行目と \( 2 \) 行目が交換可能であり、\( 1 \) 行目と \( 3 \) 行目が交換可能であるとき、各 \( 1, 2, 3 \) 行の順番を任意に並び替えることができます。したがって列に対 ...