AtCoder Beginner Contest 118 C,D問題メモ
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)
