2015-08-30

CodeForces Round#318 Div2D/Div1B Bear and Blocks

http://codeforces.com/contest/574/problem/D

ブロックを積み上げて作られたN個の塔が1列に並んでいる状況を考える。各塔は同じサイズのブロックが積まれていて、その高さが配列 A[i] で与えられる

それらの塔を、境界となっているブロックを取り除いていく操作を繰り返していくことを考える

全てのブロックを取り除くのに必要な手数を求めよ

（制約）1 ≤ N ≤ 10^5, 1 ≤ A[i] ≤ 10^9

・本番は分からなくて、左から見て右から見てっていう方針だけ思いついたところで寝落ち。

・翌日ジョギング中によく考えると、例えば左から見て増加している局面では必ず左のブロックがなくならない限りは影になっていることに気づく。

・と言うわけで画を描いて、左から見て増加している場合と減少/維持している場合でそれぞれ考察。

・さて、高さが低ければ上の画にあるように各ブロックの上と左をみてそのブロックがいつ消えるかを決定していけばよいが、高さは10^9であり一つ一つのブロックの状態を覚えておくのはTLE/MLEする。

・座標圧縮・・・？これもワーストでN=10^6メモリ必要となり、O(N^2)は今回の制約だと厳しい。

・実は必要なのは一番下の段がいつ消えるかだけなので、

　・増加時は必ず「１つ前の段の最下段が消えるターン+1」となり、

　・減少/維持時は、左から消える場合は「１つ前の段の最下段が消えるターン+1」、上から消える場合は「塔の高さ」のターン数が必要なのでそれらのうちの小さい方

で、最下段の消えるターン数だけを計算することが出来る。

・あとは右から消える場合を同様に計算し、小さい方を採用すればよい。

・「左から見て右から見て」でOKな理由としては、左からみて消えたブロックによって次に右から見て消えるブロックが増えることは無いことから従う。

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;

class TEST{
	static void Main(){
		Sol mySol =new Sol();
		mySol.Solve();
	}
}

class Sol{
	public void Solve(){
		
		int[] L=new int[N];
		L[0]=1;
		for(int i=1;i<N;i++){
			if(A[i]>A[i-1]){
				L[i]=L[i-1]+1;
			}else{
				L[i]=Math.Min(L[i-1]+1,A[i]);
			}
		}
		
		int[] R=new int[N];
		R[N-1]=1;
		for(int i=N-2;i>=0;i--){
			if(A[i]>A[i+1]){
				R[i]=R[i+1]+1;
			}else{
				R[i]=Math.Min(R[i+1]+1,A[i]);
			}
		}
		
		int[] LR=new int[N];
		for(int i=0;i<N;i++)LR[i]=Math.Min(L[i],R[i]);
		Console.WriteLine(LR.Max());
		
	}
	int N;
	int[] A;
	public Sol(){
		N=ri();
		A=ria();
	}

	static int ri(){return int.Parse(Console.ReadLine());}
	static int[] ria(){return Array.ConvertAll(Console.ReadLine().Split(' '),e=>int.Parse(e));}
}

これは本番解けてもよさそうだが本番中は全然正解に辿り着かなかったので練習不足と言う感じ。

最下段だけ考えればよいというところがなかなか良い問題と感じる。

kuuso1の日記

2015-08-30

CodeForces Round#318 Div2D/Div1B Bear and Blocks