AtCoder, Union Find, グラフ理論

問題方針与えられた情報から番号を当てられるか?

\( A_{X_i} + A_{Y_i} + Z_{i}\) が偶数という情報から番号を当てられることができるかを考えます。

例えば、\( A_1 + A_2 + 3 \mod ...

AtCoder, Union Find, グラフ理論, 探索, 深さ優先探索

問題方針各マスに番号を割り振る

\( H \) 行 \( W \) 列のマスを持つグリッドにおける \( i \) 行 \( j \) 列目のマスの番号を \( i \times W + j \) とします。このようにマスの番号を割り当 ...

AtCoder, グラフ理論, ダイクストラ法

問題方針最小共通祖先

根から 頂点 \( i \) までの距離を \(d_i \) とすると、頂点 \( u \) と 頂点 \( v \) の距離は、\( u \) と \( v \) の最小共通祖先までの距離 \( lca(u, v ...

AtCoder, 数学

問題方針

初期値においてどれだけ連続して表が出る必要があるかを考えます。

サイコロを振って出た目を \( i \) とします。次に、コインが連続で表が出る回数を \( t \) とすると、

\

を満た ...

AtCoder, 数学

問題方針答えの候補を \( a \) とすると、\( 0 \leq a \leq M – 1 \) であることが分かります。バスの台数を \( x \)、グループ数を \( y \) とすると、\を満たします。\( g = gc ...

AtCoder, 数学

問題方針

場合分けを行います。

\( B \gt A\) のときこのとき、最初の昼にジュースを買うことができません。\( B \gt D \) かつ \( B \leq A\)のとき

このとき、供給量が消費量よりも小さいので、 ...

AOJ, データ構造

問題方針

配列を使って要素を削除していく方法は TLE となる可能性があるので、リング配列のポインタを考えます。

配列 \(prev \) の \( prev \) を 番号 \( i \) の後ろの番号、配列 \(next ...

CSA, 数学

問題

長さが \( N \) のリング状の配列 \( a \) の長さが \( K \) の部分配列の和がすべて等しくなるような操作回数の最小値を求めます。

方針部分配列の和円形の配列 \( a \) が与えられたとき、サイズ \ ...

AOJ, 幅優先探索, 探索

問題方針幅優先探索

チーズは硬さ \( 1 \) から \( N \) まで順番にとる必要があるので、\( 1 \) から \( 2 \) までの最短距離を計算し、次に \( 2 \) から \( 3 \) までの最短距離を計算するよう ...

AtCoder, 数学, 累積和

問題方針最大公約数の性質

関数 \( f(\cdot) \) を最大公約数を求める関数とします。ここで、\(f(x, y)\) は \( x, y \) の最大公約数とし、\( f(x, y, z) \) は \( x, y, z\) ...