[AtCoder] 第二回全国統一プログラミング王決定戦予選 B – Counting of Trees
一見難しそうに見えますが、\( 300 \) 点の問題なので解法は簡単であることが予想できます。
実現不可能な整数列頂点 \( 1 \) からの距離について頂点 \( 1 \) からの距離が与えられるので、 ...
[AOJ] No. 0644 水ようかん (Mizuyokan)
水ようかんを切り分けた時の長さの値は、切る箇所を任意の \( 2 \) 点選ぶことを考えると、最大でも
\
あることが分かります。したがって、最小値を固定したときの、最大値を変数とみて、最大 ...
[AOJ] No. 0611 シルクロード (Silk Road)
都市 \( i \ (1 \leq i \leq N)\) に到達して滞在する可能性のある日 \( j \) の範囲は、\( i \leq j \leq M – N + i\) となります。ここで、次の配列を考えま ...
[AtCoder] Educational DP Contest E – Knapsack 2
商品の重さの最大値が \( 10^9\) なので、添え字で重さを管理して考えるのはメモリ的にきついので、別の方法を考えます。価値を添え字で管理することを考えます。\( d(i, j)\) を商品 \( i \) まで調べたとき ...
[AtCoder] Educational DP Contest D – Knapsack 1
いわゆるナップザック問題ですね。
\( d(i, j) \) を品物 \( i \) まで調べたとき、重さの総和が \( j \) であるときの価値の総和の最大値とします。初期値は、\( d(0, 0) = 0 \ ...
[AtCoder] Educational DP Contest C – Vacation
前日とは同じ行動を取ることができないことに注意して考えます。\( i \) 日目に行動 \( j = \{A, B, C\}\) を取った時の最大値を \( d(i, j) \) とします。このときの遷移式は、
[AtCoder] ABC 144 E – Gluttony
証明ができなかったので、予想を立てて考えます。おそらく、修行前の最適なコストは、次のようになります。配列 \( A, F\) を
\
\
と整列させます。このときのコストを ...
[AtCoder] ABC 144 D – Water Bottle
水筒を傾けた時に入る水の最大値を考えます。傾けた時の角度を \( \theta \) とします。このときの水筒の容量を \( V (\theta)\) とします。そして、\( V (\theta) = x \) を満たす \( ...
[AtCoder] ABC 144 C – Walk on Multiplication Table
C – Walk on Multiplication Table
方針\( N = x \times y \) を満たす正の整数 \( x, y\ (x \leq y) \) がマスの候補となるので、\( ...
[AtCoder] ABC 143 D – Triangles
全てのパターンについて調べると計算量が \( O(N^3) \) となるので間に合いません。なので、\( 2 \) 本を固定して考えます。
二分探索\( a \leq b \leq c \) として、\( b, c ...