こんにちは, Shinoryoです.
今回はAtCoder Beginner Contest 196を, Pythonで解いてみた結果を書き連ねていこうと思います.
AtCoder Beginner Contest 196 - AtCoder
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
A - Difference Max
正解は$b - c$となります.
B - Round Down
math.floorを使用すると, $X$の値が大きすぎて誤差が発生してWAとなってしまいます.
そこで, 文字列型として処理して小数点を検索し, それより左側だけを取り出して出力するということをすれば, 誤差なく出力できます.
C - Doubled
$1$から$N$までの自然数に対し, その前半と後半が文字列として等しいかどうかを判定するには, $N$が大きすぎてTLEとなってしまいます.
そこで, $11$, $22$, $\ldots$ , $99$, $1010$, $1111$, $\ldots$ , $9999$, $100100$, $\ldots$のように, $i$を繰り返してできた数を順番に作り出していくことを考えます. その数が$N$を超えたとき, $i - 1$が答えとなります. 時間計算量は$O(N)$になります.
あるいは, それを二分探索で求めることもできます. $N < 10^{12}$ですので, 初期値は$0$と$10^6$にしておけば十分でしょう. 二分探索については「SOMPO HD プログラミングコンテスト2021(AtCoder Beginner Contest 192)をPythonで解く」でも記述しています. 時間計算量は$O(\log N)$になります.
SOMPO HD プログラミングコンテスト2021(AtCoder Beginner Contest 192)をPythonで解く
こんにちは, Shinoryoです. 今回は SOMPO HD プログラミングコンテスト2021(AtCoder Beginner Contest 192) を, Pythonで解いてみた結果を書き連ねていこうと思います. AtCoder Beginner Conte...
さらに, 以下のように考えることもできます.
- $N$の桁数が$1$のとき, 答えは明らかに$0$(後の$N$の桁数が奇数のときの処理と若干異なるので, 最初に分類しておく).
- $N$の桁数が偶数のとき, $N$の前半部分を$M$として取得します.
- $M$を2回繰り返した数が$N$より大きい場合, $M$を2回繰り返した数は含めずに, 答えは$M - 1$となります.
- $M$を2回繰り返した数が$N$以下の場合, $M$を2回繰り返した数を含めて, 答えは$M$となります.
- $N$の桁数が奇数のとき, 桁数の半分(小数点以下切り捨て)だけ$9$を繰り返した数が答えになります.
時間計算量は$O(1)$になります.
D以降
D以降は私の能力不足故に省略いたします.
0 件のコメント:
コメントを投稿 (Please feel free to ask me about your questions! You can use Japanese or English in the comments.)