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.と2.が無駄な処理になっており、全ての操作回数を定めた上で宝石を取り出す回数の合計も定めているため見た目が複雑になったり、計算量も[tex:O(R4\log R)(R=\min(N,K))]と余分にかかったりしています。
雑記
- 今週あたりPaizaの練習問題を扱うこともあるかもしれません。(スキルチェック問題は扱いませんよ!)