ABC252 C - Slot Strategy の解説

数弱で解説を見てもよく分からなかったのですが、なんとかACできたので考え方を残しておきます。

問題

atcoder.jp

自分の回答

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に固定してみます。では、「揃えるのに何秒かかるか」はどのように計算すれば良いのでしょうか。ここで以下のように考えました。

  1. 一番短い秒数で止められるところに0があるリールを止める
  2. ↑で止めた秒数から一番短い秒数で止められるところに0があるリールを止める
  3. 繰り返し

具体的に入力1の場合の例を見ていきましょう。

3
1937458062
8124690357
2385760149

ここで、0がそれぞれの行において何番目(indexなので0始まり)にあるかを見てみます。すると、

リール1: 7
リール2: 6
リール3: 6

となります。これを先程のステップに当てはめてみます。

  1. 一番短い秒数で止められるところに0があるリールを止める

現在は0秒目なので、0が6の位置にあるリールが最も短い秒数、6秒で止められます。2つありますがどっちを止めても変わりはありません。ここではリール2を止めてみます。

  1. ↑で止めた秒数から一番短い秒数で止められるところに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できたのはいいですが、解説を見ても分からない数弱さはなんとかしたいですね。数式に弱い...