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

AOJ, 数学

問題方針

東南方向の斜めの道が無ければ、\( 2 \) 点間の最短距離は、

\

となります。

南西方向

観光スポットが南西方向にある場合、東南方向の道を通る必要がないので、最短距離は、

\

AtCoder, グラフ理論, 数学

問題方針

一見難しそうに見えますが、\( 300 \) 点の問題なので解法は簡単であることが予想できます。

実現不可能な整数列頂点 \( 1 \) からの距離について

頂点 \( 1 \) からの距離が与えられるので、 ...

AtCoder, 数学

問題方針

水筒を傾けた時に入る水の最大値を考えます。傾けた時の角度を \( \theta \) とします。このときの水筒の容量を \( V (\theta)\) とします。そして、\( V (\theta) = x \) を満たす \( ...

AtCoder, 数学

問題

C – Walk on Multiplication Table

方針

\( N = x \times y \) を満たす正の整数 \( x, y\  (x \leq y) \) がマスの候補となるので、\( ...

AtCoder, 数学

問題方針

\( A \) と \( B \) の公約数を考えるので、\( A \) と \( B \) の最大公約数を考えます。最大公約数を素因数の数が求める答えとなります。

コード

 

AtCoder, 数学

問題方針

条件を具体的に書き出すと、

\

となり、\( A_1 \) と \( A_N \) は不等式の制約が一つであることが分かります。よって、\( A_1 = B_1 \), \( A_N = B_{N-1} ...

AtCoder, 数学

問題方針制約から考える

\( N = 10^9 \) と制約がきついので、計算量は \( O(\sqrt{N})\) や \( O(1) \) などが考えられます。また、こういった問題は、\( N = 1 \) から実際にシミュレーショ ...

AtCoder, 数学

問題方針食材の価値

\( 1 \) 回の合成で使用された食材の価値は半減します。食材 \( i \) が合成に使われた回数を \( a_i \) とし、最終的な価値を \( f \) とすると、

\

となります。 ...

AtCoder, 数学

方針方針座標から三角形の面積を求める

有名な公式として、点 \( O = (0, 0), A = (x_1, y_1), B = (x_2, y_2)\) において、三角形 \( OAB \) の面積 \( s \) は、

...

AtCoder, 数学

問題方針方程式を立てる

\( N = 2n + 1 \) として考えます。

山 \( i \) に降った雨の量を \( x_i \) とします。このとき、

\

となります。よって、\( S_{2n+1 ...