これは Competitive Programming (2) Advent Calendar 2018 の 12 日目の記事です。 競プロの問題を D 言語で解くための Tips を集めました。 オンラインジャッジサイトによって、D 言語のコンパイラのバージョンは異なりますので、この記事では、 AtCoder …

べき乗演算子が定義されている言語について調べてみました。 D int x = 2 ^^ 10; //=> 1024 Haskell Prelude> 2 ^ 10 1024 JavaScript > 2 ** 10 1024 Julia julia> 2 ^ 10 1024 Mathematica In[1]:= 2 ^ 10 Out[1]= 1024 Python >>> 2 ** 10 1024 Ruby [1] …

オイラーのトーシェント関数は、以下の形で表すことができます(正確な定義は オイラーのφ関数 - Wikipedia にあります)。 この式の括弧内の分母を揃えます。 プログラムで値を得るときは、この式を元に以下のように計算していました。 import std.experiment…

import std.experimental.all; void main() { // 初項 1, 公差 2 auto a = recurrence!((a, n) => a[n-1] + 2)(1); writeln(a.take(10)); //=> [1, 3, 5, 7, 9, 11, 13, 15, 17, 19] // 初項 3, 公比 2 auto b = recurrence!((a, n) => a[n-1] * 2)(3); writ…

import std.experimental.all; void main() { foreach (a; [10, 20, 30]) writeln(a); } と書くと、配列の中身が foreach の変数 a に代入されて以下のように出力されます。 10 20 30 次に foreach の変数をひとつ追加します。 すると、その追加した変数には…

D 言語で、2, 3, 5, 7... のシーケンスを作る方法です。 素数をふるいにかけるとき 2 で割り切れるか 3, 5, 7... で割り切れるか を試しますが、これらを分離せずにひとつのシーケンスとして扱えると便利ですね。 import std.experimental.all; void main() …

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[…

まずは 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] 三角数を生成するところをもっと抽象化し…

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 で 2 次元リストを作るには、リスト内包表記を使って以下のように書くことが出来ます。 >>> rows, cols = 2, 3 >>> [[0] * cols for _ in range(rows)] [[0, 0, 0], [0, 0, 0]] 2 次元まではいいのですが、3 次元以上になるとリスト内包表記で書くの…

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 はタプル…