AtCoder のプログラミングコンテスト ABC 118 に参加しました。今週は ABC-only 回で、なんとか全完できました。この記事では、問題の考察を自分なりに書いていきます。
本連載は前回 (https://note.mu/vain0x/n/n07b1b0686624) までは note に書いていましたが、今後は Qiita に掲載します。
- 回答は Rust (1.15.1) で書いていて、入力のパースに自作マクロを使っています。
AtCoder Beginner Contest 118
問題一覧: https://atcoder.jp/contests/abc118/tasks
- 問題の正確な説明や制約などは問題ページを参照してください。
A - B +/- A
問題概要: A が B の約数なら A+B を出力し、そうでなければ B-A を出力せよ。
考察: A が B の約数であるとは、B を A で割った余りがゼロであることをいいます。これを実際に判定して場合分けすればOK。
筆者の回答 (AC): https://atcoder.jp/contests/abc118/submissions/4283197
B - Foods Loved by Everyone
問題概要: N 人それぞれに、 M 個の食べ物の種類について好きか嫌いかを質問した。人 i が好きな食べ物の種類のリストを A[i] とおく。すべての人が好きと答えた食べ物の種類の個数を求めよ。
考察: すべての人の「好きな食べ物の種類の集合」の共通部分の要素数が答えになります。というわけでそのように実装しましたが、冷静に考えると全探索するだけでよかった……
筆者の回答 (AC): https://atcoder.jp/contests/abc118/submissions/4283061
C - Monsters Battle Royale
問題概要: N 体のモンスターがいる。モンスター i の体力は A[i] である。いずれかのモンスター x が他のモンスター y の体力を A[x] 減らす、という操作を好きなだけ繰り返す。これによって体力が正のモンスターが1体になった。その体力としてありうる値の最小値を求めよ。
考察: もとの問題文には「ランダム」と書かれていますが、実際には確率の話は出てこないので、どのモンスターがどこに攻撃するかは好きに選べると考えていいです。
体力 A[i] の最大公約数を g とします。どのように操作をしても、体力は g の倍数になるので、最小値は g 以上です。
また、ユークリッドの互除法と同様手順を踏むことによって、最終的な体力が g になるようにできます。だから g が答えです。
筆者の回答 (AC): https://atcoder.jp/contests/abc118/submissions/4282226
D - Match Matching
問題概要: マッチ棒を W[d] 本使うことで、数字 d (1〜9) を作れる。ただし作れる数字は集合 A に含まれるものに限られる。合計 N 本のマッチ棒をちょうど使って作れる整数のうち、最大のものを求めよ。ただし W = [_, 2, 5, 5, 4, 5, 6, 3, 7, 6] である。
考察: マッチ棒の本数 N が 10^4 と多めなので、整数は 64 ビットに収まらない点に注意。
桁数が大きいほど大きい整数になるので、なるべく少ない本数のマッチ棒を使って多くの数字を作るのがよさそうです。
そこで、集合 A に含まれる数字のうち、使うマッチ棒の本数が最小である数字を d とします。複数あるときは、値が最大のものを選びます。余っているマッチ棒の本数 N が W[d] の倍数なら、すべての桁を d とするのが最善です。
問題は W[d] の倍数にならない端数の処理です。
例えば A = {2, 8, 9} のとき d=2 (W[d]=5本) です。数字の 9 (6本) や 8 (7本) を組み合わせて、マッチの余りが 5 の倍数になるようにします。N=624 では 9999 (24本) の後に 2 を120個 (600本) 並べるのがベストです。
ここで注意点として、d の個数を最大化すればいいというわけではないです。24本のマッチで 8822 を作れば d=2 の個数が最大化されますが、結果の整数は最大になりません。(はじめ、これに気づかなくてWAしました。)
では何桁ぐらいまで端数処理に費やせばいいのか。d の他に数字 e があるとき、端数処理に使うマッチの本数の上限は W[d] と W[e] の最小公倍数です。これを超えると d を並べたほうがよくなります。W の値をみると、最大で42本です。このことには後から気づいたので、本番ではおおざっぱに「整数10桁分」ということにしました。このへんを正確につめられない……
まとめると、こういうアルゴリズムにしました。全探索で10桁の整数を作る方法を列挙します。マッチ棒の残りの本数が W[d] の倍数にならないものは除外します。これで得られた最大の整数と、余ったマッチで作った数字 d を組み合わせます。これが答えです。
筆者の回答 (AC): https://atcoder.jp/contests/abc118/submissions/4290474
想定解は DP らしいです。
D: 想定解
(追記 2019-02-18)
公式の解説 PDF を読んで想定解を実装しました。
提出: https://atcoder.jp/contests/abc118/submissions/4306236
これは、はじめに DP によって「dp[n]: マッチ棒 n 本で作れる整数の桁数の最大値」を調べます。これによって答えとなる最大の整数の桁数が判明します。
あとは「マッチ棒の残りを使って、整数の残りの桁をぴったり埋められるか？」に注意しながら、整数の各桁の値を上位桁から順に決めていける、という流れのようです。