読者です 読者をやめる 読者になる 読者になる

World CodeSprint 5の参加日記

3完+1部分点で暫定349位/6403人。難易度Moderateを1つ落としたのが悔しい。
https://www.hackerrank.com/contests/world-codesprint-5/challenges


CamelCase

CamelCaseの文字列に、英単語がいくつあるか答えよ。

大文字の数+1を返せばよい。

Console.WriteLine(str.Count(s => s >= 'A' && s <= 'Z') + 1);


String Construction

空文字列pに以下の操作を行い、文字列sを作りたい。最小のコストを答えよ。
・p末尾に任意の文字を足す(1ドル)
・p内の部分文字列を、p末尾に足す(0ドル)

2度目以降に使う文字にはコストがかからないので、sから重複を排除した文字数を答えればよい。

Console.WriteLine(s.Distinct().Count());


Short Palindrome

英小文字のみからなる文字列sが与えられる。このとき、次の条件を満たす部分文字列が、s内にいくつあるか答えよ。
・任意のインデックスa,b,c,d(0 <= a < b < c < d)について、s[a]==s[d]かつs[b]==s[c]
1 <= |s| <= 10^6、解答は10^9+7のModを出力する

動的計画法を次のように定義して解いた。
dp_1[i][j]:0~iの文字jの個数
dp_2[i][l][m]:0~iで、{…,文字l,…,文字m,…}になっているパターン数
 → dp_2[i][l][s[i]] = dp_1[i-1][l] + dp_2[i-1][l][s[i]]
dp_3[i][j][k]:0~iで、{…,文字j,…,文字k,…,文字k,…}になっているパターン数
 → dp_3[i][j][s[i]] = dp_2[i-1][l][s[i]] + dp_3[i-1][j][s[i]]
このまま実装するとメモリが不足するので、配列の再利用を行っている。

const ulong mod = 1000000007;

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

    var dp_1 = new ulong[26];
    var dp_2 = new ulong[26, 26];
    var dp_3 = new ulong[26, 26];
    
    ulong ret = 0;
    for (int i = 0; i < s.Length; i++)
    {
        var c = s[i] - 'a';
        for (int x = 0; x < 26; x++)
        {
            ret += dp_3[c, x];
            ret %= mod;
        }

        for (int x = 0; x < 26; x++)
        {
            dp_3[x, c] += dp_2[x, c];
            dp_3[x, c] %= mod;
        }

        for (int x = 0; x < 26; x++)
        {
            dp_2[x, c] += dp_1[x];
            dp_2[x, c] %= mod;
        }

        dp_1[c]++;
        dp_1[c] %= mod;
    }

    Console.WriteLine(ret);
}

Editorialよりすっきりした解だと思うのだが、どうだろうか。


Longest Increasing Subsequence Arrays

長さmのInt型の配列を作る。このとき、部分列として、必ず{1,2,3,…n}が含まれるようにしたい。可能なパターン数を答えよ。
1 <= m <= 5x10^5、1 <= n <= 10^5
n <= m
解答は10^9+7のModを出力する

Editorialより。S[n]の位置+1をループすることで求めることができる。
f:id:yambe2002:20160725053056p:plain

static Int64 Solve(Int64 m, Int64 n)
{
    Int64 ret = 0;
    Int64 nPowX = 1;

    var n1PowX = ModPow(n - 1, m - n, mod);
    var invN1 = ModInv(n - 1, mod);

    for (Int64 x = 0; x <= m - n; x++)
    {
        //これだと大きいケースでTLEになる
        //var n1PowX = ModPow(n - 1, m - n - x, mod);
        
        //Invを掛けていく方法では、最終的に1になってはくれない
        if (m - n - x == 0) n1PowX = 1;

        var value = (Nck((int)(m - x - 1), (int)(n - 1)) * nPowX % mod) * n1PowX;
        value %= mod;

        ret += value;
        if (ret >= mod) ret -= mod;

        nPowX *= n;
        nPowX %= mod;

        n1PowX *= invN1;
        n1PowX %= mod;
    }

    return ret;
}

