Skip to content

B11

Directory actions

More options

Directory actions

More options

Latest commit

 

History

History
 
 

B11

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
B11.go
B11.go
 
 
B11.js
B11.js
 
 
B11.php
B11.php
 
 
B11.py
B11.py
 
 
B11.ts
B11.ts
 
 
README.md
README.md
 
 

README.md

✅ 目次

  1. 入力処理（fsによる読み込み）
  2. 配列 A のソート処理
  3. 二分探索 lowerBound() の仕組み（図で詳しく）
  4. 出力処理（配列の結果を join して出力）

1. 🔰 入力処理（fs）

const input: string[] = fs.readFileSync('/dev/stdin', 'utf8').trim().split(/\s+/);

🎯 処理内容

  • fs.readFileSync('/dev/stdin', 'utf8') により 全体を一気に読み込み。
  • trim().split(/\s+/) によって、スペースや改行区切りの数字列を string[] として取得。

🧠 具体例

入力

5
1 3 3 3 1
2
4
3

input 配列の状態：

input = [
  "5",       // N
  "1", "3", "3", "3", "1",  // A
  "2",       // Q
  "4", "3"   // クエリX
]

2. 📊 配列 A のソート処理

A.sort((a, b) => a - b);
  • JavaScriptの標準ソート（文字列ソート）ではなく、数値ソート。
  • 昇順に並び替える。

🧠 例：A = [1, 3, 3, 3, 1]

Before sort: [1, 3, 3, 3, 1]
↓
After sort:  [1, 1, 3, 3, 3]

3. 🔍 二分探索（lowerBound）

function lowerBound(arr: number[], target: number): number {
    let left = 0;
    let right = arr.length;
    while (left < right) {
        const mid = (left + right) >>> 1;
        if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return left;
}

🎯 意味

「配列 arr の中で target より小さい要素はいくつあるか？」 ➡️ arr はソート済なので、二分探索で調べられる！

🧠 例：A = [1, 1, 3, 3, 3], target = 3

初期状態

arr = [1, 1, 3, 3, 3]
target = 3
left mid right arr[mid] 判定 次の範囲
0 2 5 3 3 >= 3 → ✖ [0, 2)
0 1 2 1 1 < 3 → ✔ [2, 2) (終了)

➡️ 結果：left = 2 → 3 より小さい要素は 2個

📘 イメージ図（探索範囲）

配列:    [1, 1, 3, 3, 3]
index:    0  1  2  3  4
target: 3

        ↑
      [left=2] = 答え！

4. 🖨️ 出力処理

console.log(results.join('\n'));
  • results にクエリごとの答えを配列で格納。
  • 最後に join('\n') により Q行の出力としてまとめて出力。

🧠 例：結果 = [5, 2]

results = [5, 2]
console.log(results.join('\n')) →
5
2

✅ 全体フロー図（まとめ）

        入力 (fs.readFileSync)
                ↓
         文字列配列 input[]
                ↓
          配列Aの抽出・整形
                ↓
            Aをソート
                ↓
        各クエリに対して
       ┌───────────────┐
       │ lowerBound() │ ←─── target X
       └───────────────┘
                ↓
         結果を配列に保存
                ↓
       join('\n')でまとめて出力
提出日時 問題 ユーザ 言語 得点 コード長 結果 実行時間 メモリ
2025-07-06 23:34:52 B11 - Binary Search 2 myoshizumi Go (go 1.20.6) 1000 803 Byte 42 ms 3004 KiB 詳細
2025-07-06 23:24:50 B11 - Binary Search 2 myoshizumi PHP (php 8.2.8) 1000 887 Byte 76 ms 32112 KiB 詳細
2025-07-06 23:21:04 B11 - Binary Search 2 myoshizumi Python (CPython 3.11.4) 1000 899 Byte 112 ms 36232 KiB 詳細
2025-07-06 23:15:49 B11 - Binary Search 2 myoshizumi TypeScript 5.1 (Node.js 18.16.1) 1000 1048 Byte 126 ms 76908 KiB 詳細
2025-07-06 23:11:11 B11 - Binary Search 2 myoshizumi JavaScript (Node.js 18.16.1) 1000 877 Byte 384 ms 76448 KiB 詳細