CodeChef May Cook-off 2011

CodeChef May Cook-off 2011（1:00~3:30)

■Popular Rice Recipe

やるだけ．

view plainprint?

1. import java.util.*;  
2. import java.lang.*;  
3. import java.math.*;  
4. import java.io.*;  
5.   
6. import static java.lang.Math.*;  
7. import static java.util.Arrays.*;  
8.   
9. public class Main{  
10.  Scanner sc=new Scanner(System.in);  
11.   
12.  int INF=1<<28;  
13.  double EPS=1e-9;  
14.   
15.  void run(){  
16.   int caze=sc.nextInt();  
17.   for(int k=0; k<caze; k++){  
18.    int n=sc.nextInt();  
19.    HashMap<String, Integer> map=new HashMap<String, Integer>();  
20.    int ans=0;  
21.    for(int i=0; i<n; i++){  
22.     String s=sc.next();  
23.     int p=sc.next().equals("+")?1:-1;  
24.     if(map.containsKey(s)){  
25.      ans-=map.get(s);  
26.     }  
27.     ans+=p;  
28.     map.put(s, p);  
29.    }  
30.    println(""+ans);  
31.   }  
32.  }  
33.   
34.  void println(String s){  
35.   System.out.println(s);  
36.  }  
37.   
38.  void print(String s){  
39.   System.out.print(s);  
40.  }  
41.   
42.  void debug(Object... os){  
43.   System.err.println(Arrays.deepToString(os));  
44.  }  
45.   
46.  public static void main(String[] args){  
47.   new Main().run();  
48.  }  
49. }  

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

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main{
 Scanner sc=new Scanner(System.in);

 int INF=1<<28;
 double EPS=1e-9;

 void run(){
  int caze=sc.nextInt();
  for(int k=0; k<caze; k++){
   int n=sc.nextInt();
   HashMap<String, Integer> map=new HashMap<String, Integer>();
   int ans=0;
   for(int i=0; i<n; i++){
    String s=sc.next();
    int p=sc.next().equals("+")?1:-1;
    if(map.containsKey(s)){
     ans-=map.get(s);
    }
    ans+=p;
    map.put(s, p);
   }
   println(""+ans);
  }
 }

 void println(String s){
  System.out.println(s);
 }

 void print(String s){
  System.out.print(s);
 }

 void debug(Object... os){
  System.err.println(Arrays.deepToString(os));
 }

 public static void main(String[] args){
  new Main().run();
 }
}

■Distribute idlis Equally

シミュレーションなので，やるだけですが，時間内にACを取れませんでした．
原因はPriorityQueueにおいてremove()を使っていたことです．
removeを使うと，計算量は，
O((A number of times)*n*(A number of test cases))
となり，TLEしてしまうのです．
実際，removeを使わずに実装すれば，
O((A number of times)*log(n)*(A number of test cases))
となるので，余裕で間に合います．
以下，Practiceにて通ったコード．

view plainprint?

1. import java.util.*;  
2. import java.lang.*;  
3. import java.math.*;  
4. import java.io.*;  
5.   
6. import static java.lang.Math.*;  
7. import static java.util.Arrays.*;  
8.   
9. public class Main{  
10.  Scanner sc=new Scanner(System.in);  
11.   
12.  int INF=1<<28;  
13.  double EPS=1e-9;  
14.   
15.  int n;  
16.  int[] a;  
17.   
18.  void run(){  
19.   int t=sc.nextInt();  
20.   for(int j=0; j<t; j++){  
21.    n=sc.nextInt();  
22.    a=new int[n];  
23.    for(int i=0; i<n; i++){  
24.     a[i]=sc.nextInt();  
25.    }  
26.    println(solve()+"");  
27.   }  
28.  }  
29.   
30.  int solve(){  
31.   int sum=0;  
32.   for(int e : a){  
33.    sum+=e;  
34.   }  
35.   if(sum%n!=0){  
36.    return -1;  
37.   }  
38.   PriorityQueue<R> que1=new PriorityQueue<R>();  
39.   PriorityQueue<R> que2=new PriorityQueue<R>();  
40.   for(int e : a){  
41.    que1.add(new R(e));  
42.    que2.add(new R(-e));  
43.   }  
44.   int t;  
45.   for(t=0;; t++){  
46.    R p=que1.poll();  
47.    for(;p.f;){  
48.     p=que1.poll();  
49.    }  
50.    p.f=true;  
51.    R q=que2.poll();  
52.    for(;q.f;){  
53.     q=que2.poll();  
54.    }  
55.    q.f=true;  
56.    int min=p.v;  
57.    int max=-q.v;  
58.    if(min==max){  
59.     break;  
60.    }  
61.    int r=(int)((max-min+1)/2.0);  
62.    min+=r;  
63.    max-=r;  
64.    que1.add(new R(min));  
65.    que2.add(new R(-min));  
66.    que1.add(new R(max));  
67.    que2.add(new R(-max));  
68.   }  
69.   return t;  
70.  }  
71.   
72.  class R implements Comparable<R>{  
73.   int v;  
74.   boolean f;  
75.   R(int v){  
76.    this.v=v;  
77.   }  
78.   @Override  
79.   public int compareTo(R r){  
80.    return v-r.v;  
81.   }  
82.  }  
83.    
84.  void println(String s){  
85.   System.out.println(s);  
86.  }  
87.   
88.  void print(String s){  
89.   System.out.print(s);  
90.  }  
91.   
92.  void debug(Object... os){  
93.   System.err.println(Arrays.deepToString(os));  
94.  }  
95.   
96.  public static void main(String[] args){  
97.   new Main().run();  
98.  }  
99. }  

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

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main{
 Scanner sc=new Scanner(System.in);

 int INF=1<<28;
 double EPS=1e-9;

 int n;
 int[] a;

 void run(){
  int t=sc.nextInt();
  for(int j=0; j<t; j++){
   n=sc.nextInt();
   a=new int[n];
   for(int i=0; i<n; i++){
    a[i]=sc.nextInt();
   }
   println(solve()+"");
  }
 }

 int solve(){
  int sum=0;
  for(int e : a){
   sum+=e;
  }
  if(sum%n!=0){
   return -1;
  }
  PriorityQueue<R> que1=new PriorityQueue<R>();
  PriorityQueue<R> que2=new PriorityQueue<R>();
  for(int e : a){
   que1.add(new R(e));
   que2.add(new R(-e));
  }
  int t;
  for(t=0;; t++){
   R p=que1.poll();
   for(;p.f;){
    p=que1.poll();
   }
   p.f=true;
   R q=que2.poll();
   for(;q.f;){
    q=que2.poll();
   }
   q.f=true;
   int min=p.v;
   int max=-q.v;
   if(min==max){
    break;
   }
   int r=(int)((max-min+1)/2.0);
   min+=r;
   max-=r;
   que1.add(new R(min));
   que2.add(new R(-min));
   que1.add(new R(max));
   que2.add(new R(-max));
  }
  return t;
 }

 class R implements Comparable<R>{
  int v;
  boolean f;
  R(int v){
   this.v=v;
  }
  @Override
  public int compareTo(R r){
   return v-r.v;
  }
 }
 
 void println(String s){
  System.out.println(s);
 }

 void print(String s){
  System.out.print(s);
 }

 void debug(Object... os){
  System.err.println(Arrays.deepToString(os));
 }

 public static void main(String[] args){
  new Main().run();
 }
}

■Result

----o

これは酷い…．