[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\) を作ることができるか調べます。
文字が現れる頻度を計算する各文字列についてどの文字の頻度を計算します。も ...
[Codeforces] Codeforces Round #573 (Div. 2) C. Tokitsukaze and Discard Items
\( 1 \) から \( n \) までの数字があり、\( k \) 個ごとに仕切りがあります。初期の配置では、仕切り \( i \) には、\( ik \) から \((i + 1)k\) までの数字が存在しています。 ...
[yukicoder] No. 848 なかよし旅行
解説を見ても良く分かりませんでした。
似たような問題で、CSA の良問があります。
コード#include <bits/stdc++.h>using namespace std;typedef l ...
[AtCoder] ABC 133 D – Rain Flows into Dams
\( N = 2n + 1 \) として考えます。
山 \( i \) に降った雨の量を \( x_i \) とします。このとき、
\
となります。よって、\( S_{2n+1 ...
[AtCoder] ABC 133 C – Remainder Minimization 2019
区間 \( \) を全探索する必要はなく、\( \) の範囲を調べればよいです。これは、
\
という関数を考えると、\( 0 \leq f(x) \leq 2018 \ (L \leq x \leq L ...
[yukicoder] No. 847 Divisors of Power
\( N \) を素数 \( p_i \) と 正の整数 \( a_i \) を用いて、 \( N = p_1^{a_1}p_2^{a_2} \cdots p_n^{a_n} \) と表すと、
\ ...
[yukicoder] No. 846 メダル
\
上記を満たす整数 \( x, y, z \) について、次の不等式が成り立ちます。
\begin{eqnarray}
z – 1 &<& \dfra ...