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

AtCoder, 数え上げ

問題方針

配列 \( A \) の順序は影響しないので、昇順に並び替えます。\( {}_{N} \mathrm{ C }_{K} \) 個の組み合わせの中で、最大値と最小値を求めます。最小値の総和を \( f_1 \) とし、最大値の総 ...

AtCoder, 数え上げ

問題方針

\( A_i < A_j \) を満たす \( (i, j) \ ( i < j ) \) の数を \( l_j \) とし、\( A_j < A_k \) を満たす \( (j, k) \ ( j < ...

AOJ, 数え上げ, 数学

問題方針

各桁の和の最大値は最大でも \( 72 \) なので、\( y \) を決め打ちして考えます。条件を満たす \( y \) について、\( x \) の桁和が \( y \) になるかどうかを調べます。

コード

AOJ, ビット全探索, 探索, 数え上げ

問題方針

参加するメンバーの組み合わせは \( 2^{N} – 1\) 通りあるので、ビット全探索を行います。周期が同じメンバーが増えても必ず同じ公演に参加することになるので、参加するメンバーの組み合わせが増えることはありま ...

AtCoder, 数え上げ, 文字列

問題方針

条件を満たす整数列を作ります。まず初めに、\( a_i = 0 \ ( 1 \leq i \leq N) \) とします。次に、文字列の先頭から末尾に向かって、\( S_i = \) ‘<‘ なら ...

AtCoder, 数え上げ

問題方針転倒数

転倒数を求めるアルゴリズムはマージソートを利用したものや BIT を使ったものがありますが、今回はデータ数が小さいので、\( O(N^2)\) の計算量が間に合います。\( A \) の転倒数を \( s_1 \) とし ...

AtCoder, 数え上げ

問題方針

各文字列を構成する文字の種類と数が同じであれば、同じ文字列を構成できるので、文字列の文字を整列させマップなどでカウントすれば良いです。構成要素が同じ文字列の個数を \( v \) とすると、アナグラムの個数は、

\ ...

Codeforces, 数え上げ

問題方針題意

\( 1 \) から \( n \) までの数字があり、\( k \) 個ごとに仕切りがあります。初期の配置では、仕切り \( i \) には、\( ik \) から \((i + 1)k\) までの数字が存在しています。 ...

AOJ, 全探索, 探索, 数え上げ

問題方針縦方向と横方向に分けて考える

休憩スペースは南北方向または東西方向に置くことが可能なので、縦方向と横方向に分けて考えます。

連続する空マスを数える

ある方向に向かって連続する空マスを数え、その値が \( D \) より ...

AtCoder, 数え上げ

問題方針与えられたグラフにおいて、\( 2 \) 回の移動で距離が \( 2540 \) となるパスの合計を求めたいので、ある頂点に接続している辺の距離の本数を数えます。

例えば、\(G \) を頂点 \( i \) から延び ...