結果

問題 No.10 ＋か×か
ユーザー yuki2006yuki2006
提出日時 2014-10-11 03:51:56
言語 Python2
(2.7.18)
結果
WA  
実行時間 -
コード長 1,552 bytes
コンパイル時間 499 ms
コンパイル使用メモリ 6,728 KB
実行使用メモリ 8,968 KB
最終ジャッジ日時 2023-08-28 20:41:41
合計ジャッジ時間 4,638 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 11 ms
5,952 KB
testcase_01 AC 10 ms
5,932 KB
testcase_02 AC 10 ms
6,020 KB
testcase_03 AC 1,309 ms
8,964 KB
testcase_04 AC 132 ms
6,512 KB
testcase_05 AC 10 ms
5,828 KB
testcase_06 WA -
testcase_07 AC 453 ms
7,840 KB
testcase_08 AC 114 ms
6,864 KB
testcase_09 WA -
testcase_10 AC 11 ms
5,956 KB
testcase_11 AC 11 ms
5,876 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

# -*- coding: utf-8 -*-

def solve(N, total, A):
    MAX = (1 << N + 2)
    dp = [MAX] * (total + 1)
    # 結果をビットで保存するDP
    dp[A[0]] = 0

    for i, a in enumerate(A[1:]):
        for v in xrange(total, 0, -1):
            if dp[v] == MAX:
                continue

            current = dp[v]
            # 1倍の時に上書きされてしまう対策
            mul_change = False
            if v * a <= total:
                if i == 0:
                    dp[v * a] = (1 << ((N - 2) - i))
                    mul_change = True
                else:
                    if a == 1:
                        mul_change = True
                        dp[v * a] = current | (1 << ((N - 2) - i))
                    else:
                        dp[v * a] = min(dp[v * a], current | (1 << ((N - 2) - i)))

            if v + a <= total:
                if i == 0:
                    dp[v + a] = 0
                else:
                    dp[v + a] = min(dp[v + a], current)

            if not mul_change:
                # 1倍の時以外はMAXにする。
                # 1倍の時にすると値が消えてしまう。
                dp[v] = MAX

    ans_bit = dp[total]
    if ans_bit == MAX:
        return None
    ans = ""

    while N > 1:
        ans = ("*" if ans_bit & 1 else "+") + ans
        ans_bit >>= 1
        N -= 1
    return ans



N = int(raw_input())
total = int(raw_input())
A = map(int, raw_input().split(" "))

print solve(N, total, A)
0