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