情報オリンピック2009-2010 本選３ つらら
N本のつららがあり、それぞれの最初の長さが配列aで与えられる。最初の長さは全て異なる。つららは左右両方のつららよりも長い場合のみ、１時間に１伸びる。ただし両端のつららに関してはご想像の通りです、お察しください*1。つららは長さLになった瞬間折れ、長さ0として扱う。全てのつららが折れるまでの時間を求めよ。
N <= 100000, L <= 50000, a[k] < L
解法の解法
とにかく脳内シミュレーション。まず一番長いつららは必ず開始時に伸び始め、L-a[それ]時間後に折れる。次に適当な(任意の)つららに注目すると、左右を含めた３本のうち一番長ければ同様に開始直後から伸びて折れる。それまで左右のつららは伸びない。→それでは、一番短かったら？左右のつららは折れることによってしか短くならない。つまり両方のつららが折れた後、L-a[それ]時間後に折れる。２番目に長いときとか略。これらを総合すると、
- 初期状態で一番長いつららは何も考えずにいつ折れるか分かる。
- あるつららが折れる長さは自分より初期状態で長いつららがいつ折れるか分かれば分かる。
一番長いつららは開幕伸び出すことはまずわかるでしょ、で、２番目に長いつららがその隣にあったとしたら、それが折れた後で伸び出す。隣ではなかったら開始直後から伸び出すね。１番目と２番目が分かっていればそれ以外はまだ分かってなくても３番目が…、といった感じ。N=10^5でO(n^2)がだめでO(nlogn)(つまりはソート)がOKという感じと長いものから順番にやればいろいろうまくいきそうな感じを感じとってください。
まずは長さで添え字をソートします。qsortに使うcompare関数気持ち悪いです＞＜。これだからCは…。
ばかでかい配列をスタックに確保するのは危ないのでやめましょう。スタックってデフォルトは1MBとかそんなもんじゃなかったっけ…。知ってる人はスコープをそのままでstaticをつけますが、よく分からないならグローバルに出せばいいでしょう。個の場合、どちらでも0で初期化されます。
その添え字に従い操作を行います。左右のつららが落ちるまでの時間の大きい方が自分が伸び始めるまでの時間です。自分より短いつららの場合初期化された0が入っていることを利用するとコードが節約できますが、意味が分かりにくくなってます。両方とも自分より短いなら両方に0が入っていますので最大値は0です。つまり待ち時間は0となります。
#include <stdio.h> #include <stdlib.h> int N, L; int a[100000]; int compare(const void *pa, const void *pb) { return a[*(const int *)pb] - a[*(const int *)pa]; } int main() { static int inds[100000]; static int times[100000]; int i; int ans = 0; scanf("%d%d", &N, &L); for (i = 0; i < N; i++) { scanf("%d", &a[i]); inds[i] = i; } qsort(inds, N, sizeof(int), compare); for (i = 0; i < N; i++) { int ind = inds[i]; int time = L - a[ind]; int pretime = 0; if (ind > 0 && pretime < times[ind - 1]) { pretime = times[ind - 1]; } if (ind < N - 1 && pretime < times[ind + 1]) { pretime = times[ind + 1]; } times[ind] = time + pretime; } for (i = 0; i < N; i++) { ans = times[i] > ans ? times[i] : ans; } printf("%d\n", ans); return 0; }
ちなみに風邪＋睡魔＋ブランクの中やったところ、１時間ほど（ｒｙ
２時間/制限時間４時間で２つやったものの、２とか無理じゃね
まあ万が一できたら書きますが、一般人の思考プロセスを書くのが目的なので無理だったら無理です。
なんかみんなが終了後DP*2、DPと言っていたらしいですが、私にはあんまりそういう感じに思えませんでした。いや解説書いてたらものすごくDPくさくなったが。nlognでソートして長いものからやればnで終了、みたいな。いや、それがDPの本質なのかもしれんのう…。
