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

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

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

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

  • 1. 第三回アルゴリズム実技検定
  • 2. G – グリッド金移動
  • 3. H – ハードル走
  • 4. I – 行列操作

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

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

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

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

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

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

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

G – グリッド金移動

G – グリッド金移動

無限に広がる二次元グリッドがあります。 すぬけ君ははじめマス (0,0) にいます。 障害物のあるマスが N 個あり、すぬけ君は障害物のあるマスに移動することができません。i 番目の障害物はマス (xi,yi) にあります。 すぬけ君の現在位置をマス (x,y) としたとき、一回の移動で以下の 6 箇所のうちいずれかに移動できます。

(x+1,y+1)(x,y+1)(x−1,y+1)(x+1,y)(x−1,y)(x,y−1)最小で何回移動するとマス (X,Y) に到達できるか出力してください。到達することが不可能であれば −1 を出力してください。

制約

• 入力はすべて整数
• 1≤N≤800
• −200≤xi,yi,X,Y≤200
• (xi,yi) は相異なる。つまり、同じマスに 2 個以上の障害物はない。
• (0,0) および (X,Y) には障害物はない
• (X,Y)≠(0,0)

グリッドグラフ上での最短経路問題です。移動は8近傍ではなく、右斜め上と左斜め上には移動できないことに注意します。

最短経路問題として解きたいですが、無限に広がる二次元グリッドとあるのでこのままでは解けません。

ただし、冷静に考えると、障害物がないのに大回りする経路をとる必要はありません。例えば(-200, -200)にある障害物を避けるのに(-1000, -1000)まで移動することはどう考えても必要はありません。今回は障害物は-200から200の範囲までにしか存在しないのでなので、多少余裕を見て±20くらいの範囲だけを考えるようにします。

最短経路問題として解きますが、移動コストは常に1なので、単純な幅優先探索で経路を求めることができます。ただ、障害物の座標で負の数を扱うのが面倒なので+210して全部正の数にしてしまいましょう。こうすれば二次元配列で保持できます。BFSで使う到達済フラグの管理にも同様に二次元配列に直します。

以上の通り、「二次元グリッドで扱う範囲を制限する」と「負の数を全部正の数にして扱う」の2つの方針で実装します。

var N = sc.ReadInt();
// ゴールも+210しておく
var X = sc.ReadInt() + 210;
var Y = sc.ReadInt() + 210;
// 障害物の位置を覚えておく
var blocks = new bool[440, 440];
for (int i = 0; i < N; i++)
{
    var x = sc.ReadInt();
    var y = sc.ReadInt();
    x += 210; y += 210;
    blocks[x, y] = true;
}
// 到達したかどうかを覚えておく。
var visited = new bool[440, 440];
// (0, 0)も+210しておく
// 幅優先探索で(210, 210)から開始する
var q = new Queue<(int, int, int)>();
visited[210, 210] = true;
q.Enqueue((210, 210, 0));
while (q.Count > 0)
{
    var t = q.Dequeue();
    var (x, y, cost) = t;
    // ゴールに到着したら出力
    if (x == X && y == Y)
    {
        Console.WriteLine(cost);
        return;
    }
    // いい感じにループで8方向への移動を処理する
    var dx = new int[] { -1, 0, 1, 0, 1, 1, -1, -1 };
    var dy = new int[] { 0, -1, 0, 1, 1, -1, -1, 1 };
    for (int d = 0; d < 8; d++)
    {
        // 右上と左下には移動しない
        if (dx[d] == -1 && dy[d] == -1) continue;
        if (dx[d] == 1 && dy[d] == -1) continue;

        // 移動先(nx, ny)
        var nx = x + dx[d];
        var ny = y + dy[d];
        // 移動先の座標が範囲内かどうか
        if (0 <= nx && nx < 440 && 0 <= ny && ny < 440)
        {
            // すでに到達しているもしくは障害物があれば無視
            if (visited[nx, ny]) continue;
            if (blocks[nx, ny]) continue;
            // 到達フラグを立ててからキューに追加
            visited[nx, ny] = true;
            q.Enqueue((nx, ny, cost + 1));
        }
    }
}
// 移動可能な座標すべてに移動してもゴールにたどり着かなかった場合
Console.WriteLine(-1);

