Arantium Maestum

プログラミング、囲碁、読書の話題

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。

ちなみに問題はこの記事から:

qiita.com