CodeChef May Cook-off 2011

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

■Popular Rice Recipe

やるだけ．

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にて通ったコード．

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

これは酷い…．