A. B+/-A

一瞬約数判断を素因数分解か結果の埋め込みかで解こうとしてしまった．editorialにもあるが$p$が$q$の約数かどうかは$q$が$p$で割り切れるか，すなわち$q \bmod p = 0$かで見ることができる． 解答例

B. Foods Loved by Everyone

配列で個数をカウントするよくある手法． 解答例

種類$i$の出現回数，すなわち$i$を好きな食べ物としている人数を$a[i]$に記録しておけば，種類$i$が全員に好かれているかは$a[i]=N$か否かで判断可能．記録するためには$i$が見つかるたびに$a[i]$+=$1$をすればよい．

C. Monsters Battle Royale

直観的に通してしまった．恐らくCodeforcesで類題を見たことがある．解法としては$\gcd\{A_i\}$を取ればよい． 解答例

editorialが親切なのであまり書くことがないが，答えの候補にgcdがあることの雑な説明：攻撃による体力変動から最後のモンスターの体力は$\sum k _i A_i$の形になるはず．これは整数$k_i$を上手に決めて作れる数の範囲内であるから，その粒度は最も細かくて$\gcd \{A_i\}$である（実現可能性を扨措いて）．これにより求める答えがgcd以上であることが言えたから，あとはeditorial通りユークリッドの互除法に気付けばgcdが実際に構築可能かつ最小と分かり，答えとなる．

ユークリッドの互除法になることについてもちょっと書いておきたくなった：体力$p,q \text{ s.t. } p \gt q$について大小関係が逆転するまで$(p,q) \to (p-q,q)$ $\to ...$ $\to (p-kq,q)$と遷移させると確かに$p-kq = p \bmod q$．

D. Match Matching

$10^4$を$1000$だと思い込み，コードテストで1200ms（C++で400ms）で動くのに何で提出するとTLEなんだろうとか言っていた． 解答例

最初に浮かんだ方針は$dp[i][j] \coloneqq$「$i$桁目まで使って残りマッチ数が$j$のときに作れる最大の整数（int64を超えるため文字列で管理）」^[1]． 更新は

$$dp[i][j-cost[k]] \gets \max \{ dp[i][j-cost[k]], dp[i-1][j] \char`\^ k\}$$

である（$k$は使える数字，$cost[k]$はそのコスト，「$\char`\^$」は文字列連結）が，TLEする^[2]．

ここで桁数$i$が要らない気がしてくる：例えば使う数字として$1$（コスト$2$）と$7$（コスト$3$）を考えてもかなり隙間が空くことになるし，「残りマッチ数が$j$のときに作れる整数」を考えるには不要な情報である．そこでさらに状態を纏めて$dp[j] :=$「残りマッチ数が$j$のときに作れる最大の整数」とし，$dp[j]$を順に埋めていくことを考えると，遷移は

$$dp[j-cost[k]] \gets \max \{ dp[j-cost[k]], dp[j] \char`\^ k \}$$

となる．これなら間に合う．

なお文字列で表した数字のmaxは，単にPervasives.maxでは分からない（ほかの言語でも多分そう）：maxで使われている文字列比較は辞書順による比較なので111と2では後者のほうが大きくなってしまう．したがって(1)桁数の大きさ，(2)先頭から見て初めて相違となる数字の大きさ，の順に決める必要があり，これは自前で実装することになる．

実装に際してPervasives.compareの結果が何を表すかよく覚えていなかったのでメモ：第一引数が大きい(+1)か小さい(-1)か等しい(0)かで覚えるのがよいだろうか．

editorialでは桁数を先にdpで求めてから数字を復元している．正直なところこの問題ではこの方針を採る利点があまり分からない．いちいち文字列を構築したくないときには良いのかもしれない．

因みに「優先度が最高のものを貪欲に並べて桁数最大にする → 余りを調整」みたいな方針も最初の実装中に考えていた．でも2つ以上の数字を使ったりもするので結局似たようなdpをすることになりそう？

---

1. editorialの「マッチが$j$本のときに作れる最大桁数～～」と紛らわしいが違う．この記事ではマッチの本数$n$から始めて残りが$j$本のときを，editorialでは最初からマッチが$j$本のときを意味している．従って私の実装では$j$は$n$から$0$まで降順に埋めていくことになる． ↩︎

2. 最大桁数が$N/2$である上に文字列の比較も最悪$N/2$ステップ……だが均すとlogになるようなならないような（未確認）．仮にlogだったとしても少なくとも$O(N^2 M \log N)$はあり厳しそう．実際間に合わない． ↩︎