Problem p03128 (python)

Fixed submission:
# コンテスト中の考えは悪くなかったがN本に固執して貪欲的に考えていた。
# 敗因は動的計画法が思い浮かばず書けなかったこと。
# 提出4298627を参考にした


N, M = map(int, input().split())
A = list(map(int, input().split()))

A.sort(reverse=True)  # 大きい方から探索したいため

# 各数字を作るのに必要なマッチの本数
num = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]

# dpをするための配列を用意
# pd[i]としたときに、i本のマッチで実現できる最大桁数を格納するものとする
# shapeは(N+1,) ∵ i=0~N本のときも考える
dp = [-1 * float("inf")] * (N + 1)

# 各数字を一つずつ使う場合は1桁だとわかりきっているので、初期化ができる
dp[0] = 0
for a in A:
    if num[a] <= N:  # ここは念のための処理、指定されたNがマッチで使う数字より少ないかもしれない。
        dp[num[a]] = 1

# dpのmain
for i in range(1, N + 1):  # dpに格納されているすべての要素をなめていく。
    for a in A:  # i本使うときの最大桁数を決定するためにはaを全探索して下式を最大となるものが取得できればよい
        if i - num[a] >= 0:  # 念の為の条件
            # この式については解説を参照のこと
            dp[i] = max(dp[i], dp[i - num[a]] + 1)

# 探索が終わったので答えを出す。
# 大きい桁にはなるべく大きな数字を割り振る
ans = ""
for i in range(dp[N]):  # dpによって得た桁数について上位桁から決定していく
    for a in A:  # すでに大きい順にソートしたので決定次第break
        # 1つ目の条件は探索中に配列外アクセスをするのを防ぐため。2つ目の条件についても解説を参照のこと
        if N - num[a] > -1 and dp[N - num[a]] == dp[N] - 1:
            ans += str(a)
            N -= num[a]  # マッチの本数から引くのを忘れずにね
            break

print(ans)

Buggy submission (verdict: Runtime Error):
# コンテスト中の考えは悪くなかったがN本に固執して貪欲的に考えていた。
# 敗因は動的計画法が思い浮かばず書けなかったこと。
# 提出4298627を参考にした


N, M = map(int, input().split())
A = list(map(int, input().split()))

A.sort(reverse=True)  # 大きい方から探索したいため

# 各数字を作るのに必要なマッチの本数
num = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]

# dpをするための配列を用意
# pd[i]としたときに、i本のマッチで実現できる最大桁数を格納するものとする
# shapeは(N+1,) ∵ i=0~N本のときも考える
dp = [-1 * float("inf")] * (N + 1)

# 各数字を一つずつ使う場合は1桁だとわかりきっているので、初期化ができる
dp[0] = 0
for a in A:
    if num[a] <= N:  # ここは念のための処理、指定されたNがマッチで使う数字より少ないかもしれない。
        dp[num[a]] = 1

# dpのmain
for i in range(1, N + 1):  # dpに格納されているすべての要素をなめていく。
    for a in A:  # i本使うときの最大桁数を決定するためにはaを全探索して下式を最大となるものが取得できればよい
        if i - num[a] >= 0:  # 念の為の条件
            # この式については解説を参照のこと
            dp[i] = max(dp[i], dp[i - num[a]] + 1)

# 探索が終わったので答えを出す。
# 大きい桁にはなるべく大きな数字を割り振る
ans = ""
for i in range(dp[N]):  # dpによって得た桁数について上位桁から決定していく
    for a in A:  # すでに大きい順にソートしたので決定次第break
        # 1つ目の条件は探索中に配列外アクセスをするのを防ぐため。2つ目の条件についても解説を参照のこと
        if N - num[a]　> -1 and dp[N - num[a]] == dp[N] - 1:
            ans += str(a)
            N -= num[a]  # マッチの本数から引くのを忘れずにね
            break

print(ans)

Buggy submission (verdict: Runtime Error):
# コンテスト中の考えは悪くなかったがN本に固執して貪欲的に考えていた。
# 敗因は動的計画法が思い浮かばず書けなかったこと。
# 提出4298627を参考にした


N, M = map(int, input().split())
A = list(map(int, input().split()))

A.sort(reverse=True)  # 大きい方から探索したいため

# 各数字を作るのに必要なマッチの本数
num = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]

# dpをするための配列を用意
# pd[i]としたときに、i本のマッチで実現できる最大桁数を格納するものとする
# shapeは(N+1,) ∵ i=0~N本のときも考える
dp = [-1 * float("inf")] * (N + 1)

# 各数字を一つずつ使う場合は1桁だとわかりきっているので、初期化ができる
dp[0] = 0
for a in A:
    if num[a] <= N:  # ここは念のための処理、指定されたNがマッチで使う数字より少ないかもしれない。
        dp[num[a]] = 1

# dpのmain
for i in range(1, N + 1):  # dpに格納されているすべての要素をなめていく。
    for a in A:  # i本使うときの最大桁数を決定するためにはaを全探索して下式を最大となるものが取得できればよい
        if i - num[a] >= 0:  # 念の為の条件
            # この式については解説を参照のこと
            dp[i] = max(dp[i], dp[i - num[a]] + 1)

# 探索が終わったので答えを出す。
# 大きい桁にはなるべく大きな数字を割り振る
ans = ""
for i in range(dp[N]):  # dpによって得た桁数について上位桁から決定していく
    for a in A:  # すでに大きい順にソートしたので決定次第break
        if dp[N - num[a]] == dp[N] - 1:  # この条件についても解説を参照のこと
            ans += str(a)
            N -= num[a]  # マッチの本数から引くのを忘れずにね
            break

print(ans)

Buggy submission (verdict: Runtime Error):
# コンテスト中の考えは悪くなかったがN本に固執して貪欲的に考えていた。
# 敗因は動的計画法が思い浮かばず書けなかったこと。
# 提出4298627を参考にした


N, M = map(int, input().split())
A = list(map(int, input().split()))

A.sort(reverse=True)  # 大きい方から探索したいため

# 各数字を作るのに必要なマッチの本数
num = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]

# dpをするための配列を用意
# pd[i]としたときに、i本のマッチで実現できる最大桁数を格納するものとする
# shapeは(N+1,) ∵ i=0~N本のときも考える
dp = [-1 * float("inf")] * (N + 1)

# 各数字を一つずつ使う場合は1桁だとわかりきっているので、初期化ができる
dp[0] = 0
for a in A:
    if num[a] <= N:  # ここは念のための処理、指定されたNがマッチで使う数字より少ないかもしれない。
        dp[num[a]] = 1

# dpのmain
for i in range(1, N + 1):  # dpに格納されているすべての要素をなめていく。
    for a in A:  # i本使うときの最大桁数を決定するためにはaを全探索して下式を最大となるものが取得できればよい
        if i - num[a] >= 0:  # 念の為の条件
            # この式については解説を参照のこと
            dp[i] = max(dp[i], dp[i - num[a]] + 1)

# 探索が終わったので答えを出す。
# 大きい桁にはなるべく大きな数字を割り振る
ans = ""
for i in range(dp[N]):  # dpによって得た桁数について上位桁から決定していく
    for a in A:  # すでに大きい順にソートしたので決定次第break
        if dp[N - num[a]] == dp[N] - 1:  # この条件についても解説を参照のこと
            ans += str(a)
            N -= num[a]  # マッチの本数から引くのを忘れずにね
            break

print(ans)