[yukicoder] No. 0944 煎っぞ!
コーヒー豆のおいしさ度の候補は、累積和の数だけあるので、\( N \) 通りあることがわかります。ここで、累積和を
\
とします。おいしさ度を \( s_i \) と固定したとき、条件を満たすような分割 ...
[AtCoder] ABC 148 E – Double Factorial
\( N \) が奇数の場合、\( f(N) \) は奇数となるので、答えは \( 0 \) となります。ここで、\( N ! \) の末尾に続く \( 0 \) の個数を考えます。
これは、\( N! \) の ...
[AtCoder] ABC 148 D – Brick Break
どのようにブロックを叩いても不可能な数列は、数列の要素に \( 1 \) が無い場合です。それ以外の数列は、少なくとも \( N – 1 \) 個のレンガを壊すことで条件を満たします。最終的に条件を満たす数列は、\ ...
[AtCoder] ABC 148 C – Snack
必要なお菓子の数を \( n \) とすると、\( n \) は \( A\) と \( B \) で割り切ることができる数なので、\( A, B \) の最小公倍数が答えになります。
コード#include <b ...
[AtCoder] 第二回全国統一プログラミング王決定戦本戦 B – NIKKEI String
\( n = |S| \) とします。\( S_3 , \ S_4 \) を固定して考えます。\( S \) の \( i \) 文字目から \( j \) 文字目までの部分文字列を \( S(i, j) \) \( (0 \ ...
[AtCoder] 第二回全国統一プログラミング王決定戦本戦 A – Count Triplets
\( A_i < A_j \) を満たす \( (i, j) \ ( i < j ) \) の数を \( l_j \) とし、\( A_j < A_k \) を満たす \( (j, k) \ ( j < ...
[AtCoder] ABC 146 D – Coloring Edges on Tree
必要な色の数は、頂点の最大次数となるので、任意の頂点から幅優先探索を行い、色を振り分けていきます。辺の色を順番に出力する必要があるので、マップを使って管理します。また、色を分けるときに使用できない色を管理するためにセットを使い ...
[AOJ] No. 0386 ワープ装置
\( d(i) \) を文字 \( i \) の出口への行き方の数として、動的計画法を行います。初期値は \( d(s_0) = 1\) とします。更新式は、\( d(s_i) \leftarrow d(s_i) + d(t_ ...
[AOJ] No. 0385 ボゾソート
数列の要素を交換するたびに全ての要素が昇順に調べるのは効率が悪いので別の方法を考えます。昇順に整列させたときの数列と元の数列の要素が異なるものの数を \( t \) とします。交換を行う前に、\( t = 0 \) であれば、 ...
[AOJ] No. 0384 デュードニー数
各桁の和の最大値は最大でも \( 72 \) なので、\( y \) を決め打ちして考えます。条件を満たす \( y \) について、\( x \) の桁和が \( y \) になるかどうかを調べます。
コード#incl ...