隣り合う要素でグループ分け

Ruby

0 と 1 からなる配列があります。 たとえば [0, 1, 1, 0, 0, 1, 0, 0] の配列を [[0], [1, 1], [0, 0], [1], [0, 0]] のように 0 と 1 とでグループ分けする関数が必要になったので作ってみました。

def group(xs)
  return [] if xs.empty?
  g = []
  buf = [xs[0]]
  xs.drop(1).each {|e|
    same = yield buf[-1], e
    if same
      buf << e
    else
      g << buf
      buf = [e]
    end
  }
  g << buf
  g
end

実行結果です。

p group([1, 1, 0, 0, 0, 1, 0, 1, 1]) {|a, b| a == b }
#=> [[1, 1], [0, 0, 0], [1], [0], [1, 1]]

# 偶奇でグループ分け
p group([2, 4, 6, 1, 3, 6, 8]) {|a, b| a % 2 == b % 2 }
#=> [[2, 4, 6], [1, 3], [6, 8]]

Ruby で三角数の無限シーケンスを作る

まずは Enumerator で三角数を具体的に生成してみよう。

def triangles
  Enumerator.new do |y|
    sum = 0
    1.step {|i|
      sum += i
      y << sum
    }
  end
end

p triangles.take(10)
#=> [1, 3, 6, 10, 15, 21, 28, 36, 45, 55]

三角数を生成するところをもっと抽象化したい。
iterate を作ってみる。

def iterate(init)
  x = init
  Enumerator.new do |y|
    y << x
    loop { y << (x = yield x) }
  end
end

def triangles2
  x = 1
  iterate(1) {|sum| x += 1; sum + x }
end

p triangles2.take(10)
#=> [1, 3, 6, 10, 15, 21, 28, 36, 45, 55]

iterate の外側で変数(x)を定義しないようにできないかな。

def triangles3
  iterate([1, 2]) {|a, b| [a + b, b + 1] }.lazy.map {|e| e[0] }
end

p triangles3.take(10).to_a
#=> [1, 3, 6, 10, 15, 21, 28, 36, 45, 55]

iterate 内で三角数とインデックスを引き回すようにしてみた。
lazy の部分はきちんと理解していない。

Haskell には scanl という関数があるみたいだ。
Ruby で scanl を定義してみよう。

module Enumerable
  def scanl(z)
    Enumerator.new do |y|
      y << z
      x = z
      each {|e|
        y << (x += e)
      }
    end
  end
end

def triangles4
  2.step.scanl(1) {|a, b| a + b }
end

p triangles4.take(10)
#=> [1, 3, 6, 10, 15, 21, 28, 36, 45, 55]

SageMath でフィボナッチ数の練習

sage 
sage: def fib(n):
....:     if n == 0: return 0
....:     m = matrix([[1, 1], [1, 0]]) ** n
....:     return m[0, 1]
....:
sage: [fib(i) for i in range(20)]
[0,
 1,
 1,
 2,
 3,
 5,
 8,
 13,
 21,
 34,
 55,
 89,
 144,
 233,
 377,
 610,
 987,
 1597,
 2584,
 4181]

参考

Python で多次元リストを作る

Python

Python で 2 次元リストを作るには、リスト内包表記を使って以下のように書くことが出来ます。

>>> rows, cols = 2, 3
>>> [[0] * cols for _ in range(rows)]
[[0, 0, 0], [0, 0, 0]]

2 次元まではいいのですが、3 次元以上になるとリスト内包表記で書くのはなかなか難しいです。
そこで、多次元リストを返す関数を作ってみました。

def multilist(ds, default):
    assert len(ds) > 0 and all(e > 0 for e in ds)

    def rec(index, parent):
        if index + 1 == len(ds):
            parent.extend(default() for _ in range(ds[-1]))
        else:
            for _ in range(ds[index]):
                child = []
                parent.append(child)
                rec(index + 1, child)

    root = []
    rec(0, root)
    return root

こういう風に使います。

>>> multilist([2, 3], lambda: 0)
[[0, 0, 0], [0, 0, 0]]
>>> multilist([2, 3, 4], lambda: 0)
[[[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]], [[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]]

この関数を使って、ABC 029 D - 1 を解いてみました:

collections.defaultdict とタプルを使う方法もあります

>>> import collections
>>> d = collections.defaultdict(lambda: 0)
>>> d[1, 2, 3] = 100
>>> d[1, 2, 3]
100
>>> d[0, 0, 0]
0

curry, uncurry

Haskell 
Prelude> :t curry
curry :: ((a, b) -> c) -> a -> b -> c
Prelude> :t uncurry
uncurry :: (a -> b -> c) -> (a, b) -> c
Prelude> add (a, b) = a + b
Prelude> curry add 2 3
5
Prelude> mul a b = a * b
Prelude> uncurry mul (2, 3)
6
  • curry はタプルから引数へ展開
  • uncurry は引数をタプルにまとめる

というようなイメージなのかな。

zip した各要素には uncurry が使えそう。

Prelude> xs = map (uncurry (+)) $ zip [1..] [2..]
Prelude> take 10 xs
[3,5,7,9,11,13,15,17,19,21]

AtCoder など競プロで学んだこと

これはCompetitive Programming Advent Calendar 2017の 17 日目の記事です。

AtCoder のレートは緑です。最近ようやく水色に届きました。そんな筆者ですが、AtCoder など競プロで学んだ内容をいくつか紹介したいと思います。

long に収まらない整数の余りを BigInteger を使わずに求める

64 bit を超える整数の余りを BigInteger を使わずに求める方法を、この問題から学びました。
BigInteger を使える言語には関係ないと思われるかも知れませんが、BigInteger に変換するだけで TLE になるケースがあるため、この計算方法を知っておくことは重要です。

# s mod m を計算する
def mod(s, m)
  n = 0
  for c in s.chars
    n = (10 * n + c.to_i) % m
  end
  n
end

n / m の切り上げ

// いままでずっとこう書いてました
int x = (n / m) + (n % m == 0 ? 0 : 1);

// 上の式は、以下のように書けます
int y = (n + m - 1) / m;

この計算方法は、以下で紹介されています。

gcd と lcm の分かりやすい説明

最小公倍数と最大公約数についての、とても分かりやすい説明があります。図がわかりやすく理解を助けてくれます。

この記事を読んだあとに、実際に SRM 611 の問題にチャレンジすると大変勉強になります。

桁 DP の学び方

pekenmpy さんの桁DP入門は非常に分かりやすいです。

上記の記事で桁DPを学んだ後は、以下の問題が解けるようになります。