AT274の技術だったりなかったり

あっとのTECH LOG

競プロのこととか技術のこととか。たまに日常を書きます。

ARC064 E - Cosmic Rays

競プロ

問題原文

atcoder.jp

解法

スタートとゴールにも半径０のバリアが張られていると考える。

こういうのはグラフにできないかなと考えるとうれしい。
バリア内は自由に動き回れるので、「バリアの中に入る」ではなく「バリアの中心にたどり着く」ためのコストを考える。
またバリアとバリアの間を移動する時、バリアのそれぞれの中心を結ぶ線分上を移動するのが明らかに最適。
これを考えるとバリア i と バリア j の間の移動コストは、 「バリア i と バリア j の距離 - それぞれのバリアの半径」となる。（最低０）

これで各頂点間の移動コスト（距離）が手に入るので、あとはダイクストラ法で最短距離を求めればOK！

実装

import sys
import heapq
my_input = sys.stdin.readline

xs, ys, xt, yt = map(int, my_input().split())
N = int(my_input())
C = [(xs, ys, 0), (xt, yt, 0)]  # 始点と終点も含めとく  
C += [tuple(map(int, my_input().split())) for i in range(N)]

G = [[] for i in range(N+2)]
for i in range(N + 2):
    for j in range(i + 1, N + 2):
        cost = max(0, ((C[i][0] - C[j][0]) ** 2 + (C[i][1] - C[j][1]) ** 2) ** 0.5 - (C[i][2] + C[j][2]))
        G[i].append((j, cost))
        G[j].append((i, cost))

dist = dijkstra(G, 0)
print(dist[1])

感想

「実はグラフにできます！」的な問題がすきです。

ABC171 F - Strivore

競プロ

問題原文

atcoder.jp

解法

解説放送があまりにも神だったので理解のためにこの記事をお読みになる場合はこちらをご覧いただいたほうが。。。
www.youtube.com

以下、振り返り & 反省 & まとめ です。

例えば、 abc とあって、各文字の間に文字を差し込んでいくことを考えました。
ただこれだと重複を取り除くことがめっちゃ大変そうでどうしたものかと思っていました。

こういう時は、「重複にならないようなルールを設定して、そのルールのもと数え上げる」のが良さそうだという知見です。
今回でいえば、「操作後の文字列において abc となる部分列を探す場合に、左から貪欲的に探して行く。見つかった a, b, c は必ず元の文字列の a, b, c である。」というようなルールとなります。

こうすると、 abc の各文字の間に文字を差し込む操作は以下のように捉えられます。

① a ② b ③ c ④

  1. ①〜④に好きに文字を差し込む
  2. ただしルールを守るために、 ①にはa を、 ②にはb を、 ③には c を差し込めない（④ は自由）

こうすると、 「 K 回の操作のうち、何回 ① ~ ③ に入れて、何回 ④ にいれるか」で分けたくなります。
ここでは、 K 回の操作のうち、 i 回 ① ~ ③ に差し込むものとします。

すると、
④ の部分は 特に制限はないので、 26^{K - i} 通り、 ① ~ ③ の部分は ３つの区別がつく箱に、 i 個の区別がつかないボールを入れるのと同じなので、 S の長さを N として {}_{i + N - 1} C_{N-1} 通り。（ i + N - 1 個の要素から N - 1 個を S の要素とするイメージ、あるいは i 個のボールと N - 1 個の仕切りを並べるイメージ。並べたしきりの左から a, b と なる。）

さらに挿入する各文字は、ルールに違反する１つを除く25文字種から好きに選べるので 25^{i}をかけたものになります。

これを各 i について計算して足し合わせれば答えが求められます。

つまり、「実は S の中身はどうでもよかった」ということですね。。。 すごい。。。

実装

逆元を用いたMOD上のcombinationをします。

K = int(input())
S = input()
N = len(S)
MOD = 10 ** 9 + 7

ans = 0
for i in range(K + 1):
    ans += pow(25, i, MOD) * nCr(i + N - 1, N - 1) * pow(26, K - i, MOD) % MOD
    ans %= MOD
print(ans % MOD)

感想

これが天才か。。。

ABC E - Red Scarf

競プロ

問題原文

atcoder.jp

解法

答えを、 b_1, b_2 ... b_{N} とする。

a_1 ⊕ a_2 ⊕ a_3 ⊕ a_4 = (b_2 ⊕ b_3 ⊕ b_4) ⊕ (b_1 ⊕ b_3 ⊕ b_4) ⊕ (b_1 ⊕ b_2 ⊕ b_4) ⊕ (b_1 ⊕ b_2 ⊕ b_3)

両辺に a_1 = (b_2 ⊕ b_3 ⊕ b_4) をかけると、 a_1 ⊕ (a_1 ⊕ a_2 ⊕ a_3 ⊕ a_4) = b_1 になる。
これは、 N が偶数なことより、右辺で各 b_i が 奇数回あらわれるため。

これは一般化できるので、 S = a_1 ⊕ a_2 ⊕ ... ⊕ a_N としておいて、 a_i ⊕ S を各 i について行えばよい。

N が奇数の場合には、 a_1 ⊕ a_2 ⊕ a_3 = (b_2 ⊕ b_3) ⊕ (b_1 ⊕ b_3) ⊕ (b_1 ⊕ b_2) となる。右辺はあきらかに０なので、 a_1 ⊕ a_2 ⊕ a_3 = 0 になってないといけない。
逆にもし０ならば、そのままで条件を満たしていることになる。

実装

reduce、なるほど。

from functools import reduce
N = int(input())
A = list(map(int, input().split()))

ALL_XOR = reduce(lambda x, y: x ^ y, A)
print(*[a ^ ALL_XOR for a in A], sep=' ')

感想

