SRM641D1Med ShufflingCardsDiv1
考察が重い
問題概要(原文)
$2N$ 枚のカードがあり， $1$ から $2N$ の番号がついている．以下の操作を行うことが何度でもできる．
- カードの山を前半と後半に分ける
- 分けた山の中で任意に並び替える
- リフルシャッフルをする
$(1,2,\ldots, 2N)$から最小何回の操作で $P$ にできるか？不可能ならば $-1$ を返せ．
考察
はじめから $P$ なら答えは自明に $0$
そうでなければ $1$ 回は操作が必要だと分かる． $1$ 回目のシャッフルで $1$ から $N$，$N+1$ から $2N$ を入れ替えることができるので，これらは区別しなくてもよいことがわかる．すると，この問題は以下のように言い換えられる．
$N$ 個の $0$ と $N$ 個の $1$ が並んだ数列がある．以下の操作を最小何回行えば $P$ にできるか？不可能ならば $-1$ を返せ．
- カードの山を前半と後半に分ける
- 分けた山の中で任意に並び替える
- リフルシャッフルをする
$P$ のうち(0-indexedで)偶数番目にある $0$ の数を $K$ とする．すると，山の前半に $0$ が $K$ 個ある状態から $1$ 回操作をすると， $P$ にできることがわかる．
前半にある $0$ の数を $a$ ，後半にある $0$ の数を $b$ とする．$1$ 回の操作後に，前半に残せる $0$ の数の最小値は $max(0,a-N/2)+max(0,b-(N+1)/2)$ ，最大値は $min(a,(N+1)/2)+min(b,N/2)$ である．
ソースコード
using System;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;
using Debug = System.Diagnostics.Debug;
using StringBuilder = System.Text.StringBuilder;
public class ShufflingCardsDiv1
{
public int shuffle(int[] P)
{
var n = P.Length;
for (int i = 0; i < n; i++)
P[i]--;
var cnt = 0;
{
var ok = true;
for (int i = 0; i < n; i++)
if (P[i] != i) ok = false;
if (ok) return 0;
for (int i = 0; i < n; i += 2)
if (P[i] < n / 2) cnt++;
if (cnt == n / 2) return 1;
}
//偶数番目にいきたい0の数
Debug.WriteLine(cnt);
Debug.WriteLine("");
n /= 2;
//0,1,2,...,N/2, N/2+1,...2Nを
//0,0,0,...,0,1,...1とする
//これからPを作りたい
//前半に0が何枚あるか？
var dp = Enumerate(n + 1, x => 1000000000);
var q = new Queue<int>();
q.Enqueue(n);
dp[n] = 0;
while (q.Any())
{
var a = q.Dequeue();
Debug.WriteLine(a);
var b = n - a;
var min = Math.Max(0, a - (n - (n + 1) / 2)) + Math.Max(0, b - (n + 1) / 2);
var max = Math.Min((n + 1) / 2, a) + Math.Min(b, n / 2);
for (int j = min; j <= max; j++)
{
if (dp[j] > dp[a] + 1)
{
dp[j] = dp[a] + 1;
q.Enqueue(j);
}
}
}
if (dp[cnt] >= 1000000000) return -1;
return dp[cnt] + 1;
}
static public T[] Enumerate<T>(int n, Func<int, T> f) { var a = new T[n]; for (int i = 0; i < n; ++i) a[i] = f(i); return a; }
}
コメント
- 問題の定式化が本質
- あとは単純な探索
