サイトの親カテゴリー

Codeforces, 数え上げ, 累積和, 貪欲法

問題方針

AGC 023 A – Zero-Sum Ranges と似ている問題です。\( s \) を \( a \) の累積和として、

\

とします。また、\( s_0 = 0 \) です。ある部 ...

Codeforces, 数学, 貪欲法

問題方針

\( i \) 回目の操作後の数列の総和を \( s_i \)、数列の最大値を \( b_i \) とすると、

\

となるので、先にインクリメントしてからコピーする方が最適だと考えられます。ここで、イン ...

AtCoder, セグメント木, 動的計画法

問題方針

最長増加部分列を解くような感じで解けるみたいですが、あまり理解できませんでした。

まず初めに、\( A_i \leftarrow A_i + K \) と再定義します。ここで、\( d(i) \) を末尾が \( ...

AtCoder, Union Find, 幅優先探索

問題方針Union-Find

グラフが連結かどうかを調べるには Union-Find を使えば良いので、ライブラリの dsu を使います。グループの数から \( 1 \) を引いた値が必要な道路の本数です。グループの数は、groups( ...

yukicoder, 動的計画法

問題方針

動的計画法を使って考えます。\( A_i \) の平均が \( K \) 以上ということは、\( A_i – K \) の総和が \( 0 \) 以上ということなので、\( d(i, j) \) を \( i \) ...

yukicoder, 数学

問題方針

問題文を注意して読みます。\( a^{a!} \) は

\

なので発散するスピードが速く、\( 4^{4!} > 10^9 + 7 \) となります。 したがって、\( A_i \geq 4 \) ...

yukicoder, 数学

問題方針

\( A \leftarrow A \bmod 12 \) と再定義して考えます。分針は \( 1 \) 分で \(6^\circ \) 動き、時針は \( 1 \) 時間に \( 30^\circ \) 動くので、分針は \ ...

Codeforces, 数学, 整列

問題方針

自然数 \( a, b \) が

\

を満たすとき、\( 2^{i} \leq a, b \leq 2^{i+1} -1 \) を満たす \( i \) が存在します。これは同じビット数で表現できる数は ...

Codeforces, フェニック木

問題方針

バブルソートを行った回数を求めるために、フェニック木 (BIT) を使います。詳しくは下記の参考を参照してください。

コード参考

AtCoder, 動的計画法

問題方針

ナップサック問題なので動的計画法で解きます。\( d(i, j, k) \) を スクリーンショット \( i \) まで見た時、\( j \) 枚貼り付けて幅が \( k \) であるときの重要度の合計の最大値とします。遷移 ...