262位/11880人。Easy問は省略する。
Transform to Palindrome
n種類の文字で構成された、長さmの文字列sがある。ここで、Transform[x,y]は、文字xをyへ、または文字yをxへ変換できることを意味する。k個のTransformが与えられたとき、sを変換してなるべく長いPalindromic Subsequenceの長さを求めよ。
同じTransformグループの文字を、UnionFindを使ってすべて同じ文字に変換する。そして文字列の最長Palindromic Subsequenceを求めればよい。これはDPの有名問題。
Longest palindromic subsequence - PEGWiki
public static int GetAns(List<int[]> transforms, int[] s)
{
Transform(s, transforms);
return GetLPS(s);
}
public static void Transform(int[] s, List<int[]> transforms)
{
var unionFind = new UnionFind();
foreach (var t in transforms)
{
unionFind.Unite(t[0], t[1]);
}
for (int i = 0; i < s.Length; i++)
{
s[i] = (int)unionFind.RootValue(s[i]);
}
}
public static int GetLPS(int[] s)
{
var dp = new int[s.Length + 1, s.Length + 1];
for (int i = s.Length; i >= 0; i--)
{
for (int j = i; j < s.Length + 1; j++)
{
if (i == j) dp[i, j] = 0;
if (j - i == 1) dp[i, j] = 1;
if (j - i > 1 && s[i] != s[j - 1]) dp[i, j] = Math.Max(dp[i + 1, j], dp[i, j - 1]);
if (j - i > 1 && s[i] == s[j - 1]) dp[i, j] = 2 + dp[i + 1, j - 1];
}
}
return dp[0, s.Length];
}
(UnionFindの実装は省略)
Palindromic table
n*m座標のグリッドそれぞれに、0~9の数字が入っている。任意の四角形を取り出したとき、中にある数字を並び替えて回文を作りたい。面積が最大になるように四角形を選び出せ。回文は前ゼロを含んではならない。また、面積1の四角形はいずれも有効とする。
1 <= n, m <= 10^5
n * m <= 10^5
ある範囲で回文ができるかどうかは、
・すべての文字種が偶数個である
・または1つの文字種だけが奇数個である
で判断できる。文字の種類は10個しかないので、その偶奇を10ビットで管理する。
if (i > 0) hash_sum[i][j] = hash_sum[i - 1][j];
if (j > 0) hash_sum[i][j] ^= hash_sum[i][j - 1];
if (i > 0 && j > 0) hash_sum[i][j] ^= hash_sum[i - 1][j - 1];
hash_sum[i][j] ^= hashTable[table[i][j]];
こうすれば、hash_sum[i][j]は、座標(0,0)から(i,j)までの偶奇情報になる。すると任意の範囲での偶奇情報は、XORすることで簡単に求められるようになる。
次にyでループする。あるy範囲(d,u)に対して考えたとき、まずy方向のHash値(偶奇情報)をマージしてしまう。
for (var x = 0; x < m; x++)
hash_line[x] = hash_sum[u][x] ^ (d > 0 ? hash_sum[d - 1][x] : 0);
そうしたら、「あるHash値(偶奇情報)になる最後のx位置」を保管する。2^10パターンしかないので、辞書よりも配列を使うと早い。
var dict = new int[1 << 10 + 1];
for (int i = 0; i < 1 << 10 + 1; i++) dict[i] = -1;
for (var x = 0; x < m; x++) dict[hash_line[x]] = x;
最後にxの左位置でループする(l)。各lに対し「すべての文字が偶数個になる」または「1文字だけ奇数になる」パターンを列挙し、それぞれの最後のx位置rをdict[]から探し出す。見つかったらこの四角形(u, l, d, r)で回文を作ることができる。
for (var l = 0; l < m; l++)
{
candHashes[0] = l > 0 ? hash_line[l - 1] : 0;
for (int i = 0; i <= 9; i++)
candHashes[i + 1] = hashTable[i] ^ (l > 0 ? hash_line[l - 1] : 0);
foreach (var candHash in candHashes)
{
r = dict[candHash];
if (r == -1) continue;
var newArea = (u - d + 1) * (r - l + 1);
if (newArea <= maxArea) continue;
maxArea = newArea;
ret = new Tuple<int, int, int, int, int>(maxArea, d, l, u, r);
}
}
もう一つの条件「回文は前ゼロを含んではならない」は、四角形の面積に対し、ゼロが多すぎるか否かで判断できる。範囲内のゼロの数は、ゼロの累積和を作っておけば簡単に求めることができる。
以下は全コード。
public static Tuple<int, int, int, int, int> GetAns(int n, int m, List<List<int>> table)
{
var flipped = false;
if (n > m)
{
table = Flip(table);
var tmp = n;
n = m;
m = tmp;
flipped = true;
}
var hashTable = Enumerable.Range(0, 10).Select(v => 1 << v).ToArray();
var zero_num_sum = GetZeroNumSum(table);
var hash_sum = GetHashSum(table, hashTable);
var ret = new Tuple<int, int, int, int, int>(1, 0, 0, 0, 0);
var maxArea = 1;
var candHashes = new int[11];
var zero_sum_line = new int[m];
var hash_line = new int[m];
int r;
for (int d = 0; d < n; d++)
{
for (int u = d; u < n; u++)
{
for (var x = 0; x < m; x++)
zero_sum_line[x] = zero_num_sum[u][x] - (d > 0 ? zero_num_sum[d - 1][x] : 0);
for (var x = 0; x < m; x++)
hash_line[x] = hash_sum[u][x] ^ (d > 0 ? hash_sum[d - 1][x] : 0);
var dict = new int[1 << 10 + 1];
for (int i = 0; i < 1 << 10 + 1; i++) dict[i] = -1;
for (var x = 0; x < m; x++) dict[hash_line[x]] = x;
for (var l = 0; l < m; l++)
{
candHashes[0] = l > 0 ? hash_line[l - 1] : 0;
for (int i = 0; i <= 9; i++)
candHashes[i + 1] = hashTable[i] ^ (l > 0 ? hash_line[l - 1] : 0);
foreach (var candHash in candHashes)
{
r = dict[candHash];
if (r == -1) continue;
var newArea = (u - d + 1) * (r - l + 1);
if (newArea <= maxArea) continue;
var zeroNum = zero_sum_line[r] - (l > 0 ? zero_sum_line[l - 1] : 0);
if (newArea - zeroNum < 2) continue;
maxArea = newArea;
ret = new Tuple<int, int, int, int, int>(maxArea, d, l, u, r);
}
}
}
}
if (flipped) Flip(ret);
return ret;
}
public static List<List<int>> GetZeroNumSum(List<List<int>> table)
{
var ret = new List<List<int>>();
for (int i = 0; i < table.Count; i++)
{
var list = Enumerable.Range(0, table[0].Count).Select(v => 0).ToList();
ret.Add(list);
}
for (int i = 0; i < table.Count; i++)
{
for (int j = 0; j < table[0].Count; j++)
{
if (i > 0) ret[i][j] = ret[i - 1][j];
if (j > 0) ret[i][j] += ret[i][j - 1];
if (i > 0 && j > 0) ret[i][j] -= ret[i - 1][j - 1];
ret[i][j] += table[i][j] == 0 ? 1 : 0;
}
}
return ret;
}
public static List<List<int>> GetHashSum(List<List<int>> table, int[] hashTable)
{
var ret = new List<List<int>>();
for (int i = 0; i < table.Count; i++)
{
var list = Enumerable.Range(0, table[0].Count).Select(v => 0).ToList();
ret.Add(list);
}
for (int i = 0; i < table.Count; i++)
{
for (int j = 0; j < table[0].Count; j++)
{
if (i > 0) ret[i][j] = ret[i - 1][j];
if (j > 0) ret[i][j] ^= ret[i][j - 1];
if (i > 0 && j > 0) ret[i][j] ^= ret[i - 1][j - 1];
ret[i][j] ^= hashTable[table[i][j]];
}
}
return ret;
}
この問題が解けたのはうれしかった。あとは難易度Expertに手が出るようになれば…。
Bonnie and Clyde
ノード数nの無向グラフが与えられる。ノードu,v,wについて、u-wパスとv-wパスが存在するか答えよ。ただし、2つのパスは同じノードを共有できない。
1 <= n <= 10^5
1 <= m(エッジ数) <= min( n*(n-1)/2, 2*10^5 )
1 <= q(クエリ数) <= 10^5
ノードをVertex Biconnected Componentsに分解して、Block-Cut Treeを作ることで解くことができる。Block-Cut TreeはVertex Biconnected ComponentsおよびArticulation(元ノードのうち橋になっているもの)をノードにして作成された木。
基本的にはBlock-Cut Tree上でu-w-vのパス有無を判定するだけだが、wがArticulationの場合は追加判定が必要になる。
if (lca_uw == lca_vw)
{
if (bicc.Articulations.Contains(orgW) && (bicc.Tree.DP[0][w] == lca_uv || bicc.Tree.DP[0][lca_uv] == w)) return "YES";
}
if (lca_vw == lca_uv)
{
if (bicc.Articulations.Contains(orgW) && (bicc.Tree.DP[0][w] == lca_uw || bicc.Tree.DP[0][lca_uw] == w)) return "YES";
}
if (lca_uv == lca_uw)
{
if (bicc.Articulations.Contains(orgW) && (bicc.Tree.DP[0][w] == lca_vw || bicc.Tree.DP[0][lca_vw] == w)) return "YES";
}
このように、u-LCA(u,v)-vを考えたとき、wのすぐ隣がこのLCA(u,v)ならOKになる。
また、与えられる木は連結とは限らないので、その判定も追加で必要。
public static List<string> GetAns(int n, int m, List<int[]> edges, List<int[]> queries)
{
var bicc = new BICC_BlockCut(n);
foreach (var edge in edges) bicc.AddEdge(edge[0] - 1, edge[1] - 1);
bicc.Calc();
bicc.BuildTree();
return queries.Select(q => GetAns(n, bicc, q)).ToList();
}
public static string GetAns(int n, BICC_BlockCut bicc, int[] query)
{
var u = query[0] - 1;
var v = query[1] - 1;
var w = query[2] - 1;
var orgU = u;
var orgV = v;
var orgW = w;
if (u == v && u != w) return "NO";
if (u == w && v == w) return "YES";
if (bicc.InSameComp(u, v) && bicc.InSameComp(v, w) && bicc.InSameComp(u, w)) return "YES";
u = bicc.NodeToComponentId[u];
v = bicc.NodeToComponentId[v];
w = bicc.NodeToComponentId[w];
if (!bicc.Tree.InSameTree(u, v) || !bicc.Tree.InSameTree(v, w) || !bicc.Tree.InSameTree(u, w)) return "NO";
if (bicc.Tree.Level[v] < bicc.Tree.Level[u])
{
var tmp = u;
u = v;
v = tmp;
}
var lca_vw = bicc.Tree.Lca(v, w);
var lca_uv = bicc.Tree.Lca(u, v);
var lca_uw = bicc.Tree.Lca(u, w);
if (lca_uw == lca_vw)
{
if (bicc.Articulations.Contains(orgW) && (bicc.Tree.DP[0][w] == lca_uv || bicc.Tree.DP[0][lca_uv] == w)) return "YES";
}
if (lca_vw == lca_uv)
{
if (bicc.Articulations.Contains(orgW) && (bicc.Tree.DP[0][w] == lca_uw || bicc.Tree.DP[0][lca_uw] == w)) return "YES";
}
if (lca_uv == lca_uw)
{
if (bicc.Articulations.Contains(orgW) && (bicc.Tree.DP[0][w] == lca_vw || bicc.Tree.DP[0][lca_vw] == w)) return "YES";
}
return bicc.Tree.HasShortPath(u, v, w) ? "YES" : "NO";
}
public class BICC_BlockCut
{
List<List<int>> _graph;
int _n;
public HashSet<int> Articulations;
public List<List<Tuple<int, int>>> ComponentEdges;
public List<HashSet<int>> ComponentNodes;
public List<int> NodeToComponentId;
public Tree Tree;
public List<int> SizeOfComponents;
public BICC_BlockCut(int n)
{
_n = n;
_graph = Enumerable.Range(0, n).Select(v => new List<int>()).ToList();
}
public void AddEdge(int s, int t)
{
_graph[s].Add(t);
_graph[t].Add(s);
}
List<SortedSet<int>> _nodeToComponentIds;
int T;
int[] ord;
int[] low;
int[] depth;
Stack<Tuple<int, int>> stack;
public void Calc()
{
ComponentEdges = new List<List<Tuple<int, int>>>();
low = Enumerable.Range(0, _n).Select(v => -1).ToArray();
depth = Enumerable.Range(0, _n).Select(v => -1).ToArray();
ord = Enumerable.Range(0, _n).Select(v => -1).ToArray();
stack = new Stack<Tuple<int, int>>();
for (int i = 0; i < _n; i++)
{
if (ord[i] == -1)
{
T = 0;
Dfs(i);
}
}
_nodeToComponentIds = Enumerable.Range(0, _n).Select(v => new SortedSet<int>()).ToList();
ComponentNodes = new List<HashSet<int>>();
for (int cId = 0; cId < ComponentEdges.Count(); cId++)
{
var edges = ComponentEdges[cId];
var hash = new HashSet<int>();
foreach (var e in edges)
{
hash.Add(e.Item1);
hash.Add(e.Item2);
_nodeToComponentIds[e.Item1].Add(cId);
_nodeToComponentIds[e.Item2].Add(cId);
}
ComponentNodes.Add(hash);
}
}
void Dfs(int i)
{
low[i] = ord[i] = T++;
for (int j = 0; j < _graph[i].Count(); j++)
{
var to = _graph[i][j];
if (ord[to] == -1)
{
depth[to] = depth[i] + 1;
stack.Push(new Tuple<int, int>(i, to));
Dfs(to);
low[i] = Math.Min(low[i], low[to]);
if (ord[i] == 0 || low[to] >= ord[i])
{
var edges = new List<Tuple<int, int>>();
while (true)
{
if (IsEq(stack.Peek(), i, to)) break;
edges.Add(stack.Pop());
}
edges.Add(stack.Pop());
ComponentEdges.Add(edges);
}
}
else if(depth[to] < depth[i] - 1)
{
low[i] = Math.Min(low[i], ord[to]);
stack.Push(new Tuple<int, int>(i, to));
}
}
}
bool IsEq(Tuple<int, int> edge, int u, int v)
{
return (edge.Item1 == u && edge.Item2 == v) || (edge.Item1 == v && edge.Item2 == u);
}
public void BuildTree()
{
var tuple = GetTreeGraph();
Tree = new Tree(ComponentNodes.Count() + _n, tuple.Item1.Select(v => v.ToList()).ToList(), tuple.Item2);
}
Tuple<List<HashSet<int>>, HashSet<int>> GetTreeGraph()
{
Articulations = new HashSet<int>();
var C = ComponentNodes.Count();
SizeOfComponents = Enumerable.Range(0, C + _n).Select(v => 0).ToList();
var graph = Enumerable.Range(0, C + _n).Select(v => new HashSet<int>()).ToList();
NodeToComponentId = Enumerable.Range(0, C + _n).Select(v => -1).ToList();
var extra = Enumerable.Range(0, C + _n).Select(v => -1).ToList();
for (int i = 0; i < _nodeToComponentIds.Count(); i++)
{
var tmpv = _nodeToComponentIds[i];
if (_graph[i].Count() == 0)
{
NodeToComponentId[i] = C + i;
extra[C + i] = 0;
SizeOfComponents[C + i] = 1;
}
else if (tmpv.Count() == 1)
{
NodeToComponentId[i] = tmpv.First();
extra[tmpv.First()] = 0;
SizeOfComponents[tmpv.First()]++;
}
else
{
Articulations.Add(i);
NodeToComponentId[i] = C + i;
extra[C + i] = 0;
SizeOfComponents[C + i]++;
foreach (var j in tmpv)
{
extra[j] = 0;
SizeOfComponents[j]++;
graph[C + i].Add(j);
graph[j].Add(C + i);
}
}
}
var extraHash = new HashSet<int>();
for (int i = 0; i < extra.Count(); i++)
{
if (extra[i] == -1) extraHash.Add(i);
}
return new Tuple<List<HashSet<int>>, HashSet<int>>(graph, extraHash);
}
public bool InSameComp(int u, int v)
{
return _nodeToComponentIds[u].Intersect(_nodeToComponentIds[v]).Count() > 0;
}
}
public class Tree
{
public int[] Level;
int LOGN = 20;
public int[][] DP;
int _n;
List<List<int>> _graph;
HashSet<int> _ignoreNodes;
public Tree(int n)
{
Init(n);
_graph = Enumerable.Range(0, n).Select(v => new List<int>()).ToList();
_ignoreNodes = new HashSet<int>();
}
public Tree(int n, List<List<int>> graph, HashSet<int> ignoreNodes)
{
Init(n);
_graph = graph;
_ignoreNodes = ignoreNodes;
Calc();
}
void Init(int n)
{
_n = n;
Level = new int[n];
DP = Enumerable.Range(0, LOGN).Select(v => Enumerable.Range(0, n).Select(w => 0).ToArray()).ToArray();
}
public void AddEdge(int s, int t)
{
_graph[s].Add(t);
_graph[t].Add(s);
}
int[] arr;
int currComp;
int[] dep;
int[] vis;
int T;
public void Calc()
{
arr = new int[_n];
currComp = 0;
dep = new int[_n];
vis = new int[_n];
T = 0;
for (int i = 0; i < _n; i++)
{
if (vis[i] == 0 && !_ignoreNodes.Contains(i))
{
currComp++;
Dfs(i, i);
}
}
for (int i = 1; i < LOGN; i++)
{
for (int j = 0; j < _n; j++)
{
if (!_ignoreNodes.Contains(j))
{
DP[i][j] = DP[i - 1][DP[i - 1][j]];
}
}
}
}
void Dfs(int u, int p)
{
if (vis[u] != 0) return;
Level[u] = Level[p] + 1;
DP[0][u] = p;
arr[u] = ++T;
vis[u] = currComp;
foreach (var w in _graph[u])
if (w != p)
Dfs(w, u);
dep[u] = T++;
}
public bool InSameTree(int a, int b)
{
return vis[a] == vis[b];
}
public int Lca(int a, int b)
{
if (Level[a] > Level[b])
{
var tmp = a;
a = b;
b = tmp;
}
int d = Level[b] - Level[a];
for (int i = 0; i < LOGN; i++)
{
if (((1 << i) & d) != 0) b = DP[i][b];
}
if (a == b) return a;
for (int i = LOGN - 1; i >= 0; i--)
{
if (DP[i][a] != DP[i][b])
{
a = DP[i][a];
b = DP[i][b];
}
}
return DP[0][a];
}
public bool Anc(int p, int u)
{
return (arr[u] >= arr[p] && dep[u] <= dep[p]);
}
public bool HasShortPath(int u, int v, int w)
{
if (!InSameTree(u, v) || !InSameTree(v, w)) return false;
if (Level[u] > Level[v])
{
var tmp = v;
v = u;
u = tmp;
}
int LCA = Lca(u, v);
bool ok = false;
ok |= Anc(w, u);
ok |= Anc(w, v);
ok &= Anc(LCA, w);
return ok;
}
}
ずいぶんと解けそうで解けず苦しんだ。。。