はじめに
この記事では、AtCoder Beginer Contest 166のA~F問題を解説します。
A - A?C
https://atcoder.jp/contests/abc166/tasks/abc166_a
if文が簡単です。
1 | S = input() |
B - Trick or Treat
https://atcoder.jp/contests/abc166/tasks/abc166_b
set
を使って、お菓子を持っているすぬけ君のユニーク数を数えます。
1 | ls = [] |
C - Peaks
https://atcoder.jp/contests/abc166/tasks/abc166_c
M
件の道情報それぞれに対して、良くない展望台が確定していきます。計算量はO(M)
です。
隣接する展望台の高さが同じ場合も、良い展望台とはならないことに注意しましょう。
1 | N, M = map(int,input().split()) |
D - I hate Factorization
https://atcoder.jp/contests/abc166/tasks/abc166_d
Aの符号とBの符号を(Aの符号, Bの符号)
のように表現します。
X
は正のため、(-,+)
のパターンを考慮する必要はない(-,-)
のパターンについては、A, Bの絶対値
を入れ替えて符号を(+,+)
とすることで等価なパターンが存在する。
これらの考察からA
を非負として扱っても一般性を失いません。
またA<=B
の時、A^5-B^5<=0
となり制約を満たさなくなるので、A>B
とします。
ここから解説pdfのように考えます。
A=n, B=A-1
すなわちn^5-(n-1)^5
について考えます。
先の議論からA
が非負として、n^5-(n-1)^5
は単調増加です。
そしてn
を1
ずつ増やして探索すると、n^5-(n-1)^5
が10**9
を超えるのはn=120
の時です。すなわちAは119
まで評価すればよく0<=A<=119
となります。A=n, B<A-1
の場合について考えます。-B^5
は単調減少であるため、BがA>B
の制約の元でどのような値をとっても、n^5-(n-1)^5
はA=120
で10**9
を超えるはずなので、やはりAは119
まで評価すれば十分です。
ここまでで
1 | 0<=A<=119 |
です。
最後にB
の下限について考えます。A=0
の場合、すなわち-(B^5)
についてB
を1
ずつ小さくして探索するとB=-64
で初めて10**9
を超えます。先ほどと同様の議論で、Bの下限を-63
としても問題ないことがわかります。
1 | 0<=A<=119 |
この範囲であれば、全探索をしても全く問題がありません。
1 | import sys |
E - This Message Will Self-Destruct in 5s
https://atcoder.jp/contests/abc166/tasks/abc166_e
身長+番号(A[i]+(i+1)
)と 身長-番号(A[i]-(i+1)
)を事前に計算しておき、引いて0
になる組み合わせを数え上げれば良いです。
前者のパターンを辞書として作成し、後者のパターンのクエリをループすれば良いです。
ここで、
- ペアの組み合わせではなく、順列を考えている
- 自身と比較しても、身長が正であることから条件を満たし得ない
- 番号の差の絶対値ではなく、番号の差を考えている。
自身以外との番号は必ず異なる上、番号は非負なので、順列(p,q)
の番号の差p-q
と順列(q,p)
の番号の差q-p
は必ず異なる。そのため、各ペアに対して重複してカウントする心配はない。
1 | N = int(input()) |
F - Three Variables Game
https://atcoder.jp/contests/abc166/tasks/abc166_f
解説pdfではA+B+C
の値に着目している。
クエリsi
の文字列をL
,R
としてカウンタd[L]
に着目しても解くことが出来る。
1 | S = [] |
関連記事
過去のABC解説記事です。
記事情報
- 投稿日:2020年5月4日
- 最終更新日:2020年5月4日