SRM620D1Med CandidatesSelection
解法にたどり着くまであと一歩が難しい．
問題概要(原文)
$N$ 人がいて， $M$ 個のスキルを持つ．それぞれのスキルごとに $26$ 段階のレベルがある．
$\{0,1,\ldots, N-1 \}$ をスキル $i$ でソートするという操作を何回でもできる．このとき， $j$ 番の人と $k$ 番の人において $(j<k$ とする $)$， スキルレベルが低い方が前に来る．スキルレベルが同じ場合は， $j$ が前に来る．というルールでソートする．
ある順列 $P$ になるようにすることは可能か？
考察
できる操作はソートのみ．最後の手から考えることにする．
すると，スキルレベルでいくつかのブロックに分けることができる．このブロック間はあとでこれ以前の操作で影響を受けることがなくなる．つまり最終的，全てのブロック内で単調増加列になっていればよい．
再帰的に集合を分割することにする． 使える手が複数あったときにどれを使ってもよい(より細切れにできるものがあってもどうせあとで使われるから)．
分割される回数は高々 $N$ 回． 適当にやっても $O(N^2M)$ ぐらいで済む．
ソースコード
using System;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;
using Debug = System.Diagnostics.Debug;
using StringBuilder = System.Text.StringBuilder;
public class CandidatesSelection
{
public string possible(string[] score, int[] Q)
{
var n = score.Length;
var m = score[0].Length;
var ss = Enumerate(n, x => new int[m]);
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
ss[i][j] = score[i][j] - 'A';
return f(ss, Q) ? "Possible" : "Impossible";
}
bool f(int[][] score, int[] Q)
{
var n = score.Length;
var m = score[0].Length;
Func<List<List<int>>, bool> dfs = null;
dfs = qs =>
{
//Debug.WriteLine(string.Join("|", qs.Select(x => x.AsJoinedString())));
//check
{
var ok = true;
foreach (var p in qs)
{
for (int i = 1; i < p.Count; i++)
ok &= p[i] > p[i - 1];
}
if (ok) return true;
}
for (int id = 0; id < m; id++)
{
var ok = true;
var good = false;
foreach (var p in qs)
{
for (int i = 1; i < p.Count; i++)
{
ok &= score[p[i]][id] >= score[p[i - 1]][id];
good |= score[p[i]][id] > score[p[i - 1]][id];
}
}
if (!ok) continue;
if (!good) continue;
var nqs = new List<List<int>>();
foreach (var p in qs)
{
var nl = new List<int>() { p[0] };
var v = score[p[0]][id];
for (int i = 1; i < p.Count; i++)
{
if (v == score[p[i]][id]) nl.Add(p[i]);
else
{
if (nl.Count > 0)
nqs.Add(nl);
nl = new List<int>() { p[i] };
v = score[p[i]][id];
}
}
if (nl.Count > 0) nqs.Add(nl);
}
return dfs(nqs);
}
return false;
};
return dfs(new List<List<int>>() { Q.ToList() });
}
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; }
}
コメント
- 後ろからやる，というのは典型的な発想で気づけた
- 集合を再帰的に分割してよくvalidなものであればどれを使ってもよいというのに気づけなかった
