AtCoder Beginner Contest 118 C,D問題メモ

AtCoder Beginner Contest 118

AtCoder Beginner Contest 118 解説放送 - YouTube

C - Monsters Battle Royale

問題

$N$ 体のモンスター、各HPの初期値は $A_1,A_2,...,A_N$
モンスター $i$ をモンスター $j$ に攻撃させると、 $j$ のHPは $A_j=A_j-A_i$ となる
HPが0以下になったモンスターは死に、攻撃したりさせたりができなくなる
生きているモンスターが1匹になるまで、攻撃対象 $i,j$ を任意に選ぶ
最終的に生き残った1匹のモンスターのHPとして、あり得る最小値を求めよ

解法

最大公約数。

2匹の状態を考える。 $A_1=22,A_2=14$ とする。常にHPの低い方を、高い方に攻撃させる。

phase  A1  A2
    1  22←14
    2   8→14
    3   8← 6
    4   2→ 6
    5   2→ 4
    6   2→ 2
    7   2   0    Ans:2

するとこのプロセスは、2数の最大公約数を求めるユークリッドの互除法と同じ操作になる。残る1匹のモンスターのHPは2数の最大公約数となる。

逆に、この2数同士の引き算だけで、最大公約数以下の値は作れない。（最大公約数 $g$ の倍数同士の引き算では、 $g$ の倍数しか作れない）

最大公約数は必ず作れる＆最大公約数未満は作れない→答えは最大公約数。

3匹以上の場合も同じことが言える。 $N$ 個の数の最大公約数は、3匹目は1匹目と2匹目で生き残った方、4匹目はさらにそこで生き残った方…と闘わせれば作れる。逆にこれらの数の引き算では最大公約数の倍数しか作れない。

        
              from fractions import gcd
 
n = int(input())
aaa = list(map(int, input().split()))
ans = aaa[0]
for a in aaa[1:]:
    ans = gcd(ans, a)
print(ans)

D - Match Matching

問題

マッチ棒で1～9の数字を作ると、それぞれ2,5,5,4,5,6,3,7,6本必要となる
- 参考画像
マッチ棒 $N$ 本をちょうど使い切って整数を作る
使う数字は $M$ 個、 $A_1,A_2,...,A_M$ に限定する
作れる整数の最大値を求めよ
$2 \le N \le 10000$
必ず作れるように条件が与えられる

解法

シンプルなDP

制約がそこそこ緩いので、単純なDPでも通る。

$DP[i]=$ マッチ棒 $i$ 本ちょうど使う時、作れる数字の最大値

最大値なので、答えとなる数字の並びは必ず大きい方が前に来る。数字を並べ替えても使用するマッチ棒の総数は変わらないので、たとえば '12345' とあったら '54321' と並べ替えた方が必ず大きくなる。

なので、このDPも大きい数字から試し、末尾に追加していく。

N = 17
使う数字: 4 8 9
マッチ棒: 4 7 6

初期状態
DP[0]=0

9を使う
DP[ 6] =  9
DP[12] = 99

8を追加で使う
DP[ 6] =  9
DP[ 7] =  8
DP[12] = 99
DP[13] = 98
DP[14] = 88

4を追加で使う
DP[ 4] =  4
DP[ 6] =  9
DP[ 7] =  8
DP[ 8] = 44
DP[10] = 94
DP[11] = 84
DP[12] = 444
DP[13] = 98
DP[14] = 944
DP[15] = 844
DP[16] = 4444
DP[17] = 984

計算量は、 $O(NM)$ となる。

全て1を使っても5000桁なので、多倍長整数を扱えるPythonなら特に気にせず整数比較してもまぁ大丈夫。末尾に $k$ を付ける＝10倍して $k$ を足す。

        
              n, m = map(int, input().split())
needs = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
dp = [-1] * (n + 8)
dp[0] = 0
for a in sorted(map(int, input().split()), reverse=True):
    na = needs[a]
    for i in range(n + 1):
        if dp[i] == -1:
            continue
        dp[i + na] = max(dp[i + na], dp[i] * 10 + a)
print(dp[n])

解説pdfの方法

DPで桁数テーブルを作成→先頭から貪欲に決定、とする。

求めるのは最大値なので、桁数は多い方が良い。桁数が同じなら、大きい数字が先頭に来ている方が良い。なので、まず桁数から特定する。

で、桁数だが、一見「 $N/($ 使う本数の最小値 $)$ 」で求められそうに思うが、そう単純にはいかない。

N = 17
使う数字: 4 8 9
マッチ棒: 4 7 6

桁数 = N/(マッチ棒の最小値) = 17/4 = 4...1 なので4桁？
→これだと、余りの1本を処理できない

桁を1つ犠牲にして、984 が答えとなる

これを求めるには、「 $DP[k]=$ マッチ棒 $k$ 本ちょうどで可能な最大桁数」として $k=2$ より埋めていく。

$DP[k]$ で何らかの数字が作れる時、そこに数字 $A_i$ （使うマッチ棒 $B_i$ ）を1つ付け足すと、マッチ棒は $B_i$ 本、桁数は1つ増え $DP[k+B_i]=DP[k]+1$ となる。

実際は $A_i$ は複数あるので、その中の最大値となる。

使う数字: 4 8 9
マッチ棒: 4 7 6

DP      0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17
最大桁  0  x  x  x  1  x  1  1  2  1  2  2  3  2  3  3  4  3

17本使う時の最大が3桁と分かったので、上の位から、出来るだけ大きい数字から試して貪欲に埋めていく。下の表の「 $K$ 本で $D$ 桁は作れるか？」の判定は、再びDPテーブルを利用する。

    残り  試す  使う  試した後の    試した後の  K本でD桁は
桁  本数  数字  本数  残マッチ K    残り桁数 D  作れるか？
 3    17     9     6          11           2          YES  →  9
 
 2    11     9     6           5           1           NO
 2    11     8     7           4           1          YES   → 98
 
 1     4     9     6          -2           0           NO
 1     4     8     7          -3           0           NO
 1     4     4     4           0           0          YES   → 984

枝刈り

使う本数が同じ数字は、最も大きいもののみ使う

たとえば2と3と5が共に使える場合、どれも必要本数は5なので、答えには最大の5のみ使うことになる。 2や3を使って $N$ 本ちょうどに出来る数字は、そこを単純に5に置き換えた数字の方が必ず大きい。

一度試して失敗した数字は再度試す必要は無い

貪欲に最大桁から埋める過程で、例えば上記の例では桁2の時に9は失敗しているので、桁1では試す必要は無い。

        
          
          
              
              from collections import defaultdict
 
n, m = map(int, input().split())
needs = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
usable = defaultdict(lambda: 0)
for a in map(int, input().split()):
    na = needs[a]
    usable[na] = max(usable[na], a)
use_keys = sorted(usable.keys())
 
dp = [-1] * (n + 15)
dp[0] = 0
for d in range(n + 1 - use_keys[0]):
    for u in use_keys:
        dp[d + u] = max(dp[d + u], dp[d] + 1)
 
ans = ''
remain = n
rk = [(str(a), needs[a]) for a in sorted(usable.values(), reverse=True)]
for d in range(dp[n] - 1, -1, -1):
    for a, na in rk:
        ra = remain - na
        if dp[ra] == d:
            ans += a
            remain = ra
            break
 
print(ans)

            

        
      