https://www.hackerrank.com/contests/joi2018/challenges/apples-5 前提知識 動的計画法 解説 最大値で個数制限があり、10^3制約ということなので、dp[10^3][10^3]っぽさがある。 ここから考えると、 dp[i][m] := i番目までのりんごをm箱に詰めたときの美し…

https://www.hackerrank.com/contests/joi2018/challenges/blocks-3 前提知識 動的計画法 解説 地点2～Nにある積み木は地点1に置くか、置かないかで考えるだけで良い。 他の地点に一旦移動させて、一気に地点1に移動するような行為をしてもコストは変わらな…

https://www.hackerrank.com/contests/joi2018/challenges/challenge-1716 解説 (x,y)から(a,b)への移動の最短ルートを考えてみよう。x=0のとき (0,0)からの移動は中央から一直線で行けるので、aだけかかる a=0のとき (0,0)への移動は中央へ一直線で行けるの…

https://www.hackerrank.com/contests/joi2018/challenges/rage-of-azerbaijan-citizens 解説 Xの城がYの城を攻撃するのも、Yの城がXの城を攻撃するのも変わらないので、 D=2のときは、DkとPkを入れ替えて、全てD=1のようにして処理する。 あとは、ルールに…

https://www.hackerrank.com/contests/joi2018/challenges/joi-joi-fall-in-love-1 解法 ゲームの手順を分数を使って、誤差なく計算する。 分子をup, 分母をdwnとして、計算していく。 x足す up += x*dwn x引く up -= x*dwn x/y倍する up *= x dwn *= y xで…

この記事は Competitive Programming (2) Advent Calendar 2018 の 8 日目の記事です。 前日はたたもさんの「コマンドラインツールatcoder-cliを公開しました」です。あまり見る機会は多くないけど、典型化できそうなニッチなネタを書いていきます。 対象は…