ABC118D Match Matching

ABC118 に参加しました。
結果としては3完で+32という微妙な結果に終わりました。

コンテスト終了後にD問題のMatch Matchingを解いたので、コードを載せてみます。

方針

与えられたマッチを"ちょうど"使った時の最大の数を表示する。
この"ちょうど"というところから、貪欲法でやるよりもDPでやったほうがいいという気持ちになりました。
(コンテスト本番にはDFSでやろうと思ってましたが、計算量や"ちょうど"という制約が面倒になります)

解説の資料には桁数を保存して、後から最大の数値を生成する感じになっています。
私はPython3とC++の両刀使い(どっちつかず)なので、Pythonでやってlong long int の壁を越えることができます。
そこで

として、数を文字列に変換せず直接代入しました。

コードは次の通りです。

match = [2,5,5,4,5,6,3,7,6]
n,m=map(int,input().split())
aa=list(map(int,input().split()))
#9以上多めにとってout of range を防ぐ
dp=[-1]*(n+10)

dp[0]=0
for i in range(n+1):
        for nums in aa:
                #この条件がないと、i本までで表現できる最大の数になる
                if dp[i] == -1 :continue
                dp[i+match[nums-1]] = max(dp[i]*10+nums,dp[i+match[nums-1]])

print(dp[n])

DPはちゃんと勉強していくつもりです。
いつかコンテスト本番でDを解いて見たいです。