![[C#] AtCoder 第一回 アルゴリズム実技検定 の振り返り](https://webbibouroku.com/wp-content/uploads/eye_atcoder.png)
AtCoder 第一回 アルゴリズム実技検定 をリアルタイム受験した感想 │ Web備忘録
アルゴリズム実技検定のざっくりとした概要と感想は上の記事に書きました。
第一回 アルゴリズム実技検定 振り返り
第一回 アルゴリズム実技検定の受験期間が終了し、過去問が公開されたので振り返ってみようと思います。
私はリアルタイムで受験し、64/100点の中級でした。
全体的な感想
私が解いたのはA~Iまでの9問だけでしたが、コンテストの問題と比べて圧倒的に実装力よりの問題でした。アルゴリズムの典型問題はほとんどありませんでした。ただし、それ以降の問題はわかりませんが。
時間も長く設定されておりWA時のペナルティも軽いので、私くらいのレート帯(緑)には地力が試されるような検定になっていたと思います。楽しい検定でした。
解いた問題の振り返り。
提出したコードを載せながら振り返ろうと思いましたが、提出したコードが検定サイトで確認できないことに気づきました。
提出したコードは普段は後からサービス上で参照できるので手元に保存してません。適当に思い出しながらのやっていきます。
A – 2 倍チェック / Is It a Number?
あなたは、3 桁の整数を入力として受け取り、それを 2 倍して出力するプログラムの作成を頼まれた。
ところが、どうやらプログラムに入力される文字列 S に英小文字が紛れ込むことがあるようだ。
そこで、その場合はエラーを出力することにした。S が 3 桁の整数である場合 (0 で始まる場合を含む) はその 2 倍の値を出力し、そうでなければ error と出力するプログラムを作成せよ。
簡単な問題です。が、ABCのA問題みたいな感じですね。
var ans = 0;
if (int.TryParse(S, out ans))
{
ans *= 2;
Console.WriteLine(ans);
}
else
{
Console.WriteLine("error");
}解き方は何でもよさげですが、とりあえず整数値に変換できたら2倍して出力、できなければ “error” を出力すればOKです。
B – 増減管理 / Up and Down
整数列が与えられます。１つ前の数と比較したときの増減量を出力する感じです。これもそのまま実装するだけです。
for (int i = 1; i < N; i++)
{
var d = A[i] - A[i - 1];
if (d == 0)
{
Console.WriteLine("stay");
}
else if (d > 0)
{
Console.WriteLine("up " + d);
}
else
{
Console.WriteLine("down " + -d);
}
}C – 3 番目 / The Third
6 つの相異なる整数 A, B, C, D, E, F が与えられる。
このうち 3 番目に大きい数を調べるプログラムを作成せよ。
降順にソートして3番目の要素を出力するだけです。
// Aは ABCDEF が入った配列
Array.Sort(A);
Array.Reverse(A);
var ans = A[2];
Console.WriteLine(ans);D – 重複検査 / Duplicated?
長さ N の整数列がサーバーに保管されている。
つい先ほどまで、この列には 1 から N までの整数が 1 個ずつ含まれていた。
しかし、たった今発生したトラブルにより、列のいずれか 1 個の要素が別の 1 以上 N 以下の整数に書き換えられた可能性がある。
あるいは、何の書き換えも発生しなかったかもしれない。
トラブル発生後の整数列 A1,…,AN が与えられる。
これを読み込み、書き換えが発生していたかを判定し、発生していた場合にはどの整数がどの整数に書き換えられたかを報告するプログラムを作成せよ。
出力
書き換えが発生していなかった場合、Correct と出力せよ。
書き換えが発生していた場合、整数 x が整数 y に書き換えられたとして、y と x をこの順にスペース区切りで出力せよ。
連番のデータのうち1件が書き変わったかもしれないのでそれを判定します。ループして出現回数を数えてやればいいです。200,000程度の要素数なので、十分間に合います。
// 出現回数を数える
var count = new int[N];
for (int i = 0; i < N; i++)
{
var a = A[i] - 1;
count[a]++;
}
// 1回も出現してない数(x)と2回出現した数(y)をさがす
var x = -1;
var y = -1;
for (int i = 0; i < N; i++)
{
if (count[i] == 0)
{
x = i + 1;
}
if (count[i] == 2)
{
y = i + 1;
}
}
// 出力
if (x == -1)
{
Console.WriteLine("Correct");
}
else
{
Console.WriteLine(y + " " + x);
}E – SNS のログ / Restore
あなたは、N 人のユーザが参加する SNS を運営している。彼らはユーザ 1,…,N と呼ばれ、別のユーザを何人でもフォローすることができる。
しかし、あるトラブルにより、どのユーザがどのユーザをフォローしているかの情報がすべて失われてしまった。幸い、ユーザがこの SNS で行ったすべての操作のログが残っており、あなたは操作ログをもとにフォロー状況を復元しようとしている。
操作ログは Q 行からなり、その i 行目 (1≦i≦Q) は文字列 Si である。各ユーザは以下の 3 種類の操作を行うことができ、Si は SNS 全体で i 番目に行われた操作に対応する。
- フォロー: ユーザ a がユーザ b (a≠b) をフォローする。ログには 1 a b という行が記載される。
- フォロー全返し: ユーザ a が、その時点でユーザ a をフォローしているユーザ全員をフォローする。ログには 2 a という行が記載される。
- フォローフォロー: その時点でユーザ a がフォローしている各ユーザ x に対し、ユーザ a が次を行う: 「その時点でユーザ x がフォローしているすべてのユーザ (ユーザ a 自身を除く) をフォローする」。ログには 3 a という行が記載される。
なお、この SNS が開設された時点では、どのユーザも誰もフォローしていなかった。また、ユーザ a がユーザ b を既にフォローしているとき、ユーザ a がユーザ b を再びフォローしても何も起こらない。
フォロー状況を復元せよ。
制約
- 2≦N≦100
- 0≦Q≦500
実務より？の問題ですね。各操作が少しややこしいですが、単純に全操作をトレースすれば間に合います。
こんな感じの問題はコンテストではあまり見ない印象です。ちなみに「フォローフォロー」の操作がはじめよく理解できず少し時間がかかりましたが、長時間なので余り関係ありませんでした。
// 入力省略..
// 現在の状態
var now = new bool[N, N];
for (int i = 0; i < Q; i++)
{
// 次の状態
var next = new bool[N, N];
for (int j = 0; j < N; j++)
for (int k = 0; k < N; k++)
next[j, k] = now[j, k];
if (f[i].F1 == 1)
{
// a が b をフォロー
var a = f[i].F2;
var b = f[i].F3;
next[a, b] = true;
}
else if (f[i].F1 == 2)
{
// フォロー全返し
var a = f[i].F2;
for (int j = 0; j < N; j++)
{
if (now[j, a])
{
// a をフォローしている人をフォローする
next[a, j] = true;
}
}
}
else if (f[i].F1 == 3)
{
// その時点でユーザaがフォローしている各ユーザxに対し、ユーザaが次を行う:
//「その時点でユーザxがフォローしているすべてのユーザ(ユーザa自身を除く) をフォローする」
var a = f[i].F2;
for (int x = 0; x < N; x++)
{
// a がフォローしているユーザーx
if (now[a, x])
{
for (int j = 0; j < N; j++)
{
// xがフォローしているユーザーj
if (now[x, j] && j != a)
{
// a が j をフォロー
next[a, j] = true;
}
}
}
}
}
// 状態更新
now = next;
}
// 出力
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
var res = now[i, j] ? 'Y' : 'N';
Console.Write(res);
}
Console.WriteLine();
}
// ..
struct S
{
public int F1 { get; set; }
public int F2 { get; set; }
public int F3 { get; set; }
public S(int f1, int f2, int f3)
{
this.F1 = f1;
this.F2 = f2;
this.F3 = f3;
}
}注意点として「フォローフォロー」の操作を行う際に、現在の状態を直接更新するとバグります。次の状態を用意して更新するようにします。
また、自分自身はフォローしないようにしましょう。
計算量は O(Q*N*N)=10^6 くらいで間に合います。
F – DoubleCamelCase Sort
文字列 S が与えられる。これは、1 つ以上の単語を (間に空白などを挟まずに) 連結したものである。ここで、各単語は 2 文字以上であり、最初の文字と最後の文字のみが英大文字、それ以外の文字は全て英小文字である。
これらの単語を辞書順に並べ (大文字小文字の違いは無視する)、同様に連結して出力するプログラムを作成せよ。
例えば、S= FisHDoGCaTAAAaAAbCAC とする。これは FisH, DoG, CaT, AA, AaA, AbC, AC の 7 つの単語を連結したものである。これらを辞書順に並べると AA, AaA, AbC, AC, CaT, DoG, FisH となるため、AAAaAAbCACCaTDoGFisH と出力すればよい。
これはもう、アルゴリズムとか関係なくループして単純に実装するだけです。2重ループしないようにすればOKです。
var list = new List<string>();
var now = new StringBuilder();
foreach (var c in S)
{
now.Append(c);
// 大文字かどうかを判定する
if (c < 'a')
{
// 2文字目以降の大文字は終了文字
if (now.Length >= 2)
{
list.Add(now.ToString());
now.Clear();
}
}
}
// 昇順にして出力
foreach (var res in list.OrderBy(s => s))
{
Console.Write(res);
}
Console.WriteLine();TLEする人は文字列の単純な連結が問題です。ここでは StringBuilder で文字列の連結を行っています。私は本番でTLEしました。
文字が大文字かどうかは ‘a’ より小さいかどうか判定しています。
G – 組分け / Division
あなたは、N 人の社員、社員 1,…,N を 3 つ以下のグループに最適に分割するプログラムを作ろうとしている。
すでに、社員のペア i,j (1≦i<j≦N) すべてに対して、彼らを同じグループに含めた際に生じる幸福度 Ai,j (正とは限らない) が AI によって計算されている。
グループ分けの好ましさを、同じグループに含まれる社員のペア i,j すべてに対する Ai,j の総和 (そのようなペアが存在しなければ 0) と定義する。グループ分けの好ましさの最大値を求めよ。
再帰で全探索すれば解けました。Nが小さいときは大体全探索でいける感じです。これはコンテストでもよく見る問題かもしれません。
static void Main(string[] args)
{
// 入力
N = sc.ReadInt();
A = new long[N, N];
for (int i = 0; i < N; i++)
{
for (int j = i + 1; j < N; j++)
{
A[i, j] = sc.ReadLong();
}
}
Rec(0, new int[N]);
Console.WriteLine(Ans);
}
static int N;
static long[,] A;
static long Ans = long.MinValue;
static void Rec(int n, int[] group)
{
// 幸福度を計算
if (n == N)
{
long res = 0;
for (int i = 0; i < N; i++)
{
for (int j = i + 1; j < N; j++)
{
// i,jが同じグループのとき幸福度を追加
if (group[i] == group[j]) res += A[i, j];
}
}
Ans = Math.Max(Ans, res);
return;
}
for (int i = 0; i < 3; i++)
{
// 0, 1, 2 のどれかにする
group[n] = i;
Rec(n + 1, group);
}
}まずグループは最大3つに分けられます。社員数Nが最大10なのでグループ分けのパターン数は 3^10=59049 です。全探索が間に合います。再帰で全パターンを探索してやればよいです。
また幸福度がマイナスをとりうるので、答えの初期値は小さい値を用意しておきます。
あとは再帰で社員全員を0, 1, 2の3つのグループに分けて、幸福度を計算するだけです。
ペア(組み合わせ)を列挙するには以下の2重ループで実現可能です。これはよく使うので覚えておくとよさげです。
for (int i = 0; i < N; i++)
{
for (int j = i + 1; j < N; j++)
{
// ..
}
}H – まとめ売り / Bulk Selling
これもE問題のように複数の操作を行ったときの結果を求める問題ですが、入力値の制約が大きく単純にシミュレーションを実行するとTLEする問題です。
ということで工夫が必要になります。
単品販売はそのまま計算してもOKですが、セット販売と全種類販売はループしながらシミュレートするとTLEします。なのでセット販売と全種類販売は別計算しておくことにします。
セット販売も全種類販売も、対象カードの最小枚数だけわかれば売れるかどうかがわかります。なのでカード全体の最小枚数と、奇数番目のカードの最小枚数を管理しておくようにします。またそセット・全種類販売それぞれで売った枚数も数えておけば、単品販売時にその分も考慮に入れれば正しくシミュレートできます。
// 入力省略..
// 全体の最小枚数と奇数番目のカードの最小枚数
var min = C.Min();
var min2 = long.MaxValue;
for (int i = 0; i < N; i += 2) min2 = Math.Min(min2, C[i]);
long ans = 0;
// セット販売で売った枚数と全種類販売で売った枚数
long d2 = 0;
long d = 0;
for (int _ = 0; _ < Q; _++)
{
var s1 = sc.ReadInt();
if (s1 == 1)
{
// 単品販売
var x = sc.ReadInt() - 1;
var a = sc.ReadLong();
// 残り枚数=C[x]-[全種類販売枚数]-[セット販売枚数]
var now = C[x] - d;
if (x % 2 == 0) now -= d2;
if (now - a >= 0)
{
now -= a;
C[x] -= a;
// 最小枚数更新
min = Math.Min(min, now);
if (x % 2 == 0) min2 = Math.Min(min2, now);
ans += a;
}
}
else if (s1 == 2)
{
// セット販売
var a = sc.ReadLong();
// 奇数番目のカードの最小枚数より少ない枚数の場合は売れる
if (min2 - a >= 0)
{
// 最小値を更新しておく
min2 -= a;
min = Math.Min(min, min2);
// セット販売枚数更新
d2 += a;
ans += (N + 1) / 2 * a;
}
}
else
{
// 全種類販売
var a = sc.ReadLong();
// 全体での最小枚数より少ない枚数の場合は売れる
if (min - a >= 0)
{
// 最小値を更新しておく
min -= a;
min2 -= a;
// 全種類販売枚数更新
d += a;
ans += N * a;
}
}
}
Console.WriteLine(ans);d2, d がそれぞれセット販売と全種類販売で売った枚数、min2, min がそれぞれセット販売対象のカードの最小枚数と全種類販売対象のカードの最小枚数です。
これをうまく各操作で管理しておけば、正しく販売枚数をカウントできます。
I – 部品調達 / Procurement
あなたは、あるものを作るために N 種類の部品、部品 1,…,N を購入しようとしている。ネット通販サイトを探すと、部品のセット販売が M 件見つかった。
i 件目のセット販売 (1≦i≦M) の情報は、長さ N の文字列 Si と整数 Ci の組として与えられる。Si の j 文字目 (1≦j≦N) は、このセットが部品 j を含むとき Y、含まないとき N である。また、このセットは Ci 円で販売されている。
これらのセットのうち何個かを購入し、N 種類の部品をすべて 1 個以上手に入れるのに必要な金額を求める (または、それが不可能であることを報告する) プログラムを作成せよ。
制約
- 1≦N≦10
- 1≦M≦1,000
- Si は長さ N の文字列である。
- Si の各文字は Y または N である。
- 1≦Ci≦1,000,000,000
- Ci は整数である。
M件のセットについて買う/買わないの全探索をすると O(2^M) で間に合わないので別の方法を考えます。
ということでメモ化再帰で実装してみたらTLEが突破できました。覚えてないですがたぶん検定本番でも同じ方法でACしたと思いますが自信ないです。
static void Main(string[] args)
{
N = sc.ReadInt();
M = sc.ReadInt();
Data = new Tuple<int, int>[M];
for (int i = 0; i < M; i++)
{
var val = 0;
var s = sc.ReadStr();
for (int j = 0; j < N; j++)
{
// 文字列でなく整数で管理する
if (s[j] == 'Y') val |= 1 << (N - 1 - j);
}
Data[i] = Tuple.Create(val, sc.ReadInt());
}
Memo = new long[N, (int)Math.Pow(2, N)];
// 計算結果がINFより大きいときは全部品がそろわないので-1
var ans = Rec(0, 0);
if (ans >= INF) ans = -1;
Console.WriteLine(ans);
}
static int N;
static int M;
static Tuple<int, int>[] Data;
static long[,] Memo;
static long INF = 1000000000000;
static long Rec(int n, int now)
{
if (n == N)
{
// Nまで見たとき全部の部品が買えていなければINF
if (now == Math.Pow(2, N) - 1) return 0;
else return INF;
}
// n番目の部品を買うときの計算をすでにしていたら
if (Memo[n, now] > 0) return Memo[n, now];
var res = INF;
for (int i = 0; i < M; i++)
{
if ((now >> (N - n - 1) & 1) == 1)
{
// もうすでにn番目の部品を買っているのでパスしてn+1番目の部品を見る
res = Rec(n + 1, now);
break;
}
else if (((Data[i].Item1 >> (N - n - 1)) & 1) == 1)
{
// n番目の部品を含むセットであれば買うパターンを計算
var next = now | Data[i].Item1;
// i件目のセットの金額と残りの部品を買うのに必要な金額を足したものが候補
res = Math.Min(res, Rec(n + 1, next) + Data[i].Item2);
}
}
Memo[n, now] = res;
return res;
}この実装の計算量がよくわからないですがTLEしなかったのでよしとします。
解けたのはここまででした。I問題まで全問解けて64点で中級ギリギリでした。
J – 地ならし / Leveling
解けそうで解けなかったので諦めました。
過去問が公開されてジャッジができるようになりましたが、まだ解説が出ていないので出たら解いてみようと思います。
以上。
