数弱で解説を見てもよく分からなかったのですが、なんとかACできたので考え方を残しておきます。
問題
自分の回答
int main(void){ ll N;cin>>N; map<ll,vector<ll>> MP; REP(i, N) { string s;cin>>s; REP(j, 10) { MP[(s[j]-'0')].push_back(j); } } vector<ll> anss; REP(i, 10) { ll ans = 0; map<ll,ll> memo; REP(j, MP[i].size()) { memo[MP[i][j]]++; MP[i][j] += (memo[MP[i][j]]-1)*10; } sort(MP[i].begin(), MP[i].end()); int cur = 0; REP(j, MP[i].size()) { ans+=MP[i][j]-cur; cur = MP[i][j]; } anss.push_back(ans); } sort(anss.begin(), anss.end()); OUT(anss[0]); }
考え方
文字0~9のうち、揃える文字を固定し、それぞれ揃えるのに何秒かかるのかを計算、その最小値が答えになります。ここでは0に固定してみます。では、「揃えるのに何秒かかるか」はどのように計算すれば良いのでしょうか。ここで以下のように考えました。
- 一番短い秒数で止められるところに0があるリールを止める
- ↑で止めた秒数から一番短い秒数で止められるところに0があるリールを止める
- 繰り返し
具体的に入力1の場合の例を見ていきましょう。
3 1937458062 8124690357 2385760149
ここで、0がそれぞれの行において何番目(indexなので0始まり)にあるかを見てみます。すると、
リール1: 7
リール2: 6
リール3: 6
となります。これを先程のステップに当てはめてみます。
- 一番短い秒数で止められるところに0があるリールを止める
現在は0秒目なので、0が6の位置にあるリールが最も短い秒数、6秒で止められます。2つありますがどっちを止めても変わりはありません。ここではリール2を止めてみます。
- ↑で止めた秒数から一番短い秒数で止められるところに0があるリールを止める
さて、ここが問題になります。5秒経過時点で、一番短い秒数で止められるリールはどのように判定すれば良いのでしょうか。ここで、先ほどのindexの差を見ていきます。
リール1: 7-6=1 リール3: 6-6=0
となります。では、リール3を止めるのが最適解でしょうか？しかし、リール3は止められません。というのも、現在はリール1を6秒で止めています。次にリールを止められるのは7秒目なので、リール3を止めると 0 ではなく8文字目の 1 になってしまいます。次にリール3を 0 で止められるのはリールが一周してから、つまり 10秒後 なのです(入力例2とその出力を見ると分かりやすいです)。これを踏まえて先程の差を修正します。
リール1: 7-6=1 リール3: 16(本来の数字6+一周の10)-6=10
ということで、6秒目に1を止めた後は、1秒後にリール1を止めるのが最短になります。次にリール3を止める秒数を見ていきます。
3行目: 16-7 = 9
次は9秒後に止めるとリール3が0で揃います。ということで、0を揃えるのに6+1+9=16 秒かかることが分かりました。
これを0~9全てについて行い、最小値を求めます。
コード解説
各文字がそれぞれどのindexで出現しているかをmapで持ちます。例えば0の場合だと MP[0] = {6,6,7} のようになります。
ll N;cin>>N; map<ll,vector<ll>> MP; REP(i, N) { string s;cin>>s; REP(j, 10) { MP[(s[j]-'0')].push_back(j); } }
0~9までの文字について、それぞれ何秒かかれば揃えられるかを求めるコードです。mapの memo は、indexが同じ文字をカウントするのに使っています。MP[0] = {6,6,7} の場合、6が2つあります。どちらかは一周しないと揃えられないので 16 にする必要があるため、(出現回数-1)*10 を加算しています。実行後は MP[0] = {6,16,7} となります。
前処理を行ったらソートします。こうすれば最短秒数で揃えられる順序で並んでいるので、現在時間(cur)を0秒に設定、それぞれについてcurとの差を見足し、curを更新していきます。最後にanssに結果をぶち込み、その最小値を出力すれば終了です。
REP(i, 10) { ll ans = 0; map<ll,ll> memo; REP(j, MP[i].size()) { memo[MP[i][j]]++; MP[i][j] += (memo[MP[i][j]]-1)*10; } sort(MP[i].begin(), MP[i].end()); int cur = 0; REP(j, MP[i].size()) { ans+=MP[i][j]-cur; cur = MP[i][j]; } anss.push_back(ans); } sort(anss.begin(), anss.end()); OUT(anss[0]);
感想
なんとかACできたのはいいですが、解説を見ても分からない数弱さはなんとかしたいですね。数式に弱い...
