Google Code Jam Round 1C A: Senate Evacuation - 不定期プログラミング覚え書き

問題

https://code.google.com/codejam/contest/4314486/dashboard#s=p0
政党とか議員とか難しい単語が出てきてる気がするけれど、要するに、
$n(\leq 26)$ 個の部屋に $P_i$ 人ずつの人がいて、
一度に1人or2人を部屋から屋外に出すことができる。
どこかの部屋に過半数の人数が存在しないように全員を屋外に出す方法を示せ、と言う問題。

考えたこと

基本は多い部屋から屋外に出していけば良いので優先度付きキュー使ってガシガシ消していけば良い。
サンプルにもあるけれど、A,B,Cの部屋に1人ずつ居る時にA,Bからひとりずつ屋外に出してしまうと、
C部屋1人だけが部屋の中にいると言う題意に背くシチュエーションが発生する点に注意(注1)。

(以下間違った検討)
あと、A部屋5人B部屋4人とか言う場合にA部屋から2人出してしまうとB部屋4人A部屋3人のB部屋過半数部屋になっちゃうので、
最大部屋の人数 == 2番めに人の多い部屋の人数+1の場合は最大部屋から1人だけを出してあげるほうが良さそう(注2)。
(↑今回の解法上で問題にはならなかったけれど、そもそもA部屋5人B部屋4人の時点で題意にそぐわないので、このようなケースは存在しなかった）

よって、
最大部屋の人数＞2番目に人の多い部屋の人数+1 ならば、最大部屋から2人排出
最大部屋の人数=2番目に人の多い部屋の人数+1 ならば、最大部屋から1人排出＊(注2)への対応
最大部屋の人数=2番めに人の多い部屋の人数で、現在人の居る部屋が3部屋ならば、最大部屋から1人排出＊(注1)への対応
最大部屋の人数=2番めに人の多い部屋の人数で、現在人の居る部屋が3部屋でないならば、最大部屋・2番めに人の多い部屋から1人ずつ排出

とすれば良い。

コード

int main(){
  int n_case;
  cin >> n_case;
  for( int loop = 0 ; loop < n_case ; loop++ ){
   int N;
   cin >> N;
   priority_queue<pair<int,int> > pq;
   for( int i = 0 ; i < N; i++){
      int P;
      cin >> P;
      pq.push(make_pair(P,i));
   }
   cout << "Case #" << loop+1 << ": ";
   while(pq.size()!=0){
      pair<int,int> p=pq.top();
      pq.pop();
      pair<int,int> q=pq.top();
      pq.pop();
      if( p.first > q.first+1 ){
         p.first-=2;
         cout <<(char)('A'+p.second);
         cout <<(char)('A'+p.second);
         cout <<" ";
      }
      else if(p.first == q.first+1 || pq.size()==1 ){
         p.first-=1;
         cout <<(char)('A'+p.second);
         cout <<" ";
      }
      else{
         p.first-=1;
         q.first-=1;
         cout <<(char)('A'+p.second);
         cout <<(char)('A'+q.second);
         cout <<" ";      
      }
      if(p.first!=0 )pq.push(p);
      if(q.first!=0 )pq.push(q);
   }
   cout << endl;
  }
  return 0;
}

微修正

最適手数以外の解でも認めると言うゆるい条件だったからまあ良いか、と言う気分で出してしまったけれど、
あまり筋の良い解法では無い気がした。
「最大部屋の人数=2番めに人の多い部屋の人数で、現在人の居る部屋が3部屋ならば、最大部屋から1人排出」
と言う方針も、最大部屋の人数=1である以外の場合は1人排出する必要無いし。
というわけで、以下のような書き方の方が若干賢い気がする。(Smallでpractice通過済)

int main(){
  int n_case;
  cin >> n_case;
  for( int loop = 0 ; loop < n_case ; loop++ ){
   int N;
   cin >> N;
   priority_queue<pair<int,int> > pq;
   for( int i = 0 ; i < N; i++){
      int P;
      cin >> P;
      pq.push(make_pair(P,i));
   }
   cout << "Case #" << loop+1 << ": ";
   while(pq.size()!=0){
      pair<int,int> p=pq.top();
      pq.pop();
      pair<int,int> q=pq.top();
      pq.pop();
      if( p.first >= q.first+1 ){
         p.first-=2;
         cout <<(char)('A'+p.second);
         cout <<(char)('A'+p.second);
         cout <<" ";
      }
      else if( p.first==1 && pq.size()==1 ){
         p.first-=1;
         cout <<(char)('A'+p.second);
         cout <<" ";
      }
      else{
         p.first-=1;
         q.first-=1;
         cout <<(char)('A'+p.second);
         cout <<(char)('A'+q.second);
         cout <<" ";      
      }
      if(p.first!=0 )pq.push(p);
      if(q.first!=0 )pq.push(q);
   }
   cout << endl;
  }
  return 0;
}