ABC057 D問題を解いた。

AtCoder Beginner ContestのD問題を解いた。
問題はこれ
D - Maximum Average Sets
解説はこれ
https://atcoder.jp/img/abc057/editorial.pdf
今回は問題自体の話ではなく、Counterのfor文の挙動がバージョンによってかなり違うということ。
次のコードを実行してみる。

from collections import Counter
V = list( map( int, input().split()))
CV = Counter(V)
for x in CV:
    print(x)

入力はこれ。

2 1 1 3 5 4 4 4 

AtCoderで使われているpython3.4.3だと

1
2
3
4
5

ってなる。
python3.6.0以降だと、

2
1
3
5
4

ってなる。

つまり、pytho3.6.0より前だと、数字の小さい順に出てきて、python3.6.0以降だと、listに出ていた順ででてくる。
次のWandboxに同じコードで実験できるようにしている。
[Wandbox]三へ( へ՞ਊ ՞)へ ハッハッ

AtCoderで通らなかったコードは次。正しいはず。

from math import factorial
from collections import Counter
def combination(a,b):
    if a < b:
        a, b = b, a
    comb = 1
    for i in range(b):
        comb *= a-i
    comb //= factorial(b)
    return comb

N, A, B = map( int, input().split())
V = list( map( int, input().split()))
V.sort( reverse = True)
print( sum(V[:A])/A)
CV = Counter(V)
ans = 0
K = CV[ max(V)]
if A <= K:
    for i in range(A, min(K, B)+1):
        ans += combination(K, i)
else:
    cnt = A
    for x in CV:
        if cnt <= CV[x]:
            ans += combination(CV[x],cnt)
            break
        else:
            cnt -= CV[x]
print(ans)

AtCoderで通るようにしたもの。Counterを使いたかった。

from math import factorial
from collections import Counter
def combination(a,b):
    if a < b:
        a, b = b, a
    comb = 1
    for i in range(b):
        comb *= a-i
    comb //= factorial(b)
    return comb

N, A, B = map( int, input().split())
V = list( map( int, input().split()))
V.sort(reverse = True)
print( sum(V[:A])/A)
S = list( set(V))
S.sort(reverse = True)
CV = Counter(V)
ans = 0
K = CV[S[0]]
if A <= K:
    for i in range(A, min(K, B)+1):
        ans += combination(K, i)
else:
    cnt = A
    for x in S:
        if cnt <= CV[x]:
            ans += combination(CV[x],cnt)
            break
        else:
            cnt -= CV[x]
print(ans)