障害物のフラグと到達フラグを HashSet<(int, int) にしてもたぶん大丈夫だと思います。ただタプルのハッシュはどれぐらい衝突するかわからないので整数にして配列で持ってます。こうすれば参照するのに常に O(1) です。

グリッドグラフである座標に隣接する上下左右4近傍の座標や同じく8近傍の座標を簡単にfor文で求められる以下のコードが便利です。いつかのABC解説放送で見かけたのですが、これを知るまでif文を大量に書いてました。

// 上、右、下、左の順に4近傍をループする
var dh = new int[] { -1, 0, 1, 0 };
var dw = new int[] { 0, -1, 0, 1 };
for (int d = 0; d < 4; d++)
{
    // 次の移動先となる座標(nh, nw)
    var nh = h + dh[d];
    var nw = w + dw[d];
    if (0 <= nh && nh < H && 0 <= nw && nw < W)
    {
        // 範囲内の場合はここのブロックに処理を書く...
    }
}

覚えておくと便利です。

H – ハードル走

H – ハードル走

すぬけ君は数直線上でハードル走をします。 座標 0 がスタート地点、座標 L がゴール地点です。 数直線上には N 個のハードルがあり、左から i 番目のハードルは座標 xi にあります。(0<x1<x2<⋯<xN<L が成立します。)

すぬけ君は、以下の 3 種類の行動のうち一つを選んで実行する、ということを繰り返し行うことができます。

• 行動 1: 距離 1 を走って進む。
• 行動 2: 距離 0.5 を走って進み、ジャンプして距離 1 を進み、また距離 0.5 を走って進む。合計で 2 の距離を進むことになる。
• 行動 3: 距離 0.5 を走って進み、ジャンプして距離 3 を進み、また距離 0.5 を走って進む。合計で 4 の距離を進むことになる。

すぬけ君は、走っているときは距離 1 あたり T1 秒、ジャンプ中は距離 1 あたり T2 秒の速さで進みます。ただし、すぬけ君がジャンプ中でないときに座標 x にいて、座標 x にハードルがある場合、その地点を通り過ぎるのに追加で T3 秒の時間がかかります。T1,T2,T3 は全て偶数です。

すぬけ君が座標 L を通るまでにかかる秒数の最小値を求めてください。(座標 L をジャンプして通過する場合は、ジャンプ中に座標 L を通過するまでの秒数が「座標 L を通るまでにかかる秒数」です。) 答えは整数であることが証明できます。

制約

• 入力は全て整数
• 2≤L≤10⁵
• 1≤N<L
• 0<x1<x2<⋯<xN<L
• 2≤T1,T2,T3≤1000
• T1,T2,T3 は偶数

問題を読んで思ったのは以下にもDPを使いそうな問題だということです。各座標において3つの行動による遷移があり得ます。

ただしこの問題でややこしいのは行動2と3において行動途中にゴールをまたぐ場合があるということです。その場合はゴールに到達した瞬間までの時間で答えを求めろとのことなので、その点考慮が必要です。さらに距離0.5の移動という中途半端な数字があっていやな気になりますが、0.5の移動は移動時間がすべて偶数なのでうまく処理できます。

ということでDPテーブルを

dp[i] = 座標iで行動可能なときの最小の経過時間

とします。

さらにLをまたぐ行動ではぴったりLに到達する時間の計算を別途処理します。

• 0.5走るときは T1/2
• 0.5ジャンプするには T2/2

ということを理解できればあとはジャンプ中にLを通過する場合も計算可能です。走りながらLを通過するのは各行動終了後のみなのでこれは無視できます。

実装してみます。

