ARC126 参加記録

コンテスト中AC:A

難しかったです。辛うじてAだけ解けました。

A - Make 10

本番でも自身の解法に確証がなかったので、公式解説を参照したほうがよいかもしれません。

使う数字をできるだけ少なくするようにする貪欲法を考えます。使う数字が少なければ、その後でより10を作れる可能性が大きくなるはずという思想に基づきます。

10になる組み合わせを列挙してみます。

{2,4,4}

{3,3,4} -> {6,4}

{2,2,3,3} -> {2,2,6}
{2,2,2,4}
{2,2,2,2,2}

まず、3は6にしないと10にできないので、3の個数は2で割り(切り捨て)、6とみなします。

使う数字の個数が最も少ないのは、{6,4}です。まずは、これで可能な限り10を作ります。次は条件分岐です。

(1) 6が余る時

　{2,2,6}が使う個数最小です。

　(i) 2が余る時

　　{2,2,2,2,2}を試すほかありません。

　(ii) 6が余る時

　　これ以上は10を作れません。 

(2) 4が余る時

　{2,4,4}と{2,2,2,4}が候補となります。2は{2,2,2,2,2}でも10を作れるので、

　2をできるだけ残すことを考えると、{2,4,4}を優先して作れるか試します。※

　(i) 2が余る時

　　4が1個余っている可能性があるので、{2,2,2,4}を作れるか試します。

　　そのあとは、{2,2,2,2,2}を試すほかありません。

　(ii) 4が余る時

　　これ以上10は作れません。

この貪欲法に基づくと、で解が得られます。

※補足

この記事を書いていて、特にここの正当性が曖昧だと気づきました。

考えがまとまれば、追記します。

追記

{2,2,2,4}で作った10が2個以上存在するとします。

{2,2,2,4}と{2,2,2,4}について、一方の{2,2}と他方の{4}を入れ替えて、{2,4,4}と{2,2,2,2,2}を作ることができます。これを繰り返すと、10の個数を変えることなく、{2,4,4}を貪欲に採用した状況になります(最終的に個数の偶奇に応じて{2,2,2,4}が0または1個になります)。

また、{2,2,2,4}と10を構成していないような{4}が存在するなら、{4}と{2,2}を入れ替えて、{2,4,4}と{2,2}を作り出し、{2,2,2,2,2}ができる可能性を広げることが可能です。

以上から、{2,2,2,4}より{2,4,4}の方を優先的に作る方が良いことがわかります。

これと同じように以下が言えそうです。

・{2,2}は、{4}で入れ替えた方が良い({2,2}より{4}を優先して使用した方が良い)

・{2,2,2}及び{2,4}は、{6}で入れ替えた方が良い（{2,2,2}及び{2,4}より{6}を優先して使用した方が良い）

まず、{4}や{6}が10を構成せず、余っていたとします。そうすると、既に10を構成する{2,2}, {2,2,2}, {2,4}と入れ替わることで10が更に作れる可能性が上がります。

次に、{4}や{6}が既に10を構成していたとします。仮にそれが最適な組み合わせであったとしても、{2,2}, {2,2,2}, {2,4}と入れ替わることは可能ですし、そうしても10の個数は減りません。

よって、{4}や{6}で入れ替える({4}や{6}を優先して採用する)と、解が悪化しないため、入れ替えた方が良いことになります。

この証明は厳密ではないかもしれませんが、数字を多く残した方が良いという直感的なものよりは、多少良くなったと思います。