2021-統一-解説
- 考案国：フィリピン
- 正解
- 正解は24です。
- 説明
- 部族を統一する日数は、部族の村の数の合計になりますので、村の数の多い部族ほど、後に追加したほうがよいことがわかります。具体的に考えてみましょう。
- まず、部族ごとの村の数は、少ない順に「緑2、青3、赤3、オレンジ4」です。そこで、少ない順に統一していくことを考えると、次のようになります。（統一後の色は、村の多いほうの色にしています）
(1) 最初「緑2、青3、赤3、オレンジ4」
(2) 緑と青を統一する。緑2＋青3→青5。「赤3、オレンジ4、青5」
(3) 赤とオレンジを統一する。赤3＋オレンジ4→オレンジ7。「オレンジ7、青5」
(4) オレンジと青を統一する。オレンジ7＋青5→オレンジ12。「オレンジ12」 - かかった日数を合計すると、「5＋7＋12」で24になります。
- 実際のコンピュータでは
- この問題は、最適化問題のひとつです。最適化問題では、与えられた制約条件の中で、結果の値を最大化または最小化するための戦略を考えます。私たちの生活でも、最適化問題は、目的地までの最適な道を見つけるときなどに活用されています。
- 最適化問題を解く方法のひとつに、貪欲アルゴリズムがあります。貪欲アルゴリズムでは、「各段階で最適な選択をすれば（局所的最適）、最終的に最適な結果（大域的最適）が得られる」という仮定を使います。今回の問題では、この仮定が成り立っていました。つまり、全体の日数を最小化するためには、それぞれの統一の日数を最小化しなければなりません。
- 貪欲アルゴリズムは、すべての最適化問題に適しているわけではありませんが、多くの場合は時間内に正解または正解に近い値を求めることができます。
注があるものを除き, このサイトの内容物は
