AtCoder Regular Contest 113 備忘録

AtCoder Regular Contest 113 の備忘録です。

問題はこちら↓

AtCoder Regular Contest 113 - AtCoder

今回はAB2完でした。

・A問題:A*B*C

正整数 K が与えられる。3つの正整数 ( A , B , C ) であって、ABC≦K となるものの個数を求める。ただし、A , B , C の順番が異なるだけの組みも異なる組みとして数える。
まず積が K 以下となる3つの正整数の組を求める際に A と B が決まれば自然と C も決まることから、A と B を決め打ちして考えることにする。つまり、A を1 ~ K まで、B を 1 ~ K までループを回し C が1以上になるならば答えに C を足して行くことで求めることができる。ただし、この問題では K が 2*10^5 であり、A , B を全探索してしまうと K^2 程度の計算量となってしまう。そこで A と B の範囲を狭められないか考える。A を 1 ~ K までループを回して、その時に B の取りうる範囲を考えると、A が 1 の時は K まで考えられるが A が 2 になると K/2 ("A=2" * B ≦ K )、3 になると K/3("A=3" * B ≦ K ) と範囲がかなり絞れることがわかる。この事から各 A の時について B の取りうる最大値を求めてループを回す事で高速に求めることができる。
この B の最大値は二分探索を用いることで高速に求めることができる。これによって求めた B の範囲内を全探索すれば答えが求まる。

解答例(Python)
https://atcoder.jp/contests/arc113/submissions/20400787

・B問題:A^B^C

正整数 A , B , C が与えられる。A ^ B ^ C の十進法での 1 の位を求める。
A , B , C ≦ 10 ^ 9 と大きいためそのまま計算することが出来ない。しかし、求めたい答えは 1 の位だけなので上の桁の値は関係ない為、下の桁のみを使って計算をしてやればよい。ただし、一度に纏めて計算することも出来ないので B ^ C ( = X )を先に行い、その計算結果の下の桁を使って A ^ X とすることで時間内に計算することができるようになる。最後に求めた値の 1 の位を出力すればよい。ただし、C および X の下の桁が全て 0 だった場合には 0 乗されて 1 になってしまうので、その場合は C および X を 100 程度として計算するようにする。

解答例(Python)
https://atcoder.jp/contests/arc113/submissions/20401567