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

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

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

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

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

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

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

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

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

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

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

上級向けの問題はさすがに難しくなってきます。実装、アルゴリズム、閃き、そんな感じのセットでした。ですがあまりにアルゴリズムっぽい問題はDP以外出題されてないので、普段苦戦する問題よりかは易しく感じます。これは普段のコンテストで出る数学ひらめき系問題よりもかなり実装によった出題傾向にあるからだと思います。個人的には取り組みやすいです。

検定はこの3問解いた時点で残り30分とかだったと思います。上級認定だったので気持ちよく終わりました。

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

J – 文字列解析

J – 文字列解析

英小文字 a ~ z と ( と ) からなる文字列 S が与えられます。 ある文字列 a と b に対して a+b を a と b をこの順に結合した文字列とします。 また、ある文字列 a に対して rev(a) を a を反転させた文字列とします。 以下の操作をこれ以上操作が行えなくなるまで繰り返し行ったときの、最終的な文字列 S を出力してください。

• ( や ) を含まない文字列 a (空文字列でもよい) に対して ( +a+ ) のような部分文字列が S の中にあったときに、 その部分文字列を a+rev(a) に置き換える

ただし、文字列 S で正しい括弧の対応が取れていること、すなわち最終的な文字列 S に ( や ) は含まれないことが保証されています。また、この条件下で最終的な文字列は一意に定まることが示せます。

制約

• S は長さ 1 以上 1000 以下の、英小文字 a ~ z と ( と ) からなる文字列である。
• S は 1 文字以上の英小文字を含む。
• 操作をこれ以上操作が行えなくなるまで繰り返し行ったときの、最終的な文字列 S の長さは 1000 以下であり、これに( や ) は含まれない。

これは再帰関数で文字列を置き換えていけばよいです。i文字目から見ていき、'(' があれば再帰的に処理するようなイメージです。

最終的な文字列が1000以下という制約なので、再帰をうまく実装できれば文字列を愚直に連結や反転を行っても計算量的には問題になりません。

var S = sc.ReadStr();

// n文字目をから末尾もしくは')'まで探索
// 終了後の位置と解析した文字列を返す
(int, string) Rec(int n)
{
    var a = "";
    while (n < S.Length)
    {
        if (S[n] == '(')
        {
            // カッコの中の文字を再帰的に処理
            var res = Rec(n + 1);
            n = res.Item1;
            a += res.Item2;
        }
        else if (S[n] == ')')
        {
            // 再帰終了
            // a+rev(a)と終了位置を返す
            var na = a + new string(a.Reverse().ToArray());
            return (n, na);
        }
        else
        {
            // 見つかった文字を記録
            a += S[n];
        }
        n++;
    }
    return (n, a);
}

var ans = Rec(0).Item2;
Console.WriteLine(ans);

こういう実装をスマートにできる人に憧れます。

K – 括弧

K – 括弧

( と ) からなる長さ N の文字列 S が与えられます。S の i 番目の文字を Si で表します。

以下の手順で S を 括弧の対応が取れている文字列 (後述) にすることを考えます。

まず、次の操作を 0 回以上好きなだけ行います。

