はじめに
AtCoder Beginner Contest 310の復習記事です。
記事におけるScannerクラスは、自作の入力クラスです。
Scannerクラス
public static class Scanner
{
public static T Scan<T>() where T : IConvertible => Convert<T>(ScanStringArray()[0]);
public static (T1, T2) Scan<T1, T2>() where T1 : IConvertible where T2 : IConvertible
{
var input = ScanStringArray();
return (Convert<T1>(input[0]), Convert<T2>(input[1]));
}
public static (T1, T2, T3) Scan<T1, T2, T3>() where T1 : IConvertible where T2 : IConvertible where T3 : IConvertible
{
var input = ScanStringArray();
return (Convert<T1>(input[0]), Convert<T2>(input[1]), Convert<T3>(input[2]));
}
public static (T1, T2, T3, T4) Scan<T1, T2, T3, T4>() where T1 : IConvertible where T2 : IConvertible where T3 : IConvertible where T4 : IConvertible
{
var input = ScanStringArray();
return (Convert<T1>(input[0]), Convert<T2>(input[1]), Convert<T3>(input[2]), Convert<T4>(input[3]));
}
public static (T1, T2, T3, T4, T5) Scan<T1, T2, T3, T4, T5>() where T1 : IConvertible where T2 : IConvertible where T3 : IConvertible where T4 : IConvertible where T5 : IConvertible
{
var input = ScanStringArray();
return (Convert<T1>(input[0]), Convert<T2>(input[1]), Convert<T3>(input[2]), Convert<T4>(input[3]), Convert<T5>(input[4]));
}
public static (T1, T2, T3, T4, T5, T6) Scan<T1, T2, T3, T4, T5, T6>() where T1 : IConvertible where T2 : IConvertible where T3 : IConvertible where T4 : IConvertible where T5 : IConvertible where T6 : IConvertible
{
var input = ScanStringArray();
return (Convert<T1>(input[0]), Convert<T2>(input[1]), Convert<T3>(input[2]), Convert<T4>(input[3]), Convert<T5>(input[4]), Convert<T6>(input[5]));
}
public static IEnumerable<T> ScanEnumerable<T>() where T : IConvertible => ScanStringArray().Select(Convert<T>);
private static string[] ScanStringArray()
{
var line = Console.ReadLine()?.Trim() ?? string.Empty;
return string.IsNullOrEmpty(line) ? Array.Empty<string>() : line.Split(' ');
}
private static T Convert<T>(string value) where T : IConvertible => (T)System.Convert.ChangeType(value, typeof(T));
}
コンテスト
https://atcoder.jp/contests/abc310
問題A
ドリンクのみか、割引券とともに最安値の料理を注文するかの方法のうち、安くなる方が答えとなります。
public static void Solve()
{
var (N, P, Q) = Scanner.Scan<int, int, int>();
var D = Scanner.ScanEnumerable<int>().ToArray();
var answer = Math.Min(P, Q + D.Min());
Console.WriteLine(answer);
}
問題B
価格Pの集合Sと、価格Qの集合Tを比較したときに、SとT一致しているかつ値段が異なる、またはTはSの部分集合かつ|S|>|T|であるかを判定します。
public static void Solve()
{
var (N, M) = Scanner.Scan<int, int>();
var PS = new (int P, HashSet<int> S)[N];
for (var i = 0; i < N; i++)
{
var array = Scanner.ScanEnumerable<int>().ToArray();
var p = array[0];
var c = array[1];
var s = new HashSet<int>(array.Skip(2));
PS[i] = (p, s);
}
Array.Sort(PS, (x, y) => x.P.CompareTo(y.P));
for (var i = 0; i < N; i++)
{
for (var j = i + 1; j < N; j++)
{
var (p, s) = PS[i];
var (q, t) = PS[j];
if ((s.SetEquals(t) && p < q) || t.IsSubsetOf(s) && s.Count > t.Count)
{
Console.WriteLine("Yes");
return;
}
}
}
Console.WriteLine("No");
}
問題C
文字列を順にみていき、その文字列とその文字列を反転させたものがそれまでに出現しているかを判定していきます。
public static void Solve()
{
var N = Scanner.Scan<int>();
var set = new HashSet<string>();
var answer = 0;
for (var i = 0; i < N; i++)
{
var S = Scanner.Scan<string>();
var T = new string(S.Reverse().ToArray());
if (!set.Contains(S) && !set.Contains(T))
{
set.Add(S);
set.Add(T);
answer++;
}
}
Console.WriteLine(answer);
}
問題D
全探索を行います。
現在できているチームを管理しながら、相性の悪い組ができないように選手を順番に追加していきます。
場合分けとして、現在できているチームのいずれかに選手を追加することができます。
また、現在できているチーム数がT未満の場合、新しくチームを作成して選手を追加することができます。
N人全ての選手をチームに追加したときのチーム数がT組であるときの組み合わせを数え上げます。
public static void Solve()
{
var (N, T, M) = Scanner.Scan<int, int, int>();
var ng = new int[N];
for (var i = 0; i < M; i++)
{
var (a, b) = Scanner.Scan<int, int>();
a--; b--;
ng[a] |= 1 << b;
ng[b] |= 1 << a;
}
var teams = new List<int>(T);
int Dfs(int i)
{
if (i == N)
{
return teams.Count == T ? 1 : 0;
}
var sum = 0;
for (var t = 0; t < teams.Count; t++)
{
if ((teams[t] & ng[i]) != 0) continue;
teams[t] += 1 << i;
sum += Dfs(i + 1);
teams[t] -= 1 << i;
}
if (teams.Count < T)
{
teams.Add(1 << i);
sum += Dfs(i + 1);
teams.RemoveAt(teams.Count - 1);
}
return sum;
}
var answer = Dfs(0);
Console.WriteLine(answer);
}
問題E
次のような動的計画法を解きます。
dp[i,f] := i番目までみたときのf(0|1)の個数
0に対して否定論理積をとる場合、0⊼0=1、1⊼0=1であることから、それまでの0と1の個数が1になることがわかります。
また、1に対して否定論理積をとる場合、0⊼1=1、1⊼1=0であることから、それまでの0の個数が1になり、それまでの1の個数が0になることがわかります。
これらのことから、遷移としては、次のようになります。
S[i]==0のとき
dp[i+1,0] += 1 // S[i]
dp[i+1,1] += dp[i,0] // 0⊼0=1
dp[i+1,1] += dp[i,1] // 1⊼0=1
S[i]==1のとき
dp[i+1,0] += dp[i,1] // 1⊼1=0
dp[i+1,1] += dp[i,0] // 0⊼1=1
dp[i+1,1] += 1 // S[i]
各i番目までみたときの1の個数の総和が答えとなります。
public static void Solve()
{
var N = Scanner.Scan<int>();
var S = Scanner.Scan<string>();
var dp = new long[N + 1, 2];
for (var i = 0; i < N; i++)
{
var f = S[i] - '0';
dp[i + 1, f]++;
if (f == 0)
{
dp[i + 1, 1] += dp[i, 0] + dp[i, 1];
}
else
{
dp[i + 1, 0] += dp[i, 1];
dp[i + 1, 1] += dp[i, 0];
}
}
long answer = 0;
for (var i = 1; i <= N; i++)
{
answer += dp[i, 1];
}
Console.WriteLine(answer);
}