ABC106 参加記録
今回はペナルティ込みで40分台全完。ABCオンリー回であればもっと速く解きたかったところ…
A - Garden
道の部分をくっつけると の長方形になります。
ACコード：Submission #3027956 - AtCoder Beginner Contest 106
B - 105
全探索しましょう。 の約数は
以下なので、
以下の奇数全部について、それ以下の数で全通り割って約数を数えます。問題全体で
なので十分間に合います。
「奇数」という制約を忘れないように（忘れるとサンプルが合わないので、そこで手が止まるようにはなっています）。
ACコード：Submission #3029027 - AtCoder Beginner Contest 106
C - To Infinity
操作を5000兆回繰り返した後の数列は、
- 1はそのまま
- 2以上の数字
は、
個に増殖
します。 は大きくても
オーダーなので、頭から見ていった結果は「先頭にあった1たち」＋「1でない数字のうち最初にあったものが大量に増殖したもの」で、残りは無視できます。
11234 → 112222222......(ここが意味不明なくらい長い)......(長すぎてここから先はもう関係ない)...233333......(この辺はもう考えなくていい).....
そのため、以下が答えになります。
の場合、答えは1
- そうでない場合、答えは「1でない数字のうち最初にあったもの」
ACコード：Submission #3031122 - AtCoder Beginner Contest 106
D - AtCoder Express 2
地味に手こずってしまいましたが…
列車数 , クエリ数
と非常に多いのに対して、駅の数は
と小さいです。
- 列車についての情報は
くらいで前計算したい
- クエリは
くらいで処理したい
については
くらい掛けても良さそう
と予測を立てます。
クエリ処理の時に欲しいのは、任意の に対する「左端
以上、右端
以下の列車の本数」です。それを求めるために、まず全ての列車を集計して「 左端
、右端
の列車の本数」の2次元テーブルを作ります。
そこから、以下のような手順で累積和を取り、「左端 以上、 右端
の列車の本数」→「左端
以上、右端
以下 の列車の本数」と求めていくことができます。
これが前計算できていれば、各クエリに対しては値を見るだけで即答できるので、全体計算量 で解けます。
ACコード：Submission #3034435 - AtCoder Beginner Contest 106
さいごに
ちょっと時間かかりすぎですね…
来週は久々のARCがあるかも…？ とのことです。ratedが1ヶ月空きましたが、その間の精進の成果が出せるよう頑張りましょう！
