AtCoder Beginner Contest 170
2020-06-16
コンテスト中に挑戦した問題についての感想とか.
A - Five Variables
1 2 3 4 5という入力が与えられるので, 0である場所を選ぶという問題
B - Crane and Turtle
鶴亀算が可能かどうかの問題.
全部亀の数をZとすると, 足の数は
(+ (* 2 (- X Z)) (* 4 z))
つまり,
(+ (* 2 X) (* 2 Z))
本の足があることになる.
Zの範囲は0からXなので, Yの範囲は2Xから4Xで, その間の偶数なら足の数としてあり得る.
それを判定すれば良い.
C - Forbidden List
問題分の『そのような整数が複数存在する場合は、そのうち最も小さいものを答えてください。』を読み飛ばしていたのでまずかった.
サンプルケースでそれを注意してくれていたので優しい.
与えられる数の範囲が限られているので, 箱(配列)を用意して, Xからどれだけ離れているかをキーとしてboolで保持
iをインクリメントしつつX + iとX - iが与えられていないことを探る.
今考えたら配列二つに分ける必要なかったが, Xの左右に分ける実装にしていたので, 一つの配列で書けるように書き直した. (でも, このパターンのほうが実行時間とメモリ使用量が上がっていた. 判定の際に計算しないといけないからかな.)
最初に書いた, 小さいものを答える条件があるのでX - iの方から判定を行えば良い.
D - Not Divisible
単純に割れるかどうかを判定していると間に合わない. (O(NN))
で, 間に合わなかった.
解答としては,
- 与えられた数がどういう数を割るかということを集計する.
- 与えられた数が他の数によって割られないことを確認する.
という2段階に分ける.
2段階目はO(N)で, 1段階目は以下のようにする.
- 1から与えられた数の最大値まで(あるいは与えられる数の上限まで)をインデックスに持つ配列をtで初期化して作る.
- 与えられた値を順番に見ていって, 与えられた数より大きい与えられた数の倍数がインデックスになる位置をnilにする.
- 作った配列はインデックスiがtならばiを割る数は与えられなかったことになるので, 与えれた数を走査してその様なものがあれば答えをインクリメントする.
最後に気を付けなければいけない点は同じ数があった場合にそれらは互いに割り切るので, 与えられた数をソート(O(NlogN))しておいて, 両隣に同じ数がある場合は答えとしてカウントしなければ良い.
1段階目の計算量を考える.
与えられた数の最大値をMとする, xの倍数はM/x存在するので,
(loop :for x :from 1 :to M :collect (/ M x))
で抑えられる.
1/xの不定積分がlog(x)+Cとなるから上の値はMlogMと近似できるので, 同じxについて計算しないとすると1段階目の計算量はO(MlogM)で抑えられる.
全体としてO(MlogM + NlogN)で抑えられる.
実装的な話で言うと, 解答見てから書いてみた時の話であるが, loopマクロのtoはピッタリその値ではなく上限(含む)を意味していることを忘れていた.