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 \) であるときの重要度の合計の最大値とします。遷移 ...

AtCoder, 全探索, 累積和

問題方針

長方形の和は二次元の累積和を使うことで高速に求めることができるので、全ての長方形のパターンを計算し、\( i \) 個のたこ焼きを焼くときの最大値 \( d(i) \) を求めます。\( d(j) > d(i) \ (j ...

AtCoder, 動的計画法, 累積和, 遅延評価セグメント木

問題方針遅延評価セグメント木

動的計画法のようなことを遅延セグメント木を使って行います。\( v_i \) をマス \( i \) まで行く方法の個数とします。初期値は \( v_1 = 1 \) です。区間 \( \) から整数を選 ...

AtCoder, 全探索, 数え上げ, 数学

問題方針\( A, B \) を全探索

\( A, B \) を全探索します。\( A \) を固定した時、\( A \times b \geq N \) となるような \( b \) より大きいものを探索する必要はありません。 ...