問題概要
英大文字・英小文字・括弧 ((, )) からなる文字列 $S$ が与えられる．括弧の対応は正しくとれている．
$S$ に対し，次の操作を可能な限り行う．
- 内側に括弧を含まない（この順で出現する）
(,)を選ぶ． - その括弧内側の各文字（必ず英文字である）の大文字・小文字を相互に変換する．
- その括弧の内側の文字列を反転する．
- その括弧を削除する．
操作完了後の文字列は一意に定まるので，それを求めよ．
制約
- $1 \leq |S| \leq 5 \times 10^5$
AtCoder Beginner Contest 350, D : New Friends
問題概要
$1$ から $n$ で番号付けられた $n$ 人の人がいて，$m $ 組の友好関係がある．友好関係は $m $ 項からなる列 $A, B$ によって表され，$i$ 番目の友好関係は人 $A_i$ と人 $B_i$ が友人同士であることを示す．
この人々に対し，次の操作を可能な限り行う．
- 人 $x, y, z$ であって，人 $x, y$ 及び人 $y, z$ はそれぞれ友達同士であるが，人 $x, z$ は友達同士でないような三人を選ぶ．
- 人 $x, z$ を友達同士にする．
操作は何回行われるか？
制約
- $2 \leq n \leq 2 \times 10^5$
- $0 \leq m \leq 2 \times 10^5$
- $\forall ( i, j ), i \neq j \Rightarrow ( A_i, B_j ) \neq ( A_j, B_j )$
AtCoder Beginner Contest 349, C : Airport Code
AtCoder Beginner Contest 349, E : Weighted Tic-Tac-Toe
問題概要
$3 \times 3$ のグリッド状の盤面があって，$i$ 行目第 $j$ 列には整数 $A_{ i, j }$ が書かれている．$A$ の総和は奇数である．
この盤面を使って Tic-tac-toe をする．Tic-tac-toe で勝敗が付いた場合は，その勝者の勝ちとする．引き分けだった場合は，それぞれのプレイヤーについて当該プレイヤーがマークしたセルに書かれている整数の和を得点とし，より大きい得点を獲得したプレイヤーの勝ちとする．
両者が最適にプレイしたときの勝者はどちらか？
制約
- $| A_{ i, j } | \leq 10^9$
AtCoder Beginner Contest 346, D : Gomamayo Sequence
問題概要
$n$ 項からなるバイナリ列 $S = \langle S_1, S_2, \dots, S_n \rangle$ ($S_i \in \{ 0, 1 \}$) が与えられる．$S$ に対し，次の操作を任意回適用できる．
- コスト $C_i$ かけて $S_i$ を反転する．
$S$ の添字 $i$ ($1 \leq i < n$) であって，$S_i = S_{ i + 1 }$ となるものが丁度ひとつであるようにするためにかかるコストの最小値はいくらか？
制約
- $2 \leq n \leq 2 \times 10^5$
- $1 \leq C_i \leq 10^9$
