Xenous の精進記録

AtCoder関連他、学習したことの記録です。

バーチャル参加 ABC127

  • 4完0ペナ 25分でした

A - Ferris Wheel

問題文に記載がある通りに実装します。

A, B = map(int, input().split())
if 6 <= A <= 12: print(B//2)
elif A <= 5: print(0)
else: print(B)

B - Algae

 x_{2000} が与えられているので、そこから定義通り順に計算することができます。

r, D, x = map(int, input().split())
for _ in range(10):
    x = r*x - D
    print(x)

C - Prison

色々な区間が与えられる中で、全ての区間に含まれる点の数を答える問題です。 与えられた区間の左側の最大値と、右側の最小値を管理します。この2つの間にある番号のカードは全てのゲートを通過できます。

N, M = map(int, input().split())
Lmax = 1; Rmin = N
for _ in range(M):
    L, R = map(int, input().split())
    Lmax = max(L, Lmax)
    Rmin = min(R, Rmin)
ans = max(0, Rmin - Lmax + 1)
print(ans)

D - Integer Cards

与えられたカードを順番関係なく書き換えることができる権利がいくつか与えられ、書き換えた後の和が最大になるようにしたときの和の値を答える問題です。

元々のカードに書いてある数字とその個数、書き換えられるカードの数字とその回数を全てまとめてしまい、大きい方から  N 枚になるまでとってしまえば、状況は同じになります。

提出コード

from collections import Counter

def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    A.sort()
    counterA = Counter(A)
    for _ in range(M):
        B, C = map(int, input().split())
        if C in counterA: counterA[C] += B
        else: counterA[C] = B
    counterAitems = list(counterA.items())
    counterAitems.sort(key=lambda x: x[0], reverse=True)
    idx = 0; ans = 0
    for c, b in counterAitems:
        if N-idx < b: 
            ans += c*(N-idx)
            break
        else: 
            ans += c*b
            idx += b
    print(ans)


if __name__ == "__main__":
    main()

E - Cell Distance

式変形ができず、、後日解きます。

F - Absolute Minima

三分探索での解法を思いつきましたが、関数の更新がうまく実装できず(というより再帰で組んで間に合う気がせず)結局何もできませんでした。これも後日ときます。

ABC211 参加記録

  • 4完0ペナ 33分でした

A - Blood Pressure

式が与えられているのでその通りに実装しました。誤差は生じても小さいので気にしなくて良いです。

A, B = map(int, input().split())
print((A-B)/3+B)

B - Cycle Hit

やり方はいくつかあると思いますが、問題文中の「ただし、全ての  S_iH , 2B , 3B , HR のいずれかと一致します。」というところから、種類数を見れば確定できることがわかったので、そちらで実装しました。

l = set([])
for _ in range(4):
    s = input()
    l.add(s)
if len(l) == 4: print('Yes')
else: print('No')

C - chokudai

なんか似たような問題を直近やったような。ちゃんと復習してますか?と問われたような気持ちになりました。 DP が苦手でバグらせつつ、14分くらいでAC。ここ早解きできる人はアドバンテージだと思います。

DP 配列 1行目を初期化しているなら 0 行目いらなくない...?とか色々ありますがこれで出しました。。計算量は  O(|S|) です。

MOD = pow(10,9)+7
def MODINV(n:int, MOD=MOD):
    return pow(n, MOD-2, MOD)


def main():
    S = '*' + input()
    T = '#chokudai'
    DP = [[0] * len(S) for _ in range(len(T))]

    for j in range(1, len(S)):
        DP[1][j] = DP[1][j-1] + (S[j] == T[1])
        DP[1][j] %= MOD

    for i in range(2, len(T)):
        for j in range(1, len(S)):
            DP[i][j] = DP[i-1][j-1]*(S[j] == T[i]) + DP[i][j-1]
            DP[i][j] %= MOD
    print(DP[len(T)-1][len(S)-1])


if __name__ == "__main__":
    main()

D - Number of Shortest paths

最短経路かと思いきや、場合の数を求める問題でした。どの道路も同じ長さなので、幅優先探索でできそうです。 最短で探索しつつ、その頂点に入ってくる最短経路の場合の数を足し合わせて管理していきます。

例えば下の図では、各都市で、都市1 からの最短距離を青字の数字、その都市に最短で到達するまでの場合の数をそれぞれ記載しています。 最短距離は幅優先探索の容量で良いです。場合の数の方は、今見ている都市を fr、 隣接している都市を v とおくと、都市1からの最短距離 d について d[v]-1 == d[fr] が成り立つときに、v で記録している場合の数を fr に加算していきます。

f:id:Xenous:20210724230128p:plain
距離と場合の数の管理の例

計算量は  O(N+M) くらいだと思います。

提出コード

from collections import deque
import sys

MOD = pow(10,9)+7
def MODINV(n:int, MOD=MOD):
    return pow(n, MOD-2, MOD)

input = sys.stdin.readline

def main():
    N, M = map(int, input().split())
    graph = [[] for _ in range(N)]
    for _ in range(M):
        A, B = map(int, input().split())
        graph[A-1].append(B-1)
        graph[B-1].append(A-1)
    
    fr = 0
    que = deque([fr])
    goneset = set([fr])
    pattern = [0] * N; pattern[0] = 1
    count = [0] * N
    while que:
        fr = que.popleft()
        for v in graph[fr]:
            pattern[fr] += pattern[v] * (count[fr]-1 == count[v])
            pattern[fr] %= MOD
        for to in graph[fr]:
            if to in goneset:
                continue
            count[to] = count[fr] + 1
            que.append(to)
            goneset.add(to)
    print(pattern[N-1])


if __name__ == "__main__":
    main()

E - Red Polyomino

何も思い浮かびませんでした。  N \leq 8 と小さいのですが、数え上げる方法が全くわかりませんでした。

F - Rectilinear Polygons

E問題よりもこちらの方が解きやすそうでした。 コンテスト中に考えた内容を記載しておきます。

多角形というワードから少し敬遠していましたが、サンプルであったように角張った領域でどのくらい重なっているかをクエリの数答える問題です。

パッと思い浮かぶのがいもす法です。領域が小さければ可能ですが、x軸、y軸それぞれが  10^{5} の大きさなので無理です。 そこで、片方の軸だけで管理できないか考えます。

f:id:Xenous:20210724234346p:plain
加算のイメージ

x 軸の小さい方から順に、区間加算 +1 と -1 ができて、あるタイミングのクエリに答えるために、一点取得ができれば良さそうです。 よって LazySegmentTree や BIT を使えばできそうです。

実装の時間がなかったのが惜しいですが、これで間に合うかと思います。 実装は後日やってみます。

ABC210 参加記録

  • 3完0ペナ 10分でした

A - Cabbages

 A 個までは  X 円、それ以降は  Y 円です。  N > A のときは  AX + (N-A)Y 円とかけます。そうでない時は単純に  AX 円です。

N, A, X, Y = map(int, input().split())
if N <= A:
    print(X*N)
else:
    print(X*A + Y*(N-A))

B - Bouzu Mekuri

実際に順に手札を取っていくシミュレーションをして確かめます。後で考えてみると、初めて 1 が出てくる場所がわかればいいので、入力をリストで受け取って S.index('1') でも求められそうです。

N = int(input())
S = input()
k = 0
for s in S:
    if s == '0':
        k += 1
    else:
        break
if k%2 == 0: print('Takahashi')
else: print('Aoki')

C - Colorful Candies

先にベースとなる  K 個のカウンターを持っておき、そこからウィンドウを動かすように、先頭を追加、末尾を削除、を繰り返してその都度種類数を確認します。

from collections import Counter

N, K = map(int, input().split())
C = list(map(int, input().split()))
CounterC = Counter(C[:K])
ans = len(CounterC.keys()); tmp = ans
for i in range(N-K):
    if CounterC[C[K+i]] == 0: tmp += 1
    CounterC[C[K+i]] += 1
    CounterC[C[i]] -= 1
    if CounterC[C[i]] == 0: tmp -= 1
    ans = max(ans, tmp)
print(ans)

D - National Railway

探索の仕方が難しいです。後日解きます。

E - Ring MST

こちらはある程度考察しましたが、WA が取れず。後日解きます。

ABC209 参加記録

  • 4完1ペナ 22分でした

A - Counting

 A \leq B のとき、答えは  B-A+1 個です。問題文の制約を見ると  A > B の場合も普通にあるのでそのときだけ気をつけます。(ここで 1ペナもらいました。勿体無い。。)

A, B = map(int, input().split())
if A <= B: print(B-A+1)
else: print(0)

B - Can you buy them all?

 N \leq 100 なので、純粋に一個一個代金を足し合わせて、最後に所持金  X と比較すれば間に合います。

N, X = map(int, input().split())
A = list(map(int, input().split()))
res = 0
for i in range(N): res += (i%2 == 0) * A[i] + (i%2 == 1) * (A[i] - 1)
if res <= X: print('Yes')
else: print('No') 

C - Not Equal

そのままやろうとすると調べ上げるのに時間がかかってしまいます。

まず、この問題の条件を調べ上げるにあたって、 C の順番は特に関係ないことがわかります。 次に、一度使った数字が使えないことから、 C_i が大きいときよりも、小さいときの方が使える候補が少なく、強い制約であることがわかります。

数え上げでは、強い制約から考えていくとうまくいく場合があります。今回の問題は C を小さい順に並べてから使って良い数字をカウントしていくと、場合分けなどせずに数え上げることができます。

MOD = pow(10,9)+7

N = int(input())
C = list(map(int, input().split()))
C.sort()

cnt = 0
ans = 1
for c in C:
    ans *= c - cnt
    if c - cnt == 0:
        print(0)
        return
    ans %= MOD
    cnt += 1
print(ans)

D - Collision

道路の長さが同じということから、街どうしを結ぶ最短経路の道路の本数が偶数なら街で出会い、奇数なら道路で出会います。 与えられるグラフは木になっているので、適当な頂点から BFS などで距離を求めて、高橋くん、青木くんの出発点の値の偶奇が一致しているかどうかで判定することができます。

提出コード

from collections import deque
import sys

input = sys.stdin.readline

def main():
    N, Q = map(int, input().split())
    graph = [[] for _ in range(N)]
    for _ in range(N-1):
        a, b = map(int, input().split())
        a -= 1; b -= 1
        graph[a].append(b)
        graph[b].append(a)
    
    # BFS
    fr = 0
    que = deque([fr])
    goneset = set([fr])
    count = [0] * N
    while True:
        fr = que.popleft()
        for to in graph[fr]:
            if to in goneset:
                continue
            count[to] = count[fr] + 1
            que.append(to)
            goneset.add(to)
        if len(que) == 0:
            break
    
    for _ in range(Q):
        c, d = map(int, input().split())
        c -= 1; d -= 1
        if count[c]%2 == count[d]%2: print('Town')
        else: print('Road')


if __name__ == "__main__":
    main()

E - Shiritori

本番では、先頭3文字と末尾3文字を有向グラフで表し、巡回部分を DRAW で固定した後、そうでないところに対して DFS を行い末尾から、「この頂点から始まった場合の勝ち負け」を判定をしていくことをしました。しかし WATLE どちらもとれず、、後々考えると巡回部分の DRAW や勝ち負けを記入する際のルールが一部間違っており、考察不足でした。。

まず、この問題では、しりとりで使う単語の先頭3文字と後ろ3文字で有向グラフを使うと見通しが良くなります。例えば、有向グラフにおいて、行き先がなければ次の単語が言えず「負け」です。逆に、「負け」に矢印が出ている頂点は「勝ち」です。単語の中から「負け」になる末尾3文字の単語を言えば勝ちになります。(下図の例で、ghi の始まりの単語がないので負け。def 始まりで、defghi を言えば、相手を負けにできるので勝ち。)

f:id:Xenous:20210718152323p:plain
グラフ化の例

有向グラフをプログラム上で扱うときは、3文字の英字と頂点番号を対応させておくと良いです。今回は出てきた3文字順に0から順番に数字を振っていくようにしました。

3文字の英字と頂点番号を対応づけさせるコード例

strings = dict() # 3文字の単語と頂点番号を対応させる辞書
for _ in range(N):
    s = input()[:-1]
    bfs = s[:3]; afs = s[len(s)-3:]
    if bfs not in strings:
        strings[bfs] = cnt
        cnt += 1
    if afs not in strings:
        strings[afs] = cnt
        cnt += 1

さて、ゲームの問題では、後ろから勝ち負けを判定していくのがセオリーです。先程の例のように、「負け」の頂点へ有向辺が出ていれば「勝ち」というようなルールを整理します。頂点の次数を「その頂点から出ている有向辺の数」とし、勝ち負けが確定した頂点への有向辺を削除する(次数を減らす)操作をしていくと、以下のように考えることができます。

  • 次数が 0 である頂点は「負け」
  • 「負け」に移動できる頂点は「勝ち」
  • 「負け」に移動できない頂点で、次数が 0 となった頂点は「負け」。

最後の条件について考えます。次数が 0 でないときは、「負け」には移動できないが、「勝ち」以外の頂点へ移動できることになります。これが引き分け状態となります。次数が 0 のときは、行き先が全て確定していて、それが「勝ち」であるパターンしか残りません。したがって「負け」で確定します。

以上より、各頂点の状態の更新が止まったら、「勝ち」「負け」、そして勝ちでも負けでもない「引き分け」と割り振れば良いです。

実装では、次数が 0 の方から探索するので逆向きのグラフにしています。

提出コード

from collections import deque
import sys

sys.setrecursionlimit(10**7)
input = sys.stdin.readline

def main():
    N = int(input())
    slist = []; strings = dict(); cnt = 0
    # 次数 d_out: 出ていく辺の本数で定義
    for _ in range(N):
        s = input()[:-1]
        bfs = s[:3]; afs = s[len(s)-3:]
        if bfs not in strings:
            strings[bfs] = cnt
            cnt += 1
        if afs not in strings:
            strings[afs] = cnt
            cnt += 1
        slist.append(s)
    
    graph_reverse = [[] for _ in range(cnt)]
    d_out = [0] * cnt
    for s in slist:
        bfs = s[:3]; afs = s[len(s)-3:]
        graph_reverse[strings[afs]].append(strings[bfs])
        d_out[strings[bfs]] += 1
    
    ans = ['*'] * cnt
    que = deque([])
    for i, x in enumerate(d_out):
        if x == 0:
            que.append(i)
            ans[i] = 'L'

    n = 0
    while que:
        # 次数が 0 のところからスタート
        # 操作
        #   行き先の状態が確定していたらスキップ
        #   次数を減らす
        #   Lose から伸びている辺は Win を書く
        #   Lose から伸びておらず、次数が 0 なら Lose を書く
        fr = que.popleft()
        for to in graph_reverse[fr]:
            if ans[to] != '*': continue
            d_out[to] -= 1
            if ans[fr] == 'L':
                ans[to] = 'W'
                que.append(to)
            elif d_out[to] == 0:
                ans[to] = 'L'
                que.append(to)

    # Win Lose 判定
    for s in slist:
        bfs = s[:3]; afs = s[len(s)-3:]
        res = ans[strings[afs]]
        if res == 'L': print('Takahashi')
        elif res == 'W': print('Aoki')
        else: print('Draw')


if __name__ == "__main__":
    main()

ABC208 参加記録

  • 3完0ペナ 25分でした

A - Rolling Dice

最も小さい数 1 で合計した場合と、最も大きい数 6 で合計した場合を考えれば良さそうです。その間の数は 1 から 6 を自由に使えるのでいくらでも作れます。

よって、 1\times A \leq B \leq 6\times A が成り立てば Yes、そうでないなら No です。

A, B = map(int, input().split())
if 1*A <= B <= 6*A: print('Yes')
else: print('No')

B - Factorial Yen Coin

この問題の貨幣の単位である  x ! 円は、 x! + (x+1)! > (x+2)! が成り立つことはないので、大きい方から単純に払っておけば良いです。これが成り立つ場合は DP で遷移を考える必要があります( (x+2)! 円よりも  x! + (x+1)! 円で払った方が結果的に枚数が少なくなる場合が出てくる)。

ゆえに、大きい方から商を答えに加算し、余りを次の  P 使って計算してけば、最小枚数を計算できます。 最大枚数が 100 枚しかないので、その処理も追加しておけば問題ないと思います。

P = int(input())
S = [1]
for n in range(2, 11):
    S.append(S[-1] * n)

S.reverse()
ans = 0
while P > 0:
    for s in S:
        tmp = P//s
        if tmp > 100: 
            ans += 100
            P -= 100*s
        else:
            ans += tmp
            P = P%s
print(ans)

C - Fair Candy Distribution

まずは  K \geq N であれば、全員に同じ個数のお菓子を配れるので配ってしまいます。 余りは、番号の小さい順に足していきます。python でやる際はソートする列の位置を次のように指定できます。例えば2列目をキーにしてソートする場合は list.sort(key=lambda x: x[1]) とかけます。

 A のインデックスと番号を持つリストに直して、番号でソートした後にお菓子を配り、出力時にはインデックスでソートして元の並び順に戻します。

N, K = map(int, input().split())
A = [(i, a) for i, a in enumerate(map(int, input().split()))]
A.sort(key=lambda x: x[1])
tmp = K//N
K %= N
ans = []
for i, _ in A:
    if K > 0:
        ans.append((i, tmp+1))
        K -= 1
    else:
        ans.append((i, tmp))
ans.sort(key=lambda x: x[0])
for _, x in ans:
    print(x)

D - Shortest Path Queries 2

本番ではダイクストラで実装しました。ダイクストラだと計算量が  O(N^{2}(N+M)\log{N}) となりますが、今回の制約だと  O(N^{3}) 6.4 \times 10^{7} くらいになり、この時点で厳しいです。特に  (N+M) の部分を失念しており、最悪は  M の制約が  M \leq N(N-1)/2 であることから、 O(N^{4}\log{N}) となります。

ちなみにダイクストラでの方針は、まずはスタートの頂点を固定(ここで  O(N))して、次に  k の値を動かすようにしました。 k が増えていくごとに移動可能な頂点からの道を追加し、移動可能になった頂点をキューに入れてそこからダイクストラする、という風にしました。しかし辺が多いパターンでは計算量からして間に合わず、やはり TLE になります。

実際は、ワーシャルフロイド法を使って  O(N^{3}) でできます。

私の中でワーシャルフロイド法は、書く手順だけ覚えて中身を理解できていないもの代表になっていました。 まずはコードですが、要素がコストである隣接行列 g を使って以下のように書けます。

for k in range(N):
    for i in range(N):
        for j in range(N):
            g[i][j] = min(g[i][k] + g[k][j], g[i][j])

さて、この問題の状況で考えてみます。まずは、 k = 0 の場合です。スタートの頂点とゴールの頂点のみで到達できるかどうかを見ます。その際は g[i][j] を見れば良いです。

次に、 k = 1 の場合を考えます。頂点  1 を通る場合と通らない場合では、以下のように書けます。

  •  k = 1 で固定して、g[i][k] + g[k][j]g[i][j] を比較する。比較した値を隣接行列に反映する。

次に、 k = 2 の場合を考えます。同じく頂点  1 2 を通る場合と通らない場合を考えますが、上記で  1 を通った場合と通らない場合を調べた結果が反映されているので、頂点  2 についても同様に

  •  k = 2 で固定して、g[i][k] + g[k][j]g[i][j] を比較する。比較した値を隣接行列に反映する。

となります。これを続けていくと、結果ワーシャルフロイドの実装方法と同じになります。

初期化する際、辿り着かない値を大きな値にするのですが、float('inf') を使った場合なんと TLE になりました。 int 型と float 型を混ぜると幾分か低速になるようです。

提出コード

import sys

input = sys.stdin.readline

def main():
    N, M = map(int, input().split())
    graph = [[10**12]*N for _ in range(N)]
    for _ in range(M):
        A, B, C = map(int, input().split())
        A -= 1; B -= 1
        graph[A][B] = C
    
    for i in range(N):
        graph[i][i] = 0
    
    ans = 0
    for k in range(N):
        for i in range(N):
            for j in range(N):
                tmp = min(graph[i][j], graph[i][k] + graph[k][j])
                if tmp < 10**12: ans += tmp
                graph[i][j] = tmp
    print(ans)


if __name__ == "__main__":
    main()

E - Digit Products

これは桁DP だな、、と思いましたが EDPC の桁DP がまだ理解できていなかったので諦めました。EDPC 履修後にやります。

F - Cumulative Sum

やれたらやります。

ABC207 参加記録

  • 3完0ペナ 22分でした
  • また3完だ... と思ったら DEFが最高に難しい回だったので仕方がない感じでした。

A - Repression

探索させても良いですし、ソートして大きいもの2つを取る、でも良いと思います。下記の実装は後者です。

X = list(map(int, input().split()))
X.sort()
ans = X[-1] + X[-2]
print(ans)

B - Hydrate

式に落とすと以下になります。

  •  A + kB \leq kC \times D を満たす最小の0以上の整数  k を見つける。

式変形すると  A \leq k(C\times D -B) になります。  A は制約上  10^{5} までしかとらないため、 k の最大も  A 程度になります。

したがって この式を直接  k でループさせて調べることができて、越えればその  k の値ですし、超えないなら -1 です。

A, B, C, D = map(int, input().split())
for i in range(10**7):
    if A + i*B <= D*i*C:
        print(i)
        return
print(-1)

C - Many Segments

区間を左から順に舐めとっていこうとすると混乱します。今回の問題は単純に全ての区間から2つを選ぶ全探索が  O(N^{2}) で回るので、こちらの方針で実装します。

区間の重なりについては以下のように判定します。

区間  i区間  j を取ります。それぞれを比較したとき、左端  l の値が小さい方を  i と改めておきます。 そうしたとき、区間  i の右端  r_i区間  j の左端  l_j で以下のような場合があります。

f:id:Xenous:20210626230401p:plain
区間の場合分けイメージ

区間の持ち方でパターン (i)、(ii)、(iii) に分かれ、右端と左端の関係を図のように確認し、満たすのであれば重なりがあるとしてカウントします。 以上で各区間の重なりを見ることができました。

N = int(input())
sector = []
for _ in range(N):
    t, l, r = map(int, input().split())
    sector.append((t, l, r))

ans = 0
for i in range(N):
    for j in range(i+1, N):
        ti, li, ri = sector[i]
        tj, lj, rj = sector[j]
        if li > lj:
            ti, tj = tj ,ti
            li, lj = lj, li
            ri, rj = rj, ri
        
        if ti == 2 or ti == 4:
            if lj < ri: ans += 1
        elif (ti == 1 or ti == 3) and (tj == 1 or tj == 2):
            if lj <= ri: ans += 1
        else:
            if lj < ri: ans += 1
print(ans)

D - Congruence Points

本番では重心で考える方法を思いつきはしましたが、小数の扱いになるとミスしやすいのでその方法は諦め、原点に戻す点( S T を一致させるための基準点)を全探索する方針にしました。しかし、公式解説にもありますが、重心は各点を  N 倍しておけば整数のまま扱えます。

また、整数点を回転させて整数点になるのは 90 度回転だけでは?ということを本番中否定できなかったのも反省です。これは 例えば以下のようなパターンで否定できます。三平方の定理で斜めの線分の長さが整数になるパターンです。

f:id:Xenous:20210628202134p:plain
90度回転以外の場合

ということで、角度は確定でなく探索する必要があります。しかし実数なので全探索はできません。

全体の方針としては、以下の流れで回転を調べます。

  1.  S T の重心をそれぞれ求める(各入力の点を  N 倍しておき、重心を整数で扱えるようにする)
  2.  S T の重心をそれぞれ原点へ移動させる。
  3.  S から 1 点、 T から 1 点選び、それらを重ねるように、  S の点に対する原点を中心とした回転角を求める。
  4. 求めた回転角で実際に  S を回転させて、 T と一致するか確かめる。
  5. どこかで一致したら Yes 。全部調べて一致しなかったら No とする

以下、この方針に沿って実装したコードを見ていきます。

1  S T の重心をそれぞれ求める(各入力の点を  N 倍しておき、重心を整数で扱えるようにする)

書いてあるとおり、入力時点で  N 倍します。その座標を使って重心を求めれば必ず整数になります。(なので小数点切り捨てでの割り算をしています)

N = int(input())
S = []; T = []
Sgx, Sgy = 0, 0
for _ in range(N):
    a, b = map(int, input().split())
    S.append((a*N, b*N))
    Sgx += a*N; Sgy += b*N
Sg = (Sgx//N, Sgy//N)

Tgx, Tgy = 0, 0
for _ in range(N):
    c, d = map(int, input().split())
    T.append((c*N, d*N))
    Tgx += c*N; Tgy += d*N
Tg = (Tgx//N, Tgy//N)

2  S T の重心をそれぞれ原点へ移動させる。

平行移動させるだけなので、それぞれの重心の座標を  S  T の集合から引いていくだけで良いです。

# 重心で重ねる
nS = []; Sgx, Sgy = Sg
for x, y in S:
    nS.append((x-Sgx, y-Sgy))

nT = set([]); Tgx, Tgy = Tg
for x, y in T:
    nT.add((x-Tgx, y-Tgy))

3  S から 1 点、 T から 1 点選び、それらを重ねるように、  S の点に対する原点を中心とした回転角を求める。

原点に移動させた  S の点と  T の点でループさせて、回転角を求めます。 回転角は  S の点の角度と、 T の点の角度をそれぞれ出して差を求めています。

# 一致させる点を探索する
for a, b in nS:
    for c, d in nT:
        # 回転角を求める
        stheta = theta(a, b, positive=True)
        ttheta = theta(c, d, positive=True)
        psi = ttheta - stheta
# x 軸からの回転角を求める関数
def theta(x:float, y:float, positive = False) -> float:
    if x == 0 and y == 0: return 0
    value = sqrt(x**2 / (x**2 + y**2)) * (1*(x >= 0) - 1*(x < 0))
    sign = 1 * (y >= 0) - 1 * (y < 0)
    res = acos(value) * sign
    if positive:
        res += 2*pi*(sign < 0)
    return res

求めた回転角で実際に  S を回転させて、 T と一致するか確かめる。

上の for 文の中で書きます。 回転行列の式を使って各点を原点を中心とした回転をさせます。このとき誤差が生じますが、整数点との差分がとても小さいなら、格子点上にあるとみなします。

# 点を丸める
err = 0.0000001

nnS = []
for x, y in nS:
    x, y = route(x, y, psi)
    rx, ry = round(x), round(y)
    if abs(x-rx) <= err and abs(y-ry) <= err:
        nnS.append((rx, ry))

# 整数点であることを確かめる
if len(nnS) != len(nT): continue

# 一致するか確かめる
if check(nnS, nT):
    print('Yes')
    return
# T に一致するか確かめるための関数
def check(s:list, t:set) -> bool:
    for x,y in s:
        if (x, y) not in t:
            return False
    return True

# 原点中心の回転を行う関数
def route(x:int, y:int, theta:float) -> tuple:
    return (x*cos(theta) - y*sin(theta), x*sin(theta) + y*cos(theta))

どこかで一致したら Yes 。全部調べて一致しなかったら No とする

回し切って、Yes にならなかったら No です。

以上です。計算量は  O(N^{3}) です。偏角ソートなどを使えば  O(N^{2}\log{N}) くらいになります。

提出コード

import sys
from math import cos, sin, sqrt, acos, pi

input = sys.stdin.readline
err = 0.0000001

def check(s:list, t:set) -> bool:
    for x,y in s:
        if (x, y) not in t:
            return False
    return True


def route(x:int, y:int, theta:float) -> tuple:
    return (x*cos(theta) - y*sin(theta), x*sin(theta) + y*cos(theta))


def theta(x:float, y:float, positive = False) -> float:
    """
    点(x, y) と x 軸との角度 theta を求める.

        Peremeters:
        -----------
        x, y: float
            点(x, y) の座標.
        positive: bool
            返却値を 0 <= theta < 2*pi の範囲にする
        
        Returns:
        --------
        theta: float
            点(x, y)とx軸との角度 theta
            positive が False であれば -pi/2 < theta <= pi/2 の範囲で返す
            positive が True であれば 0 <= theta < 2*pi の範囲で返す
            点(0, 0) の場合は 0 を返す
    """
    if x == 0 and y == 0: return 0
    value = sqrt(x**2 / (x**2 + y**2)) * (1*(x >= 0) - 1*(x < 0))
    sign = 1 * (y >= 0) - 1 * (y < 0)
    res = acos(value) * sign
    if positive:
        res += 2*pi*(sign < 0)
    return res


def main():
    N = int(input())
    S = []; T = []
    Sgx, Sgy = 0, 0
    for _ in range(N):
        a, b = map(int, input().split())
        S.append((a*N, b*N))
        Sgx += a*N; Sgy += b*N
    Sg = (Sgx//N, Sgy//N)

    Tgx, Tgy = 0, 0
    for _ in range(N):
        c, d = map(int, input().split())
        T.append((c*N, d*N))
        Tgx += c*N; Tgy += d*N
    Tg = (Tgx//N, Tgy//N)

    # 重心で重ねる
    nS = []; Sgx, Sgy = Sg
    for x, y in S:
        nS.append((x-Sgx, y-Sgy))

    nT = set([]); Tgx, Tgy = Tg
    for x, y in T:
        nT.add((x-Tgx, y-Tgy))

    # 一致させる点を探索する
    for a, b in nS:
        for c, d in nT:
            # 回転角を求める
            stheta = theta(a, b, positive=True)
            ttheta = theta(c, d, positive=True)
            psi = ttheta - stheta

            # 点を丸める
            nnS = []
            for x, y in nS:
                x, y = route(x, y, psi)
                rx, ry = round(x), round(y)
                if abs(x-rx) <= err and abs(y-ry) <= err:
                    nnS.append((rx, ry))
            
            # 整数点であることを確かめる
            if len(nnS) != len(nT): continue

            # 一致するか確かめる
            if check(nnS, nT):
                print('Yes')
                return
    print('No')    

if __name__ == "__main__":
    main()

E - Mod i

後ほど書きます。

F - Tree Patrolling

後ほど書きます。

バーチャル参加 ABC126

  • 全完1ペナ 65分でした

A - Changing a Character

小文字に置き換えるのは python であれば s を文字列型として s.lower() でできます。 該当箇所のみ lower を使って、それ以外はそのまま表示させるようにします。

N, K = map(int, input().split())
S = input()
print(S[:K-1] + S[K-1].lower() + S[K:])

B - YYMM or MMYY

MM として表示できるのは  1 \leq \mathrm{MM} \leq 12 になります。この範囲内であれば、MM と言えます。そうでない場合は YY です。 MMMM となる場合は AMBIGUOUS となります。片方 MM のパターンはそのままで、それ以外は全て NA です。

S = input()
bf = S[:2]; af = S[2:]
if 1 <= int(bf) <= 12: bf_flag = True
else: bf_flag = False

if 1 <= int(af) <= 12: af_flag = True
else: af_flag = False

if bf_flag and af_flag: print('AMBIGUOUS')
elif bf_flag and not af_flag: print('MMYY')
elif not bf_flag and af_flag: print('YYMM')
else: print('NA')

C - Dice and Coin

1回目の出た目の数によって、何回あと表出し続けないといけないかが変わるのでそれごとに計算します。

1回目は  1 から  N まで等確率で目が出るので、確率は  \frac{1}N 。1回目に出た値を  a とおくと、そのあとの確率は、表を連続して出す確率なので、  \left(\frac12\right)^{j} k a \times 2^{j} \geq K を満たす最小の整数)と表せます。

これを  1 から  N までのパターン全て計算して足し合わせれば良いです。

N, K = map(int, input().split())
p0 = 1/N; ans = 0.0
for score in range(1, N+1):
    cnt = 0
    while score < K:
        score *= 2
        cnt += 1
    ans += p0 / (2 ** cnt)
print(ans)

D - Even Relation

同じ色に塗られた任意の  2 頂点について、その距離が偶数である。

色が先で、その後距離を見ると、頂点どうしの距離が偶数である、という確認の順番です。

思いつきで、根を黒で借り決めして、距離が偶数であるときは親と同じ色、距離が奇数であるときは親と異なる色、とすると、塗り分けが可能で、問題文の状態を満たすことができます。

提出コード

from collections import deque

N = int(input())
graph = [[] for _ in range(N)]
for _ in range(N-1):
    u, v, w = map(int, input().split())
    u -= 1; v -= 1
    graph[u].append((v, w))
    graph[v].append((u, w))

fr = 0
que = deque([fr])
goneset = set([fr])
ans = [-1] * N; ans[fr] = 0
while True:
    fr = que.popleft()
    for to, w in graph[fr]:
        if to in goneset:
            continue
        if w%2 == 0: ans[to] = ans[fr]
        else: ans[to] = (ans[fr]+1)%2
        que.append(to)
        goneset.add(to)
    if len(que) == 0:
        break
print(*ans, sep='\n')

E - 1 or 2

 A_{X_i} + A_{Y_i} + Z_i が偶数」の情報だけだと  A_{X_i} A_{Y_i} の偶奇を確定できません。このうち片方が分かれば両方を特定できます。この場合はコスト1を使う必要があります。

また、上で明らかになった  A_{k} の情報が、他の  A_{X_j} + A_{Y_j} + Z_j で使えれば、コストを払う必要がありません。

したがって、コスト 1 払ったときに連鎖的にわかる範囲が管理できていればよく、UnionFind を使って実装できます。

提出コード

class UnionFind():
    """
    unionfind を扱うクラス (0-index)

        Parameters:
        -----------
        n: int
            管理するデータの要素数
    """
    def __init__(self, n:int):
        """
        Parameters:
        -----------
        n: int
            要素数
        parents: list
            各要素が属する親の要素番号
        grouping: set
            親番号の集合
        rank: list
            親の rank を保持するためのリスト
        size: list
            親の size を保持するためのリスト
        """
        self.n = n
        self.parents = [-1]*n
        self.grouping = set(range(n))
        self.rank = [0]*n
        self.size = [1]*n


    def find(self, x:int) -> int:
        """
        要素 x の親の要素を見つけるメソッド

        Parameters:
        -----------
        x: int
            要素番号
        
        Returns:
        --------
        int
            x の親の要素番号
        """
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    

    def union(self, x:int, y:int) -> None:
        """
        要素 x, y の属するグループを結合するメソッド
        
        Parameters:
        -----------
        x, y: int
            結合対象の要素番号
        """
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.rank[x] < self.rank[y]:
            # rank(x)の方が小さい場合は, xをくっつけて, y を親にする
            self.size[y] += self.size[x]
            self.parents[x] = y
            self.grouping.difference_update(set([x]))
        else:
            # そうでないときは, y をくっつけて, x を親にする
            self.size[x] += self.size[y]
            self.parents[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.grouping.difference_update(set([y]))


    def msize(self, x:int) -> int:
        """
        要素 x の属するグループの大きさを返すメソッド

        Parameters:
        -----------
        x: int
            要素番号
        
        Returns:
        --------
        int
            x の属するグループの大きさ(要素数)
        """
        return self.size[self.find(x)]


def main():
    N, M = map(int, input().split())
    uf = UnionFind(N)
    for _ in range(M):
        X, Y, _ = map(int, input().split())
        X -= 1; Y -= 1
        uf.union(X, Y)
    ans = len(uf.grouping)
    print(ans)


if __name__ == "__main__":
    main()

F - XOR Matching

XOR の bit 演算は、以下のようになります。

XOR 1 0
1 0 1
0 1 0

演算は、以下のように数字の各 bit どうしを比較して上記演算の結果を返します。

# ^ は XOR
5^13 #8
10進数 2進数
5: 0101
13: 1101
8: 1000

また、結合法則、交換則が成り立ちます。( \oplus

  •  (a \oplus b) \oplus c = a \oplus (b \oplus c)
  •  a \oplus b = b \oplus a

そして、0 は以下を満たします。

  •  a \oplus 0 = a
  •  a \oplus a = 0

さて、問題文の状況から、 0 以上  2^{M} 未満の整数が2つずつ使える中で数列を作り、同じ値で囲まれる間の数列の XOR を行うと  K になるようにします。

まず、XOR は bit 演算なので、演算した後に bit の最大の桁数が増えることはありません。したがって、 K \geq 2^{M} の場合は XOR して  K を作ることができません。

そうでない場合は、数列のなかに  K を入れることができます。 a \oplus a = 0 が成り立つので、以下のように  K を同じ数字で囲むと、問題文の条件を満たせます。

0 2 3 4 K 4 3 2 0

 Kうしの場合どうするかですが、次の性質を使うと簡単です。

  •  1 から  2^{M}-1 以下の整数を全てXORすると、0 になる

よって、ここから一つ  K という数字を外すと、XOR は  K になります。

ゆえに、数列を作る際は、 Kうしの間は  K 以外の  1 から  2^{M}-1 以下の整数を並べれば良いです。

例えば  M = 3 K = 5 の場合は、以下のようにすれば良いです。

0 1 2 3 4 6 7 5 7 6 4 3 2 1 0 5

これで大体答えですが、特殊なケースについて考えておきます。

 K = 0 の場合は、隣どうし数字を並べたりすることで満たせます。

また、 M=1 K=1 の場合は、このときは 0 と 1 しか使える数字がなく、どう並び替えても条件を満たす数列を作れません。この時は -1 を出します。

以上で、 O(2^{M}) で条件を満たす数列が作れました。

提出コード

from collections import deque

M, K = map(int, input().split())
if 2**M-1 < K:
    print(-1)
    return

if K == 0:
    ans = deque([])
    for i in range(2**M):
        ans.appendleft(i)
        ans.append(i)
    print(*ans)
    return

if M == 1:
    print(-1)
    return

ans = deque([K])
for p in range(0, 2**M):
    if p != K:
        ans.appendleft(p)
        ans.append(p)
ans.append(K)
    
print(*ans)