AtCoder Beginner Contest 172 に C# で参加した記録
AtCoder Beginner Contest 172 – AtCoder
ABC172 にC#で参加しました。
結果はABCDの4問ACでレートはD問題で躓いて残念な結果に。
C問題が普段よりちょっと難しかったような気がしますが、典型でいい感じの問題で楽しかったです。D問題は制約がやや厳しくて、高速化に1時間近くかかりました。
E問題は今までになくさっぱりで、手も足も出ない感じでした。
レートは下がってしまいましたが、こういう日もあるということで。振り返ります。
A – Calc
整数 a が入力されます。値 a+a2+a3 を出力してください。
やるだけ。Math.Pow(a, 2) みたいにするとdouble型になるので、普通の掛け算でやります。
var A = sc.ReadInt();
var ans = A + A * A + A * A * A;
Console.WriteLine(ans);B – Minor Change
文字列 S, T が与えられます。次の操作を繰り返して S を T に変更するとき、操作回数の最小値を求めてください。
- 操作：S の 1 文字を選んで別の文字に書き換える
制約
- S, T は長さ 1 以上 2×105 以下
- S, T は英小文字のみからなる
- S と T の長さは等しい
2つの文字列を1文字目から順番に比較していき、異なる文字を数え上げればよいです。
var S = sc.ReadStr();
var T = sc.ReadStr();
var ans = 0;
for (int i = 0; i < S.Length; i++)
{
if (S[i] != T[i]) ans++;
}
Console.WriteLine(ans);C – Tsundoku
二台の机 A, B があります。机 A には N 冊の本が、机 B には M 冊の本が、それぞれ縦に積まれています。
机 A に現在上から i 番目に積まれている本 (1≤i≤N) は読むのに Ai 分を要し、机 B に現在上から i 番目に積まれている本 (1≤i≤M) は読むのに Bi 分を要します。
次の行為を考えます。
- 本が残っている机を選び、その机の最も上に積まれた本を読んで机から取り除く。
合計所要時間が K 分を超えないようにこの行為を繰り返すとき、最大で何冊の本を読むことができるでしょうか。本を読むこと以外に要する時間は無視します。
制約
- 1≤N,M≤200000
- 1≤K≤109
- 1≤Ai,Bi≤109
- 入力中の値はすべて整数である。
読む方法はAの先頭からいくつかと、Bの先頭からいくつかです。飛ばしたりできないので必ず先頭から連続した幾つかになります。
このときAとBから読んだ本の合計が多ければ多いほど良いですが、条件として所要時間はK分以下でなければいけません。
N,Mがともに大きいので2重のループで愚直に数え上げるとTLEします。したがって何らかの方法で高速化してやる必要があります。私が実装したのは累積和＋二分探索です。
まず、机Aから読む本の数(0以上N以下)をすべて試します。Aの個数が決まったとき、残りの時間でBを先頭から読めるだけ読めばよいです。この時二分探索で読める範囲で一番大きな数を計算します。あとは冊数の最大を求めればOKです。
計算量は O(NlogM) となります。
累積和は二分探索時の判定に使います。
実装です。
var N = sc.ReadInt();
var M = sc.ReadInt();
var K = sc.ReadInt();
var A = sc.ReadIntArray(N);
var B = sc.ReadIntArray(M);
// 累積和を計算しておく
var sumA = new long[N + 1];
var sumB = new long[M + 1];
for (int i = 0; i < N; i++)
{
sumA[i + 1] = sumA[i] + A[i];
}
for (int i = 0; i < M; i++)
{
sumB[i + 1] = sumB[i] + B[i];
}
// Aの読む冊数を固定して全部試す
var ans = 0L;
for (int i = 0; i <= N; i++)
{
// Aをi冊読むとき、残り時間rem分
var rem = K - sumA[i];
// 負の数になるときはAからi冊以上は読めない
if (rem < 0) break;
// lがBから読める冊数
var l = 0;
var r = M + 1;
while (r-l > 1)
{
// mid冊読むとき、残り時間で読めるか判定
var mid = l + (r - l) / 2;
if (sumB[mid] <= rem) l = mid;
else r = mid;
}
// Aからi冊、Bからl冊読める
var res = i + l;
ans = Math.Max(ans, res);
}
Console.WriteLine(ans);累積和＋二分探索の方針がすぐに決まり、実装もバグらせずかけたので成長を感じます。典型問題はだいぶ慣れました。
D – Sum of Divisors
正整数 X に対し、X の正の約数の個数を f(X) とします。
正整数 N が与えられるので、∑NK=1K×f(K) を求めてください。
制約
- 1≤N≤107
シンプルな問題ですが制約がやや厳しめの印象を受けます。
N以下のすべての数の約数を列挙したり素因数分解をしたりするととても間に合いません。
解説PDF見ても方針がよくわからなかったですが私は以下のように解きました。
- N以下のすべての数について、エラトステネスの篩で最小素因数を求める。
- 2以上の数について、f(x)をもとめて記録しながら答えを求める。
- xが素数の時、f(x)=2
- xが合成数の時、最小素因数pで割った結果をyして、f(y)の記録からf(x)を計算する。
- xをpで割り切れる回数をcとしたとき、
f(x)=f(y)/c*c+1となる
- xをpで割り切れる回数をcとしたとき、
小さいほうから計算をして、小さい数の計算結果を利用しながら答えを求めました。
約数の個数f(x)を求めてる箇所の考え方はこんな感じです。
- 24(2331)の約数の個数は指数をみて、`42`で8個
- 12(2321)の約数の個数は指数をみて、`32`で6個
- 24の最小素因数は2、24は2で3回割り切れる
- 12の約数の個数6を3で割って4かける =>
6/3*4 = 8
前計算でN以下の数の最小素因数が O(NloglogN) くらいの計算量で求まるみたいです。よくわからないですが。
N以下の数の各計算過程において、最小素因数で割り切れる回数を求める箇所があり logN回くらいの計算が発生すると思いますが、十分高速なはずです。
[C#] エラトステネスの篩で素数列挙と素因数分解を実装する │ Web備忘録
エラトステネスの篩で素因数分解を実装する方法は上の記事にまとめてます。
var N = sc.ReadInt();
// エラトステネスの篩でN以下の数の最小素因数を求めておく
var era = new SieveOfEratosthenes(N);
// 1の計算結果は1なので初期値1
var ans = 1L;
// N以下の数の約数の個数を保持する配列
var list = new long[N + 1];
for (int i = 2; i <= N; i++)
{
// 素数であればその数の約数の個数は2個(1とその数自身)
if (era.IsPrime(i))
{
list[i] = 2;
ans += 2 * i;
continue;
}
// 最小素因数p
var p = era.Table[i];
// iがpで何回割り切れるか
var count = 0;
var now = i;
while (now % p == 0)
{
now /= p;
count++;
}
// i/pの約数の個数からiの約数の個数を計算する
var res = list[i / p] / count * (count + 1);
list[i] = res;
ans += i * res;
}
Console.WriteLine(ans);もっといい解法があると思うので解説見て頑張ります。
E,Fはわかりません。
以上。
