AtCoder Beginner Contest 118 C,D問題メモ
C - Monsters Battle Royale
問題
- N 体のモンスター、各HPの初期値は A1,A2,...,AN
- モンスター i をモンスター j に攻撃させると、j のHPは Aj=Aj−Ai となる
- HPが0以下になったモンスターは死に、攻撃したりさせたりができなくなる
- 生きているモンスターが1匹になるまで、攻撃対象 i,j を任意に選ぶ
- 最終的に生き残った1匹のモンスターのHPとして、あり得る最小値を求めよ
解法
最大公約数。
2匹の状態を考える。A1=22,A2=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匹目はさらにそこで生き残った方…と闘わせれば作れる。逆にこれらの数の引き算では最大公約数の倍数しか作れない。
1 2 3 4 5 6 7 8 |
from fractions import gcdn = 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 個、A1,A2,...,AM に限定する
- 作れる整数の最大値を求めよ
- 2≤N≤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 を足す。
1 2 3 4 5 6 7 8 9 10 11 |
n, m = map(int, input().split())needs = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]dp = [-1] * (n + 8)dp[0] = 0for 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] で何らかの数字が作れる時、そこに数字 Ai（使うマッチ棒 Bi）を1つ付け足すと、マッチ棒は Bi 本、桁数は1つ増え DP[k+Bi]=DP[k]+1 となる。
実際は Ai は複数あるので、その中の最大値となる。
使う数字: 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では試す必要は無い。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
from collections import defaultdictn, 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] = 0for 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 = nrk = [(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 breakprint(ans) |
