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を出力。問題文ちゃんと読もうね
# 入力
X = int(input())

if X < 40: # 初級の時
    print(40 - X)
    
elif X < 70: # 中級の時
    print(70 - X)

elif X < 90: # 上級の時
    print(90 - X)

else: # エキスパートの時
    print('expert')

B - Maritozzo

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

番号順に呼び出す

  • Sを辞書として持って、Tのi文字目順にSを呼び出す
  • indexに注意しようね
# before
S1 = input()
S2 = input()
S3 = input()
T = input()
 
str_L = [S1,S2,S3]
 
ans = ''
 
L = list(T)
 
for i in L:
    tmp = int(i) - 1 
    ans += str_L[tmp]
 
print(ans)
# after
# 入力
S_l = [input() for i in range(3)] # リスト内包表記だとお洒落ですね
T_l = list(input()) # ここでリスト化も済ませとくと良いね

ans = '' # ここに文字列足していくつもり

for i in T_l:
    ans += S_l[int(i)-1] # 0-indexなので、-1する必要有るよね

print(ans)

C - Neo-lexicographic Ordering

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

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

  • Xから変換用辞書と、逆変換用辞書を用意する
  • S1,S2,,SNS_1,S_2,\dots,S_Nを、変換して順に保存していく
  • このタイミングでソート
  • ソートしたものを、順に逆変換しながら出力していく
# before
from collections import defaultdict 
X = input()
N = int(input())
 
val = list(range(1,27))
trans_d = dict(zip(list(X),val))
reverse_d = dict() 
for k,v in trans_d.items():
    reverse_d[v] = k
L = []
num_L = []
 
for i in range(N):
    tmp = input()
    tmp_l = []
    for j in list(tmp):
        tmp_l.append(trans_d[j])
    num_L.append(tmp_l)
 
num_L.sort()
 
for i in num_L:
    ans = ''
    for j in i:
        ans += reverse_d[j]
    print(ans)
# after

# 入力
X_l = list(input())  # 最初から配列化
N = int(input())

# 辞書用意
val = list(range(1, 27))
trans_d = dict(zip(X_l, val))  # 変換用辞書
reversed_d = dict(zip(val, X_l))  # 逆変換用辞書

# 名前を変換しながら保存していく
S_l = []
for i in range(N):
    s = input()
    num_l = []
    for j in list(s):# 1文字ずつ変換しながら保存
        num_l.append(trans_d[j])
    S_l.append(num_l)

S_l.sort() # ここでソート

# ソート後のリストを、逆変換しながら出力していく
for i in S_l:
    name_s = ''
    for j in i:
        name_s += reversed_d[j]
    print(name_s)

{'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の意味となりますね
N = int(input())
X, Y = map(int, input().split())
 
A = [None]*N
B = [None]*N
 
for i in range(N):
    a, b = map(int, input().split())
    A[i] = min(a, X)
    B[i] = min(b, Y)
 
inf = 500
 
dp = [[[inf] * (Y+1) for _ in range(X+1)] for _ in range(N+1)]
dp[0][0][0] = 0
 
for i in range(N):
    for x in range(X+1):
        for y in range(Y+1):
 
            if dp[i][x][y] == 500:
                continue
 
            # i+1個目のお弁当を買う時
            dp[i+1][min(X, x+A[i])][min(Y, y+B[i])] = min(
                dp[i+1][min(X, x+A[i])][min(Y, y+B[i])],
                dp[i][x][y]+1
            )
 
            # i+1個目のお弁当を買わない時
            dp[i+1][x][y] = min(
                dp[i+1][x][y],
                dp[i][x][y]
            )
 
ans = dp[N][X][Y]
if ans == inf:
    ans = -1
print(ans)

Discussion

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