ARC057
A: 2兆円 - AtCoder Regular Contest 057 | AtCoder
所持金がt円ある。ある日の所持金がt円なら、次の日には1+Kt円増えている。二兆円に達するのは何日後か。
やるだけだが、k=0のケースを考慮しないとTLEになる。
public double Solve(double a, double k) { if (k == 0) return 2E12 - a < 0 ? 0 : 2E12 - a; double n = 0; while (true) { if (a >= 2E12) break; a += (1 + k * a); n++; } return n; }
B: 高橋君ゲーム - AtCoder Regular Contest 057 | AtCoder
N日間、それぞれa[i]回のゲームを行う。i日目の勝率が0~i-1日目までの勝率より真に高かったらその日は機嫌が良い。合計でK回ゲームに勝ったとすると、機嫌のよかった日数の最大値はいくつか。
なかなか解けずに苦しんだが、問題の読み違えのせいだった。
dp[i][j]を、i日目までにj回勝率があがる場合の、最小のそれまでの勝利日数とする。
dp[i+1][]は、負けた場合と、勝率が上がりギリギリの勝利数の2パターンで計算していけば求まる。
最終的に、dp[N][j]がK以下になる最大のjが答えになる。
public class Solver { const int INF = 500000 * 2000 + 1; int[] sum; List<int> _a; public int Solve(int n, int k, List<int> a) { if (a.Sum() == k) return 1; _a = a; sum = new int[a.Count()]; sum[0] = a[0]; for (int i = 1; i < a.Count(); i++) { sum[i] = sum[i - 1] + a[i]; } var dp = new int[n, n + 1]; for (int i = 0; i < n; i++) for (int j = 0; j < n + 1; j++) dp[i, j] = INF; for (int i = 0; i < n; i++) dp[i, 0] = 0; dp[0, 1] = a[0] > 0 ? 1 : 0; for (int i = 1; i < n; i++) { for (int j = 1; j < n + 1; j++) { dp[i, j] = Math.Min(dp[i - 1, j], GetMinWinNum(dp[i - 1, j - 1], i)); } } var ret = 0; for (int i = 1; i < n + 1; i++) { if (dp[n - 1, i] > k) continue; ret = Math.Max(ret, i); } return ret; } int GetMinWinNum(int prevWinSum, int idx) { if (prevWinSum == INF) return INF; var prevWinRate = (double)prevWinSum / (double)sum[idx - 1]; var needWinCnt = (int)Math.Ceiling(prevWinRate * (double)_a[idx]); if ((double)needWinCnt / (double)_a[idx] <= prevWinRate) needWinCnt++; if (needWinCnt > _a[idx]) return INF; return prevWinSum + needWinCnt; } }
ARC056
A: みんなでワイワイみかん - AtCoder Regular Contest 056 | AtCoder
K個以上のみかんを買いたい。みかんは1個A円、もしくはL個B円。最小の支払金額を求めよ。A, B, C <= 10^9、L <= 10^9、B <= A*L
ぜんぶA円で買う・なるべくB円で買って残りをA円で買う・ぜんぶB円で買う、の3パターンしかない。intだとオーバーフローする。
static ulong Solve(ulong a, ulong b, ulong k, ulong l) { return Math.Min(k * a, Math.Min((k / l) * b + (k % l) * a, ((k / l) + 1) * b)); }
B: 駐車場 - AtCoder Regular Contest 056 | AtCoder
駐車スペースがN個あり、それぞれ1~Nに番号が振られている。各駐車スペースは双方向にM本の道でつながっている。そして駐車スペースSが入口につながっている。車i(1~N)が順番に入口から入り、かつ自分の番号の駐車スペースに停めるとき、無事に駐車できる車はどれか。
駐車スペースiに車iが駐車できるというこは、Sからiまでに、i以上の頂点のみからなる経路が存在することと同じ。Dijkstra変種で解ける。
public class Solver { public static IEnumerable<int> Solve(int n, int s, List<List<int>> e) { var dist = new int[n]; for (int i = 0; i < n; i++) dist[i] = -1; var que = new PriorityQueue<ComparablePair<int, int>>(); //desc by score que.Push(new ComparablePair<int, int>(s, s)); while (que.Count() > 0) { var nextPair = que.Pop(); var score = nextPair.Item1; var node = nextPair.Item2; if (dist[node] >= score) continue; dist[node] = score; foreach (var next in e[node]) que.Push(new ComparablePair<int, int>(Math.Min(next, score), next)); } return Enumerable.Range(1, n).Where(v => dist[v - 1] >= v - 1); } }
TLEに苦しんだけど、標準出力をFlushしてないというオチだった(ずっとアルゴリズムを疑って改善してた)。
以下のコードを忘れずに付けるようにしなければ。
Console.SetOut(new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false }); foreach (var r in Solver.Solve(n, s - 1, e)) { Console.WriteLine(r); } Console.Out.Flush();
C: 部門分け - AtCoder Regular Contest 056 | AtCoder
社員がN人いて、各社員間は信頼度w[i,j]が定まっている。この会社をいくつかの部門に分けるとき、スコアを最大化せよ。
スコアは、(部門の数) x K - (異なる部門に属する2人の信頼度の総和)
1<=N<=17, 1<=w[i,j]<=10^16, 1<=K<=10^16
次のように言い換えることができる
- NxNの重み付き無向グラフの頂点を彩色する
- 使われた色の数xK-異なる色の間の重みの総和=スコア
- スコアの最大値はいくらか
Nが最大17であることに着目する。
DP[S]を頂点集合Sの解答だとすると、Sの部分集合tとuについて
DP[S] = dp[t] + k - (t-u間の重みの総和)
となる。
ある集合xの重み総和sub[x]は、その部分集合y・zについて
sub[x] = sub[y] + suz[z] + (y-z間の重みの総和)
なので、
DP[S] = dp[t] + k - sub[S] + sub[t] + sub[u]
と変形することができる。
public int Solve(int n, int k, int[,] w) { // すべての部分集合のコスト合計 var sub = new int[1 << 17]; for (int b = 0; b < 1 << n; b++) for (int i = 0; i < n; i++) for (int j = i + 1; j < n; j++) if (((1 << i) & b) != 0 && ((1 << j) & b) != 0) sub[b] += w[i, j]; // dp[S] は集合Sの解 var dp = new int[1 << 17]; for (int i = 0; i < 1 << n; i++) dp[i] = k; // Sを集合tと集合uに分解したとき、 // dp[S]は dp[t] + k - sub[S] + sub[t] + sub[u] になる for (int s = 0; s < 1 << n; s++) { for (int t = (s - 1) & s; t > 0; t = (t - 1) & s) { dp[s] = Math.Max(dp[s], dp[t] + k - sub[s] + sub[t] + sub[s - t]); } } return dp[(1 << n) - 1]; //dp[1 << n - 1] は通らないので注意! }
ARC055
A: 数え上げ - AtCoder Regular Contest 055 | AtCoder
1以上100以下の整数Nが与えられる。10^N+7を出力せよ。
1のあとN-1個のゼロを出力し、最後に7を出せばよい。
public string Solve(int n) { var ret = new StringBuilder(); ret.Append("1"); for (int i = 0; i < n - 1; i++) ret.Append("0"); ret.Append("7"); return ret.ToString(); }
B: せんべい - AtCoder Regular Contest 055 | AtCoder
大きさ1~Nのせんべいがランダムな順番に与えられる。大きさはそれぞれ1つずつ。与えられた時点で、食べるか食べないかを決定する。すでに見たせんべいの大小関係のみ分かる。最適戦略をとったとき、最大のせんべいNを食べることができる確率はいくらか。ただし、K枚までしか食べることはできない。
1<=K<=N<=1000
難しかった…。
今のせんべいが過去最大なら、(1)食べる(2)食べないのどちらかになる。
i番目のせんべいが過去最大になる確率は1/i、そうでない確率は1-1/i。
DFSで解けるが、「これまでの最大をすでに食べたか否か」を持たないとうまく遷移できない。
public class Solver { int _n; double[, ,] dp; public double Solve(int n, int k) { _n = n; dp = new double[n, k + 1, 2]; for (int i = 0; i < n; i++) for (int j = 0; j < k + 1; j++) for (int l = 0; l < 2; l++) dp[i, j, l] = -1; return dfs(0, k, 0); } double dfs(int idx, int k, int ateMaxVal) { if (idx == _n) return ateMaxVal; if (dp[idx, k, ateMaxVal] != -1) return dp[idx, k, ateMaxVal]; //current one is not max //rate: i - 1 / i var ret = ((double)(idx + 1 - 1) / (double)(idx + 1)) * dfs(idx + 1, k, ateMaxVal); //current one is max //rate: 1 / i //don't eat var temp = (1.0 / (double)(idx + 1)) * dfs(idx + 1, k, 0); //eat if(k > 0) temp = Math.Max(temp, (1.0 / (double)(idx + 1)) * dfs(idx + 1, k - 1, 1)); ret+=temp; dp[idx, k, ateMaxVal] = ret; return ret; } }
C: ABCAC - AtCoder Regular Contest 055 | AtCoder
長さNの文字列Sが与えられる。3つの空でない文字列A,B,Cを使い、S=ABCACと表現できる組み合わせは何通りか。
愚直に解いたら部分点になった。
public int Solve(char[] s) { var ret = 0; for (int ai = 0; ai < s.Length; ai++) for (int ci = s.Length - 1; ci > ai; ci--) if (Meet(s, ai, ci)) ret++; return ret; } bool Meet(char[] s, int ai, int ci) { var alen = ai + 1; var clen = s.Length - ci; var blen = s.Length - alen - alen - clen - clen; if(alen <= 0 || blen <= 0 || clen <= 0) return false; //check a while (ai >= 0) { if (s[ai] != s[alen + blen + clen + ai]) return false; ai--; } //check c while (ci < s.Length) { if (s[ci] != s[ci - clen - alen]) return false; ci++; } return true; }
ABC/ACの切れ目を全探索してゆく。このとき、AとCが両方存在できれば有効になる。
ACの存在を効率よく判定する方法は、ローリングハッシュでの二分探索や、Z-algorithmを使うやり方がある。
参考
ローリングハッシュ:蟻本(第二版)P.332
Z-algorithm:文字列の頭良い感じの線形アルゴリズムたち3 - あなたは嘘つきですかと聞かれたら「YES」と答えるブログ
ARC054
A: 動く歩道 - AtCoder Regular Contest 054 | AtCoder
円周Lの動く歩道がある。動く歩道は、時計回りに1秒間にs進んでいる。唯一の出口が最北点から時計回りに距離Dにあり、いま距離Sにいる。1秒間にY歩けるとき、最短で何秒後に出口に着けるか。
時計回りと反時計回りを試す。
public double Solve(int l, int x, int y, int s, int d) { double leftDist = s > d ? Math.Abs(s - d) : l - Math.Abs(s - d); double rightDist = d > s ? Math.Abs(s - d) : l - Math.Abs(s - d); return s == d ? 0.0 : Math.Min(rightDist / (double)(y + x), y - x <= 0 ? double.MaxValue : leftDist / (double)(y - x)); }
B: ムーアの法則 - AtCoder Regular Contest 054 | AtCoder
現在のコンピューター性能でP年かかるタスクがある。コンピューターは、1.5年ごとに処理能力が2倍になる。なるべく早いタスクの終了時間を求めよ。(タスクは中断できないものとする)
0<=P<=10^18
x年後にタスク処理を始めるとするとき、終了時間はx+P/(2^(x/1.5))になる。これは凸関数なので、三分探索で求めることができる。
間違えてタスクの開始時間を返していたのに気づかず手間取った。
ちなみに、微分すれば一発で答えが出せるようだ。
public double Solve(double p) { double l = 0; double r = p; //ternary search while(r - l > 1E-10) { var m1 = l + (r - l) / 3.0; var m2 = l + (r - l) * 2.0 / 3.0; var t1 = m1 + p / Math.Pow(2.0, m1 / 1.5); var t2 = m2 + p / Math.Pow(2.0, m2 / 1.5); if (t1 < t2) { r = m2; } else { l = m1; } } return (l + r) / 2.0 + p / Math.Pow(2.0, ((l + r) / 2.0) / 1.5); //この計算を忘れていた }
ARC053
A: ドミノ色塗り - AtCoder Regular Contest 053 | AtCoder
H x Wのタイルがある。上下または左右に隣り合う2マスを選びたい。選び方は何通りか。
2 x W x H - (W + H) が答え。
Console.WriteLine(2 * h * w - w - h);
B: 回文分割 - AtCoder Regular Contest 053 | AtCoder
英小文字からなる文字列Sを適当にならびかえ、それを分割していくつかの回文文字列を作る。この回文文字列の長さの最小値をなるべく大きくしたい。この値を求めよ。
奇数個の文字を1つずつ、出来上がる回文文字列の中心に配置する。そして残った文字(すべて偶数個)をなるべく均等に割り振ればよい。
public static int Solve(string s) { var num = new int[26]; foreach (var c in s) num[c - 'a']++; var devideNum = 0; foreach (var n in num) if (n % 2 == 1) devideNum++; if(devideNum == 0) return s.Length; var ret = 1 + (((s.Length - devideNum) / 2) / devideNum) * 2; return ret; }
C: 魔法使い高橋君 - AtCoder Regular Contest 053 | AtCoder
N個の魔法がある。i番目の魔法を唱えると、a[i]℃温度が上がったのち、b[i]℃温度が下がる。魔法を唱える順番を調整し、気温の最大値をなるべく小さくしたい。この気温を答えよ。
温度が下がる魔法と上がる魔法に分け、下がる魔法をa[i]の昇順、上がる魔法をb[i]の降順でソートする。あとは下がる魔法→上がる魔法の順番で唱える。
public static Int64 Solve(int n, Int64[][] m) { var magics_dec = m.Where(v => v[0] < v[1]).OrderBy(v => v[0]); var magics_inc = m.Where(v => v[0] >= v[1]).OrderByDescending(v => v[1]); Int64 ret = 0, cur = 0; foreach (var magic in magics_dec.Concat(magics_inc)) { ret = Math.Max(ret, cur + magic[0]); cur += magic[0] - magic[1]; } return ret; }
これもintだとオーバーフローする。
部分的に正答になったときは、まずオーバーフローを疑うのが基本になりそう。