じゅっぴーダイアリー

雑談・競プロ参加記・ライブラリ残し Twitter: @juppyjappy

ABC143 -E Travel by Car, F Distinct Numbers- Python 競技プログラミング Atcoder

こんにちは。蜜柑食べ過ぎると皮膚が蜜柑色になるよって言われて、ビビりながら毎日みかん食べてるじゅっぴーです。

f:id:jupy:20191021095601p:plain
パフォーマンスを蜜柑色にしてくれ

 
Atcoder Begginer Contest 143 -E Travel by Car, F Distinct Numbers-のPythonのコードです。

E問題

  • 問題概要

E - Travel by Car
f:id:jupy:20191021095204p:plain
 

  • 考えたこと

N <= 300でO(N^3)が通るので、3次元のdpを組みたい気持ちになります。
f:id:jupy:20191021094341j:plain
燃料残量を持つために、補給回数*10^10+最大燃料残量 を持つ等考えますが、厳しいお気持ちになります。
 
ところで、上の方法がワーシャルフロイド法に近いことが分かります。
そうすると、各々の点間の距離を求めておいてまたゴリゴリすればいいのかな?となるので、以下のことが思いつきます。
 


 
なお入力が多いのとO(N^3)のワーシャルフロイド法を二回回すので、入力を高速化しとかないと結構厳しいです。
 
ACコード(Pypy:1002ms)

F問題

  • 問題概要

F - Distinct Numbers
f:id:jupy:20191021092212p:plain
 

  • 考えること

同じ数字をまとめて個数だけで考えます。
 
各 K に対して x グループが作れるかどうかの判定が高速にできれば二分探索でいけるのですが、
これは
 各々の個数から x 個以下を取った時の最大値が kx 以上になればよい
ということが分かります。
 
アルメリアさんのこの記事が本当にわかりやすいです。)
AtCoder Beginner Contest 143 F - Distinct Numbers - ARMERIA

f:id:jupy:20191021092111j:plain
こういう構築、あんまりできた経験がない
 
各々から i 個以下を取った時の最大値はO(NlogN)で前計算しておけるので、O(NlogN)で解けます。

import bisect
n = int(input())
a = list(map(int,input().split()))
a.sort()

#b:個数
b = []
cnt = 1
for i in range(1,n):
    if a[i] == a[i-1]:
        cnt += 1
    else:
        b.append(cnt)
        cnt = 1
b.append(cnt)
b.sort()

#p[i]:各々からi個以下取った時の最大個数
p = [0]*(n+1)
for i in range(1,n+1):
    kp = bisect.bisect_left(b,i)
    p[i] = p[i-1]+len(b)-kp


for k in range(1,n+1):
    ok = 0
    ng = n+1
    while abs(ng-ok) > 1:
        mid = (ok+ng)//2
        if p[mid] >= k*mid:
            ok = mid
        else:
            ng = mid
    print(ok)