はじめに
AtCoder Beginner Contest 238の復習記事です。
記事におけるScannerクラスは、自作の入力クラスです。
コンテスト
https://atcoder.jp/contests/ABC238
問題A
Nが1または5以上の時、答えはYesになります。
また、2のN乗を計算可能な大きさに丸めてから、実際に計算することでも求めることができます。
public static void Solve()
{
var N = Scanner.Scan<int>();
N = Math.Min(60, N);
var answer = (1L << N) > N * N;
Console.WriteLine(answer ? "Yes" : "No");
}
問題B
現在のナイフの角度を持ちながら、それぞれの切れ込みの角度を計算します。360度を超える場合はx+360度と同じ角度なので、360で余りを取ります。すべての切れ込みをソートし、各切れ込みの差分の最大値が答えとなります。
public static void Solve()
{
var N = Scanner.Scan<int>();
var A = Scanner.ScanEnumerable<int>().ToArray();
var list = new List<int> { 0 };
var curr = 0;
foreach (var a in A)
{
list.Add((curr + a) % 360);
curr += a;
curr %= 360;
}
list.Add(360);
list.Sort();
var answer = 0;
for (var i = 0; i + 1 < list.Count; i++)
{
answer = Math.Max(answer, list[i + 1] - list[i]);
}
Console.WriteLine(answer);
}
問題C
f(x)を時間計算量O(1)で求めることができても、Nまで愚直に数え上げると時間計算量O(N)かかり、制約に間に合いません。
それぞれの桁数の時の個数の和を求めます。
- 1からnまでの総和は
n * (n+1) / 2。 d桁の数字個数は10^d - 10^(d-1)個存在する。(2桁の場合は、10^2 - 10^1で90個)Nと同じ桁の場合はN - 10^(d-1) + 1個存在する。(16の場合は、16 - 10^(2-1) + 1で7個)
以上を踏まえて、Nと同じ桁数まで数え上げることで、時間計算量O(logN)で求めることができます。
public static void Solve()
{
var N = Scanner.Scan<long>();
mint answer = 0;
mint i2 = mint.Inverse(2);
mint F(long x) => (mint)x * (x + 1) * i2;
var curr = 1L;
for (var l = 1; l <= 18 && curr <= N; l++)
{
curr *= 10;
if (curr <= N)
{
var x = curr - curr / 10;
answer += F(x);
}
else
{
var x = N - curr / 10 + 1;
answer += F(x);
}
}
Console.WriteLine(answer);
}
問題D
ANDにより、x >= aかつy >= aがわかり、x <= yかつx = aとしたとき、y = a + bということがわかります。
s = x + y = a + a + b = 2a + bとなり、s - 2a = bが成り立つbの存在によって答えが求まります。
このとき、y = a + b = a | bとすると、bはaの0のビットをいくつか1にしたものかつaの1のビットをすべて0にしたものになります。
public static void Solve()
{
var T = Scanner.Scan<int>();
while (T-- > 0)
{
var (a, s) = Scanner.Scan<long, long>();
var a2 = a + a;
var answer = a2 <= s;
var r = s - a2;
if (r > 0)
{
for (var i = 0; i < 63; i++)
{
if ((r >> i & 1) == 1)
{
answer &= (a >> i & 1) == 0;
}
}
}
Console.WriteLine(answer ? "Yes" : "No");
}
}
問題E
コンテスト中の考察です。
- すべてのAの走査回数が奇数? -> 例3で偽
- クエリを右増左減のソート後に区間最小が0の時に区間を1に更新して最後に区間すべてが1であれば正? -> 例1で偽
解説では、累積和行列Bを考えたときに、クエリによりlとrが与えられた場合B[r] - B[l]の値からA[l]..A[r]の総和が求められるものとし、lとrをグラフの辺として考えたとき、0からNまで連結であることを考えればいいようです。
public static void Solve()
{
var (N, Q) = Scanner.Scan<int, int>();
var dsu = new DisjointSetUnion(N + 1);
for (var i = 0; i < Q; i++)
{
var (l, r) = Scanner.Scan<int, int>();
l--;
dsu.Merge(l, r);
}
var answer = dsu.IsSame(0, N);
Console.WriteLine(answer ? "Yes" : "No");
}