[BOJ 9519, CPP] 眠い

問題リンク

[BOJ 9519](https://www.acmicpc.net/problem/9519

)

分類

実装、文字列、シミュレーション

説明

この問題については、最初は全探索による解法を試みた。

• まず文字列の長さを測定

• 0 ～ 文字列の長さ分の数値ベクトルを割り当て

• 問題の条件に従って繰り返し反転

• 指定回数だけ反転させた場合、そのハッシュ値を利用して逆順に配置

• 元の姿を確認できる！

ここで最も重要な点は、問題の条件に従って繰り返し反転させることだが、繰り返し反転させた場合、必ず初期配列と同じ状態に戻る周期が存在するという点が核心である。

上記の規則を見つけた後、その部分を細分化すると

• まず文字列の長さを測定

• 0 ～ 文字列の長さ分の数値ベクトルを割り当てる

  • 1回目から（文字列の長さ - 1）回目まで周期をチェック

  • 全体の反転回数を周期で割った回数だけ繰り返し、ハッシュを導出

• 指定回数だけ反転させた場合、そのハッシュ値を利用して逆順に配置

• 元の状態を確認できる！

このようになる。

    for (int i = 1; i <= target_length - 1; i++)
    {
        for (int j = 0; j < target_length / 2; j++)
        {
            temp = result.back();
            result.pop_back();
            result.insert(result.begin() + 2 * j + 1, temp);
        }

		if (start_vector == result)
		{
			cycle = i;
			break ;
		}
    }

当初は上記のように配列を直接操作する方式を採用していたが、この場合、insert以降の配列をすべて移動させる必要があり、一種のオーバーヘッドが発生するため、処理時間が若干長くなる傾向が見られた。

    for (int i = 1; i <= target_length - 1; i++)
    {
		temp_vector.clear();
		temp_vector.resize(target_length);
        for (int j = 0; j < target_length; j++)
        {
			if (!(j % 2))
				temp_vector[j] = result[j / 2];
			else
				temp_vector[j] = result[target_length - 1 - (j / 2)];
        }

		if (start_vector == temp_vector)
		{
			cycle = i;
			break ;
		}
		else
			result = temp_vector;
    }

そこで、以降は上記のような方式を用いて配列を事前に作成し、値を一つずつ挿入する方式を採用することで、最大でも配列の長さ分の時間しかかからないようにした。

解答コード

// 졸려

#include <iostream>
#include <vector>

using namespace std;

vector<int> flicker_action(int target_length, int count);

int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int flicker_number;
    string result_string, init_string;
    vector<char> string_vector;
    vector<int> idx_vector;

    cin >> flicker_number;
    cin.ignore();
    getline(cin, result_string);

    for (int i = 0; i < (int) result_string.length(); i++)
        string_vector.push_back(result_string[i]);
    

    idx_vector = flicker_action(result_string.length(), flicker_number);
    init_string.resize(result_string.length());

    for (int i = 0; i < (int) result_string.length(); i++)
        init_string[idx_vector[i]] = result_string[i];

    cout << init_string << endl;
    return (0);
}

vector<int> flicker_action(int target_length, int count)
{
    vector<int> result, temp_vector, start_vector;
	int cycle;

    for (int i = 0; i < target_length; i++)
        result.push_back(i);

	start_vector = result;
	cycle = 1;

    for (int i = 1; i <= target_length - 1; i++)
    {
		temp_vector.clear();
		temp_vector.resize(target_length);
        for (int j = 0; j < target_length; j++)
        {
			if (!(j % 2))
				temp_vector[j] = result[j / 2];
			else
				temp_vector[j] = result[target_length - 1 - (j / 2)];
        }

		if (start_vector == temp_vector)
		{
			cycle = i;
			break ;
		}
		else
			result = temp_vector;
    }

	result = start_vector;

    for (int i = 0; i < (count % cycle); i++)
    {
		temp_vector.clear();
		temp_vector.resize(target_length);
        for (int j = 0; j < target_length; j++)
        {
			if (!(j % 2))
				temp_vector[j] = result[j / 2];
			else
				temp_vector[j] = result[target_length - 1 - (j / 2)];
        }

		result = temp_vector;
    }

    return (result);
}