Kazun の競プロ記録

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

AtCoder Beginner Contest 268 F問題 Best Concatenation

AtCoder ABC268 ABC F問題 500 pts

問題

atcoder.jp

提出解答

atcoder.jp

問題の概要

{\tt X}, {\tt 1}, \cdots, {\tt 9} からなる文字列 T に対するスコア \operatorname{score}(T) を次のように定める.

  • a=1,2, \dots, 9 に対して, 1 \leq i \lt j \leq |T|, T_i={\tt X}, T_j=a をみたす整数の組 (i,j) の数を E_a とする.
  • \displaystyle \operatorname{score}(T):=\sum_{a=1}^9 a E_a

N 個の {\tt X}, {\tt 1}, \cdots, {\tt 9} からなる文字列 S_1, \dots, S_N に対して, (1,2, \dots, N) の並び替え P に対する \operatorname{score}(S_{P_1} \oplus \dots \oplus S_{P_N}) を全て考えた時のスコアの最大値を求めよ.

制約

  • 2 \leq N \leq 2 \times 10^5
  • S_i は {\tt X}, {\tt 1}, \cdots, {\tt 9} からなる非空文字列
  • |S_1|+\dots+|S_N| \leq 2 \times 10^5

解法

P を (1,2, \dots, N) の並び替えとし, 1 \leq i \lt j \leq N に対して, Q を P の第 i 項と第 j 項を入れ替えて得られる並び替えとする. そして,

  • A:=S_{P_1} \oplus \dots \oplus S_{P_N}
  • B:=S_{Q_1} \oplus \dots \oplus S_{Q_N}

とする. このとき, \Delta:=\operatorname{score}(B)-\operatorname{score}(A) について考える.

A から B に変化する時, スコアの増減は次のようにして起こる.

  • S_{P_i} にある {\tt X} と S_{P_j} にある数字のペアが寄与する分だけスコアが減る.
  • S_{P_j} にある {\tt X} と S_{P_i} にある数字のペアが寄与する分だけスコアが増える.

このとき, よく見ると {\tt X} と数字のペアの要素はそれぞれ独立に選べることから, S_{P_i} にある {\tt X} の数と数字の総和をそれぞれ \alpha_i, \beta_i とする. \alpha_j, \beta_j も同様に定義する. \Delta:=\beta_i \alpha_j-\alpha_i \beta_j である.

よって, 非負整数 x に対して \dfrac{x}{0} を +\infty と定義することによって,

\Delta \leq 0 \iff \dfrac{\beta_i}{\alpha_i} \leq \dfrac{\beta_j}{\alpha_j}

このことから, スコアを最大にするためには, \varphi_i:=\dfrac{\beta_i}{\alpha_i} が昇順になるように (1,2, \dots, N) を並び替えればよい事がわかる. \varphi_i は S_i のみから定まるから, 計算量 \displaystyle O\left(\sum_{i=1}^N |S_i|+N \log N \right) 時間で適切な並び替えを求め, その文字列に対するスコアを求めれば良い.