Official

C - Slot Strategy Editorial by mechanicalpenciI


まず、揃える文字を固定したときについて考えます。 例えば、 0 を揃えるとします。

\(j=0,1,\ldots,9\) について、 \(i=1,2,\ldots,N\) のうち \(S_i\)\(j\) 文字目が 0 であるようなものの個数を \(count(0,j)\) とします。

このとき、ある \(j\) について \(count(0,j)\geq 1\) かつ \(t<10\times (count(0,j)-1)+j\) ならば \(t\) 秒後までにすべてのリールを 0 に揃えることはできません。なぜなら \(j\) 文字目が 0 であるようなリールをすべて 0 を表示させて止めるには \(t'\bmod{10}=j\) であるような相異なる非負整数 \(t'\) においてボタンを押すことを \(count(0,j)\) 回繰り返さなくてはならないからです。
逆に、\(\displaystyle\max_{j=0,1,\ldots,9} (10\times (count(0,j)-1)+j)\) 秒経過するまでにはこれを達成することができます。 各時刻 \(t'\) について、\((t'\bmod{10})+1\) 文字目が 0 であり、まだ止まっていないならばそのリールを選んで停止させることを繰り返せばよいです。

同じことが 1, 2, \(\ldots\) , 9 に対しても成り立ち、求めたい値はそのうちの最小値となります。

よって、答えは

\[ \displaystyle\min_{k=0,1,\ldots,9}\left( \max_{j=0,1,\ldots,9} (10\times (count(k,j)-1)+j)\right) \]

として求めることができます。 ただし、\(count(k,j)\) で、 \(i=1,2,\ldots,N\) のうち \(S_i\)\(j\) 文字目が \(k\) であるようなものの個数を表すとします。

なお、特定の文字を揃えるのにかかる時間は高々 \(10N-1\) 秒であるため、揃える文字を決めた上でシミュレーションを行っても十分制限時間内に答えを出すことができます。

c++ による実装例:

#include <bits/stdc++.h>
using namespace std;

int main(void) {
	int n;
	string s[100];
	int cnt[10][10];
	int ans, mx;
	for (int i = 0; i < 10; i++) {
		for (int j = 0; j < 10; j++)cnt[i][j] = 0;
	}

	cin >> n;
	for (int i = 0; i < n; i++)cin >> s[i];

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < 10; j++) {
			cnt[(s[i][j] - '0')][j]++;
		}
	}

	ans = 1000;
	for (int i = 0; i < 10; i++) {
		mx = 0;
		for (int j = 0; j < 10; j++) {
			mx = max(mx, 10 * (cnt[i][j] - 1) + j);
		}
		ans = min(ans, mx);
	}

	cout << ans << endl;

	return 0;
}

Python による実装例:

n=int(input())
s=[]
for i in range(n):
	s.append(input())

cnt=[[0 for j in range(10)]for i in range(10)]
for i in range(n):
	for j in range(10):
		cnt[int(s[i][j])][j]= cnt[int(s[i][j])][j]+1

mx=[0 for i in range(10)]
for i in range(10):
	for j in range(10):
		mx[i]=max(mx[i], 10 * (cnt[i][j] - 1) + j)

print(min(mx))

posted:
last update: