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;
}
}
コメント
- 差分を取るという発想がなかった(これは典型テクなので思いつかないといけない)
