・6 min read
ABC219 茶色コーダーが解けた所まで＋あと1問
AtCoder Beginner Contest 219
ABC219の問題を、本番で自分が解けた所＋1問の解説です。
なんとかABC3完で茶色維持＋レート微増。
年内水色が目標です。止まるんじゃねぇぞ…
年内水色が目標です。止まるんじゃねぇぞ…
A - AtCoder Quiz 2
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
番号順に呼び出す
- 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
一旦数字に変換して、ソートして、その後文字列に戻す
- Xから変換用辞書と、逆変換用辞書を用意する
- を、変換して順に保存していく
- このタイミングでソート
- ソートしたものを、順に逆変換しながら出力していく
# 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
多次元DP
-
制限時間内にDPであるまでは察したけども、多次元状態を実装する力がなかった.
-
DPもうちょっと練習しないと…
-
結局ナップサック問題、の応用、のはず…
-
要素が1つの問題から考えると良いかもしれない
-
3次元DP
1:状態について
- 状態はそれぞれ、何を表すのか？
- ：個目のお弁当までチェックしましたよ
- 言い換えると、次チェックするのは個目のお弁当について考えますよ
- 決して「個のお弁当を購入しましたよ」ではない点に注意
- dpは、「1,4,5,7個目のお弁当を購入しました」という過程は残らない
- 多分ここ（途中経過）を無視して最小数を考えるから、bit全探索よりも早いんだと思う
- ： 個のたこ焼きを食べましたよ
- 個目のお弁当箱を確認（買う/買わないの選択）をして、個のたこ焼きを食べた、の意
- ： 個のたこ焼きを食べましたよ
- 個目のお弁当箱を確認（買う/買わないの選択）をして、個のたい焼きを食べた、の意
2:上限について
- なんで青木君に上げるのさ？？？？？
- 高橋君はたこ焼きを個を超えて食べる時、個食べても個食べても満足度は変わらないんですよね。
- つまり、いくつかのお弁当を買って、合計で個以上のたこ焼きが入っていた場合、食べたものとしてそれ以上は青木君にあげようね、という話
- だって、個以上食べたとしても何個食べたなんて知らないよ、記録する必要がないもの
- 必要なのは高橋君が「個食べました、満足しました」かどうか、っていう話だからね
- この「上限について」が、解説内のになる。
- を最大値とする。以上はとみなす
- たい焼きについても同上
3:dpの中身について
- 結局dp配列内部には何が収められているの？
- 状態を添え字とした時、()その状態になるために必要なお弁当の最小個数が入ってる
- 既にその状態に遷移したことがあるなら、「過去その状態に遷移した時のお弁当の最小個数」と「今回その状態に遷移する時に購入したお弁当の個数」を比較して、より小さい方（最短経路）を格納する
- これが添え字外、右辺のの意味となりますね
- 状態を添え字とした時、()その状態になるために必要なお弁当の最小個数が入ってる
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)
