Good Bye 2018 : F. New Year and the Mallard Expedition

Eよりはこっちの方が易しかった。
https://codeforces.com/contest/1091/problem/F

問題

１次元のフィールドがある。
各区間は平地・水場・溶岩のいずれかである。
これらを歩く・泳ぐ・飛ぶのいずれかで移動していく。

• 飛ぶ場合はどんな地形も移動できる。距離１移動するのに時間が１かかり、スタミナを１消費する。
• 平地は歩いて移動することもできる。距離１移動するのに時間が３かかり、スタミナを１増加する。
• 水場は泳いで移動することもできる。距離１移動するのに時間が５かかり、スタミナを１増加する。

同じ場所を行ったり戻ったりしてもよいし、移動方法は整数時間以外に切り替えてもよい。
フィールドの端から端に移動するまでの最短時間を求めよ。

解法

以下考察。

• 溶岩をわたるためには、その距離以上に、それまでの平地・水場で歩き・泳ぎでスタミナを溜めなければならない。
  • できれば時間のかからない平地で溜める方が良い。
  • 平地・水場の移動がてらスタミナがたまりきらない場合、平地・水場を無駄に行き来してスタミナを溜める。もし手前に平地があればそちらで溜めるのが良い。
• 水場を移動する際、手前に平地があればそこを歩いておいて、水場を飛ぶのが良い。平地が無い場合、水場を半分泳いで半分飛ぶ。
• 平地を移動する際、（上記溶岩や水場に向けスタミナを溜めるための徒歩分を除き）まだ移動距離があるなら、半分歩いて半分飛ぶ。

上記を素直に実装すればよい。
まず最初に溶岩を処理し、その後平地・水場を後ろから順位処理していく。

int N;
ll L[101010],LS[101010];
string S;
map<ll,ll> G,W;
int C[202020][2]={};
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	ll ret=0;
	FOR(i,N) {
		cin>>L[i];
		LS[i+1]=LS[i]+L[i];
	}
	ret=LS[N];
	
	cin>>S;
	FOR(i,N) {
		C[i+1][0]=C[i][0];
		C[i+1][1]=C[i][1];
		if(S[i]=='W') {
			C[i+1][0]++;
			W[i]=L[i];
		}
		else if(S[i]=='G') {
			C[i+1][1]++;
			G[i]=L[i];
		}
		else {
			ll a=L[i];
			while(a && W.size()) {
				ll b=min(a,W.rbegin()->second);
				a-=b;
				W.rbegin()->second-=b;
				ret+=b*2;
				if(W.rbegin()->second==0) W.erase(W.rbegin()->first);
			}
			while(a && G.size()) {
				ll b=min(a,G.rbegin()->second);
				a-=b;
				G.rbegin()->second-=b;
				ret+=b*4;
				if(G.rbegin()->second==0) G.erase(G.rbegin()->first);
			}
			if(C[i][0]) {
				ret+=a*3;
			}
			else {
				ret+=a*5;
			}
			
		}
	}
	
	while(W.size()||G.size()) {
		if(W.size() && (G.empty()|| (W.rbegin()->first>G.rbegin()->first))) {
			ret+=W.rbegin()->second;
			W.erase(W.rbegin()->first);
		}
		else {
			while(G.rbegin()->second>0 && W.size()) {
				ll mi=min(G.rbegin()->second,W.rbegin()->second);
				ret+=mi*2;
				G.rbegin()->second-=mi;
				W.rbegin()->second-=mi;
				if(W.rbegin()->second==0) W.erase(W.rbegin()->first);
			}
			ret+=G.rbegin()->second*2;
			G.erase(G.rbegin()->first);
			
		}
		
	}
	cout<<ret<<endl;
	
}

まとめ

Div1の2000ptよりは簡単な気がする。