AtCoder に関するカテゴリーです。

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) \) とします。このときの遷移式は、

AtCoder, 二分探索, 探索

問題方針最適な食べ物の配置

証明ができなかったので、予想を立てて考えます。おそらく、修行前の最適なコストは、次のようになります。配列 \( A, F\) を

\

\

と整列させます。このときのコストを ...

AtCoder, 数学

問題方針

水筒を傾けた時に入る水の最大値を考えます。傾けた時の角度を \( \theta \) とします。このときの水筒の容量を \( V (\theta)\) とします。そして、\( V (\theta) = x \) を満たす \( ...

AtCoder, 数学

問題

C – Walk on Multiplication Table

方針

\( N = x \times y \) を満たす正の整数 \( x, y\  (x \leq y) \) がマスの候補となるので、\( ...

AtCoder, 二分探索, 探索

問題方針

全てのパターンについて調べると計算量が \( O(N^3) \) となるので間に合いません。なので、\( 2 \) 本を固定して考えます。

二分探索

\( a \leq b \leq c \) として、\( b, c ...

AtCoder, 文字列

問題方針

文字列を先頭から調べていきます。連続する文字を一つとしてカウントするので、\( c = S_0\) として、\( c \) と異なる文字が出現したときカウンタを回し、文字を更新します。

コード