点の幅 (平方分割)

今回は paiza のクエリの最終問題の「点の幅」に挑戦！

この問題のポイントは、たぶん「平方分割」のアルゴリズムだと思う…

たぶんきっとそう…。

問題概要

■ ゲームのルール：

• プレイヤー A と B が、N 人の生徒の中から連続した区間を1つ選ぶ。

• 各生徒には得点 S_1 ～ S_N が与えられている。

• 選ぶ区間の長さは 最大 N/2 人まで（この制約は実装に必要ないがゲーム背景として存在）。

• 選んだ区間に含まれる生徒の「得点の最大値 − 最小値」を「得点の幅」と定義。

• 幅が大きい方が勝ち。同じ場合は引き分け（DRAW）。

■ 入力：

• N K（生徒数 N、試合数 K）
• 生徒の得点 S_1, S_2, ..., S_N（各生徒のスコア）
• K 行のクエリ：
• 各行に A_l A_r B_l B_r（AとBが選んだ生徒の区間）

■ 出力：

• K 行で、それぞれの勝者を出力：
  • A → Aが勝ち
  • B → Bが勝ち
  • DRAW → 同点

入力例：

4 2
1
3
2
4
1 2 2 3
1 2 3 4

出力例：

A
DRAW

✅ 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 students = lines.slice(1, N+1).map(Number);
	const queries = lines.slice(N+1);
    
    
	for(const q of queries){
    	const [lA, rA, lB, rB] = q.split(' ').map(Number);
   	 
    	const scoreA = getScore(lA, rA);
    	const scoreB = getScore(lB, rB);
   	 
   	 
    	if (scoreA > scoreB){
        	console.log('A');
    	}
    	else if (scoreA < scoreB){
        	console.log('B');
    	}
    	else {
        	console.log('DRAW')
    	}
	}
    
	function getScore (l, r) {
    	const temp = students.slice(l-1, r);
    	return Math.max(...temp) - Math.min(...temp);
	}
});

✨ 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 students = lines.slice(1, N+1).map(Number);
	const queries = lines.slice(N+1);
    
    
    const blockSize = Math.sqrt(N);
    const numBlocks = Math.ceil(N / blockSize);
    const blockMax = [];
    const blockMin = [];
    
    for(let i = 0; i < numBlocks; i++){
        const temp = students.slice(i * blockSize, (i+1) * blockSize);
        blockMax.push(Math.max(...temp));
        blockMin.push(Math.min(...temp));
    }
    

    
    
	for(const q of queries){
    	const [lA, rA, lB, rB] = q.split(' ').map(Number);
   	 
    	const scoreA = getScore(lA, rA);
    	const scoreB = getScore(lB, rB);
   	 
   	 
    	if (scoreA > scoreB){
        	console.log('A');
    	}
    	else if (scoreA < scoreB){
        	console.log('B');
    	}
    	else {
        	console.log('DRAW')
    	}
	}
    
	function getScore (l, r) {
	    const lIdx = l - 1;
	    const rIdx = r - 1;
	    
	    const startBlockIdx = Math.floor(lIdx / blockSize);
        const endBlockIdx = Math.floor(rIdx / blockSize);
        
        
        if (startBlockIdx === endBlockIdx){
    	    const temp = students.slice(lIdx, rIdx + 1);
    	    return Math.max(...temp) - Math.min(...temp);
    	}
    	
    	
    	const blockMaxRange = blockMax.slice(startBlockIdx + 1, endBlockIdx);
    	const blockMinRange = blockMin.slice(startBlockIdx + 1, endBlockIdx);
    	
    	const remainderLeft = students.slice(lIdx, (startBlockIdx + 1) * blockSize); 
    	const remainderRight = students.slice(endBlockIdx * blockSize, rIdx + 1);
    	
    	const candidatesMax = [...blockMaxRange, ...remainderLeft, ...remainderRight];
    	const candidatesMin = [...blockMinRange, ...remainderLeft, ...remainderRight];
    	
    	const max = Math.max(...candidatesMax);
    	const min = Math.min(...candidatesMin);
    	
    	const result = max - min;
    	return result;
	}
});

この単元で学んだ「平方分割」を使ってクエリを高速で処理した！

🗒️ まとめ

テストケース　N = 9604, K = 87473 の場合：

• 1つ目のコード：1.38秒
• 2つ目のコード：0.76秒
• 差：0.62秒
• この0.62秒のためにかけた時間：900秒 (´;ω;｀)

僕の失敗談(´;ω;｀)と解決法🐈