CodeChef June Challenge 2018: Ways to Work
CodeChef June Challenge 2018の問題: Ways to Work (Code: WRKWAYS)
問題ページ: https://www.codechef.com/JUNE18A/problems/WRKWAYS
問題概要
人が、他人とかぶらないように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
小さいから調べて、見つかった時点で答えを出力することで高速化している。
上のテストケースも高速に通る。