yukicoder, 二分探索, 探索, 累積和

問題方針

コーヒー豆のおいしさ度の候補は、累積和の数だけあるので、\( N \) 通りあることがわかります。ここで、累積和を

\

とします。おいしさ度を \( s_i \) と固定したとき、条件を満たすような分割 ...

AtCoder, 数学

問題方針

\( N \) が奇数の場合、\( f(N) \) は奇数となるので、答えは \( 0 \) となります。ここで、\( N ! \) の末尾に続く \( 0 \) の個数を考えます。

これは、\( N! \) の ...

AtCoder, 貪欲法

問題方針

どのようにブロックを叩いても不可能な数列は、数列の要素に \( 1 \) が無い場合です。それ以外の数列は、少なくとも \( N – 1 \) 個のレンガを壊すことで条件を満たします。最終的に条件を満たす数列は、\ ...

AtCoder, 数学

問題方針

必要なお菓子の数を \( n \) とすると、\( n \) は \( A\) と \( B \) で割り切ることができる数なので、\( A, B \) の最小公倍数が答えになります。

コード

 

AtCoder, 文字列

問題方針

\( n = |S| \) とします。\( S_3 , \ S_4 \) を固定して考えます。\( S \) の \( i \) 文字目から \( j \) 文字目までの部分文字列を \( S(i, j) \) \( (0 \ ...

AtCoder, 数え上げ

問題方針

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

AtCoder, グラフ理論, 幅優先探索, 探索

問題方針

必要な色の数は、頂点の最大次数となるので、任意の頂点から幅優先探索を行い、色を振り分けていきます。辺の色を順番に出力する必要があるので、マップを使って管理します。また、色を分けるときに使用できない色を管理するためにセットを使い ...

AOJ, 動的計画法

問題方針

\( d(i) \) を文字 \( i \) の出口への行き方の数として、動的計画法を行います。初期値は \( d(s_0) = 1\) とします。更新式は、\( d(s_i) \leftarrow d(s_i) + d(t_ ...

AOJ, 整列

問題方針

数列の要素を交換するたびに全ての要素が昇順に調べるのは効率が悪いので別の方法を考えます。昇順に整列させたときの数列と元の数列の要素が異なるものの数を \( t \) とします。交換を行う前に、\( t = 0 \) であれば、 ...

AOJ, 数え上げ, 数学

問題方針

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

コード