Skip to content

atCoder

Directory actions

More options

Directory actions

More options

Latest commit

 

History

History
 
 

atCoder

README.md

A11解法の概要

以下、二分探索を用いた JavaScript の実装です。
binarySearch 関数を用いて X の位置を求め、1-based index で出力します。

function binarySearch(arr, x) {
    let left = 0,
        right = arr.length - 1;
    while (left <= right) {
        let mid = Math.floor((left + right) / 2);
        if (arr[mid] === x) {
            return mid + 1; // 1-based index
        } else if (arr[mid] < x) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1; // 通常ここには到達しない（Xは必ず存在する）
}

function main() {
    const fs = require('fs');
    const input = fs.readFileSync('/dev/stdin', 'utf8').trim().split('\n');
    const [N, X] = input[0].split(' ').map(Number);
    const A = input[1].split(' ').map(Number);

    console.log(binarySearch(A, X));
}

main();

実装のポイント

  • 二分探索: 配列 A はソート済みなので、二分探索 (binarySearch) を用いて X の位置を高速に見つける。
  • 1-based index: 出力は1-based index のため、mid + 1 を返す。
  • 入力処理: fs.readFileSync("/dev/stdin", "utf8") で標準入力を取得し、改行で分割。

計算量

  • 二分探索の計算量は O(log N) であり、最大 N=100000 でも十分高速。

A12解法の概要

  1. 最小の時間: 1秒
  2. 最大の時間: ( K \times \min(A) )（最速のプリンターがすべて印刷する場合）
  3. 二分探索 を使い、「ある時間 ( T ) において K 枚以上のチラシが印刷されるか？」を判定する

この判定を効率よく行い、最小の ( T ) を求めます。

JavaScript の実装

以下は 二分探索 を用いた実装です。

function findPrintTime(N, K, A) {
    let left = 1,
        right = K * Math.min(...A);

    const canPrintKSheets = (T) => {
        let totalSheets = 0;
        for (let i = 0; i < N; i++) {
            totalSheets += Math.floor(T / A[i]);
            if (totalSheets >= K) return true; // K 枚以上印刷できるならOK
        }
        return false;
    };

    while (left < right) {
        let mid = Math.floor((left + right) / 2);
        if (canPrintKSheets(mid)) {
            right = mid; // K 枚以上印刷できるなら、もっと小さい時間を探す
        } else {
            left = mid + 1; // K 枚印刷できないなら、もっと時間が必要
        }
    }

    console.log(left);
}

// 標準入力の処理
const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin, output: process.stdout });

let input = [];
rl.on('line', (line) => {
    input.push(line.trim());
}).on('close', () => {
    const N = parseInt(input[0]);
    const K = parseInt(input[1]);
    const A = input[2].split(' ').map(Number);
    findPrintTime(N, K, A);
});

解説

1. 二分探索の範囲

  • 最小時間 left = 1
  • 最大時間 right = K * min(A)（最速のプリンターだけが K 枚印刷する場合）

2. 判定関数 canPrintKSheets(T)

  • ある時間 T で 合計何枚のチラシが印刷されるか を計算
  • 各プリンター i について Math.floor(T / A[i]) を足していく
  • 合計 K 枚以上印刷できれば true、できなければ false

3. 二分探索のロジック

  • mid = (left + right) / 2 を計算
  • canPrintKSheets(mid) を評価
    • true なら right = mid（もっと小さい時間を探す）
    • false なら left = mid + 1（もっと時間が必要）
  • left == right になったとき、最小の T が求まる

計算量

  • 判定関数 は O(N)
  • 二分探索 は O(log(K × min(A)))
  • 合計計算量 は O(N log K) で、高速に求められます。

テスト

入力

3
7
3 5 7

出力

9

ポイント

  • 3 秒ごとのプリンター → 3, 6, 9, ...
  • 5 秒ごとのプリンター → 5, 10, ...
  • 7 秒ごとのプリンター → 7, 14, ...
  • 9秒後に7枚目のチラシが出るので答えは 9。

まとめ

  • 二分探索 を使うと O(N log K) で高速に解ける
  • 判定関数 で「時間 T で K 枚印刷できるか？」を判定
  • 最小の時間 を求めるため、right = mid で狭めていく

A13解法の概要

