【C++】試験監督に見つからずに課題を受け渡すアルゴリズムの実装方法

問題概要

このチュートリアルでは、試験監督に見つかることなく課題を受け渡すためのアルゴリズムをC++で実装する方法を解説します。各学生は試験監督に課題を提出しなければなりません。ここで、学生Aの課題が学生Bの手元にあるという状況を考えてみましょう。学生Bは、試験監督に気づかれることなく課題を学生Aへ返却しなければなりません。

すべての学生は一列に並んで着席しています。私たちの狙いは、監督に見つからずに課題を学生Aのもとへ戻す方法を見つけることです。課題を受け渡しできる条件は以下のとおりです。

• ある学生（インデックスi）は、隣のインデックス（i-1）または（i+1）に座る学生にのみ課題を渡すことができる
• 学生は課題を「渡す」「受け取る」「保持する」のいずれかの行動を選択できる
• 試験監督は常に区間 [il, rl] にいる学生を見張っている
• 監視範囲内にいる学生は、課題を送ったり受け取ったりすることができない
• ただし、監視範囲内であっても課題を手元に保持しているだけであれば、見つかることはない

入力と出力の形式

入力として4つの値 p、q、r、s が与えられます。p は学生の総人数、q は試験監督による監視ステップの総数、r は課題を持つ出発側の学生の位置、s は受け取る側の学生の位置を表します。

さらに、各監視ステップ q には次の3つの情報が含まれます。

• 試験監督が指定された区間を監視する時刻
• 監視対象となる最も左側のインデックス（境界を含む）
• 監視対象となる最も右側のインデックス（境界を含む）

出力として必要なのは、「Left」「Right」「Keep」という3種類の単語からなる系列です。それぞれ、学生が課題を左または右に渡すのか（Left／Right）、それとも手元に保持するのか（Keep）を表します。

サンプルケース

入力

8 3 2 7
1 4 6
2 1 8
3 5 6

出力

Right
Keep
Right
Right
Right
Right

解説

この指示に従うことで、インデックス2の学生からインデックス7の学生へ、試験監督に見つかることなく課題が届きます。

入力

5 1 1 3
1 2 5

出力

Keep
Right
Right

解説

この指示に従うことで、インデックス1の学生からインデックス3の学生へ、試験監督に見つかることなく課題が届きます。

解法のアプローチ

ある時点において、試験監督がその区間を監視しており、現在課題を持っている学生、あるいは課題を送ろうとしている相手の学生が監視範囲内にいる場合には、その学生は課題を手元に保持します（Keep）。そうでない場合は、最終的な目標となる学生の方向へ向かう隣の学生に課題を渡します（RightまたはLeft）。

C++による実装例

#include <bits/stdc++.h>
using namespace std;
void solve(int p, int q, int r, int s,
long t[], int l[], int ar[]){
   int dir;
   string val;
   if (r < s) {
      dir = 1;
      val = "Right";
   } else {
      dir = -1;
      val = "Left";
   }
   string answer = "";
   int i = 0, current = r;
   long tim = 1;
   while (1) {
      if (i < q && tim == t[i]) {
         if ((current >= l[i] && current <= ar[i]) ||
         (current + dir >= l[i] && current + dir <= ar[i])) {
            answer += "Keep\n";
            tim++;
            i++;
            continue;
         }
         i++;
      }
      current += dir;
      answer += val+"\n";
      tim++;
      if (current == s)
         break;
   }
   cout << answer << endl;
}
int main(){
   int p = 8, q = 3, r = 2, s = 7;
   long t[q + 2] = { 1,2,3 };
   int l[q + 2] = { 4,1,5 };
   int ar[q + 2] = { 6,8,6 };
   solve(p, q, r, s, t, l, ar);
   return 0;
}

出力結果

Right
Keep
Right
Right
Right
Right

まとめ

本チュートリアルでは、試験監督に見つからずに課題を受け渡すアルゴリズムを、C++のコードとともに学びました。同じロジックはJavaやPythonなど、他のプログラミング言語でも実装できます。このアルゴリズムは競技プログラミングにおいて重要な考え方の一つであり、現実世界の問題をC++のコードで解決する良い例と言えるでしょう。本チュートリアルが皆様のお役に立てば幸いです。