はじめに
AtCoder Beginner Contest 338の復習記事です。
記事における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/abc338
問題A
先頭のみ大文字で、それ以降は全て小文字であることを判定します。
C#では、char.IsUpper()で文字が大文字であるかを判定でき、char.IsLower()で文字が小文字であるかを判定できます。
例
public static void Solve()
{
var S = Scanner.Scan<string>();
var answer = char.IsUpper(S[0]);
for (var i = 1; i < S.Length; i++)
{
answer &= char.IsLower(S[i]);
}
Console.WriteLine(answer ? "Yes" : "No");
}
問題B
文字の出現数を数え上げ、最大出現数とその文字を管理しながら、26文字を全探索します。
例
public static void Solve()
{
var S = Scanner.Scan<string>();
var count = new int[26];
foreach (var c in S)
{
count[c - 'a']++;
}
var answer = 'a';
var max = 0;
for (var i = 0; i < 26; i++)
{
if (count[i] > max)
{
answer = (char)(i + 'a');
max = count[i];
}
}
Console.WriteLine(answer);
}
問題C
料理Aの数の最大はA[i]==0のときを除いたQ[i]/A[i]の最小となり、料理Aを作る数を固定して考えます。
料理Aの数をaとしたとき、i番目の材料の残りはR[i]=Q[i]-a*A[i]であり、この時料理Bの最大はB[i]==0のときを除いたR[i]/B[i]の最小bになります。
よって、このa+bの最大値が答えとなります。
例
public static void Solve()
{
var N = Scanner.Scan<int>();
var Q = Scanner.ScanEnumerable<int>().ToArray();
var A = Scanner.ScanEnumerable<int>().ToArray();
var B = Scanner.ScanEnumerable<int>().ToArray();
const long Inf = 1L << 60;
var maxA = Inf;
for (var i = 0; i < N; i++)
{
maxA = Math.Min(maxA, A[i] == 0 ? Inf : (Q[i] / A[i]));
}
long answer = 0;
for (var a = 0; a <= maxA; a++)
{
var b = Inf;
for (var i = 0; i < N; i++)
{
var r = Q[i] - a * A[i];
var maxB = B[i] == 0 ? Inf : (r / B[i]);
b = Math.Min(b, maxB);
}
answer = Math.Max(answer, a + b);
}
Console.WriteLine(answer);
}
問題D
まだ解けていません。
問題E
弦をA[i]からB[i]の辺、B[i]-A[i]>Nの場合はB[i]からA[i]の1周分先の頂点としたA[i]+N*2への辺とします。
また、A[i]+1==B[i]の場合は円周上の辺と同じなので無視します。
辺の右端を降順に管理する優先度付きキューを用意します。
- 頂点
aを辺の左端、頂点aから辺でつながる頂点をbとします。 - キューから
a以下の頂点を削除します。 - キューの最初の頂点
xがa<x&&x<bの場合は、弦が交差します。 - それ以外のとき、キューに
bを追加します。
この操作を繰り返し、弦が交差するかどうかを判定します。
例
public static void Solve()
{
var N = Scanner.Scan<int>();
var M = N * 2;
var G = new List<int>[M].Select(x => new List<int>()).ToArray();
for (var i = 0; i < N; i++)
{
var (a, b) = Scanner.Scan<int, int>();
a--; b--;
if (a > b) (a, b) = (b, a);
if (b - a > N) (a, b) = (b, a + M);
if (a + 1 != b) G[a].Add(b);
}
var queue = new PriorityQueue<int, int>();
for (var a = 0; a < M; a++)
{
while (queue.Count > 0 && queue.Peek() <= a) queue.Dequeue();
foreach (var b in G[a])
{
if (queue.TryPeek(out var x, out _))
{
if (a < x && x < b)
{
Console.WriteLine("Yes");
return;
}
}
}
foreach (var v in G[a])
{
queue.Enqueue(v, v);
}
}
Console.WriteLine("No");
}