この問題を効率的に解くために、二分探索（Binary Search）または双方向ポインタ（Two Pointers） を活用します。

アプローチ

  1. ソート不要
    既に小さい順に並んでいるため、ソート処理は不要です。
  2. 二分探索を使用する方法
    各 A[i] について、A[i] + K 以下の最大の j を 二分探索 で求め、i < j となるペア数を加算する。
  3. 双方向ポインタを使用する方法
    • i を左ポインタ、j を右ポインタとして探索
    • A[j] - A[i] > K なら i を進める
    • A[j] - A[i] ≤ K なら j を進め、ペア数を計算

実装

1. 二分探索を使う方法

O(N log N) で解ける。

function countPairsBinarySearch(N, K, A) {
    let count = 0;

    for (let i = 0; i < N; i++) {
        let left = i,
            right = N - 1;
        while (left <= right) {
            let mid = Math.floor((left + right) / 2);
            if (A[mid] - A[i] <= K) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        count += right - i;
    }

    console.log(count);
}

// 入力例
const [N, K, ...A] = `5 3
1 2 4 5 8`
    .split(/\s+/)
    .map(Number);
countPairsBinarySearch(N, K, A);

2. 双方向ポインタ（Two Pointers）

こちらも O(N) で解ける。

function countPairsTwoPointers(N, K, A) {
    let count = 0;
    let j = 0;

    for (let i = 0; i < N; i++) {
        while (j < N && A[j] - A[i] <= K) {
            j++;
        }
        count += j - i - 1;
    }

    console.log(count);
}

// 入力例
const [N, K, ...A] = `5 3
1 2 4 5 8`
    .split(/\s+/)
    .map(Number);
countPairsTwoPointers(N, K, A);

解説

  • 二分探索：各 A[i] に対し、A[i] + K 以下の最大の j を探し、O(log N)
  • 双方向ポインタ：j を増やしながら A[j] - A[i] <= K を満たす最大の j を求め、O(N)

O(N log N) よりも O(N) の双方向ポインタの方が高速 なので、基本的には 双方向ポインタ を推奨します。

A14解法の概要

この問題を解くには、全探索では計算量が O(N^4) = 10^{12} となり、制約 (N \leq 1000) を考えると計算時間的に厳しいです。
そこで、二分探索（またはハッシュセット）を活用して O(N^2 \log N) もしくは O(N^2) に改善する方法を採用します。

解法

  1. A, B の全てのペアの和を列挙し、リスト AB を作成する（要素数は (N^2)）。
  2. C, D の全てのペアの和を列挙し、ハッシュセット CD_set に格納する（検索を O(1) にするため）。
  3. AB の各要素 sum_ab に対し、K - sum_ab が CD_set に存在するか調べる。

これにより、計算量は以下の通り：

  • AB の生成: (O(N^2))
  • CD_set の生成: (O(N^2))
  • AB の各要素について CD_set を検索: (O(N^2))

総計: (O(N^2)) であり、N=1000 でも現実的な時間で処理可能！

JavaScript 実装

function canAchieveK(N, K, A, B, C, D) {
    let AB = new Set();

    // AとBの全ペアの和を計算し、集合ABに格納
    for (let i = 0; i < N; i++) {
        for (let j = 0; j < N; j++) {
            AB.add(A[i] + B[j]);
        }
    }

    // CとDの全ペアの和を計算し、K から引いた値がABに存在するか確認
    for (let i = 0; i < N; i++) {
        for (let j = 0; j < N; j++) {
            if (AB.has(K - (C[i] + D[j]))) {
                console.log('Yes');
                return;
            }
        }
    }

    console.log('No');
}

// 入力例
const N = 3,
    K = 50;
const A = [3, 9, 17];
const B = [4, 7, 9];
const C = [10, 20, 30];
const D = [1, 2, 3];

canAchieveK(N, K, A, B, C, D);

実装のポイント

  1. Set（集合）を使って探索を O(1) に

    • AB のリストをハッシュセットにすることで、CD の各要素を検索する操作を O(1) に短縮。

  2. メモリ使用量を最小限に抑える

    • AB は N^2 のサイズなので、N=1000 なら 10^6 個の要素であり許容範囲。

実行結果

入力

3 50
3 9 17
4 7 9
10 20 30
1 2 3

出力

Yes