Google Code Jam 2020 Round 1Cの最終問題であるOversized Pancake Choppersの解説です。
この問題はTest Set1から3の3つから構成されます。本番ではTest Set 1のみ解けました。この記事ではTest Set2とTest Set3について解説します。
問題概要
N個のパンケーキが存在する。パンケーキのサイズはである。D人の客に、同じサイズのパンケーキを渡さなければいけない。これを達成するために必要な最小のカット数はいくらか。
Test Set 2
制約
- 1 ≤ N ≤ 300
- 2 ≤ D ≤ 50
考察
パンケーキは、「等分でカットする」または「まったくカットしない」のどちらかのときに、「得られるスライス数＝カット数＋１」が成立しカット数を節約できます。例えば、サイズ14のパンケーキからサイズ4のスライスを3個得るには3回カットしなければいけませんが、サイズ12のパンケーキからサイズ4のスライスを3個得るには2回のカットで済みます。
例としての場合を考えてみます。客に提供するスライスサイズは、サイズ3のパンケーキを1から4に等分した3, 3/2, 3/3, 3/4のどれかか、サイズ5のパンケーキを1から4に等分した5, 5/2, 5/3, 5/4のどれかか、サイズ6のパンケーキを1から4に等分した6, 6/2, 6/3, 6/4のどれかになります。
Test Set 2では、上に上げたスライスの候補すべてについて、以下を調べます。
- (a) パンケーキ列Aから、サイズsのスライスをD個取れるか
- 取れないとすると、このスライスサイズは大きすぎるのでダメ
- (b) パンケーキ列Aから、サイズsのスライスを取るための最小回数
(a)は、パンケーキのサイズそれぞれをsで割ってあまりを捨てたものの和をとれば求められます。
(b)は、パンケーキ列Aのうち、サイズsでちょうど割り切れるパンケーキから順に、その中でもカット回数が少なくてすむパンケーキから順に貪欲にカットしていけば求められます。例えば、5回カットして6つのスライスが得られるパンケーキより、2回カットして3つのスライスが得られるパンケーキを優先的にカットするほうが、常に得です。
以上で問題が解けました。時間計算量は です。
実装
有理数を扱うのは面倒なので、パンケーキのサイズ列 を、スライスサイズが整数になるように何倍かしておくと楽です。
私の実装を以下に示します。Python 3だとTLEしてしまったので、PyPy2で通ることを確認しました。GCJはPyPy3がないので不便です…。
#!/usr/bin/env python2 # -*- coding: utf-8 -*- """ 客に提供するスライスのサイズは、必ず「どれかのパンケーキを等分したもの」になることに着目。 つまり、スライスサイズは、A[i]/1, A[i]/2, ..., A[i]/(D-1) (i = 0..N-1) のどれかになる。 あるスライスサイズについて、全探索。 Python 3だとSet2でTLE。 PyPy2だとSet2までAC """ from __future__ import print_function import sys # Python 2, 3両対応 if sys.version_info[0] == 2: myinput = raw_input elif sys.version_info[0] == 3: myinput = input def solve(): N, D = map(int, myinput().split()) As = list(map(int, myinput().split())) # パンケーキは小さい順に並び替えておく As.sort() ans = 10 ** 10 for d in range(1, D + 1): Bs = [a * d for a in As] for a in As: # パンケーキaをd-1回カットしてd個に等分割した場合を以下で考える # このときの基準サイズは a / d である。 # 有理数は扱いにくいので、すべてをd倍する。 # つまり、パンケーキ: B # 基準サイズ: a # カット可能か調べる avail = 0 for b in Bs: avail += b // a # カット不能ならcontinue if avail < D: continue # パンケーキBsそれぞれについて、基準サイズaでちょうど割り切れる場合、 # 何個のパンケーキを取れるかを数える just = [] for b in Bs: if b % a == 0: just.append(b // a) # お得なパンケーキから順番にとっていく # AsやBsはあらかじめ昇順にソートしてあるので、justも昇順にソートされている remain_num = D # あと何個のスライスが必要か cut_num = 0 # カット回数 for j in just: if remain_num >= j: remain_num -= j cut_num += j - 1 else: break # 足りない分は残りのパンケーキから取る cut_num += remain_num ans = min(ans, cut_num) print(ans) def main(): T = int(myinput()) for testcase in range(T): print("Case #{}: ".format(testcase+1), end="") solve() main()
Test Set 3
制約
- 21ケースは 9000 ≤ N ≤ 10000.
- 残りのケースは 1 ≤ N ≤ 1000.
- 2 ≤ D ≤ 50
考察
Test Set 2の解法はTLEするのでもうひと工夫必要です。
Test Set 2の解法では、パンケーキのそれぞれについて、A * D種類のスライスサイズで割り切れるかどうかを判定していたのが無駄でした。 サイズaのパンケーキがカット数節約の効果を得るのは、このパンケーキを1, 2, ..., D分割するときだけなので、この場合のみ考えればよいです。
この考察から、以下のような手続きで, keyが「スライスサイズ」、valueが「そのスライスサイズをちょうど取れる数を並べた配列」であるような辞書を作ると良いことがわかります。
dict = {}
for a in A[0], A[1], ..., A[N - 1]:
for d in 1, 2, ..., D:
# Fraction(a, d) は、a / dを表現する有理数クラス
dict[Fraction(a, d)].push_back(d)
例としての場合を考えてみます。辞書は以下のようになります。
- key: 3/1, value: [1, 2]
- key: 3/2, value: [2, 4]
- key: 3/3, value: [3]
- key: 3/4, value: [4]
- key: 5/1, value: [1]
- key: 5/2, value: [2]
- key: 5/3, value: [3]
- key: 5/4, value: [4]
- key: 6/1, value: [1]
- key: 2/1, value: [3]
keyは約分された有理数で持つ必要があります。各keyについて、サイズsのスライスを取るための最小回数を求める方法は、Test Set 2で書いたとおりです。
残る問題は、パンケーキ列Aから、サイズsのスライスをD個取れるかの確認です。もし上記辞書のkeyのそれぞれについてこの確認をしてしまうと時間計算量はとなり時間が足りません。
そこで、単調性を利用した二分探索を使います。keyの値をソートすると、小さなスライスサイズのときは問題なくスライスD個をとることができて、スライスサイズを大きくしていくと、どこかのタイミングでスライスD個をとれなくなります。その境界、つまりぎりぎりD個のスライスを作れる最大のスライスサイズs_maxを二分探索で探しておきます。
そうすれば、スライスのサイズsがs_max以下であるかどうかをチェックするだけで、スライスをD個取れるかが分かります。
以上で問題が解けました。時間計算量は、二分探索が 、各keyについてサイズsのスライスを取るための最小回数を求める部分が
だと思います。
実装
私の実装を以下に示します。これもPython 3だとTLE、PyPy2でACです。
また、Pythonの標準ライブラリで提供されているFractionクラスは遅すぎたので自力実装しています。カスタムクラスを辞書のkeyとして使うために__hash__と__eq__を実装しました（参考: python - Object of custom type as dictionary key - Stack Overflow ）。カスタムクラスをソートするために普通は比較関数を実装すると思いますが、Python 2とPython 3で必要な比較関数が違う（参考: python - Object of custom type as dictionary key - Stack Overflow）のが面倒だったので、分子 / 分母を浮動小数点数でもっておいてそれをkeyにソートするようにしました。大小関係の逆転が起こると嫌だなと思いましたが一応ACしました。
#!/usr/bin/env python3 # -*- coding: utf-8 -*- """ パンケーキが価値があるのは、ちょうど等分で割り切れるとき。 すべてのパンケーキについて、1等分 .. D等分を試して (スライスのサイズ, 何個のスライスが取れるか) のタプルを得る Python 3だとTLE """ from __future__ import print_function from __future__ import division import array from bisect import * from collections import * import fractions from fractions import Fraction import heapq from itertools import * import math import random import re import string import sys # Python 2, 3両対応 if sys.version_info[0] == 2: input = raw_input gcd = fractions.gcd elif sys.version_info[0] == 3: gcd = math.gcd class MyFraction: """fractions.Fractionがあまりに遅いので自分で実装""" def __init__(self, n, d): gcd_value = gcd(n, d) self.numerator = n // gcd_value self.denominator = d // gcd_value self.real = n / d # hashのkeyとして使うために__hash__, __eq__が必要 def __hash__(self): hashed_value = hash((self.numerator, self.denominator)) return hash((self.numerator, self.denominator)) def __eq__(self, other): return (self.numerator, self.denominator) == \ (other.numerator, other.denominator) def __repr__(self): return "{} / {} ({})".format(self.numerator, self.denominator, self.real) def mydiv(n, fraction): """floor(n(整数) / fraction)を返す""" return (n * fraction.denominator // fraction.numerator) def solve_set3(N, D, As): ans = 10 ** 10 slice_size_to_slice_num_list = defaultdict(list) for a in As: for d in range(1, D + 1): # fractions.Fraction()は非常に遅い # slice_size = Fraction(a, d) # そのため、自作クラスを使う slice_size = MyFraction(a, d) slice_num = d slice_size_to_slice_num_list[slice_size].append(slice_num) # slice_sizeのうち、D個カットできる境目を二分探索する # これにより、後段でO(N)でスライスが可能かをチェックする必要がなくなる slice_size_list = list(slice_size_to_slice_num_list.keys()) slice_size_list.sort(key=lambda obj: obj.real) lo = 0 hi = len(slice_size_list) while hi - lo > 1: mid = (lo + hi) // 2 # パンケーキからslice_sizeサイズのスライスを何個作れるか？ slice_size = slice_size_list[mid] cuttable_slice_num = 0 for a in As: cuttable_slice_num += mydiv(a, slice_size) if cuttable_slice_num >= D: break if cuttable_slice_num >= D: lo = mid else: hi = mid # カット可能なスライスの範囲のみを探索 for slice_size in slice_size_list[:(lo + 1)]: slice_num_list = slice_size_to_slice_num_list[slice_size] # スライスの個数が小さいものから順番に slice_num_list.sort() cnt = 0 profit = 0 for slice_num in slice_num_list: cnt += slice_num if cnt <= D: profit += 1 ans = min(ans, D - profit) return ans def solve(): N, D = map(int, input().split()) As = list(map(int, input().split())) print(solve_set3(N, D, As)) def main(): T = int(input()) for testcase in range(T): print("Case #{}: ".format(testcase+1), end="") solve() main()
