HackerRank Week of Code 33 参加日記
262位/11880人。Easy問は省略する。
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); } // Change letters in the same group to the same letter 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]); } } // Longest Palindromic Subsequence: O(N^2) 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の実装は省略)
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; // 1種類だけ奇数個 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) { // nで二重ループするので、n>mのときは反転させる。Flip()の実装は省略 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); // 返り値。面積, r1, c1, r2, c2 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); // あるHash値(偶奇情報)になる最後のx位置 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; // 1種類だけ奇数個 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に手が出るようになれば…。
ノード数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; // same start pos but w is different if (u == v && u != w) return "NO"; // already goaled if (u == w && v == w) return "YES"; // same component 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]; // should be in the same tree 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; // results public HashSet<int> Articulations; public List<List<Tuple<int, int>>> ComponentEdges; public List<HashSet<int>> ComponentNodes; public List<int> NodeToComponentId; // tree of BICC 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); } // need to run Calc() first 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) // isolated { NodeToComponentId[i] = C + i; extra[C + i] = 0; SizeOfComponents[C + i] = 1; } else if (tmpv.Count() == 1) // in single comp { NodeToComponentId[i] = tmpv.First(); extra[tmpv.First()] = 0; SizeOfComponents[tmpv.First()]++; } else // articulation vertex { 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; } } // basic tree with Lca() and Asc() 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); } // working for calc() 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]; } // p is Anc of u public bool Anc(int p, int u) { return (arr[u] >= arr[p] && dep[u] <= dep[p]); } // has short path: u - w - v 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; } }
ずいぶんと解けそうで解けず苦しんだ。。。
Codechef May Challenge 2017 参加日記
CodechefのLong Challengeに初参加した。221位/7492人
Chefの一日は必ず、料理・食事・睡眠の順番である。1日の行動ログが料理'C'、食事'E'、睡眠'S'の形式で与えられたとき、これが有効かどうかを答えよ。
1 <= N(ログの長さ)<= 10^5
C・E・Sの順番になっているかチェックすればよい。ただし、Cが無いなど抜けている場合もOKになる。
public static string GetAns(string s) { var vals = "CES"; var idx = 0; for (int i = 0; i < vals.Length; i++) { while (idx < s.Length && s[idx] == vals[i]) idx++; } return idx == s.Length ? "yes" : "no"; }
大学のコースがN個あり、難易度順に昇順で並んでる。各コースは難易度のより低いコースを履修要件としてもつことがある。配列a[i]は、コースiが必要とする履修要件コースの数である。このとき、他コースの履修要件となっていないコースの数を最大にしたい。この数を答えよ。
1 <= N <= 10^5
0 <= a[i] <= i
各コースごと、なるべく難易度の低いコースを必要数だけ要件に割り当てればよい。
public static int GetAns(int n, int[] a) { var ret = a.Length; for (int i = 1; i < a.Length; i++) { ret = Math.Min(ret, a.Length - a[i]); } return ret; }
Median of adjacent maximum numbers
長さ2N(Nは奇数)の整数列Aが与えられる。配列Bを、B[i] = Max(A[2 * i - 1], A[2 * i]) としたとき、Bの中央値が最大になるようにAを並び替えよ。その中央値とAを解答すること。
1 <= N <= 50000
1 <= A[i] <= 2*N
Aをソートし、上位1/4をBに割り当てる。
public static Tuple<int, int[]> GetAns(int n, int[] a) { var ret = a; var sorted = a.OrderBy(v => v).ToArray(); for (int i = 0; i < a.Length / 2; i++) ret[i * 2] = sorted[i]; for (int i = 0; i < a.Length / 2; i++) ret[i * 2 + 1] = sorted[i + a.Length / 2]; return new Tuple<int, int[]>(ret[a.Length / 2], ret); }
長さNのBinary配列Aがあるとき、次の2種類のクエリに対応せよ。
・Aを右に1シフト
・連続したK要素内における1の数の最大値を出力
1 <= N, K, P <= 10^5 (Pはクエリ数)
配列sumsを
sums[i] = A[i:i+K]の1の数
とすると、シフトが無いと仮定したとき解は
Max(sums[k]) k: 0~N-k
になる。これは範囲内の最大値を求めているだけなので、セグメント木を使えばO(logN)で求められる。
そして、現在のA配列の始まる位置を管理していけば(Aが右シフトするたび-1を加算)、実際に求めるsums上の範囲が計算できる。
public static List<int> GetAns(int n, int k, int p, int[] a, string req) { var sums = new int[a.Length]; //sums from current to current + k var wk = a.Concat(a).ToArray(); k = Math.Min(k, a.Length); var sum = 0; for (int i = 0; i < wk.Length && i < a.Length + k; i++) { if (i >= k) { sums[i - k] = sum; } sum += wk[i]; if (i >= k) { sum -= wk[i - k]; } } var ret = new List<int>(); var seg = new SegTree_max(); seg.Init(sums.Length); for (int i = 0; i < sums.Length; i++) seg.Update(i, sums[i]); var limit = a.Length; foreach (var r in req) { if (r == '!') { limit--; if (limit == 0) limit = a.Length; } else { var maxVal = 0; // max from [0, limit - k] // for (int i = 0; i <= limit - k ; i++) maxVal = Math.Max(maxVal, sums[i]); maxVal = Math.Max(maxVal, seg.Query(0, limit - k + 1)); // max from [limit, Math.Min(a.Length - 1, a.Length + limit - k)] // for (int i = limit; i <= Math.Min(a.Length - 1, a.Length + limit - k); i++) maxVal = Math.Max(maxVal, sums[i]); maxVal = Math.Max(maxVal, seg.Query(limit, Math.Min(a.Length, a.Length + limit - k + 1))); ret.Add(maxVal); } } return ret; } public class SegTree_max { const int MAX_N = 1 << 17; int _n; int[] _dat = new int[2 * MAX_N - 1]; public void Init(int n) { _n = 1; while (_n < n) _n *= 2; for (int i = 0; i < 2 * _n - 1; i++) _dat[i] = 0; } public void Update(int k, int a) { k += _n - 1; _dat[k] = a; while (k > 0) { k = (k - 1) / 2; _dat[k] = Math.Max(_dat[k * 2 + 1], _dat[k * 2 + 2]); } } public int Query(int a, int b) { return Query(a, b, 0, 0, _n); } int Query(int a, int b, int k, int l, int r) { if (r <= a || b <= l) return 0; if (a <= l && r <= b) return _dat[k]; else { var vl = Query(a, b, k * 2 + 1, l, (l + r) / 2); var vr = Query(a, b, k * 2 + 2, (l + r) / 2, r); return Math.Max(vl, vr); } } }
N個のウェブサイトについて、それぞれファイヤーウォールでブロックするべきか否かの情報が与えられる。これを元にファイヤーウォールにフィルタをいくつか設定したい。最小のフィルタ長の合計を求めよ。なおウェブサイトは、Prefixがフィルタのいずれかと一致した場合にブロックされる。不可能な場合は-1を返すこと。
サイト名は英小文字のみ
1 <= N <= 2*10^5
サイト長の合計は2*10^5以下
同じサイト名は存在しない
Trie木で管理すればよい。それぞれのノードに、フィルタ対象サイトの一部かどうか・フィルタ対象外の子があるか・フィルタ対象サイトの最終文字になってるか、などの情報を持つ。再帰でDFSを実装すれば楽だが、StackOverflowが怖かったのでBFSにした。
*GetAns()に冗長なチェックがたくさんあるが、問題文だけだと省いてよいか曖昧だった
public static List<string> GetAns(List<string> toFilter, List<string> notFilter) { if (toFilter.Contains("")) { if (notFilter.Count() > 0) return null; return new List<string> { "" }; } if (notFilter.Contains("") && toFilter.Count() > 0) return null; // no two sites have same name var concat = toFilter.Concat(notFilter); if (concat.Count() != concat.Distinct().Count()) return null; // length should not exceed if (concat.Sum(c => c.Length) > 200000) return null; var trie = new Trie(); foreach (var f in toFilter) trie.AddString(f, true); foreach (var n in notFilter) trie.AddString(n, false); var ret = trie.GetAns(); if (ret != null) ret.Sort(); if (ret != null && ret.Sum(r => r.Length) > 200000) return null; return ret; } public class Trie { public class Node { public Node Parent; public char CharToParent; // 'a' - 'z' public Node[] Children; public bool IsFilter; public bool HasNofilterChildren; public bool IsLastCharOfFilter; public Node(bool isFilter) { Children = new Node[26]; IsFilter = isFilter; } public Node Add(char c, bool isFilter, bool isLastCharOfFilter) { if (Children[c - 'a'] == null) Children[c - 'a'] = new Node(isFilter); Children[c - 'a'].IsFilter |= isFilter; Children[c - 'a'].HasNofilterChildren |= !isFilter; Children[c - 'a'].IsLastCharOfFilter |= isLastCharOfFilter; Children[c - 'a'].Parent = this; Children[c - 'a'].CharToParent = c; return Children[c - 'a']; } public string GetString() { var ret = new StringBuilder(); var cur = this; while (cur.Parent != null) { ret.Append(cur.CharToParent); cur = cur.Parent; } return new string(ret.ToString().Reverse().ToArray()); } } Node _root = new Node(false); public void AddString(string str, bool isFilter) { var node = _root; for (var idx = 0; idx < str.Length; idx++) { node = node.Add(str[idx], isFilter, isFilter && idx == str.Length - 1); } } public List<string> GetAns() { var ret = new List<string>(); var stack = new Stack<Node>(); stack.Push(_root); while (stack.Count() > 0) { var node = stack.Pop(); if (node.IsFilter && !node.HasNofilterChildren && node != _root) { ret.Add(node.GetString()); continue; } if (node.IsFilter && node.Children.All(c => c == null ? true : !c.IsFilter)) { return null; } if (node.IsLastCharOfFilter && node.Children.Any(c => c == null ? false : c.HasNofilterChildren)) { return null; } for (int i = 0; i < 26; i++) { if (node.Children[i] != null) { stack.Push(node.Children[i]); } } } return ret; } }
要素数Nの整数列Aから、積がKを超えないサブシーケンスの組み合わせ数を答えよ。
1 <= N <= 30
1 <= K, A[i] <= 10^18
半分全列挙。Aの上半分とtop、下半分をbottomとする。まずbottomの全組み合わせについて積を求め、bottomValues[]に保管する。このときKを超える分はカウントしておく。次にtopの全組み合わせについて積を求め、BottomValuesから閾値を超える分(掛けるとKを超える値)の個数をカウントする(LowerBound()を使えばよい)。そして全組み合わせ数からカウント分を引けば答えとなる。
public static long GetAns(long k, long[] a) { if (a.Length == 1) return a[0] <= k ? 1 : 0; var top = a.Take(a.Length / 2).ToArray(); var bottom = a.Skip(a.Length / 2).ToArray(); var bottomValues = new List<long>(); for (int mask = 1; mask < 1 << bottom.Length; mask++) { long cur = 1; for (int i = 0; i < a.Length; i++) { if (((mask >> i) & 1) == 1) cur = Mux(cur, bottom[i]); if (cur > k) break; } bottomValues.Add(cur); } bottomValues.Sort(); long ret = 0; ret += (bottomValues.Count() - LowerBound(bottomValues, k + 1)); for (int mask = 1; mask < 1 << top.Length; mask++) { long cur = 1; for (int i = 0; i < a.Length; i++) { if (((mask >> i) & 1) == 1) cur = Mux(cur, top[i]); if (cur > k) break; } if (cur > k) { ret++; ret += bottomValues.Count(); } else { long thres = k % cur == 0 ? k / cur + 1 : (long)Math.Ceiling((double)k / (double)cur); ret += (bottomValues.Count() - LowerBound(bottomValues, thres)); } } return ((1 << a.Length) - 1) - ret; } static long Mux(long v1, long v2) { try { return checked(v1 * v2); } catch { return long.MaxValue; } } static int LowerBound(List<long> ar, long val) { var lb = -1; var ub = ar.Count(); while (ub - lb > 1) { var mid = (lb + ub) / 2; if (ar[mid] >= val) ub = mid; else lb = mid; } return ub; }
根をRとするノード数Nのツリーを考える。各ノードはそれぞれIDと暗号キーを持っている。このとき、次の2つのタイプのクエリがQ個与えられたときの結果を答えよ。
0 v u k:暗号キーkをもつノードuをノードvにつなげて追加する
1 v k:値aとbを出力する。aはノードvからRまでのパス上に存在するノードのうちでXOR(a, k)が最小になるもので、bはXOR(a, k)が最大になるもの
1 <= N <= 100,000
1 <= Q <= 200,000
1 <= R, u[i], v[i], key, k[i] <= 2^31 - 1
すべてのIDは一意
ノードuをノードvに追加するとき、ノードvからRまでのパスがすでに存在する。
※実際の問題では、標準入出力のやり取りにややこしいルールがあったが、省略する。
「ノードuをノードvに追加するとき、ノードvからRまでのパスがすでに存在する」ので、ルートRからあるノードまでのパスは、一度作成されると変わることが無い。この固定されたパス上の値をk[]とすると
・XOR(k[i], Key)が最大(最小)になるKeyを探せ
という部分問題になり、これは0と1で作るTrie木を作っておけば効率的に求めることができる。
あとは元のツリーを平方分割し、ある深さごとのノードに範囲内を管理するTrie木を作成しておけば良い。
(下のコードは深さ11000ごとに無条件でTrie木を作成してるが、遅延評価にすればもっと効率が良いはず)
static void Main(string[] args) { var s = Console.ReadLine().Split().Select(v => Int32.Parse(v)).ToArray(); var n = s[0]; var q = s[1]; s = Console.ReadLine().Split().Select(v => Int32.Parse(v)).ToArray(); var r = s[0]; var key = s[1]; var graph = new Graph(); graph.AddNode(r, key, -1); for (int i = 0; i < n - 1; i++) { s = Console.ReadLine().Split().Select(val => Int32.Parse(val)).ToArray(); var u = s[0]; var v = s[1]; var k = s[2]; graph.AddNode(u, k, v); } var last_ans = 0; for (int i = 0; i < q; i++) { s = Console.ReadLine().Split().Select(val => Int32.Parse(val)).ToArray(); var t = s[0] ^ last_ans; if (t == 0) { var v = s[1] ^ last_ans; var u = s[2] ^ last_ans; var k = s[3] ^ last_ans; graph.AddNode(u, k, v); } else { var v = s[1] ^ last_ans; var k = s[2] ^ last_ans; var ans = graph.GetAns(v, k); var min_ans = ans.Item1; var max_ans = ans.Item2; Console.WriteLine(min_ans + " " + max_ans); last_ans = min_ans ^ max_ans; } } } public class Graph { public static int TRIE_THRES = 11000; Node _rootNode; Dictionary<int, Node> _nodeDict = new Dictionary<int, Node>(); class Node { public int Key; public Node Parent; public int Depth; public Trie Trie; public Node ParentTrieNode; public Node(int key, Node parent, int depth) { Key = key; Parent = parent; Depth = depth; if (depth != 0 && (depth % Graph.TRIE_THRES) == 0) { Trie = GetTrie(); } } Trie GetTrie() { var ret = new Trie(); var current = this; while (current != null && current.Trie == null) { ret.AddNode(current.Key); current = current.Parent; } this.ParentTrieNode = current; return ret; } public Tuple<int, int> GetAns(int key) { var minVal = Int32.MaxValue; var maxVal = -1; var current = this; while (current != null) { if (current.Trie == null) { minVal = Math.Min(minVal, current.Key ^ key); maxVal = Math.Max(maxVal, current.Key ^ key); current = current.Parent; } else { minVal = Math.Min(minVal, current.Trie.GetMin(key)); maxVal = Math.Max(maxVal, current.Trie.GetMax(key)); current = current.ParentTrieNode; } } return new Tuple<int, int>(minVal, maxVal); } } public void AddNode(int id, int key, int parentId) { if (parentId == -1) { _rootNode = new Node(key, null, 0); _nodeDict.Add(id, _rootNode); } else { var parent = _nodeDict[parentId]; var node = new Node(key, parent, parent.Depth + 1); _nodeDict.Add(id, node); } } public Tuple<int, int> GetAns(int id, int key) { return _nodeDict[id].GetAns(key); } } public class Trie { Node _rootNode = new Node(null); class Node { public int Key; // only last node has it public Node Parent; public Node ZeroNode; public Node OneNode; public Node(Node parent) { Parent = parent; } public Node AddNode(int val) { if (val == 0) { if (ZeroNode == null) ZeroNode = new Node(this); return ZeroNode; } else { if (OneNode == null) OneNode = new Node(this); return OneNode; } } } public void AddNode(int key) { var currentTrieNode = _rootNode; for (int i = 30; i >= 0; i--) { currentTrieNode = currentTrieNode.AddNode((key >> i) & 1); } currentTrieNode.Key = key; } public int GetMin(int key) { return GetMinMax(true, key); } public int GetMax(int key) { return GetMinMax(false, key); } int GetMinMax(bool isMin, int key) { var curNode = _rootNode; for (int i = 30; i >= 0; i--) { var val = (key >> i) & 1; if (!isMin) { // max if (val == 1 && curNode.ZeroNode != null) { curNode = curNode.ZeroNode; } else if (val == 0 && curNode.OneNode != null) { curNode = curNode.OneNode; } else if (curNode.ZeroNode != null) { curNode = curNode.ZeroNode; } else { curNode = curNode.OneNode; } } else { // min if (val == 1 && curNode.OneNode != null) { curNode = curNode.OneNode; } else if (val == 0 && curNode.ZeroNode != null) { curNode = curNode.ZeroNode; } else if (curNode.OneNode != null) { curNode = curNode.OneNode; } else { curNode = curNode.ZeroNode; } } } return curNode.Key ^ key; } }
長さNのサンドイッチがある。これを長さ1~Kのいくつかのサンドイッチに切る方法はいくつあるか。ただし、サンドイッチの数はなるべく少なくしたい。サンドイッチの数と、切る方法の数(MでModをとること)を答えよ。
1 <= N <= 10^18
1 <= K <= 10^18
2 <= M <= 10^6
詳しくはここにあるが、nCr Mod xの問題に帰結することができる。
May Long Contest Editorial – codedecode0111 – Medium
ただし、xは素数とは限らないのがこの問いの難しいところ。よくわからないので保留(放置)・・・。
http://m00nlight.github.io/algorithm/2015/04/11/hackerrank-ncr
http://hamayanhamayan.hatenablog.jp/entry/2017/05/26/123020
Sea Battleという以下のゲームをプレーするAIを作成せよ。サーバー側のAIが対戦相手となる。
・敵、味方それぞれに10x10のボードがある
・駒の種類と数は、サイズ1x4のサブマリン1個、サイズ1x3のデストロイヤー2個、サイズ1x2のクルーザー3個、サイズ1x2のバトルシップ4個
・駒の配置は任意に作成できる。ただし、駒どおしは隣り合ってはならない(斜めも含む)
・ターン制のゲーム
・相手ボードは見えない
・相手のボードの好きなセルを爆撃できる。このとき、当たらなかった・当たった・当たって撃墜した、の情報が知らされる
・当たった場合は連続で爆撃できる
・船のあるセルすべてに当たれば撃墜
・先にすべての船を撃墜したほうが勝ち
・先手はプレーヤー
サーバーAIはランダムに空白セルを爆撃する。このとき、当たったら上下左右いずれかの隣を続けて爆撃する。また、空白セルでも船が無いと分かっているセルは無視する(すでに爆撃をトライした、残りの船がサイズ的に収まらない、撃墜した船に隣り合っている)。
サーバーAIとほぼ同じだが、追加で
・初期配置はなるべく隅に寄せる
・なるべく連続する空白セルの中央を打つ
・当たった後の追撃は、盤の中央に近いもの、また連続する空白セルがあるものを優先
の処理を入れた。
これでだいたい平均的なスコアだった。上位者はもっと細かくセルごとに船の存在確率を計算しているようだった。
※実装は省略
HackerRank Week of Code 32 参加日記
396位/8447人の不本意な結果。レートも少し落ちた。
以下、Easy問題は省略する。
次の式が与えられる。
円周上にn個の点(0~n-1)があったとき、点iから距離R[i]までジャンプすることができる。たとえばR[i]が2であれば、{i-1, i-1, i, i+1, i+2}へジャンプできる。点sから点tまでの最少ジャンプ数を答えよ。不可能な場合は-1を出力すること。
1 <= n <= 10^7
0 <= s, t <= n
1 <= p <= n
0 <= R[0], g, seed < p
現在地から到達できる最小点と最大点を保持してイテレーションしていけばよい。セグメント木で効率よく求められそうだが、nが小さいので愚直にループして間に合う。実装では面倒なエッジ処理を避けるため、最初にR[]を3つつなげ直線とみなして解いた。
public static int GetAns(int n, int s, int t, int r_0, int g, int seed, int p) { var r = GetR(r_0, n, g, seed, p); return GetAns(n, s, t, r); } public static int[] GetR(int r_0, int n, int g, int seed, int p) { var ret = new int[n]; ret[0] = r_0; for (int i = 1; i < n; i++) { ret[i] = (ret[i - 1] * g + seed) % p; } return ret; } public static int GetAns(int n, int s, int t, int[] r) { var newR = new int[r.Length * 3]; for (int i = 0; i < r.Length; i++) { newR[i] = newR[i + n] = newR[i + 2 * n] = r[i]; } var ts = new List<int>{ t, t + n, t + 2 * n }; var left = s + n; var right = s + n; var oldLeft = -1; var oldRight = -1; var ret = 0; while (true) { if (left < 0 || right >= newR.Length) break; //fail safe foreach (var tc in ts) { if (left <= tc && tc <= right) return ret; } var newLeft = left; var newRight = right; var cur = left; while (cur <= right) { if (oldLeft != -1 && cur == oldLeft) cur = oldRight + 1; newLeft = Math.Min(newLeft, cur - newR[cur]); newRight = Math.Max(newRight, cur + newR[cur]); cur++; } if (newLeft == left && newRight == right) break; //no change -> no answer oldLeft = left; oldRight = right; left = newLeft; right = newRight; ret++; } return -1; }
a,b,cからなる長さnの文字列sがある。次を満たす(i,j,k)の組み合わせ数を答えよ。
- s[i] = "a", s[j] = "b", s[k] = "c"
- (j + 1)^2 = (i + 1)(k + 1)
1 <= n <= 5 x 10^5
i*kが平方数のとき、iの素因数のうちべき乗数が奇数のものと、とkの素因数のうちべき乗数が奇数のものが一致する。たとえば
i = 3^2 * 5^1 * 7*2
k = 5^3 * 11*2
とすると、べき乗数が奇数になっている素因数はi、kともに5で一致しているため、i*kは平方数になる。
これを利用し、i、kすべてについてこの情報(べき乗数が奇数の素因数組み合わせ)が同じものどおしで、i*kがj*jの集合に存在するかチェックすればよい。情報の一致不一致はHash化して判断する。また、素因数分解はエラトステネスの篩の応用で高速に求められる。
// s[i] = 'a', s[j] = 'b', s[k] = 'c' // (j + 1) ^ 2 = (i + 1)(k + 1) public static long GetAns(string s) { var Is = new List<int>(); var J_pows = new HashSet<long>(); var Ks = new List<int>(); for (int i = 0; i < s.Length; i++) { if (s[i] == 'a') Is.Add(i + 1); if (s[i] == 'b') J_pows.Add((long)(i + 1) * (i + 1)); if (s[i] == 'c') Ks.Add(i + 1); } // sieve (2-s.Length + 1) var p = new int[s.Length + 2]; for (int i = 2; i < p.Length; i++) { if (p[i] != 0) continue; for (int j = i; j < p.Length; j += i) p[j] = i; } // hash list var rnd = new Random(); var hashList = new long[s.Length + 2]; for (int i = 1; i < hashList.Length; i++) hashList[i] = ((hashList[i - 1] * 37L + 123847L) << 31) + rnd.Next(); // prime hash => i/j values var i_hashes = GetHashes(Is, p, hashList); var k_hashes = GetHashes(Ks, p, hashList); var ret = 0L; foreach (var hash in i_hashes.Keys) { foreach (var i in i_hashes[hash]) { if (!k_hashes.ContainsKey(hash)) continue; foreach(var k in k_hashes[hash]) { if (J_pows.Contains((long)i * k)) ret++; } } } return ret; } static Dictionary<long, List<int>> GetHashes(List<int> values, int[] primes, long[] hashes) { var ret = new Dictionary<long, List<int>>(); foreach (var v in values) { var hash = GetHash(v, primes, hashes); if (!ret.ContainsKey(hash)) ret.Add(hash, new List<int>()); ret[hash].Add(v); } return ret; } static long GetHash(int value, int[] primes, long[] hashes) { if (value == 1) return 0; var curIdx = value; var ret = 0L; do { ret ^= hashes[primes[curIdx]]; curIdx /= primes[curIdx]; } while (curIdx > 1); return ret; }
n種類の色があり、色iのボールがA[i]個ある。さらにm個の箱があり、箱jにはC[j]個のボールが入る。
- 箱には、同色のボールは2個以上は入らない
- 色iのボールを箱jに入れると、B[i][j]のキャンディーがもらえる
- 箱にC[j]個より多くのボールを入れると、ペナルティとして超過分^2のキャンディを払う
のとき、なるべく多くのキャンディーを稼げ。
1 <= n, m <= 100
1 <= A[i] <= 100
0 <= C[i] <= 100
0 <= B[i][j] <= 10^3
次のような最小費用流の問題に還元できる(Uは大きな値)。
最小費用はたとえば
U - ボーナス[0]
U - ボーナス[1] + ペナルティ
U
U - ボーナス[3]
のような合計値になる(色2は箱に入れられていない)。最終的に求めたいのはボーナスとペナルティの合計だから、Sum(A)*Uからこの値を引いたものが解答になる。
public static int GetAns(int n, int m, int[] a, int[] c, int[][] b) { var total = a.Sum(); var graph = new MinCostFlow(n + m + 2 + 1); var s = n + m; var t = s + 1; var U = 3000; // colors for (int col = 0; col < n; col++) { graph.AddEdge(s, col, a[col], 0); graph.AddEdge(col, t, a[col], U); } // boxes for (int box = 0; box < m; box++) { var boxNode = box + n; // ordinal graph.AddEdge(boxNode, t, c[box], 0); // additional for (int j = 1; j <= 30; j++) { graph.AddEdge(boxNode, t, 1, 2 * j - 1); } } for (int col = 0; col < n; col++) { for (int box = 0; box < m; box++) { var boxNode = box + n; graph.AddEdge(col, boxNode, 1, U - b[col][box]); } } var flow = U * total - graph.GetMinCostFlow(s, t, total); return flow; } public class MinCostFlow { const int INF = 1 << 30; class Edge { public int v, r; public int c, w; public Edge(int v, int c, int w, int r) { this.v = v; this.c = c; this.w = w; this.r = r; } } List<List<Edge>> _graph; public MinCostFlow(int n) { _graph = new List<List<Edge>>(); for (int i = 0; i < n; i++) _graph.Add(new List<Edge>()); } public void AddEdge(int u, int v, int c, int w) { int x = _graph[u].Count(); int y = _graph[v].Count(); _graph[u].Add(new Edge(v, c, w, y)); _graph[v].Add(new Edge(u, 0, -w, x)); } List<T> GetList<T>(int size) { var ret = new List<T>(); for (int i = 0; i < size; i++) ret.Add(default(T)); return ret; } public int GetMinCostFlow(int s, int t, int f) { int n = _graph.Count(); int ret = 0; var h = GetList<int>(n); var dist = GetList<int>(n); var cap = GetList<int>(n); var use = GetList<int>(n); while (f > 0) { var q = new PriorityQueue<ComparablePair<int, int>>(1); for (int i = 0; i < dist.Count(); i++) dist[i] = INF; dist[s] = 0; cap[s] = f; q.Push(new ComparablePair<int, int>(0, s)); while (q.Count() != 0) { var d = -q.Peek().Item1; var u = q.Peek().Item2; q.Pop(); if (dist[u] != d) { continue; } foreach (var e in _graph[u]) { if (e.c > 0 && dist[e.v] > dist[u] + e.w + h[u] - h[e.v]) { dist[e.v] = dist[u] + e.w + h[u] - h[e.v]; q.Push(new ComparablePair<int, int>(-dist[e.v], e.v)); use[e.v] = e.r; cap[e.v] = Math.Min(cap[u], e.c); } } } if (dist[t] == INF) { return -1; } int v = t; while (v != s) { int u = _graph[v][use[v]].v; int x = _graph[v][use[v]].r; int y = use[v]; _graph[u][x].c -= cap[t]; _graph[v][y].c += cap[t]; ret += cap[t] * _graph[u][x].w; v = u; } for (int i = 0; i < n; i++) { h[i] += dist[i]; } f -= cap[t]; } return ret; } }
MinCostFlowは蟻本より。C#だとTLEぎりぎりになるようだ。なお本番ではMinCostの算出にPrimal-Dualを使っていたのと、二分探索でFlowを固定して最小費用を複数回もとめたので多くのケースでTLEになっていた。
HackerRank Week of Code 30 参加日記
289位/10554人でレートほぼ変化なし。以下、難易度EasyとMediumのものは省略する。
斜面上にn本のポールがあり、それぞれ高度x[i]と重さw[i]が与えられる(高度はユニーク)。これをk本のスタックにまとめたい。
・スタック位置はもともとポールがあった場所のみ有効
・ポールは下にのみ移動できる
・移動には、(ポールの重さx高度差)のコストがかかる
このときの最小コストを求めよ。
1 <= k < n <= 5000
1 <= w[i], x[i] <= 10^6
ポールは高度順(昇順)で与えられる
以下、ポールの順序を逆転して考える(0が一番上、n-1が一番下。必ず1番下のポール位置を使うことがヒントになる)。
F(n, k)を、ポール0~nでk個のスタックを作ったときの最小コストと定義する。
、とすると、
このように展開すると、まずの部分は予め計算すれば定数時間で求めることができる。
そして、の部分は、独立項、傾きの線集合について、最小値を求めることと同義。傾きは単調増加しているので、Convex Hull Trickを使うといちいちループせずとも効率よく求めることができる。
Convex Hull Trickはこのサイトが分かりやすかった。
http://wcipeg.com/wiki/Convex_hull_trick
class Program { const int MAXN = 5000; static double[] weight = new double[MAXN + 5]; static double[] pos = new double[MAXN + 5]; static double[] A = new double[MAXN + 5]; static double[] B = new double[MAXN + 5]; static double[] F = new double[MAXN + 5]; static double[,] dp = new double[MAXN, 2]; static void Main(string[] args) { int N, K, x, k; var s = Console.ReadLine().Split().Select(v => Int32.Parse(v)).ToList(); N = s[0]; K = s[1]; for (x = N - 1; x >= 0; --x) { s = Console.ReadLine().Split().Select(v => Int32.Parse(v)).ToList(); pos[x] = s[0]; weight[x] = s[1]; } for (x = 0; x < N; ++x) { A[x] = weight[x] + (x > 0 ? A[x - 1] : 0); B[x] = pos[x] * weight[x] + (x > 0 ? B[x - 1] : 0); F[x] = dp[x, 1] = B[x] - pos[x] * A[x]; } var convexHullTrick = new ConvexHullTrick(); for (k = 2; k <= K; ++k) { convexHullTrick.Init(); convexHullTrick.AddLine(A[k - 2], dp[k - 2, (k - 1) & 1] - B[k - 2]); for (x = k - 1; x < N; ++x) { if (k == x + 1) dp[x, k & 1] = 0; else dp[x, k & 1] = F[x] + convexHullTrick.Query(pos[x], true); convexHullTrick.AddLine(A[x], dp[x, (k - 1) & 1] - B[x]); } } Console.WriteLine((double)dp[N - 1, K & 1]); } } public class ConvexHullTrick { class Line { public double A; public double B; public Line(double a, double b) { A = a; B = b; } public double GetY(double x) { return A * x + B; } } Deque<Line> lines = new Deque<Line>(); public void Init() { lines.Init(); } // y = ax + b public void AddLine(double a, double b) { Insert(new Line(a, b)); } double Area(Line a, Line b, Line c) { var ax = (b.A - a.A); var bx = (c.B - a.B); var ay = (c.A - a.A); var by = (b.B - a.B); return ax * bx - ay * by; } bool Cw(Line a, Line b, Line c) { return Area(a, b, c) < 0; } void Insert(Line l) { while (lines.Count > 1 && Cw(lines[lines.Count - 2], lines[lines.Count - 1], l)) { lines.PopBack(); } if (lines.Count == 1) { if (lines[0].B > l.B) lines.PushBack(l); } else { lines.PushBack(l); } } public double Query(double x, bool canRemoveFrontLines = false) { if (lines.Count == 0) { return 0; } if (canRemoveFrontLines) { while (lines.Count > 1 && lines[0].GetY(x) > lines[1].GetY(x)) { lines.PopFront(); } return lines[0].GetY(x); } else { for (int i = 0; i < lines.Count - 1; i++) { if (lines[i].GetY(x) < lines[i + 1].GetY(x)) { return lines[i].GetY(x); } } } return lines[lines.Count - 1].GetY(x); } }
DequeはC++のDequeをC#で実装した個人ライブラリのもの。List等だとTLEになる。
整数の数列が与えられる。次にq個のクエリが"left right x y"の形で与えられる。クエリごとに、数列で以下の条件を満たす要素数を答えよ。
(制約)
1 <= n, q, <= 4 x 10^4
0 <= a[i] <= 4 x 10^4
0 <= left <= right < n
1 <= x <= x x 10^4
0 <= y < x
・xが小さいとき
あらかじめ、x,yのすべての組み合わせについて、a[i]%x==y を満たす要素番号を配列で持てばよい。Left・Rightで二分探索すればO(logN)で求めることができる。
・xが大きいとき
xが大きいとあらかじめ準備することが不可能になる。その代わりa[i]の組み合わせ数が小さくなるので、こちらを列挙できる。同様に、あり得るa[i]の組み合わせ分だけそれぞれ要素番号を持っておけば、Left・Rightでの二分探索が可能になる。
class Program { static int N = 40000; static int K = 200; //sqrt(N) static void Main(string[] args) { Console.SetOut(new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false }); // [x, y] => list of all indices satisfy a[i] % x == y var pos = new List<int>[K + 2, K + 2]; for (int i = 0; i < K + 2; i++) for (int j = 0; j < K + 2; j++) pos[i, j] = new List<int>(); // [z] => list of all indices satisfy a[i] == z var poss = new List<int>[N + 1]; for (int i = 0; i < N + 1; i++) poss[i] = new List<int>(); int n, q; var str = Console.ReadLine().Split().Select(v => Int32.Parse(v)).ToArray(); n = str[0]; q = str[1]; var a = ReadLine().Split().Select(v => Int32.Parse(v)).ToArray(); for (var i = 1; i < K; i++) { for (int j = 0; j < n; j++) { pos[i, a[j] % i].Add(j); } } for (var i = 0; i < n; i++) { poss[a[i]].Add(i); } for (var i = 0; i < q; i++) { str = Console.ReadLine().Split().Select(v => Int32.Parse(v)).ToArray(); var l = str[0]; var r = str[1]; var x = str[2]; var y = str[3]; int ans = 0; if (x < K) { int st = LowerBound(pos[x, y], l); int en = UpperBound(pos[x, y], r); --en; if (en - st + 1 >= 1) ans += en - st + 1; } else { // iterate through all a[i] candidates that satisfy a[i] % x == y for (int z = y; z <= 40000; z += x) { // count the number within the range int st = LowerBound(poss[z], l); int en = UpperBound(poss[z], r); --en; if (en - st + 1 >= 1) ans += en - st + 1; } } Console.WriteLine(ans); } Console.Out.Flush(); } }
LowerBound()とUpperBound()は個人ライブラリのもの。
以下の2つを定義する。
・無向グラフGの三角形の数を、辺(u, v)・(u, w)・(v, w)がGの辺であるトリプル{u, v, w}(順序は問わない)の数と定義する
・グラフG'を、三角形の数/頂点数が最大となるグラフGのvertex-induced sub-graphと定義する
Gが与えられたとき、G'のいずれか一つを出力せよ。
1 <= 頂点数 <= 50
例として、次のグラフを考える。
これを以下のようなS-Tグラフに変換する。
このグラフをよく観察すると、
・m = 0.1のとき
最大フローは三角形の数より小さい
・m = 0.333...のとき
最大フローは三角形の数より小さい。三角形Aからのフローは1になるが、三角形B+Cからのフローが2に満たないので。
・m = 0.5のとき
最大フローは三角形の数と等しくなる。三角形Aからのフローは1、三角形B+Cからのフローが2になる。
・mがそれより大きいとき
最大フローは三角形の数と等しくなる
となっている。つまり、ちょうどフローと三角形の数が等しくなる場合のmが、求める「三角形の数/頂点数が最大」となることが分かる。よって、mを使って二分探索すれば解が求められる。
最終的な解は、「ちょうどフローと三角形の数が等しくなる場合」よりも少しだけ小さいmを使って最大フローを求めたときの、T側の集合(Maximum Closure Problemの最適解ではないほうの集合)になる。
class Program { static double MAX_FLOW = double.MaxValue; static void Main(string[] args) { var n = Int32.Parse(Console.ReadLine()); // graph var g = new bool[n, n]; for (var i = 0; i < n; i++) { var s = Console.ReadLine().Split().Select(v => v == "1").ToArray(); for (var j = 0; j < n; j++) { g[i, j] = s[j]; } } // triangles var t = new List<Tuple<int, int, int>>(); for (int i = 0; i < n; i++) { for (int j = 0; j < i; ++j) { for (int k = 0; k < j; ++k) { if (g[i, j] && g[j, k] && g[k, i]) { t.Add(new Tuple<int, int, int>(i, j, k)); } } } } int S, T; S = t.Count() + n; T = t.Count() + n + 1; Dinic graph = new Dinic(); double l = 0, r = 50 * 50 * 50; while ((r - l) > 1e-10) { double m = (l + r) / 2; graph.Init(); for (var i = 0; i < n; i++) { graph.AddEdge(S, t.Count() + i, m); } for (var i = 0; i < t.Count(); i++) { graph.AddEdge(t.Count() + t[i].Item1, i, MAX_FLOW); graph.AddEdge(t.Count() + t[i].Item2, i, MAX_FLOW); graph.AddEdge(t.Count() + t[i].Item3, i, MAX_FLOW); graph.AddEdge(i, T, 1); } var x = graph.GetMaxFlow(S, T); if (t.Count() > x) { l = m; } else { r = m; } } var ret = graph.GetStCut(S).Where(v => v >= t.Count() && v != S && v != T).Select(v => v - t.Count()); Console.WriteLine(ret.Count()); foreach (var v in ret) Console.Write((v + 1) + " "); Console.WriteLine(); } }
Dinicは個人ライブラリのもの。
Maximum closure problem
Maximum closure problem の学習まとめ。以下のサイトを参考にした。
Closure problem - Wikipedia
http%3A%2F%2Friot.ieor.berkeley.edu%2F~dorit%2Fpub%2Fscribe%2Flec11%2FLec11posted.pdf&usg=AFQjCNEhubnfNuotTV0_wrbkGGdEF9UHMA&sig2=ewamZFzAoKgnMP5FaFV5cA&bvm=bv.151325232,d.amc *1
Maximum closure problemとは、ノードに重み(正負あり)の付いた有向グラフがあたえられたとき、重みの合計値が最大になるグラフのClosedなサブセットを求める問題である。
Closedのグラフとは、グラフの全ノードについて、その下流ノードがすべてそのグラフに属するもの。たとえば下の図だと、(a)はClosedだが(b)はClosedではない。
(*1より抜粋)
求め方
次のようなS-Tグラフを作成する。
・Sから正の重みがついたノードへ、その重み付きのエッジを追加
・Tから負の重みがついたノードへ、その重み付きのエッジを追加
・それ以外のエッジは、重み∞にする
そしてS-Tの最小カットを行い、S側の集合が求めるサブセットになる。
例えば次のような元グラフがあったとする。
これをS-Tグラフ化したものが以下になる。(点線が最小カット)
S側の集合{b, c, d, e, g}が最大のClosedセットであり、重みの合計値は6になっている。
有向グラフについて、がの最小カットであれば、はの重みの合計が最大になっているclosedセットである。(はから作成したグラフ)
証明
、とする。
(*1より抜粋)
は定数なので、を最小化するということは、の最大化と同じことがわかる。
最小s-tカットの求め方は、以下のスライドが分かりやすかった。
https://www.slideshare.net/KuoE0/acmicpc-minimum-cut
また、Dinicという方法で最小カット(最大フロー)を求める方法はこちらが参考になる。
https://www.slideshare.net/KuoE0/acmicpc-dinics-algorithm
DinicのC#実装
public class Dinic { public class Edge { public int V; public double C; public Edge N; public Edge B; } Edge[] _pool = new Edge[0]; int _topIdx; Edge[] _adj = new Edge[0]; public int MaxIdx; int _minV; public Dinic() { Expand(ref _pool, 128, true); Expand(ref _adj, 128, false); Init(); } public void Init() { for (int i = 0; i < _adj.Length; i++) _adj[i] = null; _topIdx = 0; MaxIdx = 0; _minV = Int32.MaxValue; } void Expand(ref Edge[] edges, int size, bool fillWithEmptyEdge = false) { if (edges.Length <= size) { var newEdges = new Edge[Math.Max(size, edges.Length * 2)]; for (int i = 0; i < edges.Length; i++) newEdges[i] = edges[i]; if (fillWithEmptyEdge) { for (int i = edges.Length; i < newEdges.Length; i++) { newEdges[i] = new Edge(); } } edges = newEdges; } } public void AddEdge(int u, int v, double c, double bc = 0) { MaxIdx = Math.Max(MaxIdx, Math.Max(u + 1, v + 1)); _minV = Math.Min(_minV, Math.Min(u, v)); Expand(ref _pool, _topIdx + 1, true); Expand(ref _adj, MaxIdx); _pool[_topIdx].V = v; _pool[_topIdx].C = c; _pool[_topIdx].N = _adj[u]; _adj[u] = _pool[_topIdx]; _topIdx++; _pool[_topIdx].V = u; _pool[_topIdx].C = bc; _pool[_topIdx].N = _adj[v]; _adj[v] = _pool[_topIdx]; _topIdx++; _adj[u].B = _adj[v]; _adj[v].B = _adj[u]; if (u == v) { _adj[u].N.B = _adj[u]; _adj[v].B = _adj[v].N; } } int[] _d; int[] _q; int _qh; int _qt; Edge[] _cur; public double GetMaxFlow(int s, int t) { MaxIdx = Math.Max(MaxIdx, Math.Max(s + 1, t + 1)); _minV = Math.Min(_minV, Math.Min(s, t)); _d = new int[MaxIdx]; _q = new int[MaxIdx]; _cur = new Edge[MaxIdx]; double f = 0; while (ReLabel(s, t)) { for (int i = 0; i < MaxIdx; i++) _cur[i] = _adj[i]; f += Augument(s, t, s, double.MaxValue); } return f; } bool ReLabel(int s, int t) { for (int i = 0; i < MaxIdx; i++) _d[i] = Int32.MaxValue; _d[_q[_qh = _qt = 0] = t] = 0; while (_qh <= _qt) { var u = _q[_qh++]; for (var i = _adj[u]; i != null; i = i.N) { if (i.B.C != 0 && _d[i.V] > _d[u] + 1) { _d[i.V] = _d[u] + 1; if ((_q[++_qt] = i.V) == s) { return true; } } } } return false; } double Augument(int s, int t, int u, double e) { if (u == t) return e; double f = 0; for (var i = _cur[u]; i != null; i = i.N) { if (i.C > 0 && _d[u] == _d[i.V] + 1) { var df = Augument(s, t, i.V, Math.Min(e, i.C)); if (df > 0) { i.C -= df; i.B.C += df; e -= df; f += df; } } if (!(e > 0)) break; } return f; } // (S, T) public Tuple<List<int>, List<int>> GetStCut(int s) { var used_flg = new bool[MaxIdx]; Dfs(s, used_flg); var ret_s = new List<int>(); var ret_t = new List<int>(); for (int i = _minV; i < MaxIdx; i++) { if (!used_flg[i]) { ret_t.Add(i); } else { ret_s.Add(i); } } return new Tuple<List<int>, List<int>>(ret_s, ret_t); } void Dfs(int u, bool[] used_flg) { if (used_flg[u]) return; used_flg[u] = true; for (var i = _adj[u]; i != null; i = i.N) { if (i.C > 1e-6) Dfs(i.V, used_flg); } } }
CodinGame - Ghost in the Cell 参加日記
CodinGameのコンテストに初参加してみた。ゲームAIを作ってその強さを競うものなのだが、面倒な環境構築が不要でなかなか楽しかった。対戦動画も観ていて面白い。
https://www.codingame.com/replay/194505045
黄色が私。最終的にCyborgの数が多いほうが勝ち
ランキングはリーグ制。最初はウッドリーグ3部からスタートし、リーグボスを倒すごとにウッド2→ウッド1→ブロンズ→シルバー→ゴールドとランクアップする。また、途中でルールが追加されることもある。
ゲームルール概略
- ターン制
- マップ上にいくつかの工場がある
- 工場間は長さの違う道で繋がれている
- 工場は味方・敵・中立のいずれか
- 工場は1ターンごと0~3体のCyborgを自動生産する
- 1ターンごと、味方・敵同時に行動を起こす
- 自工場からほかの工場にCyborg部隊を送ることができる
- 敵または中立の工場にCyborg部隊が到着したら戦いが起こる
- 戦いはCyborg数の多いほう勝利し、数の差分だけ生き残る
- 戦いに勝ったら工場を占領できる
- 最終的に相手を全滅させるか、400ターン後にcyborgの多いほうが勝ち
- 1ターンに複数の部隊を送ることができる*
- Cyborgを10消費して、工場のCyborg生産数を増やすことができる(3まで)*
- 2回まで爆弾を送ることができる*
- 爆弾を被弾すると、工場のCyborg数が半分、または10まで減る(小さいほう)*
(*はリーグが上がるごとに追加されたルール)
実装
1ターンの制限時間が50msしかないので、深く手を読む方針はとらなかった。基本的に、(1)危ない自工場があったら助ける(2)生産力のある中立工場があったら占領しようとする(3)敵に爆弾を送ってみる(4)敵工場を占領しようとする(4)遊んでる工場があったら前線に兵を送る、の優先順位で手の候補をいくつか作成し、そこから21手くらい先までシミュレートして局面評価がベストのものを採用した。
反省
序盤にいろいろ考えすぎて実装が遅れたのが良くなかった。Topcoderのマラソンマッチと違い途中でルールが変わるし、またリーグが落ちることは(たぶん)ない仕組みなので、軽いコードをどんどん書いてSubmitしていったほうがよさそうだ。シミュレーション中の手や評価関数がまったく詰められなかったのも反省点。
結果はぎりぎりシルバーリーグの103位/311人だった。次回はシルバー上位を目標にしよう。
HackerRank Ad Infinitum16 参加日記
始めて参加した。数学関連の問題がでるコンテストらしい。
46位/673人だけど初回参加者用の区分だっただからレベルが低いのかも。
ad Infinitum: 無限に、永久に(ラテン語)
q個の整数が与えられる。それぞれの整数(nとする)について、集合[1,n]内で、一意な素因数の数が最も多いものを算出し、その数を出力せよ。
1 <= q <= 10^5
1 <= n <= 10^18
素数を小さい順に、nを超えるまでかけていけばよい。素数は50くらいまでしか使わないので、最初に列挙しておくと効率が良い。
var q = Int32.Parse(Console.ReadLine()); while (q > 0) { var n = Int64.Parse(Console.ReadLine()); var ret = 0; BigInteger x = 1; foreach (var p in primes) //primesは素数のリスト(昇順) { x *= p; if (x > n) break; ret++; } Console.WriteLine(ret); q--; }
Russian Peasant Exponentiation
q個のクエリが与えられる。それぞれのクエリでは、整数k,m,a,bが与えられる。(a+bi)^kを求めよ(iは虚数単位)。解は、実部と虚部をそれぞれmでModしたものを出力せよ。
大きなべき乗を求める方法は次を参考にせよ
https://www.hackerrank.com/external_redirect?to=http://lafstern.org/matt/col3.pdf
1 <= q <= 10^5
0 <= k <= 10^18
2 <= m <= 10^9
0 <= a, b <= m
「ロシア農民のアルゴリズム」を複素数に応用しろというもの。複素数クラスを作成し、乗算とModを実装すれば、実数と同じコードになる。複素数クラスはNumericsのものだとオーバーフローの危険性がありそうだ。
static void Main(string[] args) { Console.SetOut(new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false }); var q = Int32.Parse(Console.ReadLine()); while (q > 0) { //a,b,k,m -> (a + bi)^k mod m var str = Console.ReadLine().Split(); var a = Int64.Parse(str[0]); var b = Int64.Parse(str[1]); var k = Int64.Parse(str[2]); var m = Int64.Parse(str[3]); var comp = new MyComplex(a, b); var modPow = ModPow(comp, k, m); //mod前のmの足し忘れ注意! Console.WriteLine(string.Format("{0} {1}", (modPow.Real + m) % m, (modPow.Imaginary + m) % m)); q--; } Console.Out.Flush(); } //ロシア農民のアルゴリズム static MyComplex ModPow(MyComplex x, Int64 n, Int64 mod) { while ((n & 1) == 0) { x = (x * x) % mod; n >>= 1; } var ret = x; n >>= 1; while (n > 0) { x = (x * x) % mod; if ((n & 1) != 0) ret = (ret * x) % mod; n >>= 1; } return ret % mod; } class MyComplex { public Int64 Real; public Int64 Imaginary; public MyComplex(Int64 real, Int64 img) { Real = real; Imaginary = img; } public static MyComplex operator *(MyComplex c1, MyComplex c2) { return new MyComplex(c1.Real * c2.Real - c1.Imaginary * c2.Imaginary, c1.Real * c2.Imaginary + c1.Imaginary * c2.Real); } public static MyComplex operator %(MyComplex c1, Int64 mod) { return new MyComplex((c1.Real) % mod, (c1.Imaginary) % mod); } }
正n角形のパンケーキが与えられる。このパンケーキは、①中心と各頂点を通るもの②中心と各頂点の中間点を通るもの、の2種類の軸が存在する(合計n本)。軸は0~n-1の番号が時計回りに連続でついている。
このとき、n個のクエリが与えられる。クエリの種類は2つ:
タイプ1:軸kで裏返す
タイプ2:パンケーキを、(360*k) / n 度だけ時計回りに回転させる
すべてのクエリが終了したときのパンケーキを、タイプ1またはタイプ2を1回だけ適用させて、初期位置に戻したい。このクエリを答えよ。
3 <= n <= 10^6
1 <= m <= 10^6
0 <= k <= n
ややこしく考えると嵌りそうだが、実際は初期に軸0にあった頂点の位置と、裏返されているか否かだけ管理すればよい。
var str = Console.ReadLine().Split(); var n = Int32.Parse(str[0]); var m = Int32.Parse(str[1]); var x = 2 * n; //位置(頂点+頂点間) var pos = 0; //初期に軸0にあった頂点の位置 var isFlipped = false; while (m > 0) { str = Console.ReadLine().Split(); var k = Int32.Parse(str[1]); switch (str[0]) { case "1": //rotate pos = (pos + k * 2) % x; break; default: //flip pos = (pos + ((k + x - pos) % x) * 2) % x; isFlipped = !isFlipped; break; } m--; } if (!isFlipped) { Console.WriteLine("1 " + ((x - pos) / 2).ToString()); } else { Console.WriteLine("2 " + (pos / 2).ToString()); }
方程式がq個与えられたとき、それぞれ次を満たす最も原点に近い点を求めよ。
・xとyは整数
・xは0より大きい
複数の解があるときは、xのより小さいものを答えよ。
1 <= q <= 10^5
1 <= a <= 10^8
1 <= b <= 10^8
1 <= c <= 10^8
a, b, cは整数
整数解が存在するといことは、cはgcd(a,b)で割り切れる。そして、拡張ユークリッドアルゴリズムを使って一組の(x, y)が計算できたとき、すべての組は次の形で表せる。ベズーの等式 - Wikipedia
ここで、、とすると
と表すことができる。
を最小化するのが目的なので、上式の展開
を最小化すればよい。
とおくと、
になる。よって答えは以下のようになる。(実装は省略)
1. が負のとき
の場合
2. が正のとき
または の場合
m次元の超空間にn人が存在している。この人達は、次元のグリッド線上だけを動くことができる。全員の総移動距離が最小になるよう、空間のある地点に集まりたい。この地点を求めよ。
各人の初期位置は、次元0、次元1...の順にx0,x1...の形で与えられる。
1 <= n <= 10^4
1 <= m <= 10^2
- 10^9 <= xi <= 10^9 (整数のみ)
集合地点の位置は整数
グリッド線上のみ動くことができる(次元間をナナメに移動することはできない)ということは、各次元内で移動が完結しているということになる。よって、次元ごとに集合地点を求めればよい。
ある次元について、移動距離が最小になるのは、真ん中にいる人に集まる場合なので、ソートしてIndexが中点のものが答えになる。
static void Main(string[] args) { var str = Console.ReadLine().Split(); var n = Int64.Parse(str[0]); var m = Int64.Parse(str[1]); var friends = new List<List<Int64>>(); for (int i = 0; i < n; i++) { friends.Add(Console.ReadLine().Split().Select(v => Int64.Parse(v)).ToList()); } for (int i = 0; i < m; i++) { Console.Write(Get(i, friends)); if (i != m - 1) Console.Write(" "); } Console.WriteLine(); } static Int64 Get(int dimension, List<List<Int64>> friends) { var values = new List<Int64>(); foreach (var friend in friends) { values.Add(friend[dimension]); } values.Sort(); return values[(values.Count() - 1) / 2]; }