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

第三回 アルゴリズム実技検定 – AtCoder

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

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

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

AtCoder が主催する アルゴリズム実技検定 の第三回に参加しました。第三回の検定はコロナウイルスの影響により無料開催となりました。

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

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

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

私の場合は第一回が中級、第二回上級81点、今回が上級88点でした。前回より1問多く溶けました。解けた問題の振り返り記事を書いていこうと思います。今回は上級認定に必要な J, K, L の3問について解説します。

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

J – 回転寿司

J – 回転寿司

寿司を食べたことのない N 人の子供たちが回転寿司屋にやってきました。 それぞれの子供には 1,2,3,…,N の番号がついています。

M 個の寿司が順番に流れてきます。i 番目に流れてくる寿司の美味しさは ai です。 寿司は 1,2,3,…,N 番の子供の前をこの順に通ります。

それぞれの子供は自分の前に寿司が流れてきたとき、以下のいずれかの条件を満たすときに限りその寿司を取って食べます。それ以外の場合は何もしません。

• まだ寿司を一つも食べていない
• 今までに食べたどの寿司よりも美味しさが大きい

それぞれの寿司について、何番の子供が食べるかを求めてください。

制約

• 与えられる入力は全て整数
• 1≤N≤10⁵
• 1≤M≤3×10⁵
• 1≤ai≤10⁹

子供たちは強欲なので、後ろの子が食べれてなくてもおいしいものはどんどん食べます。

寿司はM個が文字通りN人の前を流れていくので、愚直に全探索すると O(NM) かかりTLEします。なので工夫して高速に各寿司が誰に食べられるかを判定できるようにします。

前のほうにいる子供たちはおいしいものを独占します。後ろに回すのは自分が食べたものより美味しさが小さいものです。つまり前の子供より後ろの子供のほうが食べた美味しさの最大は小さくなります。つまり単調減少です。

流れてきたすしの美味しさをaiとすると、ai以下となる寿司しか食べたことのない子供のうち一番左の位置にいるのがこの寿司を食べる子供です。ここまで考察が進めば二分探索ができるとわかります。

例えば美味しさ3のすしが流れてきたとき、5人の子供がいて食べたの美味しさの最大それぞれが [9,7,3,2,0] だったとします。この状態で寿司を食べるか食べないかは以下のようにちょうど2つの区間に分かれます。

前>>>>>>後

9 7 3 2 0
<---> <-->

左側の区間は3以上なので食べない
右側の区間は3未満なので食べる

食べる区間の左端にいる子供が実際に流れてきた寿司を食べます。ちなみに0になっている子はまだ1つもお寿司を食べていない子です。

なお、流れてきたお寿司が誰にも食べられない場合もあります。 例えば5人に対して、5,4,3,2,1,1 と流れてきた場合、6個目の1は誰にも食べられません。

ということで実装します。

var N = sc.ReadInt();
var M = sc.ReadInt();
var max = new int[N]; // i番目の子供が食べた美味しさの最大
for (int i = 0; i < M; i++)
{
    var a = sc.ReadInt();

    // 寿司を食べた子供の中から
    // a未満の美味しさしか食べてない子供の左端を探す
    // [0, N) で探す
    var l = -1;
    var r = N;
    while (r - l > 1)
    {
        var mid = l + (r - l) / 2;
        var val = max[mid];
        if (val < a) r = mid;
        else l = mid;
    }
    if (r == N)
    {
        Console.WriteLine(-1);
    }
    else
    {
        max[r] = a;
        Console.WriteLine(r + 1);
    }
}

単純な二分探索です。計算量は O(MlogN) です。

結構単純な二分探索なので、中級の問題とあまり難易度的には変わらなかったかもしれません。

K – コンテナの移動

K – コンテナの移動

1,2,…,N の番号がついた N 個の机と、1,2,…,N の番号がついた N 個のコンテナがあります。 机の上には複数のコンテナを積み上げることができます。

はじめ、コンテナ i は机 i の上に置かれています。

