Pythonで毎日AtCoder #24

はじめに

前回
今回はこれの解ける問題を解いていきます。

#24

ABC045-C
1110diff

考えたこと
初めてbit全探索という手法を知ったので使っていきます。文字の間に記号を入れるかを全探索します。

s = input()

ans = 0
n = len(s) - 1 #間は文字数よりも1少ない
for i in range(2 ** n):
    op = [''] * n
    for j in range(n):
        if ((i >> j) & 1):
            op[n - j - 1] = '+'
    formula = ''
    for p_n, p_o in zip(s,op+['']):
        formula += (p_n+p_o)
    ans += eval(formula)

print(ans)

ABC079-C
302diff

考えたこと
前の問題と違うのは記号が二つになったことですが、ほとんど同じです。
evalは文字の式を計算してintを返してくれます。

abcd = input()
n = len(abcd) - 1
for i in range(2 ** n):
    op = ['-'] * n
    for j in range(n):
        if ((i >> j) & 1):
            op[n - j - 1] = '+'
    formula = ''
    for p_n, p_o in zip(abcd, op + ['']):
        formula += (p_n + p_o)
    if eval(formula) == 7:
        print(formula + '=7')
        break

ARC029
465diff

考えたこと
どっちの肉焼き機を使うかでbit全探索。あとは、最小値を更新していくだけ。

n = int(input())
t = [int(input()) for _ in range(n)]
ans = 10**9
for i in range(2 ** n):
    niku = ['Left'] * n
    for j in range(n):
        if ((i >> j) & 1):
            niku[n - j - 1] = 'Right'
    wait_time_left = 0
    wait_time_rignt = 0
    for k in range(n):
        if niku[k] == 'Left':
            wait_time_left += t[k]
        if niku[k] == 'Right':
            wait_time_rignt += t[k]
    wait_time = max(wait_time_left,wait_time_rignt)
    ans = min(ans,wait_time)
print(ans)

できなかった問題

ABC104-C
中途半端に解く問題の処理を書けなかった。

d, g = map(int,input().split())
pc = [list(map(int,input().split())) for _ in range(d)]
n = len(pc)
ans = 10**9
for i in range(2 ** n):
    cost = 0
    score = 0
    check = [False] * n

    for j in range(n):
        if ((i >> j) & 1):
            check[n - j - 1] = True

    for k in range(n):
        if check[k]:
            for l in range(pc[k][0]):
                cost += 1
                score += 100 * (k+1)
                if l == pc[k][0]-1:
                    score += pc[k][1]
                if score >= g:
                    ans = min(ans,cost)
print(ans)

ABC002-C
議員12人を派閥に含むか否かを考えたときに、知り合い同士を確認するコード書くすることができなかった。

まとめ

難しい。新しいことを学習するのは楽しいけど、解けないと意味がないので定着するように過去問を解く。では、また