バーチャル参加 ABC127 - Xenous の精進記録

4完0ペナ 25分でした

A - Ferris Wheel

問題文に記載がある通りに実装します。

A, B = map(int, input().split())
if 6 <= A <= 12: print(B//2)
elif A <= 5: print(0)
else: print(B)

B - Algae

$x_{2000}$ が与えられているので、そこから定義通り順に計算することができます。

r, D, x = map(int, input().split())
for _ in range(10):
    x = r*x - D
    print(x)

C - Prison

色々な区間が与えられる中で、全ての区間に含まれる点の数を答える問題です。与えられた区間の左側の最大値と、右側の最小値を管理します。この2つの間にある番号のカードは全てのゲートを通過できます。

N, M = map(int, input().split())
Lmax = 1; Rmin = N
for _ in range(M):
    L, R = map(int, input().split())
    Lmax = max(L, Lmax)
    Rmin = min(R, Rmin)
ans = max(0, Rmin - Lmax + 1)
print(ans)

D - Integer Cards

与えられたカードを順番関係なく書き換えることができる権利がいくつか与えられ、書き換えた後の和が最大になるようにしたときの和の値を答える問題です。

元々のカードに書いてある数字とその個数、書き換えられるカードの数字とその回数を全てまとめてしまい、大きい方から $N$ 枚になるまでとってしまえば、状況は同じになります。

提出コード

from collections import Counter

def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    A.sort()
    counterA = Counter(A)
    for _ in range(M):
        B, C = map(int, input().split())
        if C in counterA: counterA[C] += B
        else: counterA[C] = B
    counterAitems = list(counterA.items())
    counterAitems.sort(key=lambda x: x[0], reverse=True)
    idx = 0; ans = 0
    for c, b in counterAitems:
        if N-idx < b: 
            ans += c*(N-idx)
            break
        else: 
            ans += c*b
            idx += b
    print(ans)


if __name__ == "__main__":
    main()

E - Cell Distance

2021/9/4 追記

解答を見てからしばらく経って自分で解いてみました。この手の問題は「言い換え（= 和をとる順番を変える）」で解けるパターンが多いですね。

まず、この問題を解く方針としてあり得そうなのが以下です。

$i$ と $j$ （もしくは $x$ 軸と $y$ 軸）を分離する
総和の順序を(可能な場合に)入れ替える
式変形して引き算の形にする（包徐原理）

第一ステップ：和の取り方を変える

ストレートに考えると、次のように計算したいです。

まず配置を固定する。
配置されたコマに番号を振って、それぞれ $|x_{i} - x_{j}| + |y_{i} - y_{j}|$ を計算して足す。

この方針の計算量は $O(K^{2})$ ですが、コマの数は $K \leq N \times M \leq 2 \times 10^{5}$ なので、間に合いません。

ここから、和の取り方を変えてみます。

配置を固定するのではなく、先に全て洗い出してしまいます。全ての配置がわかったら、距離 $d$ のものがいくつあるかを数えて足し合わせる、という風に考えます。

※ ここでまだ距離 $d$ が明確に定義していません。2点の $|x_{i} - x_{j}| + |y_{i} - y_{j}|$ は、本当はそれぞれの軸に分解して考えたいですが、今の段階でできるかわからないので、これを距離 $d$ だと一旦考えておくことにします。

f:id:Xenous:20210904105251p:plain — 和の考え方のイメージ

さて、和の取り方を変えてみたものの、まだ途方もない感じがします。さらに考えてみます。

距離 $d$ のものがいくつあるかを計算する際、 $K$ 個の配置のまま考えると大変そうですが、よくよく考えると2つのコマのペアだけ見ていれば良いです。

そして、「そのペアが何回現れるか」が知りたいことです。

f:id:Xenous:20210904111519p:plain — 2つのコマに注目するイメージ

ここから、「2つ配置する × それが全体の配置の中で現れる回数」に対して、距離を計算すると答えになることがわかります。式にすると $_{N\times M}C_{2} \times _{N\times M-2}C_{K-2}$ です。

$_{N\times M}C_{2}$ ：マス全体から2つ選んでコマを置く。
$_{N\times M-2}C_{K-2}$ ：選んだ2つを除いて、残りのコマを置く場合の数

以上より、和の計算方法を、配置を固定してからではなく、2つのコマが配置全体のうち何回現れるか？という取り方に変えました。

しかし、 $_{N\times M}C_{2}$ は $O((NM)^{2})$ です。まだ計算量の改善が必要です。

第二ステップ：軸で分ける

計算式 $|x_{i} - x_{j}| + |y_{i} - y_{j}|$ を、それぞれの軸だけで計算できないか考えます。

式から、 $x$ と $y$ は独立しています（互いに影響を及ぼさない）。全ての配置において $x$ について調べて、その後全ての配置においても $y$ について調べる、ということができます。

f:id:Xenous:20210904120459p:plain — $x$ 軸に注目した場合のイメージ

$x$ 軸に注目して、二つのコマを適当に配置したとき、実際は $y$ 軸方向にも空間があるので、実質 $N^{2}$ 通りを見ていることと同じになります。

二つのコマを配置する場合の数は $_MC_2$ で計算できますが、 $O(M^{2})$ なので場合によっては TLE します。単純に並べるのではなく、 $|x_{i} - x_{j}|$ ごとにグループ化すると良いです。これを $d = |x_{i} - x_{j}|$ とすると、

距離 $d$ で二つのコマを配置する場合の数は $M-d$ 通り

であることがわかります。これは $O(M)$ で計算できます。ゆえに、このときの計算の式は

$(M-d) \times d \times N^{2} \times _{N\times M-2}C_{K-2}$

となります。

$y$ 軸についても同様に計算することができます。以上より、これらを足し合わせたものを $10^{9}+7$ で割ったあまりが答えになります。

提出コード

MOD = pow(10,9)+7
def MODINV(n:int, MOD=MOD):
    return pow(n, MOD-2, MOD)


class common_combinations():
    """
    mod を含む combination を高速に求めるためのクラス

        parameters:
        -----------
        N : int
            nCk を求める n の範囲(mod 未満)の最大値を N に設定する
            デフォルトは 510,000
        MOD : int
            設定したい mod の値
            デフォルトは 1,000,000,007
    """
    def __init__(self, N=510000, MOD=10**9+7):
        """
        combination を O(1) で計算するための前処理
        """
        self.N = N
        self.MAX_NUM = self.N + 1
        self.MOD = MOD

        self.fac  = [0 for _ in range(self.MAX_NUM)]
        self.finv = [0 for _ in range(self.MAX_NUM)]
        self.inv  = [0 for _ in range(self.MAX_NUM)]

        self.fac[0]  = self.fac[1] = 1
        self.finv[0] = self.finv[1] = 1
        self.inv[1] = 1

        for i in range(2, self.MAX_NUM):
            self.fac[i] = self.fac[i-1] * i % self.MOD
            self.inv[i] = self.MOD - self.inv[self.MOD%i] * (self.MOD // i) % self.MOD
            self.finv[i] = self.finv[i-1] * self.inv[i] % self.MOD


    def combinations(self, n:int, k:int) -> int:
        """
        combination を計算して返すメソッド

            Parameters:
            -----------
            n, k : int
                nCk に対応する整数 n, k.
            
            Returns:
            --------
            int
                nCk (mod) の計算結果.
                n または k が 0 より小さい場合は 0 を返す.
                n が k より小さい場合も 0 を返す.
        """
        if n < k:
            return 0
        if n < 0 or k < 0:
            return 0
        return self.fac[n] * (self.finv[k] * self.finv[n-k] % self.MOD) % self.MOD


def main():
    N, M, K = map(int, input().split())
    cc = common_combinations(N*M+10)

    # x の計算
    ans = 0
    for d in range(M):
        ans += (((M-d)*d)%MOD) * (N**2%MOD) * cc.combinations(N*M-2, K-2)
        ans %= MOD
    
    # y の計算
    for d in range(N):
        ans += (((N-d)*d)%MOD) * (M**2%MOD) * cc.combinations(N*M-2, K-2)
        ans %= MOD

    print(ans)


if __name__ == "__main__":
    main()

F - Absolute Minima

三分探索での解法を思いつきましたが、関数の更新がうまく実装できず（というより再帰で組んで間に合う気がせず）結局何もできませんでした。これも後日ときます。