[伯俊]15729密室脱出-javascript


📌 質問する


https://www.acmicpc.net/problem/15729

📌 に答える

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "input.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\n");

let n = Number(input[0]);
let goal = input[1].split(" ").map(Number);

let arr = new Array(n).fill(0);
let cnt = new Array(n).fill(0);
let ans = 0;
for (let i = 0; i < arr.length; i++) {
  if (arr[i] !== goal[i] && cnt[i] % 2 === 0) {
    for (let j = 1; j <= 2; j++) {
      cnt[i + j]++;
    }
    ans++;
  }
  if (arr[i] === goal[i] && cnt[i] % 2 === 1) {
    for (let j = 1; j <= 2; j++) {
      cnt[i + j]++;
    }
    ans++;
  }
}
console.log(ans);
✔アルゴリズム:グリディ
ボタンを押すたびに並べ替えが更新されないのがポイントです.
✔ボタンを押すと、右側の2つのボタンも押されます.
✔0に初期化したシナリオをメモのシナリオと比較し、その他の場合はボタンを押します.
  • arr[i]とgoal[i]は異なり、cnt[i]は偶数
    結果は別の状況です.ボタンを数回押した後、現在の値は初期値arr[i]に等しい.したがって,ボタンを押すと,右側の2つのcnt配列が1増加する.
  • arr[i]とgoal[i]は異なり、cnt[i]は奇数
    結果は同じ状況です.ボタンは奇数押下状態であるため、現在値は初期値arr[i]ではない.だからボタンを押さない.
  • arr[i]はgoal[i]と等しく、cnt[i]は偶数である
    結果は同じ状況です.ボタンを数回押した後、現在の値は初期値arr[i]に等しい.だからボタンを押さない.
  • arr[i]はgoal[i]と同様、cnt[i]は奇数
    結果は別の状況です.ボタンを数回押した後、現在の値は初期値arr[i]ではないため、ターゲット[i]とは異なる.したがって,ボタンを押すと,右側の2つのcnt配列が1増加する.
  • ✔難易度:標準白駿銀色1