競プロでよくある「バランスのとれた括弧列」の定義が壊れがちな話

なるほどなぁと思ったし周知しておくべきだと思ったので記事にしました。

よくある間違った定義 - 1

バランスのとれた括弧列は以下のいずれかの条件を満たす。

  1. 空文字列
  2. バランスのとれた括弧列{ \displaystyle A }が存在し、'(',{ \displaystyle A },')'をこの順に結合した文字列
  3. バランスのとれた括弧列{ \displaystyle A },{ \displaystyle B }が存在し、{ \displaystyle A },{ \displaystyle B }をこの順に結合した文字列

E - Parentheses

C - 部分文字列と括弧

よくある間違った定義 - 2

バランスのとれた括弧列は以下のいずれかの条件を満たす。

  1. '()'
  2. バランスのとれた括弧列{ \displaystyle A }が存在し、'(',{ \displaystyle A },')'をこの順に結合した文字列
  3. バランスのとれた括弧列{ \displaystyle A },{ \displaystyle B }が存在し、{ \displaystyle A },{ \displaystyle B }をこの順に結合した文字列

Problem G: Flipping Parentheses

Problem - 1272F - Codeforces

正しい定義 - 1

バランスのとれた括弧列は以下のいずれかのルールで構成される。

  1. 空文字列
  2. バランスのとれた括弧列{ \displaystyle A }が存在し、'(',{ \displaystyle A },')'をこの順に結合した文字列
  3. バランスのとれた括弧列{ \displaystyle A },{ \displaystyle B }が存在し、{ \displaystyle A },{ \displaystyle B }をこの順に結合した文字列

Star in Parentheses

正しい定義 - 2

バランスのとれた括弧列は以下のいずれかの条件を満たす空でない文字列である。

  1. '()'
  2. バランスのとれた括弧列{ \displaystyle A }が存在し、'(',{ \displaystyle A },')'をこの順に結合した文字列
  3. バランスのとれた括弧列{ \displaystyle A },{ \displaystyle B }が存在し、{ \displaystyle A },{ \displaystyle B }をこの順に結合した文字列

正しい定義 - 3

バランスのとれた括弧列は以下のいずれかの条件を満たす。

  1. 空文字列
  2. バランスのとれた括弧列{ \displaystyle A }が存在し、'(',{ \displaystyle A },')'をこの順に結合した文字列
  3. 空文字列でないバランスのとれた括弧列{ \displaystyle A },{ \displaystyle B }が存在し、{ \displaystyle A },{ \displaystyle B }をこの順に結合した文字列

K - 括弧

F - Bracket Sequencing

正しい定義 - 4

A bracket sequence is called regular if it is possible to obtain correct arithmetic expression by inserting characters "+" and "1" into this sequence.

Problem - 1132A - Codeforces

Codeforcesでよく使われる定義っぽい。

正しい定義 - 5

何が問題？

要するに、条件を満たす文字列集合が複数存在するのが問題です。

定義3は本当に正しい？

定義3を満たす集合の要素は定義5を満たすことを確認しましょう。

こういうのの典型テクとして、定義3を満たす集合のある要素が定義5を満たさないとして、満たさない最短の要素を持ってきて矛盾を導くというのがあります。こうすると、それより短い要素は定義5を満たしていることになります。

この最短の要素が定義3のどの条件を満たすかで場合分けします。

1) 空文字列

これは明らかに定義5を満たしています。

2) (A)

Aは定義5を満たすので、括弧の数は対応が取れています。また、

「0～i文字目までの'('の数」 == 「Aの0～i-1文字目までの'('の数 + 1」 >= 「Aの0～i-1文字目までの')'の数 + 1」 == 「0～i文字目までの')'の数 + 1」 > 「0～i文字目までの')'の数」

となるので、(A)も定義5を満たします。

3) AB

これも定義5を満たします。（証明は読者の演習問題とする。）（書くのが面倒になった。）

以上から、定義5を満たさない最短の要素は、定義3のどの条件を満たすとしても定義5を満たしてしまうので矛盾が導けました。したがって、定義3を満たす集合の要素は定義5を満たします。

逆に、定義5を満たす文字列の集合は定義3を満たすことを示す必要がありますが、面倒になったのでこれも読者の演習問題とします。

感想

正しい問題文を書くの難しい。。。

追記：正しい定義 - 6