[Codeforces] Codeforces Round #674 (Div. 3) D. Non-zero Segments
AGC 023 A – Zero-Sum Ranges と似ている問題です。\( s \) を \( a \) の累積和として、
\
とします。また、\( s_0 = 0 \) です。ある部 ...
[Codeforces] Codeforces Round #674 (Div. 3) C. Increase and Copy
\( i \) 回目の操作後の数列の総和を \( s_i \)、数列の最大値を \( b_i \) とすると、
\
となるので、先にインクリメントしてからコピーする方が最適だと考えられます。ここで、イン ...
[AtCoder] ACL Beginner Contest D – Flat Subsequence
最長増加部分列を解くような感じで解けるみたいですが、あまり理解できませんでした。
まず初めに、\( A_i \leftarrow A_i + K \) と再定義します。ここで、\( d(i) \) を末尾が \( ...
[AtCoder] ACL Beginner Contest C – Connect Cities
グラフが連結かどうかを調べるには Union-Find を使えば良いので、ライブラリの dsu を使います。グループの数から \( 1 \) を引いた値が必要な道路の本数です。グループの数は、groups( ...
[yukicoder] No. 1238 選抜クラス
動的計画法を使って考えます。\( A_i \) の平均が \( K \) 以上ということは、\( A_i – K \) の総和が \( 0 \) 以上ということなので、\( d(i, j) \) を \( i \) ...
[yukicoder] No. 1237 EXP Multiple!
問題文を注意して読みます。\( a^{a!} \) は
\
なので発散するスピードが速く、\( 4^{4!} > 10^9 + 7 \) となります。 したがって、\( A_i \geq 4 \) ...
[yukicoder] No. 1236 長針と短針
\( A \leftarrow A \bmod 12 \) と再定義して考えます。分針は \( 1 \) 分で \(6^\circ \) 動き、時針は \( 1 \) 時間に \( 30^\circ \) 動くので、分針は \ ...
[Codeforces] Codeforces Round #672 (Div. 2) B. Rock and Lever
自然数 \( a, b \) が
\
を満たすとき、\( 2^{i} \leq a, b \leq 2^{i+1} -1 \) を満たす \( i \) が存在します。これは同じビット数で表現できる数は ...
[Codeforces] Codeforces Round #672 (Div. 2) A. Cubes Sorting
バブルソートを行った回数を求めるために、フェニック木 (BIT) を使います。詳しくは下記の参考を参照してください。
コード#include <bits/stdc++.h>using namespace std;t ...
[AtCoder] ABC 015 D – 高橋くんの苦悩
ナップサック問題なので動的計画法で解きます。\( d(i, j, k) \) を スクリーンショット \( i \) まで見た時、\( j \) 枚貼り付けて幅が \( k \) であるときの重要度の合計の最大値とします。遷移 ...