本番はわちゃわちゃした結果左右から累積xorで解いてしまった。（例の黒板gcd的な）
コンテスト終わりのTLを見てたら理解できた感じがします。ありがとうございます。

ところで茶diffとはいったい。

ABC171 D - Replacing

競プロ

問題原文

atcoder.jp

解法

愚直にやると当然間に合わない。
あらかじめ全要素の和を計算しておいて、差分更新だけするようにやれば間に合う。
差分更新は各数の個数を持っておけばできる。

実装

from collections import Counter
N = int(input())
A = list(map(int, input().split()))
C = Counter(A)

Q = int(input())
SUM = sum(A)
for q in range(Q):
    b, c = map(int, input().split())
    SUM -= C[b] * b
    SUM += C[b] * c
    C[c] += C[b]
    C[b] = 0
    print(SUM)

こういうのは Counter の十八番。
b の個数が0になるのでちょっと注意。
要素数も持つUnionFindでもできそうですね。

感想

PASTに出そう。

ARC027 C - 最高のトッピングにしような

競プロ

問題原文

atcoder.jp

解法

あるトッピングを交換する時、スペシャルチケットはなるべく温存し、普通のチケットを多く使いたくなる。
すると、最大でもスペシャルチケットの枚数分しかトッピングは手に入らないこと、それさえ守ればスペシャルチケットを普通のチケットと同じように扱えることがわかるので、「どこまで見たか」「何枚使ったか」「いくつ交換したか」で状態を同一視してdpで解ける。

計算量は O(XN(X + Y) になる。

実装

PyPyで。MLEしたのでdpテーブル使いまわし。

from copy import deepcopy
import sys
my_input = sys.stdin.readline
 
def main():
    X, Y = map(int, map(int, my_input().split()))
    N = int(input())
    items = [list(map(int, my_input().split())) for i in range(N)]
 
    # dp[i][j][k] := i番目までみてj枚チケットを使い、k個選んでいる時の嬉しさの合計の最大値
    # dp[i + 1] の計算時に dp[i] しか 使わないのでテーブル使いまわし
    dp = [[0] * (X + 1) for _ in range(X + Y + 1)]
    for i, (t, h) in enumerate(items):
        nx_dp = [[0] * (X + 1) for _ in range(X + Y + 1)]
        for j in range(X + Y + 1):
            for k in range(X + 1):
                nx_dp[j][k] = max(nx_dp[j][k], dp[j][k])
                if (k + 1 > X) or (j + t > X + Y):
                    continue
                nx_dp[j + t][k + 1] = max(nx_dp[j + t][k + 1], dp[j][k] + h)
 
        dp = nx_dp
 
    ans = 0
    for j in range(X + Y + 1):
        for k in range(X + 1):
            ans = max(ans, dp[j][k])
    print(ans)
 
 
if __name__ == "__main__":
    main()

感想

numpy使いこなしたい気持ちはあるんですよ。気持ちは。

ABC168 D - .. (Double Dots)

競プロ

問題原文

atcoder.jp

解法

部屋１から幅優先探索をすれば、各部屋まで最小の移動回数で到達できる。
逆にいうと、それを辿れば各部屋から部屋１まで最小の移動回数で到達できる。

よって、次の部屋に移るタイミングで、今いた部屋の番号を次の部屋の道しるべとして置いていけばいい。

実装

from collections import deque
N, M = map(int, input().split())
G = [[] for _ in range(N)]
for i in range(M):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    G[a].append(b)
    G[b].append(a)

que = deque([0])
guideposts = [-1] * N
guideposts[0] = None

while que:
    n = que.pop()
    for to in G[n]:
        if guideposts[to] != -1:
            continue
        guideposts[to] = n
        que.appendleft(to)

print('Yes')
print(*[guisepost + 1 for guisepost in guideposts[1:]], sep="\n")

感想

コウイウノスキー！

AGC041 B - Voting Judges

競プロ

問題原文

atcoder.jp

解法

とりあえず降順ソート。
ついでに 上位 P 番以内に入るために最低限必要なボーダーも求めておく。

x 番目が採用されるような時、 x - 1 番目も採用されるので、単調性があることがわかる。
つまり答えの境界を二分探索できる。

ここからは二分探索内部パート。
x 番目ができるだけ採用されるように頑張ることを考える。

まず、 M 人全員はとりあえず x 番目に投票すべき。これで x 番目のスコアは A_x + M になる。（これを X とする） またこの時点でボーダーを達成していなければ明らかに達成不可能。

次に、残り M × (V - 1) 票を X を超えないように割り振り切ることを考える。
まず条件として、 M 票より多く割り振ることはできない。（１つの問題に投票できるのは１人１回なので）
つまり、ある A_i に対して、 \min(M, X - A_i) 票まで割り振ることができる。
また、上位 P 番以内に入っていて ボーダーを超えているようなもの は、 A_x が採用されるのとは実質関係ないので M 票入れてしまって良い。（ボーダーピッタリのやつまで対象にするとボーダーがこわれる）

実装

N, M, V, P = map(int, input().split())
A = sorted(list(map(int, input().split())), reverse=True)
BORDER = A[P - 1]

# にぶたん: x番目の問題が採用される可能性があるか？
ok, ng = 0, N
while abs(ok - ng) > 1:
    x = (ok + ng) // 2
    x_score = A[x] + M
    remain_vote = M * (V - 1)

    if x_score < BORDER:
        ng = x
        continue

    for i, a in enumerate(A):
        if i == x:
            continue
        elif i < P and A[i] > BORDER:
            remain_vote -= M
        else:
            remain_vote -= min(M, x_score - a)

    if remain_vote <= 0:
        ok = x
    else:
        ng = x

print(ok + 1)

感想

なんか一回間違って３週間ぐらい放置してたら解けた！w