[AOJ] No. 0594 超都観光 (Super Metropolis)
東南方向の斜めの道が無ければ、\( 2 \) 点間の最短距離は、
\
となります。
南西方向観光スポットが南西方向にある場合、東南方向の道を通る必要がないので、最短距離は、
\
[AtCoder] AGC 040 A – ><
条件を満たす整数列を作ります。まず初めに、\( a_i = 0 \ ( 1 \leq i \leq N) \) とします。次に、文字列の先頭から末尾に向かって、\( S_i = \) ‘<‘ なら ...
[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 \) を満たす \( ...