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マスのマス目がある。１番左上のマスから、右が左に１マスずつ進める。このとき、一番右下に行く方法は何通りあるか。
ただし、下からAマス以内かつ左からBマス以内は通れない。
1 <= H, W <= 100000
1 <= A < H
1 <= B < W

f:id:yambe2002:20160726121234p:plain
左上から図の①までの経路数を求め、それぞれに②右下までの経路数を掛けて合計すればよい。

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を含むとは以下のように定義する。
${ a_x + a_{x+1} + ... + a_{y-1} = X }$
${ a_y + a_{y+1} + ... + a_{z-1} = Y }$
${ a_z + a_{z+1} + ... + a_{w-1} = Z }$
を満たす ${ 0 \leq x < y < z < w \leq z }$ が存在する。
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;  //ループ１回目は今回の値だけ存在する！
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)までの長方形内を赤く塗る。両方の色が塗られた箇所は紫になる。赤、青の有無を答えよ。

青の有無は、４頂点が赤の中心から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頂点の有向グラフの頂点に着色していく。ただし、頂点間には次のタイプの制約がいくつかある。
タイプ１：ある頂点xに塗るとき、すでに頂点yに塗られていなければならない
タイプ２：ある頂点uに塗るとき、すてに頂点vに塗られていてはならない
タイプ１がA個、タイプ２がB個存在する。着色できる頂点の最大数を求めよ。
1 <= N <= 100
0 <= A <= 100
0 <= B <= 10

タイプ１のみで考えると、y→xの有効グラフについて、閉ループを構成するノードが着色できない。そして、着色不可のノードの下流もすべて着色できない。
タイプ２は
　uに着色するとき：uに塗るときは、すでにvに塗られていなければならない
　uに着色しないとき：uを着色不可とする
と言い換えることができ、これはタイプ１と同じ制限となる。
タイプ２は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);