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: