AtCoder Beginner Contest 118
Updated:
Source codes
Solutions
A - B +/- A
これは指示通りにやるだけです。
if b % a == 0
puts a + b
else
puts b - a
end
B - Foods Loved by Everyone
int X[100]; を初期化して X[A]++; としていくだけでよろしい。最後は $X[i] = N$ ならば ans++; とする。
C - Monsters Battle Royale
解答
$A[i]$ らの最大公約数 $L$ が答え。
ans = a[0]
a.each{|x|
ans = ans.gcd(x)
}
puts ans
解答の正当化
まず任意の(死んでいる)モンスターも含めて、そいつの HP は $L$ の倍数である。よって最小値の候補は $L$ である。実際に $L$ を作る方法があることを示せばよろしい。
まずユークリッド互除法により、 $A[0]$ と $A[1]$ を戦わせると $\gcd(A[0], A[1])$ のモンスターが $2$ 体できる。これを戦わせて一方を殺害する。新たに $A[0] \gets \gcd(A[0], A[1])$ というモンスターが生き残ったことになる。こいつと $A[2]$ をユークリッド互除法で戦わせる。これを繰り返す。こうして最後に生き残ったモンスターの HP は $\gcd _ {i \in N} A[i]$ すなわち $L$ である。
ポイント
これは直感でわかった。 Ruby の最大公約数は 整数.gcd(整数) で求まることに注意するべきだった。
D - Match Matching
私の解答
まず map<int, int> X を、 cost を入力すると作れる最大の整数を返す map として定義する。出来るだけ桁数の多い並べ方を見出す。
もし $X[2] = 1$ が存在するのであれば、それは $1$ を並べられるということである。
- $N \% 2 = 0$ の場合： $1$ を並べるのが最善である。
- $N \% 2 = 1$ の場合： cost が奇数であるものが必ず使えるので、その cost の数字を使う。その数字の後に $1$ を並べるのが最善である。
そうでない場合は、まず cost 最小の数字を用いて $N \leq 100$ 程度まで $N$ を減らす。その後 $N$ を可能な cost たちで分割することを深さ優先探索で全列挙する。そしてそいつらで最大の数字を出力するものを選べばいいのだが、桁数最大のもののうち、最初の 12 桁くらいを見れば十分である。
実装
まず、以上の場合わけは必要ない。したがって下の分だけ実装すればよろしい。
実装では vector<int> V(10, 0); を
$V[i] = i$ を使う個数
を持っておいて、まず $N \leq 100$ まで減らす。その後 DFS のタネとして $V$ と $N$ を用いて以上のことを実行すれば十分である。
int を string に変更するなら to_string でできるし、 string を ll に変更するならば stoll でできる。
ポイント
最初に減らしていた数字を後から接続していたので間違えていた。もう少し綺麗に実装したかった。
模範解答
模範解答は桁 DP だった。まず $\{ A _ i \}$ たちは降順であるとして良い。 桁数が最大となるマッチの使い方のうち、できるだけ前の数字を使うようなものが最大の数を与える(貪欲法) 。以下を定める。
$H[i] =$ 数字 $i$ を作るために必要なマッチの数。
$DP[i] = i$ 個のマッチを使って作れる数字の最大の桁数。ただし $i$ 個のマッチを使って数字が作れない場合は $-1$ であると規約する。
ここで $DP$ を求めにいく。初期状態： $DP[0] = 0$ 、その他 $DP[i] = -1$ 。遷移： $i \in N$ に対し、 $DP[i] \geq 0$ ならば、 $j \in M$ に対し、 \[ DP[i + H[A _ j]] \gets \max(DP[i + H[A _ j]], DP[i] + 1). \]
そして解答であるが、まず $ind = 0$ とする。 $N - H[A _ {ind}] \geq 0$ かつ $DP[N] = DP[N - H[A _ {ind}]] + 1$ が成立するならば、それは数字 $A _ {ind}$ が、最大桁数を達成するために、特に最上位桁として、使える ということである。よって $N \mathbin{ {-} {=} } H[A _ {ind}]$ を実行し、 $A _ {ind}$ を出力する。そうでないならば $ind {++}$ とする。これを $N > 0$ の間繰り返す。
最後に cout << endl; で flush する安全である。少なくとも私のローカルでは必要である。
Others
unrated で助かった。
A - sample: 3, tle: 2.000, time: 01:24, from_submit: 81:09
B - sample: 3, tle: 2.000, time: 02:32, from_submit: 78:37
C - sample: 3, tle: 2.000, time: 02:53, from_submit: 75:44
D - sample: 3, tle: 2.000, time: 75:44, from_submit: 00:00