AtCoder, 累積和

問題方針

二次元の累積和を利用して解きます。二次元の累積和を利用することで長方形の領域で表される土地の地価の和を \( O(1) \) で計算することができます。よって、全てのマスを全探索して求めます。計算量は、\( O(H^2W^2) ...

AtCoder, 二分探索, 探索

問題方針

\( f(N) = AN + Bd(N)\) とすると、\( f(N) \) は増加関数なので、二分探索を行います。整数の桁数は、対数を使うよりも、数値を文字列に変換してから長さを得る方が良いと思います。

コード

AtCoder, 数学

問題方針

マス \( i, j \) から \( (i + 1, j + 2) \) に移動するような動き方の回数を \( a \), マス \( i, j \) から \( (i + 2, j + 1) \) に移動するような動き方の ...

AtCoder, 探索, 深さ優先探索

問題方針

順列を生成して距離を計算します。

コード

 

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

問題方針

座標間の距離が与えられるので、相対的な位置が分かります。したがって、ある座標の値を \( x_i = 0 \) として、\( M \) 個の情報に誤りがあるかどうかを調べます。

グラフ

各座標をグラフの頂点として、\ ...

AtCoder, 数え上げ, 文字列

問題方針

条件を満たす整数列を作ります。まず初めに、\( a_i = 0 \ ( 1 \leq i \leq N) \) とします。次に、文字列の先頭から末尾に向かって、\( S_i = \) ‘<‘ なら ...

AtCoder, グラフ理論, 数学

問題方針

一見難しそうに見えますが、\( 300 \) 点の問題なので解法は簡単であることが予想できます。

実現不可能な整数列頂点 \( 1 \) からの距離について

頂点 \( 1 \) からの距離が与えられるので、 ...

AtCoder, 動的計画法

問題方針

商品の重さの最大値が \( 10^9\) なので、添え字で重さを管理して考えるのはメモリ的にきついので、別の方法を考えます。価値を添え字で管理することを考えます。\( d(i, j)\) を商品 \( i \) まで調べたとき ...

AtCoder, 動的計画法

問題方針

いわゆるナップザック問題ですね。

\( d(i, j) \) を品物 \( i \) まで調べたとき、重さの総和が \( j \) であるときの価値の総和の最大値とします。初期値は、\( d(0, 0) = 0 \ ...

AtCoder, 動的計画法

問題方針動的計画法

前日とは同じ行動を取ることができないことに注意して考えます。\( i \) 日目に行動 \( j = \{A, B, C\}\) を取った時の最大値を \( d(i, j) \) とします。このときの遷移式は、