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]; }