paiza 二次元データの区間探索 js

線形探索メニュー【二次元データ 1 〜 2・ピクニック・三次元データ・二次元データの区間探索】

Task

n 個の文字列に含まれる[.]の数を計算し合計を出力してね。

【二次元データ 1】コード

reader.on('close', () => {
   const [n, m] = lines[0].split(' ').map(Number);
   let ans = 0;  // 出力値を 0 で初期化
   for (let i = 1; i <= n; i++) {  // n 行の入力を…
      const s = lines[i];  // 1 行ずつ s で受け取り
      for (let j = 0; j < m; j++) { 
         if (s[j] === '.') {  // s を一文字ずつ調べて '.' なら…
            ans++;  // ans を加算
         }
      }
   }
   console.log(ans);
});

文字列も添字を使えば一文字ずつ調べることができました。

top

問題【STEP: 2】二次元データ 2

Task

n 個の文字列に含まれる k の数を計算して合計を出力してね。

【二次元データ 2】コード

reader.on('close', () => {
   const [n, m, k] = lines[0].split(' ').map(Number);
   let ans = 0;  // 出力値を 0 で初期化
   for (let i = 1; i <= n; i++) {  // n 行の入力を…
      const s = lines[i].split(' ').map(Number);  // 数値化して s (配列)で受け取り
      for (let j = 0; j < m; j++) {
         if (s[j] === k) {  // s[j] が k なら… 
            ans++;
         }
      }
   }
   console.log(ans);
});

【STEP: 1】とほぼ同じコードです。‘.’の数を計算が k (数値)の数を計算になったので入力を半角スペース区切りの配列に変換し更に要素を数値化して s で受け取りました。if文の条件式は s[j] === k になっています。

top

問題【STEP: 3】ピクニック

Task

a[i][j] = a[i+1][j] = a[i][j+1] = a[i+1][j+1] となる場所は何通り？

【ピクニック】コード

reader.on('close', () => {
   const [n, m] = lines[0].split(' ').map(Number);
   const A = [];  // n 行 ✕ m 列 の二次元配列
   let ans = 0;  // 出力値を 0 で初期化
   for (let i = 1; i <= n; i++) {
      A.push(lines[i].split(' ').map(Number));  // 入力を(' ')区切りの配列に変換し 各値を数値化してから A に保存
   }
   for (let i = 0; i < n - 1; i++) {
      for (let j = 0; j < m - 1; j++) {
         const [a, b, c, d] = [A[i][j], A[i + 1][j], A[i][j + 1], A[i + 1][j + 1]];
         // A[i][j] を a に代入し a の 右・下・右下の各値を b, c, d に代入
         if (a === b && a === c && a === d) {  // a が b, c, d と一致すれば…
            ans++;  // ans を 1 加算
         }
      }
   }
   //console.table(A);
   console.log(ans);
});

二次元配列の各値にアクセスするために二重ループを使っています。二次元配列の値の確認はconsole.table()を使うとわかりやすいですね。

top

問題【STEP: 4】ピクニック 2

Task

k * k 個の区画の価値の合計が最大となる場所の価値の合計はいくら？

【ピクニック 2】コード

reader.on('close', () => {
   const [n, m, k] = lines[0].split(' ').map(Number);
   const A = [];  // 各区画の価値を保存
   let Max_price = 0;  // 価値の合計が最大となる場所の価値(0で初期化)
   for (let i = 1; i <= n; i++) {
      A.push(lines[i].split(' ').map(Number));  // 入力を(' ')区切りの配列に変換し 各値を数値化して A に保存
   }
  // ここから 配列 A の 二次元累積和(配列 S) を生成
   const S = [[]];  // A の累積和を保存する配列
   for (let i = 0; i <= m; i++) {
      S[0].push(0);
   }
   for (let i = 0; i < n; i++) {
      S.push([0]);
      for (let j = 0; j < m; j++) {
         S[i + 1].push(S[i + 1][j] + A[i][j] + S[i][j + 1] - S[i][j]);
      }
   }
  // ここまで 配列 A の 二次元累積和(配列 S) を生成
   for (let i = k; i <= n; i++) {
      for (let j = k; j <= m; j++) {
         const price = S[i][j] - S[i - k][j] - S[i][j - k] + S[i - k][j - k];
  // 各区画の価値を price に代入し Max_price と比較して price の値が大きければ
            if (price > Max_price) {
            Max_price = price;  // Max_price を price で上書き
          }
       }
    }
   console.log(Max_price);
});

