2010年8月16日月曜日

TopCoder SRM 479

SRM 479(8/15 1:00~3:00)

今日こそはRatingを上昇させると意気込みましたが…

■TheCoffeeTimeDivOne(Div1 Easy)
コーヒーと紅茶を乗客に配るのにかかる時間を求める問題.
最初はシンプルに求められるのかと思いましたが,無理そうだったので,44,777,777回のループに.
何とか強引に書き上げ,提出.しかし,最大ケースを投げるとTLEすることが判明.
ループ内の探索をboolean配列によるテーブルに直した所,無事通ったので再提出.
この再提出のせいで,得点は最低点の75.0p.もっと冷静に実装すれば一発で解けた問題だったと思います.

import java.util.*;
import java.math.*;
import java.lang.*;

public class TheCoffeeTimeDivOne{
public long find(int n, int[] tea){
long cost=0;
for(int i=0;i<tea.length;i++) tea[i]=-tea[i];
Arrays.sort(tea);
for(int i=0;i<tea.length;i++) tea[i]=-tea[i];
for(int i=0;i<tea.length;i++){
if(i%7==0){
cost+=47;
cost+=tea[i];
}else{
cost+=tea[i-1]-tea[i];
}
if(i%7==6 || i==tea.length-1){
cost+=tea[i];
}
cost+=4;
}
long cost2=0;
int px=0;
Arrays.sort(tea);
int lastX=0;
int lastI=0;
boolean[] has=new boolean[n+1];
for(int i=0;i<tea.length;i++)
has[tea[i]]=true;
for(int x=n,i=0;x>=1;x--){
if(has[x])
continue;
if(i%7==0){
cost2+=47;
cost2+=x;
}else{
cost2+=px-x;
}
if(i%7==6){
cost2+=x;
}
cost2+=4;
lastI=i;
lastX=x;
px=x;
i++;
// System.out.println("i="+i);
// System.out.println("x="+x);
// System.out.println(""+cost2);
}
if(lastI%7!=6)
cost2+=lastX;
// System.out.println("cost="+cost);
// System.out.println("cost2="+cost2);
return cost+cost2;
}
}


■Challenge
流石に怖くて出来ませんでした…

■Result
○×× 0 0
75.0p

■Rating
1207 -> 1282

土壇場でRatingが回復しました…
もっと早く提出したいものです…

0 件のコメント: