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; }
}

コメント

  • 問題の定式化が本質
  • あとは単純な探索