TopCoder SRM 479

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

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

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

view plainprint?

1. import java.util.*;  
2. import java.math.*;  
3. import java.lang.*;  
4.   
5. public class TheCoffeeTimeDivOne{  
6.   public long find(int n, int[] tea){  
7.     long cost=0;  
8.     for(int i=0;i<tea.length;i++) tea[i]=-tea[i];  
9.     Arrays.sort(tea);  
10.     for(int i=0;i<tea.length;i++) tea[i]=-tea[i];  
11.     for(int i=0;i<tea.length;i++){  
12.       if(i%7==0){  
13.         cost+=47;  
14.         cost+=tea[i];  
15.       }else{  
16.         cost+=tea[i-1]-tea[i];  
17.       }  
18.       if(i%7==6 || i==tea.length-1){  
19.         cost+=tea[i];  
20.       }  
21.       cost+=4;  
22.     }  
23.     long cost2=0;  
24.     int px=0;  
25.     Arrays.sort(tea);  
26.     int lastX=0;  
27.     int lastI=0;  
28.     boolean[] has=new boolean[n+1];  
29.     for(int i=0;i<tea.length;i++)  
30.       has[tea[i]]=true;  
31.     for(int x=n,i=0;x>=1;x--){  
32.       if(has[x])  
33.         continue;  
34.       if(i%7==0){  
35.         cost2+=47;  
36.         cost2+=x;  
37.       }else{  
38.         cost2+=px-x;  
39.       }  
40.       if(i%7==6){  
41.         cost2+=x;  
42.       }  
43.       cost2+=4;  
44.       lastI=i;  
45.       lastX=x;  
46.       px=x;  
47.       i++;  
48. //      System.out.println("i="+i);  
49. //      System.out.println("x="+x);  
50. //      System.out.println(""+cost2);  
51.     }  
52.     if(lastI%7!=6)  
53.       cost2+=lastX;  
54. //    System.out.println("cost="+cost);  
55. //    System.out.println("cost2="+cost2);  
56.     return cost+cost2;  
57.   }  
58. }  

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が回復しました…
もっと早く提出したいものです…