train ticket と all green
今日の競プロ。
train ticket は、与えられた4桁の数字の各桁を順番そのままに、引くか足すかして、=7ができるか問う問題。簡単な全探索でeval使って瞬殺。
def main(): abcd = list(input()) flag = False for op1 in ['+', '-']: for op2 in ['+', '-']: for op3 in ['+', '-']: ans = abcd[0]+op1+abcd[1]+op2+abcd[2]+op3+abcd[3] if eval(ans) == 7: flag = True print(ans+'=7') break if flag: break if flag: break if __name__ == '__main__': main()
問題は all green の方だったんだけど、正直なぞい。 一応、解が、多くなかったから、移植してメモ。
def main(): D, G = [int(i) for i in input().split()] p = [] c = [] for i in range(D): pp, cc = [int(i) for i in input().split()] p.append(pp); c.append(cc) ans = 1e9 for mask in range(1<<D): s = 0; num = 0; rest_max = -1 for i in range(D): # どのビットが立っているか確認する if mask >> i & 1: # i 番目の問題を全完した時の点数を追加する s += 100 * (i+1) * p[i] + c[i] num += p[i] else: # ビットが立っていない点数が一番高い問題のメモ # 足りなかったらここから解いて点数を追加する # 残ったやつ 1 つだけを見ればばいい # なぜなら、bit全探索で、他のパターンは自動的に出るから rest_max = i if s < G: # rest_max 番目の点数をあらかじめ計算しておく s1 = 100 * (rest_max+1) # 目標 - 今まで解いた問題の得点 + rest_max 番目の問題の得点 - 1 need = (G - s + s1 - 1) // s1 # max になってはいけない if need >= p[rest_max]: continue num += need ans = min(ans, num) print(ans) if __name__ == '__main__': main()
如何せん 27 行目。ここは、(G-s)//s1でやると、落ちる意味わからん。教えてエロい人。 それは、置いといて、ビット全探索からの、問いてない点数が高い方から探索っていうのが、できなかった。 解説動画のコメントで、これ、300?っていうのがあったけど、全く同感だった。きついわ。