ABC141 C - Attack Survival

備忘録

問題

atcoder.jp

回答

"use strict"
 
function Main(input) {
  input = input.trim().split('\n');
  const N = Number(input[0].trim().split(' ')[0]);
  const K = Number(input[0].trim().split(' ')[1]);
  const Q = Number(input[0].trim().split(' ')[2]);
  const A = input.slice(1, Q+1).join(' ').trim().split(' ').map(Number);
  const ary = new Array(N).fill(K)
 
  let ans = {};
  for(let i=0; i<Q; i++){
    ans[A[i]-1] = ans[A[i]-1] ? ans[A[i]-1] + 1 : 1;
  }
 
  for(let i=0; i<N; i++){
    let tmp = 0;
    if(ans[i]){
      tmp = Q - ans[i];
    } else {
      tmp = Q;
    }
 
    if(K - tmp > 0){
      console.log('Yes');
    } else {
      console.log('No');
    }
  }
}
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

考え方

初期ポイントはK、誰かが正解すると正解した人以外ポイントが-1されて、
問題はQ個出題される。
つまり回答した回数をAとするとき、最後に残るポイントはK - Q + Aとなる。
この最後に残ったポイントが0以上の時Yes、0以下の時Noを出力すればよい。

単純にforを2つ重ねてAiを順番に探索、Ai以外のポイントを-1とすると、
Nが最大1e5のため、時間超過になりそうだった。
そのため、はじめに回答者をkey、回答回数をvalueとした連想配列を作り、
連想配列に対して、K - 連想配列のvalue > 0を順に行うことで、答えを出した。
（回答数がない場合、Qポイント失っていると考えることができる）