CodeChef June Challenge 2018: Ways to Work

問題概要

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

この時、を適切に選ぶことによって、人の日程の組み合わせの通り数をちょうど通りにする必要がある。
となる時、が最小となる時のの各値はいくらになるか？解のうちの1つを出力せよ。

制約

1つのテストケースに含まれるケース数:

全てのケースのの和はを超えない

解法

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

まずより、人目のスケジュールが決まった後の人目のスケジュールの選び方は通りになることが分かる。
これより、におけるスケジュールの組み合わせは通りであることが分かる。これが通りになればよい。

ここで、とする。この時、より、

という関係が導ける。

この関係より、はに比べて、いくらでも増加してよいが、減少については高々1にする必要があることが分かる。
例えば、は上の関係を満たす。

今回問われているのはを最小にすることである。この解に関係してくるのは、の内の、最後の真の単調減少列のみである。
例えば、であれば、解に関係するのはのみであり、それ以外のは影響を与えない。例えば、としても答えは変化しない。

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

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

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

この解の候補の探索を各について行う。の探索についてはで行うことができ、についてもであるため、になる。

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

実装

提出コード(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
小さいから調べて、見つかった時点で答えを出力することで高速化している。
上のテストケースも高速に通る。