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\)のとき

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

AtCoder, 数学, 累積和

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

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

AtCoder, グラフ理論, 二部グラフ

問題方針二部マッチング問題

基本的には、 GRL_7_A Bipartite Matchingと同じようにして解くことができます。

頂点は与えられますが、辺がどのようになっているかは自分で実装しなければいけません。赤い点のラ ...

AtCoder, 数学

問題方針連立方程式

問題文より、次の連立方程式が得られます。

\

\この連立方程式は、\( a_i + b_j = c_ {i, j}\) から得られます。この連立方程式が解を持つための条件は、係数行列 \( A \) ...

AtCoder, 動的計画法

問題方針動的計画法

\( dp \) をマス \( (i, j)\) におけるアメの所持数の最大値とします。マスの移動は右か下に行くかだけなので、下に行くことができるのは \( 1 \) 回だけとなります。したがって、

\ ...

AtCoder, ビット全探索, 探索

問題方針ビット全探索

ある曜日のどの時間帯に店を営業するかどうかで利益が変わり、\( 5 \) つの曜日と午前・午後を考えれば良いので、\( 2^{10} \) 通りのビット全探索を行えば良いことが分かります。

店の営業情報は \ ...