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?っていうのがあったけど、全く同感だった。きついわ。