ABC166

はじめに

この記事では、AtCoder Beginer Contest 166のA~F問題を解説します。

A - A?C

https://atcoder.jp/contests/abc166/tasks/abc166_a

if文が簡単です。

1
2
3
4
5
S = input()
if S=='ABC':
print('ARC')
else:
print('ABC')

B - Trick or Treat

https://atcoder.jp/contests/abc166/tasks/abc166_b

setを使って、お菓子を持っているすぬけ君のユニーク数を数えます。

1
2
3
4
5
6
7
ls = []
N, K = map(int,input().split())
for k in range(K):
_ = input()
A = list(map(int,input().split()))
ls+=A
print (N-len(set(ls)))

C - Peaks

https://atcoder.jp/contests/abc166/tasks/abc166_c

M件の道情報それぞれに対して、良くない展望台が確定していきます。計算量はO(M)です。

隣接する展望台の高さが同じ場合も、良い展望台とはならないことに注意しましょう。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
N, M = map(int,input().split())
ok = [1] * N
H = list(map(int,input().split()))
for m in range(M):
a, b = map(int,input().split())
a-=1
b-=1
if H[a] < H[b]:
ok[a] = 0
elif H[a] > H[b]:
ok[b] = 0
else:
ok[a] = ok[b] = 0
print (sum(ok))

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は単調増加です。
    そしてn1ずつ増やして探索すると、n^5-(n-1)^510**9を超えるのはn=120の時です。すなわちAは119まで評価すればよく0<=A<=119となります。

  • A=n, B<A-1の場合について考えます。
    -B^5は単調減少であるため、BがA>Bの制約の元でどのような値をとっても、n^5-(n-1)^5A=12010**9を超えるはずなので、やはりAは119まで評価すれば十分です。

ここまでで

1
2
0<=A<=119
B<=118

です。

最後にBの下限について考えます。A=0の場合、すなわち-(B^5)についてB1ずつ小さくして探索するとB=-64で初めて10**9を超えます。先ほどと同様の議論で、Bの下限を-63としても問題ないことがわかります。

1
2
0<=A<=119
-63<=B<=118

この範囲であれば、全探索をしても全く問題がありません。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
INF = 10**10
MOD = 10**9 + 7
X = int(input())
MAX_X = 10**9
a_max = 0
while(1):
a_max+=1
if a_max**5 - (a_max-1)**5 > MAX_X:
break
b_min = 0
while(1):
b_min-=1
if -(b_min)**5 > MAX_X:
break
#print (a_max, b_min)
for i in range(a_max):
for j in range(b_min+1,a_max-1):
if i**5 - j**5 == X:
print (i,j)
exit()

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
N = int(input())
A = list(map(int,input().split()))

minus = []
plus = []
for i in range(len(A)):
minus.append(A[i]-(i+1))
plus.append(A[i]+(i+1))

d = {}
for m in minus:
d[m] = d.get(m,0) + 1 # 初期を0としてカウントアップ

ans = 0
for p in plus:
ans += d.get(-p,0) # 足して0になる(符号を反転させて等しい)ものをカウント
print (ans)

F - Three Variables Game

https://atcoder.jp/contests/abc166/tasks/abc166_f

解説pdfではA+B+Cの値に着目している。

クエリsiの文字列をL,Rとしてカウンタd[L]に着目しても解くことが出来る。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
S = []
history = []
N, A, B ,C = map(int,input().split())
d = {}
d['A'] = A
d['B'] = B
d['C'] = C

for n in range(N):
s = input()
S.append(s)

def select(L,R,x): # xを選択した場合の処理
diff = 1
if x==R:
diff = -1
d[L] += diff
d[R] -= diff
history.append(x)

for n in range(N):
L, R = S[n]
if d[L] >= 2: # 2以上なら無条件で引いて良い
select(L,R,R)
elif d[L] == 0: # 0なら無条件で足すしかない。それができないならNo
if d[R] == 0:
print ('No')
exit()
else:
select(L,R,L)
elif d[L] == 1:
if d[R] >= 2: # 2以上なら無条件で引いて良い
select(L,R,L)
elif d[R] == 0: # 0なら無条件で足すしかない
select(L,R,R)
elif d[R] == 1:
if n!=N-1: # 最後のクエリでない場合
if L in S[n+1]: # 次のクエリに出現する方に足しておく
select(L,R,L)
else:
select(L,R,R)
else: # 最後のクエリなら
select(L,R,L) # どちらでもOK
print ('Yes')
for h in history:
print (h)

関連記事

過去のABC解説記事です。

  • ABC165
    • A-F問題を解いています。
  • ABC164
    • A-E問題を解いています。
  • ABC163
    • A-D問題を解いています。
  • ABC162
    • A-E問題を解いています。

記事情報

  • 投稿日:2020年5月4日
  • 最終更新日:2020年5月4日