ABC276の振り返り(A, B, C, D)
振り返りです。
AtCoder Beginner Contest 276 - AtCoder
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
A - Rightmost
略
自由欄
B - Adjacency List
略
自由欄
C - Previous Permutation
やってみよう！
C関数を完成させて「Run」ボタンをクリックしよう！
自由欄
解説を見る
解説のようなことがしたかったのです、はい…
何の言い訳のしようもなく、力不足でした😣
そして解説のコードがめちゃくちゃスッキリしてるのでまるっとパクります。
from io import StringIO def C(N, P): out = StringIO() for i in range(N - 2, -1, -1): if P[i] > P[i + 1]: break for j in range(N - 1, i, -1): if P[i] > P[j]: break P[i], P[j] = P[j], P[i] print(*P[:i + 1] + P[i + 1:][::-1], end="", file=out) return out.getvalue() test_all(C)結果：#36567286
自由欄
NEXT OR PREVIOUS PERM
という訳で、上のコードを参考に隣(前 or 次)の順列を求める関数(ジェネレーター)を作ってみました。
from operator import lt, gt def next_perm(a, rev=False): a = a.copy() op = gt if rev else lt n = len(a) while True: for i in range(n - 2, -1, -1): if op(a[i], a[i + 1]): break else: return None for j in range(n - 1, i, -1): if op(a[i], a[j]): break a[i], a[j] = a[j], a[i] a = a[:i + 1] + a[i + 1:][::-1] yield a.copy() from itertools import permutations # 昇順 a = list(range(5)) list(list(p) for p in permutations(a))[1:] == list(next_perm(a)) # 降順 a = list(range(5)) list(list(p) for p in permutations(a))[::-1][1:] == list(next_perm(a[::-1], rev=True))next_permを使った提出
結果：#36584782
重複する要素がある場合
これは意図した訳ではないのですが、上の実装では重複する要素がある場合でもしっかりと辞書順でユニークな数列を返してくれます。
a = [1, 2, 3, 3] p1 = sorted([ list(p) for p in set(list(permutations(a)))]) p2 = [a] + list(next_perm(a)) p1 == p2 for a, b in zip(p1, p2): print(a, b)解説を見る2
もう一つの解説では、
- 当該順列が辞書順で何番目かを求める
- 任意の要素から辞書順でN番目の順列を求める
という2つの関数を作成しています。
コードを追うだけではよく分からなかったので以下も参照。
- 階乗進法 - Wikipedia
- 辞書順で N 番目の順列を求める \| iilj memo
- 順列を一瞬で取得するプログラム - 目標は商店街をつくる事なんです。
- 辞書式に並べたとき何番目問題 ｜ 数学の偏差値を上げて合格を目指す
考え方としては中高の数学で扱うんですね…記憶にない😇
一つ工夫したのは、id_of_permutationで「着目する数字より小さい数がいくつあるか」を算出するのにABC264で紹介したBITを使った点です。
これによって計算量が$O(n^2)$から$O(n \log n)$に縮減されました(はず…)。
加えて、数字が連番でない場合や文字列にも対応しています。
class BIT: def __init__(self, a): if hasattr(a, "__iter__"): self.size = len(a) self.data = [0] * self.size self.bit = [0] * (self.size + 1) for i, j in enumerate(a): self.add(i, j) elif isinstance(a, int): self.size = a self.data = [0] * a self.bit = [0] * (a + 1) else: raise TypeError() def add(self, i, x): self.data[i] += x i += 1 while i <= self.size: self.bit[i] +="x" i & -i def sum(self, i): '''get sum of data[:i] ''' total="0" while> 0: total += self.bit[i] i -= i & -i return total def __getitem__(self, key): return self.data[key] def __setitem__(self, key, value): self.add(key, value - self[key]) self.data[key] = value def __len__(self): return self.size def __repr__(self): return self.data.__repr__() def __iter__(self): return self.data.__iter__() class Perm_n(): def __init__(self, items): self.n = len(items) # 階乗(0!, 1!, 2!, ..., n!)を保持 self.fa = [1] # itemが辞書順で何番目(0-index)かを保持 self.order = {} for i, item in enumerate(sorted(items), 1): self.fa.append(self.fa[-1] * i) self.order[item] = i - 1 def nth_perm(self, x): S = list(self.order.keys()) ans = [] for i in range(self.n): d, m = divmod(x, self.fa[self.n - 1 - i]) ans.append(S[d]) S = S[:d] + S[d+1:] x = m return ans def id_of_perm(self, perm): # i番目以降にi番目より小さい要素がいくつあるか bit = BIT(self.n) smaller = [None] * self.n for i in range(self.n - 1, -1, -1): o = self.order[perm[i]] bit[o] = 1 smaller[i] = bit.sum(o) ans = 0 for i in range(self.n): ans += self.fa[self.n - 1 - i] * smaller[i] return ans def C(N, P): out = StringIO() perm = Perm_n(P) print(*perm.nth_perm(perm.id_of_perm(P) - 1), end="", file=out) return out.getvalue() test_all(C)結果：#36584862
自由欄
D - Divide by 2 or 3
やってみよう！
D関数を完成させて「Run」ボタンをクリックしよう！
自由欄
try(振り返り)
せっかくなのでD問題もやってみます。
と言っても今回はもう力尽きたので早速解説を見ます。
最大公約数ですか… なるほどね！😇
from math import gcd def D(N, a): gcd_a = a[0] for ai in a[1:]: gcd_a = gcd(gcd_a, ai) cnt = 0 for ai in a: ai //= gcd_a while ai % 3 == 0: ai //= 3 cnt += 1 while ai % 2 == 0: ai //= 2 cnt += 1 if ai != 1: return -1 return cnt test_all(D)結果：#36598050
自由欄