Kazun の競プロ記録

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

AtCoder Beginner Contest 252 C問題 Slot Strategy

AtCoder ABC ABC252 C問題 300 pts

問題

提出解答

問題の概要

$N$ 個の $0,1, \dots, 9$ がちょうど $1$ 回ずつ現れる文字列 $S_1, \dots, S_N$ がある.

各リールは停止していない限り表示が毎秒 $S_0 \to S_1 \to S_2 \to \dots S_9 \to S_0 \to S_1 \to \dots$ と変化する.

$1$ 秒あたり高々 $1$ 個のリールを停止させることができるとき, 全てのリールが停止した上で同じ整数を表示させるのには何秒必要か?

制約

$1 \leq N \leq 100$
$S_i$ は $0,1, \dots, 9$ がちょうど $1$ 回ずつ現れる文字列.

解法

全てのリールが停止した上での表示させる整数に関して全探索する.

$a~(0 \leq a \leq 9)$ で揃えるとする. このとき, $j_1, \dots, j_N$ を $S_{i,j_i}=a$ となる整数とする (このような整数 $j_i$ は制約から唯一存在する) .

このとき, $0 \leq k \leq 9$ に対して, $j_1, \dots, j_N$ にある $k$ の個数を $\chi_j(k)$ と書く. このとき, $j_i=k$ となる全ての $i$ 番目のリールを $a$ を表示させて止めるためには, 最短でも $\max(0, 10(\chi_j(k)-1)+k)$ 秒必要である. そして, この目標は実際にこの時間で達成可能である.

そして, $k$ が異なればリールを同士において, 停止させる操作は互いに行なうことになる. よって, $a$ で揃える場合の最短時間は

$\displaystyle \max_{k=0,1,\dots,9} \max(0, 10(\chi_j(k)-1)+k)$

この議論は $a$ をある整数に固定していた. よって, この議論を $a=0,1, \dots,9$ に対して行い, それぞれの場合における最短時間を求め, それらの最小値が答えになる.