var N = sc.ReadInt();
var L = sc.ReadInt();
var hurdle = new bool[L];
for (int i = 0; i < N; i++)
{
    var x = sc.ReadInt();
    hurdle[x] = true;
}
var T1 = sc.ReadInt();
var T2 = sc.ReadInt();
var T3 = sc.ReadInt();
// 大きめにDPテーブルを保持しておく(初期値=INF)
var dp = new int[L + 10];
for (int i = 0; i < L + 10; i++)
{
    dp[i] = int.MaxValue / 2;
}
// 座標0を移動時間0にしておく
dp[0] = 0;
for (int i = 0; i < L; i++)
{
    // ハードルがあるときの追加コスト
    var additionalCost = hurdle[i] ? T3 : 0;
    // 行動 1: 距離1 を走って進む。
    dp[i + 1] = Math.Min(dp[i + 1], dp[i] + T1 + additionalCost);
    // 行動 2: 距離0.5 を走って進み、ジャンプして距離1 を進み、また距離0.5 を走って進む。合計で2 の距離を進むことになる。
    dp[i + 2] = Math.Min(dp[i + 2], dp[i] + T1 + T2 + additionalCost);
    // 行動 3: 距離0.5 を走って進み、ジャンプして距離3 を進み、また距離0.5 を走って進む。合計で4 の距離を進むことになる。
    dp[i + 4] = Math.Min(dp[i + 4], dp[i] + T1 + T2 * 3 + additionalCost);
    // ジャンプ中にLを通過する場合はいい感じに処理する
    if (i + 1 == L) dp[L] = Math.Min(dp[L], dp[i] + T1 / 2 + T2 / 2 + additionalCost);
    if (i + 2 == L) dp[L] = Math.Min(dp[L], dp[i] + T1 / 2 + T2 + T2 / 2 + additionalCost);
    if (i + 3 == L) dp[L] = Math.Min(dp[L], dp[i] + T1 / 2 + T2 + T2 + T2 / 2 + additionalCost);
}
var ans = dp[L];
Console.WriteLine(ans);

I – 行列操作

I – 行列操作

以下の条件を満たすような N×N 行列 a があります。

• ai,j=N×(i−1)+j−1 (1≤i,j≤N)

Q 個のクエリ Query1,…,QueryQ が与えられるので、順番に処理してください。 クエリは 4 種類あり、入力形式とクエリの内容は以下の通りです。

• Queryi=1 A B のとき: 行列 a の A 行目と B 行目の要素を列番号を維持しながら交換せよ。
• Queryi=2 A B のとき: 行列 a の A 列目と B 列目の要素を行番号を維持しながら交換せよ。
• Queryi=3 のとき: 行列を転置せよ。つまり ai,j の要素は転置後 aj,i に位置する。
• Queryi=4 A B のとき: 行列 a の A 行 B 列に位置する要素を出力せよ。ただし、1 番目と 2 番目の種類のクエリにおいて A=B であったとき、クエリを処理したあとの行列は処理する前と同じであることに注意してください。

制約

• 入力は全て整数
• 1≤N,Q≤10⁵
• 1≤A,B≤N
• 4 A B という形式のクエリが 1 つ以上存在する

この問題は今回解いた13問で個人的に一番難しかったかもしれないです。

この問題の条件を満たす行列とは、N=3のとき以下のようなデータとなります。

0 1 2
3 4 5
6 7 8

この行列に対してQuery 1,2,3で行のスワップ、列のスワップ、転置という操作を行います。Query 4では指定された位置の値を出力します。

まず最大ケースにおいて、Nが10⁵なので N×N 行列 a は 10¹⁰個の要素を持つため、これを実際に配列等で保持することはできません。つまり何かしらの工夫で行列データを管理しなければなりません。クエリ数も 10⁵ と大きいため計算量を考慮しなければなりません。

以下考察です。

まず行と列のスワップについてのみ考えます。行と列のスワップという操作はそれぞれ独立に行うことができ、互いに影響しません。実際に実際にノートなりに書いてみると当たり前ですが、行をスワップしても列だけでみると位置は変わらないことがわかります。

