SRM607D1Med CombinationLockDiv1

こういう系は苦手

問題概要(原文)

$0$ から $9$ の $10$ 段階のダイヤルロックが $N(1 \leq N \leq 2500)$ 個並んでいる. 今の並びを $P$ としてこれを $Q$ にしたい.できる操作は連続したダイヤルロックの現在の数をまとめて $1$ 加算, $-1$ 減算のみである.

最小の操作数を求めよ.

考察

$P$ を $Q$ にしたいので, $A_i = Q_i-P_i (\text{mod}\;10)$ というような数列 $A$ について考える. 出来る操作は

  • $[l,r]$ を選んで, $A_l$ から $A_r$ に $1$ 加算する(法を $10$ とする).
  • $[l,r]$ を選んで, $A_l$ から $A_r$ に $-1$ 加算する(法を $10$ とする).

のみである. ここで $B_0 = A_0, B_i = A_i-A_{i-1} (\text{mod}\;10)$ という数列 $B$ を考える. $B$ の全ての要素を $0$ にするのが目標である. 差分に対してできる操作は以下の $3$ 種類しかない.

  • $B_i = B_i+1$ とする
  • $B_i=B_i-1$ とする
  • $B_i=B_i+1,B_j=B_j-1(i \neq j)$ とする

$3$ つ目の操作をうまく使うと手数が最小になることがわかる. $0$ にする側, いくつかは $10$ にする側に割り振ると考えて全探索すればよい.

ソースコード

using System;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;
using Debug = System.Diagnostics.Debug;
using StringBuilder = System.Text.StringBuilder;
public class CombinationLockDiv1
{
    public int minimumMoves(string[] P, string[] Q)
    {
        var s = string.Concat(P);
        var t = string.Concat(Q);
        var n = s.Length;
        var ans = 1000000000;
        var a = new int[n];
        for (int i = 0; i < n; i++)
            a[i] = (t[i] - s[i] + 100) % 10;
        var b = new int[n];
        b[0] = a[0];
        for (int i = 1; i < n; i++)
            b[i] = (a[i] - a[i - 1] + 100) % 10;
        Array.Sort(b);
        for (int i = 0; i <= n; i++)
        {
            var u = 0;
            var v = 0;
            for (int j = 0; j < n; j++)
            {
                if (j < i) u += b[j];
                else v += 10 - b[j];
            }
            ans = Math.Min(ans, u + v - Math.Min(u, v));
        }
        return ans;
    }

}

コメント

  • 差分を取るという発想がなかった(これは典型テクなので思いつかないといけない)