白駿1158ジョセフス

13272 ワード
アルゴリズム#アルゴリズム# テキストリンク

ジョセフ?初めて聞いた名前ですが、問題を読んで少し考えてみましたが、どこで触れたか分かりません.
制限事項の最大値は5000なので、時間の複雑さを考慮する必要はないと判断し、結果的に失算しました.
最初に作成されたコードは次のとおりです.
const fs = require('fs');
let input = fs
  .readFileSync('./input.txt')
  .toString()
  .trim()
  .split(' ')
  .map((v) => +v);
const [N, K] = input;

const queue = Array.from({ length: N }, (_, i) => i + 1);
let answer = '';

let cnt = 0;
while (queue.length) {
  if (cnt === K - 1) {
    answer += `${queue[0]}, `;
    queue.splice(0, 1);
    cnt = 0;
  } else {
    for (let i = 0; i < K - 1; i++) {
      queue[queue.length] = queue[0];
      queue.splice(0, 1);
      cnt++;
    }
  }
}
answer = answer.slice(0, -2);
console.log(`<${answer}>`);
cntは変数であり,繰り返し文により最初に出現した要素を最後尾に置き,spliceの方法で削除し,Kとカウントされた瞬間に答え変数に追加し,spliceにより削除を実現する.
しかし、つなぎ方のためか、5000でテストしてみましたが、本当に時間がかかりました.
だから再包装してコードを修正しました.
const fs = require('fs');
let input = fs
  .readFileSync('./input.txt')
  .toString()
  .trim()
  .split(' ')
  .map((v) => +v);
const [N, K] = input;

const queue = Array.from({ length: N }, (_, i) => i + 1);
let answer = '';

while (queue.length) {
  for (let i = 0; i < K; i++) {
    queue.push(queue.shift());
  }

  answer += `${queue.pop()}, `;
}
answer = answer.slice(0, -2);
console.log(`<${answer}>`);
push, pop法はO(1)時間の複雑さを有するため,積極的に用いることができ,spliceの使用を抑制した.
カットを極力抑える.
[PG]JOYSTIC
JavaSE国際化の簡単な例