ABC191 振り返り

はじめに

誤読祭りに誤差祭り...大変な回だったので戒めとして記事にすることにしました。

A - Vanishing Pitch
B - Remove It
C - Digital Graffiti
D - Circle Lattice Points
E - Come Back Quickly
F - GCD or MIN

A - Vanishing Pitch

Difficulty : 25(AC)

いつもの A より問題文が複雑な気がする。
$V \times T$ から $V \times S$ の間は球が消えているので、判定する。

v,t,s,d = map(int,input().split())
if v*t <= d <= v*s:
    print('No')
else:
    print('Yes')

B - Remove It

Difficulty : 20(AC)

A より DIff 低いってどういうこと。
前から順番に見ていって、$X$ と違うならリストに加えていく。

n,x = map(int,input().split())
a = list(map(int,input().split()))
ans = []
for i in range(n):
    if a[i] != x:
        ans.append(a[i])
print(*ans)

C - Digital Graffiti

DIfficulty : 1063(-)

これは何角形ですか？

そうです八角形ですね。

多くの人を誤読させた問題。
上の図を三角形と考えた人は多いはず(自分も考えた一人)。
解説を見て、ようやくこの問題の正しい答えが分かりました。
そのマスの各頂点(
左上$(i,j)$、右上$(i,j+1)$、左下$(i+1,j)$、右下$(i+1,j+1)$
)の黒マスの合計が奇数なら答えが +1 されるようです。

h,w = map(int,input().split())
s = [list(input()) for i in range(h)]
ans = 0
for i in range(h-1):
    for j in range(w-1):
        cnt = 0
        for n,m in ((0,0),(1,0),(0,1),(1,1)):
            ni,mj = n+i,m+j
            if s[ni][mj] == '#':
                cnt += 1
        if cnt % 2 == 1:
            ans += 1
print(ans)

D - Circle Lattice Points

DIfficulty : 1953(-)

なんでACできないんですか？
そうです誤差のせいですね。

誤差WAが多すぎて難易度爆上がりな問題。
自分は格子点の内部の求め方が分からなかったので、コンテスト中に以下の記事を見つけて参考にしました。

任意の円の内部の格子点の数を求める(@Tukaene様)

これを参考に実装しても誤差のせいでサンプル3が合わず断念しました。 が、コンテスト後に他の人のACを見たところ、Decimalを使って計算すれば正確な精度となり、ACできたようです。

from math import ceil,floor
from decimal import Decimal
x,y,r = map(Decimal,input().split())
low = ceil(x-r)
high = floor(x+r)

ans = 0
for i in range(low,high+1):
    d = Decimal(r**2-(x-i)**2).sqrt()
    top = floor(y+d)
    bottom = ceil(y-d)
    ans += top - bottom + 1
print(ans)

E - Come Back Quickly

Difficulty : 1323(AC(1))

実行制限時間が3秒、$N$ も $ M $ も 2000 と小さい。ならワーシャルフロイド使っても問題ないのでは？(TLE)

TLEしたので、それぞれの頂点からダイクストラしました。 使ったら早くなるんじゃないかな、という感覚で一応heapqを採用しています。

from heapq import heappop,heappush
n,m = map(int,input().split())
INF = 10**10
graph = [[] for i in range(n)]
for i in range(m):
    a,b,c = map(int,input().split())
    a -= 1
    b -= 1
    graph[a].append((c,b))
for i in range(n):
    cost = [INF] * n
    queue = []
    for j,k in graph[i]:
        heappush(queue,(j,k))
    while queue:
        c,k = heappop(queue)
        if cost[k] > c:
            cost[k] = c
            for x,y in graph[k]:
                heappush(queue,(c+x,y))
    ans = cost[i]
    if ans == INF:
        print(-1)
    else:
        print(ans)

F - GCD or MIN

Difficulty : 2333(-)

普通に難しすぎるやんけ。

コンテスト中の考察
操作して残る数字候補を考える。サンプル3を見て思ったのが、「与えられた数字で、一番小さい整数(以下 min とする)以下の整数しか残らないのでは？」ということ。

$gcd(A,B)$ を考えると、$min(A,B)$ が最大公約数になることはあっても、それを超える整数が最大公約数になることはない。min 以下で、何か法則があって選ばれるのでは？

min の約数かと考えたが、サンプル3で残る数字が 3 とか 6 とか 7 とかで全部が 27 の約数というわけではない。でも、min 以外の整数には約数としてありえる。ならこの約数と何かを使えば答えが求まるのでは？

$N$ が 2000 なので、$gcd(A_i,A_j)(1 \le i,j \le 2000)(i \neq j)$ で各最大公約数を求め、最大公約数、約数で出た整数が答えの候補かと考えたがWA、時間切れ

コンテスト後解説を見て
どうやら答えが min 以下になることと、約数を使うのは間違ってなかったようです。

連想配列 $t$ を用意します。 $A_i$ の約数を求め、約数を $j_1...$ とします。連想配列に $t_j$ がないなら $t_j = A_i$ とし、あるなら $t_j = gcd(t_j,A_i)$ で更新します。最終的に $t_j = j$ なら残る整数としてあり得ます。

この操作は、その約数同士が含まれる整数同士を $gcd$ して、その整数を作ることができるか調べています。サンプル2では、全ての整数に共通する約数は $(1,2)$ ですが、全て $gcd$ しても 1 になることはないので残せません。サンプル 3 では、$gcd(30,49)$ で 1 になるので、この二つを $gcd$ し、後の操作を全て $min$ にすることで 1 が残るように操作できます。これで作れる整数が分かりました。

考察に書いてある通り、最終的な答えは全て min より小さいので、min 以下の整数の個数を数える必要があります。$2,5$ のような配列が与えられた場合、連想配列では 5 が残る整数候補になります。しかし、2 との操作をする必要があり、残すことはできません。約数を求める時点で min を超える約数を除外するか、作れる整数を求めた後に min 以下の整数のみを数えるなどで、正しい答えが出ます。

from math import floor,sqrt,gcd
n = int(input())
a = list(map(int,input().split()))
b = [[] for i in range(n)]
m = min(a)
for i in range(n):
    x = a[i]
    for k in range(1,floor(sqrt(x))+1):
        if x % k == 0:
            b[i].append(k)
            if x // k != k:
                b[i].append(x//k)
t = {}
for i in range(n):
    for j in b[i]:
        if not j in t:
            t[j] = a[i]
        else:
            t[j] = gcd(t[j],a[i])
ans = 0
for i,j in t.items():
    if i == j and i <= m:
        ans += 1
print(ans)