価値の合計が最大となる場所の価値の合計なので二次元累積和を使ってみました。

top

問題【STEP: 5】三次元データ

Task

高さ h cm・幅 m cm・奥行 n cm のオブジェの色 x が使用されている石の個数は？

【三次元データ】コード

reader.on('close', () => {
   const [n, m, h, x] = lines[0].split(' ').map(Number);
   const a = []; 
   for (let i = 1; i <= h * n; i++) {
  // 配列 a に 配列化した入力値を保存し ニ次元配列を生成
      a.push(lines[i].split(' ').map(Number));
   }
   for (let i = 0; i < h; i++) {
      a.push(a.splice(0, n));
// 二次元配列 a の要素を先頭から n 個ずつ切り取り 要素数 h 個の二次元配列を生成 => a の末尾に追加
   }
   let ans = 0;
   for (let i = 0; i < h; i++) {  // h は配列 a の要素数
      for (let j = 0; j < n; j++) {  // n は配列 a[i] の要素数
         for (let k = 0; k < m; k++) {  // m は配列 a[i][j] の要素数
            if (a[i][j][k] === x) {  // a[i][j][k] が x なら…
               ans++;  // ans を加算
            }
         }
      }
   }
  console.log(ans);
});

課題が三次元データになっているので三次元配列を生成しました。三次元配列のデータにアクセスするために三重ループを使っています。

top

問題【FINAL】二次元データの区間探索

Task

n ✕ m の敷地の No.1〜No. x の区画のうち k ✕ k のシートを敷ける場所は何通り？

【二次元データの区間探索】コード 1/2

reader.on('close', () => {
   const [n, m, k, x] = lines[0].split(' ').map(Number);
   const A = [];  // n ✕ m の敷地
   for (let i = 1; i <= n; i++) {
      A.push(lines[i].split(' ').map(Number));  // n 行 m 列の敷地番号
   }
   for (let i = 0; i < n; i++) {
      for (let j = 0; j < m; j++) {  // n 行 m 列の区画を探索して…
         if (A[i][j] <= x) {  // 区画の各値が x 以下(予約済のスペース)なら…
             A[i][j] = 0;  // 値を 0 で上書き
         }
      }
   }
  // ここから 配列 A の 二次元累積和(配列 S) を生成
   const S = [ [] ];
   for (let i = 0; i <= m; i++) {
      S[0].push(0);
   }
   for (let i = 0; i < n; i++) {
      S.push([0]);
      for (let j = 0; j < m; j++) {
         S[i + 1].push(S[i + 1][j] + A[i][j] + S[i][j + 1] - S[i][j]);
      }
   }
  // ここまで 配列 A の 二次元累積和(配列 S) を生成
   let ans = 0;
   for (let i = k; i <= n; i++) {
      for (let j = k; j <= m; j++) {
  // 二次元累積和(配列 S) の部分和 を site に代入
         const site = S[i][j] - S[i - k][j] - S[i][j - k] + S[i - k][j - k];
         if (!site) {  // site が 0(false)なら
            ans++;  // ans を 1 加算
         }
      }
   }
   console.log(ans);
});

こちらの課題も二次元累積和を使いました。x 以下の番号は全て 0 に置き換え累積和が 0 であれば ans を 1 加算。

top

【二次元データの区間探索】コード 2/2

reader.on('close', () => {
   const [n, m, k, x] = lines[0].split(' ').map(Number);
   const A = [];  // n ✕ m の敷地
   for (let i = 1; i <= n; i++) {
      A.push(lines[i].split(' ').map(Number));  // n 行 m 列の敷地番号
   }
    let ans = 0;
    for (let i = 0; i <= n - k; i++) {
        for (let j = 0; j <= m - k; j++) {  // A[i][j] は シートの左上
            let able_to_lay_sheet = true;  // シートを敷けるか否かの真偽値
            for (let h = 0; h < k; h++) {
                for (let w = 0; w < k; w++) {  // A[i][j] から右下に向かって k * k マスの範囲に…
                    if (A[i + h][j + w] > x) {  // 番号が x より大きい区画がある場合
                        able_to_lay_sheet = false;  // シートを敷くことができない
                    }
                }
            }
            if (able_to_lay_sheet) {  // able_to_lay_sheet が true なら…
                ans++;  // ans を加算
            }
        }
    }
    console.log(ans);
});

C++ の解答コード例を参照しました。

top