ループ変数をクロージャで包む
Common Lisp や ISLISP の do がループ変数を破壊的変更するのに対して Scheme では新しく環境を生成するのを知った時には「似て非なるものだ……」と思いました。 https://t.co/xKLGTMEzuA
— 齊藤敦志 (@SaitoAtsushi) 2020年10月30日
Gauche で確認コードを書いてみました。
(use srfi-42) ; list-ec (define (f) (list-ec (: i 0 3) (lambda () i))) (define (g) (rlet1 lis () (do ((i 0 (+ i 1))) ((= i 3)) (push! lis (lambda () i)))))
実行結果です。
gosh> (map (lambda (f) (f)) (f)) (0 1 2) gosh> (map (lambda (f) (f)) (g)) (2 1 0)
ハミング数
Gauche の data.heap モジュール を使ってハミング数を求めてみます。(効率は悪いです)
(use data.heap) (use gauche.generator) (define (hamming n) (define (gen) (generate (^[yield] (let1 heap (make-binary-heap) (binary-heap-push! heap 1) (let loop () (let1 v (binary-heap-pop-min! heap) (yield v) (dolist (x '(2 3 5)) (binary-heap-push! heap (* v x))) (loop))))))) ;; 連続する重複値は流さないジェネレータ (define (distinct g) (let1 head (g) (generate (^[yield] (yield head) (let loop ((prev head)) (let1 curr (g) (unless (eqv? prev curr) (yield curr)) (loop curr))))))) (generator->list (distinct (gen)) n))
実行結果です。
gosh> (hamming 30) (1 2 3 4 5 6 8 9 10 12 15 16 18 20 24 25 27 30 32 36 40 45 48 50 54 60 64 72 75 80)
参考:
ソート後の移動先インデックスを求める
配列をソートしたときの移動先インデックスを知りたい場合があります。
D 言語だと topNIndex 関数で知ることが出来ます。
import std; void main() { auto a = [99, 1, 100, 2, 150]; auto id = new int[a.length]; a.topNIndex(id, Yes.sortOutput); foreach (i; 0..a.length) { writefln("a[%d] = %d", id[i], a[id[i]]); } }
実行結果です。
a[1] = 1 a[3] = 2 a[0] = 99 a[2] = 100 a[4] = 150
競プロ(AtCoder)の問題を D 言語で解くための Tips
これは Competitive Programming (2) Advent Calendar 2018 の 12 日目の記事です。
競プロの問題を D 言語で解くための Tips を集めました。
オンラインジャッジサイトによって、D 言語のコンパイラのバージョンは異なりますので、この記事では、
AtCoder での現時点(2018/12/12)のコンパイラバージョン(DMD64 v2.070.1)を想定しています。
配列の要素を一気に書き換える
a[] = 100
と書くと、配列 a の要素を全て 100 に書き換えることができます。
import std.stdio; void main() { int[3] a; // 要素は 0 で初期化されます writeln(a); // [0, 0, 0] a[] = 100; // 全ての全てを 100 で書き換える writeln(a); // [100, 100, 100] }
2 次元配列の使い方
import std.stdio; void main() { auto a = new int[][](2, 3); writeln(a); // [[0, 0, 0], [0, 0, 0]] writeln(a.length); // 2 writeln(a[0].length); // 3 a[0][1] = 100; writeln(a); // [[0, 100, 0], [0, 0, 0]] }
配列の最大値、最小値を求める
reduce
を使います。
import std.algorithm; import std.stdio; void main() { int[] a = [3, 1, 4, 1, 5]; writeln(a.reduce!((a, b) => min(a, b))); // 1 writeln(a.reduce!((a, b) => max(a, b))); // 5 // こう書くこともできます writeln(a.reduce!min); // 1 writeln(a.reduce!max); // 5 }
※ minElement
, maxElement
が 2.072.0 から追加されましたが、AtCoder のコンパイラは 2.070.0 なので残念ながら使うことは出来ません。
Set を使う
C++ の set
クラスに相当するクラスは D 言語の標準ライブラリにはありません。代わりに連想配列を使います。
import std.stdio; void main() { bool[int] set; foreach (x; [3, 1, 4, 1, 5, 9, 2]) { set[x] = true; } writeln(set.length); // 6 writeln(1 in set ? "yes" : "no"); // yes writeln(set.keys); // [5, 4, 3, 2, 1, 9] }
スタック、キューを使う
D 言語の標準ライブラリには、スタック、キューは用意されていませんが、 DList クラスがスタック、キューの代わりになります。
スタックとしての使い方:
import std.container; import std.stdio; void main() { auto stack = DList!int(); writeln(stack.empty); // true // スタックにプッシュ stack.insertBack(10); // スタックの要素をピーク writeln(stack.back); // 10 stack.insertBack(20); writeln(stack.back); // 20 // スタックからポップ stack.removeBack(); writeln(stack.back); // 10 }
キューとしての使い方:
import std.container; import std.stdio; void main() { auto queue = DList!int(); writeln(queue.empty); // true // キューに値を格納する queue.insertBack(10); queue.insertBack(20); // キューから値を取り出す int x = queue.front; writeln(x); // 10 queue.removeFront(); }
タプルに名前が付けられる
import std.stdio; import std.typecons; alias Point = Tuple!(int, "x", int, "y"); void main() { auto p = Point(10, 20); writeln(p); // Tuple!(int, "x", int, "y")(10, 20) writeln(p.x); // 10 writeln(p.y); // 20 }
オイラーのトーシェント関数
オイラーのトーシェント関数は、以下の形で表すことができます(正確な定義は オイラーのφ関数 - Wikipedia にあります)。
この式の括弧内の分母を揃えます。
プログラムで値を得るときは、この式を元に以下のように計算していました。
import std.experimental.all; int totient(int n) { int ret = n; for (int p = 2; p * p <= n; p++) { if (n % p == 0) { ret = ret / p * (p - 1); while (n % p == 0) n /= p; } } if (n != 1) ret = ret / n * (n - 1); return ret; } void main() { writeln(iota(1, 20).map!totient); //=> [1, 1, 2, 2, 4, 2, 6, 4, 6, 4, 10, 4, 12, 6, 8, 8, 16, 6, 18] }
npca2013年部誌_競技プログラミングと初等整数論入門(PDF) と読むと、 この関数を次のように計算していました。
int totient2(int n) { int ret = n; for (int p = 2; p * p <= n; p++) { if (n % p == 0) { ret -= ret / p; // ここが違う while (n % p == 0) n /= p; } } if (n != 1) ret -= ret / n; // ここが違う return ret; }
こちらのほうが計算が単純になっていますね。この計算方法がどこから来るのか考えてみます。
最初の式に戻りますと、
この式の最初の と を掛けると
となります。最初の括弧内の項では、 から を引いています。 次に最初の括弧内の項を と置くと
となり、 を展開すると
となります。ここで行っているのは、 から を引いています。
つまり、これは ret -= ret / p
がやっていることなのですね。
参考
D言語: recurrence の練習
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); writeln(b.take(10)); //=> [3, 6, 12, 24, 48, 96, 192, 384, 768, 1536] // フィボナッチ数列 auto fibs = recurrence!((a, n) => a[n-2] + a[n-1])(1, 1); writeln(fibs.take(10)); //=> [1, 1, 2, 3, 5, 8, 13, 21, 34, 55] // 三角数 auto t = recurrence!((a, n) => a[n-1] + n)(0).drop(1); writeln(t.take(10)); //=> [1, 3, 6, 10, 15, 21, 28, 36, 45, 55] }