Open8日前にコメント追加2

AtCoder: ABC upsolve 特訓 (JavaScript)

JavaScript

競技プログラミング

AtCoder

学習記録

mae616

 ABC376結果

今回はCとDを解説放送を見る。

 A
 問題https://atcoder.jp/contests/abc376/tasks/abc376_a

 解いたコードfunction main(input) {
  const args = input.split("\n");
  const [n, c] = args.shift().split(" ").map(Number);
  const t = args[0].split(" ").map(Number);

  if (n === 1) {
    console.log(1);
    return;
  }

  let prev = t[0];
  let count = 1;
  for (let i = 1; i < n; i++) {
    if (c <= t[i] - prev) {
      count++;
      prev = t[i];
    }
  }

  console.log(count);
}

main(require("fs").readFileSync("/dev/stdin", "utf8"));
t が前に押した時からの時間経過と勘違いしてしまい 2回ペナルティ。

 B
 問題https://atcoder.jp/contests/abc376/tasks/abc376_b

 解いたコードfunction main(input) {
  const args = input.split("\n");
  const [n, q] = args.shift().split(" ").map(Number);

  let count = 0;
  const hands = { L: 1, R: 2 };
  for (let i = 0; i < q; i++) {
    const [h, t] = args[i].split(" ");

    let h2;
    if (h === "L") {
      h2 = hands["R"];
    } else {
      h2 = hands["L"];
    }

    let temp;
    if (h2 >= hands[h] && h2 <= Number(t)) {
      temp = n - (Number(t) - hands[h]);
    } else if (h2 <= hands[h] && h2 >= Number(t)) {
      temp = n - hands[h] + Number(t);
    } else {
      temp = Math.abs(hands[h] - Number(t));
    }
    count += temp;
    hands[h] = Number(t);
  }

  console.log(count);
}

main(require("fs").readFileSync("/dev/stdin", "utf8"));
どう解いたらいいのかわからなくて、正直「ワンチャン合ってないかな」で出したらいけた。

ここも解法見たほうがいいと思うけど、気持ち的にしんどいから今回はこれはおさらいしない（次の機会に...）。

 C
 問題https://atcoder.jp/contests/abc376/tasks/abc376_c

 解いたコードfunction main(input) {
  const args = input.split("\n");
  const n = Number(args.shift());
  const omocha = args.shift().split(" ").map(Number);
  const hako = args[0].split(" ").map(Number);

  omocha.sort((a, b) => a - b);
  hako.sort((a, b) => a - b);

  for (let i = n - 1; i >= 0; i--) {
    if (omocha[i] <= hako[hako.length - 1]) {
      hako.pop();
      omocha.splice(i, 1);
    }
    if (hako.length === 0) {
      break;
    }
  }

  if (omocha.length === 1 && hako.length === 0) {
    console.log(omocha[0]);
  } else {
    console.log(-1);
  }
}

main(require("fs").readFileSync("/dev/stdin", "utf8"));
そんなに数が多くなさそうだから、ギリギリこれでも時間内にいけるだろう、でいけた。

他の人のやり方を見ると2分探索の人が多いよう。

 解説放送Cの箇所

https://www.youtube.com/live/T0-OjBkwi2U?si=9kQ0v_GcTqaTpyL2&t=3127

 アルゴリズム

 コードfunction main(input) {
  const args = input.split('\n');
  const n = Number(args[0]);
  const a = args[1].split(' ').map(Number);
  const b = args[2].split(' ').map(Number);
  a.sort((a, b) => a - b);
  b.sort((a, b) => a - b);

  const judge = (x) => {
    const nb = [...b, x];
    nb.sort((a, b) => a - b);
    for(let i=0; i<n; i++){
      if(a[i] > nb[i]) return false;  
    }
    return true;
  };

  let wa = 0;
  let ac = n - 1;
  let flg = false;
  while(wa <= ac){
    if(ac === wa){
      if(flg || judge(a[ac])){
        console.log(a[ac]);
      }else{
        console.log(-1);
      } 
      return;
    }
    
    const wj = Math.floor((wa + ac) / 2);
    if(judge(a[wj])){
      flg = true;
      ac = wj;
    }else{
      wa = wj + 1;
    }
  }
  console.log(-1);
}

