SRM629D1Med CandyCollection
考察に手間取った
問題概要(原文)
$N$ 種類のガチャと $N$ 枚のカードがある．種類 $i$ のガチャには種類 $p,q (p \neq q)$ のカードがそれぞれ $a,b$ 枚入っている． ここで，どの種類のカードもちょうど $2$ 種類のガチャからしか手に入らないことが保証されている．
$N$ 種類のカード全てを $1$ 枚以上手に入れたい．何回ガチャを回せば十分か？
考察
$1$ 種類のガチャには $2$ 種類のカードしかない．つまり，種類 $i$ のガチャから $p,q$ に無向辺を張ると， 閉路が出来上がる．
閉路 $1$ つに着目する． 端の買い方を決め打ちする． 遷移は以下の $4$ 通り
- 両方のカードが当たるまで引く
- ここのガチャで当てないと，もう手に入らないカードが当たるまで引く
- 次のガチャでも引けるカードが当たるまで引く
- 買わない
これを適切に試して，全てのカードが買われているようにする最小値を求める．
これを全ての閉路について適切にやればよい． $O(N)$ でもできるが，$O(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 CandyCollection
{
public int solve(int[] t1, int[] num1, int[] t2, int[] num2)
{
var n = t1.Length;
var ans = 0;
var used = new bool[n];
for (int i = 0; i < n; i++)
{
if (used[i]) continue;
used[i] = true;
var dp = new int[2, 2];
for (int j = 0; j < 2; j++)
for (int k = 0; k < 2; k++)
dp[j, k] = 1000000000;
dp[0, 0] = 0;
dp[0, 1] = num1[i] + 1;
dp[1, 0] = num2[i] + 1;
dp[1, 1] = Math.Max(num1[i], num2[i]) + 1;
var c = t2[i];
var p = -1;
for (int j = 0; j < n; j++)
if (used[j]) continue;
else
{
if (t1[j] == c) { p = j; break; }
else if (t2[j] == c)
{
Swap(ref t1[j], ref t2[j]);
Swap(ref num1[j], ref num2[j]);
p = j; break;
}
}
for (; p != -1;)
{
used[p] = true;
var next = new int[2, 2];
for (int j = 0; j < 2; j++)
for (int k = 0; k < 2; k++)
next[j, k] = 1000000000;
for (int j = 0; j < 2; j++)
{
next[j, 0] = Math.Min(dp[j, 1], dp[j, 0] + num2[p] + 1);
next[j, 1] = Math.Min(dp[j, 1] + num1[p] + 1, dp[j, 0] + Math.Max(num1[p], num2[p]) + 1);
}
dp = next;
c = t2[p];
p = -1;
for (int j = 0; j < n; j++)
if (used[j]) continue;
else
{
if (t1[j] == c) { p = j; break; }
else if (t2[j] == c)
{
Swap(ref t1[j], ref t2[j]);
Swap(ref num1[j], ref num2[j]);
p = j; break;
}
}
}
ans += Math.Min(dp[0, 1], Math.Min(dp[1, 0], dp[1, 1]));
}
return ans;
}
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; }
static public void Swap<T>(ref T a, ref T b) { var tmp = a; a = b; b = tmp; }
}
コメント
- フローだと思って考察して最大カットに帰着させてしまった