Q 個のクエリが与えられるので、順番に処理してください。 i 番目のクエリでは机 fi にあるコンテナ xi とその上に積み上げられたコンテナたちを、机 ti に順番を変えずに移動させてください。

このとき、机 ti にすでにコンテナがある場合、以下の図のように既に積み上げられたコンテナたちの上にさらに積み上げるように移動させる必要があります。

※ここに画像

f=1,t=2,x=4 の例です。机 1 にあるコンテナ 4 とその上にあるコンテナ 2 を机 2 の上に動かします。机 2 の上にはコンテナ 3,5 が置かれているので、その上にさらに積み上げる必要があります。

Q 個のクエリを処理した後、それぞれのコンテナがどの机の上にあるかを求めてください。

制約

• 与えられる入力は全て整数
• 2≤N≤2×10⁵
• 1≤Q≤2×10⁵
• 1≤fi,ti,xi≤N
• fi≠ti
• コンテナ xi はクエリを処理する時点で机 fi 上にあることが保証される

クエリの数もコンテナの数も大きいので、移動させるたびにコンテナを1つずつ動かしていては実行時間が間に合いません。なので計算量O(1)でまとめて移動できるようにします。

ということで、コンテナを自分の下にあるコンテナと上にあるコンテナへの参照を持つ連結リストのノードとして管理するようにします。またコンテナxを高速に参照できるようにこれを配列に入れて別途保持しておきます。最後に、各机の一番上にあるコンテナも別途管理します。つまりコンテナxiは配列i番目の要素を、机tiの一番上にあるコンテナは机の配列のi番目の要素を参照すると得られます。

このようにコンテナを管理しておくと、移動処理が以下のように実装できます。

• コンテナxの下にあるコンテナを移動先の机の一番上のコンテナに更新する
• 移動先の一番上のコンテナをもともとコンテナxのあった机の一番上のコンテナにする
• もともとコンテナxの下にあったコンテナyの上にあるコンテナをnullにする
• もともとコンテナxのあった机の一番上のコンテナをコンテナyにする

最後に、各机の一番上にあるコンテナから再帰的に親をたどれば、最終的に各コンテナがどの机にあるかわかります。

static void Solve()
{
    var N = sc.ReadInt();
    var Q = sc.ReadInt();

    // x番目のコンテナの参照を格納する配列
    var containers = new Container[N];
    // ti番目の机の一番上のコンテナの番号
    var desktop = new int[N];
    for (int i = 0; i < N; i++)
    {
        containers[i] = new Container(i);
        desktop[i] = i;
    }
    for (int i = 0; i < Q; i++)
    {
        // 机fから机tにx番目のコンテナを移動する
        var f = sc.ReadInt();
        var t = sc.ReadInt();
        var x = sc.ReadInt();
        f--; t--; x--;

        // 移動処理
        var moveTop = desktop[f];
        desktop[f] = containers[x].Parent;
        if (desktop[f] != -1) containers[containers[x].Parent].Child = -1;
        containers[x].Parent = desktop[t];
        if (desktop[t] != -1) containers[desktop[t]].Child = x;
        desktop[t] = moveTop;
    }
    // 再帰的にすべてのコンテナの位置を求める
    var list = new int[N];
    for (int i = 0; i < N; i++)
    {
        if (desktop[i] != -1)
        {
            var q = new Queue<int>();
            q.Enqueue(desktop[i]);
            while (q.Count > 0)
            {
                var now = q.Dequeue();
                if (now == -1) continue;
                list[now] = i;
                q.Enqueue(containers[now].Parent);
            }
        }
    }
    // 出力
    foreach (var ans in list)
    {
        Console.WriteLine(ans + 1);
    }
}
class Container
{
    // x番目のコンテナ
    public int X;
    // 自分の下にあるコンテナ番号
    public int Parent;
    // 自分の上にあるコンテナ番号
    public int Child;
    public Container(int x)
    {
        this.X = x;
        this.Parent = -1;
        this.Child = -1;
    }
}

移動部分の参照差し替えのコードをバグらせて、実装に結構手間取ってしまいました。ノートに書いてみるなどして整理してから実装しましょう。

