特殊な探索 《線形探索》

線形探索メニュー【偶数の探索・奇数の探索・最小値・最大値・点の距離・範囲内の点・成績優秀者1〜2】

問題【STEP: 1】偶数の探索
Task
数列 a_1, … , a_n が与えられます。最初に現れる偶数が何番目にあるかを求めてね。

【STEP: 1】コード

reader.on('close', () => {
   const n = Number(lines[0]);
   const a = lines[1].split(' ').map(Number);
   for (let i = 0; i < n; i++) {
      if (a[i] % 2 === 0) {  // a[i] が 2 で割り切れれば…
         console.log(i + 1);  // i + 1を出力
         break;  // ループを止める
      }
   }
});
hogeちゃんの画像

a[i]が 2 で割り切れれば i + 1を出力して break でループを止めればOK。

top
問題【STEP: 2】奇数の探索
Task
数列 a_1, … , a_n が与えられます。最後に現れる奇数が何番目にあるかを求めてね。

【STEP: 2】コード

reader.on('close', () => {
   const n = Number(lines[0]);
   const a = lines[1].split(' ').map(Number);
   for (let i = n - 1; i >= 0; i--) {  // 末尾からループ
      if (a[i] % 2 === 1) {  // a[i] を 2 で割った余りが 1 なら…
         console.log(i + 1);  // i + 1を出力
         break;  // ループを止める
      }
   }
});
hogeちゃんの画像

a[i]を 2 で割った余りが 1 なら i + 1を出力。

top
問題【STEP: 3】条件付き最小値
Task
数列(a_1, … , a_n)に含まれる値で k 以上であるもののうち 値が最小のものを出力してね。

【STEP: 3】コード

reader.on('close', () => {
   const n = Number(lines[0]);
   const k = Number(lines[2]);
   const a = lines[1].split(' ').map(Number);
   a.sort((s, b) => s - b);  // a を 昇順に並替
   for (let i = 0; i < n; i++) {
      if (a[i] >= k) {  // a [i] が k 以上なら…
         console.log(a[i]);  // a[i] を 出力
         break;
      }
   }
});
hogeちゃんの画像

a.sort((s, b) => s - b) で a を小さい順に並べ替えて a[i] が k 以上になるまで ループ。

top
問題【STEP: 4】条件付き最大値
Task
数列(a_1, … , a_n)に含まれる値で k 以下であるもののうち 値が最大のものを出力してね。

【STEP: 4】コード

reader.on('close', () => {
   const n = Number(lines[0]);
   const k = Number(lines[2]);
   const a = lines[1].split(' ').map(Number);
   a.sort((s, b) => b - s);  // a を 降順に並替
   for (let i = 0; i < n; i++) {
      if (a[i] <= k) {  // a [i] が k 以下なら…
         console.log(a[i]);  // a[i] を 出力
         break;
     }
   }
});
hogeちゃんの画像
a.sort((s, b) => b - s) で a を大きい順に並べ替えて a[i] が k 以下になるまで ループ。
top
問題【STEP: 5】点と点の距離
Task
n 個の点のうち 点 n とのマンハッタン距離が k 以下であるような点の数を求めてね。

【STEP: 5】コード

reader.on('close', () => {
   const n = Number(lines[0]);
   const k = Number(lines[n + 1]);
   let ans = 0;
   for (let i = 1; i <= n; i++) {
      const [xn, yn] = lines[n].split(' ').map(Number);  // 点 n の座標
      const [x, y] = lines[i].split(' ').map(Number);  // 点 n 以外の各座標
      const [X, Y] = [xn - x, yn - y].map(Math.abs);  // X, Y は xn - x, yn - y の絶対値
      if (X + Y <= k) {  // マンハッタン距離が k 以下なら…
         ans++;  // ans を加算
      }
   }
   console.log(ans);
});
hogeちゃんの画像

点 [xn, yn] と 点 [x, y] の マンハッタン距離 は [xn - x, yn - y].map(Math.abs) で引き算の値の 絶対値 を求めて足し合わせればOK。

 

top
問題【STEP: 6】長方形に含まれる点
Task
n 個の点のうち 指定されたの4頂点からなる長方形の内部に含まる点の数を求めてね。

【STEP: 6】コード

reader.on('close', () => {
   const n = Number(lines[0]);
   let ans = 0;
   for (let i = 1; i <= n; i++) {
      const [x_s, x_t] = lines[n + 1].split(' ').map(Number);  // 長方形の x 座標
      const [y_s, y_t] = lines[n + 2].split(' ').map(Number);  // 長方形の y 座標
      const [x, y] = lines[i].split(' ').map(Number);  // 点の座標
      if (x >= x_s && x <= x_t && y >= y_s && y <= y_t) {  // 点の座標 が長方形の座標内に収まれば
         ans++;  // ans を加算
      }
   }
   console.log(ans);
});
hogeちゃんの画像

長方形の左上は [x_s, y_s] 右下は[x_t, y_t]なので [x, y] の各値が 左上以上 且つ 右下以下なら ans を加算しました。

top
問題【STEP: 7】成績優秀者の列挙 1
Task
n 人の生徒がテストを受けて k 点以上で合格です。合格した人の名前を出力してね。

【STEP: 7】コード

reader.on('close', () => {
   const n = lines[0] - 0;
   const k = lines[n + 1];
   for (let i = 1; i <= n; i++) {
      const [s, t] = lines[i].split(' ');  // s は生徒名, t はテストの点数
      if (t - k >= 0) {  // テストの点数 - 基準点 が 0 以上なら…
         console.log(s);  // 生徒名を出力
      }
   }
});
hogeちゃんの画像

得点 t  – 基準点 k  が 0 以上 なら 生徒名 s を表示。

top
問題【FINAL】成績優秀者の列挙 2
Task
n 人の生徒がテストを受けて k 点以上 l 点以下で合格です。合格した人の名前を出力してね。

【FINAL】コード

reader.on('close', () => {
   const n = lines[0] - 0;
   const [k, l] = lines[n + 1].split(' ');
   for (let i = 1; i <= n; i++) {
      const [s, t] = lines[i].split(' ');
      if (t - k >= 0 && l - t >= 0) {  // 得点 -  k が 0 以上 且つ l - 得点 が 0 以上 なら…
         console.log(s);  // 生徒名を出力
      }
   }
});
hogeちゃんの画像

得点 t – 基準点 k が 0 以上 で 更に 基準点 l – 得点 t が 0 以上なら 生徒名 s を出力。

top

コメント