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

問題方針

各生徒をノードに見立てて、隣接リストを構築します。生徒 \( i \) が所属している部活動を \( g_i \) とし、所属が未確定のときを \( g_i = 0 \) とします。生徒 \( a, b \) が同じ部活動に所 ...

AOJ, 実装

問題方針

コースターの画像のピクセルの添え字は、\( i \) 行 \( j \) 列を表していて、\( 0 \leq i \leq N – 1 \wedge 0 \leq j \leq N – 1 \) として ...

AOJ, 動的計画法, 文字列

問題方針

動的計画法を行います。\( d(i, j) \) を \( t \) の \( j \) 番目までの部分文字列において、\( b \) の \( j \) 番目までの部分文字列の出現回数とします。初期値は、\( d(i, 0) ...

AOJ, 全探索, 探索

問題方針

両端のパンケーキは \( 1 \) 枚だけ裏返すことができることに着目します。左端のパンケーキは単独で裏返す回数を \( k \) とすると、最小値を達成するためには、\( 0 \leq k \leq p_1 \) であること ...

AOJ, 整列, 貪欲法

問題方針

\( i \) 番目のタクシーは、\( i + 1 \) 番目以降のタクシー乗り場に行くことができるので、\( N \) 番目のタクシーから考えていきます。\( N \) 番目のタクシーは、\( s_N \) の最大値を取るこ ...

yukicoder, 数学

問題方針

関数 \( f(x) \) を持ち帰りと店内の料金の差とすると、次のように計算できます。

\

これは、\( \left \lfloor \dfrac{100 + Q}{100}x \right \rfl ...

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

問題方針

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

\

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

AtCoder, 数学

問題方針

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

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

AtCoder, 貪欲法

問題方針

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

AtCoder, 数学

問題方針

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

コード