ルール変更でBeginnerになりました。
Nの制約がテストケースと違う気がする。 あまり確率の問題は得意ではないが、これはそこまで難しくない。
まずサイコロで初期確率は1 / Nずつになる。 さらにそれぞれの場所から始めたとき、Kを超えるまで連続してコインで面を出し続けなければならない。
何回出し続ける必要があるか、はlog Kなので10000だと14程度なはずなのにこれが通らず、30ぐらいにしたら通った。
def solve(N, K): b = 1 / N poss = [b for _ in range(N + 1)] for n in range(30): for i in range(N + 1): if i == 0: continue if (i << n) < K <= (i << n + 1): poss[i] = b * (0.5 ** (n + 1)) return "{:1.12f}".format(sum(poss[1:])) assert (solve(3, 10) == "0.145833333333") assert (solve(1, 1) == "1.000000000000") assert (solve(1, 2) == "0.500000000000") assert (solve(2, 2) == "0.750000000000") assert (solve(2, 2) == "0.750000000000") assert (solve(1, 3) == "0.250000000000") assert (solve(1, 4) == "0.250000000000") assert (solve(10000, 10000) == "0.333431365967") assert (solve(100000, 5) == "0.999973749998") assert (solve(1, 10000) == "0.000061035156") if __name__ == "__main__": N, K = tuple(map(int, input().split(" "))) print(solve(N, K))
最近、問題文の配列が1から始まるとき、配列は0番目を余分に取るようにしてる。こっちのほうがミスが少ない気がするのと、 結局heapの配列上の実装などを考えるとき1から始まることを意識しないとダメなので。
これは例示が若干ひっかけ。 同じ色に塗られていれば偶数であるが、偶数であれば同じ色、というわけではない。
何の疑いもなく、単に幅優先探索をすればよい。 colorの決定をvisited代わりにすると実装が楽。
木だから深さ優先探索もいけるかな。
from collections import deque def solve(N, UVWs): vertexes = {} for u, v, w in UVWs: vertexes.setdefault(u, []).append((v, w % 2)) vertexes.setdefault(v, []).append((u, w % 2)) colors = [-1 for _ in range(N + 1)] colors[1] = 0 que = deque() que.append((1, colors[1])) while que: u, c = que.popleft() for v, w in vertexes[u]: if colors[v] == -1: colors[v] = (c + w) % 2 que.append((v, colors[v])) return "\n".join(str(c) for c in colors[1:]) assert (solve(3, [(1, 2, 2), (2, 3, 1)]) == "0\n0\n1") assert (solve(5, [(2, 5, 2), (2, 3, 10), (1, 3, 8), (3, 4, 2)]) == "0\n0\n0\n0\n0") if __name__ == "__main__": N = int(input()) UVWs = [tuple(map(int, input().split(" "))) for _ in range(N - 1)] print(solve(N, UVWs))
これは一瞬。
魔法を使えばある一つのカードの整数が判明する。これによってこの一つと偶数条件で対になっているカードが判明し、連鎖的に対になっているカードがすべて判明する。
つまり1回の魔法により、一つの集合がすべてわかることになるので、UnionFindを使って、集合の数を取ればよい。
珍しく、assert文を一つも書かなかった。
class UnionFind: import sys sys.setrecursionlimit(100000) def __init__(self, n): self.parents = [i for i in range(n + 1)] def root(self, i): if self.parents[i] == i: return i else: self.parents[i] = self.root(self.parents[i]) return self.parents[i] def unite(self, i, j): self.parents[self.root(self.parents[i])] = self.root(j) def is_unite(self, i, j): return self.root(i) == self.root(j) def solve(N, XYZs): uf = UnionFind(N) for x, y, z in XYZs: uf.unite(x, y) return len(set([uf.root(i) for i in range(1, N + 1)])) if __name__ == "__main__": N, M = tuple(map(int, input().split(" "))) XYZs = [tuple(map(int, input().split(" "))) for _ in range(M)] print(solve(N, XYZs))
Fはジャッジ中なのでまた今度。