もしかしたらもっとスマートな実装があるかもしれません。

L – スーパーマーケット

L – スーパーマーケット

高橋君のスーパーマーケットには陳列棚があります。 この陳列棚には商品を並べられる列が N 本あり、それぞれの列には 1,2,…,N の番号がついています。 列 i には Ki 個の商品が手前から奥へと一列に並べられており、手前から j 番目の商品の消費期限は Ti,j です。

ここで、全ての商品の消費期限は相異なることが保証されます。

M 人の客が順番にやってきます。 i 番目にやってきた客は全ての列について現在の時点で手前から ai 番目までにある商品を見た後、見た商品のうち最も消費期限の値が大きいものを選んで棚から取って購入します。

それぞれの客について、購入した商品の消費期限の値を求めてください。

制約

• 与えられる入力は全て整数
• 1≤N≤10⁵
• 1≤Ki≤10⁵
• 1≤M≤∑Ni=1(Ki)≤3×10⁵
• 1≤Ti,j≤10⁹
• Ti,j は相異なる
• 1≤ai≤2

問題文を読んで難しくないか？と思ったのですが、制約を見るとaiは1か2しかなく、消費期限もそれぞれ異なるので何とかなりそうです。

コンテスト中の実装では平衡二分探索木を2個使って、とりうる範囲から一番大きい消費期限のデータを取り出せるようにしました。

平衡二分探索木1には1列目の商品が、平衡二分探索木2には1,2列目の商品が入っていて、常に最大の消費期限の商品が取り出せるようにします。平衡二分探索木から購入されたデータを取り出したら、別の平衡二分探索木からも削除するようにします。

こうすれば常に購入対象となる商品がそれぞれの平衡二分探索木で正しく管理できるようになります。

番兵として各列に消費期限がマイナスの商品を一番後ろに2つ追加しておくことにします。この商品が取り出されることはないので、配列外参照しなくなります。

あとどの陳列棚から取り出した商品化をわかるようにするため、平衡二分探索木に詰めるデータを (消費期限, 列番号) としてあげると簡単です。

ということで実装です。

var N = sc.ReadInt();
var T = new int[N][];
for (int i = 0; i < N; i++)
{
    var k = sc.ReadInt();
    T[i] = new int[k + 2];
    for (int j = 0; j < k; j++)
    {
        T[i][j] = -sc.ReadInt();
    }
    T[i][k] = int.MaxValue / 4;
    T[i][k + 1] = int.MaxValue / 4;
}
var count = new int[N];
var max1 = new Treap<(int, int)>();
var max2 = new Treap<(int, int)>();
for (int i = 0; i < N; i++)
{
    max2.Insert((T[i][0], i));
    max2.Insert((T[i][1], i));
    max1.Insert((T[i][0], i));
}
var M = sc.ReadInt();
for (int i = 0; i < M; i++)
{
    var a = sc.ReadInt();
    var t = (0, 0);
    if (a == 1) t = max1[0];
    else t = max2[0];
    var col = t.Item2;
    Console.WriteLine(-t.Item1);
    count[t.Item2]++;
    if (max1.ValueCount(t) > 0)
    {
        var v2 = T[t.Item2][count[col]];
        var v3 = T[t.Item2][count[col] + 1];
        max1.Insert((v2, col));
        max2.Insert((v3, col));
    }
    else
    {
        var v2 = T[col][count[col]];
        var v3 = T[col][count[col] + 1];
        if (max1.ValueCount(t) > 0)
        {
            max1.Insert((v2, col));
        }
        max2.Insert((v3, col));
    }
    max1.Erase(t);
    max2.Erase(t);
}

実装が複雑怪奇になってますが、コンテスト中にがちゃがちゃ手を動かしすぎた結果です。復習しないとですね。

平衡二分探索木は Treap を自前実装したクラスを使ってます。

歯ごたえのある問題でした。ここまで12問解けて上級です。PASTには後3問あり、14問解けるとエキスパートです。