2017-01-12

HackerRank Week of Code - 26 参加日記

398位/6951人でレート減してしまった。いつも数学の問題が多いと順位を落としてしまう。以下Easy問は省略。

整数iとjがいずれも素数、かつ距離が2のとき、これらをペアであるとする。整数nとmが与えられたとき、区間[n,m]にはいくつのペアが存在するか。ただし、(i, j)と(j, i)は同じペアと扱う。
1 <= n <= m <= 10^9
m - n <= 10^6

あらかじめエラトステネスの篩を使って区間内の素数を列挙し、あとはi=n..m-2でループしてiとi+2が両方素数の場合をカウントすればよい。

// n, m <= 10^9, m - n <= 10^6
public static int GetAns(int n, int m)
{
    var isPrime = new bool[m - n + 1];
    SegSieve(n, m + 1, isPrime);
    var ret = 0;
    for (int i = n; i <= m - 2; i++)
    {
        if (isPrime[i - n] && isPrime[i - n + 2]) ret++;
    }
    return ret;
}

// returns primes in [a, b)
public static void SegSieve(int a, int b, bool[] isPrime)
{
    for (int i = 0; i < isPrime.Length; i++) isPrime[i] = true;
    for (int i = 0; i < isPrime.Length; i++)
    {
        if (i + a < 2) isPrime[i] = false;
    }

    var sqrtb = (int)Math.Ceiling(Math.Sqrt(b));

    // prime table of [0, sqrt[b])
    var primeTable_0_b = new int[sqrtb];
    var primeTable_0_b_is = new bool[sqrtb];

    Sieve(primeTable_0_b, primeTable_0_b_is);

    foreach (var p in primeTable_0_b)
    {
        if (p == -1) continue;
        var st = (a / p) * p;
        if (st == 0) st = p;
        if (st == p) st += p;
        while (st < b)
        {
            if (st >= a) isPrime[st - a] = false;
            st += p;
        }
    }
}

public static void Sieve(int[] prime, bool[] isPrime)
{
    for (int i = 0; i < prime.Length; i++) prime[i] = -1;
    for (int i = 0; i < isPrime.Length; i++) isPrime[i] = true;
    isPrime[0] = isPrime[1] = false;

    var idx = 0;
    for (int i = 2; i < isPrime.Length; i++)
    {
        if (isPrime[i])
        {
            prime[++idx] = i;
            for (int j = 2 * i; j < isPrime.Length; j += i) isPrime[j] = false;
        }
    }
}

Music on the Street

無限に長いストリート上に、ポイントa_0、a_1、... a_nが設置されている。a_0より前のストリートではある曲のジャンルが、a_0とa_1の間ではまた別の曲のジャンルが演奏されている（a_nからあとも同様）。ある人がある地点からポイントが大きくなる方向に時速1マイルでmマイル歩くとき、同じジャンルの曲をh_min時間以上、h_max時間以内だけ聞きたい。これを満足するスタート地点のいずれかを求めよ。
1 <= n <= 10^6
abs(a_i) <= 10^9、a_iは昇順で与えられる
1 <= h_min <= h_max <= 10^9
1 <= m <= 10^9

スタート地点の候補は限られているので、そのすべてで条件に合致するかトライする。予めボーダー間がすべて条件を満たすかどうかを管理する区間木を作っておけばよい。また、歩き始めのIndexや終点のIndexを求めるにはLowerBoundとUpperBoundも必要になる。
本番ではRmq内の配列サイズが足りず、1問RLEになっていた。

class Program
{
    public static long n;
    public static List<long> a;
    public static long m;
    public static long hmin;
    public static long hmax;

    public static Rmq _rmq;

    static void Main(string[] args)
    {
        n = long.Parse(Console.ReadLine());
        a = ReadLine().Split().Select(v => long.Parse(v)).ToList();
        var str = Console.ReadLine().Split();
        m = long.Parse(str[0]);
        hmin = long.Parse(str[1]);
        hmax = long.Parse(str[2]);
        Console.WriteLine(GetAns());
    }

    public static long GetAns()
    {
        // from left
        for (int i = 0; i < a.Count(); i++)
        {
            if (Ok(a[i] - hmin))
            {
                return a[i] - hmin;
            }
            if (Ok(a[i] - hmax))
            {
                return a[i] - hmax;
            }
            if (Ok(a[i]))
            {
                return a[i];
            }
        }

        //from right
        for (int i = a.Count() - 1; i >= 0; i--)
        {
            if (Ok(a[i] + hmin - m))
            {
                return a[i] + hmin - m;
            }
            if (Ok(a[i] + hmax - m))
            {
                return a[i] + hmax - m;
            }
            if (Ok(a[i] - m))
            {
                return a[i] - m;
            }
        }

        return -1000;
    }

