数え上げに関するカテゴリーです。

yukicoder, 数え上げ

問題方針

\( x^2 + y^2 \) の頻度をあらかじめ計算しておき、\( z^2 – w^2 + D \) が存在するかを調べます。また、定数倍高速化をすることで、\( N^3 \) のコードもギリギリ通りました。

AtCoder, Union Find, 数え上げ

問題方針

例えば、\( 1 \) 行目と \( 2 \) 行目が交換可能であり、\( 1 \) 行目と \( 3 \) 行目が交換可能であるとき、各 \( 1, 2, 3 \) 行の順番を任意に並び替えることができます。したがって列に対 ...

AtCoder, 数え上げ

問題方針

\( K \geq 0 \) として考えます。\( a + b = K + c + d \)  を満たす \( a, b, c, d \) の組み合わせを考えます。\( 2 \leq a + b \leq 2N \wedge ...

AtCoder, 数え上げ

問題方針

\( A_1 \neq 0 \) のとき場合の数は \( 0 \) となります。ここで、\( d_i(j) \) を \( i \) 番目までの人を調べ終えた時、同じ帽子が \( j \) 個であるパターン数とします。初期値は ...

AtCoder, Union Find, 数え上げ

問題方針照らされるマスについて

散らかっていないマス \( (i, j) \)に照明を置いたとき、水平方向を照らすマスの数を \( a(i, j) \) とし、垂直方向を照らすマスの数を \( b(i, j) \) とします。このとき、 ...

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

問題方針

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

\

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

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

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

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

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

問題方針

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

\

となります。ここで、

\

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

\

を満たすとき、

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

問題方針

全ての手札の組み合わせは \( {}_{NM} \mathrm{ C }_{K} \) 通りありますが、確率を比較するうえでは必要ありません。フラッシュの総数は、同一のソートから \( {}_{N} \mathrm{ C }_ ...

AtCoder, 数え上げ

問題方針方針1

行と列はそれぞれ独立に選ぶことができることに注目します。 \( i \) 行目にある爆弾の個数を \( R(i) \) とし、\( j \) 列目にある爆弾の個数を \( C(j) \) とします。マス \( (i, j ...