SageMath でフィボナッチ数の練習
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 で 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
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を学んだ後は、以下の問題が解けるようになります。
- ABC 029 - D - 1
- 1 以上 N 以下のすべての整数に含まれる 1 の個数を求める問題です。
- ABC 007 - D - 禁止された文字
- [A, B] の範囲の数のうち、4 または 9 が含まれる数値がいくつあるかを求める問題です。
- Typical DP Contest - E - 数
- N 以下の整数で、各桁の和が D の倍数である個数を求める問題です。
VSCode で Markdown のみ行末の空白を削除しない
再帰に対する考え方を教えてくれた練習問題
確か『LISP I』だったと思うけど、次のような練習問題があった。
2 つの引数をとり、その 2 つの値の合計を返す関数を書け。ただし + は使わずに 1+ と 1- を使って。
なお、2 つの引数は正の整数と仮定してよい。
答えをみたら「なあんだ」と思えるが、その当時は自力でこの問題を解くことができなかった。 再帰に対する考え方を教えてくれた関数のひとつとして、その影響は大きい。
(defun add (x y) (if (zerop x) y (add (1- x) (1+ y)))) ; Emacs の *scratch* バッファでの実行結果 (add 1 2) ; 3 (add 100 2) ; 102