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になっていた。