はじめに
ここのところサボってしまっていましたが、今回初の新ABC全完ということで気分がいいので久しぶりに参戦記を書きたいと思います。
A
問題文が微妙にわかりずらかったですが、要はA-2Bです。隙間の長さは負にならないことに注意すれば問題ないでしょう
A, B = map(int, input().split())
print(max(A-B*2, 0))
B
全探索すれば通りますが、O(N^2)です。和の二乗から各たこ焼きの美味しさの二乗を引いて二で割ることでも求められO(N)です。無駄な高速化はしないようにしていますが、今回は自明すぎたのでしてしまいました。
N = int(input())
d = list(map(int, input().split()))
s = sum(d)
ans = s**2
for i in range(N):
ans-=d[i]**2
print(ans//2)
C
隣り合う要素が異なるような場所の数＋１が答えです
N = int(input())
S = input()
ans = 1
now = S[0]
for i in range(1, N):
if now == S[i]:
continue
now = S[i]
ans += 1
print(ans)
D
こういういくつも要素が動く系の数え上げはいくつかを固定してあげるとうまくいくことがあります。今回、三角形に使う棒の長さをa<=b<=cとして、b, cを固定すると、a>c-bとなるaの数え上げに帰着します。単調性から、二分探索でlognで求められるので、全体ではO(N^2logN)です。pypyでN^2logNがN=2000で通るかどうか不安でしたが、約800msで通りました
from bisect import bisect_right
N = int(input())
L = list(map(int, input().split()))
L.sort()
ans = 0
for i in range(N):
for j in range(i):
m = L[i]-L[j]
k = bisect_right(L, m)
n = max(0, j-k)
ans+=n
print(ans)
実は、L<10^3を利用すると、二分探索をしなくても大丈夫です。
各0<l<10^3についてその長さの棒の数を管理すると、上の二分探索パートがO(1)の処理に置き換えられます。
E
まず、給油をすると、必ず燃料はLリットルになるので、移動方法として最善なのは、Lリットルで行けるところまで行って、ギリギリのところで給油することを繰り返すことです。そう考えると、ある頂点から距離L以内の頂点を見つけると良さそうです。
Q<=N(N-1)/2から、最悪の場合、あらゆる頂点の組み合わせについて考える必要があるので、ワーシャルフロイドが使えそうだなぁという気持ちになります。
そうして、Lリットルの燃料で到達できる頂点を見つけた後はその頂点に向けて長さ１の辺を張ったグラフを考え、その最短経路を求めれば答えが出ます。はじめ前半のパートが幅優先探索で十分と考えてしまい3WA出してしまいました...。BFSは辺の長さが全て１の時のみ、最短距離を正しく出してくれるので、逆に後半パートには使えます。
計算量はO(N**3)ですがN＜＝３００なのでpypyで間に合うか不安で、実際1700msとかなりギリギリでした。ワーシャルフロイドは単純なループなのでまあまあ早かったっぽいですね。
inf = 10**10
def warshall_floyd(d):
for i in range(N):
for a in range(N):
for b in range(N):
d[a][b] = min(d[a][b], d[a][i]+ d[i][b])#頂点iを使う場合と使わない場合
return d
N, M, L = map(int, input().split())
G = [[inf]*N for _ in range(N)]
for i in range(N):
G[i][i] = 0
for _ in range(M):
a, b, c = map(int, input().split())
G[a-1][b-1] = c
G[b-1][a-1] = c
G = warshall_floyd(G)
G2 = [[0]*N for _ in range(N)]
for i in range(N):
for j in range(N):
if i == j:
G2[i][j] = 0
elif G[i][j]<=L:
G2[i][j] = 1
else:
G2[i][j] = inf
d = warshall_floyd(G2)
Q = int(input())
for _ in range(Q):
s, t = map(int, input().split())
ans = d[s-1][t-1]-1
print(ans if ans < 10**9 else -1)
実は、ダイクストラを改造することでもできます。距離だけでなく、何回給油が必要かを持っておくことで正しい答えを得ることができます。
inf = 10**10
def dijkstra(s):
d = [(inf, 1)] * N
used = [False] * N
d[s] = (0, -L)
for i in range(N):
v = -1
for i in range(N):
if used[i]:
continue
if v==-1:
v = i
elif d[v]>d[i]:
v = i
if v == -1:
break
used[v] = True
m, r = d[v]
r = -r
for nv in range(N):
c = cost[v][nv]
if r>=c:
d[nv] = min(d[nv],(m, -(r-c)))
elif c<=L:
d[nv] = min(d[nv], (m+1, -(L-c)))
return d
N, M, L = map(int, input().split())
cost = [[inf]*N for _ in range(N)]
for _ in range(M):
a, b, c = map(int, input().split())
cost[a-1][b-1] = c
cost[b-1][a-1] = c
ans = []
for i in range(N):
ans.append(dijkstra(i))
Q = int(input())
for _ in range(Q):
a, b = map(int, input().split())
res = ans[a-1][b-1][0]
print(res if res != inf else -1)
ちなみにダイクストラには何種類かあって、O(MlogN)とO(N^2)がありますが、今回、最悪でM ~ N^2なので後者を採択しないと(少なくともpythonでは)死にます。
F
N<３＊10**5なので各k<NについてO(logN)くらいで求められれば間に合いそうです（pythonだと間に合わないけど）。取り除ける最大の回数を求めるのは難しそうですが、取り覗ける回数にはn回取り除けるならn-1回取り除けるという単調性があるので、二分探索が使えそうです。二分探索をするにはn回取り除けるかどうかが高速に判定できる必要があります。n回で取り除けるのは同じ数字からn個までなので、同じ数字からn個取った時に、その総数がn＊kより大きければ、可能、そうでなければ不可能と判定できます。同じ数字からn個取った時の総数は前計算が可能なので、判定はO(1)で行えるので全体ではO(NlogN)です。
from collections import Counter
N = int(input())
A = list(map(int, input().split()))
C = Counter(A)
C = list(C.values())
C.sort()
n = len(C)
m = max(C)
S = [0]*(m+1)
b = 0
for i in range(n):
c = C[i]
if b<c:
for j in range(b+1, c+1):
S[j] = S[j-1]+(n-i)
b = c
for i in range(1, N+1):
ok = 0
ng = N+1
while ng-ok>1:
mid = (ok+ng)//2
if S[min(m, mid)]>=mid*i:#midが条件を満たすか
ok = mid
else:
ng = mid
print(ok)
時間がなさすぎたのでかなりのクソコードになっています。
解説を読むと、もう少し賢く、今回の問題とは逆のn回取り出せる最大の長さk = f(n)を求めてから元の問題を解くということをしています。やはり今回のポイントは、取り出す回数nを固定すると楽になることでした。