ARC049-ARC058+ABC043メモ(練習)
AtCoder Beginner Contest 043 - AtCoder Beginner Contest 043 | AtCoder
D - アンバランス / Unbalanced
文字列tについて、tの長さが2以上であり、かつ過半数の文字が同じとき、tをアンバランスを呼ぶ。文字列sからアンバランスな部分文字列を探して、その位置を出力せよ。複数ある場合は、どれを出力してもよい。
2 <= |s| <= 10^5
sは小文字のアルファベットのみ
過半数かどうかなので、連続する3文字分のみ判定すればよい。
if (s.Length == 2) { if (s[0] == s[1]) Console.WriteLine("1 2"); else Console.WriteLine("-1 -1"); return; } for (int i = 0; i < s.Length - 2; i++) { for (int c = 'a'; c <= 'z'; c++) { var cnt = 0; for (int j = 0; j < 3; j++) if (s[i + j] == c) cnt++; if (cnt >= 2) { Console.WriteLine(string.Format("{0} {1}", i + 1, i + 3)); return; } } } Console.WriteLine("-1 -1");
AtCoder Regular Contest 058 - AtCoder Regular Contest 058 | AtCoder
C: こだわり者いろはちゃん / Iroha's Obsession - AtCoder Regular Contest 058 | AtCoder
嫌いな数字D1,D2...Dkある。10進表記でこれらの数字を使わずN円のものを買うとき、支払額の最小はいくらか。
Nから1ずつ増やして試していけばよい。
for (int i = n; i < Int32.MaxValue; i++) { if (!i.ToString().Select(c => Int32.Parse(c.ToString())).ToList().Any(c => cannot_use.Contains(c))) { Console.WriteLine(i); break; } }
D: いろはちゃんとマス目 / Iroha and a Grid - AtCoder Regular Contest 058 | AtCoder
縦Hマス、横Wマスのマス目がある。1番左上のマスから、右が左に1マスずつ進める。このとき、一番右下に行く方法は何通りあるか。
ただし、下からAマス以内かつ左からBマス以内は通れない。
1 <= H, W <= 100000
1 <= A < H
1 <= B < W
左上から図の①までの経路数を求め、それぞれに②右下までの経路数を掛けて合計すればよい。
const Int64 mod = 1000000007; static Int64 Solve(int h, int w, int a, int b) { Precal_FactAndInv(mod); Int64 ret = 0; for (int i = 0; i < h - a; i++) { var c = Nck(b + i - 1, i, mod); c *= Nck(w - b - 1 + h - 1 - i, h - 1 - i, mod); ret += c; ret %= mod; } return ret; }
本番でNck()をあらかじめ用意していなかったので、TLEにならない解をうまく作れなかった。
E: 和風いろはちゃん / Iroha and Haiku - AtCoder Regular Contest 058 | AtCoder
長さNの、それぞれの値が1~10の数列は全部で10^N通りある。このうち、XYZを含むものは何通りか。XYZを含むとは以下のように定義する。
を満たすが存在する。
3 <= N <= 40
1 <= X <= 5
1 <= Y <= 7
1 <= Z <= 5
全パターン(10^n)からXYZを含まないパターンを引いて求める。含まないパターンは次のDPを定義して計算。
・DP[i][s]:0~iまでで、S={2つ前の値, 1つ前の値, 今回の値}の場合の組み合わせ合計
Sの各値を単純に1~10で持つと状態数が多すぎて計算できないが、X, Y, Zの合計が17しかないことに着目し、1をb1、2をb10・・・というように二進数で管理すれば、Sは17ビットまで小さくなる。
Int64 ret = 1; for (int i = 0; i < n; i++) { ret *= 10; ret %= mod; } var possibleMask = 1 << (x + y + z); possibleMask |= 1 << (y + z); possibleMask |= 1 << (z); var mask = (1 << (x + y + z + 1)) - 1; var prevDp = new UInt64[mask + 1]; var curDp = new UInt64[mask + 1]; prevDp[1] = 1; //ループ1回目は今回の値だけ存在する! for (int cnt = 0; cnt < n; cnt++) { for (int prevState = 0; prevState <= mask; prevState++) { for (int i = 1; i <= 10; i++) { var nextState = ((prevState << i) | (1)) & mask; if ((possibleMask & nextState) == possibleMask) continue; curDp[nextState] += prevDp[prevState]; curDp[nextState] %= mod; } } prevDp = curDp; curDp = new UInt64[mask + 1]; } for (int state = 0; state < mask + 1; state++) { ret -= (Int64)prevDp[state]; ret %= mod; } ret = (ret + mod) % mod; //負になる場合あり Console.WriteLine(ret);
試しにXYZを含める場合で計算しようとしたが断念。
ARC052
A: 何期生? - AtCoder Regular Contest 052 | AtCoder
文字列Sには、1つの連続する数字が含まれる。この数字を出力せよ。
そのまま。正規表現で解いてみた。
Console.WriteLine(new Regex(@"[^0-9]").Replace(Console.ReadLine(), ""));
B: 円錐 - AtCoder Regular Contest 052 | AtCoder
三次元空間にN個の円錐が、重ならないように浮いている。どの円錐も、底辺がyz平面と水平である。円錐[i]は、底辺のx座標x[i]、半径r[i]、高さh[i]が与えられる。
このとき、Q個の以下のクエリに答えよ
二つの整数AとBが与えられたとき、A<=x<=Bとなる空間のうち、いずれかの円錐の内側にある部分の体積を求める
1<=N<=100、1<=Q<=100000、0<=x[i]<=10000、1<=h[i]<=10000、1<=R[i]<=1000
0<=A[i]<=B[i]<=20000
v[p](pは0~20000)をx座標[0,p]の空間のうち円錐の内側にある部分の体積合計、と定義して前もって計算した。各クエリに対しv[B]-v[A]が答えとなる。
もっとも、工夫無しで普通に解いても時間内に間に合うようだ。
var v = new double[20001]; for (int p = 1; p < 20001; p++) { for (int i = 0; i < n; i++) { if (p <= x[i]) continue; var v1 = (1.0 / 3.0) * Math.PI * Math.Pow((double)r[i], 2) * (double)h[i]; var v2 = p >= x[i] + h[i] ? 0 : (1.0 / 3.0) * Math.PI * Math.Pow((double)r[i] * ((double)(h[i] - (p - x[i])) / (double)h[i]), 2) * (double)(h[i] - (p - x[i])); v[p] += (v1 - v2); } } //result for (int i = 0; i < q; i++) { Console.WriteLine(v[b[i]] - v[a[i]]); }
C: 高橋くんと不思議な道 - AtCoder Regular Contest 052 | AtCoder
町0~N-1がある。町の間にはいくつかの道があり、道はタイプAとタイプBに分けられる。タイプAを通るとコスト1、タイプBを通ると(今までに通ったタイプBの数)+1のコストがかかる。町0からそれぞれの町までの最小コストを求めよ。
1 <= N <= 10^4
1 <= M <= 10^5
現在の町Idx・コスト・今までのタイプBの合計、を保持してDijkstraをするだけだが、適切に枝刈りをしないとTLEになる。
static void Main(string[] args) { ///Std入力は省略 //Dijkstra var que = new PriorityQueue<Path>(); var min_bnum = new int[n]; var min_cost = new int[n]; for (int i = 0; i < n; i++) { min_bnum[i] = Int32.MaxValue; min_cost[i] = Int32.MaxValue; } que.Push(new Path(0, 0, 0)); while (que.Count() > 0) { var path = que.Pop(); if (NoNeed(path, min_bnum, min_cost)) continue; Update(path, min_bnum, min_cost); foreach (var typeA in e_typeA[path.Idx]) { var newPath = new Path(typeA, path.Cost + 1, path.Bnum); if (NoNeed(newPath, min_bnum, min_cost)) continue; //Queueに入れる前にカットする que.Push(newPath); } foreach (var typeB in e_typeB[path.Idx]) { var newPath = new Path(typeB, path.Cost + path.Bnum + 1, path.Bnum + 1); if (NoNeed(newPath, min_bnum, min_cost)) continue; //Queueに入れる前にカットする que.Push(newPath); } } for (int i = 0; i < n; i++) Console.WriteLine(min_cost[i]); } static bool NoNeed(Path path, int[] min_bnum, int[] min_cost) { if (path.Bnum >= min_bnum[path.Idx] && path.Cost >= min_cost[path.Idx]) return true; return false; } static void Update(Path path, int[] min_bnum, int[] min_cost) { min_bnum[path.Idx] = Math.Min(min_bnum[path.Idx], path.Bnum); min_cost[path.Idx] = Math.Min(min_cost[path.Idx], path.Cost); }
ARC051
A: 塗り絵 - AtCoder Regular Contest 051 | AtCoder
二次平面がある。(x1, y1)から距離r以下の部分を青く塗り、つぎに(x2, y2)から(x3, y3)までの長方形内を赤く塗る。両方の色が塗られた箇所は紫になる。赤、青の有無を答えよ。
青の有無は、4頂点が赤の中心からr以上離れているかどうかで判定できる。
Console.WriteLine(x1 - r < x2 || x1 + r > x3 || y1 + r > y3 || y1 - r < y2 ? "YES" : "NO"); Console.WriteLine(GetSqDist(x1, y1, x2, y2) > r * r || GetSqDist(x1, y1, x2, y3) > r * r || GetSqDist(x1, y1, x3, y2) > r * r || GetSqDist(x1, y1, x3, y3) > r * r ? "YES" : "NO"); static double GetSqDist(double x1, double y1, double x2, double y2) { return Math.Pow(x1 - x2, 2) + Math.Pow(y1 - y2, 2); }
B: 互除法 - AtCoder Regular Contest 051 | AtCoder
ユークリッドの互除法でGCDを求める以下のコードがある。
int counter = 0; int gcd(int a, int b) { if (b == 0) return a; counter++; return gcd(b, a%b); }最終的なcounterの値がKとなる、aとbの組み合わせを答えよ。
フィボナッチ数列のn(k)とn(k-1)が解答になる。
ulong prev = 1; ulong cur = 1; for (int i = 0; i < k; i++) { var wk = cur; cur = prev + cur; prev = wk; } Console.WriteLine(string.Format("{0} {1}", cur, prev));
C: 掛け算 - AtCoder Regular Contest 051 | AtCoder
整数a1, a2, ...aNが与えられたとき、一番小さいものをA倍する操作をB回繰り返した結果を、昇順に並び変えて出力せよ。ただし結果は10^9+7でModする。
1 <= N <= 50
1 <= ai <= 10^9
1 <= A, B <= 10^9
最小値にどんどんAを掛けていくと、ある時点から、最小値*Aが常に最大値以上になる。そのため、その時点までは地道に計算し、さらに残り回数がNの倍数になるように調整すると、その順番と最終的な順番が等しくなる。
a.Sort(); if (A > 1) { // 最大と最小の差が十分小さくなり、かつ残り回数がNの倍数になるまでは手順通り行う while (a[0] * A < a[N - 1] && B > 0) { a[0] *= A; a.Sort(); B--; } var num = B % (UInt64)N; for (UInt64 i = 0; i < num; i++) { a[0] *= A; a.Sort(); B--; } //あとは順番は変わらないので、残った分を均等にModPow()する var pow = B / (UInt64)N; for (int i = 0; i < N; i++) { a[i] %= mod; //これがないとオーバーフロー a[i] *= ModPow(A, pow, mod); } } foreach (var ai in a) Console.WriteLine(ai % mod);
ARC050
A: 大文字と小文字 - AtCoder Regular Contest 050 | AtCoder
大文字と小文字が与えられたとき、同じアルファベットか判定せよ。
両方大文字に変換して比較。
Console.WriteLine(Console.ReadLine().Split().Select(s => s.ToUpper()).Distinct().Count() == 1 ? "Yes" : "No");
B: 花束 - AtCoder Regular Contest 050 | AtCoder
赤い花がR本、青い花がB本ある。x本の赤い花と1本の青い花、もしくは1本の赤い花とy本の青い花からなる花束を作るとき、作ることのできる花束の個数の最大値を求めよ。すべての花を使い切る必要はない。
1 <= R, B <= 10^18
2 <= x, y <= 10^19
k本の花束を作ることができるかで二分探索する。条件は
・赤い花と青い花がk本ずつ必要
・(赤い花の本数-k) / (x-1) + (青い花の本数-k) / (y-1) がk-1以上
となる。分母が-1になるのは、すでに各花束に1本ずつ割り当て済であるため。
Int64 left = 0; Int64 right = Math.Max(r, b); while (right - left > 1) { var m = (left + right) / 2; if(m <= r && m <= b && (r - m) / (x - 1) + (b - m) / (y - 1) >= m) left = m; else right = m; } Console.WriteLine(left);
条件がうまく出せずに苦しんだ。こういったときは、きれいな判定文は諦めて、さっさと泥臭く書いたほうが時間を無駄にせずに良さそうだ。
C: LCM 111 - AtCoder Regular Contest 050 | AtCoder
数字の1をA個並べた数xと、B個並べた数yがある。xとyの最小公倍数をMで割った余りを求めよ。
1 <= A, B <= 10^18
2 <= M <= 10^9
以下のサイトが分かりやすかった。
AtCoder Regular Contest 050 C - LCM 111 - pekempeyのブログ
1がA個並んだ数と1がB個並んだ数のGCDは、1がGCD(A,B)個並んだ数と等しくなる。LCMの公式により、
LCM(x, y) = x * y / 1がGCD(A,B)個並んだ数
になる。逆元をそのまま計算できないので、xまたはyどちらかに (1 / 1がGCD(A,B)個並んだ数)を掛けてから算出する。
LCM(x, y) = x * (y / 1がGCD(A,B)個並んだ数)
上記の掛け算の左右どちらも、111...または100100...といった形なので、等比数列の和で求めることができる。
なお、等比数列の和は、rを分母に使う普通の公式(S=a(1-r^n)/(1-r))は使えない。
static void Main(string[] args) { var str = Console.ReadLine().Split(); var a = Int64.Parse(str[0]); var b = Int64.Parse(str[1]); var mod = Int64.Parse(str[2]); var gcd = Gcd(a, b); var ret = ModPowSum(10, b, mod); ret *= ModPowSum(ModPow(10, gcd, mod), a / gcd, mod); Console.WriteLine(ret % mod); } static Int64 Lcm(Int64 a, Int64 b) { return (a * b) / Gcd(a, b); } static Int64 Gcd(Int64 a, Int64 b) { if (a < b) { var tmp = a; a = b; b = tmp; } if (b == 0) return a; var p = a > b ? a : b; return Gcd(b, p % b); } static public Int64 ModPow(Int64 x, Int64 n, Int64 mod) { Int64 ret = 1; while (n > 0) { if ((n & 1) == 1) ret = ret * x % mod; x = x * x % mod; n >>= 1; } return ret; } //等比数列の和を逆元なしで求める。O(Logn)。 public static Int64 ModPowSum(Int64 r, Int64 n, Int64 mod) { if (n == 0) return 0; //nが奇数:1 + r + ... + r^(n-1) = 1 + r(1 + r + ... + r^(n-2)) if (n % 2 == 1) return (ModPowSum(r, n - 1, mod) * r + 1) % mod; //nが偶数:1 + r + ... + r^(n-1) = ( 1 + r + ... + r^(n/2-1)) + r^(n/2) x ( 1 + r + ... + r^(n/2-1)) Int64 result = ModPowSum(r, n / 2, mod); return (result * ModPow(r, n / 2, mod) + result) % mod; }
自力で頑張ってみたが、等比数列の和でやはり躓いてしまった。上の関数はライブラリに入れておく。
ARC049
A: "強調" - AtCoder Regular Contest 049 | AtCoder
文字列Sと、整数A,B,C,Dが与えられる。SのA,B,C,D文字目の後ろに"を挿入した文字列を出力せよ。
そのまま実装する。LINQ便利。
Console.WriteLine(s.Insert(a, "\"").Insert(b + 1, "\"").Insert(c + 2, "\"").Insert(d + 3, "\""));
B: 高橋ノルム君 - AtCoder Regular Contest 049 | AtCoder
二次元座標にN人の人がいて、それぞれ位置(x,y)が与えられる。また、各人に定数ciが割り当てられており、その人がある点(X,Y)に移動するには、ci * Max(|xi - X|, |yi - Y|)の時間がかかる。全員が一点に集まるのに必要な、最小の時間を求めよ。
2 <= N <= 1000
- 10^5 <= xi, yi <= 10^5
1 <= ci <= 1000
「ある時間tで一点に集まることができるか」で二分探索。各人が時間tで行ける範囲の四角形がすべて重なればOK。
static void Main(string[] args) { /// 入力は省略 double l = 0; double r = 100000 * 1000 + 1; while (r - l > 0.0001) { var m = (l + r) / 2.0; if (Possible(m, x, y, c)) r = m; else l = m; } Console.WriteLine(r); } static bool Possible(double t, double[] x, double[] y, double[] c) { double x1 = -100001; double y1 = -100001; double x2 = 100001; double y2 = 100001; for (int i = 0; i < x.Length; i++) { if (x[i] - t / c[i] > x2) return false; if (y[i] - t / c[i] > y2) return false; if (x[i] + t / c[i] < x1) return false; if (y[i] + t / c[i] < y1) return false; x1 = Math.Max(x1, x[i] - t / c[i]); y1 = Math.Max(y1, y[i] - t / c[i]); x2 = Math.Min(x2, x[i] + t / c[i]); y2 = Math.Min(y2, y[i] + t / c[i]); } return true; }
C: ぬりまーす - AtCoder Regular Contest 049 | AtCoder
N頂点の有向グラフの頂点に着色していく。ただし、頂点間には次のタイプの制約がいくつかある。
タイプ1:ある頂点xに塗るとき、すでに頂点yに塗られていなければならない
タイプ2:ある頂点uに塗るとき、すてに頂点vに塗られていてはならない
タイプ1がA個、タイプ2がB個存在する。着色できる頂点の最大数を求めよ。
1 <= N <= 100
0 <= A <= 100
0 <= B <= 10
タイプ1のみで考えると、y→xの有効グラフについて、閉ループを構成するノードが着色できない。そして、着色不可のノードの下流もすべて着色できない。
タイプ2は
uに着色するとき:uに塗るときは、すでにvに塗られていなければならない
uに着色しないとき:uを着色不可とする
と言い換えることができ、これはタイプ1と同じ制限となる。
タイプ2は2^10パターンしかないので、全列挙して最大数を求めればよい。また、閉ループの検出は強連結成分分解を使うと効率が良い。
var ret = 0; var scc = new Scc(); //強連結成分分解のクラス(個人ライブラリ) for (int mask = 0; mask < 1 << typeBs.Count(); mask++) { scc.Init(n); foreach (var typeA in typeAs) scc.AddEdge(typeA.Item2, typeA.Item1); //y -> x のエッジを足す var notUse = new bool[n]; for (int i = 0; i < typeBs.Count(); i++) { var typeB = typeBs[i]; if ((mask >> i) % 2 == 1) scc.AddEdge(typeB.Item1, typeB.Item2); //u -> v のエッジを足す else notUse[typeB.Item1] = true; //uを使用禁止にする } scc.GetScc(); //強連結成分分解 //閉ループ内のノードは使用できない for (int sccIdx = 0; sccIdx < scc.SComponents.Count(); sccIdx++) { if (scc.SComponents[sccIdx].Count() > 1) //連結成分内のノード個数が1以上=閉ループ { foreach (var comp in scc.SComponents[sccIdx]) notUse[comp] = true; } } //使用禁止ノードの下流はすべて使用できない for (int j = 0; j < n; j++) for (int i = 0; i < n; i++) if (notUse[i]) foreach (var child in scc.E[i]) notUse[child] = true; ret = Math.Max(ret, notUse.Count(v => !v)); } Console.WriteLine(ret);
HackerRank Week of Code - 23 参加日記
281位/10162人。たぶん実際の参加者はこの半分くらいか。
難易度Easyの2問は省略する。
二次元平面上の(0,0)地点にいる人が、地点(x,y)にたどり着きたい。彼はおかしなマシンを持っていて、このマシンは①ある地点(x,y)から(x,y)+k(a,b)へ飛び、②さらにその地点(x,y)から(x,y)+n(a',b')で飛ぶことができる。ここで、(a',b')はベクトル(a,b)を反時計回り方向に直行させた、同じ長さのベクトルとする。a,b,x,yが与えられたとき、目的地に着くためのkとnを求めよ。
1<=x,y,z,b<=10^9
(0,0)→(a,b)→(x,y)が90度になる点を見つければよく、これは図にすれば簡単に求められる。
var k = ((a / b) * x + y) / (b / a + a / b); Console.WriteLine(k / a); //k Console.WriteLine(-(x - k) / b); //n
英小文字からなる文字列sと整数mが与えられる。このとき、
1 <= tの長さ <= m
s・t = t・s
を満たす文字列tがいくつあるか答えよ。
1 <= |s| <= 5 x 10^5
1 <= m <= 2 x 10^9
たとえば文字列sが
abcabc
なら、tになり得るのは
abc・abcabc
の2つになる。文字列sが
ababab
なら、tになり得るのは
ab・abab・ababab
の3つ。つまり、sの中で、abcのように繰り返される文字列の長さの最小値でmを割ればよい。
static void Main(string[] args) { var mod = 1000000007; var s = ReadLine().ToCharArray(); var m = Int64.Parse(Console.ReadLine()); var packetSize = GetPacketSize(s); Console.WriteLine((m / packetSize) % mod); } static Int64 GetPacketSize(char[] s) { for (Int64 i = 1; i <= s.Length / 2; i++) { if (Satisfies(i, s)) return i; } return s.Length; } static bool Satisfies(Int64 size, char[] s) { if (s.Length % size != 0) return false; for (Int64 i = size; i < s.Length; i += size) { for (Int64 j = 0; j < size; j++) { if (s[j] != s[i + j]) return false; } } return true; }
ノード数n(番号1..n、1が根)の木があり、ノード間の距離は1である。あるノードのスイッチがONのとき、そのサブノードもすべてスイッチがONになる。スイッチONのノードからは特別なパワーが発生し、その量は各ノードuに対し、(uからスイッチONノードへの距離)^2の合計になる。スイッチをONにするノードvと、ノードuが与えられたとき、uが受けるパワーの値を求めよ。ただし、クエリはq個連続して与えられる。
1<=n,q<=10^5
n,qが大きいので普通にやるとTLE。区間で処理する。
・オイラーツアーの結果をIN時間とOUT時間の配列にする
・すると、頂点vの子ノードは区間となる
・これをセグメント木で管理する
セグメント木は3つ用意し、セグメントに対して①加算した距離の合計、②加算した距離xセグメント長の合計、③加算した距離の二乗の合計、を保持するようにする。
①と②があれば③は計算で求められる。(詳しくはコード中にコメント)
これをまず、ノード1からの距離で初期化する。そして、ノード1から子ノードを再帰的に処理していくことで、すべてのノードからの情報に更新することができる。
//ノード番号は0-indexedで持つ const int maxn = 500042; static List<int>[] g; //グラフ情報 (親 => 子) static int[] que; //クエリi番目のノードv static List<int>[] lst; //ノードuに関係するクエリ番号 static int[] _in; //DFS時の各ノードのIN時間 static int[] _out; //DFS時の各ノードのOUT時間 //セグメント木の接点の値(3種類) static Int64[] _add; static Int64[] _sum1; static Int64[] _sum2; static Int64[] ans; static void Main(string[] args) { var n = Int32.Parse(Console.ReadLine()); //変数の初期化 g = Enumerable.Range(0, maxn).Select(v => new List<int>()).ToArray(); _in = new int[maxn]; _out = new int[maxn]; _add = new Int64[4 * maxn]; _sum1 = new Int64[4 * maxn]; _sum2 = new Int64[4 * maxn]; ans = new Int64[maxn]; //ノード情報を取得 var nodeInfo = ReadLine().Split().Select(v => Int32.Parse(v)).ToArray(); for (int i = 1; i < n; i++) { int p = nodeInfo[i - 1]; g[p - 1].Add(i); } //ルートからの距離で、_in[]・_out[]・_add[]・_sum1[]・_sum2[]を作成する dfs1(); //クエリ情報を取得 var q = Int32.Parse(Console.ReadLine()); que = new int[q]; lst = Enumerable.Range(0, maxn).Select(v => new List<int>()).ToArray(); for(int i = 0; i < q; i++) { var str = Console.ReadLine().Split(); var u = Int32.Parse(str[0]) - 1; var v = Int32.Parse(str[1]) - 1; que[i] = v; lst[u].Add(i); } // uごとに解を作成 dfs2(); for (int i = 0; i < q; i++) Console.WriteLine(ans[i]); } static int t = 0; static void dfs1(int v = 0, int h = 0) { _in[v] = t++; upd(_in[v], _in[v] + 1, h); foreach(var u in g[v]) dfs1(u, h + 1); _out[v] = t; } // 区間[a, b)をvalでインクリメントする // vはセグメント木の接点番号で、接点は[l,r)に対応づいている // _add[v]: 接点vの区間に対して加算されたvalの合計 // _sum1[v]: 接点vの区間に対して加算されたvalの総合計(_add x 区間の長さ) // _sum2[v]: 接点vの区間に対して加算されたval^2の合計 static void upd(int a, int b, int val, int v = 1, int l = 0, int r = maxn) { if (a <= l && r <= b) { _add[v] += val; _sum2[v] += 2 * _sum1[v] * val + (r - l) * val * val; //例:(a+k)^2 + (b+k)^2 = (a^2 + b^2) + 2 (a+b) k + 2 k^2 _sum1[v] += (r - l) * val; return; } if (r <= a || b <= l) return; int m = (l + r) / 2; upd(a, b, val, 2 * v, l, m); upd(a, b, val, 2 * v + 1, m, r); _sum1[v] = _sum1[2 * v] + _sum1[2 * v + 1]; _sum2[v] = _sum2[2 * v] + _sum2[2 * v + 1]; _sum2[v] += 2 * _sum1[v] * _add[v] + (r - l) * _add[v] * _add[v]; _sum1[v] += (r - l) * _add[v]; } // ノードuに関連する解を求める // 全ノード分を再帰的に static void dfs2(int u = 0) { // 自分以下のサブノードを-1、それ以外を+1すると自分からの距離になる // ひとつひとつやると遅いので、再帰的に全ノードでやってしまう foreach(var node in g[u]) { upd(0, maxn, 1); upd(_in[node], _out[node], -2); dfs2(node); upd(0, maxn, -1); upd(_in[node], _out[node], 2); } // ノードuに関連する解を保持 foreach (var q in lst[u]) { // vのIN時間・OUT時間から、その区間までの距離^2の合計を求める ans[q] = get(_in[que[q]], _out[que[q]]).Item1; } } // 区間[a,b)の結果を返す // Item1: 値の2乗の合計 // Item2: 値の合計 static Tuple<Int64, Int64> get(int a, int b, int v = 1, int l = 0, int r = maxn) { if(a <= l && r <= b) return new Tuple<Int64, Int64>(_sum2[v], _sum1[v]); if(r <= a || b <= l) return new Tuple<Int64, Int64>(0, 0); int m = (l + r) / 2; var A = get(a, b, 2 * v, l, m); var B = get(a, b, 2 * v + 1, m, r); var C = new Tuple<Int64, Int64>(A.Item1 + B.Item1, A.Item2 + B.Item2); //区間[a,b)部を足す //Cだけだと、[a, m)合計+[m, b)合計なので足りない int inter = Math.Min(r, b) - Math.Max(l, a); var r_first = C.Item1 + 2 * C.Item2 * _add[v] + inter * _add[v] * _add[v]; var r_second = C.Item2 + inter * _add[v]; return new Tuple<Int64, Int64>(r_first, r_second); }
セグメント木を利用する問題は初めてだった。じっくりEditorialのコードを読んで何とか理解できた。
Topcoder SRM696 参加日記
0完でレート微増だった。Div1のEasyはなぜこんなに難易度が高いのだろう(解けてない人が多すぎる)。
頂点数50、辺の数が1~20の無向グラフがある。初期状態では、いずれの頂点も着色されていない。着色には、両端が着色されている辺の数と等しいコストがかかる。すべての頂点を着色するときの最小コストを算出せよ。
辺の数が20と小さいので、辺の情報でbitDPを行う。
dp[mask]:辺集合maskを作るための最小コスト
とし、maskはビット1の辺がコストに関係しないもの(両端が着色されていな辺)と定義する。
そして、問題とは逆に、すべてが着色された状態(mask=0、コスト=0)から、色を消すごとにコストを追加していくとうまくいく。
public int countfee(int[] x, int[] y) { var m = x.Length; //各頂点につながるエッジの情報(頂点番号->マスク) var v_mask = new int[50]; for (int i = 0; i < m; i++) { v_mask[x[i]] |= 1 << i; v_mask[y[i]] |= 1 << i; } //無効なエッジの集合を作るための最小コスト(無効なエッジ:コストに絡まないもの) var dp = new int[(1 << m)]; for (int i = 0; i < (1 << m); i++) dp[i] = Int32.MaxValue / 3; //すべてのエッジが有効な状態(全頂点がPaintされている状態)から色を消していく dp[0] = 0; for (int mask = 0; mask < 1 << m; mask++) { //それぞれの頂点の色を消してみる for (int v = 0; v < 50; v++) { var mask_erased = mask | v_mask[v]; //色を消した頂点に関連するエッジすべて dp[mask_erased] = Math.Min(dp[mask_erased], dp[mask] + m - BitCount(mask)); } } return dp[(1 << m) - 1]; } static int BitCount(int i) { i = i - ((i >> 1) & 0x55555555); i = (i & 0x33333333) + ((i >> 2) & 0x33333333); return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24; }
HackerRank Week of Code - 22 参加日記
457位/12356人。Mediumを1つ落としたのが痛い。いつも数学がネックだ・・・。
n人のゲストとm枚のクッキーがある。ゲスト全員に同じ枚数を配るためには、あと何枚クッキーを焼けばよいか。
クッキーがすでに足りているか、足りない場合はゲストの人数で割り切れるかで場合分けする。
if (m <= n) Console.WriteLine(n - m); else if (m % n == 0) Console.WriteLine(0); else Console.WriteLine((m / n + 1) * n - m);
N本の棒aiが与えられる。この棒すべてを使って非退化な多角形を作るには、最少で何本の棒を折る必要があるか。折れた棒は両方使うものとする。
1 <= N <= 50
1 <= ai <= 100
「非退化」というのは重なった辺も、長さゼロの辺も存在しないという意味で、要するに普通の多角形のことらしい。
1本しかないときは、当然2回折らないと多角形にならない。
2本のときは、同じ長さなら2回、違う長さなら1回折る必要がある。
3本以上あるなら、
最長の辺の長さ > それ以外の辺の長さ合計
に合致したら一本も折らなくてよい。それ以外のときは、最長のものを1回折る必要がある。
if (a.Count() == 1) { Console.WriteLine(2); } else if (a.Count() == 2) { if (a[0] == a[1]) Console.WriteLine(2); else Console.WriteLine(1); } else { if (a[0] < a.Sum() - a[0]) Console.WriteLine(0); else Console.WriteLine(1); }
理屈は簡単だが、棒が1本からという条件を見逃すとWAになってしまう。
2つの整数の集合があり、次のオペレーションが可能である。
1、XとYから1つずつを選ぶ()
2,から1引き、 に1足す
XとYが等しくなる最少のオペレーション回数を求めよ。不可能な場合は-1を返すこと。
XとYの合計が異なるときは不可能。それ以外であれば、両方ともソートして1つずつオペレーションしていけば良い。
if (x.Sum() != y.Sum()) { Console.WriteLine(-1); return; } Int64 diff = 0; x.Sort(); y.Sort(); for (int i = 0; i < n; i++) { diff += Math.Abs(x[i] - y[i]); } Console.WriteLine(diff / 2);
整数の数列が次を満足するとき、この数列はNiceであるとする
・
・ (kがmを割り切るすべてのk,mのペアについて)
一部が-1になっている整数の数列nが与えられる。-1に任意の数字を入れたとき、この数列がNiceになる組み合わせ数を求めよ。
まず、a[i]の添え字がa[p*q]と素因数分解できるものは無視することができる(中国の剰余定理によりa[p]とa[q]が決まっていれば、a[p*q]が一意に求まるため)。
そして、各素数のべき乗番目
a[p], a[p^2], a[p^3] ... (p^x < n)
について、値が-1ならp通りのパターンがある。
たとえば、p=3のとき
a[3]: -1 → あり得る値は { 0, 1, 2 }
a[9]: -1 → あり得る値は { 0, 1, 2, 3, 4, 5, 6, 7, 8 }
となるが、a[3]でどの値が選ばれたとしても、a[9]で候補になる数は9/3=3個になる。
static void Main(string[] args) { Console.SetOut(new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false }); var n = Int32.Parse(Console.ReadLine()); var a = ReadLine().Split().Select(s => Int32.Parse(s)).ToList(); a.Insert(0, 0); //それぞれのkの因数すべて var facts = Enumerable.Range(0, n + 1).Select(v => new List<int>()).ToList(); for (var k = 2; k <= n; k++) { Int64 kp = k; while (kp <= n) { facts[(int)kp].Add(k); kp += k; } } //すでに値がある場合に、Niceに違反する因数がないかチェック for (var k = n; k > 0; k--) { if (a[k] == -1) continue; foreach (var fact in facts[k]) { if (a[fact] != -1 && a[fact] != a[k] % fact) { Console.WriteLine(0); Console.Out.Flush(); return; } a[fact] = a[k] % fact; } } //kが(素数^p)で表せるならその素数を取得 var basePrimes = new int[n + 1]; for (var k = 2; k <= n; k++) { if (facts[k].Count() == 1) { Int64 kp = k; while (kp <= n) { basePrimes[kp] = k; kp *= k; } } } //a[k]が-1かつkが(素数^p)で表せるなら、k通りの組み合わせがある Int64 ret = 1; for (var k = 2; k <= n; k++) { if (a[k] == -1 && basePrimes[k] != 0) { ret *= (Int64)basePrimes[k]; ret %= 1000000007; } } Console.WriteLine(ret); Console.Out.Flush(); }
要素数nの集合がある。Uの部分集合すべてに値0が代入されている。
この時、次の3タイプのクエリが渡される。
1. 1 x S:集合Sの部分集合すべてに値xを代入する
2. 2 x S:集合Sの部分集合すべての値についてxとXORをとる
3. 3 s:集合Sの値を出力する
クエリが連続で与えられるので、出力値を求めよ。
1 <= n <= 16
1 <= m(クエリ数) <= 10^5
0 <= x <= 2^30 - 1
最後に代入された時間と値、そしてそこからのXOR合算を効率よく求める必要がある。
各クエリごとのループ回数を少なくするため、下位8ビットと上位8ビットに平方分割する。クエリ1・2では、下位8ビットのサブセットすべてについて、以下の情報を保持していく。
var set_times = new int[1 << 8, 1 << 8]; //最後に代入した時間 var set_values = new int[1 << 8, 1 << 8]; //代入された値 var xor_time = new List<ComparablePair<int, int>>[1 << 8, 1 << 8]; // XORした時間と、そこまでのXOR合算
クエリ3では、①該当ビットに最後に代入された値を取得し、②その時間をもとにそこからのXOR合算を算出する。
たとえば、
1:XOR、2:代入、3:XOR、4:代入、5:代入、6:XOR、7:XOR
だったとしたら、最終的な値は5で代入された値へ、3までのXOR合算と7までのXOR合算をXORしたものになる。この、最後の代入の直前のXORは、時間で二分探索すれば求められる。
①②いずれも、上位8ビットのスーパーセットすべて+下位8ビットのパターンで行えばよい。
static void Main(string[] args) { Console.SetOut(new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false }); var str = Console.ReadLine().Split(); var n = Int32.Parse(str[0]); var m = Int32.Parse(str[1]); var set_times = new int[1 << 8, 1 << 8]; //last updated time to [H, L] var set_values = new int[1 << 8, 1 << 8]; //[H, L] => value of mask { all subsets of H } + L var xor_time = new List<ComparablePair<int, int>>[1 << 8, 1 << 8]; // time of xor -> xor value of mask [H, L] for (int i = 0; i < 1 << 8; i++) { for (int j = 0; j < 1 << 8; j++) { set_times[i, j] = -1; xor_time[i, j] = new List<ComparablePair<int, int>>() { new ComparablePair<int, int>(-1, 0) }; } } for (int i = 0; i < m; i++) { str = Console.ReadLine().Split(); var bit = 0; for (int j = 0; j < n; j++) { bit *= 2; if (str[str[0] == "1" || str[0] == "2" ? 2 : 1][j] == '1') bit += 1; } var top = bit >> 8; var bottom = bit & 0xFF; //assign if (str[0] == "1") { var val = Int32.Parse(str[1]); var sub = bottom; do { set_values[top, sub] = val; set_times[top, sub] = i; sub = (sub - 1) & bottom; } while (sub != bottom); } //xor if (str[0] == "2") { var val = Int32.Parse(str[1]); var sub = bottom; do { xor_time[top, sub].Add(new ComparablePair<int, int>(i, val ^ xor_time[top, sub].Last().Item2)); sub = (sub - 1) & bottom; } while (sub != bottom); } //print if (str[0] == "3") { //find the last updated time and its time var val = 0; var lastUpdated = -1; //iterate supersets of top var comp = ~top & 0xFF; for (int sub = comp; ; sub = (sub - 1) & comp) { int super_top = top | sub; //superset of top if (set_times[super_top, bottom] > lastUpdated) { lastUpdated = set_times[super_top, bottom]; val = set_values[super_top, bottom]; } if (sub == 0) break; } //apply xors from the last updated time comp = ~top & 0xFF; for (int sub = comp; ; sub = (sub - 1) & comp) { int super_top = top | sub; //superset of top var tgt_xors = xor_time[super_top, bottom]; var right_xor = tgt_xors.Last().Item2; var left_xor = GetLastXor_BeforeLastUpdate(tgt_xors, lastUpdated).Item2; //get the last xor-ed value before the update time using binary search // getting xors from i to j: xor(0..j) ^ xor(0..i-1) val ^= (left_xor ^ right_xor); if (sub == 0) break; } Console.WriteLine(val); } } Console.Out.Flush(); } //return [upper_bound() - 1], xors are sorted by item1 static ComparablePair<int, int> GetLastXor_BeforeLastUpdate(List<ComparablePair<int, int>> xors, int time) { var lb = -1; var ub = xors.Count(); while (ub - lb > 1) { var mid = (lb + ub) / 2; if (xors[mid].Item1 <= time) { lb = mid; } else { ub = mid; } } return xors[lb]; }
AGC003の参加日記
2完で416位/700人くらい。AtCoderのコンテストは問題文が分かりやすくて良い(日本語だからというだけじゃなく)。
二次元平面上のある点から、1ターンずつ東西南北いずれかに正の距離移動する。ターンごとの方角が与えられたとき、元の位置に戻ることができるか。
東西と南北それぞれについて、たとえば東だけなどある方向に行きっぱなしになっていなければ、元の位置に戻ることができる。
if (((str.Count(c => c == 'E') == 0 && str.Count(c => c == 'W') == 0) || (str.Count(c => c == 'E') > 0 && str.Count(c => c == 'W') > 0)) && ((str.Count(c => c == 'N') == 0 && str.Count(c => c == 'S') == 0) || (str.Count(c => c == 'N') > 0 && str.Count(c => c == 'S') > 0)) ) { Console.WriteLine("Yes"); } else { Console.WriteLine("No"); }
1からNまでの整数が書かれたカードが、それぞれAi枚ある。2枚のカードについて、整数の差の絶対値が1以下ならペアを作ることができる。作ることのできるペアの最大数を求めよ。
連続したカードごとのグループを作り、グループ内のカード枚数/2を合計すればよい。
Int64 ret = 0; Int64 sum = 0; for (int i = 0; i < a.Count(); i++) { if (a[i] == 0) { ret += sum / 2; sum = 0; } else sum += a[i]; } ret += sum / 2; Console.WriteLine(ret);
長さNの数列Aに以下の操作を行い、昇順にソートする。
・操作1:連続する2つの要素の順番を反転
・操作2:連続する3つの要素の順番を反転
最少の操作1の回数を答えよ。
1 <= N <= 10^5
0 <= Ai <= 10^0 (整数のみ)
操作2は何回行ってもも構わないので、奇数位置にある値はコストなしで動かすことができる。よって、偶数位置にあるものを、奇数位置へ動かす回数が答えとなる。
(同じ回数だけ、奇数位置から偶数位置に動かすものがある)
var n = Int32.Parse(Console.ReadLine()); var a = new List<Int64>(); var dictIdx = new Dictionary<Int64, int>(); for (int i = 0; i < n; i++) { a.Add(Int64.Parse(Console.ReadLine())); dictIdx.Add(a[i], i); } var wk = a.OrderBy(v => v).ToList(); var indices = new Int64[n]; for (int i = 0; i < wk.Count; i++) { indices[dictIdx[wk[i]]] = i; } Int64 ret = 0; for (int i = 0; i < a.Count(); i++) { if (i % 2 == 0 && indices[i] % 2 == 1) ret++; } Console.WriteLine(ret);
Booking.com Back End CodeSprintの参加日記
全完で暫定85位/3075人。Tシャツ貰えるのかな?
Jhonはn個の町、Ziziはm個の町を訪れたい。そのうちc個は重なっている。最後に訪れる都市が決まっているとして、二人の希望の都市すべてを訪れる順番は何通りあるか。
訪れる町の合計n+m-cをもとに計算する。
var num = n + m - c - 1; UInt64 ret = 1; while (num > 0) { ret *= num; num--; } Console.WriteLine(ret);
グループにn人のメンバーがいて、それぞれm個の事柄に興味を持っている。さらに、y個の都市があり、それぞれがz個の満足させられる興味内容を持つ。メンバーは、1個以上の興味内容が満たされれば満足する。なるべく多くのメンバーを満足させるには、どの2都市を選べばよいか。アルファベット順で答えよ。ただし、解が複数になるときは、もっとも距離の近い2都市を答えること。
0 < n, m, y, z <= 250
都市数が250と少ないので、すべての組み合わせを試せば求められる。
if (cities.Count() == 1) { Console.WriteLine(cities[0].Name); return; } var mi = -1; var mj = -1; var maxScore = -1; var minDist = double.MaxValue; for (int i = 0; i < y - 1; i++) { for (int j = i + 1; j < y; j++) { var score = GetScore(cities[i], cities[j], passions); var dist = GetDist(cities[i], cities[j]); if (score > maxScore || (score == maxScore && dist < minDist)) { mi = i; mj = j; maxScore = score; minDist = dist; } } } foreach (var c in new List<City>() { cities[mi], cities[mj] }.OrderBy(c => c.Name)) { Console.Write(c.Name + " "); } Console.WriteLine();
複数の都市について、合計m個のレビューが付いている。各レビューには、レビュアーID・日時・レビュー本文がある。それぞれのレビューは以下のようにスコアが付けられる。
・日付が2016/6/15から2016/7/15なら20点、それ以外なら10点
・本文が100文字以上なら20点、それ以外なら10点
ここで、n個の興味内容が与えられたとき、それぞれについて最も高スコアのレビューを書いたレビュアーのIDを出力せよ
1 <= n <= 100
1 <= m <= 3250
0 <= r(レビュアーID) <= 100
レビュー本文は5000字以内
地道に統計を取るだけだが、少し工夫をしないとTLEになる。
レビュー本文が大きいので標準のConsole.ReadLine()が使えなかったり、日付がUnixTimeなので変換が必要だったり、入力文字列に無駄な空白があったりと、アルゴリズム以外のところが面倒だった。実際の仕事でのコーディングに近いのかもしれないが、プログラミングコンテストとしては面白くなかった。
class Program { static void Main(string[] args) { var str = Console.ReadLine().Split(); var n = Int32.Parse(str[0]); var m = Int32.Parse(str[1]); var passions = new List<string>(); for (int i = 0; i < n; i++) { passions.Add(Console.ReadLine().ToUpper()); } Dictionary<int, Reviewer> reviewers = new Dictionary<int, Reviewer>(); for (int i = 0; i < m; i++) { str = Console.ReadLine().Split().Where(s => !string.IsNullOrEmpty(s)).ToArray(); //テストケースに変な空白が入っている...問題文に明記してないのはひどい var id = Int32.Parse(str[0]); var timeStamp = str[1]; var body = ReadLine(); var review = new Review() { TimeStamp = timeStamp, Body = body.ToUpper() }; if (!reviewers.ContainsKey(id)) reviewers.Add(id, new Reviewer() { Id = id }); reviewers[id].Reviews.Add(review); } foreach (var reviewer in reviewers) reviewer.Value.CalcScoreByPassion(passions); var reviewerList = reviewers.Select(r => r.Value).ToList(); foreach (var passion in passions) { var best = reviewerList.OrderByDescending(r => r.GetScoreByPassion(passion)).ThenBy(r => r.Id).First(); Console.WriteLine(best.GetScoreByPassion(passion) == -1 ? "-1" : best.Id.ToString()); } } ///独自ReadLine()は省略 } class Reviewer { public int Id; public List<Review> Reviews = new List<Review>(); public Dictionary<string, int> ScoreByPassion = new Dictionary<string,int>(); public void CalcScoreByPassion(List<string> passions) { foreach (var passion in passions) { var score = Reviews.Sum(r => r.GetScoreByPassion(passion)); if (score > 0) ScoreByPassion.Add(passion, score); } } public int GetScoreByPassion(string passion) { return ScoreByPassion.ContainsKey(passion) ? ScoreByPassion[passion] : -1; } } class Review { public string TimeStamp; public string Body; bool? _isInRange; bool IsInRange { get { if (_isInRange == null) { try { //UnixTimeを変換して比較… var timeStamp_Datetime = new DateTime(1970, 1, 1, 0, 0, 0, 0, System.DateTimeKind.Utc); timeStamp_Datetime = timeStamp_Datetime.AddSeconds(UInt64.Parse(TimeStamp)); if (new DateTime(2016, 6, 15) <= timeStamp_Datetime && timeStamp_Datetime <= new DateTime(2016, 7, 15)) _isInRange = true; else _isInRange = false; } catch { _isInRange = false; } } return (bool)_isInRange; } } Dictionary<string, int> ScoreByPassion = new Dictionary<string, int>(); public int GetScoreByPassion(string passion) { if (ScoreByPassion.ContainsKey(passion)) return ScoreByPassion[passion]; if (!Body.Contains(passion)) { ScoreByPassion.Add(passion, 0); return 0; } var ret = Body.Length >= 100 ? 20 : 10; ret += (IsInRange ? 20 : 10); ScoreByPassion.Add(passion, ret); return ret; } }
n人が遠足で訪れたイベントの順番を思い出したとする。ただし、すべてのイベントを思い出しているとは限らない。このとき、順番に矛盾があるかどうか答えよ。
たとえば、遠足に行ったのが2人だとして、思い出した内容が次のときは矛盾がない。
1. Eiffel tower, Olympus, Disneyland
2. Eiffel tower, Oktoberfest, Disneyland
しかし以下のような場合は矛盾している。
1. Disneyland, Eiffel tower
2. Eiffel tower, Disneyland
1 <= x(遠足の回数) <= 20
1 <= n <= 200
イベントの個数は1000以下、イベント名は50文字以下
前のイベント->後のイベントをエッジとする有向グラフを作成し、トポロジカルソートを試みればよい。ソート不可なら矛盾ありになる。前問と違ってとてもコンテストらしい問題。
var x = Int32.Parse(Console.ReadLine()); for (int i = 0; i < x; i++) { var n = Int32.Parse(Console.ReadLine()); var idx = 0; Dictionary<string, int> attToIdIdx = new Dictionary<string, int>(); var edge = new List<List<int>>(); for (int j = 0; j < 1001; j++) edge.Add(new List<int>()); for (int j = 0; j < n; j++) { var str = Console.ReadLine().Split(',').Select(s => s.Trim()).ToArray(); for (int k = 0; k < str.Length - 1; k++) { if (!attToIdIdx.ContainsKey(str[k])) { attToIdIdx.Add(str[k], idx); idx++; } if (!attToIdIdx.ContainsKey(str[k + 1])) { attToIdIdx.Add(str[k + 1], idx); idx++; } edge[attToIdIdx[str[k]]].Add(attToIdIdx[str[k + 1]]); } } var ok = TopologicalSort(Enumerable.Range(1, idx).ToList(), edge) != null; if (ok) Console.WriteLine("ORDER EXISTS"); else Console.WriteLine("ORDER VIOLATION"); }
TopologicalSort()は個人ライブラリのもの。
n人のメンバーと、n枚のチケットがある。メンバーはそれぞれ、いくつかの興味のある事柄を持っている。チケットはそれぞれ、満足させられる興味事項を持っている。メンバーは、最低1つの興味が満たされれば満足する。なるべく多くのメンバーを満足させるようにチケットを割り当てたとき、満足したメンバーは何人か。
メンバーとチケットで二部マッチングを行えばよい。
var n = Int32.Parse(Console.ReadLine()); var rightSides = new List<HashSet<string>>(); for (int i = 0; i < n; i++) { var str = Console.ReadLine().Split(); rightSides.Add(new HashSet<string>(str.Skip(2))); } var leftSides = new List<HashSet<string>>(); for (int i = 0; i < n; i++) { var str = Console.ReadLine().Split(); leftSides.Add(new HashSet<string>(str.Skip(1))); } var biMatching = new BipartiteMatching(); for (int l = 0; l < leftSides.Count(); l++) { var left = leftSides[l]; for (int r = 0; r < rightSides.Count(); r++) { var right = rightSides[r]; if (left.Any(lv => right.Contains(lv))) { biMatching.AddPair(l, r); } } } Console.WriteLine(biMatching.GetMaxMatchingNum());
BipertiteMatchingは個人ライブラリのもの。
n個の都市がe本の双方向の道でつながれている。それぞれの道は通過するのにh時間かかる。また、都市には、滞在しなければならない時間viが設定されている。いま都市Bevagnaにいるとき、時間内になるべく多くの都市を訪れたい。その順番を答えよ。ただし、以下の制約がある。
・現在は月曜の午前8時である
・0時から午前8時までは睡眠をとる必要がある
・睡眠をとるのは必ず都市でなければならない
・睡眠中は滞在時間にカウントされない
・滞在時間を超えないと、その都市を離れることはできない
・期限は日曜の午前8時
1 <= n <= 20
1 <= e <= 20
1 <= vi <= 1000
1 <= h <= 1000
現在地・経過時間・訪問済み都市情報を保持してDijkstraすればよい。それに加え、経路復元が必要なので、親ノードも情報も持つ。
static void Main(string[] args) { ///入力は省略 //dijkstra Node ret = null; var que = new PriorityQueue<Node>(); que.Push(new Node() { Current = 0, Time = 8, Visited = 1 }); while (que.Count() > 0) { var node = que.Pop(); if (ret == null || (ret.VisitedNum < node.VisitedNum)) ret = node; foreach (var edge in graph[node.Current]) { var nextNode = GetNextNode(edge, node, c); if (nextNode == null) continue; que.Push(nextNode); } } ///出力は省略(retを親までたどって逆に出力) } static Node GetNextNode(Edge edge, Node curretNode, Dictionary<int, int> cityNumToCost) { //already visited if ((curretNode.Visited & (1 << edge.To)) != 0) return null; var ret = new Node() { Time = curretNode.Time, Current = edge.To, Visited = curretNode.Visited | (1 << edge.To), VisitedNum = curretNode.VisitedNum + 1, Parent = curretNode, }; //update time var day = curretNode.Time >> 8; var hour = curretNode.Time & 0xFF; //add traveling time if (24 - hour >= edge.Cost) { hour += edge.Cost; } else { day++; hour = 8; if (24 - hour >= edge.Cost) { hour += edge.Cost; } else { return null; } } if (hour == 24) { hour = 8; day++; } //add staying time var stayTime = cityNumToCost[edge.To]; while (stayTime > 0) { var diffTime = Math.Min(24 - hour, stayTime); hour += diffTime; stayTime -= diffTime; if (hour == 24) { hour = 8; day++; } } if (day > 5 && hour != 8) return null; ret.Time = (day << 8) | (hour & 0xFF); return ret; } class Node : IComparable { public int Time; public int Current; public int Visited; public int VisitedNum; public Node Parent; public int CompareTo(object obj) { var tgt = obj as Node; if (tgt.Visited == Visited) return Time.CompareTo(tgt.Time); return VisitedNum.CompareTo(tgt.VisitedNum); } } class Edge { public int Cost; public int To; }
Morgan Stanley Codeathon 2016の参加日記
3完1部分点で暫定192位/3601人。数学が分からなくて苦しんだ。
ある銘柄のN日分の株価が与えられる。ちょうど利益Diを得るためには、いつ買っていつ売ればよいか。ただし、株を保持する日数は最小化したい。さらに、複数の解がある場合は、もっとも早く利益を得られる組み合わせを答えよ。
1 <= N <= 2x10^5
1 <= D <= 10
1 <= Ni, Di <= 10^8
簡単そうに見えるが、2つの制限を満足させるのに手間取った。後ろからループし、その日に買った場合に条件を満たせるかを判定していけばよい。
N日分の株価情報(最大2x10^5個)が1行で与えられるため、標準のConsole.ReadLine()だと入力バッファが足りないと思われる。
class Program { static void Main(string[] args) { var str = Console.ReadLine().Split(); var n = Int32.Parse(str[0]); var d = Int32.Parse(str[1]); var price = ReadLine().Split().Select(s => long.Parse(s)).ToArray(); for (int i = 0; i < d; i++) { var profit = long.Parse(Console.ReadLine()); int left = -1; int right = Int32.MaxValue; if (Get(profit, ref left, ref right, price)) Console.WriteLine(string.Format("{0} {1}", left + 1, right + 1)); else Console.WriteLine("-1"); } } static bool Get(long profit, ref int left, ref int right, long[] price) { var dict = new Dictionary<long, int>(); for (int i = price.Length - 1; i >= 0; i--) { if (dict.ContainsKey(price[i] + profit)) { var l = i; var r = dict[price[i] + profit]; if (left == -1 || right - left >= r - l) { right = r; left = l; } } if (!dict.ContainsKey(price[i])) dict.Add(price[i], i); else dict[price[i]] = i; } return left != -1; } static string ReadLine() { StringBuilder sb = new StringBuilder(); while (true) { int ch = Console.Read(); if (ch == -1) break; if (ch == '\r' || ch == '\n') { if (ch == '\r') Console.Read(); return sb.ToString(); } sb.Append((char)ch); } if (sb.Length > 0) return sb.ToString(); return null; } }
整数Nが与えられたとき、N^2を割り切るがNを割り切らない数で、N未満のものの個数を答えよ。
1 <= N <= 10^12
整数Nの素因数分解をとおく。なので、の因数は個とわかる。
このうちN未満のものは個となる。これと、の因数数との差が答えとなる。
static void Main(string[] args) { var n = UInt64.Parse(Console.ReadLine()); var factors = GetFactors(n); UInt64 ret1 = 1; foreach (var factor in factors) ret1 *= (2 * factor.Value + 1); ret1--; ret1 /= 2; UInt64 ret2 = 1; foreach (var factor in factors) ret2 *= (factor.Value + 1); ret2--; Console.WriteLine(ret1 - ret2); } public static Dictionary<UInt64, UInt64> GetFactors(UInt64 n) { var ret = new Dictionary<UInt64, UInt64>(); while (n % 2 == 0) { if (!ret.ContainsKey(2)) ret.Add(2, 0); ret[2]++; n = n / 2; } for (UInt64 i = 3; i <= Math.Sqrt(n); i = i + 2) { while (n % i == 0) { if (!ret.ContainsKey(i)) ret.Add(i, 0); ret[i]++; n = n / i; } } if (n > 2) { if (!ret.ContainsKey(n)) ret.Add(n, 0); ret[n]++; } return ret; }
Samantha and Portfolio Management
N個のポートフォリオと、それぞれの収益率riが与えられる。また、i番目のポートフォリオの収益の分散がであるとする。各ポートフォリオに重みづけwiを付けたとき、全体の収益分散を最小化したい。このときの期待収益と分散を答えよ。
0 <= wi <= 1
分散を最小化するのだから、収益は無視して重みづけwiが求められる。ポートフォリオそれぞれの分散がだとする。このとき、重みづけをのようにすれば、最終的な分散がになって最小化する。あとは、この重みづけを使って利益を求めればよい。
static void Main(string[] args) { var n = Int32.Parse(Console.ReadLine()); var r = new List<int>(); for (int i = 0; i < n; i++) r.Add(Int32.Parse(Console.ReadLine())); var w = GetW(r); var v = new Tuple<int, int>(1, Enumerable.Range(1, r.Count()).Sum()); var e = GetE(r, w); v = Modify(v); e = Modify(e); Console.WriteLine(string.Format("{0} {1}", e.Item1, e.Item2)); Console.WriteLine(string.Format("{0} {1}", v.Item1, v.Item2)); } static Tuple<int, int> Modify(Tuple<int, int> value) { var gcd = Gcd(value.Item1, value.Item2); return new Tuple<int, int>(value.Item1 / gcd, value.Item2 / gcd); } static List<Tuple<int, int>> GetW(List<int> r) { var b = Enumerable.Range(1, r.Count()).Sum(); var ret = new List<Tuple<int, int>>(); for (int i = 0; i < r.Count(); i++) { ret.Add(new Tuple<int, int>(i + 1, b)); } return ret; } static Tuple<int, int> GetE(List<int> r, List<Tuple<int, int>> e) { var t = 0; for (int i = 0; i < r.Count(); i++) { t += r[i] * e[i].Item1; } return new Tuple<int, int>(t, e[0].Item2); } static int Gcd(int a, int b) { if (a < b) { var tmp = a; a = b; b = tmp; } if (b == 0) return a; var p = a > b ? a : b; return Gcd(b, p % b); }
1~Nの町があり、いま町1に滞在している。町の間には、M本の普通の道とK本の特別な道がある(いずれも双方向)。それぞれの道には、通過に必要な時間zが与えられる。すべての特別な道を通って町Nまで行くときの最短時間を求めよ。
1 <= N <= 1000
1 <= M <= 2000
1 <= K <= 10
1 <= x, y <= N, x != y
1 <= z <= 1000
次のようなノードクラスを使ってDijkstraで最短経路を求めればよい。Kは最大で10本しかないのでビットで情報を持つことができる。
public class Node : IComparable { public int Current; //今いる町 public int Time; //今までの経過時間 public int PassedK; //通った特別な道情報 public int PassedKNum; //通った特別な道の本数 public int CompareTo(object obj) { var tgt = obj as Node; if (PassedKNum == tgt.PassedKNum) return Time.CompareTo(tgt.Time); return PassedKNum.CompareTo(tgt.PassedKNum); } }
Dikstraの部分。典型題のためかDifficultの割には正答率が高かった。
var que = new PriorityQueue<Node>(); que.Push(new Node() { Current = 0, Time = 0 }); var minCosts = new int[n, 1025]; //町Idx、特別な道情報->最小コスト for (int i = 0; i < n; i++) for (int j = 0; j < 1025; j++) minCosts[i, j] = Int32.MaxValue; Node ret = null; while (que.Count() > 0) { var node = que.Pop(); if (node.PassedKNum == k && node.Current == n - 1) if (ret == null || node.Time < ret.Time) ret = node; foreach (var edge in e[node.Current]) { var nextNode = GetNextNode(node, edge); if (nextNode.Time >= minCosts[nextNode.Current, nextNode.PassedK]) continue; minCosts[nextNode.Current, nextNode.PassedK] = Math.Min(minCosts[nextNode.Current, nextNode.PassedK], nextNode.Time); que.Push(nextNode); } } Console.WriteLine(ret.Time);