AtCoder Beginner Contest 165 感想&解説 - Ruteのプログラミング日記

2020/05/02 (土) 21:10-22:50に、AtCoder Beginner Contest 165 が開催されました！

皆さん、お疲れ様でしたー。https://atcoder.jp/contests/abc165

私は、ABの2完で撤退。今回はC問題のDifficultyが1197と、ほぼ水色近くのDifficultyでしたが、D問題はそれに対し505でした。

(C問題とD問題でDifficultyに壁が出来るのはよく見るのですが、今回の場合は

C問題とE問題の間にD問題の谷が出来ていたように感じます。)

発行日: 2020/05/02

では問題について振り返っていきましょう。

A問題 A-We Love Golf

https://atcoder.jp/contests/abc165/tasks/abc165_a

問題概要:

$A$ 以上 $B$ 以下の整数の範囲のうち、 $K$ の倍数があれば"OK",なければ"NG"と出力せよ。

100点問題でループ....!? と最初戸惑いました。私はループを用いて $A$ 以上 $B$ 以内にKの倍数があるかを判定しました。

(これは、 $O(B-A+1)$ で高速です。)

ただ、回答例を見ると $O(1)$ で解く解法もあったので、そういう考え方もあるのかと納得させられました。

B問題 B-1%

https://atcoder.jp/contests/abc165/tasks/abc165_b

問題概要:

$100×1.01^{N}≧X$ が成り立つ $N$ のうち、最小のものを求めよ。

最初、Dice And Coinのようにlogを用いて解くのかと思っていました。

＜このような式変形を考えていました＞

$X≦100×1.01^{N}$

$\log_{1.01} X≦ \log_{1.01} 100 +\log_{1.01} 1.01^N$

$\log_{1.01} X≦\log_{1.01} 100+ N$

$\log_{1.01} X- \log_{1.01} 100 ≦ N$

(これを満たす最小の $N$ が答え)

ただ、式変形が間違っていたかどうか分からないのですが、計算結果がサンプルの出力と異なっていました。

よくよく考えると、 $X = 10^{18}$ の時、答えは $3760$ となっていたので、

$100$ に $1.01$ を掛け合わせて続け、掛け合わせた段階で $X$ を超えていた時の年数を出力すればよかったのでした。(単純なループで良かったのです)

D問題 D - Floor Function

https://atcoder.jp/contests/abc165/tasks/abc165_d

問題概要:

$A,B,N$ という3つの整数が与えられます。

$0≦x≦N$ の範囲における、 $floor(Ax/B)-A×floor(x/B)$ の最大値を求めよ。

コンテスト中に解けなかったのですが、よくよく考えるとこれはwolframを利用すれば考えが容易になるということがわかりました。

wolframでこの関数のグラフを出力してみると、

このような出力になりました。よって、考えるのは $0≦x≦B-1$ の範囲まででよく、

関数を $f(x)$ としたときに、 $f(N)$ と $f(B-1)$ の値のうち最大のものを出力すればよかったということになります。

計算量は言うまでもなく $O(1)$ です。

(コンテスト後で復習しました。)

以上、AtCoder Beginner Contest 164 感想 &解説でした。

(今回は茶Difficultyが解けなかったのがつらい....)