なので配列で今x行目にあるのは初期状態で何行目にあったのかという値を保持するようにします。。列についても同様です。スワップするときは配列内の値のみをスワップするようにします。こうすると実際に保持するのは10⁵個の要素を持つ配列2つで済みます。

クエリ4の出力では現在a行目は初期状態のH[a]行目、現在のb列目は初期状態のW[b]列目ということがわかるので、これを使って条件式から値を計算して求めることができます。

最後にクエリ3の転置という操作ですが、具体的には以下のような操作をします。

0 1 2
3 4 5
6 7 8

↓転置

0 3 6
1 4 7
2 5 8

↓さらに転置すると元に戻る

0 1 2
3 4 5
6 7 8

参考リンク: 転置行列 – Wikipedia

左上からの対角線を軸に反転させています。つまり行列全体に対して(行にも列にも)影響があり、これを実行時にすべて反映させるのは無理そうです。なので転置しているかどうかのフラグだけ保持しておき、ほかのクエリを実行するときに転置の状態を考慮するようにします。なお転置は2回実行すると元に戻ります。

転置前後の行列をよく確認してみると、転置後の行のスワップは転置前の列をスワップしていることと同義であり、列についてはその逆であることがわかります。したがって、転置しているかどうかで行をスワップするか列をスワップするか処理を分岐させます。

最後に転置後の行列について、a行目b列目の値は転置前の行列のb行目a列目の値であることがわかります。

以上より、転置状態のフラグを保持しておけば、転置前の行列に対するスワップと出力の組み合わせで転置クエリを処理できるようになります。

var N = sc.ReadInt();
var H = Enumerable.Range(0, N).ToArray();
var W = Enumerable.Range(0, N).ToArray();
var Q = sc.ReadInt();

// 転置されているかどうか
var rev = false;
for (int i = 0; i < Q; i++)
{
    var q = sc.ReadInt();
    if (q == 1)
    {
        // a行目とb行目をスワップする
        var a = sc.ReadInt();
        var b = sc.ReadInt();
        a--; b--;
        if (rev)
        {
            // 転置状態では列をスワップ
            var tmp = W[a];
            W[a] = W[b];
            W[b] = tmp;
        }
        else
        {
            var tmp = H[a];
            H[a] = H[b];
            H[b] = tmp;
        }
    }
    else if (q == 2)
    {
        // a列目とb列目をスワップする
        var a = sc.ReadInt();
        var b = sc.ReadInt();
        a--; b--;
        if (rev)
        {
            // 転置状態では行をスワップ
            var tmp = H[a];
            H[a] = H[b];
            H[b] = tmp;
        }
        else
        {
            var tmp = W[a];
            W[a] = W[b];
            W[b] = tmp;
        }
    }
    else if (q == 3)
    {
        // 転置する(フラグを反転)
        rev = !rev;
    }
    else
    {
        // a行目b列目の値を出力する
        var a = sc.ReadInt();
        var b = sc.ReadInt();
        a--; b--;
        // 転置状態ではb行a列の値が答え
        if (rev)
        {
            var tmp = a;
            a = b;
            b = tmp;
        }
        var h = H[a];
        var w = W[b];
        var ans = (long)N * h + w;
        Console.WriteLine(ans);
    }
}

スワップ処理が何度も書かれて冗長なのでもう少しスマートに書けると思いますが、やりたいことは実装できてます。

これは考察が必要で結構難しい問題でした。行と列のスワップは独立してやればいいというのはすぐわかったのですが、転置をうまくここに落とし込むのに悩みました。

ここまで解けて中級です。I問題が結構難しくて中級になれなかったという人もいたのではないでしょうか。GHがBFSとDPという典型アルゴリズムを問う問題に対し、Iが考察ひらめき系問題で歯ごたえのある問題セットだと思いました。私は楽しく解けました。

中級ともなると、競技プログラミング未経験者にはかなり難しいのではないかと思います。AtCoderだと緑くらいのレートが安定しないと難しい難易度だと思います。

以上。