arc7をpythonで

まぁ題名の通り、先日不参加したARC7をちょこっとPythonでといてみた。
それで、Cは考えなきゃいけなそうだったのでとりあえずA,BをACしてあとはなんとなく数学ガールみてquicksortをpythonで実装してみたり、union-findをpythonで実装してみたりしてた

A

入力をWA解で見て学んで実装

#!/usr/bin/env python
# coding:utf-8

import sys

x = str(sys.stdin.readline().strip())
s = str(sys.stdin.readline().strip())

res = []
for word in s:
    if word != x:
        res.append(word)

ans = ''.join(res)

print ans

B

こちらも入力を頑張るだけ

#!/usr/bin/env python
# coding: utf-8

(n, m) = map(int, (raw_input().split(' ')))
cases = range(1, n+1)

d = 0
for i in range(m):
    nd = int(raw_input())
    cnt = 0
    for j in cases:
        if j == nd:
            cases[cnt] = d
            d = nd
        cnt += 1

for i in cases:
    print i

quicksort

擬似コードとpythonの互換性が良いことに気づいた

#!/usr/bin/env python
# coding: utf-8

def qsort(a, l, r):
    if l < r:
        p = l
        k = l + 1
        while k <= r:
            if a[k] < a[l]:
                tmp = a[p+1]
                a[p+1] = a[k]
                a[k] = tmp
                p += 1
            k += 1
        tmp = a[l]
        a[l] = a[p]
        a[p] = tmp
        a = qsort(a, l, p-1)
        a = qsort(a, p+1, r)
    return a

in1 = raw_input().split(' ')

in1 = qsort(in1, 0, len(in1)-1)

for i in in1:
    print i,
print

union-find

クラス初めてまともに書いた。
テストのためにアリ本に載ってるunion-findするだけ問題実装してみた(構造体的なものをつくるのに調べるのが面倒だったので最小全域木はやめておいた)

#!/usr/bin/env python
# coding: utf-8

class unionfind:
    rank = []
    par = []
    def __init__(self, n):
        self.n = n
        for i in range(n):
            self.rank.append(0)
            self.par.append(i)
    
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    def same(self, x, y):
        return self.find(x) == self.find(y)

(n, k) = map(int, (raw_input().split(' ')))
T = raw_input().split(' ')
X = raw_input().split(' ')
Y = raw_input().split(' ')

uf = unionfind(n * 3)

ans = 0
for i in range(k):
    t = int(T[i])
    x = int(X[i]) - 1
    y = int(Y[i]) - 1
    if x < 0 or n <= x or y < 0 or n <= y:
        ans += 1
        continue
    if t == 1:
        if uf.same(x, y+n) or uf.same(x, y+2*n):
            ans += 1
        else:
            uf.unite(x, y)
            uf.unite(x+n, y+n)
            uf.unite(x+2*n, y+2*n)
    else:
        if uf.same(x, y) or uf.same(x, y+2*n):
            ans += 1
        else:
            uf.unite(x, y+n)
            uf.unite(x+n, y+2*n)
            uf.unite(x+2*n, y)

print ans