AtCoder,整列

問題方針

元の配列と昇順に整列させた配列を比べて、異なる箇所が \( 2 \) 箇所以下であれば、昇順にすることができます。

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

AtCoder,データ構造

問題方針子どもの移動の挙動

どのような文字列でも十分に移動を行うと、’RL’ または ‘LR’ という二つのマスを行き来することになります。また、’RL’ という文 ...

AtCoder,実装

問題方針

あるマス \( i \) について、\( H_{i – 1} > H_{i} \) ならば、単調非減少とはなりません。\( H_{i-1} = H_{i} \) ならば、何もせず、\( H_{i – ...

AtCoder,動的計画法

問題方針動的計画法

\( d(i, j) \) を \( i \) 桁目までの調べた時、余りが \( j \) となるものの個数とします。初期値として、\( d(0, 0) = 1 \) とします。

\( S_i = ?\) のと ...

AtCoder,貪欲法

問題方針

\( i \) 番目の勇者が \( i \) 番目のモンスターを可能な限り倒し、\( i + 1 \) 番目のモンスターを可能な限り倒します。これを \( 1 \) 番目の勇者から順番にシミュレーションします。

コード# ...

AtCoder,数学

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

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

...

AtCoder,二分探索,動的計画法,探索

問題方針広義単調減少部分列

\( A_1 \geq A_2 \geq \cdots \geq A_i \) となるような広義単調減少列に対して、\( i \) 個の色が必要であることが分かります。これは、連続しない部分列に対しても言える ...

AtCoder,実装

問題方針最後の箱から調べる

後ろの箱からボールを入れることを考えると、その箱以降の倍数の個数は変化しないことが分かります。

例えば、\( i < \dfrac{N}{2} \) を満たす \( i \) の倍数は、\( ...

AtCoder,整列

問題方針

\( A \) を昇順に整列させた配列を \( B \) とすると、\( B_N \) は \( A \) の最大値となります。\( A_i \) を取り除いた配列の最大値は、\( A_i = B_N \) ならば、\(B_{ ...

AtCoder,数学

問題方針方程式を立てる

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

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

\

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