B. Space Emergency

2011-05-22

01:19 |

0..N の星を順に移動したい。星間の距離は与えられる。１時間につき0.5単位進める。
ブーストを使うと１時間につき１単位進める。
ブーストは最大 L 個使えて、別々な星のところに置ける。
ブーストを準備するのに t 時間かかる。スタートと同時に全ブーストの準備を開始できる。
最短何時間で星 N に辿りつける？

Small はブーストの数が最大２なので、総当りで。少し考えてアイデアが出なかったら泥臭く確実に点を取りに行く作戦。
L==0 の場合、L==1 の場合、L==2 の場合でコードを分けたりして相当泥臭いｗｗ
着実に Small クリア。

Large は、0<=L<=N なので計算量がやばそう。
基本的には距離が長いところから順にブーストを割り当てていけばいいが、t が大きい時はブーストが準備できずに通りすぎてしまう。
その辺考慮してどういう戦略がいいのか思い浮かばなかった。
C に行って戻ってきて、とりあえず使用ブースト数が L-1 のときの解にブーストを１個最適に追加したものが最適解になりそうな気がしたので１個ずつ追加していく O(N^2) のコードを書いたが Large じゃやっぱり終わらず。

解説や上位陣のコードを見ると、単純に t 秒以降にいるエリアの中で距離でソートして短縮できる時間が大きい物順に L 個取るという方法で行けるみたい。
言われてみるとそうだ orz
t 秒以降に行けるエリアは、その前にブーストを置くことで変わってしまうのではないかと思ってわざわざ難しく考えてしまったが、そもそも t 秒より前にブーストを置いても効果がないので杞憂であった。
このくらい解けないとまずいな....

int main()
{
	int T;
	cin>>T;
	//cout<<T<<endl;
	REP(ttt, T)
	{
		ll L,t,N,C;
		cin>>L>>t>>N>>C;
		int v[N];
		REP(i, C) cin>>v[i];
		FOR(i, C, N) v[i]=v[i-C];
		//REP(i, N) cout<<v[i]<<endl;;
		
		ll mintt = -1;
		if(L==0)
		{
			ll tt=0;
			REP(i, N)
			{
				tt+=v[i]*2;
			}
			//cout<<"tt "<<tt<<endl;
			if(mintt==-1 || tt<mintt) mintt=tt;
		}
		else if(L==1)
		{
			FOR(ba, 0, N)
			{
				// use in ba
				ll tt=0;
				REP(i, N)
				{
					if(i==ba)
					{
						if(t<=tt) tt+=v[i];
						else if(t<tt+v[i]*2) tt+= (t-tt) + v[i]-(t-tt)/2;
						else tt+=v[i]*2;
					}
					else
					{
						tt+=v[i]*2;
					}
				}
				if(mintt==-1 || tt<mintt) mintt=tt;
			}
		}
		else
		{
			FOR(ba, 0, N-1)
			FOR(bb, ba, N)
			{
				// use in ba, bb
				ll tt=0;
				REP(i, N)
				{
					if(i==ba||i==bb)
					{
						if(t<=tt) tt+=v[i];
						else if(t<tt+v[i]*2) tt+= (t-tt) + v[i]-(t-tt)/2;
						else tt+=v[i]*2;
					}
					else
					{
						tt+=v[i]*2;
					}
				}
				if(mintt==-1 || tt<mintt) mintt=tt;
			}
		}
		
		cout<<"Case #"<<ttt+1<<": "<<mintt<<endl;
	}
	return 0;
}