[C#] 第二回アルゴリズム実技検定PAST GHI(中級)問題振り返り

第二回アルゴリズム実技検定の振り返り記事です。

• [C#] 第二回アルゴリズム実技検定PAST A-F(初級)問題振り返り │ Web備忘録
• [C#] 第二回アルゴリズム実技検定PAST GHI(中級)問題振り返り │ Web備忘録 <-このページ
• [C#] 第二回アルゴリズム実技検定PAST JKL(上級)問題振り返り │ Web備忘録

第一回の振り返りは以下の記事にあります。

• [C#] AtCoder 第一回 アルゴリズム実技検定 の振り返り │ Web備忘録

第二回アルゴリズム実技検定

AtCoder が主催する アルゴリズム実技検定 の第二回に参加しました。

この検定は5時間の試験時間で全15問のアルゴリズム能力が試される問題を解きます。自分の好きな言語でプログラムを書き、それを提出すると実際に実行されてそのコードがあっているかがテストされます。

普段の AtCoder のコンテストに比べると実装よりの問題が多く、数学的考察やひらめき系の問題は少なくっています。

検定結果に応じて5段階(エントリー、初級、中級、上級、エキスパート)の公式認定の等級が付与されます。

私の場合は第一回が中級で、今回は81点の上級でした。せっかくなので解けた問題の振り返り記事を書いていこうと思います。この記事では中級認定に必要な問題GHIの3問(A-Fまで解けた前提)を振り返ります。

3問の感想としてこれまでの問題に比べると計算量を意識しなければならない問題が増えました。動的計画法という花形アルゴリズム問題も登場し、経験者向けといったようなセットでした。とはいえI問題のトーナメントは単純に言われた通り実装するだけで、F問題とかのほうが難しかったような気がしないでもないです。

以下コードはすべてC#です。入力部分はいい感じに読み替えてください。

G – ストリング・クエリ

G – ストリング・クエリ

文字列 S に対して Q 回の操作を行います。初め文字列 S は空文字列です。

i 回目の操作の種類は整数 Ti(1≤i≤Q) で表され、その内容は以下の通りです。

• Ti=1 のとき
  • 英小文字 Ci と整数 Xi が与えられる。S の末尾に Ci を Xi 文字追加する。
• Ti=2 のとき
  • 整数 Di が与えられる。S の先頭から Di 文字を削除する。S の長さが Di 文字以下である場合は、S は空文字列となる。 そして、この操作でa, b, c, ⋯ z の各文字が何文字削除されたかを求める。それぞれ del_a,del_b,⋯,del_z 文字削除された場合、del_a²+del_b²+⋯+del_z² を出力する。

制約

• 1≤Q≤10⁵
• Ti=1 または 2
• Ci は英小文字
• 1≤Xi≤10⁵
• 1≤Di≤10⁵
• Q,Ti,Xi,Di は整数
• Ti=2 の操作が 1 つ以上存在する

大量のクエリを処理する問題です。確か第一回の検定でも似たような問題があったような気がします。この問題では、クエリで文字の追加と削除を行いますが、その文字数がそれぞれ10⁵と大きく、クエリも同じくらいあるので文字通りクエリをシミュレートすると、計算量的に間に合いません。したがって工夫が必要です。

追加のクエリと削除のクエリそれぞれで考えます。

まず追加クエリですが、これは単純に追加する文字Ciと文字数Xiのペアで追加するようにします。こうすることで、O(1) の計算量で追加ができます。

削除ですが、これはリストの先頭タプルから順番に確認し、指定のDi文字が消せるまで繰り返すようにします。この時削除した文字について、文字種ごとに個数を数えておきます。指定数削除できたら、削除された文字について2乗和を求めてやればOKです。

10⁵文字の削除の場合に、10⁵のリストの先頭から削除を行い、1回のクエリで O(N) かかりそうですが、10⁵のリストができるには10⁵回の追加クエリを処理していることになるので、大量の削除を行おうと、追加クエリ実行回数以上の計算量はかかりません。

データを通常のリストや配列を使うと先頭要素の削除が計算量的に難しいので、Dequeu を自前で実装するか LinkedList を使うとよいでしょう。今回は管理するデータに対してランダムアクセスは必要ないので、先頭と末尾へのデータ追加削除が高速にできる LinkedList を使うことにします。

以上、この実装方針で計算量 O(Q) となります。

var Q = sc.ReadInt();
var list = new LinkedList<(char, int)>();
for (int i = 0; i < Q; i++)
{
    var t = sc.ReadInt();
    if (t == 1)
    {
        // 追加: 文字cをx個末尾に追加
        var c = sc.ReadStr()[0];
        var x = sc.ReadInt();
        list.AddLast((c, x));
    }
    else
    {
        // 削除: 
        var d = sc.ReadInt();
        var count = new int[26];
        // 空文字になるか、指定文字数削除されるまでループ
        while (list.Count > 0 && d > 0)
        {
            var delCount = Math.Min(list.First.Value.Item2, d);
            // 先頭を取り出しておく
            var first = list.First.Value;
            list.RemoveFirst();
            // 削除される文字と何文字あるか
            var c = first.Item1;
            var m = first.Item2;
            if (m > delCount)
            {
                // 先頭の文字数のほうが大きい場合はxだけ残る
                var x = m - delCount;
                list.AddFirst((c, x));
            }
            // 削除した文字数だけ引いておく
            d -= delCount;
            // 消した文字を数えておく
            count[c - 'a'] += delCount;
        }

        // 2乗和を計算する
        var ans = 0L;
        foreach (var c in count)
        {
            ans += (long)c * c;
        }
        Console.WriteLine(ans);
    }
}

C# は競技プログラミング的にみると標準ライブラリが弱いため、このような問題に対応できるように Deque 等を自前で実装したものを持っていないと、難しいことがあります。

C# で Deque(両端キュー)を実装してみる │ Web備忘録

DequeについてC#の実装を知りたい人は上の記事を参考にしてください。今回の問題のように LinkedList で代用できることもありますが、違いを知っておくとよいでしょう。

H – 1-9 Grid

H – 1-9 Grid

縦 N マス、横 M マスのマス目があり、各マスには S, G, 1 から 9 の数字のうちいずれかが書かれています。S と G の書かれたマスはただ 1 つ存在します。

マス目の状態は文字からなるサイズ N×M の二次元配列 A で表され、上から i 行目、左から j 列目に書かれた文字は Ai,j です。

今、S のマスから出発して G のマスに移動しようとしています。各マスからは、4 方向に隣り合うマスに移動することができます。マス目の外に出るような移動はできません。S のマスから G のマスへのそのような経路であって、1, 2, ⋯, 9 の書かれたマスをこの順に含むような経路のうち、隣のマスに移動する回数が最小である経路での移動回数を求めてください。また、そのような経路が存在しない場合は −1 を出力してください。

なお、経路が 1, 2, ⋯, 9 の書かれたマスをこの順に含むとは、k 回の移動でマスに書かれていた文字を c0= S, c1,c2,⋯,ck = G としたとき、ci1= 1, ci2=2, ⋯, ci9= 9 となるような 1≤i1≤i2⋯≤i9<k が存在することを表します。

ただし、同じマスは複数回通って良く、S, G の書かれたマスを途中で通過しても構いません。

制約

• 1≤N,M≤50
• A は S, G, および 1 から 9 の数字から成るS, G の書かれたマスはちょうど 1 つずつ存在する

この問題は問題文を誤読していて非常に時間がかかりました。

「1, 2, ⋯, 9 の書かれたマスをこの順に含むような経路」というのは、

S 5 1 2 3 6 4 5 7 6 7 8 9 G

みたいな移動経路でゴールまでどりついたとき、この中に移動経路が部分列として 123456789 が含まれているかという意味です。1の前に5があろうが関係ありません。つまり上の経路は条件を満たします。

問題文を理解したところで制約に目を移すと、H, Wが非常に小さいことがわかります。マス目が少ないので全探索を考えてみます。

当たり前ですが、最初の移動はスタート地点から1のマスへ最短で移動する方法が最善です。次は2のマスへ、3のマスへ … ゴールのマスへと最短で移動すれば特定の9マスを踏む経路における最短経路が求まります。

ただし、スタート地点から遠い1に移動するのがよい場合もあるので、最も近い1(次のマス)に移動するような貪欲法は最短経路が求まりません。最初の移動はすべての1のマスへの移動を計算する必要があります。続くマスについても同様です。

ありうるすべての1-9の組み合わせを試すことを考えます。マスの位置さえわかればその間の最短経路はすぐに計算できます。したがって全探索の計算量は O(1のマス数 * 2のマス数 * ... * 9のマス数) となります。

最悪のケースは、おそらく各数字のマスが均等に存在する場合です。つまり各数字のマスが 25(=250/10) ずつの時、計算量が O(259=3814697265625) となります。これではとても間に合いません。

ここでメモ化再帰の考えを使います。今回の全探索では、例えば特定の7のマスから8,9,Gと進む場合の最短経路は1度計算すればほかの経路における計算でも利用することができます。したがってこの計算をメモ化しておくことで計算量を小さくすることができます。詳細は実装を見てください。

var N = sc.ReadInt();
var M = sc.ReadInt();

// 1-9の位置を管理するリスト(0をS, 10をGとする)
var pos = new List<(int, int)>[11];
for (int i = 0; i < 11; i++)
{
    pos[i] = new List<(int, int)>();
}

// 各数の出現位置を覚える
for (int i = 0; i < N; i++)
{
    var S = sc.ReadStr();
    for (int j = 0; j < M; j++)
    {
        var c = S[j];
        if (c == 'S') pos[0].Add((i, j));
        else if (c == 'G') pos[10].Add((i, j));
        else pos[c - '0'].Add((i, j));
    }
}

// あるマスからGまでの最短経路
var memo = new int[N, M];
var inf = int.MaxValue / 2;
// 現在の座標と次に移動する先の数字
int Rec(int h, int w, int nextNumber)
{
    // Gまで到達
    if (nextNumber == 11) return 0;
    // 計算済
    if (memo[h, w] > 0) return memo[h, w];

    var res = inf;
    // 次に移動する先の番号を全探索
    foreach (var p in pos[nextNumber])
    {
        var nh = p.Item1;
        var nw = p.Item2;
        // 次のマスへの移動コスト
        var cost = Math.Abs(nh - h) + Math.Abs(nw - w);
        res = Math.Min(res, Rec(nh, nw, nextNumber + 1) + cost);
    }

    // メモしておく
    memo[h, w] = res;
    return res;
}
// スタート地点からか計算
var ans = Rec(pos[0][0].Item1, pos[0][0].Item2, 1);
if (ans >= inf) ans = -1;
Console.WriteLine(ans);

メモ化再帰の動的計画法でした。

存在しない数字があれば経路が存在しないと判定できるので、先にその判定をしてもよいです。

I – トーナメント

I – トーナメント

人 1、人 2、…、人 2^N の 2^N 人が一列に並んでトーナメントを行いました。このトーナメントは以下のようにして行われました。

1 回戦: 1≤i≤2^N-1 を満たすそれぞれの i について、人 2i−1 と人 2i が戦う。どちらか一方が勝つので、勝った方が残る。i 回戦 (i≥2): i−1 回戦で残った人が番号順に左から並び、左から 2 人ずつペアになり、各ペア内の 2 人が戦う。どちらか一方が勝つので、勝った方が残る。各試合の記録は失われてしまいましたが、人 i の強さが Ai であったことは記録に残っていました。ここで、2 人の人が戦ったとき、強さの値が大きい方が勝ちます。

それぞれの人について、その人が最後に戦ったのは何回戦か求めてください。

制約

• 1≤N≤16
• 1≤Ai≤2N
• A の要素は相異なる

        ┌──  8
     ┌──┤
     │  └──  7
  ┌──┤
  │  │ ┌──  6
  │  └─┤
  │    └──  5
──┤
  │     ┌──  4
  │  ┌──┤
  │  │  └──  3
  └──┤
     │  ┌──  2
     └──┤
        └──  1

今回の問題では上のようなきれいなトーナメント表で行われました。シードなどはありません。

出場選手は多くても 2¹⁶=65536 人程度なので、トーナメントのすべての試合をシミュレートしても間に合います。1回戦を行い、勝ち残った人を新しい配列に入れて、試合を行います。これを繰り返せばよいです。計算量は 2N です。

var N = sc.ReadInt();
var m = 1 << N; // 2^N

// 選手番号と数値をペアで持っておく
var players = new List<(int, int)>();
for (int i = 0; i < m; i++)
{
    var a = sc.ReadInt();
    players.Add((i, a));
}

// 最後に戦ったのが何回戦かを記録する
var ans = new int[m];
while (players.Count > 1)
{
    var next = new List<(int, int)>();
    for (int i = 0; i < players.Count; i += 2)
    {
        // 記録更新
        ans[players[i].Item1]++;
        ans[players[i+1].Item1]++;

        // 数字が大きい人が勝ち上がり
        if (players[i].Item2 > players[i + 1].Item2)
        {
            next.Add(players[i]);
        }
        else
        {
            next.Add(players[i + 1]);
        }
    }
    // 勝ち上がった選手に更新する
    players = next;
}

foreach (var item in ans)
{
    Console.WriteLine(item);
}

選手番号と数値をペアで持っておくと、最後に戦ったのが何回戦か記録できます。

以上、中級認定に必要な3問の振り返りでした。