ARC053 - ARC057メモ(練習)

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

次のように言い換えることができる

  1. NxNの重み付き無向グラフの頂点を彩色する
  2. 使われた色の数xK-異なる色の間の重みの総和=スコア
  3. スコアの最大値はいくらか

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だとオーバーフローする。
部分的に正答になったときは、まずオーバーフローを疑うのが基本になりそう。