Official

B - Better Students Are Needed! Editorial by physics0523


\(N \le 1000\) なので、ひとり合格者を決める際に \(N\) 人の候補者を全員調べるような解法でもこの問題に正解できますが、割愛します。
今回は、整数のソートを使って小技的な解法でこの問題に正解することを考えます。

まず、 1. での合格者を決める手続きについて考えます。
\(C_i = 10000 \times (100-A_i) + i\) という値を考え、この値についてソートすることを考えます。 例えば \(A=(95,70,100,85)\) とすると \(C=(50001,300002,3,150004)\) となり、これをソートすると \((3,50001,150004,300002)\) となります。(\(C_i\)\(10000\) で割った余りが受験者の番号に対応することに注意してください。)
\(C_i\) をソートすると、 (\(A_i\) の大きい順) \(\rightarrow\) (受験者の番号の小さい順) の優先順位でソートできます。
理由: 受験番号の差は、どれだけ大きくても \(999\) です。ところが、得点 \(A_i\)\(1\) 点違うだけでも \(C_i\) には \(10000\) の差が生じるので、これにより得点 \(A_i\) が優先されたソートが実現します。

これ以降の段階でも同様のことを行えば、この問題に正解することができます。

実装例(C++):

#include<bits/stdc++.h>

using namespace std;

int main(){
  int n,x,y,z;
  cin >> n >> x >> y >> z;
  vector<int> a(n+5),b(n+5);
  for(int i=1;i<=n;i++){cin >> a[i];}
  for(int i=1;i<=n;i++){cin >> b[i];}
  vector<bool> passed(n+5,false);

  vector<int> c;
  for(int i=1;i<=n;i++){
    c.push_back(10000*(100-a[i])+i);
  }
  sort(c.begin(),c.end());
  for(int i=0;i<x;i++){
    passed[c[i]%10000]=true;
  }

  c.clear();
  for(int i=1;i<=n;i++){
    if(!passed[i]){
      c.push_back(10000*(100-b[i])+i);
    }
  }
  sort(c.begin(),c.end());
  for(int i=0;i<y;i++){
    passed[c[i]%10000]=true;
  }

  c.clear();
  for(int i=1;i<=n;i++){
    if(!passed[i]){
      c.push_back(10000*(200-(a[i]+b[i]))+i);
    }
  }
  sort(c.begin(),c.end());
  for(int i=0;i<z;i++){
    passed[c[i]%10000]=true;
  }

  for(int i=1;i<=n;i++){
    if(passed[i]){cout << i << "\n";}
  }
  return 0;
}

posted:
last update: