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)