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

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

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

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

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

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

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

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

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

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

私の場合は第一回が中級で、今回は81点の上級でした。せっかくなので解けた問題の振り返り記事を書いていこうと思います。この記事では初級認定に必要な問題ABCDEFの6問を振り返ります。ちなみにC問題まで解けてエントリーです。

初級までの問題は基本的には問題文に書いてあることを正確にコードに落とし込むスキルが問われます。アルゴリズム的には全探索がすべてだと思ってもよいです。と思ってたらF問に優先度付きキューの問題もありました。結構実装も大変だったりで難しめの問題だと思いました。

ただ検定時間が5時間と長くペナルティもないので、実装よりの問題は普段のコンテストより解きやすくなっていると思います。

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

A – エレベーター

A – エレベーター

下から順に B9, B8, …, B1, 1F, 2F, …, 9F と呼ばれる 18 のフロアを持つ建物があります。

この建物のエレベーターは、隣接する 2 つのフロア間の移動に常に 1 秒を要します。例えば、B9 から 9F への移動には 17 秒を要し、反対方向も同様です。

2 つのフロア S, T が与えられます。エレベーターが S から T へ移動するには最短で何秒を要するでしょうか。

制約

• S, T はいずれも B1,B2,B3,B4,B5,B6,B7,B8,B9,1F,2F,3F,4F,5F,6F,7F,8F,9F のいずれかである
• S と T は等しくない

文字列でフロア表記が2つ与えられるので、そのフロア間の移動にかかる時間を求めるという問題です。簡単な問題ですが、実装がちょっと面倒くさいです。

実装方法としてはB9から9Fまでの文字列をすべて配列に入れておき、与えられた文字列に一致するインデックスを探し、その差の絶対値が答えになります。制約の部分は順番が違っているのでコピーするのは注意が必要です。

// 入力
var S = sc.ReadStr();
var T = sc.ReadStr();
var a = new string[] 
{ 
    "B9", "B8", "B7", "B6", "B5", "B4", "B3", "B2", "B1", 
    "1F", "2F", "3F", "4F", "5F", "6F", "7F", "8F", "9F" 
};
var ans = Math.Abs(Array.IndexOf(a, S) - Array.IndexOf(a, T));
Console.WriteLine(ans);

B – 多数決

B – 多数決

ある国で選挙が行われました。候補者は a, b, c の 3 名です。

投票されたすべての票を表す文字列 S が与えられます。S は英小文字 a, b, c からなり、S の i 文字目は i 番目の投票者が投票した候補者を表します。最多得票を得た候補者は誰か求めてください。

なお、最多得票を得た人物はちょうど 1 名であることが保証されています。

制約

• 1≤|S|≤1000
• S は a, b, c からなる文字列である
• 最多得票を得た人物はちょうど 1 名

文字列Sの中に一番多く含まれる文字を答えればOKです。文字は a,b,c の3つなのでこのいずれかが答えになります。

文字を数字に対応付けるには、英小文字の場合だと c - 'a' で a,b,c,d..z がちょうど 0,1,2,3..25 の数字に変換できます。競技プログラミングだとよく使うテクニックです。

var S = sc.ReadStr();

// Sに含まれるa,b,cを数え上げる
var count = new int[3];
foreach (var c in S)
{
    count[c - 'a']++;
}
// 最多得票数
var max = count.Max();
for (int i = 0; i < 3; i++)
{
    if (count[i] == max)
    {
        // 最多得票の文字を出力して終了
        Console.WriteLine((char)('a' + i));
        return;
    }
}

C – 山崩し

C – 山崩し

整数 2≤N≤50 に対して、縦 N マス、横 2N−1 マスのマス目があります。

上から i 行目、左から j 列目のマスをマス (i,j) と表します。

このマス目は白黒の 2 色で 山型 に塗られています。具体的には、|j−N|<i を満たす 1≤i≤N,1≤j≤(2N−1) についてはマス (i,j) は黒く塗られており、他のマスは白く塗られています。

