AtCoder Beginner Contest ABC415 解法メモ

文中で使用しているのは、PythonライクでAtCoderに最適な言語の1つNimです

ABC415

ABC415A - Unsupported Type

解法

echo if X in A: "Yes" else: "No"
ACコード

ABC415B - Pick Two

解法

(1..S.len).toSeq.filterIt(S[it-1]=='#')
として、#の区画番号を集めた配列$n$をつくり、
for i in 0..<n.len div 2: echo n[i*2],',',n[i*2+1]
とすればよい
ACコード

ABC415C - Mixture

解法

状態$0$（$1$つも薬品が入っていない状態）から状態$2^N-1$（すべての薬品が入っている状態）に到達できるかDFSすればよい
状態$i$からの遷移は、0..<Nにわたって、薬品$j$がまだ入っていない、つまり、(i shr j and 1)==0なら、薬品$j$を加えた状態ni=i+1 shl jに移していけばよい
その際、S[ni]=='0'（状態の$S$の頭に$0$を加えておくとよい）でなくてはならないし、通常のDFS通り、すでに到達した状態ならパスすればよい
ACコード

メモ

問題の意味を読み取るのに一苦労
なぜか未到達チェックを抜いてTLEした挙句、計算量削減の工夫があるのかとさまよってしまった

ABC415D - Get Many Stickers

解法

瓶入りコーラはすぐに空き瓶に換えられるので、単に瓶として扱ってよく、コーラショップでの取引は、$Ai-Bi$本の瓶を渡してシールを$1$枚もらうことと同義である
よって、シールを最大化するには、手持ちの瓶が$Ai$を上回る限り、$Ai-Bi$が最小になる条件で交換を続けていけばよい
ただし、制約上、取引を$1$回ずつシミュレートはできないので、瓶の本数を$Ai-Bi$で割って、同じ条件を一度に適用することを考える
$Ai-Bi$順に条件をソートして、
残りの瓶の本数から$Ai-(Ai-Bi)$を引いたものを$Ai-Bi$で割った回数（残りの瓶が$Ai$ならちょうど$1$回、それより小さかったら$0$回）適用できる（負数にならないよう、$0$との最大値をとっておく）として、順次当てはめていけばよい
適用できる回数を足し合わせた数が、手に入れられる最大のシールの枚数となる
ACコード

メモ

$1$取引ずつ適用しようとしてTLE

ABC415E - Hungry Takahashi

解法

「はじめに持っていた最小のコイン枚数を求める」という問題から、後ろからDPすることを考える
dp[h][w]=そのマスから右下のゴールまで倒れずに行かれるために持っているべき最小のコイン
とすれば、
右下のマスから、
右と下のマスから最小値をとった上で、
dp[h][w]=max(0,dp[h][w]-A[h][w]+P[h+w])
としていけばよい（負数となる、ということは、そのマス以降で倒れることなく結果的にコインが増える、ということなので0としてよい）
dp[0][0]が答えとなる
ACコード

メモ

DPの置き方、後ろからDPすることがわからない

---

反復学習にはmochiがおすすめ
全問入ったdeckはこちら