日々drdrする人のメモ

今日も明日もdrdr

CodeChef June Challenge 2018: Ways to Work

CodeChef June Challenge 2018の問題: Ways to Work (Code: WRKWAYS)
問題ページ: https://www.codechef.com/JUNE18A/problems/WRKWAYS

問題概要

 {N}人が、他人とかぶらないように1日ずつ選択し、計 {N}日働く。
各々には締め切りがあり、 {i}番目の人の締め切りは {d_i}となっている。つまり、他人とかぶらないように {1, ..., d_i}の中から働く日時を選択しなければならない。


この時、 {d_1, d_2, ..., d_N}を適切に選ぶことによって、 {N}人の日程の組み合わせの通り数をちょうど {C}通りにする必要がある。
 {d_1 \le d_2 \le ... \le d_N}となる時、 {d_N}が最小となる時の {d_1, d_2, ..., d_N}の各値はいくらになるか?解のうちの1つを出力せよ。

制約

1つのテストケースに含まれるケース数:  {1 \le T \le 100}
 {1 \le N \le 10^6}
全てのケースの {N}の和は {10^7}を超えない
 {1 \le C \le 10^9}

解法

 {C}を約数でうまく分解すると解ける。

まず {d_1 \le .. \le d_N}より、 {1, ..., i-1}人目のスケジュールが決まった後の {i}人目のスケジュールの選び方は {d_i - (i-1)}通りになることが分かる。
これより、 {d_1 \le d_2 \le ... \le d_N}におけるスケジュールの組み合わせは {\displaystyle \prod_i (d_i - (i-1))}通りであることが分かる。これが {C}通りになればよい。

ここで、 {a_i = d_i - (i-1)}とする。この時、 {d_i \le d_{i+j} (j > 0)}より、
 {a_i + (i-1) \le a_{i+j} + (i+j-1) \rightarrow \underline{a_i - a_{i+j} \le j}}
という関係が導ける。

この関係より、 {a_{i+1}} {a_i}に比べて、いくらでも増加してよいが、減少については高々1にする必要があることが分かる。
例えば、 {(a_1, ..., a_{10}) = (1, 3, 2, 1, 7, 6, 5, 12, 11, 10)}は上の関係を満たす。


今回問われているのは {d_N}を最小にすることである。この解に関係してくるのは、 {a_1, ..., a_N}の内の、最後の真の単調減少列のみである。
例えば、 {(a_1, ..., a_{10}) = (1, 3, 2, 1, 7, 6, 5, 12, 11, 10)}であれば、解に関係するのは {(12, 11, 10)}のみであり、それ以外の {a_i}は影響を与えない。例えば、 {(1, 1, 2, 3, 5, 6, 7, 12, 11, 10)}としても答えは変化しない。

そのため、最後の真の単調減少列以外は、例のように昇順に並べておくと計算しやすくなる。


解法としては、 {C}の約数で分解し、各 {a_i}を計算した上で、 {a_N}が最小になる数列を求める。

 {C}の2以上のある約数を {X}とし、最後の真の単調減少列の長さを {k}と決める。
まず {X*(X-1)*...*(X-k)}で割り算を行い、割り切れれば、そこで残った {Y = C / ( (X-1) * ... * (X-k) )}について、 {(N - k-1)}個の1以上 {X}以下の約数に分解できるかを調べる。分解できれば昇順に並べた上で真の単調減少列の前に結合し、解の候補とする。(この分解自体は {O(\sqrt{Y})}で行える)

この解の候補の探索を各 {X, k}について行う。 {X}の探索については {O(\sqrt{C})}で行うことができ、 {k}についても {C \le 10^9 < 13!}であるため、 {0 \le k \le 12}になる。

最後に、計算した数列のうち、 {X-k}が最小になる数列について、各 {a_i}から {d_i}を計算し、答えを出力すればよい。

実装

提出コード(PyPy2): https://www.codechef.com/viewsolution/18729265

T = int(input())
# x以下の約数でyを分解
def calc(y, x):
    # yがx以下なので分解する必要なし
    if 1 < y <= x:
        return [y]
    S = []
    w = 2
    # √y ≦ v となるvでyを分解
    while w*w <= y > x:
        if y % w:
            w += 1
            continue
        v = y // w
        if x < v:
            w += 1
            continue
        assert y//v == w <= x
        y //= v
        S.append(v)
        break
    if 1 < y <= x:
        S.append(y)
        return S
    # w ≦ √y となるwでyを分解
    while w > 1 and y > x:
        if y % w:
            w -= 1
            continue
        if x < w:
            w -= 1
            continue
        while y % w == 0 and y > x:
            y //= w
            S.append(w)
        w -= 1
    if 1 < y <= x:
        S.append(y)
        return S
    # x < y となる数が残って分解できない場合
    if y > 1:
        return None
    return S
def check(N, C, x):
    T = [x]
    y = C // x; z = 0
    while len(T) < N and z < x-1 and y % (x-1-z) == 0:
        y //= x-1-z
        T.append(x-1-z)
        z += 1
 
    # 各kについて、x, x-1, ..., x-k を真の単調減少列とできるか調べる
    while T:
        S = calc(y, x)
        if S is not None:
            M = len(S) + len(T)
            if M <= N:
                # 長さがNに満たない場合は1を追加してNに合わせる
                return [1]*(N-M) + sorted(S) + T
        y *= T.pop()
    return None
 
for _ in xrange(T):
    N, C = map(int, raw_input().split())
    x = 2
    if N == 1:
        print(C)
        continue
    if C == 2:
        ans = [1]*(N-2)+[2,1]
    else:
        ans = [1]*(N-1)+[C]
    # Cの全ての約数xについて調べる
    while x*x <= C:
        if C % x:
            x += 1
            continue
        r = check(N, C, x)
        if r is not None and r[-1] < ans[-1]:
            ans = r
        r = check(N, C, C//x)
        if r is not None and r[-1] < ans[-1]:
            ans = r
        x += 1
    # a_i -> d_i
    for i in xrange(N):
        ans[i] += i
    print(" ".join(map(str, ans)))

上の提出コードで通ったが、探索のやり方がまずそうで、制約を満たす下記のテストケースをローカルで試したら結構時間がかかった。テストケースが弱い気がする。

10
1000000 958003200
1000000 958003200
1000000 958003200
1000000 958003200
1000000 958003200
1000000 958003200
1000000 958003200
1000000 958003200
1000000 958003200
1000000 958003200

コンテスト後に書き直したコード: https://www.codechef.com/viewsolution/18874317
小さい {X}から調べて、見つかった時点で答えを出力することで高速化している。
上のテストケースも高速に通る。