(n-1)^(m-n-x)をループ内で直接求めるとTLEになるので、(n-1)^(-1)のModを掛けていくことで算出する。ただし、この方法だと最終的に(n-1)^0のとき解が1になってくれないので、その場合だけ直接1をアサインすることになる。
ModPow()、Nck()、ModInv()は個人ライブラリより。


Balanced Forest

ノード数nの木があり、各ノードにはc[i]個のコインが付いている。ここで、どれかのノードにコインがcw個付いたノードを足し、n+1ノードの木にする。この木の2つのエッジを切ったとき、出来た3つの木が同じ数のコインを持つようにしたい。cwの最小値を求めよ。不可能な場合は-1とする。
1 <= n <= 5x10^4
1 <= c[i] <= 10^9

部分点(30%)
1 <= n <= 100
1 <= c[i] <= 100

部分点(50%)
1 <= n <= 2000
1 <= c[i] <= 10^9

本番では50%の部分点だった。エッジでループし、該当エッジをカットしたときの小さいほうが、最終的な3つの木の1つとなり得るかを判定している。そのとき、予め「ノードAからみたノードB以降の木の合計値」を求めることで計算量を削減した。
https://www.hackerrank.com/contests/world-codesprint-5/challenges/balanced-forest/submissions/code/6349361

Editorialによると、ノード1をルートとし、各ノードに子ノードのコイン合計を持つことで、O(n Log(n))で算出できる。これは本番で場合分けがうまくいかず、断念したやり方だった。
Editorialサンプルの変数名やコメントを直したものが以下。

static Int64 Solve()
{
    // Nodeクラスの配列を作成
    // 各Nodeについて、サブ木の合計、DFSの到着時間、およびDFSのLeave時間を保持する
    Dfs(1, 0);

    // サブ木合計値から、最小の到着時間、最大の到着時間とそれぞれのノードインデックスを保持する辞書を作成する
    for (int i = 1; i <= n; i++)
    {
        if (!minArrivalTime_BySum.ContainsKey(c[i].SumOfSubtree))
        {
            minArrivalTime_BySum[c[i].SumOfSubtree] = c[i].ArriveTime;
            maxArrivalTime_BySum[c[i].SumOfSubtree] = c[i].ArriveTime;
            idxOfMinArrivalTime_BySum[c[i].SumOfSubtree] = i;
            idxOfMaxArrivalTime_BySum[c[i].SumOfSubtree] = i;
        }
        else
        {
            if (minArrivalTime_BySum[c[i].SumOfSubtree] > c[i].ArriveTime)
            {
                minArrivalTime_BySum[c[i].SumOfSubtree] = c[i].ArriveTime;
                idxOfMinArrivalTime_BySum[c[i].SumOfSubtree] = i;
            }
            if (maxArrivalTime_BySum[c[i].SumOfSubtree] < c[i].ArriveTime)
            {
                maxArrivalTime_BySum[c[i].SumOfSubtree] = c[i].ArriveTime;
                idxOfMaxArrivalTime_BySum[c[i].SumOfSubtree] = i;
            }
        }
    }

    minCw = (Int64)1e15;

    // 木のコイン合計が偶数、かつちょうど半分のサブ木合計があったら、その値が解になり得る
    if (sum % 2 == 0 && maxArrivalTime_BySum.ContainsKey(sum / 2)) minCw = sum / 2; 

    // 全ノードのループ
    for (int i = 1; i <= n; i++)
    {
        if (3 * c[i].SumOfSubtree <= sum)   // この時は、該当サブ木にcwを足すことを試す
            TryAddCw_ToSubTree(i);
        else if (2 * c[i].SumOfSubtree < sum)   // サブ木合計を、最終的な1/3の1つとできるか試す
            TryAddCw_ToAnotherTree(i);
    }
    return minCw == (Int64)1e15 ? -1 : minCw;
}

