paiza 問題集点の幅 js

クエリメニュー【′I′の数・ドーナツ・点の幅】

Task

ゲームのジャッジをしてね。※ 教科書のページを掴んで″I″の合計数が多い方が勝ち。

【STEP: 1】コード

reader.on('close', () => {
  const [N, K] = lines[0].split(' ').map(Number);
  const A = [0];  // A は 累積和を保存するための配列
  const P = N / 3;
  for (let i = 1; i <= N; i++) {
    A.push(A[i - 1] + Number(lines[i]));  // A に "I" の数の累積和を保存
  }
  for (let i = N + 1; i <= N + K; i++) {
    let [a, b] = [0, 0];  // [a, b] は A と B の点数
    const [Al, Ar, Bl, Br] = lines[i].split(' ').map(Number);
    if (Ar - Al + 1 >= P && Br - Bl + 1 >= P) {  // 2人共反則なので…
      console.log('DRAW');  // "DRAW"(引き分け)
    } else if (Ar - Al + 1 >= P) {  // A が反則なので…
      console.log('B');  // B の勝ち
    } else if (Br - Bl + 1 >= P) {  // B が反則なので…
      console.log('A');  // A の勝ち
    } else {
      a = A[Ar] - A[Al - 1];  // A の得点
      b = A[Br] - A[Bl - 1];  // B の得点
      if (a === b) {  // 得点が同じなら…
        console.log('DRAW');  // "DRAW"(引き分け)
      } else {
        console.log(a > b ? 'A' : 'B');  // a > b なら "A" を出力 さもなくば "B" を出力
      }
    }
  }
});

累積和を使って区間和を求めています。

top

問題【STEP: 2】ドーナツ

Task

四角いドーナツに埋め込まれているチョコの数を出力してね。

【STEP: 2】コード

reader.on('close', () => {
   const [H, W, N] = lines[0].split(' ').map(Number);
   const D = [];  // チョコの数(入力値)を保存するための 2 次元配列
   const S = [new Array(W + 1).fill(0)];  // チョコの数の 2 次元累積和
   for (let h = 1; h <= H; h++) {
      D.push(lines[h].split(' ').map(Number));  // D に入力値の配列を保存
      S.push([0]);  // S に [0] を保存
      for (let w = 1; w <= W; w++) {
  // D の累積和を計算して S に保存
         S[h][w] = (S[h - 1][w] + S[h][w - 1] + D[h - 1][w - 1] - S[h - 1][w - 1]);
      }
   }
   for (let n = H + 1; n <= N + H; n++) {
      const [y, x, b, s] = lines[n].split(' ').map(Number);
      const [bs, ss] = [b, s].map(x => (x - 1) / 2);
      const [sy, sx, ey, ex, ssy, ssx, sey, sex] = [y - bs, x - bs, y + bs, x + bs, y - ss, x - ss, y + ss, x + ss];
      const Br = S[ey][ex] - S[sy - 1][ex] - S[ey][sx - 1] + S[sy - 1][sx - 1];
      const Sr = S[sey][sex] - S[ssy - 1][sex] - S[sey][ssx - 1] + S[ssy - 1][ssx - 1];
      console.log(Br - Sr);
   }
});

二次元累積和の配列を生成し範囲内の値を取得しました。

top

問題【FINAL】点の幅

Task

ゲームのジャッジをしてね。※ルール = 生徒を選んでテスト得点の幅が大きい方が勝ち。

【FINAL】コード

reader.on('close', () => {
  const [N, K] = lines[0].split(' ').map(Number);
  const Ns = Math.sqrt(N);
  const S = [];
  const Min = [];
  const Max = [];
  for (let i = 1; i <= N; i++) {
    S.push(Number(lines[i]));
  }
  const A = [...S];
  for (let i = 0; i < Ns; i++) {
    const s = S.splice(0, Ns);
    let [max, min] = [s[0], s[0]];
    S.push(s);
    for (let i = 1; i < Ns; i++) {
      max = Math.max(max, s[i]);
      min = Math.min(min, s[i]);
    }
    Max.push(max);
    Min.push(min);
  }
  for (let k = N + 1; k <= N + K; k++) {
    const [Al, Ar, Bl, Br] = lines[k].split(' ').map(x => x - 1);
    let A_point = Al;
    let [Amin, Amax] = [A[Al], A[Al]];
    while (A_point <= Ar) {
      if (A_point % Ns === 0 && A_point + Ns - 1 <= Ar) {
        Amin = Math.min(Amin, Min[A_point / Ns]);
        Amax = Math.max(Amax, Max[A_point / Ns]);
        A_point += Ns;
      } else {
        Amin = Math.min(Amin, A[A_point]);
        Amax = Math.max(Amax, A[A_point]);
        A_point++;
      }
    }
    let B_pointt = Bl;
    let [Bmin, Bmax] = [A[Bl], A[Bl]];
    while (B_pointt <= Br) {
      if ((B_pointt) % Ns === 0 && B_pointt + Ns - 1 <= Br) {
        Bmin = Math.min(Bmin, Min[B_pointt / Ns]);
        Bmax = Math.max(Bmax, Max[B_pointt / Ns]);
        B_pointt += Ns;
      } else {
        Bmin = Math.min(Bmin, A[B_pointt]);
        Bmax = Math.max(Bmax, A[B_pointt]);
        B_pointt++;
      }
    }
    const Bp = Bmax - Bmin;
    const Ap = Amax - Amin;
    if (Ap > Bp) {
      console.log('A');
    } else if (Ap < Bp) {
      console.log('B');
    } else {
      console.log('DRAW');
    }
  }
});

一応これでクリアできましたけどもう少しコードを整理しないと駄目ですね。 (๑ ᷄ω ᷅)

top