2

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

6 min read

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から変換用辞書と、逆変換用辞書を用意する
  • S1,S2,,SNS_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,j,k)はそれぞれ、何を表すのか?
    • iiii個目のお弁当までチェックしましたよ
    • 言い換えると、次チェックするのはi+1 i + 1個目のお弁当について考えますよ
      • 決して「ii個のお弁当を購入しましたよ」ではない点に注意
      • dpは、「1,4,5,7個目のお弁当を購入しました」という過程は残らない
      • 多分ここ(途中経過)を無視して最小数を考えるから、bit全探索よりも早いんだと思う
    • jjjj個のたこ焼きを食べましたよ
      • ii個目のお弁当箱を確認(買う/買わないの選択)をして、jj個のたこ焼きを食べた、の意
    • kkkk個のたこ焼きを食べましたよ
      • ii個目のお弁当箱を確認(買う/買わないの選択)をして、kk個のたい焼きを食べた、の意

2:上限について

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

3:dpの中身について

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



Discussion

コメントにはログインが必要です。