AtcoderのコンテストのABC140に参加した。
今回はA～C問題までをクリア！
D問題は時間はたっぷりとあったのだけどどう解いていいのかさっぱりだった。。久々に競技プログラミングに挑戦したから勘が鈍ったかな？

まぁとにかくいつも通りに、C問題を解いていこうと思う。
それじゃあ、いってみよう！

ABC140Cの問題

問題文
長さ N の値の分からない整数列 A があります。
長さ N−1 の整数列 B が与えられます。
このとき、Bi≥max(Ai,Ai+1)が成立することが分かっています。
A の要素の総和として考えられる値の最大値を求めてください。

制約
- 入力は全て整数
- 2≤N≤100
- 0≤Bi≤10^5

アルゴリズム

んんん...？ちょっと整理してみないとぱっとはわからないかも。まずは整理してみようかな。

適当に数列Aを用意してみると

数列A: 4, 2, 3
数列B: max(4, 2), max(2, 3) = 4, 3

こんな感じに数列Bが求められる。では逆にこの数列Bの場合の最大の数列Aはどうなるかというと

数列B: 4, 3
数列A: 4, 3, 3

これはどう求めているかというと以下のように求めている。

数列B:       4,   3
                / \  / \     min(x, y)
数列A:    4,   3,   3

数列Aのi番目の数値は、数列Bのi-1、i番目の数値の小さいほうの数値となっている。（Aの1番目と最後だけは、Bの一番目と最後の数値）

たったこれだけ。数列Bが数列Aの最大値を用いて構成されているため、数列は逆にBの最小値で構成した場合が最大のパターンとなる。
あとは、数列Aの各値を合計すればよいだけ。

というわけで、アルゴリズムは以下の通り。

1. 数列Bを受け取る
2. 数列Aの合計値を数列Bの一番目の値とする
3. i = 2 とする
4. 合計値にmin(Bi-1, Bi)を足す
5. i が N -1 でないなら手順3へ
6. 合計値に数列Aの最後の値を足す
7. 求められた合計値が解答となる

さぁこれを実装して完成だ！

解答

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

package main

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

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
}

func min(l ...int) int {
   r := l[0]
   for _, n := range l {
       if n < r {
           r = n
       }
   }
   return r
}

func main() {
   s := wordScanner(100)
   n, b := scanNAndIntSlice(s)
   b = b[:len(b)-1]

   a := b[0]
   for i := 1; i < n-1; i++ {
       a += min(b[i-1], b[i])
   }
   a += b[len(b)-1]

   fmt.Println(a)
}

ふぅ、久々競技プログラミングに挑戦したから、思ったよりアルゴリズムを思いつくのに時間がかかってしまった。

実は最近は、問題を解くのではなく、ずっとAtcoderの解答自動化ツールの作成を行っていた。

今回は、これを利用して解答していたため、テストと提出がすごい楽だった。問題解くのに集中していればよいからね。

一応、ツールの作成はいったん落ち着いたから、過去問解くのを再開しないと。
頑張っていくぞー！

＝＝＝＝＝＝＝＝

前回の競プロへの挑戦はこちらから。