Akash and Akhil

アルゴリズム概要

n 個のボール [0, 1, 2, …, n-1] が並んでいる。 以下の操作をステップ i = 0, 1, …, n-1 の順に実施する： 配列[i : n] を in-place で逆順にする

最終的にボール番号 k が何番目のインデックスにあるかを答える。 シミュレーションすると最終配列には明確なパターンがあり、閾値 τ = ⌊n/2⌋ を使って O(1) で答えられる。

入力:
2
3 1   ← n=3, k=1
5 2   ← n=5, k=2

出力:
2
4

ステップバイステップ解説

Python 実装

HackerRank 形式・型注釈付き。競技用と業務用の2パターンを掲載。

from __future__ import annotations
import sys
from typing import Final

input = sys.stdin.readline


def solve_competitive(n: int, k: int) -> int:
    """
    競技プログラミング向け実装（性能最優先）

    最終配列パターン:
      偶数インデックス: n-1, n-2, n-3, ...
      奇数インデックス: 0, 1, 2, ...

    閾値 tau = n // 2 で分岐:
      k <  tau  →  奇数位置  →  2*k + 1
      k >= tau  →  偶数位置  →  2*(n-1-k)

    Time : O(1)
    Space: O(1)
    """
    tau: Final[int] = n >> 1          # n // 2（ビットシフト）
    if k < tau:
        return (k << 1) | 1           # 2*k + 1
    return (n - 1 - k) << 1           # 2*(n-1-k)


def solve_production(n: int, k: int) -> int:
    """
    業務開発向け実装（型安全・エラーハンドリング重視）

    Args:
        n: ボールの総数 (n >= 1)
        k: 検索するボール番号 (0 <= k < n)
    Returns:
        ボール k の最終インデックス (0-based)
    Raises:
        ValueError: n または k が制約を満たさない場合
    """
    if n < 1:
        raise ValueError(f"n must be >= 1, got {n}")
    if not (0 <= k < n):
        raise ValueError(f"k must satisfy 0 <= k < n, got k={k}, n={n}")

    tau: Final[int] = n // 2

    # k < tau  →  奇数インデックスに配置  →  2*k + 1
    if k < tau:
        return 2 * k + 1

    # k >= tau  →  偶数インデックスに配置  →  2*(n-1-k)
    return 2 * (n - 1 - k)


if __name__ == "__main__":
    t: int = int(input().strip())
    for _ in range(t):
        parts = input().rstrip().split()
        n_val: int = int(parts[0])
        k_val: int = int(parts[1])
        print(solve_competitive(n_val, k_val))

フローチャート

フローの説明：
1. n と k を受け取り、閾値 τ = ⌊n/2⌋ を計算する。
2. k < τ なら奇数インデックス側 → 2·k + 1 を返す。
3. k ≥ τ なら偶数インデックス側 → 2·(n−1−k) を返す。
4. テストケース数 t 回だけループする（紫の破線）。

計算量分析