    public static bool Ok(long pos)
    {
        var stIdx = (int)UpperBound(a, pos);
        if (stIdx >= a.Count() - 1) stIdx = a.Count() - 1;
        if (stIdx < 0) stIdx = 0;

        // check current pos to next bound
        if (!OkDist(pos, a[stIdx])) return false;

        var edIdx = (int)LowerBound(a, pos + m);
        edIdx--;
        if (edIdx >= a.Count() - 1) edIdx = a.Count() - 1;
        if (edIdx < 0) edIdx = 0;

        // check last bound to last pos
        if (!OkDist(a[edIdx], pos + m)) return false;

        // check intervals are all OK
        return OkIntervals(stIdx, edIdx);
    }

    public static bool OkIntervals(int idx1, int idx2)
    {
        if (idx1 == idx2) return true;
        if (idx1 + 1 == idx2) return OkDist(a[idx1], a[idx2]);

        if (_rmq == null)
        {
            _rmq = new Rmq();
            _rmq.Init((int)n + 1);

            for (int i = 0; i < n - 1; i++)
            {
                if (!OkDist(a[i], a[i + 1]))
                {
                    _rmq.Update(i, 0);
                }
                else
                {
                    _rmq.Update(i, 1);
                }
            }
        }
        return _rmq.Query(idx1, idx2) == 1;
    }

    public static bool OkDist(long pos1, long pos2)
    {
        var gap = pos2 - pos1;
        if (gap == 0) return true;
        return gap >= hmin && gap <= hmax;
    }

    public static long LowerBound(List<long> ar, long val)
    {
        long lb = -1;
        long ub = ar.Count();

        while (ub - lb > 1)
        {
            var mid = (lb + ub) / 2;
            if (ar[(int)mid] >= val)
            {
                ub = mid;
            }
            else
            {
                lb = mid;
            }
        }

        return ub;
    }

    public static long UpperBound(List<long> ar, long val)
    {
        long lb = -1;
        long ub = ar.Count();

        while (ub - lb > 1)
        {
            var mid = (lb + ub) / 2;
            if (ar[(int)mid] <= val)
            {
                lb = mid;
            }
            else
            {
                ub = mid;
            }
        }

        return lb + 1;
    }
}

public class Rmq
{
    const int MAX_N = 2000005;
    int _n;
    int[] _dat = new int[2 * MAX_N - 1];

    public void Init(int n)
    {
        _n = 1;
        while (_n < n) _n *= 2;
        for (int i = 0; i < _dat.Length; i++) _dat[i] = Int32.MaxValue;
    }

    public void Update(int k, int a)
    {
        k += _n - 1;
        _dat[k] = a;
        while (k > 0)
        {
            k = (k - 1) / 2;
            _dat[k] = Math.Min(_dat[k * 2 + 1], _dat[k * 2 + 2]);
        }
    }

    public int Query(int a, int b)
    {
        return Query(a, b, 0, 0, _n);
    }

    int Query(int a, int b, int k, int l, int r)
    {
        if (r <= a || b <= l) return Int32.MaxValue;
        if (a <= l && r <= b) return _dat[k];
        else
        {
            var vl = Query(a, b, k * 2 + 1, l, (l + r) / 2);
            var vr = Query(a, b, k * 2 + 2, (l + r) / 2, r);
            return Math.Min(vl, vr);
        }
    }
}

Satisfactory Pairs

