ABC008 C - コイン

AtCoder Python3

備忘録

問題

atcoder.jp

回答

import sys
import os
import math
import bisect
import itertools
import collections
import heapq
import queue
import array
import time
import numpy as np
from decimal import Decimal, ROUND_HALF_UP

# 時々使う
# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
# from collections import defaultdict, deque

# 再帰の制限設定
sys.setrecursionlimit(10000000)


def ii(): return int(sys.stdin.buffer.readline().rstrip())
def il(): return list(map(int, sys.stdin.buffer.readline().split()))
def fl(): return list(map(float, sys.stdin.buffer.readline().split()))
def iln(n): return [int(sys.stdin.buffer.readline().rstrip())
                    for _ in range(n)]


def iss(): return sys.stdin.buffer.readline().decode().rstrip()
def sl(): return list(map(str, sys.stdin.buffer.readline().decode().split()))
def isn(n): return [sys.stdin.buffer.readline().decode().rstrip()
                    for _ in range(n)]


def lcm(x, y): return (x * y) // math.gcd(x, y)


# MOD = 10 ** 9 + 7
MOD = 998244353
INF = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N = ii()
    C = [ii() for _ in range(N)]
    C.sort()

    ret = 0
    for i in range(N):
        l = 0
        for j in range(N):
            if i == j:
                continue
            if C[i] % C[j] == 0:
                l += 1
        else:
            if l == 0:
                ret += 1
            elif l % 2 == 0:
                # l + 1 通り中、左に偶数個揃うのはl // 2 + 1通り
                ret += ((l//2)+1)/(l+1)
            else:
                # odd
                ret += 0.5
    print(ret)


if __name__ == '__main__':
    main()

考え方

実際に起こり得るコインの並びを全てシミュレートする場合、100!通りを試す必要があります。
実際に、100!通りを全て試すのは不可能です。
そのため、各コインが表となる期待値を求めるO(N**2)の解法を考えます。

  • 回答概要
    • 各コインが表となる期待値を求める
    • 各コインの期待値の合算が列の中で表を向いている枚数の期待値となる

まず、素直な実装を考えます。
各コインが取りうる位置を全て試す方法で実装すると、
N枚のコインに対して、N!通りの並びが存在します。
しかし、制約では1 <= N <= 100となっているため、
100!通りを試すのは不可能です。
そのため、別の方針を考えます。

操作終了後に表を向いているコインの枚数の期待値は、
各コインが表になる期待値の合計に等しいです。
（コインの枚数の期待値 = 1枚目のコインが表になる期待値 + 2枚目のコインが表になる期待値 + ... + N枚目のコインが表になる期待値) そのため、各コインが表になる期待値を求めて、合算した値が回答となります。

各コインが表になる期待値は、
表になるコインの位置 ÷ コインが置かれる全ての位置です。
また、コインが表となるケースは、
対象のコインより左に、対象コインの約数となるコインが偶数毎存在するときです。
そのため、各コインに対して、約数となるコインの枚数から期待値を求めることが出来ます。

約数となるコインが存在しない場合、
そのコインは必ず表になります。
そのため期待値は1です。

約数となるコインが偶数毎存在している場合には、
約数となるコインがl枚のとき、
期待値は( ( l // 2 ) + 1) / ( l + 1 )となります。
（対象のコインを〇、約数となるコインを●としたとき、
[●, ●, 〇], [●, 〇, ●], [〇, ●, ●]のような並びになる）

約数となるコインが奇数毎存在している場合には、
期待値は0.5です。
（対象のコインを〇、約数となるコインを●としたとき、
[●, ●, ●, 〇], [●, ●, 〇, ●], [●, 〇, ●, ●], [〇, ●, ●, ●]のような並びになり、
2分の1で左側が偶数枚になる）

あとは全てのコインの期待値を合算することで、回答を得ることが出来ます。