問題

a, b, c, d, e の5種類の文字を使った新しい言語を考える。これらの文字は以下の2種類のタイプに分けられる。

タイプ V : a と e が該当する
タイプ C : b と c と d が該当する

この言語では、CV もしくは CVC の形になるものが1音節となる。例えば、 ba, ced, bab は音節に該当するが、 aa, eda, baba は該当しない。

この言語にて、単語とは1個以上の音節から構成されるものを表す。単語が与えられるので、どのような音節から構成されているかを表示せよ。

例えば、 bacedbab という単語は、 ba.ced.bab と構成される。（ただし、 . は音節の境界を示す。）

入力

まず最初の1行目に、テストケースの個数を表す整数 $t$ が与えられる。

その後、 $t$ 個のテストケースのそれぞれに対して、以下のように入力が与えられる。

最初の1行目には、整数 $n$ が与えられる。
次の1行には、 $n$ 文字の文字列が与えられる。

条件

実行時間制限: 1s
メモリ制限: 256MB
$1 \leq t \leq 100$
- すべてのテストケースにおける $n$ の値の合計は $2 \cdot {10}^{5}$ を超えない。
与えられる文字列はすべて a, b, c, d, e のいずれかの文字から構成される単語である。

出力

$t$ 行にわたり、各テストケースについて、与えられた単語を . を用いて1音節ずつに分割した状態で出力すること。

解法

音節は CV もしくは CVC の形をとることから、与えられる単語は CVC... という形になります。このときに、最初の音節にあたる部分が CV の形なのか CVC の形なのかということが問題になります。

ここで、与えられる文字列は単語の形をしているため、必ず音節に区切ることができます。すなわち、区切った以降の文字列についても単語の形をしているため、単語は必ず CV + （単語） もしくは CVC + （単語） という形で与えられるということが言えます。

以上から、与えられた文字列の $i$ 文字目以降の部分が単語の形をしていれば、 $i - 1$ 文字目と $i$ 文字目の間の部分に . を打つことで、音節ごとに単語を区切ることができます。

$i$ 文字目以降の部分については、

$i$ 文字目が C, $i + 1$ 文字目が V であり、 $i + 2$ 文字目以降の部分が単語である
$i$ 文字目が C, $i + 1$ 文字目が V, $i + 2$ 文字目が C であり、 $i + 3$ 文字目以降の部分が単語である

のいずれかの条件を満たせば、単語であると判定することができます。

これを再帰的に実装することで、各テストケースにおいて $O(n)$ の計算量で、音節ごとに単語を区切ることができます。

ソースコード

まず、 $i - 1$ 文字目と $i$ 文字目の間に . を打つことができるかどうかを判定する関数 have_period() を以下のように実装しました。

int n;
string s; // 入力される文字列
bool period[int(2e5 + 5)]; // period[i] は i - 1 文字目と i 文字目の間に . を打つことができるかを表す
bool visited[int(2e5 + 5)]; // visited[i] は i 文字目以降が単語かどうかを調べたかどうかを表す

// 与えられた文字が C タイプなのかを判定する関数 is_c()
bool is_c(char c) { return (c == 'b' || c == 'c' || c == 'd'); }

bool have_period(int idx) { // idx 文字目以降が単語かどうかを判定する
  if (idx == n) {
    // 引数の idx が n と等しいならば考える部分は空文字列であり、これは単語とみなして true を返す
    return period[idx] = true;
  }
  if (visited[idx]) {
    // もし引数の idx を既に調べていたならば、 period[idx] をそのまま返す
    return period[idx];
  }

  // idx について調べたことにする
  visited[idx] = true;

  bool ans = false; // 最終的にピリオドを打てるのかを表す bool 値の ans
  if (idx + 2 <= n && is_c(s[idx]) && !is_c(s[idx + 1])) {
    // CV の形になっていれば、 idx + 2 での結果を調べて ans を更新する
    ans = ans | have_period(idx + 2);
  }
  if (idx + 3 <= n && is_c(s[idx]) && !is_c(s[idx + 1]) && is_c(s[idx + 2])) {
    // CVC の形になっていれば、 idx + 3 での結果を調べて ans を更新する
    ans = ans | have_period(idx + 3);
  }

  return period[idx] = ans; // 最終的に period[idx] の値を更新して、それを返す
}

この have_period() 関数が実装されている状態で、区切られた文字列を出力する solve() 関数を以下のように実装しました。

int n;
string s; // 入力される文字列
bool period[int(2e5 + 5)]; // period[i] は i - 1 文字目と i 文字目の間に . を打つことができるかを表す
bool visited[int(2e5 + 5)]; // visited[i] は i 文字目以降が単語かどうかを調べたかどうかを表す

void solve() {
  // 値の入力
  cin >> n;
  cin >> s;

  // period, visited の初期化を行う
  fill(period, period + n, false);
  fill(visited, visited + n, false);

  // have_period() 関数を用いて、 s[0] 以降の部分が単語かどうかを判定する
  have_period(0);

  // 最終結果の表示
  for (int i = 0; i < n; i++) {
    // period[i] が true ならば、 i - 1 文字目と i 文字目の間に . を出力する（このときに、先頭の文字には . は打たないので、 i > 0 の条件を足している）
    if (i > 0 && period[i]) {
      cout << ".";
    }
    // s[i] を出力する
    cout << s[i];
  }
  cout << endl;

  return;
}

提出したコード: https://codeforces.com/contest/1915/submission/240083102
GitHub

感想

難易度こそ少し上がりますが、この問題に似ていると思いました。

どちらの問題も再帰を使わず、文字列を後ろから見ていくことによっても解くことはできると思うのですが、前から見ていく方が直感的かと思いまして、今回はこのように解いています。

yutasの競技プログラミング勉強帖

競技プログラミングの問題についての解説記事を主に書いています。

D - Unnatural Language Processing / Codeforces Round 918 (Div. 4)

問題

入力

条件

出力

解法

ソースコード

感想