mikanbox55's diary

AdventCalenderのために作りました。中の人のやる気しだいで記事が増えるかも

AtCoder ABC 118 D Match Matching

私的にやってるatcoderですが先日ABCのC埋めがやっと終わりました。Dからは1問あたりのボリュームが増えるので詰まった問題とかについて出来るだけアウトプットを残していきたいと思い記事を書くことにしました。

人によってはAB問題は簡単だから埋めるまでも無いって意見の人もいますが、AB埋めする時にc++でやると、STLの各コンテナ型やtemplateの復習にもなるので大抵の方にはお勧めします。

では本題。 問題リンク

問題概要

  • N本のマッチ棒をぴったり使って出来るだけ大きな数を作る
  • 1-9までの数字のうちM種類の使える数字がA_{i} (1 \leq i \leq M) で与えられる

制約条件

  • N \leq 10^4

考察

最初に上の桁から貪欲に決めていく方法を考えた。基本的には桁数が大きいほど良いので、提示された全ての数字 A_{i} のうち、必要なマッチの数が一番小さいA_{i}ものA_{min}を選択し、必要なマッチの最小数で割ればN / M( A_{min} )、大体の桁数は出せる。

ここで問題になるのは、ちょうどN本使う必要があるため、適当なA_{i}を組み合わせて使用マッチの数をNにする必要があるということである。一番下の桁から探索し、マッチの数がぴったりかつ、桁数が最大で数字が最大になる組み合わせを探す。

....というような考え方でやってたが、マッチの数がぴったりかつ、桁数が最大で数字が最大になる組み合わせを探す この部分の探索が結局難しくて諦めた。なんかいけそうな気もするが考慮すべき制約の数や組み合わせが膨大になってきた時点で他の解法を検討すべきだったと今になって思う

以下に想定した解法でACした記事が載ってた。制約じゃなくてある桁数まで全探索でいけるっぽい。今度試してみるかー。 qiita.com

想定解法

想定解法はDPらしい。確かに制約条件が N \leq 10 ^4 なので、DPは選択肢に入れといた方がよかった。 DPの形式は以下
dp_{i} = マッチ棒をi本使って作れる整数の最大値

遷移式
dp_{i} = funcmax(dp ( i ) ,dp ( i - M ( A_{j} ) )

確かに、この定義だと dpの添字i*に対して局所最適性 ( i_{1} \leq i_{2} → dp_{1} \leq dp_{2} )は成り立っていることがわかる。

あとは整数の最大値をどうやって保存するかである。
条件より生成される整数は10^4桁までで、到底long long などに収まらない。初見ではvectorを使って一つひとつ各桁を保存することを考えたが、いくつかの記事でstring型に保存するのを見た。確かにこれならいちいちpushする代わりに 足し算で処理できるし、桁数はsize()で取れて比較もcharを取り出して比較すれば良いので非常にあっている.

あとはfunc_maxの部分を正確に定義すれば良い。ifとかで書かずにちゃんと外部に関数で書こう。
今回重要なのは桁数なので、最初に桁数を比較。次に各桁の数を見ていって比較をすることで正確に比較ができる。

以上。