A - Make 10 Editorial
by 
maspy
◆偶奇性の利用
長さが \(10\) の棒を作るときに使用する長さの \(3\) の棒は、必ず偶数本使うことになります。したがって、「長さが \(3\) の棒が \(N_3\) 個ある」という代わりに初めから「長さが \(6\) の棒が \(\lfloor\frac{N_3}{2}\rfloor\) 個ある」として考えればよいです。 したがって本問題は、長さが \(2, 4, 6\) の棒から長さ \(10\) の棒を作る問題へと帰着することができます。さらにすべての棒の長さを \(2\) で割ることで、次の問題に帰着することができます：
長さが \(1\) の棒が \(N_1\) 個、長さが \(2\) の棒が \(N_2\) 個、長さが \(3\) の棒が \(N_3\) 個ある。長さがちょうど \(5\) に等しい棒を最大でいくつ作ることができるかを求めよ。
以下の解説でも、元の問題の代わりにこの問題を扱っていきます。
長さ \(5\) の棒をなるべくたくさん作る方法を、「最適解」と呼ぶことにします。
◆最適解の構造 (1)
例えば「長さ \(2\) の棒がひとつある」状態に比べて、「長さ \(1\) の棒がふたつある」状態の方が、選択肢が広く有利であるというような直感が働くと思います。このような観察を元に最適解に仮定できる構造を整理していきます。
次を示すことができます：
長さ \(2\), \(3\) の棒がひとつ以上あるとき、最適解のうちで、それらを接着して長さ \(5\) の棒を作るものが存在する。
このことを証明しましょう。どの最適解も長さ \(2\), \(3\) の棒を接着しないと仮定して矛盾を導きます。最適解をひとつとり、\(X\) とします。また、長さ \(2\), \(3\) の棒のひとつずつに \(A\), \(B\) という名前を付けておきます。
- \(X\) が棒 \(A, B\) を使わない場合：\(A, B\) を接着して長さ \(5\) の棒を増やすことができるので、\(X\) の最適性に矛盾する。
- \(X\) が棒 \(A\) のみを使う場合：\(A\) を含む長さ \(5\) の棒を解体して \(A\), \(B\) を接着しなおすことで、長さ \(2,3\) の棒を接着するような最適解が得られるので矛盾。
- \(X\) が棒 \(B\) のみを使う場合：同様に矛盾。
- \(X\) が棒 \(A\), \(B\) ともに使う場合：\(A\) を含む長さ \(5\) の棒と、\(B\) を含む長さ \(5\) の棒を解体して、\(A\)と\(B\)、および残った棒たち を接着しなおすことで、長さ \(2,3\) の棒を接着するような最適解が得られるので矛盾。
以上で証明できました。
◆最適解の構造 (2)
上で示したことより、長さ \(2, 3\) の棒が両方存在する場合の接着させ方は解決しました。あとは、長さ \(2\), \(3\) どちらかの棒が存在しない場合について考えていきます。
同様に、次を証明することができます。証明は省略します。
長さ \(2\) の棒が存在せず、長さ \(3\) の棒が \(1\) つ以上、長さ \(1\) の棒が \(2\) つ以上存在するとき、最適解のうちで、これら長さ \(3, 1, 1\) の棒を接着するものが存在する。
長さ \(3\) の棒が存在せず、長さ \(2\) の棒が \(2\) つ以上、長さ \(1\) の棒が \(1\) つ以上存在するとき、最適解のうちで、これら長さ \(2, 2, 1\) の棒を接着するものが存在する。
長さ \(3\) の棒が存在せず、長さ \(2\) の棒が \(1\) つだけ存在し、長さ \(1\) の棒が \(3\) つ以上存在するとき、最適解のうちで、これら長さ \(2, 1, 1, 1\) の棒を接着するものが存在する。
◆貪欲アルゴリズム
結局、次の貪欲アルゴリズムによって、最適解のひとつが得られることが分かります。
(step 1) 長さ \(2, 3\) の棒がどちらもひとつ以上あるならば、それらを接着して長さ \(5\) の棒を作る。このことを、可能な限り繰り返す。
(step 2) 長さ \(3\) の棒が \(1\) つ以上、長さ \(1\) の棒が \(2\) つ以上存在するとき、それらを接着して長さ \(5\) の棒を作る。このことを、可能な限り繰り返す。
(step 3) 長さ \(2\) の棒が \(2\) つ以上、長さ \(1\) の棒が \(1\) つ以上存在するとき、それらを接着して長さ \(5\) の棒を作る。このことを、可能な限り繰り返す。
(step 4) 長さ \(2\) の棒が \(1\) つ以上、長さ \(1\) の棒が \(3\) つ以上存在するとき、それらを接着して長さ \(5\) の棒を作る。このことを、可能な限り繰り返す。
(step 5) 長さ \(1\) の棒が \(5\) つ以上存在するとき、それらを接着して長さ \(5\) の棒を作る。このことを、可能な限り繰り返す。
◆解答例
posted:
last update: