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
制約
考察
パンケーキは、「等分でカットする」または「まったくカットしない」のどちらかのときに、「得られるスライス数＝カット数＋１」が成立しカット数を節約できます。例えば、サイズ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がないので不便です…。
"""
客に提供するスライスのサイズは、必ず「どれかのパンケーキを等分したもの」になることに着目。
つまり、スライスサイズは、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
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:
avail = 0
for b in Bs:
avail += b // a
if avail < D:
continue
just = []
for b in Bs:
if b % a == 0:
just.append(b // a)
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しました。
"""
パンケーキが価値があるのは、ちょうど等分で割り切れるとき。
すべてのパンケーキについて、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
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
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):
slice_size = MyFraction(a, d)
slice_num = d
slice_size_to_slice_num_list[slice_size].append(slice_num)
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_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()
