エイシング プログラミング コンテスト 2020 に C# で参加した記録
エイシング プログラミング コンテスト 2020 – AtCoder
エイシング プログラミング コンテスト 2020 にC#で参加しました。
結果はABCDの4問ACでした。C問題で制約を勘違いして時間をロスしました。D問題は初歩的なコーディングミスを犯してREを重ねました。
ABC相当の難易度のコンテストでしたが、結構難しめのセットだったようです。レートは微増で助かった感じです。
では振り返ります。
A – Number of Multiples
L 以上 R 以下の整数のうち、d の倍数であるようなものはいくつありますか？
これはよく見る典型の数え上げです。
X以下の整数について、dの倍数であるようなもの(つまりdで割り切れるようなもの)は X/d で求まります。
R 以下の整数について d の倍数の個数が求まれば、あとは L-1 以下の整数について d の倍数を求めて引いてあげればよいです。
var L = sc.ReadInt();
var R = sc.ReadInt();
var d = sc.ReadInt();
var ans = R / d - (L - 1) / d;
Console.WriteLine(ans);まあ、この問題は制約が小さいので全探索してもOKです。
var L = sc.ReadInt();
var R = sc.ReadInt();
var d = sc.ReadInt();
var ans = 0;
for (int i = L; i <= R; i++)
{
if (i % d == 0) ans++;
}
Console.WriteLine(ans);B – An Odd Problem
1,2,3,…,N の番号がついた N 個のマスがあります。各マスには整数が書かれており、マス i には ai が書かれています。
以下の 2 つの条件の両方を満たすマスはいくつありますか？
- マスの番号は奇数
- マスに書かれた整数は奇数
for文回して数えるだけです。
var N = sc.ReadInt();
var A = sc.ReadIntArray(N);
var ans = 0;
for (int i = 0; i < N; i++)
{
if (i % 2 == 0 && A[i] % 2 == 1) ans++;
}
Console.WriteLine(ans);C – XYZ Triplets
f(n) を以下の 2 つの条件の両方を満たすような 3 つの整数の組 (x,y,z) の個数とします。
- 1≤x,y,z
- x2+y2+z2+xy+yz+zx=n
整数 N が与えられるので、f(1),f(2),f(3),…,f(N) をそれぞれ求めてください。
制約
- 与えられる入力は全て整数
- 1≤N≤104
基本的な方針としては全探索です。
ただし単純に全探索すると、N 回のループを3重にして O(N3) になってTLEすると思います。
ただ、x2+y2+z2+xy+yz+zx が N 以上になったらそれ以上は計算しても無駄なので無視します。こうすれば無駄な計算をせずに間に合います。
解説PDFでは先にx,y,zの範囲を考えてからループ回数を決め撃ってました。
var N = sc.ReadLong();
var list = new long[N + 1];
for (int x = 1; x < N; x++)
{
for (int y = 1; y < N; y++)
{
if (x * x + y * y + x * y >= N) continue;
for (int z = 1; z < N; z++)
{
var f = x * x + y * y + z * z + x * y + y * z + z * x;
if (f <= N) list[f]++;
if (f > N) continue;
}
}
}
for (int i = 1; i <= N; i++)
{
Console.WriteLine(list[i]);
}D – Anything Goes to Zero
popcount(n) を n を 2 進表記したときの 1 の個数とします。 例えば、popcount(3)=2,popcount(7)=3,popcount(0)=0 です。
f(n) を、「n を popcount(n) で割ったあまりに置き換える」という操作を繰り返した際に n が 0 になるまでの操作回数とします(この問題の制約下で n が有限回の操作後に必ず 0 になることが証明できます)。
以下は n=7 の例で、2 回の操作で n が 0 になります。
- popcount(7)=3 なので、7 を 3 で割ったあまりである 1 に置き換えます。
- popcount(1)=1 なので、1 を 1 で割ったあまりである 0 に置き換えます。
2 進表記で N 桁の整数 X が与えられます。 1≤i≤N を満たす整数 i について、X の上から i 桁目のビットを反転した整数を Xi とします。 f(X1),f(X2),…,f(XN) を求めてください。
制約
- 1≤N≤2×105
- X は 2 進表記で N 桁の(先頭の桁が 1 とは限らない)整数
一目問題がややこしくて難しそうです。Nの制約が大きく、愚直に計算することも難しそうです。
まずはNが最大の場合を考えます。2進表記で2×105桁になるので当然 long 型などの整数型には収まりません。ただし1回操作すると、どんなに大きな数でも1の個数で割った余りになるので、大きくても2×105以下の数になります。これなら普通の計算ができそうです。
N, Xが小さいとき
Nが小さいときは、問題文通りの操作を実行して計算量的に問題ありません。ただし、popcount() をできるだけ高速に求めたいです。が、今回は簡単のため、以下のように32桁分のループを回してビット演算で求めることにします。
static int PopCount(uint n)
{
var count = 0;
for (int i = 0; i < 32; i++)
{
if (((n >> i) & 1) == 1) count++;
}
return count;
}
// 動作確認
// for (int i = -10; i <= 10; i++)
// {
// var s = Convert.ToString(i, 2).PadLeft(32, '0');
// Console.WriteLine($"{s} {PopCount((uint)i)}");
// }C++だと組み込みで用意されてるコンパイラもあるみたいですが、C#だと自前実装する必要があります。今回の問題ではこの実装で十分です。
これを使って小さい数で何回操作できるか求めてみます。
var X = 7;
var ans = 0;
while (X > 0)
{
ans++;
var count = PopCount((uint)X);
X %= count;
}
Console.WriteLine(ans);こんな感じで求まります。Xをint型の範囲で大きくしても問題ありません。
N, Xが大きいとき
Nが大きいとき、どのようになるかを考えます。先ほど述べた通り、1回目の操作が大変ですが2回目以降は値がint型の範囲に収まるので、上の計算を使えば求められそうです。
Nが大きいと余りの計算が難しいですが、各桁独立に余りを求めることで2進表記で膨大な桁を持つ数でも余りが求まります。
今回の問題では各桁のビットを反転した値に対して操作を行います。したがって各桁の操作後には popcount(X)±1 だけ1の個数があることになります。それぞれのパターンについて、余りを求めておきます。
あとは各桁における反転後の数を求めます。1の桁を反転する場合は -2i 、0の桁を反転する場合は +2i します。こうすることで、1回操作した後の値が求まります。
2回目以降は上で自走した処理を使えばOKです。
ゼロ除算の例外ケース
単純に上の内容を実装する popcount(X)-1==0 のとき、0除算が発生して RE になります。したがって、この場合は特殊扱いしてやる必要があります。
これは簡単で、popcount(X)==1 && X[i]=='1' の場合、操作回数0にしてやるだけです。すべての桁が0の時、値が0になるので操作回数は0回です。
これでRE食らいました。
実装
// 下の位から計算したいのでXを反転しておく
var N = sc.ReadInt();
var X = sc.ReadStr().Reverse().ToArray();
// popcount(X)±1
var pcount = X.Count(c => c == '1');
var pc = new int[2];
pc[0] = pcount + 1;
pc[1] = pcount - 1;
// ゼロ除算しないように1にする
if (pc[1] == 0) pc[1] = 1;
// popcount(X)±1で余りを求めたXの値
var v = new long[2];
// popcount(X)±1で余りを求めた2^iとX
var pow = new long[N, 2];
pow[0, 0] = 1;
pow[0, 1] = 1;
for (int i = 0; i < N; i++)
{
for (int j = 0; j < 2; j++)
{
if (i > 0)
{
// 2^iを求める
pow[i, j] = pow[i - 1, j] * 2;
pow[i, j] %= pc[j];
}
// Xの値を余りをとりながら求める
if (X[i] == '1') v[j] += pow[i, j];
v[j] %= pc[j];
}
}
// 2回目以降の操作を数える
// 上位桁から出力するので逆順
for (int i = N - 1; i >= 0; i--)
{
// 1個しかない'1'を反転すると0になるので操作ゼロ回
if (pcount == 1 && X[i] == '1')
{
Console.WriteLine(0);
continue;
}
// X[i] == '0' の時、1になるのでpopcount(X)+1で余りを求める
// X[i] == '1' の時、0になるのでpopcount(X)-1で余りを求める
var j = X[i] - '0';
var now = v[j];
// 反転後の値の変化を計算しておく
if (X[i] == '0')
{
now += pow[i, j];
now %= pc[j];
}
else
{
now -= pow[i, j];
if (now < 0) now += pc[j];
}
// 2回目以降の操作は普通に計算して求める
var ans = 1L;
while (now > 0)
{
ans++;
now %= PopCount((uint)now);
}
Console.WriteLine(ans);
}Dに手間取りすぎてEは解けませんでした。
