AtCoder Beginner Contest 165 に C# で参加した記録
AtCoder Beginner Contest 165 – AtCoder
ABC165 にC#で参加しました。結果はABCDの4問ACでした。
開始が10分遅れるという問題がありましたが、レートがつくコンテストになりました。
パフォーマンスは1300くらいでレートは10くらい上がりました。
C問題が普段と異なり実装よりの重たい問題だったので、D問題の正答者数のほうがC問題より多くなっているのが驚きでした。D問題のほうは数学ひらめき問題系だったので私個人としては難しく感じましたが、何とかACできました。
以下、振り返ります。
A – We Love Golf
ジャンボ高橋君はゴルフの練習をすることにしました。
ジャンボ高橋君の目標は飛距離を K の倍数にすることですが、ジャンボ高橋君の出せる飛距離の範囲は A 以上 B 以下です。
目標の達成が可能であれば OK と、不可能であれば NG と出力してください。
これは単純にA以上B以下の整数すべてに対してKで割り切れるか判定すればよいです。
for (int i = A; i <= B; i++)
{
if (i % K == 0)
{
Console.WriteLine("OK");
return;
}
}
Console.WriteLine("NG");"OK" と "NG" の文言を間違えないように注意しましょう。
B – 1%
高橋くんはAtCoder銀行に 100 円を預けています。
AtCoder銀行では、毎年預金額の 1 % の利子がつきます(複利、小数点以下切り捨て)。
利子以外の要因で預金額が変化することはないと仮定したとき、高橋くんの預金額が初めて X 円以上になるのは何年後でしょうか。
制約
- 101≤X≤1018
- 入力はすべて整数
入力で与えられるXが非常に大きいので難しそうに感じますが、実は数学的な考察は必要なく、愚直に複利の計算をシミュレートすればOKです。
入力例2で 1018 の答えが 3760 なのでループでシミュレートしても高々3760回程度の計算しか行われないことからわかります。複利の力がすごいです。
ということでループでXを超えるまで1%の利子を計算し続ければOKです。
var now = 100L;
var ans = 0;
while (now < X)
{
ans++;
// 1%の利子は100で割った値
now += now / 100;
}
Console.WriteLine(ans);1%の複利の計算は、現在の金額に100で割った切り捨てを足し合わせればよいです。なお64bit整数で桁あふれはしません。
利子を求める部分で now * 101 / 100 とすると桁あふれします。これに気づくのに時間がかかりました。
C – Many Requirements
正整数 N , M , Q と、4 つの整数の組 ( ai , bi , ci , di ) Q 組が与えられます。
以下の条件を満たす数列 A を考えます。
- A は、長さ N の正整数列である。
- 1≤A1≤A2≤⋯≤AN≤M
この数列の得点を、以下のように定めます。
- Abi−Aai=ci を満たすような i についての、 di の総和 (そのような i が存在しないときは 0)
A の得点の最大値を求めてください。
制約
- 入力は全て整数
- 2≤N≤10
- 1≤M≤10
- 1≤Q≤50
- 1≤ai<bi≤N (i=1,2,…,Q)
- 0≤ci≤M−1 (i=1,2,…,Q)
- (ai,bi,ci)≠(aj,bj,cj) (i≠j のとき)
- 1≤di≤105 (i=1,2,…,Q)
すごくややこしい問題で、気後れしてしましますが、とにかく言われた通りの操作を実行できるか考えます。
まず制約に目を向けると、NもMもQも小さい数字であることから全探索ができそうです。だいたいC問題の難し気な問題は大体全探索で解けると思います。今回の問題だと、条件を満たす正整数列Aをすべて列挙し、そのすべてに対してQ個の整数の組についての得点を求めて最大値を探すことにします。
var N = sc.ReadInt();
var M = sc.ReadInt();
var Q = sc.ReadInt();
var A = new int[Q];
var B = new int[Q];
var C = new int[Q];
var D = new long[Q];
for (int i = 0; i < Q; i++)
{
A[i] = sc.ReadInt();
B[i] = sc.ReadInt();
C[i] = sc.ReadInt();
D[i] = sc.ReadLong();
}
var ans = 0L;
var array = new int[N];
// 正整数列のn番目の要素を作成する再帰関数
void Rec(int n, int prev)
{
// 正整数列Aができたので得点を計算する
if (n == N)
{
var res = 0L;
// Q組の整数について得点を計算する
for (int i = 0; i < Q; i++)
{
var ai = A[i] - 1;
var bi = B[i] - 1;
if (array[bi] - array[ai] == C[i]) res += D[i];
}
// 最大値を答えとする
ans = Math.Max(ans, res);
return;
}
// 直前の値以上の値を生成する
for (int d = 0; d <= M; d++)
{
var now = prev + d;
if (now > M) break;
array[n] = now;
// 次の要素を生成する
Rec(n + 1, now);
}
}
// 正整数列(1以上)にしなければならないので prev=1 で生成する
Rec(0, 1);
Console.WriteLine(ans);正整数列の列挙は再帰関数を使って行うのが良いと思います。直前の要素以上でM以下の値をループして作成します。これをN回再帰的に呼び出せば、完成します。あとはこの数列について得点を計算すればOKでした。
計算量についてはコンテスト中に考えたんですが、詳しくはわからなかったです。editorial.pdf に計算量の詳細があります。
D – Floor Function
整数 A, B, N が与えられます。
N 以下の非負整数 x に対する floor(Ax/B)−A×floor(x/B) の最大値を求めてください。
ただし、floor(t) とは、実数 t 以下の最大の整数のことを表します。
制約
- 1≤A≤106
- 1≤B≤1012
- 1≤N≤1012
- 入力は全て整数
とりあえず制約が大きいので全探索はできません。つまり数学的にO(1)で求める必要がありそうです。二分探索とかもあり得るのですが、今回は違いました。書いたコードが以下の通りです。
var x = Math.Min(B - 1, N);
var ans = (A * x) / B - A * (x / B);
Console.WriteLine(ans);20分考えて閃いたコードが当たりだった感じです。何を考えていたのか覚えてないですが、想定解法のコードがかけた感じです。
運がよかったです。
E – Rotation Matching
解けませんでした。
制約に反した入力のテストケースがあったみたいで、unrated になるかもしれないみたいです。
以上。
