C++で数直線上に訪れた異なる地点の数をカウントする方法

0と1からなる2進数列が与えられます。ある人が current_pos に格納された位置（地点）にいると仮定します。この位置を起点として、2進数列の値が 0 であれば1ステップ左へ移動し（current_pos - 1）、1 であれば1ステップ右へ移動します（current_pos + 1）。目的は、2進数列をすべて処理し終えた後に、訪れた異なる位置（地点）の数を求めることです。

この問題は、各地点が訪問された回数（頻度）を記録することで解けます。頻度がゼロでなければ、異なる地点のカウントを1つ増やします。

入力例

Path[]= "001100" current_pos=3

出力例

数直線上で訪れた異なる地点の数: 3

解説

path[0] から処理を開始し、初期位置は 3 です。

Path[0]: 0 → 左へ移動 ...currpos=2
Path[1]: 0 → 左へ移動 ...currpos=1
Path[2]: 1 → 右へ移動 ...currpos=2
Path[3]: 1 → 右へ移動 ...currpos=3
Path[4]: 0 → 左へ移動 ...currpos=2
Path[5]: 0 → 左へ移動 ...currpos=1

異なる位置の合計は 3 で、訪れた地点は 1、2、3 です。

入力例

Path[]= "010101" current_pos=5

出力例

数直線上で訪れた異なる地点の数: 2

解説

path[0] から処理を開始し、初期位置は 5 です。

Path[0]: 0 → 左へ移動 ...currpos=4
Path[1]: 1 → 右へ移動 ...currpos=5
Path[2]: 0 → 左へ移動 ...currpos=4
Path[3]: 1 → 右へ移動 ...currpos=5
Path[4]: 0 → 左へ移動 ...currpos=4
Path[5]: 1 → 右へ移動 ...currpos=5

異なる位置の合計は 2 で、訪れた地点は 4 と 5 です。

プログラムで使用しているアプローチ

• 0と1からなる文字列を path に格納します。
• current_pos に開始地点を格納します。
• 関数 getDistinctPoints(int current_pos, string path) は、現在位置とパスを引数に受け取り、異なる地点の数を返します。
• 変数 len には path の長さを格納します。
• 配列 frequency[21] は、各地点が訪問された回数を格納するために使用します。インデックスが地点を表し、扱う範囲は 0〜20 です。
• path 文字列の走査を開始します。
• 現在の値が 0 の場合は左へ移動し（current_pos - 1）、訪問回数を frequency[current_pos]++ で更新します。
• それ以外（現在の値が 1）の場合は右へ移動し（current_pos + 1）、訪問回数を frequency[current_pos]++ で更新します。
• 次に frequency 配列を走査し、ゼロ以外の値ごとにカウントを増やします。
• count には訪れた異なる地点の数が格納されます。
• count を結果として返します。

サンプルコード

#include <bits/stdc++.h>
using namespace std;
// 0〜20の範囲で訪れた異なる地点の数を求める
int getDistinctPoints(int current_pos, string path){
    // path の長さ
    int len = path.length();
    int count=0;
    // 各地点の訪問回数を格納する配列
    int frequency[21]={0};
    // path 内のすべての移動指示に対して
    for (int i = 0; i < len; i++) {
        // 左方向の場合
        if (path[i] == '0') {
            current_pos--;
            frequency[current_pos]++; // 訪問回数を増やす
        }
        // 右方向の場合
        else {
            current_pos++;
            frequency[current_pos]++; // 訪問回数を増やす
        }
    }
    for(int i=0;i<21;i++)
        if(frequency[i]!=0) // 訪問済みなら frequency[i] はゼロ以外
            count++;
    return count;
}
int main(){
    int current_pos = 3;
    string path = "011101100";
    cout << "数直線上で訪れた異なる地点の数: " << getDistinctPoints(current_pos, path);
    return 0;
}

出力

数直線上で訪れた異なる地点の数: 5

このアルゴリズムの計算量は、パスの長さを n とすると O(n) です。訪問頻度を配列で管理することで、各地点の到達回数を効率的に記録でき、最後にゼロ以外の要素を数えるだけで異なる地点の総数が求まります。移動範囲が配列のサイズを超える可能性がある場合は、unordered_map や set を使うとより柔軟に対応できます。