AtCoder:ABC118-D(Match Matching)を復習する-ぐぐりらにっき

こんにちは、ぐぐりら(<a href="https://twitter.com/guglilac">@guglilac</a>)です。
コンテスト自体には参加していないですが、練習のため解きました。

ABC118回はCまではすんなりいけて、Dでつまったので、復習。

自分でこのレベルも解けるようになりたい。

## 問題

マッチが$N$本与えられた時に、作れる数字の最大値を求める問題。

数字`1,2,3,4,5,6,7,8,9`を 1つ作るには、それぞれちょうど `2,5,5,4,5,6,3,7,6`本のマッチ棒を使うという設定。
デジタル表示みたいなあれだと思う。

問題ではさらに、使っていい数字が$M$個指定されます。
使っていい数字列は$$A_1,A_2,A_3,...,A_M$$と与えられます。

## 考察

### 自分で考えたこと
なるべく桁数は多い方がいいから、本数のコストが少ない数字を使いまくればいいのか〜、じゃあ1を作りまくればいいのでは、と考えた

使える数字も指定されているから、その中で一番コストが小さいものを貪欲に。。。と思ったけどn本ちょうど使わないといけないから貪欲には無理なのか。じゃあDPで解くのかな。

本数をxとして
「$DP[x]$:ぴったり$x$本使った場合の最大値」として更新していけばいいのかな、と考えましたが、保持しておく数字が大きすぎて難しいかなと思いました。

リストとして持っておいて、新しく数字を追加する際に毎回降順ソートする、桁数はリストの長さとして取得するなどしていくのでできるのかも？と思いましたが、結局数値の比較の際にリストの要素を全部結合しないといけないのでだめそう。

### 解説をよんで

途中まではあってて、DPに入れるものが「作成できる数字の最大値」ではなく「最大桁数」でした。

**DPに保持していく値は必ずしも求める答えではない**、肝に銘じておきたい

最大桁数ならDPできます。

桁数が決まったら、なるべく大きい数字を左から埋めていけばおっけーですが、ここもちょっとわからず。

解説を見るとわかったのですが、
その数字が一番左に入りうるかは、つくったDPテーブルを見ていけば確認できるのですね。

ある数字を作るのに必要なマッチの本数分を減らした時に、残りのマッチの本数で作ることができる最大桁数がDPテーブルと整合が取れているか確認するわけです。すごい。

DPはある要素(だいたい最後の要素)を求めるために使うイメージでしたが、**テーブル全体を使う**ことがあるんですね。勉強になりました。

## コード

自分で書いたACしたコード。

```python
inf = float("inf")
N, M = map(int, input().split())
A = map(int, input().split())
C = [2, 5, 5, 4, 5, 6, 3, 7, 6]
costs = {m: C[m - 1] for m in A}
dp = [0]
for i in range(1, N + 1):
    dp.append(
        max([dp[i - c] if i - c >= 0 else -inf for c in costs.values()]) + 1)

digits = list(costs.keys())
digits = sorted(digits, reverse=True)
num = N
result = []
for _ in range(dp[N]):
    for digit in digits:
        if num >= costs[digit] and dp[num - costs[digit]] != -inf and dp[num - costs[digit]] == dp[num] - 1:
            result.append(str(digit))
            num -= costs[digit]
            break
print("".join(result))
```

残りのマッチの本数で作ることができる最大桁数がDPテーブルと整合が取れているか確認する部分がいろいろ条件が増えてしまってわかりづらい。

```python
num >= costs[digit]
```
の条件を忘れて一つだけREになりました

コーナーケースに気づけるようになりたいです。

AtCoder:ABC118-D(Match Matching)を復習する

0 件のコメント:

コメントを投稿

このブログを検索

POPULAR POSTS

SPONSORED LINK

RECENT POSTS

TWEETS

ARCHIVES

LABEL

CONTACT