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 \) より大きいものを探索する必要はありません。 ...

AtCoder, 数学

問題方針

シミュレーションすると分かると思いますが、\( A_i \) の値は周期的に遷移します。剰余は \( 0 \) から \( M – 1 \) までの値を取ります。したがって、周期的になる前の \( A_i \) の ...

yukicoder, 数え上げ, 数学, 累積和

問題方針

\ であることを利用して、

\

となります。ここで、

\

について考えます。自然数 \( k \) を用いて、\( A_i \) が

\

を満たすとき、

yukicoder, 数学

問題方針

\( p = 2 \) のときは \( x = 2 \) が答えとなります。それ以外について考えます。フェルマーの小定理より、

\

となるので、自然数 \( t \) について、

\ ...

AtCoder, 幾何学

問題方針

最大値は辺の長さの総和となります。最小値は座標で考えると難しいので、図形として考えます。辺の長さを \( a < b < c \) とすると、\( c < a + b \) のとき三角形を作成することができま ...