ABC219 茶色コーダーが解けた所まで＋あと1問

AtCoder Beginner Contest 219

https://atcoder.jp/contests/abc219

ABC219の問題を、本番で自分が解けた所＋1問の解説です。

なんとかABC3完で茶色維持＋レート微増。
年内水色が目標です。止まるんじゃねぇぞ…

A - AtCoder Quiz 2

https://atcoder.jp/contests/abc219/tasks/abc219_a

if文

• X点の値によって出力を変える
• 以上以下、超える、未満に注意しようね
• エキスパートの時は点数じゃなくてexpertを出力。問題文ちゃんと読もうね

B - Maritozzo

https://atcoder.jp/contests/abc219/tasks/abc219_b

番号順に呼び出す

• Sを辞書として持って、Tのi文字目順にSを呼び出す
• indexに注意しようね

C - Neo-lexicographic Ordering

https://atcoder.jp/contests/abc219/tasks/abc219_c

一旦数字に変換して、ソートして、その後文字列に戻す

• Xから変換用辞書と、逆変換用辞書を用意する
• $S_1,S_2,\dots,S_N$を、変換して順に保存していく
• このタイミングでソート
• ソートしたものを、順に逆変換しながら出力していく

{'b': 1, 'a': 2, 'c': 3, 'd': 4, 'e': 5, 'f': 6, 'g': 7, 'h': 8, 'i': 9, 'j': 10, 'k': 11, 'l': 12, 'm': 13, 'n': 14, 'o': 15, 'p': 16, 'q': 17, 'r': 18, 's': 19, 't': 20, 'u': 21, 'v': 22, 'w': 23, 'x': 24, 'z': 25, 'y': 26}

D - Strange Lunchbox

https://atcoder.jp/contests/abc219/tasks/abc219_d

多次元DP

• 制限時間内にDPであるまでは察したけども、多次元状態を実装する力がなかった.

• DPもうちょっと練習しないと…

• 結局ナップサック問題、の応用、のはず…

• 要素が1つの問題から考えると良いかもしれない

• 3次元DP

1:状態について

• 状態$(i,j,k)$はそれぞれ、何を表すのか？
  • $i$：$i$個目のお弁当までチェックしましたよ
  • 言い換えると、次チェックするのは$i + 1$個目のお弁当について考えますよ
    • 決して「$i$個のお弁当を購入しましたよ」ではない点に注意
    • dpは、「1,4,5,7個目のお弁当を購入しました」という過程は残らない
    • 多分ここ（途中経過）を無視して最小数を考えるから、bit全探索よりも早いんだと思う
  • $j$ ： $j$個のたこ焼きを食べましたよ
    • $i$個目のお弁当箱を確認（買う/買わないの選択）をして、$j$個のたこ焼きを食べた、の意
  • $k$ ： $k$個のたこ焼きを食べましたよ
    • $i$個目のお弁当箱を確認（買う/買わないの選択）をして、$k$個のたい焼きを食べた、の意

2:上限について

• なんで青木君に上げるのさ？？？？？
  • 高橋君はたこ焼きを$X$個を超えて食べる時、$X + 10$個食べても$X +10000$個食べても満足度は変わらないんですよね。
  • つまり、いくつかのお弁当を買って、合計で$X$個以上のたこ焼きが入っていた場合、$X$食べたものとしてそれ以上は青木君にあげようね、という話
    • だって、$X$個以上食べたとしても何個食べたなんて知らないよ、記録する必要がないもの
    • 必要なのは高橋君が「$X$個食べました、満足しました」かどうか、っていう話だからね
  • この「上限について」が、解説内$dp[i][min(j+A_i,X)][Y]$の$min(j+A_i,X)$になる。
    • $X$を最大値とする。$X$以上は$X$とみなす
  • たい焼きについても同上

3:dpの中身について

• 結局dp配列内部には何が収められているの？
  • 状態$(i,j,k)$を添え字とした時、($dp [i][j][k]$)その状態になるために必要なお弁当の最小個数が入ってる
    • 既にその状態に遷移したことがあるなら、「過去その状態に遷移した時のお弁当の最小個数」と「今回その状態に遷移する時に購入したお弁当の個数」を比較して、より小さい方（最短経路）を格納する
    • これが添え字外、右辺の$min$の意味となりますね