ABC131 メモ

A - Security

入力された数値を4文字の文字列として受け取り、1文字目と2文字目が等しい、または2文字目と3文字目が等しい,または3文字目と4文字目が等しい、のいずれかであれば「入力しづらい」数字となる。

131A.py

S = input()

if S[0] == S[1] or S[1] == S[2] or S[2] == S[3]:
    ans = 'Bad'

else:
    ans = 'Good'

print(ans)

B - Bite Eating

作る予定だったアップルパイの「味」を、リンゴの「味」を足し上げながら求める。同時に、リンゴの「味」の絶対値が最も小さいものを探す。なぜなら、リンゴの「味」の絶対値が最も小さいものはアップルパイの「味」への影響が最も小さいから。

計算量は$O(N)$。

131B.py

N, L = map(int, input().split())

pie = 0
apple = 0
m = float('inf')

for i in range(N):
    pie += L+i
    if m > abs(L+i):
        m = abs(L+i)
        apple = L+i

ans = pie-apple
print(ans)

C - Anti-Division

前回の121Dと似ている問題。その時と似た感じで、AからBの間の個数は、1からBの間の個数から、1からA-1の間の個数を引いてあげれば求まると考えた。そこで1からNまでの整数のうち、C,D共に割り切れないものの個数を求められれば良いと分かった。

逆に、CまたはDで割り切れるものの個数は、Cで割り切れるものの個数と、Dで割り切れるものの個数を足して、CでもDでも割り切れるもの（＝CとDの最小公倍数で割り切れるもの）の個数を引いてあげれば求まるので、これをNから引けば良い。高校数学のベン図をイメージしながら解いた。

計算量は$O(1)$。

131C.py

import math

def count(N, C, D):
    LCM =(C*D)//math.gcd(C, D)
    return N - N//C - N//D +N//LCM

A, B, C, D = map(int, input().split())

ans = count(B, C, D)-count(A-1, C, D)
print(ans)

D - Megalomania

初見で解けなかった。要解き直し。
最初は締め切りに間に合わせるために取り掛かる必要のある時間で並び替えた。締め切りの時間順で解けることに気づくのがよくわからない。

131D.py

N = int(input())

lst = []
for i in range(N):
    A, B = map(int, input().split())
    lst.append([B, A])

lst.sort()

time = 0
ans = 'Yes'
for i in range(N):
    time += lst[i][1]

    if time > lst[i][0]:
        ans = 'No'
        break

print(ans)

E - Friendships

初見で解けなかった。要解き直し。
どうすれば制御しやすい形のグラフを作れるか（？）みたいな考え方はよくわからなかった。

131E.py

N, K = map(int, input().split())

if K > ((N-1)*(N-2))//2:
    print(-1)

else:
    edges = []
    for i in range(2, N+1):
        edges.append([1, i])

    cnt = ((N-1)*(N-2))//2-K

    for i in range(2, N):
        if cnt == 0:
            break
        for j in range(i+1, N+1):
            if cnt == 0:
                break
            edges.append([i, j])
            cnt -= 1

    M = len(edges)
    print(M)
    for i in range(M):
        print(*edges[i])

F - Must Be Rectangular!

初見で解けなかった。要解き直し。
2部グラフの作り方がよくわからなかった。Yを十分大きな数字に置き換えてXと一緒のグラフとして扱った。
座標をグラフに置き換えて考える問題は初めて見た。

131F.py

from collections import deque
N = int(input())

edges = [[] for i in range(2*(10**5)+1)]

for i in range(N):
    x, y = map(int, input().split())
    y += 10**5
    edges[x].append(y)
    edges[y].append(x)

flag = [0]*(2*(10**5)+1)
ans = 0

for i in range(1, 2*(10**5)+1):
    if flag[i] == 0:
        xcnt = 0
        ycnt = 0
        edgecnt = 0

        d = deque()
        d.append(i)
        flag[i] = 1

        while d:
            now = d.popleft()
            if now <= 10**5:
                xcnt += 1
            else:
                ycnt += 1

            for i in edges[now]:
                edgecnt += 1
                if flag[i] == 1:
                    continue

                d.append(i)
                flag[i] = 1

        if xcnt > 1 and ycnt > 1:
            ans += xcnt*ycnt-edgecnt//2

print(ans)