AtCoder AGC 024 C - Sequence Growing Easy (Go)

irisruneです。AtCoder用の手元環境をもう少し整備したい思いです。

問題

atcoder.jp

700点の割には単純な問題だと思います。

package main

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

var sc *bufio.Scanner

func nextStr() string {
    sc.Scan()
    return sc.Text()
}

func nextInt() int {
    sc.Scan()
    i, e := strconv.Atoi(sc.Text())
    if e != nil {
        panic(e)
    }
    return i
}

func main() {
    sc = bufio.NewScanner(os.Stdin)
    sc.Buffer(make([]byte, 0), 1000000001*3)
    sc.Split(bufio.ScanWords)
    n := nextInt()

    ans := 0
    aPrev := 0
    for i := 0; i < n; i++ {
        a := nextInt()
        switch {
        case a > i || a > aPrev+1:
            fmt.Println(-1)
            return
        case a == aPrev+1:
            ans++
        default:
            ans += a
        }
        aPrev = a
    }
    fmt.Println(ans)
}

入力例1について、0 1 / 1 2のように1ずつ増加する部分列で分解してみます。すると、後者の部分列を2回の操作で生成した後に、前者の部分列を1回の操作で生成するという手順が見えてきます。このように、1ずつ増加する部分列を後ろから組み上げていくことで全体の数列をと等しくすることができます。

ここで考えるのは以下の2点です。

1. どのような場合にと等しくすることができるか。
2. 操作回数は最小で何回になるか。

と等しくすることができない場合について考えると、数列0 1 2 ...の各要素と同じ位置でより大きな値が入る場合が挙げられます。また連続する2つの要素について、前の要素より後の要素が2以上大きい場合にもと等しくすることができません。逆にそれ以外の場合はと等しくすることができます。

残った操作回数の最小値は以下のようにして求めることができます。

1. 要素を前から順番に見て、前の要素より値がちょうど1大きい場合は回数を1増やす。
2. 前の要素と同じかそれ以下の値の場合は、その値の数だけ回数を増やす。

雑記

• またコンテスト参加していない期間が長かったので今週のコンテストは出られるように準備をしておきます。