情報妖精の競プロ日記

AtCoderの問題に対する方針を主に書きます

AtCoder Beginner Contest 106

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

これは、道を平行移動しても変わらないことに着目すると畑の右下に道が来るように配置できることが分かります。(別に右下で無くても構いません)。
そうすると、残った畑部分は(A-1)(B-1)ヤードあるので、これを出力すれば良いです。

B - 105

ある自然数nを素因数分解すると{p_1}^{a_1} \cdot {p_2}^{a_2} \cdots {p_m}^{a_m}と表せるとき、約数の数は(a_1+1)(a_2+1)\cdots (a_m+1)と表せることを利用します。
今回の場合、約数の個数が8個ですから考えられるケースはa_1=7、a_1=1, a_2=3、a_1=3, a_2=1、a_1=1, a_2=1, a_3=1しかあり得ません。
まず、a_1=7に関しては3^7=2187>200よりあり得ません。同様にa_1=1,a_2=3に関しても3\cdot 5^3=375>200より存在しません。
a_1=3, a_2=1に関しては、3^3 \cdot 5 = 135, 3^3 \cdot 7 = 189の2つが存在します。
a_1=1, a_2=1, a_3=1に関しては、3 \cdot 5 \cdot 7 = 105, 3 \cdot 5 \cdot 11 = 165, 3 \cdot 5 \cdot 13 = 195の3つが存在します。
よって、1 \leq N < 105において答えは0個、105 \leq N < 135なら1個、135 \leq N < 165なら2個、165 \leq N < 189なら3個、189 \leq N < 195なら4個、195 \leq N \leq 200なら5個になります。

C - To Infinity

まず、1は何度操作しても1のままです。逆に、他の数は少なくとも変化を行うたびに長さが増えます。
ところで、問題文を見ると変化回数は5000兆回もあるので、左から見た時に最初に見る1以外の数は非常に長い長さになっていることが容易に想像できます。
言い換えると、左からK番目まで1が並んでいるならば答えは1、そうでないなら最初に出てきた1以外の数になります。

D - AtCoder Express 2

まず、今回のような各クエリについて答えを返す質問形式の問題は、各質問において答えを迅速に返す必要があります。
今回の場合、Q \leq 100000であることから1回の質問に使える計算量は{\rm O}(1)か{\rm O}(N)、{\rm O}(\log M)辺りになります。
また、考えられる区間[L, R]は高々N^2個しかないことから、予め全ての区間における答えを求めておけないかと考えます。
今、f(L, R)を区間[L, R]を走る電車の本数、g(L, R)を走る区間が[L, R]に完全に含まれる電車の本数とします。
この時、g(L, R)は次のように表せます。

  • L = Rならg(L, R)=f(L, R)
  • L \neq Rならg(L, R)=f(L, R)+g(L + 1, R) + g(L, R - 1) - g(L + 1, R - 1)

これは、区間の幅をwとすると幅がwとなる全ての区間は幅がw-1となる全ての区間が分かっていれば導出できるということを表しています。
ということは、幅が0となる区間から順に求めていけば、{\rm O}(N^2)で全てのg(L, R)を求めることができます。
この時、各質問についてg(p_i, q_i)がそのまま答えとなるので、答えが一瞬で導出できることになりました。
よって、計算量はf(L, R)を求めるのに{\rm O}(M)、g(L, R)を求めるのに{\rm O}(N^2)、質問に対し答えは{\rm O}(1)となったので最終的に{\rm O}(M+N^2+Q)で答えを導出できます。

結果

oooo 4完(1000点) 1:31-7:34(1WA)-18:36-36:08(1WA) / 46:08
186位

感想

D問題以外は比較的易しい問題だったのではないでしょうか。
D問題に関しては、区間を問う問題は累積和や尺取り法などのアルゴリズムが利用できること、クエリ系の問題には事前計算が有効なこと、累積和は事前計算として頻繁に使われることなどを知っていると速く挑めたのではないかと思います。
また、制約条件から答えを予想する力も競プロでは結構試されるので、知っておいて損はないかと思います。