JOI 二次予選 2021 A - 往復すごろく (AOJ 0691, 難易度 5)

結構アドホックで難しいと思った！

• 問題へのリンク

問題概要

マスが横一列に並んだすごろくが与えられる ( と番号づけされている)。すごろくの各マスは . と x と # のいずれかである。

• マス とマス は X である
• 他のマスは長さ の文字列 で与えられる
  • X は含まず、. と # のみである

このすごろくのマス () に、コマを右向きに配置する。このすごろくには次のようなルールが設定されている。

• X が書かれたマスに駒が乗ると、駒の向きは反転する
• . が書かれたマスに駒が乗ったとしても、何も起こらない
• # が書かれたマスに駒が乗ると、駒の向きは反転する。このとき、このマスに書かれた文字を . に変更する。したがって、その後はこのマスに駒が乗ったとしても向きは反転しない。

なお、駒の反転や文字の変更にかかる時間は無視できる。すごろくと駒の初めの状態が与えられたとき、# が書かれたマスがすべてなくなるまでに要する時間を求めるプログラムを作成せよ。

制約

• 

考えたこと

グリッド上の各点の間を動いていく問題は

• グリッドの各マスについて考えていく (データとしては文字列 S を直接扱う)
• グリッドの特別な点の index を格納したベクトルを考えて、それを考えていく (データとしては index を格納した vector<int> 型の変数をもつイメージ)

という 2 つの考え方があるように思う。今回は後者の考え方がぴったりになる。具体的には、たとえば = #..#.##. という場合には、それを というデータに変換して考える。

マス の左側と右側のそれぞれの index を考える

そして今回はさらに、マス の左側と右側の index を格納したベクトル (lefts と rights とする) をそれぞれ考えよう。そしてそれらを、 に近い方から格納していく。

たとえば = #..#.###.#, のときは、次のようになる。

• lefts =
• rights =

そして、rights → lefts → rights → lefts → ... という順序で、「先頭要素を取り出してそこに移動する」というのを繰り返して行けば OK。先頭要素を取り出していく処理は、vector を deque で実装しておけば pop_front() 関数が使える。このような細部の実装方法は色々ある。

また、lefts と rights とで要素数に差があるとき、どちらかが先に枯渇することがある。lefts が枯渇した場合は目的値となる index を として、rights が枯渇した場合は目的値となる index を とする。lefts と rights の両方が空になった時点で処理を終了する。

計算量は となる。

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N, A;
    string S;
    cin >> N >> A >> S;
    deque<int> lefts, rights;
    for (int i = 0; i < N; ++i) {
        if (S[i] != '#') continue;
        if (i+1 < A) lefts.push_back(i+1);
        else rights.push_back(i+1);
    }
    reverse(lefts.begin(), lefts.end());

    long long res = 0, prev = A, nex;
    int to_right = 1; // 1; rights へ、0: lefts へ
    while (!lefts.empty() || !rights.empty()) {
        if (to_right) {
            nex = (!rights.empty() ? rights[0] : N+1);
            if (!rights.empty()) rights.pop_front();
        } else {
            nex = (!lefts.empty() ? lefts[0] : 0);
            if (!lefts.empty()) lefts.pop_front();
        }
        res += abs(nex - prev);
        prev = nex;
        to_right = 1 - to_right;
    }
    cout << res << endl;
}