今回も paiza のクエリメニューで「アイドルグループ」問題に挑戦！
JS には順序付集合がないから苦労したけど、前回の二分探索で解決！
あと、ビットシフトの使い所がやっとわかった✨
問題概要
📘 シナリオ
- paiza君は、N人のロボットアイドルグループのマネージャー。
- アイドルの名前はランダムで、管理が大変。
- メンバーは加入・脱退が頻繁にあり、そのたびにメンバー情報を更新する必要がある。
📌 処理するイベント
1️⃣ join name
- アイドル
nameがグループに加入する。
2️⃣ leave name
- アイドル
nameがグループから脱退する。 -
nameは必ずグループ内にいる。
3️⃣ handshake
- 現在のメンバーを 辞書順で改行区切りで出力 する。
- メンバーが0人のときは何も出力しない。
入力例:
2 7
nene
ao
handshake
leave nene
join neko
join koko
handshake
leave neko
handshake
出力例:
ao
nene
ao
koko
neko
ao
koko
❌ NGコード例：タイムオーバー
const rl = require('readline').createInterface({input:process.stdin});
const lines = [];
rl.on('line', (input) => lines.push(input));
rl.on('close', () => {
const [N, K] = lines[0].split(' ').map(Number);
const idol = lines.slice(1, N+1);
const events = lines.slice(N+1);
for(const e of events){
const [command, name] = e.split(' ');
if (command === 'join') {
idol.push(name);
}
else if (command === 'leave') {
const index = idol.indexOf(name);
idol.splice(index, 1);
}
else if (command === 'handshake'){
idol.sort().forEach(i => console.log(i));
}
}
});
🔍 ボトルネック 1️⃣ ：indexOf
-
leaveのたびにidol.indexOf(name)を呼んでいる - これは 配列の先頭から順に走査 なので O(N) かかる
- 毎回これを繰り返すと合計 O(KN) になる（K = イベント数）
🔍 ボトルネック 2️⃣ ：.sort()
-
handshakeのたびにidol.sort()を呼んでいる -
Array.prototype.sort()は O(N log N) - 毎回全部ソートしてるので、回数が多いと O(K N log N) に膨れる
✅ OKコード例：
const rl = require('readline').createInterface({input:process.stdin});
const lines = [];
rl.on('line', (input) => lines.push(input));
rl.on('close', () => {
const [N, K] = lines[0].split(' ').map(Number);
const idol = lines.slice(1, N+1);
const events = lines.slice(N+1);
idol.sort();
for(const e of events){
const [command, name] = e.split(' ');
if (command === 'join') {
const index = lowerBound(idol, name);
idol.splice(index, 0, name)
}
else if (command === 'leave') {
const index = lowerBound(idol, name);
idol.splice(index, 1);
}
else if (command === 'handshake'){
if(idol.length() === 0) continue;
idol.forEach(i => console.log(i));
}
}
});
function lowerBound(arr, value) {
let left = 0, right = arr.length;
while(left < right){
const mid = (left + right) >> 1;
if (arr[mid] < value) left = mid + 1;
else right = mid;
}
return left;
}
✅ 【全体の流れ】
1️⃣ 入力を全部 lines に格納
2️⃣ 1 行目で N（初期人数）と K（イベント数）を取得
3️⃣ idol に初期メンバーを格納してソート
4️⃣ イベントを 1 行ずつ処理
・ join → 二分探索で挿入位置を探して splice(位置、削除数、要素) で追加
・ leave → 二分探索で削除位置を探して splice() で削除
・ handshake → 現在の idol を辞書順に出力
💡 常に 配列を辞書順に保つ のがポイント！
✅ 【二分探索（lowerBound）とは？】
function lowerBound(arr, value) {
let left = 0, right = arr.length;
while(left < right){
const mid = (left + right) >> 1;
if (arr[mid] < value) left = mid + 1;
else right = mid;
}
return left;
}
🔍 やりたいこと
value（名前）を辞書順で入れるべき場所（条件を満たす境界）を探す。
中央より右にあるか左にあるかで二分して探していく。
🔍条件とは？
→ 「arr[i] ≥ value」 となる 「最初の位置」 を探す
探索：
🔹 arr[mid] < value なら mid は条件を満たしていない
→ だから「条件を満たす位置は mid より右にある」
→ 左端を右に寄せ、探索範囲を右側へ
🔹 それ以外（arr[mid] ≥ value）なら mid は条件を満たしている
→ もっと左に条件を満たす位置があるかもしれない
→ right を mid にして探索範囲を左に縮める
🔍最終的に left が挿入位置
→ 配列のどこに value を入れればソート順が崩れないか分かる。
✨ ポイント！
文字列でも辞書順比較は arr[mid] < value でOK。
JS の文字列比較は Unicode コード順だからそのまま辞書順。
✅ 【ビットシフト >> とは？】
const mid = (left + right) >> 1;
-
>> 1は「2 進数で右に 1 ビットシフトする」＝ 整数除算で ÷2
- つまり
(left + right) >> 1はMath.floor((left + right) / 2)と同じ意味
- ビット演算の方がほんの少し速いし、整数丸めが保証される
例:
10 (2進数: 1010) >> 1 → 0101 → 5
8 (2進数: 1000) >> 1 → 0100 → 4
✅ 【この lowerBound の使い所】
- 辞書順を守りつつ追加（
join） - 辞書順の位置を正確に特定して削除（
leave） -
spliceは O(N) だが、位置探索が O(log N) で速いから実用的
🗒️ メモ＆まとめ
-
毎回 配列全体を
sort()するより、二分探索 +splice()が速い！ -
文字列でも二分探索できる（辞書順）
-
>> 1は中央を高速に求める便利テク (ビットシフト)