前回はこちらから。

前回の日曜日に開催されたABC138のコンテストに参加することができた。さらに久しぶりにAからD問題までノーミスで解くことができた！これはとてもうれしい！

なので、その際に解いたCとD問題について二回に分けてnoteに書いていこうと思う。
最初はC問題から。タイトルが「Alchemist」で錬金術師を意味している。いつもタイトルは気にしてなかったのだけど、内容が錬金術をしているみたいだったので、タイトルは「錬金術師」とかだろ〜って思い、つい気になってしまった。

ちょっと話がそれたけど、さぁ解いていこう！

ABC138C問題

問題文
あなたは鍋と N 個の具材を持っています。
各具材は 価値 と呼ばれる実数の値を持ち、i 個目 (1≤i≤N) の具材の価値は vi です。
2 個の具材を鍋に入れると、それらは消滅して新たに 1 個の具材が生成されます。
この新たな具材の価値は元の 2 個の具材の価値を x,y として (x+y)/2 であり、この具材を再び鍋に入れることもできます。
この具材の合成を N−1 回行うと、最後に 1 個の具材が残ります。
この具材の価値として考えられる最大の値を求めてください。

制約
- 2≤N≤50
- 1≤vi≤1000
- 入力中の値はすべて整数である。

アルゴリズム

具材を混ぜて新たな具材を生成していく単純な処理を可能な限り繰り返していく問題。単純な問題には単純なアルゴリズムで解いていこう。

1. すべての具材を価値順に昇順ソートする
2. 最初の具材と二番目の具材をまぜまぜ
3. 新たにできた具材と次の具材をまぜまぜ
4. 可能な限り手順3を繰り返す
5. 最後の具材が完成品

今回の問題は、混ぜる順番が重要そう。
どういった順番で混ぜるのがいいのだろうかというと、価値が低い順に混ぜていくのが良い。最初のほうに混ぜられた具材ほど何度も何度も価値を2で割られてしまう。なので、価値が高い具材はなるべく最後にまぜまぜしたほうが良い。

じゃあ、錬金するごとに新たな具材と前もって存在する具材を価値順に並べなおして、再度価値が低いのを選んでいこう！

ってなるんだけど、実は今回はもう少し楽ができる！なんと新たに錬金された具材は最も価値が低いことが証明されている。なのでソートがいらない！理由は以下の数式を見てほしい。

前提：
　a ≦ b
結果：
　(a+b)/2 ≦ b
導出：
　a/2 ≦ b/2　⇒　a/2 + b/2 ≦ b/2 + b/2 ⇒　(a+b)/2 ≦ b

ある2つの具材を混ぜてできた具材の価値は、混ぜる前の具材の価値よりも高くなれないんだ！

というわけで、新たな具材は最も価値が低いことにしてかまわない。そのため、ソートしなくても最も価値順の先頭に置くことができる。

これを知ってから、コードに落とすためのアルゴリズムを考えると以下のようになると思う。

1. 具材を価値順に昇順ソートする
2. 1番目の具材をi保持する（変数に入れておく）
3. i = 2とする
4. 保持している具材とi番目の具材を合成し、価値を求める
5. 新たな具材を保持する
6. i < N の場合、i を1上げ手順4へ
7. 現在保持している具材の価値を解答とする

これをコードに落とすと以下のようになる。

// v は具材の価値の配列
sort.Ints(v)
ans := float64(v[0])
for i := 1; i < n; i++ {
    ans = (ans + float64(v[i])) / 2.0
}

すごいシンプルでしょ！
あとは、入出力処理をつけたら完成だー！

解答

最終的には、以下のコードに。

package main

import (
   "bufio"
   "fmt"
   "os"
   "sort"
   "strconv"
)

func main() {
   s := wordScanner(100)
   n, v := scanNAndIntSlice(s)

   sort.Ints(v)

   ans := float64(v[0])
   for i := 1; i < n; i++ {
       ans = (ans + float64(v[i])) / 2.0
   }
   fmt.Println(ans)
}

func wordScanner(n int) *bufio.Scanner {
   s := bufio.NewScanner(os.Stdin)
   s.Split(bufio.ScanWords)
   b := make([]byte, n)
   s.Buffer(b, n)
   return s
}

func scanNAndIntSlice(s *bufio.Scanner) (int, []int) {
   s.Scan()
   n, _ := strconv.Atoi(s.Text())
   return n, scanIntSlice(s, n)
}

func scanIntSlice(s *bufio.Scanner, n int) []int {
   vals := make([]int, n)
   for i := range vals {
       s.Scan()
       m, _ := strconv.Atoi(s.Text())
       vals[i] = m
   }
   return vals
}

今回の問題は、ちょっとしたことに気づくと処理が簡単になる問題だった。解答もシンプルになるし、結構好みな問題だった。

この問題解いてて思ったけど、この錬金術師は結構な損しているなって感想...
錬金するたびに錬金の具材を消失して、出来上がるのは元の具材と同じぐらいの価値の具材。
なので、錬金なんてせずに最も価値の高い具材こそ本当に価値が高い具材ってことになる。錬金するほどに、具材は失うわ、価値は減ってくわでさんざんな錬金術だなぁって思ってた。

まぁ何はともあれ、うまく解くことができたし、楽しかった。

さぁ、次回はD問題を解いていこう！