はじめに
AtCoder Beginner Contest 236の復習記事です。
記事におけるScannerクラスは、自作の入力クラスです。
コンテスト
https://atcoder.jp/contests/abc236
問題A
文字列を文字の配列としてとり、指定されたインデックスの中身を入れ替えます。
public static void Solve()
{
var S = Scanner.Scan<string>().ToCharArray();
var (A, B) = Scanner.Scan<int, int>();
A--; B--;
(S[A], S[B]) = (S[B], S[A]);
Console.WriteLine(string.Join("", S));
}
タプルを使うことで、一時変数を使わずに値を入れ替えることができます。
var tmp = a;
a = b;
b = a;
(a, b) = (b, a); // 上と同じ
問題B
カードはすべて数値なので、4N枚のカードの総和(4 * N * (N+1) / 2)から渡されたカードの束Aの総和を引くことで、抜き取られたカードを求めることができます。
public static void Solve()
{
var N = Scanner.Scan<long>();
var A = Scanner.ScanEnumerable<long>().ToArray();
var answer = 4L * (N * (N + 1) / 2) - A.Sum();
Console.WriteLine(answer);
}
問題C
文字列をキーとした辞書を作成し、急行列車が止まる駅をチェックします。時間計算量はO(NlogN)になります。
public static void Solve()
{
var (N, M) = Scanner.Scan<int, int>();
var S = Scanner.ScanEnumerable<string>().ToArray();
var T = Scanner.ScanEnumerable<string>().ToArray();
var dict = new Dictionary<string, bool>();
foreach (var s in S)
{
dict[s] = false;
}
foreach (var t in T)
{
dict[t] = true;
}
foreach (var s in S)
{
Console.WriteLine(dict[s] ? "Yes" : "No");
}
}
ほかにも、TはSの部分列であることが制約で保証されているため、Sを前から順に見ていったとき、次のTと一致した場合にはYesを表示し、Tを次に進めるといった方法でも、時間計算量O(N)で解くことができます。
public static void Solve()
{
var (N, M) = Scanner.Scan<int, int>();
var S = Scanner.ScanEnumerable<string>().ToArray();
var T = Scanner.ScanEnumerable<string>().ToArray();
var queue = new Queue<string>(T);
foreach (var s in S)
{
if (queue.TryPeek(out var t) && s == t)
{
queue.Dequeue();
Console.WriteLine("Yes");
}
else
{
Console.WriteLine("No");
}
}
}
問題D
今見ている人とスコアをもって深さ優先探索を行い、すべての人がペアを組み終わったときのスコアを最大値を求めます。遷移としては、既にペアを組んでいる場合は次の人に進み、組んでいない場合は今見ている人以降のまだペアを組んでいない人とペアを組みます。
public static void Solve()
{
var N = Scanner.Scan<int>();
var A = new int[N * 2, N * 2];
for (var i = 0; i < N * 2 - 1; i++)
{
var AA = Scanner.ScanEnumerable<int>().ToArray();
for (var j = 0; j < AA.Length; j++)
{
A[i, j + i + 1] = A[j + i + 1, i] = AA[j];
}
}
var answer = 0;
var used = new bool[N * 2];
void Dfs(int curr, int xor)
{
if (curr >= N * 2)
{
if (used.All(x => x))
{
answer = Math.Max(answer, xor);
}
return;
}
if (!used[curr])
{
for (var next = curr + 1; next < N * 2; next++)
{
if (!used[next])
{
used[curr] = used[next] = true;
Dfs(curr + 1, xor ^ A[curr, next]);
used[curr] = used[next] = false;
}
}
}
else
{
Dfs(curr + 1, xor);
}
}
Dfs(0, 0);
Console.WriteLine(answer);
}
問題E
コンテスト中の考察です。
- 二部探索?
- 最初に奇数番目と偶数番目をそれぞれ分けて、もし値が増えるならそれぞれ足していくことで平均値はでそう?
- 上の方針では、
1 2 4 5 7 8のように番目をとるとダメになる可能性がある。
解説では、平均と中央値ともに二部探索でした。
public static void Solve()
{
var N = Scanner.Scan<long>();
var A = Scanner.ScanEnumerable<long>().ToArray();
long DP(IEnumerable<long> source)
{
var (x, y) = (0L, 0L);
foreach (var v in source)
{
var z = Math.Max(x, y) + v;
(x, y) = (y, z);
}
return Math.Max(x, y);
}
double Average()
{
bool F(long k) => DP(A.Select(x => x * 1000 - k)) >= 0;
return BinarySearch((long)1e12 + 1, 0, F) / 1000d;
}
long Median()
{
bool F(long k) => DP(A.Select(x => x >= k ? 1L : -1L)) > 0;
return BinarySearch((long)1e9 + 1, 0, F);
}
Console.WriteLine(Average());
Console.WriteLine(Median());
}
BinarySearchは[ng, ok)の間で、funcの判定式を使って二部探索を行う関数です。
public static long BinarySearch(long ng, long ok, Func<long, bool> func)
{
while (Math.Abs(ok - ng) > 1)
{
var m = (ok + ng) / 2;
if (func(m)) ok = m;
else ng = m;
}
return ok;
}