• 1≤i≤N を選ぶ。Si が ( ならば ) に、) ならば ( に変更する。この操作のコストは Ci である。

その後、次の操作を行います。

• S から 0 文字以上選んで削除し (全ての文字を削除しても良い)、削除しなかった文字を元の順序で繋げる。S の i 文字目を削除するコストは Di である。

S を括弧の対応が取れている文字列にするための合計コストの最小値を求めてください。

なお、括弧の対応が取れている文字列とは、次のうちいずれかの条件を満たす文字列です。

• 空文字列
• ある括弧の対応が取れている空でない文字列 A,B が存在し、 A , B をこの順に連結した文字列
• ある括弧の対応が取れている文字列 A が存在し、 (, A, ) をこの順に連結した文字列

制約

• 1≤N≤3000
• S の長さは NS の各文字は ( または )
• 1≤Ci≤10⁹
• 1≤Di≤10⁹
• N,Ci,Di は整数

与えられた文字列について、最終的に '(' と ')' の数が等しくなるように、書き換えるか削除するかしなければなりません。さらに左から '(' を見つけたら+1, ')' を見つけたら-1として計算した時、負の数になるような文字列は条件を満たしません。つまり "())(" みたいな文字列はカッコの数は等しいですが、左から順番に見たときに3文字目の ')' の時点で対応が取れていないことがわかります。

ということで、左から見ていき、書き換える操作と削除する操作をシミュレートすることを考えます。そのとき、現時点で対応の取れてない '(' の数を数えておき、')' の数をそれ以上にしないようにします。これを dp でシミュレートします。

漸化式は以下の通りです。

dp[i][j] = i文字目まででj個未対応の'('が見つかっている状態になる最小コスト

遷移の際にjが負の数になるような遷移は前述の通り許されません。最終的に対応の取れていないカッコを0にしたいので dp[N][0] が答えになります。計算量は O(N2) です。

ということで実装です。

var N = sc.ReadInt();
var S = sc.ReadStr();
var C = sc.ReadLongArray(N);
var D = sc.ReadLongArray(N);

var inf = long.MaxValue / 2;
var dp = new long[N + 1, N + 1];
for (int i = 0; i < N + 1; i++)
{
    for (int j = 0; j < N + 1; j++)
    {
        dp[i, j] = inf;
    }
}
dp[0, 0] = 0;

// dp[i, j] = i文字目まででj個対応してない '(' が見つかっている状態の最小コスト
for (int i = 0; i < N; i++)
{
    for (int j = 0; j < N; j++)
    {
        if (dp[i, j] >= inf) continue;

        // 削除、書き換え、そのままの時の対応の取れていない(の数
        var nj0 = j;
        var nj1 = j + (S[i] == '(' ? -1 : 1);
        var nj2 = j + (S[i] == '(' ? 1 : -1);

        // 削除する
        if (nj0 >= 0)
            dp[i + 1, nj0] = Math.Min(dp[i + 1, nj0], dp[i, j] + D[i]);
        // 書き換える
        if (nj1 >= 0)
            dp[i + 1, nj1] = Math.Min(dp[i + 1, nj1], dp[i, j] + C[i]);
        // そのまま
        if (nj2 >= 0)
            dp[i + 1, nj2] = Math.Min(dp[i + 1, nj2], dp[i, j]);
    }
}

var ans = dp[N, 0];
Console.WriteLine(ans);

コンテスト中にはメモ化再帰で解きました。基本的な漸化式の立て方？はあってたので良かったです。コンテスト中はメモ化再帰でしかDPを解いたことがないです。

L – 辞書順最小

L – 辞書順最小

長さ N の整数列 A1,A2,⋯,AN があります。ここから K 個の要素を選び、それらを相対的な順序を保ったまま並べて新しい数列を作るという操作を考えます。ただし、Ai と Aj (i≠j) をともに選べるのは |i−j|≥D であるときに限ります。

この操作で作ることのできる数列のうち、辞書順で最小である数列を求めてください。そのような操作が不可能である場合は −1 を出力してください。

なお、長さ K の数列 x1,x2,⋯,xK が y1,y2,⋯,yK より辞書順で小さいとは、二つの数列が異なり、かつ i を xi≠yi であるような最小の整数としたとき xi<yi であることをいいます。

制約

• 2≤N≤2×10⁵
• 1≤D≤N
• 1≤K≤N
• 0≤Ai≤10⁹
• 入力は全て整数

辞書順最小を求めるには、選べる区間から最も小さい数を貪欲に選び続けるのがよいです。また、最小の数が複数ある場合は最も左側から選びます。選べる区間を愚直にループして探索しては計算量が O(N2) になってTLEします。

つまり、ある区間の最小値を左側優先で高速に取り出すことができればこの問題を解くことができます。

区間最小値を取り出せるデータ構造として、今回は SparseTable というデータ構造を使いますが Segment Tree でも可能です。SparseTable は前計算をO(NlogN) で行っておけば区間の最小値を O(1) で求められます。

あとは選べる区間の考え方ですが、例えば N=5, D=2, K=2の時は、次の区間から1つ目の数を選ばなければなりません。

a0 a1 a2 a3 a4 a5
<--------->

もしa4やa5を1つ目の数として選ぶと、2つ目の数が選べなくなります。こんな感じで区間をいい感じに定めてK回区間最小値を求めれば、それが辞書順最小の数列になります。

与えられた条件のもとN個からK個選ぶには K + (K - 1) * (D - 1) がNより小さくなくてはいけません。K個 + 選ぶときの間隔が(K - 1) * (D - 1)になります。これがKを超えるとき、左から詰めて選んでも選びきることができません。これがわかれば残りrem個の時にどこまで選べるかはわかると思います。

詳細はコードを見てください。

// 入力
var N = sc.ReadInt();
var K = sc.ReadInt();
var D = sc.ReadInt();
var A = sc.ReadLongArray(N);
var AwithIndex = new (long, int)[N];
for (int i = 0; i < N; i++)
{
    AwithIndex[i] = (A[i], i);
}

// K個選べない場合
if (K + (K - 1) * (D - 1) > N)
{
    Console.WriteLine(-1);
    return;
}

// 構築した数列
var list = new List<long>();

// 配列Aの区間最小値を求めるスパーステーブルを構築する
var st = new SparseTable<(long, int)>(AwithIndex);

// 残りrem個選ばなければいけない
var rem = K;

// 今の状態から選べる区間の左端インデックス
var l = 0;
while (rem > 0)
{
    // 残りrem個選ぶときに選べる区間の右端
    var r = N - (rem - 1) * (D - 1) - rem + 1;

    // 区間[l, r)から最小値とそのインデックスを取得
    var tup = st.GetValue(l, r);
    list.Add(tup.Item1);

    // 次に選べる区間の左端を更新
    l = tup.Item2 + D;
    rem--;
}

var ans = string.Join(" ", list);
Console.WriteLine(ans);

スパーステーブル本体はこんな感じです。

class SparseTable<T> where T : IComparable
{
    private T[] A;
    private int[,] Table;
    private int[] LogTable;
    private int N;
    private bool IsMin;
    public SparseTable(T[] a, bool min = true)
    {
        A = a;
        IsMin = min;
        N = a.Length;
        CreateTable();
    }
    private void CreateTable()
    {
        LogTable = new int[N + 1];
        for (int i = 2; i < N + 1; i++)
        {
            LogTable[i] = LogTable[i >> 1] + 1;
        }

        Table = new int[N, LogTable[N] + 1];
        for (int i = 0; i < N; i++)
        {
            Table[i, 0] = i;
        }

        for (int k = 1; (1 << k) <= N; k++)
        {
            for (int i = 0; i + (1 << k) <= N; i++)
            {
                var indexL = Table[i, k - 1];
                var indexR = Table[i + (1 << (k - 1)), k - 1];
                Table[i, k] = Compare(A[indexL], A[indexR]) <= 0 ? indexL : indexR;
            }
        }
    }
    private int Compare(T a, T b)
    {
        return IsMin ? a.CompareTo(b) : b.CompareTo(a);
    }
    public T GetValue(int l, int r)
    {
        var k = LogTable[r - l];
        var indexL = Table[l, k];
        var indexR = Table[r - (1 << k), k];
        return Compare(A[indexL], A[indexR]) <= 0 ? A[indexL] : A[indexR];
    }
}

スパーステーブルとは何ぞやという人は以下の記事に詳細があるので確認してください。

SparseTable の実装と解説 [C#] │ Web備忘録

検定前に調べてたので役立ってうれしかったです。

比較な可能なデータであればスパーステーブルに詰め込めるようにしています。今回は (long, int) のタプルにして値とインデックスのペアで持たしています。タプルは左側の値を優先で比較が行われます。C++とかと同じですね。こうすることで区間の最小かつインデックスの最小のデータが取り出せるようになります。

解説PDFによると、優先度付きキューを用いて最小値を管理しておく方法があるみたいです。たしかに1度区間外になった要素はそれ以降も利用しないので、取り出しても捨てるようにすればよさそうですね。

以上。