AtCoder Beginner Contest 169 に C# で参加した記録
AtCoder Beginner Contest 169 – AtCoder
ABC169 にC#で参加しました。
結果はABCDFの5問ACで青パフォ、レートは昨日のARC級に続きいい感じに増えました。
B問題、C問題はyukicoderで似たような問題解いた気がして、冷静に取り組めた算数問題でした。E問題が全然意味不明で、F問題に取り組めたら解けました。DPは楽しいね。
ということで振り返ります。
A – Multiplication 1
A×B を求めてください。
掛け算問題第1問。やるだけ。以上。コードはいらない！
B – Multiplication 2
掛け算問題第2問。めちゃめちゃWAを稼いだのでは。
N 個の整数 A1,…,AN が与えられます。
A1×…×AN を求めてください。
ただし、結果が 1018 を超える場合は、代わりに -1 を出力してください。
制約
- 2≤N≤105
- 0≤Ai≤1018
- 入力は全て整数である。
N個の数を掛け算して結果を求めるプログラムを書きます。ただし制約を見ると 0≤Ai≤1018 なので各掛け算でオーバーフローが起こります。
オーバーフローしないような工夫が必要です。
まず、与えられた数に0が含まれるときは別途処理して 0 を出力して終わります。そうではないとき、掛け算を行います。
掛け算は最大で、1018*1018 が実行されることになるので、64bit整数ではまかなえません。
掛け算をオーバーフローしないようにする工夫はいくつかあります。
- 多倍長整数を使う。(C# だと
BigIntegerという多倍長整数があります。) - オーバーフローを検出する(C# だと
checked{}でくるむと例外として検出できます。) - 式変形して解く。(
1018 / A[i] < ansであればNGとする。)
想定解法は3つ目だと思います。いずれの場合も0が含まれる場合は必ず先に処理しておくことが必要です。すべての実装方法を試してみます。
多倍長整数を使う
var N = sc.ReadInt();
var A = sc.ReadLongArray(N);
if (A.Contains(0))
{
Console.WriteLine(0);
return;
}
BigInteger ans = 1L;
for (int i = 0; i < N; i++)
{
ans *= A[i];
if (ans > (long)1e18)
{
Console.WriteLine(-1);
return;
}
}
Console.WriteLine(ans);一番直感的な方法だと思います。1018を超えた時点で終了しましょう。一応桁が大きくなっても計算できるのが多倍長整数ですが、TLEする可能性が高まります。
オーバーフローを検出する
checked
{
var N = sc.ReadInt();
var A = sc.ReadLongArray(N);
if (A.Contains(0))
{
Console.WriteLine(0);
return;
}
var ans = 1L;
for (int i = 0; i < N; i++)
{
var ok = true;
try
{
ans *= A[i];
ok = ans <= (long)1e18;
}
catch (Exception)
{
ok = false;
}
if (!ok)
{
Console.WriteLine(-1);
return;
}
}
Console.WriteLine(ans);
}C# では checked キーワードでくるむとオーバーフローを例外として検出できます。今回の問題ではlong型でオーバーフローすると問答無用でNGです。また、オーバーフローしない範囲でも1018を超えるかどうかは判定しましょう。
ただし例外処理なので競技プログラミング的には邪道な気がします。邪道でもACできたら正義ですが。オーバーフローを検出するくらいなら多倍長整数を使うほうがスマートだと思います。
式変形で割り算を使って判定する
計算途中の値を accum 次にかける値を A[i] としたとき、
accum * A[i] > 1018であるかどうかを判定したいのでこれを式変形します。掛け算がオーバーフローの原因なのでこれを移行して割り算にします。
accum > 1018 / A[i]これで上の式と同等の判定式になります。解説PDFでもこんな感じの実装をしてました。なのであってると信じます。
var N = sc.ReadInt();
var A = sc.ReadLongArray(N);
if (A.Contains(0))
{
Console.WriteLine(0);
return;
}
var accum = 1L;
for (int i = 0; i < N; i++)
{
if (accum > (long)1e18 / A[i])
{
Console.WriteLine(-1);
return;
}
accum *= A[i];
}
Console.WriteLine(accum);コンテスト本番ではめんどくさいから多倍長整数使ったれと提出したら、0が含まれる場合を忘れて2WAです。そのあと式変形に書き換えてACしました。
C - Multiplication 3
A×B の小数点以下を切り捨て、結果を整数として出力してください。
制約
- 0≤A≤1015
- 0≤B<10
- A は整数B は小数第 2 位まで与えられる
掛け算問題3問目です。
この問題、yukicoderで類題を解いた気がします。yukicoderの星1.5を全部解けばこんな問題によく出会える気がします。気のせいかもしれませんが。
基本的に出力が小数にならない問題は浮動小数点型を使わないようにしたいです。言語によっては気にせず浮動小数で計算しても精度的に問題ない場合もあるようです。特にPythonなど。C#でもdouble型はだめですがdecimal型なら普通に計算しても通りました。
ただ想定解法のやり方は勉強しておいたほうがよいでしょう。
今回は制約が小数点第2位までしか与えられないので100倍して整数にして計算するのが良いです。A,Bの制約的にも最大で 1015*103=1018でlong型に収まります。
後は小数点以下切り捨てなので掛け算の後に100で割ればよいです。
var A = sc.ReadLong();
var B = long.Parse(sc.ReadStr().Replace(".", ""));
var C = A * B;
var ans = C / 100;
Console.WriteLine(ans);小数の入力を文字列として受け取り、小数点を取り除いたのちに整数型に変換しています。小数点以下2桁固定の入力なので、これで100倍したことにります。
あとは掛け算して100で割り算するだけです。
var A = sc.ReadLong();
var B = (decimal)sc.ReadDouble();
var ans = (long)(A * B);
Console.WriteLine(ans);これでも通るみたいです。小数の扱いと精度について勉強しないとですね。
D - Div Game
正の整数 N が与えられます。 N に対して、以下の操作を繰り返し行うことを考えます。
- はじめに、以下の条件を全て満たす正の整数 z を選ぶ。
- ある素数 p と正の整数 e を用いて、 z=pe と表せる
- N が z で割り切れる
- 以前の操作で選んだどの整数とも異なる
- N を、N/z に置き換える
最大で何回操作を行うことができるか求めてください。
制約
- 入力はすべて整数である。
- 1≤N≤1012
Nに対して素数のべき乗数で割り算を何回行えるかを数えます。ただし同じ数では割れません。素数のべき乗で割るのでNは素因数分解しましょう。
例えば 8(=26) のとき、26 で割ると1回でしか割れませんが、21, 22, 23 で割ると3回割れます。つまり小さい指数から順番に試せばよいことがわかります。指数は多くともlogN個くらいにしかならないので1つずつ試しても十分高速です。
ということで実装です。素因数分解は以下の関数を使います。
static List<Tuple<long, int>> PrimeFactors(long n)
{
var res = new List<Tuple<long, int>>();
var count = 0;
for (long x = 2; x * x <= n; x++)
{
count = 0;
while (n % x == 0)
{
n /= x;
count++;
}
if (count > 0) res.Add(Tuple.Create(x, count));
}
if (n != 1) res.Add(Tuple.Create(n, 1));
return res;
}素数と指数のペアのリストを返します。解法の実装はこんな感じです。
var N = sc.ReadLong();
// 素因数分解の結果
var pf = PrimeFactors(N);
var ans = 0;
foreach (var t in pf)
{
// 残りの使える指数の個数
var rem = t.Item2;
// 次に試す指数の個数(1,2,3...と順番に試す)
var now = 1;
while (true)
{
if (rem >= now)
{
// 残りの指数の個数より試している個数が少ない場合
ans++;
rem -= now;
}
else
{
break;
}
now++;
}
}
Console.WriteLine(ans);CもDは5分くらいで解けました。Bで10分2WAです。。。
E - Count Median
解けませんでした。1時間くらい考えたんですが。
F - Knapsack for All Subsets
長さ N の正整数列 A1, A2, …, AN と正の整数 S が与えられます。
集合{1,2,…,N} の空でない部分集合 T について、f(T) を以下のように定めます。
- T の空でない部分集合 {x1,x2,…,xk} であって、 Ax1+Ax2+⋯+Axk=S をみたすものの個数
T として考えられる集合は 2N−1 通りありますが、そのすべてに対する f(T) の和を求めてください。ただし、答えは非常に大きくなることがあるので、998244353 で割ったあまりを出力してください。
制約
- 入力は全て整数である。
- 1≤N≤3000
- 1≤S≤3000
- 1≤Ai≤3000
なぜかF問題が解けました。Eと交互ににらめっこして普通にナップサック問題に工夫したらACしました。
var N = sc.ReadInt();
var S = sc.ReadInt();
var A = sc.ReadLongArray(N);
var dp = new long[N + 1, S + 1];
dp[0, 0] = 1;
for (int i = 0; i < N; i++)
{
for (int j = 0; j <= S; j++)
{
// 選ばないとき、含む場合と含まない場合を考慮する
dp[i + 1, j] += dp[i, j] * 2;
dp[i + 1, j] %= 998244353;
var nj = j + A[i];
if (nj > S) continue;
// 含む場合は
dp[i + 1, nj] += dp[i, j];
dp[i + 1, nj] %= 998244353;
}
}
var ans = dp[N, S];
Console.WriteLine(ans);普通のナップサック問題のDPをしただけだとSにぴったり一致する場合の個数だけが求まります。Sに一致する足し算に使われなかった要素数の2乗が必要になりそうだなという風に考えたので、個数を数えられないかなとかいろいろ考えたのですが、結果、足し算に含まれない場合に先に2乗しておけばよいのではということでした。
ということで通常のナップサックDPに *2 を追加したらACしました。これでよいのか？たぶんよいでしょう。。。解説放送を確認します。
以上。