static void TryAddCw_ToSubTree(int x)
{
    if ((sum - c[x].SumOfSubtree) % 2 == 0) //サブ木以外が2で割れなければ無理
    {
        Int64 p = (sum - c[x].SumOfSubtree) / 2;    //最終的な1/3のコイン数

        if (maxArrivalTime_BySum.ContainsKey(p) && (c[idxOfMaxArrivalTime_BySum[p]].ArriveTime > c[x].ArriveTime || c[idxOfMaxArrivalTime_BySum[p]].LeaveTime < c[x].ArriveTime))
            minCw = Math.Min(minCw, p - c[x].SumOfSubtree);                
        else if (minArrivalTime_BySum.ContainsKey(p) && (c[idxOfMinArrivalTime_BySum[p]].ArriveTime > c[x].ArriveTime || c[idxOfMinArrivalTime_BySum[p]].LeaveTime < c[x].ArriveTime)) 
            minCw = Math.Min(minCw, p - c[x].SumOfSubtree);
        else if (minArrivalTime_BySum.ContainsKey(p + c[x].SumOfSubtree) && 
                c[idxOfMinArrivalTime_BySum[p + c[x].SumOfSubtree]].ArriveTime < c[x].ArriveTime && 
                c[idxOfMinArrivalTime_BySum[p + c[x].SumOfSubtree]].LeaveTime >= c[x].ArriveTime) 
            minCw = Math.Min(minCw, p - c[x].SumOfSubtree);
        else if (maxArrivalTime_BySum.ContainsKey(p + c[x].SumOfSubtree) &&
                c[idxOfMaxArrivalTime_BySum[p + c[x].SumOfSubtree]].ArriveTime < c[x].ArriveTime && 
                c[idxOfMaxArrivalTime_BySum[p + c[x].SumOfSubtree]].LeaveTime >= c[x].ArriveTime) 
            minCw = Math.Min(minCw, p - c[x].SumOfSubtree);

        return;
    }
}

static void TryAddCw_ToAnotherTree(int x)
{
    Int64 add = 3 * c[x].SumOfSubtree - sum;

    if (minArrivalTime_BySum[c[x].SumOfSubtree] != maxArrivalTime_BySum[c[x].SumOfSubtree]) minCw = Math.Min(minCw, add);
    else if (minArrivalTime_BySum.ContainsKey(c[x].SumOfSubtree - add) && (c[idxOfMinArrivalTime_BySum[c[x].SumOfSubtree - add]].ArriveTime < c[x].ArriveTime || c[idxOfMinArrivalTime_BySum[c[x].SumOfSubtree - add]].ArriveTime > c[x].LeaveTime)) minCw = Math.Min(minCw, add);
    else if (maxArrivalTime_BySum.ContainsKey(c[x].SumOfSubtree - add) && (c[idxOfMaxArrivalTime_BySum[c[x].SumOfSubtree - add]].ArriveTime < c[x].ArriveTime || c[idxOfMaxArrivalTime_BySum[c[x].SumOfSubtree - add]].ArriveTime > c[x].LeaveTime)) minCw = Math.Min(minCw, add);
    else if (minArrivalTime_BySum.ContainsKey(2 * c[x].SumOfSubtree - add)) minCw = Math.Min(minCw, add);

    return;
}

//// 省略

class Node
{
    public Int64 SumOfSubtree; //c[i].s - sum of values in subtree rooted in i
    public int ArriveTime;  //time when dfs arrived in i-th node
    public int LeaveTime; //time when dfs leave i-th node ( all children are marked)
};

TryAddCw_ToSubTree()とTryAddCw_ToAnotherTree()で細かい場合分けをしているが、ノードのコイン数は必ず1以上なのだから、もっと簡略化できそうな気がする。
(あるノードのサブ木合計値が、そのノードの子で発生することは有り得ないため)