[C#] 第三回アルゴリズム実技検定PAST A-F(初級)問題振り返り解説 │ Web備忘録

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

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

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

1. 第三回アルゴリズム実技検定
2. A – ケース・センシティブ
3. B – ダイナミック・スコアリング
4. C – 等比数列
5. D – 電光掲示板
6. E – スプリンクラー
7. F – 回文行列

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

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

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

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

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

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

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

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

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

A – ケース・センシティブ

長さ 3 の英大文字・英小文字のみからなる文字列 s,t が与えられます。

s,t が大文字と小文字の違いを含めて一致するなら same を、そうではないが大文字と小文字の違いを区別しない場合に一致するなら case-insensitive を、以上に該当しないなら different を出力してください。

文字列2つが一致するかどうかを判定しますが、大文字小文字を無視して比較した時に一致するかどうかも判定する必要があります。

完全一致は、s == t で判定すればよいです。大文字と小文字の違いを区別しないという処理をどうするかがポイントです。

C# には ToLower(), ToUpper() で文字列を小文字ないし大文字に変換することができます。これを使って小文字に統一して一致するかどうかを判定すれば大文字と小文字の違いを区別しない場合の一致判定ができます。

var S = sc.ReadStr();
var T = sc.ReadStr();
if (S == T)
{
    // 完全に一致する
    Console.WriteLine("same");
}
else if (S.ToLower() == T.ToLower())
{
    // 大文字と小文字の違いを区別しない場合に一致する
    Console.WriteLine("case-insensitive");
}
else
{
    // まったく異なる
    Console.WriteLine("different");
}

C#に用意された関数である、ToLower() や ToUpper() を使わないで実装することもできます。

方針としては文字として扱うのではなく、0,1,2,..,25 の 26文字の数字として扱います。

Asciiコードでは大文字のほうが小文字より値が大きいです。よって、以下のようにして大文字小文字を無視して数字に変換した配列を作成します。

完全一致しない場合は作成した配列の各要素ごとに比較してすべて一致するか判定します。

var S = sc.ReadStr();
var T = sc.ReadStr();

// 大文字小文字を無視した0..25の数値に変換しておく
var sa = new int[S.Length];
var ta = new int[T.Length];
for (int i = 0; i < S.Length; i++)
{
    sa[i] = S[i] - 'a';
    if (S[i] - 'a' < 0) sa[i] = S[i] - 'A';
    ta[i] = T[i] - 'a';
    if (T[i] - 'a' < 0) ta[i] = T[i] - 'A';
}

if (S == T)
{
    // 完全に一致する
    Console.WriteLine("same");
}
else if (Enumerable.Range(0, 3).All(i => sa[i] == ta[i]))
{
    // 大文字と小文字の違いを区別しない場合に一致する
    Console.WriteLine("case-insensitive");
}
else
{
    // まったく異なる
    Console.WriteLine("different");
}

B – ダイナミック・スコアリング

プログラミングコンテストが開催されます。このコンテストの参加者は N 人で、コンテストには M 個の問題が出題されます。参加者には 1,2,…,N の番号が、問題には 1,2,…,M の番号が振られています。

このコンテストにおいて、問題の得点はその問題を解いた人間の人数によって変化します。具体的には、N−(現時点でこの問題を解いた人数) が得点となります。

参加者のスコアは解いた問題の得点の合計です。問題の得点が変化した場合、参加者のスコアも変化することに注意してください。例えば、N=2,M=1 の場合において、はじめ問題 1 の得点は 2 です。その後、参加者 1 が問題 1 を解いたとき、問題 1 の得点は 1、参加者 1 のスコアは 1 となります。らにその後、参加者 2 が問題 1 を解いたとき、問題 1 の得点は 0 となり、参加者 1,2 のスコアは 0 となることに注意してください。

以下の形式で与えられる Q 個のクエリ s1,s2,…,sQ を順番に処理してください。

参加者 n の現在のスコアを出力せよ。

1 n という形式で与えられる。

参加者 n が問題 m を解いた。

2 n m という形式で与えられる。

制約

1≤N,Q≤10⁵

1≤M≤50

si は下記のいずれかの形式の文字列

1 n (1≤n≤N)

2 n m (1≤n≤N,1≤m≤M)

どの参加者も同じ問題を複数回解くことはない

B問題にしてAよりもずいぶん長い問題文でややこしい感じです。参加者のスコアは状況により変化します。今回は制約的にも全探索でも問題ないので、問題文をしっかり読んでその通り実装してやる必要があります。実装力を試す問題でした。

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

// n問目をm人目が解いたかどうか
var solved = new bool[N, M];
// m人目が解いた問題数
var count = new int[M];

for (int i = 0; i < Q; i++)
{
    var x = sc.ReadInt();
    if (x == 1)
    {
        // 参加者nの現在のスコアを求める
        var n = sc.ReadInt();
        n--;
        var score = 0;
        for (int j = 0; j < M; j++)
        {
            if (solved[n, j])
            {
                score += N - count[j];
            }
        }
        Console.WriteLine(score);
    }
    else
    {
        // 参加者nが問題mを解いた
        var n = sc.ReadInt();
        var m = sc.ReadInt();
        n--; m--;
        solved[n, m] = true;
        count[m]++;
    }
}

こんな感じのクエリごとに出力がある問題は上記のような入力と出力を交互にしてもACできるのですが、こうするとデバッグが大変です。ですが出力データをリストなりに退避して後で出力するのは面倒でコードの見通しが悪くなります。なので私は以下のようにしています。

static void Main(string[] args)
{
    // 自動でFlushされないようにする
    var sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
    Console.SetOut(sw);
    // 問題を解く
    Solve();
    // 解き終わったら最後にFlushする
    Console.Out.Flush();
}
static void Solve() 
{
    // ここで問題を解く
    // 入力を受け取ったり、出力したり...
}

C# の Console.WriteLine() は AutoFlush が true の状態だと実行のたびにFlushされます。Flushされるとこの場合コンソール上にそのタイミングで書き出されます。

今回の問題みたいなクエリ問題だと、サンプルを実行した時に

クエリ1
クエリ1の出力
クエリ2
クエリ3
クエリ3の出力
...

みたいな感じで入力と出力が交互になって、入力例があってるかどうか判別しずらいので上記のようにコードの最後でFlushしたほうが見やすくなります。また、Flush自体が重い処理のため、大量の出力(10⁵回くらい)が実行される場合はAtCoderだと500msくらい高速化も期待できます。

C – 等比数列

初項 A、公比 R の等比数列の第 N 項が 10⁹ より大きければ large を、10⁹ 以下ならその値を整数で出力してください。

制約

入力はすべて整数

1≤A,R,N≤10⁹

打って変わって数学チックな問題です。

等比数列の第N項は an = A*R^(N-1) で求まります。初項に対してN-1回公比Rをかけた値が第N項です。

制約を見てみると、N≤10⁹ となっているので、数学的にうまく求める必要がありそうですが、全探索で求めることができます。

まず、R=1のとき、1を何回かけても変わらないので等比数列のすべての項は初項と一致します。よって第N項もAです。

Rが2以上のとき、ループして第2項から第N項までを順番に求めればよいです。第n+1項は第n項*公比で求まります。

途中で10⁹を超えれば処理を中断し、"large" を出力します。中断しないとオーバーフローして正しい結果が得られません。

var A = sc.ReadLong();
var R = sc.ReadLong();
var N = sc.ReadLong();
if (R == 1)
{
    Console.WriteLine(A);
    return;
}
// an = A*R^(N-1)
var ans = A;
for (int i = 0; i < N-1; i++)
{
    ans *= R;
    if (ans > (int)1e9)
    {
        Console.WriteLine("large");
        return;
    }
}
Console.WriteLine(ans);

一見ループの中の計算量が O(N) のため TLE しそうに見えますが、TLEは発生しません。なぜならTLEするような回数ループするまでに10⁹を超えて処理が終了するからです。

ループ回数が最も多くなる条件、初項A=2かつ公比R=2の時、log(10⁹)≒30回程度の計算で処理が終了する(10⁹を超える)ことがわかります。公比Rや初項Aが大きくなればより早くループ内の処理は終了します。よって計算量的にも問題のないコードになっています。

なお、計算はlong型で行いましょう。初項A=10⁹、公比R=10⁹のとき、第2項が10⁹*10⁹=10¹⁸ となり、int型だとオーバーフローします。

ここまで解けてエントリーです。

D – 電光掲示板

N 桁の数字列を表示する電光掲示板があります。この電光掲示板は 5 行 4N+1 列に並べられたランプにより構成されます。 1≤j≤N を満たす j について、左から j 桁目の数字の表示には左から 4j−2,4j−1,4j 列目のランプが用いられます。それ以外の 1,5,…,4N+1 列目のランプは全て消灯しています。

電光掲示板の表示の状況は 5 つの長さ 4N+1 の文字列 s1,s2,s3,s4,s5 により表されます。具体的には、1≤i≤5,1≤j≤4N+1 を満たす (i,j) について、 si の先頭から j 番目の文字は上から i 行目、左から j 列目のランプの点灯状況を表しています。

文字列中の # は対応する位置のランプが点灯していることを、. は消灯していることを表します。

電光掲示板に表示されている N 桁の数字列を出力してください。

各数字の表示の仕方については入力例 1 を参考にしてください。

制約

1≤N≤50

s1,s2,s3,s4,s5 は #、. のみからなる長さ 4N+1 の文字列

s1,s2,s3,s4,s5 の 1,5,…,4N+1 文字目は全て .

入力に対応する数字列が必ず存在し、各数字の表示の仕方は入力例 1 のものと同様

入力例1は以下の通りです。

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

ちょっと見ずらいかもしれませんが、0から9までが並んでいます。左から4列ごとに1文字となっています。

上記入力例のような形式の5行からなる文字列が与えられるので、どのような数字列になっているかを判定するのがこの問題の趣旨です。

アルゴリズムというよりは実装力が問われる問題だと思います。どのような実装方針を採るか、いろいろあると思いますが制約的に計算量には余裕がありそうなので、以下のようにしました。

入力例1の内容をコードに埋め込み、事前に各数に対応する文字列に分解しておく。
入力文字列を1文字ずつに対応するように文字列に分解
得られた文字列と各数に対応する文字列が一致するか判定する

var N = sc.ReadInt();
var S = sc.ReadStrArray(5);

// テンプレート文字列を5行の文字列で保持しておく
var template = new string[5];
template[0] = ".###..#..###.###.#.#.###.###.###.###.###.";
template[1] = ".#.#.##....#...#.#.#.#...#.....#.#.#.#.#.";
template[2] = ".#.#..#..###.###.###.###.###...#.###.###.";
template[3] = ".#.#..#..#.....#...#...#.#.#...#.#.#...#.";
template[4] = ".###.###.###.###...#.###.###...#.###.###.";

// テンプレート文字列を分解して、4文字*5行の文字列(改行文字なし)として保持しておく
var nums = new string[10];
for (int i = 0; i < 10; i++)
{
    for (int j = 0; j < 5; j++)
    {
        var si = i * 4;
        nums[i] += template[j].Substring(si + 1, 3);
    }
}

// 入力文字列を判定する
var ans = "";
for (int i = 0; i < N; i++)
{
    // 現在の数字に対応する文字列を求める
    var now = "";
    for (int j = 0; j < 5; j++)
    {
        var si = i * 4;
        now += S[j].Substring(si + 1, 3);
    }
    // 一致する数を探す
    for (int j = 0; j < 10; j++)
    {
        if (nums[j] == now) ans += j.ToString();
    }
}
Console.WriteLine(ans);

入力例1からいい感じに各数に対応するような形で文字列を切り出すのが難しかったので、マルっと埋め込んで都度分解するようなコードにしました。

E – スプリンクラー

1,2,3,…,N の番号がついた N 個の頂点と 1,2,3,…,M の番号がついた M 本の無向辺からなる無向グラフが与えられます。辺 i は頂点 ui と vi を双方向につないでいます。

それぞれの頂点には色を塗ることが可能で、はじめ頂点 i は色 ci で塗られています(この問題において、色は 1 以上 105 以下の整数で表されます)。

それぞれの頂点にはスプリンクラーが設置されています。頂点 i にあるスプリンクラーを起動すると、頂点 i に隣接する全ての頂点の色がスプリンクラー起動時点の頂点 i の色で塗り替えられます。

以下の形式で与えられる Q 個のクエリ s1,s2,…,sQ を順番に処理してください。

頂点 x の現在の色を出力する。その後、頂点 x にあるスプリンクラーを起動する。

1 x という形式で与えられる。

頂点 x の現在の色を出力する。その後、頂点 x の色を y で上書きする。

2 x y という形式で与えられる。

制約

与えられる入力は全て整数

1≤N,Q≤200

0≤M≤N(N−1)/2

1≤ui,vi≤N

1≤ci≤10⁵

si は下記のいずれかの形式の文字列

1 x (1≤x≤N)

2 x y (1≤x≤N,1≤y≤10⁵)

与えられるグラフに多重辺や自己ループは存在しない

グラフ問題の基礎的な知識を問う問題です。これはいかにも競技プログラミングという感じです。

これはある頂点に隣接する頂点を高速に求めることができれば与えられた操作を愚直に実行しても計算量が O(MQ) で十分高速に動作します。

与えられるグラフは隣接する頂点を管理する隣接リストとして管理すればOKです。

隣接リスト – Wikipedia

実装はC#だと List<int>[] で管理するとよいでしょう。

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

// グラフを隣接リストで管理する
var G = new List<int>[N];
for (int i = 0; i < N; i++)
{
    G[i] = new List<int>();
}
// 各辺の入力を受け取る
for (int i = 0; i < M; i++)
{
    // uとvが辺で結ばれる(0-indexedにする)
    var u = sc.ReadInt();
    var v = sc.ReadInt();
    u--; v--;
    // 無向グラフなので双方向に辺を張る
    G[u].Add(v); // u -> v の辺
    G[v].Add(u); // v -> u の辺
}

// 各頂点の現在の色
var colors = sc.ReadIntArray(N);
for (int i = 0; i < Q; i++)
{
    var q = sc.ReadInt();
    if (q == 1)
    {
        // 頂点xの現在の色を出力
        var x = sc.ReadInt();
        x--;
        Console.WriteLine(colors[x]);
        // 頂点xに隣接する頂点の色を更新する
        foreach (var next in G[x])
        {
            colors[next] = colors[x];
        }
    }
    else
    {
        // 頂点xの色をyに更新する
        var x = sc.ReadInt();
        var y = sc.ReadInt();
        x--;
        Console.WriteLine(colors[x]);
        colors[x] = y;
    }
}

隣接リストでグラフが管理できれば後は実装するだけでOKです。

F – 回文行列

整数 N 及び小文字アルファベットからなる N×N 行列 a が与えられます。以下の条件を満たすような長さ N の文字列 S をいずれか 1 つ構築してください。

文字列 S は英小文字から構成される。

文字列 S は回文である。なお, 回文とは前から読んでも後ろから読んでも同じである文字列である。

Si は ai1,ai2,…,aiN のいずれかと同じ文字である。

ただし、条件を満たす文字列が存在しない場合はそれを指摘してください。

制約

N は整数1≤N≤500

ai,j は英小文字

長さNの回文となる文字列を作ります。ただし、Sの1文字目は行列aの1行目から選び、2文字目2行目から、N文字目はN行目から選んで構成しなければなりません。

回文であるための条件は問題文にある通りですが、具体的に 1文字目とN文字目、2文字目とN-1文字目、3文字目とN-2文字目というような感じで一致する必要があり、これはつまり i文字目とN-i-1文字目 が一致しなければならないということです。ただし i <= N/2 の範囲でです。前半と後半を突き合わせてチェックするので、後半のチェック不要です。

つまり、i行目とN-i-1行目に同じ文字が含まれていればその中からどれか1文字選べばOKで、含まれていなければ条件を満たす文字列が存在しないということになります。

Nが奇数の時、例えばN=3の時は真ん中の2文字目についてはどんな文字でも回文になるので適当に選んでもOKです。

Nが500なので一致する文字が存在するかどうかも普通にチェックして計算量的に大丈夫です。今回は Linq の Intersect で積集合を計算しています。

var N = sc.ReadInt();
var S = sc.ReadStrArray(N);

// a は構成する回文の文字配列
var a = new char[N];
// 前半の行についてチェックする
for (int i = 0; i < (N + 1) / 2; i++)
{
    // i行目とN-i-1行目の積集合を求める
    var kouho = S[i].Intersect(S[N - i - 1]).ToArray();
    // 積集合が空の時、回文にできないので-1出力
    if (kouho.Length == 0)
    {
        Console.WriteLine(-1);
        return;
    }
    // 共通する文字があれば先頭を答えとして選ぶ
    a[i] = kouho[0];
    a[N - i - 1] = kouho[0];
}
var ans = new string(a);
Console.WriteLine(ans);

ちょうど真ん中の文字については、i == N-i-1 となり必ず一致する文字が得られるようになっています。

計算量は各行O(N)で積集合O(N)を求めているので O(N^2) となるので、十分高速です。積集合を採っているところはあらかじめ前計算で、各行の出現文字を数えていれば O(N*26) で計算できます。

各行で出現するアルファベットをビット列(26桁)で管理すれば、AND演算を使って回文判定できるので O(N) で判定部分を計算できます。

いずれにせよ前計算で O(N^2) かかるのであんまり関係ないかもしれませんが。

ここまで6問解けて初級でした。普段の割と実装によった感じの問題で解いていて楽しかったです。

以上。

AtCoder Beginner Contest 169 に C# で参加した記録

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

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

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

A – ケース・センシティブ

B – ダイナミック・スコアリング

C – 等比数列

D – 電光掲示板

E – スプリンクラー

F – 回文行列

競技プログラミングカテゴリの最新記事

エイシングプログラミングコンテスト 2020 に C# で参加した記録

AtCoder Beginner Contest 173 に C# で参加した記録

AtCoder Beginner Contest 172 に C# で参加した記録

AtCoder Beginner Contest 171 に C# で参加した記録

AtCoder Beginner Contest 170 に C# で参加した記録

東京海上日動プログラミングコンテスト2020 に C# で参加した記録

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

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

A – ケース・センシティブ

B – ダイナミック・スコアリング

C – 等比数列

D – 電光掲示板

E – スプリンクラー

F – 回文行列

競技プログラミングカテゴリの最新記事

エイシング プログラミング コンテスト 2020 に C# で参加した記録

AtCoder Beginner Contest 173 に C# で参加した記録

AtCoder Beginner Contest 172 に C# で参加した記録

AtCoder Beginner Contest 171 に C# で参加した記録

AtCoder Beginner Contest 170 に C# で参加した記録

東京海上日動 プログラミングコンテスト2020 に C# で参加した記録

エイシングプログラミングコンテスト 2020 に C# で参加した記録

東京海上日動プログラミングコンテスト2020 に C# で参加した記録