AtCoder Beginner Contest 118

Updated:

AtCoder Beginner Contest 118

ソースコード

解法のメモ

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$ を用いて以上のことを実行すれば十分である。

intstring に変更するなら to_string でできるし、 stringll に変更するならば 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 する安全である。少なくとも私のローカルでは必要である。

その他

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