CodinGame - Wondev Woman 参加日記
二度目のCodingGameコンテスト。ボードゲームAIの強さを競うもので、結果は世界310位/2299人、アメリカ17位/179人(ゴールドリーグ中位)だった。前回のCodinGame参加日記にも書いたが、このコンテストは
- ランキングはリーグ制
- ウッドリーグ3部からスタート
- リーグボスを倒すごと、ウッド2→ウッド1→ブロンズ→シルバー→ゴールド→レジェンドとランクアップする
- ランクアップとき、ルールが追加されることがある
の特徴がある。マッチを美しいグラフィックで観戦できるのが楽しい。
https://www.codingame.com/replay/243115997
ゲームルール概要
- ターン制の2Dボードゲーム
- お互い1つ(上位リーグより2つ)の駒を持つ
- 初期配置はランダム
- ボード上の各セルは、高さ(0~4)を持つ
- また、ボード上には移動できないセルもある
- 駒は上下左右および斜めの8か所に移動できる
- ただし、移動できるのは現在より低い地点か、1つだけ高い地点のみ
- また、高さ4のセルへは移動できない
- 各ターンで1つの駒へ、次の命令を行う
- MOVE&BUILD …移動して、移動先の隣接セルの高さを+1する
- PUSH&BUILD(上位リーグより) …隣接する敵駒を押して移動させ、その場所の高さを+1する
- 下位リーグ:高さ3のセルに最初に到達したほうが勝ち
- 上位リーグ:高さ3のセルに到着した回数の多いほうが勝ち
- 敵の駒情報は、味方に隣接してる場合のみ与えられる(上位リーグより)
実装
- 1手だけ読む
- ゴール回数、現在地と移動可能な隣接セルでスコアを付ける
- 現在地・隣接セルともに、高いほどよいスコアにする
- 敵に近かったらペナルティ
- 動けなくなったらペナルティ
敵の場所の予想、狭い場所を嫌う仕組みなどは思いついたが実装せず。2手読みさせたら弱くなったのが原因不明。
https://bitbucket.org/yambe2002/codingame-wondev-woman
反省
こんな感じに「それっぽく不具合なく動く」程度でゴールド中位くらいになるようだ。Topcoder MMの黄色下位と同レベルくらいか。
レジェンドリーグからが本番の雰囲気があるので、次回はそこを目指したい。
Codechef June Challenge 2017 参加日記
966位/9366人の自己ワースト記録。追い上げが甘かった。以下、易しい問題(全体の正答率が高いもの)は省略する。
N個の料理と、それぞれを食べたときの満足度A[i]が与えられる。次の条件ですべての料理を食べたとき、得られる満足度の合計を最大化せよ。
・料理からSubsetを選択
・Subsetを食べる。このときの満足度は、Subsetの数x各満足度の和
1 <= N <= 10^5
-10^8 <= A[i] <= 10^8
基本的に満足度が正の料理は1つのSubsetとして食べ、負の料理は1つずつ食べる。ただし、あまり負の値が大きくないものは、正のSubsetに加えたほうが良い場合もある。なので負のものを小さい順に正のSubsetに加えて試していけばよい。
public static long GetAns(long[] a) { var negs = a.Where(v => v < 0).OrderByDescending(v => v).ToArray(); var posCnt = a.Count(v => v >= 0); var posSum = a.Where(v => v >= 0).Sum(); var ret = posCnt * posSum + negs.Sum(); var allNegSum = negs.Sum(); if (negs.Count() > 0) { var negsSum = 0L; for (int i = 0; i < negs.Length; i++) { negsSum += negs[i]; var newRet = (posCnt + (i + 1)) * (posSum + negsSum) + (allNegSum - negsSum); ret = Math.Max(ret, newRet); } } return ret; }
整数[1,K]のSubsetがN個与えられる。Subsetからペアを選んだとき、そのUnionが1~Kすべてを含む組み合わせ数を求めよ。
1 <= N, K <= 2500
1 <= len[i] <= K
1 <= len[1] + len[2] + ... + len[N] <= 10000
(len[i]はSubset[i]の長さ)
Subsetのペア組み合わせすべてを判定すればよい。各Subsetの状態(最大2500ビット分)をInt64型の配列で表せば、計算量はO(N^2 * K/64)程度なので間に合う。
static Bit[] bits = new Bit[2501]; public static long GetAns(int n, int k, List<int[]> sets) { for (int i = 0; i < sets.Count; i++) bits[i] = new Bit(sets[i]); long ret = 0; for (int i = 0; i < sets.Count() - 1; i++) { for (int j = i + 1; j < sets.Count(); j++) { if (bits[i].Match(bits[j], k)) ret++; } } return ret; } public class Bit { public ulong[] Data = new ulong[40]; public Bit(int[] listData) { foreach (var data in listData) Set(data - 1); } public void Set(int idx) { Data[idx / 64] |= (1ul << idx % 64); } public bool Match(Bit b2, int k) { if (k % 64 != 0) { var idx = k / 64; var val = Data[idx] | b2.Data[idx]; if (val != (1UL << k % 64) - 1) return false; k -= k % 64; } for (int i = 0; i < k; i += 64) { var d = Data[i / 64] | b2.Data[i / 64]; if (d != ulong.MaxValue) return false; } return true; } }
3つの整数を引数にとる関数f(x,y,z)は、y>=xかつy>=zのときは(x+y)*(y+z)、それ以外ならゼロを返す。配列A、B、Cが与えられたとき、f(A[i], B[j], C[k])の合計を求めよ。解答は1000000007でMODして出力すること。
1 <= len(A), len(B), len(C) <= 100000
1 ≤ A[i], B[i], C[i] ≤ 1000000000
Bを固定値bで考える。さらに、A・Cからb以上の要素のみ取り出した配列をそれぞれa、cとする。
a: a[0], a[1], a[2],...
b
c: c[0], c[1], c[2],...
すると求める値は、
(a[0]+b)(b+c[0])+(a[0]+b)(b+c[1])+ ... +
(a[1]+b)(b+c[0])+(a[1]+b)(b+c[1])+ ....
...
となる。これを変形すると
(a[0]+b)*{(cの数)*b + (cの合計)}+
(a[1]+b)*{(cの数)*b + (cの合計)}+
...
それぞれの右辺が同じなので
{(aの合計)+(aの数)*b)}*{(cの数)*b + (cの合計)}
となる。
Aからb以上の要素を取り出すのには、予めAをソートして二分探索を使えばよい。
(a[]の合計)などは、予めAをソートし、合計していったものを配列で持っておけば簡単に求められる。
サンプルはC++。C#だとTLEになってしまうようだ。CodechefのC#はバージョンが低いせいか、Array.Sort()がちょっと遅い気がする。
long long MOD = 1000000007; void getSumArray(long long *ar, long long *ret, int n) { for (int i = 0; i < n; i++) { ret[i] = ((i == 0 ? 0 : ret[i - 1]) + ar[i]) % MOD; } } int main() { int t; scanf("%d", &t); while ( t > 0 ) { int p, q, r; scanf("%d %d %d", &p, &q, &r); long long a[p]; long long b[q]; long long c[r]; for(int i = 0; i < p ; i++) { scanf("%lld", &a[i]); } for(int i = 0; i < q ; i++) { scanf("%lld", &b[i]); } for(int i = 0; i < r ; i++) { scanf("%lld", &c[i]); } sort(a, a + p); sort(c, c + r); long long aSum[p]; long long cSum[r]; getSumArray(a, aSum, p); getSumArray(c, cSum, r); long long ret = 0; for (int i = 0; i < q; i++) { long long y = b[i]; int aUb = min(p - 1, lower_bound(a, a + p, y + 1) - a - 1); int cUb = min(r - 1, lower_bound(c, c + r, y + 1) - c - 1); if (aUb < 0 || cUb < 0) continue; ret += ((aUb + 1) * y % MOD + aSum[aUb]) * ((cUb + 1) * y % MOD + cSum[cUb]) % MOD; ret %= MOD; } cout << ret << endl; t--; } }
長さNの整数列Aがある。整数L,R,X,YからなるクエリがQ個与えられるので、それぞれに対し次の疑似コード結果を回答せよ。
F(L, R, X, Y) { result := 0 for( i = X to i = Y ) { if( isPrime(i) ) { for( j = L to j = R ) { number := a[j] exponent := 0 while( number % i == 0 ) { exponent := exponent + 1 number := number/i } result := result + exponent } } } return result }1 <= N, Q <= 10^5
1 <= L <= R <= N
1 <= X <= Y <= 10^6
2 <= A[i] <= 10^6
問題を言い換えると、
・Aの部分配列[L:R]を抜き出し、
・要素それぞれの素因数のうち、X以上Y以下の部分について
・階乗部分の合計を求めよ
となり、セグメント木で解くことができる。各セグメントには、範囲内の素因数分解した値を配列でもつ。たとえば
A[0]=12, A[1]=10, A[2]=18
だとすると、セグメントでもつ値は
Seg[0]=[2,2,3]
Seg[1]=[2,5]
Seg[2]=[2,3,3]
Seg[0:1]=[2,2,2,3,5]
Seg[1:2]=[2,2,3,3,5]
Seg[0:2]=[2,2,2,2,2,3,3,3,5,5]
となる。あとは対象セグメントからX以上Y以下の要素数を回答すればよい(二分探索)。
public static List<int> GetAns(int[] a, List<Tuple<int, int, int, int>> queries) { var sieve = GetSieve(1000001); var factTable = GetFactTable(a, sieve); var segTree = new SegTree(a, factTable); return queries.Select(q => segTree.Query(q.Item1 - 1, q.Item2, q.Item3, q.Item4)).ToList(); } public static List<List<int>> GetFactTable(int[] a, int[] sieve) { var ret = new List<List<int>>(); foreach (var v in a) ret.Add(GetFactList(v, sieve)); return ret; } public static List<int> GetFactList(int value, int[] sieve) { var ret = new List<int>(); while (true) { if (sieve[value] == 0) { ret.Add(value); break; } ret.Add(sieve[value]); value /= sieve[value]; } ret.Reverse(); return ret; } public static int[] GetSieve(int n) { var ret = new int[n + 1]; for (int i = 0; i < ret.Length; i++) ret[i] = 0; ret[0] = ret[1] = -1; for (int i = 2; i < ret.Length; i++) { if (ret[i] != 0) continue; for (int j = i + i; j < ret.Length; j += i) { ret[j] = i; } } return ret; } public class SegTree { int _n; SegNode[] _dat; public class SegNode { // sorted public List<int> Factors; public SegNode(List<int> factors) { Factors = factors; } public SegNode(SegNode s1, SegNode s2) { if (s1 == null && s2 != null) { Factors = s2.Factors; return; } if (s1 != null && s2 == null) { Factors = s1.Factors; return; } Factors = new List<int>(); if (s1 == null && s2 == null) return; int l1 = 0, l2 = 0; while (l1 < s1.Factors.Count() && l2 < s2.Factors.Count()) { while (l1 < s1.Factors.Count() && l2 < s2.Factors.Count() && s1.Factors[l1] < s2.Factors[l2]) { Factors.Add(s1.Factors[l1]); l1++; } while (l1 < s1.Factors.Count() && l2 < s2.Factors.Count() && s1.Factors[l1] > s2.Factors[l2]) { Factors.Add(s2.Factors[l2]); l2++; } while (l1 < s1.Factors.Count() && l2 < s2.Factors.Count() && s1.Factors[l1] == s2.Factors[l2]) { Factors.Add(s1.Factors[l1]); l1++; Factors.Add(s2.Factors[l2]); l2++; } } while (l1 < s1.Factors.Count()) { Factors.Add(s1.Factors[l1]); l1++; } while (l2 < s2.Factors.Count()) { Factors.Add(s2.Factors[l2]); l2++; } } public int Query(int x, int y) { var ret = LowerBound(Factors, y + 1); if (ret >= Factors.Count()) ret = Factors.Count(); var xl = UpperBound(Factors, x - 1); if (xl > 0) ret -= xl; return ret; } public int LowerBound(List<int> ar, int 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; } public static int UpperBound(List<int> ar, int val) { var lb = -1; var ub = ar.Count(); while (ub - lb > 1) { var mid = (lb + ub) / 2; if (ar[mid] <= val) { lb = mid; } else { ub = mid; } } return lb + 1; } } int[] _a; List<List<int>> _factTable; public SegTree(int[] a, List<List<int>> factFable) { _a = a; _factTable = factFable; _n = 1; while (_n < a.Count()) _n *= 2; ConstructTree(); } void ConstructTree() { _dat = new SegNode[_n * 2]; ConstructTree(0, 0, _a.Count()); } void ConstructTree(int k, int l, int r) { // bottom-most if (l == r - 1) { _dat[k] = new SegNode(_factTable[l]); return; } ConstructTree(k * 2 + 1, l, (l + r) / 2); ConstructTree(k * 2 + 2, (l + r) / 2, r); _dat[k] = new SegNode(_dat[k * 2 + 1], _dat[k * 2 + 2]); } public int Query(int a, int b, int x, int y) { return Query(a, b, 0, 0, _a.Count(), x, y); } int Query(int a, int b, int k, int l, int r, int x, int y) { if (r <= a || b <= l) return 0; if (a <= l && r <= b) return _dat[k] == null ? 0 : _dat[k].Query(x, y); else { var vl = Query(a, b, k * 2 + 1, l, (l + r) / 2, x, y); var vr = Query(a, b, k * 2 + 2, (l + r) / 2, r, x, y); return vl + vr; } } }
ノード数N・エッジ数Mからなる連結の無向グラフがある。ノードの破壊にはcost[i]の費用がかかる。なるべく少ないコストで、グラフからループを取り除いたときのトータルコストを求めよ。ただし、最終的なグラフは連結でなければならない。
1 <= N <= 10^4
N-1 <= M <= 5*10^4
1 <= cost[i] <= 10^5
テストケースは、(1)N<=20(2)N<=40(3)M=N(4)M<=N+3(5)完全グラフ(6)ランダム、のいずれかの条件で作成される。
次の方針で平均より少し上くらいの結果だった。
1、完全グラフのとき(M=N*(N-1)/2)は、最もコストの大きい2ノード以外をすべて破壊して終了
2、次数1のノードを、隣のノードにまとめてしまう(コストは合算する)。これでループの一部となるノードのみとなる
3、次数とコストの降順+乱数でノードを並び替える
4、ノードをひとつずつ取り出して、閉ループができないようにグラフを作っていく
5、あまったノードは破壊対象とし、解答の候補に入れる
6、時間があるなら3へ戻る
実装:https://www.codechef.com/viewsolution/14190840
上位陣は完全グラフかどうかだけでなく、6つのデータタイプのそれぞれを判断して別のロジックを用意しているようだ。
例:https://www.codechef.com/viewsolution/14237992
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); } } }