ARMERIA

放置していたけど更新再開、Rubyと競技プログラミングの話が中心になっていく予定です

ABC106 参加記録

今回はペナルティ込みで40分台全完。ABCオンリー回であればもっと速く解きたかったところ…

f:id:betrue12:20180818223814p:plain

A - Garden

A - Garden

道の部分をくっつけると  (A-1) \times (B-1) の長方形になります。

ACコード:Submission #3027956 - AtCoder Beginner Contest 106

B - 105

B - 105

全探索しましょう。 N の約数は  N 以下なので、  N 以下の奇数全部について、それ以下の数で全通り割って約数を数えます。問題全体で  O(N^{2}) なので十分間に合います。

「奇数」という制約を忘れないように(忘れるとサンプルが合わないので、そこで手が止まるようにはなっています)。

ACコード:Submission #3029027 - AtCoder Beginner Contest 106

C - To Infinity

C - To Infinity

操作を5000兆回繰り返した後の数列は、

  • 1はそのまま
  • 2以上の数字  a は、 a^{5000兆} 個に増殖

します。 K は大きくても  10^{18} オーダーなので、頭から見ていった結果は「先頭にあった1たち」+「1でない数字のうち最初にあったものが大量に増殖したもの」で、残りは無視できます。

11234112222222......(ここが意味不明なくらい長い)......(長すぎてここから先はもう関係ない)...233333......(この辺はもう考えなくていい).....

そのため、以下が答えになります。

  •  K \le (先頭の1の個数) の場合、答えは1
  • そうでない場合、答えは「1でない数字のうち最初にあったもの」

ACコード:Submission #3031122 - AtCoder Beginner Contest 106

D - AtCoder Express 2

D - AtCoder Express 2

地味に手こずってしまいましたが…

列車数  M \le 200000, クエリ数  Q \le 100000 と非常に多いのに対して、駅の数は  N \le 500 と小さいです。

  • 列車についての情報は  O(M) くらいで前計算したい
  • クエリは  O(Q) くらいで処理したい
  •  N については  O(N^{2}) くらい掛けても良さそう

と予測を立てます。

クエリ処理の時に欲しいのは、任意の  L, R に対する「左端  L 以上、右端  R 以下の列車の本数」です。それを求めるために、まず全ての列車を集計して「 左端  L 、右端  R の列車の本数」の2次元テーブルを作ります。

そこから、以下のような手順で累積和を取り、「左端  L 以上、 右端 R の列車の本数」→「左端  L 以上、右端  R 以下 の列車の本数」と求めていくことができます。

f:id:betrue12:20180819020229p:plain

これが前計算できていれば、各クエリに対しては値を見るだけで即答できるので、全体計算量  O(N^{2} + M + Q) で解けます。

ACコード:Submission #3034435 - AtCoder Beginner Contest 106

さいごに

ちょっと時間かかりすぎですね…

来週は久々のARCがあるかも…? とのことです。ratedが1ヶ月空きましたが、その間の精進の成果が出せるよう頑張りましょう!