GCJ Round1Aに参加。無事突破できました。
Cの2Incorrectが無ければ1ページ目に残れたのに残念。
とはいえQualification Round以外の満点は初めてなのでうれしいです。
https://code.google.com/codejam/contest/4224486/dashboard#s=p0
問題
Kaylinはキノコが好きで、目の前の皿にキノコがあるとそれを食べる。
また、Bartholomewは任意のタイミングでキノコを皿に追加できる。
一定間隔毎に皿のキノコの数を数えると、M[i]となっていた。
Kaylinが次の手順でそれぞれキノコを食べていたと仮定するとき、食べたキノコの最小数を求めよ。
- (皿にキノコがある限り)任意の数を食べる。
- (皿にキノコがある限り)一定のペースで任意の数を食べる。
解法
前者の場合、直前の状態よりキノコが減っていれば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); }
まとめ
内容は大したことないが、問題文が長くて理解が難しすぎる…。