競技プログラミング

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は単調増加です。
    そして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
2
0<=A<=119
B<=118

です。

最後にBの下限について考えます。A=0の場合、すなわち-(B^5)についてBを1ずつ小さくして探索すると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日