正の整数nが与えられたとき、ax + bx = n に解が存在する(a, b)のパターン数を求めよ(a < b、x,yは正の整数）。
4 <= n <= 3x10^5

axでイテレートし、その内部でax・byの約数の組み合わせを作って、該当するものを合算していけばよい。

public static int GetAns(int n)
{
    // 使う約数を準備
    var divs = new List<int>[n + 1];
    for (int i = 1; i <= n; i++)
    {
        for (int j = i; j <= n; j += i)
        {
            if (divs[j] == null) divs[j] = new List<int>();
            divs[j].Add(i);
        }
    }

    int ct = 0;
    for (int xa = 1; xa < n; xa++)
    {
        int yb = n - xa;
        foreach (var a in divs[xa])
        {
            foreach (var b in divs[yb])
            {
                var x = xa / a;

                // x <= b / gcd(a, b) は
                // 同じ(a,b)ペアでxが最小のもののみをカウント
                if (a < b && x <= b / gcd(a, b))
                {
                    ct++;
                }
            }
        }
    }

    return ct;
}

public static int gcd(int a, int b)
{
    while (b > 0)
    {
        int c = a;
        a = b;
        b = c % b;
    }
    return a;
}

2017-01-12

Facebook Hacker Cup 2017 Qualification Round 参加日記

C# プログラミングコンテスト

○○×で予選通過。R1は時間的に参加できるかどうか微妙だ。

Progress Pie
進捗パイチャートと点Xがあたえられたとき、Xがチャートの色付き部分に入っているかどうかを判定する。
点の位置とチャートの進捗p(%)を0%からの角度に変換して求めた。

public static bool GetAns(int p, int x, int y)
{
    x -= 50;
    y -= 50;

    // 特殊なケース
    if (x == 0 && y == 0) return p > 0;
    if (p == 0) return false;

    // 中心から遠すぎる
    if (x * x + y * y > 2500) return false;

    var theta = Math.PI * 2 * (p / 100.0);

    // 垂直線(0%線)と中心-点Xの角度を求め、象限ごとに処理する
    var pt = new Pt(x, y);
    var theta_pt = Math.Asin(pt.Cross(_zero) / (pt.Norm() * _zero.Norm()));
    if (x < 0 && y < 0) //3rd
    {
        theta_pt = Math.PI - theta_pt;
    }
    else if (x < 0) //4th
    {
        theta_pt = Math.PI * 2 + theta_pt;
    }
    else if (y < 0) //2nd
    {
        theta_pt = Math.PI - theta_pt;
    }

    return theta_pt <= theta;
}

Lazy Loading
重さの異なるN個の荷物を、なるべく多くの回数で運ぶ。ただし一回50ポンド以上は運ばなければならない。また、まとめて運んでいる荷物は、その中で一番重い荷物x個数でトータルの重さと嘘をつくことができる。
残っている荷物で最も重いものを1つと、軽いほうから50ポンドと虚偽できるまで運ぶのを繰り返せばよい。

public static int GetAns(List<int> w)
{
    var ret = 0;

    while (w.Count() > 0)
    {
        w.Sort();
        if (w.Count() * w[w.Count() - 1] < 50) break;
        w = w.Skip((int)Math.Ceiling((double)50 / (double)w[w.Count() - 1]) - 1).ToList();
        w.Remove(w.Last());
        ret++;
    }

    return ret;
}

Fighting the Zombie
部分的には、Y面のサイコロをN回振ったとき、その合計がある数N以上になる確率を求める問題になる。
dp[i, j]をi回振って合計がjになる確率と定義すれば、
dp[i + 1, j + 1] += dp[i, j] / N
dp[i + 1, j + 2] += dp[i, j] / N
...
dp[i + 1, j + N] += dp[i, j] / N
と更新して最終的な確率がすべて求められる。
（実装は省略）

2016-12-15

HackerRank Week of Code - 25 参加日記

C# プログラミングコンテスト

25位/7510人の自己ベスト。Hardの１問を正答できたのと、Hard/Expertの部分点を取れたのが大きかった。以下、難易度Easyのものは省略する。

Baby Step, Giant Step

2次元上の座標(0,0)から(d,0)に移動する最小のステップ数を求めよ。ただし、1回のステップでは距離aまたは距離bのみ進むことができる。a,b,dの組み合わせはq個与えられるので、それぞれについて答えること。
1 <= q <= 10^5
1 <= a <= b <= 10^9
0 <= d <= 10^9

x座標軸上のみで考えると、(x1,0)から(x2,0)まで移動するステップ数は、
１、x2-x1がaまたはb：1
２、x2-x1がb*2より小さい：2
３、それ以外：(x1+b,0)から(x2,0)までのステップ数+1
となる。愚直に再帰で実装するとStackOverflowになるので、３の部分はループでbを足していく。

public static int GetAns(int a, int b, int d)
{
    var ret = 0;
    if (d > 2 * b)
    {
        ret = (d - 2 * b) / b;
        d -= ret * b;
    }
    while (d > b * 2)
    {
        d -= a;
        ret++;
    }

    if (d == a || d == b)
        ret += 1;
    else if (d != 0)
        ret += 2;

    return ret;
}

Stone Division

2人のプレーヤーが次のゲームを戦う。いずれも最善手を指したときに、勝利するのはどちらか。
・n個の石でできた山が１つある
・m個の一意なInt型の集合S = { ${ s_0, s_1, ..., s_{m-1} }$ }がある
・プレーヤーは交互に手を指す。手番では、Sから任意の ${ s_i }$ と任意の山１つを選んで、その集まりを ${s_i}$ 個の山に分割する。このとき、分割された集合は同数である必要がある
・指せる手がないプレーヤーが負けとなる
1 <= n <= 10^18
1 <= m <= 10
2 <= ${s_i}$ <= 10^18

NimやGrundy数の理解が前提。本番ではWL-Algorithmで解いて部分正答だった。
参考：grundy数を習得したかった - nanikakaのAOJ航海日誌
${ g(x) }$ を１つの山にx個の石があるときのGrundy数とする。
xをkで割ったとき、Grungy数は
${ g(d)\,xor\,g(d)\,xor\,...\,xor\,g(d)\,\, (k\,times) }$
となる。よって、kが偶数のときは0、奇数のときはg(d)に一致する。（＝kが偶数なら勝ち）

class Program
{
    static List<long> s;
    static Dictionary<long, bool> dict = new Dictionary<long, bool>();

    static void Main(string[] args)
    {
        var str = Console.ReadLine().Split();
        var n = long.Parse(str[0]);
        var m = Int32.Parse(str[1]);
        s = Console.ReadLine().Split().Select(st => long.Parse(st)).ToList();
        Console.WriteLine(GetAns(n) ? "First" : "Second");
    }

    static bool GetAns(long n)
    {
        var ret = false;
        if (dict.ContainsKey(n)) return dict[n];

        foreach (var k in s)
        {
            if (n % k != 0) continue;
            ret |= k % 2 == 0;
            if (ret) break;
            ret |= !GetAns(n / k);
            if (ret) break;
        }

        dict.Add(n, ret);
        return ret;
    }
}

Good Point

二次平面上に、n個の厳密な凸多角形と、m個の楕円(Ellipse)がある。すべての多角形と楕円が重なる点を求めよ。該当点は存在することが保障されている。また、該当するものであれば、どの点を答えても良い。
1 <= n <= 500
3 <= ${v_i }$ <= 1500 (多角形iの頂点数)
3 <= ${ \sum_{i=0}^{n-1} v_i }$ <= 1500
1 <= m <= 1500
各座標は[ -10^4, 10^4 ]の範囲にある
楕円のSemi Major Axisは10^4以下の整数
誤差は10^-4まで許容

本番でこれが解けたのはうれしい。
凸多角形と楕円が重なる部分は、かならず凸型の図形になる。よって、最終的な凸型図形までの距離をf(x, y)とすると、xおよびyを固定してできる関数f(A, y), f(x, B)はいずれも凹型の曲線になる。なのでXとYそれぞれで三分探索すれば解が求められる。

class Program
{
    static void Main(string[] args)
    {
        //polygon
        var polygons = new List<Polygon>();
        var n = Int32.Parse(Console.ReadLine());
        for (int i = 0; i < n; i++)
        {
            var polygon = new Polygon();
            var v = Int32.Parse(Console.ReadLine());
            for (int j = 0; j < v; j++)
            {
                var str = Console.ReadLine().Split();
                var x = Int32.Parse(str[0]);
                var y = Int32.Parse(str[1]);
                polygon.AddPoint(new Pt(x, y));
            }
            polygons.Add(polygon);
        }

        //ellipses
        var ellipses = new List<Ellipse>();
        var m = Int32.Parse(Console.ReadLine());
        for (int i = 0; i < m; i++)
        {
            var str = Console.ReadLine().Split();
            var x1 = Int32.Parse(str[0]);
            var y1 = Int32.Parse(str[1]);
            var x2 = Int32.Parse(str[2]);
            var y2 = Int32.Parse(str[3]);
            var a = Int32.Parse(str[4]);
            ellipses.Add(new Ellipse(x1, y1, x2, y2, a));
        }

        var lx = -10001.0;
        var rx = 10001.0;
        var ly = -10001.0;
        var ry = 10001.0;

        // ternary search in x
        for (int i = 0; i < 48; i++)
        {
            var x1 = lx + (rx - lx) / 3;
            var x2 = rx - (rx - lx) / 3;

            var ly_x1 = -10001.0;
            var ry_x1 = 10001.0;
            var x1Score = GetScore_TernaryY(ref ly_x1, ref ry_x1, x1, ellipses, polygons);

            var ly_x2 = -10001.0;
            var ry_x2 = 10001.0;
            var x2Score = GetScore_TernaryY(ref ly_x2, ref ry_x2, x2, ellipses, polygons);

            if (x2Score > x1Score)
            {
                //remove right
                rx = x2;
            }
            else
            {
                //remove left
                lx = x1;
                ly = ly_x2;
                ry = ry_x2;
            }
        }

        Console.WriteLine(lx);
        Console.WriteLine(ly);
    }

    static double GetScore_TernaryY(ref double ly, ref double ry, double x, List<Ellipse> ellipses, List<Polygon> polygons)
    {
        var score = GetScore(x, ly, ellipses, polygons);
        for (int i = 0; i < 48; i++)
        {
            var y1 = ly + (ry - ly) / 3;
            var y2 = ry - (ry - ly) / 3;

            var y1Score = GetScore(x, y1, ellipses, polygons);
            var y2Score = GetScore(x, y2, ellipses, polygons);

            if (y2Score > y1Score)
            {
                //remove right
                ry = y2;
            }
            else
            {
                //remove left
                ly = y1;
                score = y2Score;
            }
        }
        return score;
    }

    static double GetScore(double x, double y, List<Ellipse> ellipses, List<Polygon> polygons)
    {
        return GetScore(new Pt(x, y), ellipses, polygons);
    }

    static double GetScore(Pt pt, List<Ellipse> ellipses, List<Polygon> polygons)
    {
        return ellipses.Sum(e => e.GetDist(pt)) + polygons.Sum(p => p.GetDist(pt));
    }
}


public class Polygon
{
    public List<Edge> Edges;

    List<Pt> _points;

    public Polygon()
    {
        Edges = new List<Edge>();
        _points = new List<Pt>();
    }

    public void AddPoint(Pt point)
    {
        _points.Add(point);
        if (_points.Count >= 2)
        {
            Edges.Add(new Edge(_points[_points.Count() - 2], _points[_points.Count() - 1]));
        }
    }

    public double GetDist(Pt pt)
    {
        double minDist = Double.MaxValue;
        var inside = true;

        for (int i = 0; i < Edges.Count(); i++)
        {
            if (!IsCcw(pt, Edges[i].p1, Edges[i].p2))
            {
                inside = false;
            }

            minDist = Math.Min(minDist, Edges[i].Dist(pt));
        }

        return inside ? 0 : minDist;
    }

    public bool IsCcw(Pt p, Pt p1, Pt p2)
    {
        return Pt.Ccw(p, p1, p2) == 1;
    }
}

public class Ellipse
{
    public Pt P1;
    public Pt P2;
    public double A;
    public double D;

    public Ellipse(double x1, double y1, double x2, double y2, double a)
    {
        P1 = new Pt(x1, y1);
        P2 = new Pt(x2, y2);
        A = a;
        D = 2 * a;
    }

    public double GetDist(Pt pt)
    {
        var ret = P1.Dist(pt) + P2.Dist(pt);
        return ret <= D ? 0 : (ret - D) / 2;
    }
}

PtとEdgeは個人ライブラリのもの。

DAG Queries

頂点数n、辺数mのDAGが与えられる。すべての頂点vは値として整数a[v]持ち、これの初期値は0である。次のクエリの結果を答えよ。クエリは3タイプある。
1. 1 u x: 頂点uから訪れることのできる頂点vについて、a[v]をxに更新する
2. 2 u x: 頂点uから訪れることのできる頂点vについて、a[v]>xならa[v]をxに更新する
3. u: a[u]を出力する
2 <= n <= 10^5
1 <= m, q <= 10^5 (qはクエリの数)
0 <= x <= 10^9

すべてのクエリをため込んで出力のたびにa[v]を算出する方法も、クエリが来るたびに各a[i]を算出する方法もTLEになる。平方分割を使って解決する。

すべてのクエリをローカル変数に保持
クエリタイプ2について、 ${ \sqrt{q} }$ くらいのブロックごとに、ブロックkの時点でクエリ2だけでa[v]の値がどうなるかの情報、type_2[k][v]を作成する
クエリを最初から処理：(1)クエリ1はキューque1に入れていく。que1のサイズが ${ \sqrt{q} }$ を超えたらその時点でクエリ1だけで値がどうなるかの情報type_1[v]を作成する(2)クエリ3が来たらtype_2とtype_1を使って出力値を計算

Editorialによると、グラフすべてを計算しようとするとメモリが足りなくなるので、グラフを3つくらいに分割して3回処理を回す必要がある。
理屈はわかるのだが、C#で実装したらTLEになってしまった・・・。

2016-10-26

HackerRank Week of Code - 24 参加日記

C# プログラミングコンテスト

392位/9177人。難易度Hardの「XOR Matrix」が解けそうで解けなく3日ほど苦しんだ(結果は部分正解)。Easy問題は省略する。

Simplified Chess Engine

盤の大きさが4x4、かつクイーン・ルーク・ナイト・ビショップだけが存在するミニチェスを考える。勝利条件は相手のクイーンを取ることとする。盤面g個が与えられたとき、ｍ手以内に先手が必勝かどうかをそれぞれ答えよ。
先手後手それぞれ、クイーンが１個、ルークが０~2個、ナイトとビショップが合計0~２個ある
1 <= g <= 200
1 <= m <= 6

十分に小さいゲーム木なので、MinMax法で簡単に求められる。ただし実装が少し重い。ちなみに、所定の手数までの勝敗なので、Zobrist Hashなどで同一局面を排除するとWAになる。

class Program
{
    enum PIECES { EMPTY, Q, N, B, R, q, n, b, r };

    static void Main(string[] args)
    {
        var g = Int32.Parse(Console.ReadLine());

        while( g > 0 )
        {
            var str = Console.ReadLine().Split();
            var w = Int32.Parse(str[0]);
            var b = Int32.Parse(str[1]);
            var m = Int32.Parse(str[2]);
            var board = GetInitBoard();

            while ( w > 0 ) 
            {
                SetPiece_Init(true, board, Console.ReadLine().Split());
                w--;
            }

            while ( b > 0 ) 
            {
                SetPiece_Init(false, board, Console.ReadLine().Split());
                b--;
            }

            if (MinMax('W', board, m)) Console.WriteLine("YES");
            else Console.WriteLine("NO");

            g--;
        }
    }

    static PIECES[,] GetInitBoard()
    {
        var ret = new PIECES[4, 4];
        for (int row = 0; row < 4; row++)
        {
            for (int col = 0; col < 4; col++)
            {
                ret[row, col] = PIECES.EMPTY;
            }
        }
        return ret;
    }

    static void SetPiece_Init(bool isWhite, PIECES[,] board, string[] inStrs)
    {
        var piece = GetPiece(!isWhite ? inStrs[0].ToLower()[0] : inStrs[0][0]);
        var col = inStrs[1][0] - 'A';
        var row = inStrs[2][0] - '1';
        MovePiece(board, -1, -1, row, col, piece).Item2;
    }

    static PIECES GetPiece(char p)
    {
        switch (p) {
            case 'Q':
                return PIECES.Q;
            case 'N':
                return PIECES.N;
            case 'B':
                return PIECES.B;
            case 'R':
                return PIECES.R;
            case 'q':
                return PIECES.q;
            case 'n':
                return PIECES.n;
            case 'b':
                return PIECES.b;
            case 'r':
                return PIECES.r;
        }
        return PIECES.EMPTY;
    }

    //return IsTerminalState
    static bool MovePiece(PIECES[,] board, int prevRow, int prevCol, int row, int col, PIECES piece)
    {
        var isTerminal = false;

        if (prevRow != -1) board[prevRow, prevCol] = PIECES.EMPTY;

        if (board[row, col] != PIECES.EMPTY)
        {
            if (board[row, col] == PIECES.Q || board[row, col] == PIECES.q) isTerminal = true;
        }

        board[row, col] = piece;
        return isTerminal;
    }

    static char GetNextTurn(char turn)
    {
        return turn == 'W' ? 'B' : 'W';
    }

    static bool IsHisPiece(char turn, PIECES piece)
    {
        if(piece == PIECES.EMPTY) return false;

        if (turn == 'W')
            return piece == PIECES.Q || piece == PIECES.N || piece == PIECES.B || piece == PIECES.R;

        if (turn == 'B')
            return piece == PIECES.q || piece == PIECES.n || piece == PIECES.b || piece == PIECES.r;

        return false;
    }

    static bool Win(PIECES[,] board, char turn)
    {
        bool Q_exist = false;
        bool q_exist = false;

        for (int row = 0; row < 4; row++)
        {
            for (int col = 0; col < 4; col++)
            {
                if(board[row, col] == PIECES.Q) Q_exist = true;
                if(board[row, col] == PIECES.q) q_exist = true;
            }
        }

        if(turn == 'W' && !q_exist) return true;
        if(turn == 'B' && !Q_exist) return true;
        return false;
    }

    static PIECES[,] CopyBoard(PIECES[,] org)
    {
        var ret = new PIECES[4, 4];
        for (int row = 0; row < 4; row++)
        {
            for (int col = 0; col < 4; col++)
            {
                ret[row, col] = org[row, col];
            }
        }
        return ret;
    }

    static bool IsInRange(int row, int col)
    {
        return IsInRange(row) && IsInRange(col);
    }

    static bool IsInRange(int pos)
    {
        return pos >= 0 && pos < 4;
    }

    static int[,] Moves_N = new int[,]
    {
        { 2, 1}, { 1, 2}, { -1, 2}, { -2, 1}, { -2, -1}, { -1, -2}, { 1, -2}, { 2, -1},
    };

    static bool IsEnemy(PIECES p, PIECES p2)
    {
        if (p == PIECES.Q || p == PIECES.R || p == PIECES.B || p == PIECES.N)
            return p2 == PIECES.q || p2 == PIECES.r || p2 == PIECES.b || p2 == PIECES.n;

        if (p == PIECES.q || p == PIECES.r || p == PIECES.b || p == PIECES.n)
            return p2 == PIECES.Q || p2 == PIECES.R || p2 == PIECES.B || p2 == PIECES.N;

        return false;
    }

    static void TryMove(ref List<Tuple<int, int>> moves, PIECES[,] board, int row, int col, PIECES piece, int rowDiff, int colDiff)
    {
        row += rowDiff;
        col += colDiff;

        while (IsInRange(row, col))
        {
            if (board[row, col] == PIECES.EMPTY)
            {
                moves.Add(new Tuple<int, int>(row, col));
            }
            else if(IsEnemy(piece, board[row, col]))
            {
                moves.Add(new Tuple<int, int>(row, col));
                break;
            }
            else
            {
                break;
            }
            row += rowDiff;
            col += colDiff;
        }
    }

    static List<Tuple<int, int>> GetNextPositions(int row, int col, PIECES piece, PIECES[,] board)
    {
        var ret = new List<Tuple<int, int>>();

        if (piece == PIECES.N || piece == PIECES.n)
        {
            for (int i = 0; i < Moves_N.GetLength(0); i++)
            {
                var nextRow = row + Moves_N[i, 0];
                var nextCol = col + Moves_N[i, 1];
                if (IsInRange(nextRow, nextCol))
                {
                    if(board[nextRow, nextCol] == PIECES.EMPTY || IsEnemy(piece, board[nextRow, nextCol]))
                        ret.Add(new Tuple<int, int>(nextRow, nextCol));
                }
            }
        }
        else
        {
            switch (piece)
            {
                case PIECES.Q:
                case PIECES.q:
                    TryMove(ref ret, board, row, col, piece, 1, 0);
                    TryMove(ref ret, board, row, col, piece, 0, 1);
                    TryMove(ref ret, board, row, col, piece, -1, 0);
                    TryMove(ref ret, board, row, col, piece, 0, -1);
                    TryMove(ref ret, board, row, col, piece, 1, 1);
                    TryMove(ref ret, board, row, col, piece, -1, 1);
                    TryMove(ref ret, board, row, col, piece, 1, -1);
                    TryMove(ref ret, board, row, col, piece, -1, -1);
                    break;
                case PIECES.R:
                case PIECES.r:
                    TryMove(ref ret, board, row, col, piece, 1, 0);
                    TryMove(ref ret, board, row, col, piece, 0, 1);
                    TryMove(ref ret, board, row, col, piece, -1, 0);
                    TryMove(ref ret, board, row, col, piece, 0, -1);
                    break;
                case PIECES.B:
                case PIECES.b:
                    TryMove(ref ret, board, row, col, piece, 1, 1);
                    TryMove(ref ret, board, row, col, piece, -1, 1);
                    TryMove(ref ret, board, row, col, piece, 1, -1);
                    TryMove(ref ret, board, row, col, piece, -1, -1);
                    break;
            }
        }

        return ret;
    }

    //turn: 'W' or 'B'
    //return true if the player won
    static bool MinMax(char turn, PIECES[,] board, int depth)
    {
        //White could not capture black's Qween within m moves
        if (depth == 0) return turn == 'W' ? false : true;

        var nextTurn = GetNextTurn(turn);

        for (int row = 0; row < 4; row++)
        {
            for (int col = 0; col < 4; col++)
            {
                if (IsHisPiece(turn, board[row, col]))
                {
                    foreach (var nextPos in GetNextPositions(row, col, board[row, col], board))
                    {
                        var nextBoard = CopyBoard(board);
                        var nextIsTerm = MovePiece(nextBoard, row, col, nextPos.Item1, nextPos.Item2, board[row, col]);

                        if (nextIsTerm)
                        {
                            if (Win(nextBoard, turn)) return true;
                        }
                        else
                        {
                            if (!MinMax(nextTurn, nextBoard, depth - 1)) return true;
                        }
                    }
                }
            }
        }
        return false;
    }
}

XOR Matrix

数列a[0], a[1]... a[n]が与えられる。次の操作をm-1回行ったときの最終的な値を出力せよ。

i < n-1 ならa[i]へ XOR(a[i], a[i+1])を代入

i = n-1 ならa[i]へ XOR(a[i], a[0])を代入

1 <= n <= 10^5
0 <= m <= 10^18 - 1
0 <= a[j] <= 10^9

たとえば要素0にXOR加算する要素は、
1
1 1
1 0 1
1 1 1 1
1 0 0 0 1
1 1 0 0 1 1
1 0 1 0 1 0 1
1 1 1 1 1 1 1 1
1 0 0 0 0 0 0 0 1
のようにパスカルのフラクタルと同じ形になる。
(最上段は初期状態、その後は上から、操作１終了後、操作２終了後・・・の順)
パスカルのフラクタルがすべて1になるのは2^k回目のときで、その次の状態が該当要素と最終要素のXORになる。よって、現在の状態から2^kだけ飛ばして計算することが可能。
要素0以外も、シフトするだけで同じパターンとなる。

static void Main(string[] args)
{
    var str = Console.ReadLine().Split();
    var n = Int32.Parse(str[0]);
    var m = long.Parse(str[1]);
    var a = ReadLine().Split().Select(s => long.Parse(s)).ToArray();

    m--;
    while (m > 0)
    {
        long cnt = 1;
        while (cnt << 1 <= m)
        {
            cnt <<= 1;
        }

        var tmp = new long[a.Length];
        for (long i = 0; i < a.Length; i++)
        {
            tmp[i] = a[i] ^ a[(i + cnt) % a.Length];
        }
        a = tmp;
        m -= cnt;
    }

    foreach (var v in a)
    {
        Console.Write(v.ToString() + " ");
    }
    Console.WriteLine();
}

Shashank and the Palindromic Strings

文字列のリスト ${ a = [a_0, a_1, ..., a_{n-1} ] }$ がq個与えられる。それぞれについて次の条件を満たすパターン数を答えよ。

${ s_{i} }$ を ${a_{i}}$ の空文字以外のサブシーケンスとしたとき、 ${s_0 + s_1+ ...+ s_{n-1}}$ が回文になる

1 <= q <= 50
1 <= n <= 50

全文字列を連結した文字列sを考える。DPを次のように定義する。
${ dp[r, c, was1, was2] }$ ：セグメント[r, c]で回文になるサブシーケンスのパターン数。
　was1: s[r]の元文字列にある文字を含むかどうか
　was2: s[c]の元文字列にある文字を含むかどうか
更新条件は２通りある。
１. s[r]とs[c]の元文字列が同じとき

// ｒ・ｃの元文字列を使わないのは空文字のパターンのみ
dp[r, c, 0, 0] = 1;

// s[r]とs[l]を回文として使わないパターン
dp[r, c, 1, 1] = dp[r, c - 1, 1, 1] + dp[r + 1, c, 1, 1];
dp[r, c, 1, 1] -= dp[r + 1, c - 1, 1, 1]; // 重複を排除

// s[r]とs[l]を回文として使うパターン
if (s[r] == s[c])
{
    dp[r, c, 1, 1] += dp[r + 1, c - 1, 1, 1];
    dp[r, c, 1, 1] += dp[r + 1, c - 1, 0, 0];
}

２. s[r]とs[c]の元文字列が違うとき
２-１. s[r+1]とs[r]の元文字列が違い、さらにs[c-1]とs[c]の元文字列が違う場合

// rが元文字列の右端で、cが元文字列の左端のとき

// どちらの文字列も使わない場合は、その内側の結果と同じ
dp[r, c, 0, 0] = (r + 1 == c ? 1 : dp[r + 1, c - 1, 1, 1]);

// どちらかの文字列を使う場合は、使わない側をはぶいたパターン数に一致
dp[r, c, 1, 0] = dp[r, c - 1, 1, 1];
dp[r, c, 0, 1] = dp[r + 1, c, 1, 1];

// どちらも使うとき。s[r]とs[c]が一致しないと0になる
dp[r, c, 1, 1] = (s[r] == s[c] ? dp[r, c, 0, 0] : 0);

２-２. s[r+1]とs[r]の元文字列が違うが、s[c-1]とs[c]の元文字列は同じ場合

// s[r]が元文字列の右端だがs[c]は元文字列の左端ではないとき

dp[r, c, 0, 0] = dp[r, c - 1, 0, 0];    //s[r]、s[c]いずれの元文字列も使わない
                                        //dp[r + 1, c - 1, 0, 0]のような気がするが・・・？
dp[r, c, 1, 0] = dp[r, c - 1, 1, 0];    //s[r]の元文字列を使う
dp[r, c, 0, 1] = dp[r + 1, c, 1, 1];    //s[r]の元文字列を使わない
dp[r, c, 1, 1] = dp[r, c - 1, 1, 1];    //どっちも使う->s[r]を使うしかない

if (s[r] == s[c])
{
    //s[r]とs[c]が同じなら、この２つを回文に使うパターンが追加される
    dp[r, c, 1, 1] += dp[r + 1, c - 1, 1, 1];
    dp[r, c, 1, 1] += dp[r + 1, c - 1, 1, 0];

    //元文字列が隣り合っていた場合！
    if (A[r] + 1 == A[c])
    {
        dp[r, c, 1, 1]++; // 1増えるのみ
    }
}

２-３. s[r+1]とs[r]の元文字列が同じだが、s[c-1]とs[c]の元文字列は違う場合
　（２-２と同様）
２-４. s[r+1]とs[r]の元文字列も、s[c-1]とs[c]の元文字列も違う場合

// s[r]が元文字列の右端ではなく、s[c]が元文字列の左端ではないとき

// どちらの元文字列も使わないときは1つ内側の結果と同じ
dp[r, c, 0, 0] = dp[r + 1, c - 1, 0, 0];

// 片方の元文字列を使わないときは、使わない側を１つ内側にした結果と同じ
dp[r, c, 0, 1] = dp[r + 1, c, 0, 1];
dp[r, c, 1, 0] = dp[r, c - 1, 1, 0];

// どちらの元文字列も使うとき
dp[r, c, 1, 1] = dp[r + 1, c, 1, 1] + dp[r, c - 1, 1, 1];
dp[r, c, 1, 1] -= dp[r + 1, c - 1, 1, 1];   // 重複を排除

if (s[r] == s[c])
{
    // s[r]とs[c]が同じ文字なら、両方の元文字列を使うパターンに
    // 内側の結果すべてが加算される
    dp[r, c, 1, 1] += dp[r + 1, c - 1, 1, 1];
    dp[r, c, 1, 1] += dp[r + 1, c - 1, 1, 0];
    dp[r, c, 1, 1] += dp[r + 1, c - 1, 0, 1];
    dp[r, c, 1, 1] += dp[r + 1, c - 1, 0, 0];
}

最終的な実装は省略。

2016-10-12

ARC049-ARC058+ABC043メモ（練習）

C# プログラミングコンテスト

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);

2016-10-12

HackerRank Week of Code - 23 参加日記

C# プログラミングコンテスト

281位/10162人。たぶん実際の参加者はこの半分くらいか。
難易度Easyの2問は省略する。

Treasure Hunting

二次元平面上の(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

Unexpected Problem

英小文字からなる文字列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;
}

Gravity Tree

ノード数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の子ノードは区間 ${ [in_v, out_v) }$ となる
・これをセグメント木で管理する
セグメント木は３つ用意し、セグメントに対して①加算した距離の合計、②加算した距離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時間

//セグメント木の接点の値（３種類）
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のコードを読んで何とか理解できた。

2016-08-31

Topcoder SRM696 参加日記

C# プログラミングコンテスト

0完でレート微増だった。Div1のEasyはなぜこんなに難易度が高いのだろう（解けてない人が多すぎる）。

Div1 Easy Gperm

頂点数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;
}