あるエンジニアのAtCoder奮闘記

東京都港区にあるアミフィアブル株式会社のエンジニアが、AtCoderで解いた問題について振り返ったりしていく会社公認のブログです。

AtCoder ABC 128 D - equeue (Go)

irisruneです。この土日のコンテストは不参加だったのもあり記事にするのは間に合いませんでした。

https://atcoder.jp/contests/abc128/tasks/abc128_d

"D"equeueとかけてるからD問題なんですかね。B、Cが難しければDも難しいときました。効率の良い方法を探そうとするとドツボにはまりそうな問題です。

package main

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

var sc *bufio.Scanner

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

func minInt(a, b int) int {
    if a < b {
        return a
    }
    return b
}

func maxInt(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func sumValue(jewels []int) int {
    ret := 0
    for _, j := range jewels {
        ret += j
    }
    return ret
}

func main() {
    sc = bufio.NewScanner(os.Stdin)
    sc.Split(bufio.ScanWords)
    n, k := nextInt(), nextInt()

    deque := make([]int, n)
    for i := range deque {
        deque[i] = nextInt()
    }

    ans := 0
    // i : 操作回数
    // j : 宝石を取り出す回数
    // m : 左から宝石を取り出す回数
    // l, r : 左右から宝石を取り出す処理を回す変数
    for i := 0; i <= minInt(k, n*2); i++ {
        for j := (i + 1) / 2; j <= minInt(i, n); j++ {
            for m := 0; m <= j; m++ {
                var jewels []int
                for l := 0; l < m; l++ {
                    jewels = append(jewels, deque[l])
                }
                for r := 0; r < j-m; r++ {
                    jewels = append(jewels, deque[n-1-r])
                }
                sort.Sort(sort.Reverse(sort.IntSlice(jewels)))
                jewels = jewels[0 : j-(i-j)]
                ans = maxInt(ans, sumValue(jewels))
            }
        }
    }

    fmt.Println(ans)
}

制約が非常に緩いので結局全探索するだけです。BもCも全探索だったような気はしますが全探索のアルゴリズムや実装を考える必要があるのでやや難しいとは思います。

今回取った全探索アルゴリズムは、

  1. 操作回数をR=0,1,\dots,\min(2N,K)回とおく。
  2. 宝石を取り出す回数をA+B=\lceil\frac{2}{R}\rceil,\dots,\min(R,K)回とおく。
  3. 左から宝石を取り出す回数をA=0,1,\dots,A+B回とおく。
  4. 右から宝石を取り出す回数をB回とおく。
  5. 取り出した宝石から価値の低い順に宝石を戻す動作をR-(A+B)回行う。
  6. 残った宝石の価値を合計する。

というものです。公式解説に変数名を揃えてみましたが、無駄に複雑なアルゴリズムになってるのがよくわかりますね。

主に1.と2.が無駄な処理になっており、全ての操作回数を定めた上で宝石を取り出す回数の合計も定めているため見た目が複雑になったり、計算量も[tex:O(R4\log R)(R=\min(N,K))]と余分にかかったりしています。

雑記

  • 今週あたりPaizaの練習問題を扱うこともあるかもしれません。(スキルチェック問題は扱いませんよ!)