Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Regular Contest 157 A問題 XXYYX

AtCoder ARC157 ARC 300 pts A問題

問題
提出解答
問題の概要
- 制約
解法

問題

提出解答

問題の概要

$\texttt{X}, \texttt{Y}$ からなる長さ $N$ の文字列 $S$ のうち, 以下を満たすものは存在するか?

のなかでつの文字が隣り合う箇所のうち
- $\texttt{XX}$ がちょうど $A$ 箇所
- $\texttt{XY}$ がちょうど $B$ 箇所
- $\texttt{YX}$ がちょうど $C$ 箇所
- $\texttt{YY}$ がちょうど $D$ 箇所

制約

$1 \leq N \leq 2 \times 10^5$
$A,B,C,D \geq 0$
$A+B+C+D=N-1$

解法

次のような問題に帰着させる.

以下は同値である.

条件を満たす文字列が存在する.
以下で定義される有向グラフ上にオイラー路が存在する.
- $V=\{X,Y\}$
- $\overrightarrow{XX}$ が $A$ 本, $\overrightarrow{XY}$ が $B$ 本, $\overrightarrow{YX}$ が $C$ 本, $\overrightarrow{YY}$ が $D$ 本

各孤の始点と終点に対応する頂点が隣り合う $2$ つの文字に対応する.

ここで, 有向グラフ $F'=(V',E')$ において, オイラー路が存在するための必要条件は

全ての頂点の相対次数が $0$ である.
ある $1$ 頂点の相対次数が $1$ , 別の頂点の相対次数が $-1$ , 残りの全ての頂点の相対次数が $0$ である.

ことのどちらか一方が成立することである. なお, ここで, 相対次数とは, 出次数 $-$ 入次数して定義される.

各場合について考える. ここで, いま, $D$ には $2$ 頂点しかないので, 条件を満たす文字列が存在するための必要条件は $\lvert B-C \rvert \leq 1$ である.

$B-C$ の値で場合分けする.

$B-C=1$ のとき, 上から順に以下のように経由すれば, オイラー路が存在する.

$\overrightarrow{XX}$ を $A$ 回
$\overrightarrow{XY}$
$\overrightarrow{YY}$ を $D$ 回
$\overrightarrow{YX}, \overrightarrow{XY}$ を $C$ セット

$B-C=-1$ のときも $B-C=1$ の場合と同様に存在する.

$B-C=0$ のとき

(ア) $B \neq 0$ のとき, 上から順に以下のように経由すれば, オイラー路が存在する.

$\overrightarrow{XX}$ を $A$ 回
$\overrightarrow{XY}$
$\overrightarrow{YY}$ を $D$ 回
$\overrightarrow{YX}$
$\overrightarrow{YX}, \overrightarrow{XY}$ を $B$ セット

(イ) $B=0$ のとき, $C=0$ でもあるから, 別の頂点に移動できない. よって, $A=0$ または $D=0$ でなくてはならない. 逆に, $A=0$ または $D=0$ の場合は存在する.

以上から,

$\lvert B-C\rvert=1 \lor (B=C \land (B \neq 0 \lor (A=0 \lor D=0)))$

かどうかを判定すれば良い.