下は N=5 の場合の例です。(# は黒く塗られたマス、. は白く塗られたマスを表します)

....#....
...###...
..#####..
.#######.
#########

ここで、黒く塗られたマスのうちいくつかに X を書きます。

書き込んだ後の状態は文字からなるサイズ N×(2N−1) の 2 次元配列 S として与えられ、Si,j がマス (i,j) の状態を表します。Si,j が X のとき、マス (i,j) は X の書かれた黒く塗られたマスであり、Si,j が # のとき、マス (i,j) は X の書かれていない黒く塗られたマスであり、Si,j が . のとき、マス (i,j) は白く塗られたマスです。

それから、i=N−1,N−2,⋯,1 の順番で次の操作を行います。2≤j≤2N−2 に対して、マス (i,j) が黒く塗られているが X は書かれておらず、マス (i+1,j−1),(i+1,j),(i+1,j+1) のうち 1 つ以上に X が書かれているとき、マス (i,j) に X を書く。全ての操作を終えた後のマス目の状態を計算してください。

制約

• 2≤N≤50
• Si,j は . または # または X
• S に対応するマス目の状態は、山型に塗られたマス目の黒く塗られたマスのうち 1 つ以上に X を書くことで得られる

いろいろと難しい感じに長い問題文が続きますが、やるべきことは下の段から順番に見ていき、真下か斜め下にXがあればそのマスをXに書き換えるという操作です。これを下段から上段に向かって順番にシミュレーションすればOKです。このシミュレーションを行うと、最初下のほうにXがあったとするとどんどん上にXか増えていきます。

最終的に書き換えられた山を出力して完成です。

// 入力は文字列の配列で受け取る
var N = sc.ReadInt();
var S = sc.ReadStrArray(N);

// 最終的に出力するデータが格納された配列
// 入力時の状態にしておく
var ans = new char[N, 2 * N - 1];
for (int i = 0; i < N; i++)
{
    for (int j = 0; j < 2 * N - 1; j++)
    {
        ans[i, j] = S[i][j];
    }
}

// 下段から見ていく(一番下の段は書き換えられないので見ない)
for (int i = N - 2; i >= 0; i--)
{
    // 端から見ていく
    for (int j = 1; j < 2 * N - 2; j++)
    {
        // 書き換えられるのは # のマスだけ
        if (S[i][j] != '#') continue;

        // 真下、右下、左下のいずれかが X かどうか
        if (ans[i + 1, j - 1] == 'X' || ans[i + 1, j] == 'X' || ans[i + 1, j + 1] == 'X')
            ans[i, j] = 'X';
    }
}

// 出力
for (int i = 0; i < N; i++)
{
    for (int j = 0; j < 2 * N - 1; j++)
    {
        Console.Write(ans[i, j]);
    }
    Console.WriteLine();
}

これも与えられた操作をきっちりとコードに落とし込めるかを試すような問題でした。

問題文をよく読みましょう。配列の横幅のサイズを2Nにして制御文字を出力してコンテスト中にWAを連発しました。

D – パターンマッチ

D – パターンマッチ

英小文字から成る文字列 S が与えられます。

英小文字または . から成る長さ 1 以上 3 以下の文字列 T が S にマッチするとは、次の条件を満たすことを表します。

T の長さを K とする。 S の連続する K 文字であって、T の . を自由にそれぞれ英小文字 1 文字に置き換えることで一致するような部分が存在する。英小文字または . から成る長さ 1 以上 3 以下の文字列全てのうち、S にマッチするものの個数を求めてください。

制約

• 1≤|S|≤100
• S は英小文字から成る

Sの文字数が小さいので全パターンを試しても十分間に合います。

var S = sc.ReadStr();
var set = new HashSet<string>();

// 1文字のパターン
for (int i = 0; i < S.Length; i++)
{
    set.Add(S.Substring(i, 1));
    set.Add(".");
}
// 2文字のパターン
for (int i = 0; i < S.Length - 1; i++)
{
    // ".." "XX" "X." ".X" 
    var s = S.Substring(i, 2);
    set.Add(s);
    set.Add(s[0] + ".");
    set.Add("." + s[1]);
    set.Add("..");
}
// 3文字のパターン
for (int i = 0; i < S.Length - 2; i++)
{
    // "..." "XXX" "XX." "X.X" ".XX" "X.." ".X." "..X" 
    var s = S.Substring(i, 3);
    set.Add(s);
    set.Add("" + s[0] + s[1] + ".");
    set.Add(s[0] + "." + s[2]);
    set.Add("." + s[1] + s[2]);
    set.Add(s[0] + "..");
    set.Add("." + s[1] + ".");
    set.Add(".." + s[2]);
    set.Add("...");
}

var ans = set.Count();
Console.WriteLine(ans);

文字列の1-3文字の部分文字列をすべて列挙し、それを “.” に置き換えた文字列をすべて HashSet<string> に追加します。これでマッチする文字列すべてが列挙できます。

最後にカウントをとると、重複を除いたマッチする文字列の数が得られます。

絶対にもっとスマートな解法があると思いますが、まあ計算量的にも間に合うしOKでしょう。

解説PDFによると、すべてのパターンを列挙し、それをマッチさせてすべて数える方法となってました。

E – 順列

E – 順列

1,2,…,N の順列 A1,A2,…,AN が与えられます。

各整数 1≤i≤N に対して、次の条件を満たす 1 以上の整数 j として考えられる最小の値を求めてください。

• x=i とする。x を Ax で置き換えるという操作をちょうど j 回行った後、x=i となる。

制約

• 1≤N≤100
• 1≤Ai≤N
• Ai≠Aj(i≠j)
• 入力は全て整数

問題がよくわからないですが、とりあえず言われたことを実装しましょう。問題文では 0-indexed になっているので、その点注意しましょう。

var N = sc.ReadInt();
var A = sc.ReadIntArray(N);

// 各Aiを操作して得られる最小の値を格納する配列
var B = new int[N];

// 各要素について、条件を満たすまで操作を繰り返す
for (int i = 0; i < N; i++)
{
    var j = 0;
    var x = i + 1;
    while (true)
    {
        // x = i となるまで x を Ax で置き換える
        j++;
        x = A[x - 1];
        if (x == i+1) break;
    }
    B[i] = j;
}
var ans = string.Join(" ", B);
Console.WriteLine(ans);

F – タスクの消化

F – タスクの消化

N 個のタスクがあります。i 個目のタスクは Ai 日目 (今日を 1 日目とします) またはそれ以降に実行することができ、消化することで Bi ポイントが得られます。

あなたは、これから 1 日ごとに、「タスクを一つ選んでそれを消化する」という行為を繰り返します。 1 以上 N 以下のすべての整数 k に対して、これから k 日間で得られるポイントの合計の最大値を求めてください。

ただし、1 以上 N 以下のすべての整数 k に対して、k 日目までに実行することのできるタスクが k 個以上存在することが保証されています。

制約

• 1≤N≤2×10⁵
• 1≤Ai≤N1≤Bi≤100
• 入力中のすべての値は整数である。

ここにきて急に競技プログラミングチックな問題が出てきました。

毎日タスクを1つ消化できるが、Ai日以降にしか実行できないという制約があるタスクです。Ai日以降という制約がなければソートして大きいほうから順番にタスクを消化していけばいいですが、ここではそうは行きません。

i日目に消化するタスクは、その時点で消化できるタスクの中から最もポイントの大きいものを選びたいです。

しかし、毎日実行できるタスクを集めてソートして最高ポイントのタスクを消化するという選択も取れません。都度ソートしては O(N*NlogN) くらいかかり計算が間に合いません。

ここで使えるのが優先度付きキューです。優先度付きキューに現時点で実行できるタスクを詰め込み、最高ポイントの得られるタスクを取り出せるようにすればこの問題を解くことができます。

var N = sc.ReadInt();

// i日目以降に実行できるタスクのポイントを管理するリスト
var tasks = new List<int>[N + 1];
for (int i = 0; i < N + 1; i++)
{
    tasks[i] = new List<int>();
}
for (int i = 0; i < N; i++)
{
    // a日目以降にポイントbで実行できる
    var a = sc.ReadInt();
    var b = sc.ReadInt();
    tasks[a].Add(b);
}

// 現時点で実行できるタスクを管理する優先度付きキュー
var q = new PriorityQueue<int>();
// これまで実行したタスクのポイント合計
var sum = 0;

// i日目について
for (int i = 1; i < N + 1; i++)
{
    // i日目以降に実行できるタスクを優先度付きキューに入れる
    foreach (var t in tasks[i])
    {
        q.Enqueue(t);
    }
    // 現時点i日目で実行できるタスクから
    // 最も大きいポイントのタスクを実行する
    if (q.Count > 0) sum += q.Dequeue();

    // i日間で得られるポイントの合計
    Console.WriteLine(sum);
}

優先度付きキューは、詰め込んだデータの最大or最小を取り出せるデータ構造です。今回はタスクのポイントが大きいデータを取り出すようにしました。

データの追加、取り出しにはデータ数をNとすると、それぞれ O(logN) かかります。今回はデータの追加と取り出しがN回行われるので、計算量が O(NlogN) になります。

優先度付きキューについては C++ だと標準ライブラリに用意されていますが、C#だとそんなものはありません。なので自分で作らなければなりません。今回使用した優先度付きキューのクラスは以下の通りです。

class PriorityQueue<T>
{
    public int Count;
    private int Capacity;
    private bool IsMaxHeap;
    private T[] Buffer;
    private IComparer<T> Cmp;
    public PriorityQueue(bool isMaxHeap = true, IComparer<T> cmp = null)
    {
        Count = 0;
        Capacity = 1 << 10;
        IsMaxHeap = isMaxHeap;
        Buffer = new T[Capacity];
        if (cmp != null) Cmp = cmp;
        else Cmp = Comparer<T>.Default;
    }
    private void Resize()
    {
        Capacity <<= 1;
        Array.Resize(ref Buffer, Capacity);
    }
    public void Enqueue(T value)
    {
        if (Count == Capacity) Resize();
        Buffer[Count] = value;
        Count++;
        UpHeap();
    }
    public T Dequeue()
    {
        var res = Buffer[0];
        Swap(0, Count - 1);
        Count--;
        DownHeap();
        return res;
    }
    public T Peek() { return Buffer[0]; }
    private void Swap(int i, int j)
    {
        var tmp = Buffer[i];
        Buffer[i] = Buffer[j];
        Buffer[j] = tmp;
    }
    private void UpHeap()
    {
        var n = this.Count - 1;
        while (n != 0)
        {
            var parent = (n - 1) / 2;
            if (Compare(Buffer[n], Buffer[parent]) > 0)
            {
                Swap(n, parent);
                n = parent;
            }
            else break;
        }
    }
    private void DownHeap()
    {
        var parent = 0;
        while (true)
        {
            var child = 2 * parent + 1;
            if (child > this.Count - 1) break;
            if (child < Count - 1 && Compare(Buffer[child], Buffer[child + 1]) < 0)
            {
                child += 1;
            }
            if (Compare(Buffer[parent], Buffer[child]) < 0)
            {
                Swap(parent, child);
                parent = child;
            }
            else break;
        }
    }
    private int Compare(T x, T y)
    {
        var res = Cmp.Compare(x, y);
        if (!IsMaxHeap) res *= -1;
        return res;
    }
}

データ数は動的に増やせるようにしています。あと比較関数を渡せば独自の型でも詰め込めます。今回は整数型なので new PriorityQueue<int>(); みたいにして初期化すればOKです。用意されているメソッドは Queue と同じ感じです。

[C#][VB] 優先度付きキューを実装する方法 │ Web備忘録

実装の詳細は上の記事を確認してください。