HackerEarch July Circuits '17 参加日記

HackerEarth初参戦。74位/6699人とまずまずの成績だった。
以下、易問は省略する。

Permutation and reverse

1~nの数字が書かれたn枚のカードがある。このランダムに並んでいるカードを、区間を指定して反転、を繰り返して昇順にソートせよ。
<採点方法>
配列a[]が与えられる。無限配列 { b_i = a_i \, mod\,n }と定義する。
i番目の作業区間の長さを {len_i} としたとき、 {len_i} と一致する次の {b} の位置をposとする。作業するごとposを更新したとき、最終的なposの位置が小さいほど、高得点となる。

上位10人くらいには入ったが、それでもトップの1/4程度のスコアだった。
<方針>
bの位置でループし、
・未ソート区間の左端または右端をうまく作れるときは作る
・それ以外なら、なるべく昇順または降順になるよう、一部を並び替える
を繰り返す
・候補手が複数あるときはランダムに選択
・時間いっぱいトライしてベストのものを回答する
https://www.hackerearth.com/submission/10398190/


Download file

サイズS(MB)のファイルをダウンロードしたい。時間t[i]におけるダウンロードスピードがD[i]で与えられたとき、ダウンロード時間を最小化せよ。
1 <= N <= 100,000
1 <= D[i], S <= 1,000,000
0 <= t[i] <= 1,000,000
t[0] = 0、tの値は昇順

必ず、ダウンロードの開始時間または終了時間がt[i]のいずれかになる。よって、t[i]をループして最短のものを探せばよい。ダウンロード時間は累積和を使えばO(1)で求められる。
https://www.hackerearth.com/submission/10349554/


Dreamplay and Upside Down

文字列Pがある。(1)末尾に文字を追加(2)文字を削除、のいずれかを繰り返し、なるべく少ないステップで回文を作れ。
1 <= Pの長さ <= 5000

文字位置でループ。その文字(もしくは文字間)を中心として回文を作り、最小ステップのものを回答する。あらかじめダミー文字('.'など)を挿入すると、文字間を考えなくてよいので楽。
https://www.hackerearth.com/submission/10285667/


Travelling Tom

n個の都市が双方向の道でつながっている。また、k種類のトークンがあり、それぞれ値段c[i]である。道にはそれぞれ、通過に必要なトークンの種類が設定される(トークンは使いまわせし)。すべての都市を訪れるために必要な、最小の金額を答えよ。
・すべての2<=i<=kについて、c[i] >= 2 * c[i-1]
・1 <= n <= 10^5
・1 <= m <= 10^5
・1 <= c[i] <= 10^18

本番では二分探索+UnionFindで解いて半分ほどTLEになっていた。
https://www.hackerearth.com/submission/10394484/
kの最大値が60程度なのがポイント。あるトークンだけが不足してるとき、全都市が連結でなければ、そのトークンは必須と判断していけばよい(実装は省略)。


MST revisited

ノード数N、エッジ数Nの無向グラフがある。エッジは重みづけされている。自己ループや並行エッジは存在せず、グラフは常に連結されている。エッジを1つ削除・追加するクエリをQ個実行する。このとき、クエリ実行ごとにMSTのコストを答えよ。
・3 <= N <= 300,000
・1 <= Q <= 300,000
・グラフは常に連結、かつ自己ループや並行エッジは存在しない
・1 <= エッジの重み <= 1,000,000

本番ではBICCで実装した。削除エッジがループ内かどうか判定し、計算量を節約してなんとか1サンプルのAC(3/4でTLE)だった。
https://www.hackerearth.com/submission/10374653/
上位陣はLink-cut木というデータ構造を使って解いていた。
https://www.hackerearth.com/challenge/competitive/july-circuits-17/algorithm/mst-revisited-3f9d614c/submission/10347662/
基本的には、ループを作ってしまう1つのエッジ(両ノードのrootが同じになっているもの)を保持し、他はLink-cut木で挿入・削除を繰り返しているようだ。そしてサブ木ごとにMaxコストを保持することで、ループ内の最大コストを算出する計算量を減らしている。
Link-cut木の解説はこちらが参考になる。
プログラミングコンテストでのデータ構造 2 ~動的木編~


Transportation network

n個の都市があり、1つのクエリで都市uとvを道路または鉄道で繋ぐ。クエリごとに、ネットワークがbalancedかどうかと答えよ。balancedなネットワークとは、
・すべての都市のペアu,vについて、u,vが道路で繋がれているときのみ、鉄道で繋がれている
ものをいう。
1 <= n <= 10^5
1 <= q <= 2x10^5
1 <= u, v <= n

本番ではUnionFindを2つ作り、グループに所属するノード数を比較して2/3ほどTLEだった。
https://www.hackerearth.com/submission/10375122/
2つのUnionFindの状態判定に工夫がいる。たとえば道路のネットワークに注目したときには、Queueに保持したエッジごとに鉄道側のUnionFindにおいて同じグループが判定する。分割は無いので同グループと判明したエッジは削除してOK。これを道路側・鉄道側両方で実施する。

var str = Console.ReadLine().Split().Select(v => Int32.Parse(v)).ToList();
var n = str[0];
var q = str[1];

var uf1 = new UnionFind(n);
var uf2 = new UnionFind(n);
var que1 = new Queue<Tuple<int, int>>();
var que2 = new Queue<Tuple<int, int>>();

while (q-- > 0)
{
    str = Console.ReadLine().Split().Select(v => Int32.Parse(v)).ToList();

    (str[0] == 1 ? uf1 : uf2).Unite(str[1] - 1, str[2] - 1);
    (str[0] == 1 ? que1 : que2).Enqueue(new Tuple<int, int>(str[1] - 1, str[2] - 1));

    for (int i = 0; i < 2; i++)
    {
        var uf = i == 0 ? uf2 : uf1;
        var que = i == 0 ? que1 : que2;

        //balanced?
        while (que.Count() > 0)
        {
            var n1 = que.Peek().Item1;
            var n2 = que.Peek().Item2;
            if (uf.root(n1) != uf.root(n2))
            {
                break;
            }
            else
            {
                que.Dequeue();
            }
        }
    }

    Console.WriteLine(que1.Count() == 0 && que2.Count() == 0 ? "YES" : "NO");
}