AtCoder Beginner Contest 106 (ABC106) の解説です。
AtCoder Beginner Contest 106 旧版
AtCoder Beginner Contest 106 beta版
解けた問題だけ解説をしていきますー
要項
AtCoder Beginner Contest 106
rated 1200
8/18(土) 21:00 ~ 22:40 (100分)
100-200-300-400 (4問)
ペナルティ: 5分
方針
全完
A - Garden
これは、道を平行移動しても変わらないことに着目すると畑の右下に道が来るように配置できることが分かります。(別に右下で無くても構いません)。
そうすると、残った畑部分はヤードあるので、これを出力すれば良いです。
B - 105
ある自然数を素因数分解すると
と表せるとき、約数の数は
と表せることを利用します。
今回の場合、約数の個数が8個ですから考えられるケースは、
、
、
しかあり得ません。
まず、に関しては
よりあり得ません。同様に
に関しても
より存在しません。
に関しては、
の2つが存在します。
に関しては、
の3つが存在します。
よって、において答えは0個、
なら1個、
なら2個、
なら3個、
なら4個、
なら5個になります。
C - To Infinity
まず、は何度操作しても
のままです。逆に、他の数は少なくとも変化を行うたびに長さが増えます。
ところで、問題文を見ると変化回数は5000兆回もあるので、左から見た時に最初に見る以外の数は非常に長い長さになっていることが容易に想像できます。
言い換えると、左から番目まで
が並んでいるならば答えは
、そうでないなら最初に出てきた
以外の数になります。
D - AtCoder Express 2
まず、今回のような各クエリについて答えを返す質問形式の問題は、各質問において答えを迅速に返す必要があります。
今回の場合、であることから1回の質問に使える計算量は
か
、
辺りになります。
また、考えられる区間]は高々
個しかないことから、予め全ての区間における答えを求めておけないかと考えます。
今、を区間
]を走る電車の本数、
を走る区間が
]に完全に含まれる電車の本数とします。
この時、は次のように表せます。
なら
なら
これは、区間の幅をとすると幅が
となる全ての区間は幅が
となる全ての区間が分かっていれば導出できるということを表しています。
ということは、幅が0となる区間から順に求めていけば、で全ての
を求めることができます。
この時、各質問についてがそのまま答えとなるので、答えが一瞬で導出できることになりました。
よって、計算量はを求めるのに
、
を求めるのに
、質問に対し答えは
となったので最終的に
で答えを導出できます。
結果
oooo 4完(1000点) 1:31-7:34(1WA)-18:36-36:08(1WA) / 46:08
186位