塩見周子の徒然日記

自分のことを塩見周子と思い込んでいるオタクです

復習 3/26, 3/27

atcoder.jp

桁DP的な発想 解説読んでパッと理解できなかった

atcoder.jp

これも桁DP的発想

atcoder.jp

提出した後で「2,8とかの組み合わせの時無理じゃね?」とか気付く。ちゃんと考察をしましょう。

atcoder.jp

グラフの用語を知った。
・直径:一番遠い点間の距離
・二部グラフ:二つのグループに分けられるグラフ。グループAはグループBの頂点としか繋がっておらず、逆も然り。例えば三角形に頂点が並んでいるグラフは二部グラフではないが、四角形に並んでいたら二部グラフ。二部グラフの時、隣接する頂点のグループ番号を偶数、奇数、偶数、奇数……と交互にできる。




atcoder.jp

とにかく桁数がデカけりゃデカいほど強いので、それを目標にしてまずはDPで「マッチ棒ビッタリ使った時に最大何桁作れるか?」を求める。そしてそれが求まったら、dpの最後から遡ってどういう数字を各桁に割り当てればいいかを求める。賢い。

atcoder.jp

結局は高校数学。1<=i<=kのそれぞれのiに対して、(n-k+1_C_i)*(k-1_C_i-1)を求めてあげればいいだけの話。考え方は「最初に赤いボールn-k個を並べて、①その間のi個のどこにボールを入れるか、②その場所に何個のボールを入れるか、の二つをかけたもの」

逆元の求めかたを、例外処理(例えば4C6なんてのは存在しない)も入れて書き直した。

import math
mod = 10**9+7
def comb(p,q):
    if p >= q:
        a = math.factorial(p)%mod
        b = math.factorial(q)%mod
        c = math.factorial(p-q)%mod
        return ((a*pow(b*c, mod-2, mod))%mod)
    else:
        return 0

どうでもいいけどn=10**3くらいだったらpythonの方が早そう


atcoder.jp

二分探索と、「二つの配列の各要素を掛け合わせた時の最大値をできるだけ小さくするにはどう掛けあわせるのが最適?」っていう問題をちゃんと考える。
二分探索で値を見つけるコードを覚えとこう。

n,k = map(int,input().split())
A = list(map(int,input().split()))
F = list(map(int,input().split()))
A.sort()
F.sort()
F.reverse()
t = sum(A)
ok = 10**12
ng = -1
if t <= k:
    print(0)
else:
    while abs(ok-ng) > 1:
        cur = 0
        mid = (ok+ng)//2
        for i in range(n):
            temp = mid/F[i]
            if int(temp) == temp:
                cur += max(0, int(A[i]-temp))
            else:
                if A[i]-temp > 0:
                    cur += int(A[i]-temp)+1
        if cur > k:
            ng = mid
        else:
            ok = mid
    print(ok)

scrapbox.io

(こちらのサイトを参考にさせていただきました。ありがとうございました。)