HackerRank Week of Code - 23 参加日記

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の子ノードは区間となる
・これをセグメント木で管理する
セグメント木は３つ用意し、セグメントに対して①加算した距離の合計、②加算した距離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のコードを読んで何とか理解できた。