読者です 読者をやめる 読者になる 読者になる

kmjp's blog

競技プログラミング参加記です

Google Code Jam 2015 Round 1A : A. Mushroom Monster

GCJ

GCJ Round1Aに参加。無事突破できました。
Cの2Incorrectが無ければ1ページ目に残れたのに残念。
とはいえQualification Round以外の満点は初めてなのでうれしいです。
https://code.google.com/codejam/contest/4224486/dashboard#s=p0

問題

Kaylinはキノコが好きで、目の前の皿にキノコがあるとそれを食べる。
また、Bartholomewは任意のタイミングでキノコを皿に追加できる。

一定間隔毎に皿のキノコの数を数えると、M[i]となっていた。
Kaylinが次の手順でそれぞれキノコを食べていたと仮定するとき、食べたキノコの最小数を求めよ。

  1. (皿にキノコがある限り)任意の数を食べる。
  2. (皿にキノコがある限り)一定のペースで任意の数を食べる。

解法

前者の場合、直前の状態よりキノコが減っていればKaylinが食べたと判断し、増えていればBartholomewが追加したと考えられるのでsum(max(M[i]-M[i+1],0))を答えればよい。

後者の場合、食べるペースPはP=max(0,max(M[i]-M[i+1]))である。
よってKaylinの食べるようは(皿にないときは食べられないので) sum(min(P,M[i]))である。

int N,M[2020];

void solve(int _loop) {
	int f,i,j,k,l,x,y;
	ll Y=0,Z=0;
	
	cin>>N;
	FOR(i,N) cin>>M[i];
	
	FOR(i,N-1) Y+=max(M[i]-M[i+1],0);
	int pace=0;
	FOR(i,N-1) pace=max(pace,max(M[i]-M[i+1],0));
	FOR(i,N-1) Z+=min(pace,M[i]);
	
	_P("Case #%d: %lld %lld\n",_loop,Y,Z);
}

まとめ

内容は大したことないが、問題文が長くて理解が難しすぎる…。

広告を非表示にする