SRM 518 500pt: ConvexSequence

問題概要

整数列(長さN<50, 要素x<10^9)が与えられる。各要素を減らして凸になるようにしたい。最小いくつ減らす必要があるか求める問題。

考えたこと

• 前2つを覚えてDP？でも前2つのとりうる値の範囲が広すぎてアレだ。
• 実は特徴点が全部列挙できたりしないんだろうか。無理っぽいなあ。
• 最小値をどれにするか全探索して増加列と減少列に分離する？
• 最小値はdecする必要が無いように思うけど、ほんとかなあ？
• じゃあ、両端から狭めていく？
• 区間に関するDP？
• 全部ダメだ。本番は手も足も出ずに完封負けした。
• チャレンジフェーズ。やけに出してる人が多いが見てみるとみんな局所改善の繰り返し。
• 本当に？とおもうより先に、何でみんなこれが見えるの？という驚きが先にきた。
  • でも今にして思えば、提出率がやたら高い問題って貪欲っぽい解法が多い気がする。
  • もちろん罠で大撃墜祭になることもあるわけだけど。
• 一応greedy解法が正解を与えることと、時間内に終了することはSRM直後のTwitterなどを見て理解したつもり。
  • 値が下がるしかないから、この要素はある値より小さくなければダメ、という制約を順次適用していけばよい、という考え方らしい。
• でもこれを自力でちゃんと思いつく自信は全くない。

practiceで通ったコード

#include <algorithm>
#include <vector>
#include <cstdio>
using namespace std;

typedef long long int64;

struct ConvexSequence {

	int64 getMinimum(vector <int> a) {
		const int N = a.size();

		int64 ret = 0;

		for(;;){
			bool update = false;

			for(int i=1; i<N-1; i++){
				if(a[i-1] + a[i+1] < 2*a[i]){
					int diff = a[i] - (a[i-1] + a[i+1]) / 2;
					ret += diff;
					a[i] -= diff;
					update = true;
				}
			}

			if(!update){
				break;
			}
		}

		return ret;
	}

};