はじめに
AtCoder Beginner Contest 248の復習記事です。
記事におけるScannerクラスは、自作の入力クラスです。
コンテスト
https://atcoder.jp/contests/abc248
問題A
0から9の合計から登場する数字を全て引いた後の値が答えとなります。
public static void Solve()
{
var S = Scanner.Scan<string>();
var sum = 9 * 10 / 2;
foreach (var c in S)
{
sum -= c - '0';
}
Console.WriteLine(sum);
}
問題B
初期値をAとして、Bより小さいうちにAを何回K倍することができるかを数え上げます。
public static void Solve()
{
var (A, B, K) = Scanner.Scan<long, long, long>();
var curr = A;
var answer = 0;
while (curr < B)
{
curr *= K;
answer++;
}
Console.WriteLine(answer);
}
問題C
i番目の値まで決めたときに、それまでの総和がjであるような数列の総数を動的計画法として答えを数え上げます。
これは、i+1番目の値は、i番目までの総和jに1<=k<=Mの何れかを足した数への遷移することができます。
そのため、dp[0,0]=1 (0番目までの総和は0)を初期値として遷移していき、N番目まで見終わったときの1<=k<=Mの合計が答えとなります。
public static void Solve()
{
var (N, M, K) = Scanner.Scan<int, int, int>();
var NM = N * M;
var dp = new mint[N + 1, NM + 1];
dp[0, 0] = 1;
for (var i = 0; i < N; i++)
{
for (var j = 0; j <= NM; j++)
{
for (var k = 1; k <= M; k++)
{
if (j + k <= NM) dp[i + 1, j + k] += dp[i, j];
}
}
}
mint answer = 0;
for (var i = 1; i <= K; i++)
{
answer += dp[N, i];
}
Console.WriteLine(answer);
}
問題D
クエリごとに指定された範囲を走査してしまうと、クエリごとの計算量がO(N)、全体計算量がO(N^2)となってしまい、実行時間制限内に終えることができないので、クエリごとの計算量を削減する方法を考えます。
ある値Xを考えたとき、[L,R]の出現する場所の個数はRより大きい場所の番目 - L以上の場所の番目で求めることができます。
例えば、A=[3,1,4,1,5]、L=1、R=3、X=1のとき、場所idx[1]=[2,4]となり、Rより大きい場所の番目 - L以上の場所の番目は2番目-1番目なり、1個となります。
そのため、あらかじめ値ごとに出現する場所を保持しておき、LとRの個数をそれぞれ二部探索することで、クエリごとの計算量がO(logN)、全体計算量がO(NlogN)で求めることができます。
public static void Solve()
{
var N = Scanner.Scan<int>();
var A = Scanner.ScanEnumerable<int>().ToArray();
var dict = new Dictionary<int, List<int>>();
for (var i = 0; i < N; i++)
{
var a = A[i];
if (!dict.ContainsKey(a)) dict[a] = new List<int>();
dict[a].Add(i);
}
var Q = Scanner.Scan<int>();
while (Q-- > 0)
{
var (L, R, X) = Scanner.Scan<int, int, int>();
L--; R--;
if (dict.ContainsKey(X))
{
var list = dict[X];
var l = LowerBound(list, L);
var r = UpperBound(list, R);
Console.WriteLine(r - l);
}
else
{
Console.WriteLine(0);
}
}
}
問題E
コンテスト中の考察です。
- 全ての2点間の傾き
aと切片bを保持し、直線y=ax+bが成り立つ点がK個以上あればその直線は妥当? WAが11個でる...
数え上げの方法が間違えていました。
ある点を固定したとき、その点からの傾きが同じものどうしで数え上げ、その傾きをとる頂点の個数がK-1個ならば、その傾きの直線が妥当であるといえます。このとき
K-1以上で数えてしまうと、その傾きを取る頂点の個数がK+1、K、K-1のように重複して数えてしまうことに注意します。
public static void Solve()
{
var (N, K) = Scanner.Scan<int, int>();
if (K == 1)
{
Console.WriteLine("Infinity");
return;
}
var P = new (long X, long Y)[N];
for (var i = 0; i < N; i++)
{
var (x, y) = Scanner.Scan<long, long>();
P[i] = (x, y);
}
var answer = 0;
for (var i = 0; i < N; i++)
{
var dict = new Dictionary<Fraction, int>();
for (var j = i + 1; j < N; j++)
{
var (x1, y1) = P[i];
var (x2, y2) = P[j];
var (dx, dy) = (x2 - x1, y2 - y1);
var frac = new Fraction(dy, dx);
if (!dict.ContainsKey(frac)) dict[frac] = 0;
dict[frac]++;
}
foreach (var count in dict.Values)
{
if (count == K - 1) answer++;
}
}
Console.WriteLine(answer);
}
public readonly struct Fraction : IComparable<Fraction>, IEquatable<Fraction>
{
public long Y { get; }
public long X { get; }
public Fraction(long y, long x)
{
static long Gcd(long a, long b) => b == 0 ? a : Gcd(b, a % b);
var g = Gcd(y, x);
(Y, X) = (y / g, x / g);
}
public static bool operator <(Fraction left, Fraction right) => left.CompareTo(right) < 0;
public static bool operator <=(Fraction left, Fraction right) => left.CompareTo(right) <= 0;
public static bool operator >(Fraction left, Fraction right) => left.CompareTo(right) > 0;
public static bool operator >=(Fraction left, Fraction right) => left.CompareTo(right) >= 0;
public static bool operator ==(Fraction left, Fraction right) => left.Equals(right);
public static bool operator !=(Fraction left, Fraction right) => !left.Equals(right);
public int CompareTo(Fraction other) => (Y * other.X).CompareTo(X * other.Y);
public bool Equals(Fraction other) => Y == other.Y && X == other.X;
public override bool Equals(object obj) => obj is Fraction other && Equals(other);
public override int GetHashCode() => HashCode.Combine(Y, X);
public override string ToString() => $"{Y}/{X}";
}