[AtCoder] ABC 135 D – Digits Parade
\( d(i, j) \) を \( i \) 桁目までの調べた時、余りが \( j \) となるものの個数とします。初期値として、\( d(0, 0) = 1 \) とします。
\( S_i = ?\) のと ...
[AtCoder] ABC 135 C – City Savers
\( i \) 番目の勇者が \( i \) 番目のモンスターを可能な限り倒し、\( i + 1 \) 番目のモンスターを可能な限り倒します。これを \( 1 \) 番目の勇者から順番にシミュレーションします。
コード# ...
[Codeforces] Educational Codeforces Round 69 (Div. 2) C. Array Splitting
\( a \) が昇順に整列されていることが重要です。
偏差に着目する\( e_i = a_{i + 1} – a_{i} \) とすると、\( l < r \) として、
\ ...
[Codeforces] Educational Codeforces Round 69 (Div. 2) B. Pillars
柱を \( a_1 < a_2 < \cdots < a_n \) のように並び替えることができるかという問題です。どのようにして整列させるかというと、\( a \) を昇順に整列させた配列を \( b \) ...
[AtCoder] AGC 036 A – Triangle
有名な公式として、点 \( O = (0, 0), A = (x_1, y_1), B = (x_2, y_2)\) において、三角形 \( OAB \) の面積 \( s \) は、
...
[AtCoder] ABC 134 E – Sequence Decomposing
\( A_1 \geq A_2 \geq \cdots \geq A_i \) となるような広義単調減少列に対して、\( i \) 個の色が必要であることが分かります。これは、連続しない部分列に対しても言える ...
[AOJ] DPL 1 D 最長増加部分列
LIS: Longest Increasing Subsequence (最長部分増加列) という問題です。この問題では、狭義単調増加列の中で最も大きいものを求めます。
動的計画法と二分探索参考を参照してください。 ...
[AtCoder] ABC 134 D – Preparing Boxes
後ろの箱からボールを入れることを考えると、その箱以降の倍数の個数は変化しないことが分かります。
例えば、\( i < \dfrac{N}{2} \) を満たす \( i \) の倍数は、\( ...
[AtCoder] ABC 134 C – Exception Handling
\( A \) を昇順に整列させた配列を \( B \) とすると、\( B_N \) は \( A \) の最大値となります。\( A_i \) を取り除いた配列の最大値は、\( A_i = B_N \) ならば、\(B_{ ...
[Codeforces] Educational Codeforces Round 68 (Div. 2) C. From S To T
文字列 \( s \) に \( p\) に含まれる文字の数だけ任意の場所に挿入して、文字列 \(t\) を作ることができるか調べます。
文字が現れる頻度を計算する各文字列についてどの文字の頻度を計算します。も ...