Shredding Paper
例によって競プロの記事から簡単面白そうな問題を解いてみる。
Shredding Company | Aizu Online Judge
import itertools as it import heapq def solve(k, n): s = str(n) if k == n: return (n, [s]) a = it.product((0,1), repeat=len(s)-1) b = ([0]+[i+1 for i, x in enumerate(z) if x]+[len(s)] for z in a) c = ([s[start:end] for start, end in zip(z, z[1:])] for z in b) d = ((sum(int(x) for x in z), z) for z in c) e = (z for z in d if z[0] < k) f = heapq.nlargest(2, e, key=lambda x:x[0]) if not f: return "Error: no sum smaller than k value {}".format(k) if len(f) == 2 and f[0][0] == f[1][0]: return "Error: two sums with identical largest value above k" return f[0]
itertoolsらぶ。
- 各桁の間の空間に分割を入れるか入れないかを0/1で表し、そのすべてのパターンをitertools.productで網羅する。
- 各パターンごとに、その0と1のリストを添字に変換し直し、その添字のリストを使って分割された数の文字列のリストを作成する。
- 足しあわせてフィルタして最大の値二つをheap queueを使って取り出して最大値が単独であることを確認して返す。
途中経過のいい名前を考えるのが一番大変・・・ というわけでそこはとりあえず放棄。The two hard problems in CS are concurrency and naming things。
ちなみに問題はこの記事から: