はじめに
AtCoder Beginner Contest 315の復習記事です。
記事における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/abc315
問題A
aeiou以外の文字を連結したものが答えになります。
public static void Solve()
{
var S = Scanner.Scan<string>();
var builder = new StringBuilder();
const string AEIOU = "aeiou";
foreach (var c in S)
{
if (!AEIOU.Contains(c)) builder.Append(c);
}
var answer = builder.ToString();
Console.WriteLine(answer);
}
問題B
真ん中の日midは、(Dの総和+1)/2で求めることができます。
合計日数を数え上げながら順に月を見ていき、その月以前の合計日数+その月の日数がmid以上になったとき、その月が答えの月となり、mid-その月以前の合計日数でその月の日にちを求めることができます。
public static void Solve()
{
var M = Scanner.Scan<int>();
var D = Scanner.ScanEnumerable<int>().ToArray();
var sum = D.Sum();
var mid = (sum + 1) / 2;
var cum = 0;
for (var i = 0; i < M; i++)
{
if (cum + D[i] < mid)
{
cum += D[i];
}
else
{
Console.WriteLine($"{i + 1} {(mid - cum)}");
return;
}
}
}
問題C
2つのカップの組み合わせを愚直に探索してしまうと、時間計算量がO(N^2)となり、実行時間制限に間に合いません。
そこで、2つのカップの味が異なるときの最大値と、2つのカップの味が一緒の時の最大値を求め、最終的な最大値を求めます。
2つのカップの味が異なるとき、全てのカップのうち美味しさSが最大のものと、それとは異なる味のうち美味しさSが最大となるものが最大の満足度となります。
2つのカップの味が一緒のとき、各味において美味しさSが大きい方から2つ選んだものが、各味における満足度の最大となります。
これにより、2つのカップの味が異なるときの最大値と、各味2つ選んだ時の最大値のうち、最大となるものが答えとなります。
public static void Solve()
{
var N = Scanner.Scan<int>();
var S = new Dictionary<long, Dictionary<int, int>>();
var ices = new (int F, long S)[N];
for (var i = 0; i < N; i++)
{
var (f, s) = Scanner.Scan<int, long>();
ices[i] = (f, s);
}
Array.Sort(ices, (x, y) => y.S.CompareTo(x.S));
long answer = 0;
for (var i = 1; i < N; i++)
{
if (ices[i].F != ices[0].F)
{
answer = ices[0].S + ices[i].S;
break;
}
}
var count = new int[N + 1];
var same = new long[N + 1];
for (var i = 0; i < N; i++)
{
var (f, s) = ices[i];
if (count[f] == 0)
{
count[f]++;
same[f] += s;
}
else if (count[f] == 1)
{
count[f]++;
same[f] += s / 2;
}
}
for (var i = 1; i <= N; i++)
{
answer = Math.Max(answer, same[i]);
}
Console.WriteLine(answer);
}
問題D
また解けていません。
問題E
本iの前提となる各本Pを、iから各Pに対する有向辺としたグラフとしたとき、このグラフに対して1を始点とした深さ優先探索の帰りがけ順に頂点を並べたものが答えとなります。
public static void Solve()
{
var N = Scanner.Scan<int>();
var G = new List<int>[N].Select(x => new List<int>()).ToArray();
var queue = new Queue<int>();
var used = new bool[N];
for (var i = 0; i < N; i++)
{
var P = Scanner.ScanEnumerable<int>().ToArray();
foreach (var v in P.Skip(1).Select(x => x - 1))
{
G[i].Add(v);
}
}
var answer = new List<int>();
void Dfs(int u)
{
foreach (var v in G[u])
{
if (used[v]) continue;
Dfs(v);
}
used[u] = true;
answer.Add(u);
}
Dfs(0);
Console.WriteLine(string.Join(" ", answer.Select(x => x + 1).Where(x => x != 1)));
}