main(require('fs').readFileSync('/dev/stdin', 'utf8'));
解説放送見てやったら、言語の違いで全く通らなくて、何度か心が折れそうになった...

 Dできなかった。

でもD問題で書いてアウトでも挑戦できたの初めてかも。進歩٩( ᐛ )و

 問題https://atcoder.jp/contests/abc376/tasks/abc376_d

 挑戦したコード(RE: 実行エラー)function main(input) {
  const args = input.split("\n");
  const [n, m] = args.shift().split(" ").map(Number);

  const hen = {};
  args.forEach((v) => {
    const a = v.split(" ");
    if (!(a[0] in hen)) hen[a[0]] = [a[1]];
    else hen[a[0]].push(a[1]);
  });

  if (!("1" in hen)) {
    console.log(-1);
    return;
  }

  let min = Infinity;
  (function recursion(keiroTemp, count) {
    for (let i = 0; i < keiroTemp.length; i++) {
      if (keiroTemp[i] === "1") {
        min = Math.min(min, count);
        return;
      }

      if (!(keiroTemp[i] in hen)) continue;
      recursion(hen[keiroTemp[i]], count + 1);
    }
  })(hen["1"], 1);

  console.log(min === Infinity ? -1 : min);
}

main(require("fs").readFileSync("/dev/stdin", "utf8"));

 解説放送Dの箇所

https://www.youtube.com/live/T0-OjBkwi2U?si=Dnk7igS5jUtc8MQj&t=5041

mae616

ABC379 C

問題

コンテスト中のコード(TLE)

function main(input) {
  const args = input.split("\n");
  const [n, m] = args[0].split(" ").map(Number);

  const x = args[1].split(" ").map(Number);
  const a = args[2].split(" ").map(Number);

  const hit = [];
  const ary = new Array(n).fill(0);
  let sum = 0;
  for (let i = 0; i < m; i++) {
    ary[x[i] - 1] = a[i];
    sum += a[i];
    if (a[i] > 1) {
      hit.push({ key: x[i] - 1, stone: a[i] });
    }
  }
  hit.sort((a, b) => a.key - b.key);

  if (sum !== n || ary[n - 1] > 1) {
    console.log(-1);
    return;
  }

  let count = 0;
  let from = hit.length - 1;
  let i = ary.length - 1;
  while (from >= 0 && hit[from].key < i) {
    if (ary[i] === 1) {
      ary.pop();
    } else if (ary[i] === 0) {
      hit[from].stone--;
      count += i - hit[from].key;
      ary.pop();
      ary[hit[from].key]--;
      if (hit[from].stone === 1) {
        hit.pop();
      }
    } else {
      console.log(-1);
      return;
    }
    from = hit.length - 1;
    i = ary.length - 1;
  }

  if (!(ary.length > 0 && ary.every((item) => item === 1))) {
    console.log(-1);
    return;
  }

  console.log(count);
}

main(require("fs").readFileSync("/dev/stdin", "utf8"));

解説放送

見て解いたもの(WAになるんだけどAIに聞いてもわからない)

function main(input) {
  const args = input.split("\n");
  const [n, m] = args[0].split(" ").map(Number);

  const x = args[1].split(" ").map(Number);
  const a = args[2].split(" ").map(Number);

  const hit = [];
  for (let i = 0; i < m; i++) {
    hit.push({ key: x[i], stone: a[i] });
  }
  hit.push({ key: n + 1, stone: 0 }); // 番兵

  hit.sort((a, b) => a.key - b.key);

  let count = 0;
  let prevKey = 0;
  let currentStone = 1;
  for (let i = 0; i < hit.length; i++) {
    const L = hit[i].key - prevKey;
    const carry = currentStone - L;

    // 当てはめる
    if (L > 0) {
      count += ((L - 1) * L) / 2;
    }

    if (carry < 0) {
      console.log(-1);
      return;
    }

    // 繰り越し
    count += L * carry;

    prevKey = hit[i].key;
    currentStone = carry + hit[i].stone;
  }

  if (currentStone !== 0) {
    console.log(-1);
  } else {
    console.log(count);
  }
}

main(require("fs").readFileSync("/dev/stdin", "utf8"));

とりあえず、今回は諦める