C++で目的のページにたどり着くための最小ページめくり回数を求める方法

問題の概要

Nページからなる本が与えられたとき、目的のページKに到達するために必要な最小のページめくり回数を計算するのがこの問題です。

この問題には以下のルールがあります。

• ページめくりは、本の前側(1ページ目)から始めることも、後ろ側(Nページ目)から始めることもできます。
• 各ページは表と裏の2面を持っています。ただし、最初のページは裏面のみ、最後のページも本の総ページ数によっては裏面のみの場合があります。

具体例

N = 5、K = 4 の場合を考えてみましょう。このとき最小のページめくり回数は 1回 となります。

• 前からめくる場合: 2回必要です。(1) → (2, 3) → (4, 5)
• 後ろからめくる場合: 1回で済みます。(4, 5) を一度開くだけです。

したがって、最小のページめくり回数は 1 となります。

アルゴリズム

この問題は、以下の式を使って効率的に解くことができます。

1. Kが偶数の場合:
   前からの距離 = (K - 0) / 2
   後ろからの距離 = (N - 1 - K) / 2

2. Kが奇数の場合:
   前からの距離 = (K - 1) / 2
   後ろからの距離 = (N - K) / 2

つまり、前から数えた場合と後ろから数えた場合のそれぞれのめくり回数を計算し、そのうち小さい方を採用すればよいのです。

C++での実装例

以下は、上記のアルゴリズムをC++で実装したコードです。

#include <iostream>
#include <algorithm>
using namespace std;

int getMinPageTurns(int n, int k){
    // 最終ページが片面のみの場合に対応するため調整
    if (n % 2 == 0) {
        ++n;
    }
    // 前からと後ろからのめくり回数の小さい方を返す
    return min((k + 1) / 2, (n - k + 1) / 2);
}

int main(){
    int n = 5, k = 4;
    cout << "Required page turns = " << getMinPageTurns(n, k) << endl;
    return 0;
}

実行結果

上記のプログラムをコンパイルして実行すると、以下の出力が得られます。

Required page turns = 1

解説

このコードのポイントは以下の通りです。

• (k + 1) / 2: 前からページをめくった場合に必要な回数を整数除算で求めています。
• (n - k + 1) / 2: 後ろからページをめくった場合に必要な回数を求めています。
• n % 2 == 0 のチェック: 総ページ数が偶数の場合、最後のページが片面のみになるため、n を1増やして計算を整えています。

このように、単純な数式と標準ライブラリの min 関数を組み合わせることで、条件分岐を最小限に抑えたシンプルかつ効率的な実装が可能になります。計算量は O(1) であり、どんなにページ数が多くても一定時間で答えを求められます。