cafelier のSRM参加記録です。コンテスト中に考えてたことを執拗に全部書き残すとどうなるだろうかという試み本番中にこういうコードが書きたかったなあ、という後で書いた反省コードを書き残す試み
スパムが来たのでしばらくコメント欄をはてなユーザ限定にしています、すみません、
|
ちょっと分子が分母を上回りましたがいくつかAOJの問題をDで解いてみました（サブミットは当然してないです）。しかしあまり面白くならなかったので途中で飽きた。
|
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1004
さっき実は、10003 は面白くないから 10004 をやろう、と思ったら間違えて 1004 を解いてしまったのでその話をします。
|
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1005
せっかくなので1000番台をもう一個。
|
AtCoder で使える、 Google Code Jam 2012 予選 でもトップの人が宣伝している、などなどの理由で最近D言語が競技プログラマーの間でブームらしいです。SPOJやCodeChefでもリストには入っていますがバージョン古い気がするので微妙です。このビッグウェーブに乗るべくD言語を使ってみようかなーという人向けの紹介記事を書きます。
まずは、(1/2) では、これだけ知っておけば、競技プログラミングの最中に何かがD言語で書けなくて問題が解けないということはないだろう という知識の部分だけ書きます。別の言い方をすると、「Codeforces の Unknown Language Round でD言語が出たらこのページを見れば最初の5問は瞬殺」が目標です。
言語やライブラリの仕様は http://dlang.org/ に書いてあります。
日本語訳は http://www.kmonos.net/alang/d/ にありますが１年分古いです（すみません）。基本的には日本語訳でもまだほとんど問題ないはずですが、「あれ？書いてあることと動作が違うぞ？」と思ったときは本家の英語の方を必ず確認してください。
日本でD言語を活発に使っている人たちはよくTwitterで見かけます。「D言語」という単語や #d_lang というハッシュタグを含むツイートをしていると @repeatedly さんや @mono_shoo さんに発見されてレスがつく可能性があるので積極的に絡んでいくと色々Dの情報が得られるかも知れません。
コマンドラインでの使い方だけ書きます。GUI や IDE がないとわからない！という人は…頑張って他の解説を探してください。
D言語のソースコードは .d という拡張子のファイルに書きます。hogehode.d に書いたコードをコンパイルするには
dmd hogehoge.d
です。hogehoge.exe (Windowsの場合) か hogehoge (Linux等の場合) というバイナリができるので動かしてください。
rdmd hogehoge.d
とするとコンパイル＆実行を一発でやってくれるので便利です。最近私はこれしか使ってません
ソースファイルの文字コードはUTF-8かUTF-16かUTF-32のどれかです。日本語のコメントを書くときは、Shift_JISやEUC-JPで保存しないように気をつけてください。日本語コメント書かない場合は気にしなくていいです。
プログラムは void main() という関数から実行されます。if や for や while や do-while や continue や break や switch や goto や return の使い方は全部 C++ や Java と同じです。関数の定義の仕方も同じです。コメントの書き方も同じです。全部同じです。同じように使ってください。
void main() { // 100以下の素数の和を計算している。 int total = 0; for(int n=2; n<=100; ++n) { if( is_prime(n) ) total += n; } } /* 素数判定 */ bool is_prime(int n) { for(int v=2; v*v<=n; ++v) if( n%v == 0 ) return false; return true; }
CやC++と違って、関数はどの順番に並べても構いません。C言語の「プロトタイプ宣言」みたいなものはありませんので書かないで下さい。
これも基本的にC系の言語とおなじです。同じように使ってください。
使える演算子も全部同じです。+, -, *, /, %, ビット演算, 等号不等号各種, += で加算代入, ++ でインクリメント, などなど。同じように使ってください。
C の printf や C++ の cout や Java の System.out に相当するものは、標準ライブラリの std.stdio モジュールを import して使います。
import std.stdio; void main() { write("Hello, "); // write は改行なしで出力 writeln("world."); // writeln は最後に改行をつける writeln(1+2*3); // 文字列以外のものを渡したら自動で文字列化して表示 writeln(1, " ", 10, " ", 3.141592); // 引数を複数渡すとつなげて表示 }
こんな風に出力されます。
Hello, world. 7 1 10 3.141592
細かい書式などの指定は、write, writeln の代わりに writef と writefln を使います。
import std.stdio; void main() { writef("%d %x %b ", 17, 17, 17); // 10進, 16進, 2進 writefln("%.2f", 3.141592); // 小数点以下2桁まで }
17 11 10001 3.14
デバッグ用の出力を C++ なら cerr、Java なら System.err に出すことがあると思いますが、D だと、stderr の write, writeln, writef, writefln を使います。
import std.stdio; void main() { stderr.write("Hello, "); stderr.writeln(1+2*3); stderr.writef("%d %x %b ", 17, 17, 17); stderr.writefln("%.2f", 3.141592); }
普通の標準出力の方も、これに揃えて stdout.writeln("Hello") みたいな書き方もできます。
データを標準入力から読み込むには、やはり同じく std.stdio の、readf （C言語のscanfっぽい書式指定読み込み）と readln （一行読み込み）という関数があります。stdin.readf や stdin.readln と書いても同じ機能です。ただし、readf は scanf 等に似て非なるものなので、慣れずに使うとハマります。ハマりポイントの説明が面倒なので、readln だけを使うのが競技プログラミングには個人的にはおすすめです。
import std.stdio; void main() { for(int i=0; i<100; ++i) { string s = readln(); // 一行読み込み write(s); } }
readln() は標準入力から一行読み込みます。注意点として、C++ の std::getline と違って、readln は最後に改行文字を含みます。要らない場合は、std.string モジュールの chomp() 関数を使うと、末尾の改行文字がもしあれば落としてくれます。
import std.stdio; import std.string; void main() { string no_kaigyo_firstline = chomp(readln()); }
標準入力の終わり (EOF) では、改行文字を含まない、つまり長さ 0 の文字列が帰ってくるので、EOF判定はそれでやるか、stdin.eof() で判定します。
import std.stdio; void main() { string s; while( (s=readln()).length == 0 ) writeln("<", chomp(s), ">"); // あるいは // for(;;) { // string s=readln(); // if( stdin.eof() ) break; // writeln("<", chomp(s), ">"); // } }
競技プログラミングの場合、入力データはほぼ確実に空白区切りで渡されるので、そういう入力形式のときは、std.array の split 関数で切り分けてから、std.conv の to!int 関数などで文字列から変換します。
例えば、かの有名な A+B Problem はこんなコードになります。
import std.stdio; // readln import std.array; // split import std.conv; // to void main() { string[] input = split(readln()); // splitで文字列を文字列の配列に切り分け int a = to!int(input[0]); // 第0要素を整数に変換 int b = to!int(input[1]); // 第1要素を整数に変換 writeln(a+b); // 表示 }
splitは前後の空白等を自動で削ってくれるので、chompなくてもいいです。予想が付くとおもいますが、doubleに変換したいときはto!doubleです。readln() と split() と to!int と to!long と to!double さえあれば基本的に困らないはず。
配列を使う適当なサンプルプログラムです。エラトステネスの篩というアルゴリズムです。
import std.stdio; void main() { int N = 1000; bool[] is_prime = new bool[N]; // 長さNの配列 int[] primes; // 長さ0の空配列 for(int p=2; p<N; ++p) { if( is_prime[p] ) { // 添え字アクセス primes ~= p; // 配列の末尾に追加（push_back） for(int q=p+p; q<N; q+=p) is_prime[q] = false; // 添え字アクセス } } writeln( primes.length ); // 1000未満の素数は何個？ }
型 T の要素の配列は T[] という型です。配列を新しく作るときは new T[要素数] です。Javaと同じですね。new してますが、ガベージコレクションが働いて要らなくなったらメモリは勝手に解放されるので、解放のことは気にしなくていいです。
Java と違うのは、途中で配列の長さを変えられます。~= 演算子で末尾に要素を足します。ArrayList や std::vector に近いです。.length で長さがとれます。
別のサンプル。
import std.stdio; void main() { int[] fractal = [0]; for(int i=1; i<10; ++i) fractal = fractal ~ [i] ~ fractal; // ~ は配列結合演算子 fractal.length = 30; // .lengthは代入して変更もできます。std::vectorでいうresize()です。 writeln(fractal); }
[0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1]
別の。
void main() { int[] primes = [2, 3, 5, 7, 11, 13, 17]; writeln( primes[0..1] ); // [2] writeln( primes[0..2] ); // [2, 3] writeln( primes[2..$] ); // [5, 7, 11, 13, 17] writeln( primes[2..$-1] ); // [5, 7, 11, 13] }
配列[x..y] でx番目(含む)からy番目(含まない)の部分配列が取り出せます。O(1)です（単にポインタずらしているだけなので）。配列の添え字の中だけで使える $ という特殊な式があって、その配列の .length を指します。
別のサンプル。一括処理みたいなの。
int[] x = [1,2,3]; int[] y = [4,5,6]; int[] z; z[] = x[] + y[]; // [5,7,9]; x[] = z[] + 3; // [8,10,12]; x[] = 1; // [1,1,1]
別の。今ではこの組み込みのsortは使わない（次回説明します）のですが、とりあえず今回の範囲で競技プログラミングに必要な要素に全部触れておこうと思ったのでとりあえずのソートの仕方にも触れておきます。詳しくは次回。
int[] x = [111,2,33]; x.sort; // x は [2,33,111] になる。
もう一つだけ。
int[] x = [1,2,3]; int[] y = x.dup; // コピー！ y[0] = 100; writeln(x[0]); // 1
.dupで配列のコピーを作ります。単にy=xとすると同じ領域を指すのでyを書き換えたらxも変わります。
すでに何度か出てきてますが、string という型が文字列です。
void main() { string hello = "hello"; for(int i=0; i<hello.length; ++i) writeln(hello[i]); }
h e l l o
string の実体は immutable(char)[ ] という型で、つまりだいたい char の配列です。なので、~ で結合できますし、[ ] で添字アクセスできますし、[1..$-1] で部分文字列を作れます。ただし、immutable つまり 変更できない char の配列なので、
hello[0] = 'w';
のようなコードはコンパイルエラーになります。書き換えはできません。（JavaのStringと同じです。）書き換えがしたいときは char[] を別途つくってください。
文字列としての色々な便利操作関数は以下のモジュールにあります。
「UnknownLanguageRound最初の数問は瞬殺」編をお届けしました。準備段階なので、これだけだと特にD言語が魅力的には見えないかもしれませんが、その辺は続きをご覧下さい…と言いたいところですが、実は私にとって、こと競技プログラミングに限って言うと、D言語の一番の魅力はもうここまで紹介済みです。つまり
Dの配列はstd::vectorよりJavaの配列よりJavaのArrayListよりC#のArrayListより使いやすい
と思うのです。（C#の多次元配列は羨ましいのでここには列挙しない）。文章で読んでるだけだとなかなか実感が湧かないかもしれませんが、配列のスライス（部分配列取り出し）と結合とその他色々はとても便利です。RubyやPythonを使っている人にはその辺の機能は当たり前だと思いますが、その当たり前の機能が、C++に匹敵する速度で手に入るのは非常に魅力的です。言語の定数倍の遅さのせいで正しいはずのコードが通らない、ということはDならまずありません。
|
続きです。
string[] strs = ["aaa", "bbb", "ccc"]; foreach(s; strs) // strsの要素をループ writeln(s); foreach(i, s; strs) // strsの要素を添え字付きでループ writeln(i, ": ", s); foreach(i; 0..100) // 0から99まで(100は含まない)ループ writeln(i); foreach_reverse(s; strs) // strsの要素を逆順にループ writeln(s); foreach_reverse(i, s; strs) // strsの要素を添え字付きで逆順にループ writeln(i, ": ", s); foreach_reverse(i; 0..100) // 99から0までループ writeln(i);
はい。
標準ライブラリの std.bigint というモジュールを import すると BigInt 型が使えます。普通に+-*/で演算できます。JavaのprobablePrimeのような格好いいメソッドはありません。
import std.stdio; import std.bigint; BigInt factorial(int n) { return n>0 ? factorial(n-1) * n : BigInt(1); } void main() { writeln(factorial(1000)); }
複素数が言語組み込みの型としてあります。cfloat, cdouble, creal という型名です。std.complexというライブラリ実装に置き換えるという話があったんですがまだ置き換わってないので組み込み型の方を紹介します。
import std.stdio; import std.math; // 実部 .re と虚部 .im と四則演算以外の関数は std.math で void main() { creal z = 1+2i; z = z*z; // (1+2i)(1+2i) = -3+4i writeln(z.re); // -3 writeln(z.im); // 4 writeln(conj(z)); // -3+-4i }
普通の整数や浮動小数点数にもちょっと便利機能があります。
void main() { int x = 3^^4; // 3の4乗 : 81 int veryLarge = int.max; // intに入る最大値すなわち2147483647 real inf = real.inf; // IEEE754の∞値 }
競技プログラミング的に言うと、べき乗は3状態あるもののビットじゃないけどビットマスク、っぽいものの計算が楽になったりします。.max や .min や .inf は変数の初期値として埋めておくと役に立つ場面が色々。
std::map<string, int> や java.util.HashMap<String, Integer> のような、あれです。メモ化に使います。
int[string] m; m["one"] = 1; m["two"] = 2; m["three"] = 3; if( "four" in m ) writeln("hogehoge"); m.remove("three"); writeln(m.length); // 2 foreach(key, value; m) { ... } int[string] point_to_same_as_m = m; // 同じmapを参照 int[string] another = m.dup; // コピーはdupで
そんな感じで ValueType[KeyType] という型として言語組み込みでこの機能を持っています。実装はハッシュ表を使っているので、C++のstd::mapやjavaのTreeMapのような、キーの順序通りに取り出す機能は、この連想配列にはありません。
HashSet相当のものはないので、私は bool[Type] を set としてよく使っています。
std.container
に、BinaryHeap (priority_queue/PriorityQueue) と RedBlackTree (set/TreeSet) があります。私使ったことないので詳しくは知りません...。
std.typecons モジュールに、Tuple!() というテンプレートが用意されています。2つ組や3つ組を作れます。
import std.typecons; void main() { Tuple!(int, string, real) t = tuple(1, "hello", 3.14); // tuple() 関数はC++のmake_pairみたいなもの、型を省略して構築 int x = t[0]; // 0番目はint string y = t[1]; // 1番目はstring t[2] = 2.72; // 2番目はreal }
DのTupleの良いところは、メンバの名前をfirstやsecondじゃなくて自由に決められるところです。
Tuple!(int, "src", int, "dest") edge = tuple(0, 2); writeln(edge.src, "-->" edge.dest);
型名が長いなーと思ったら、aliasを使います（C++で言うtypedefです）。
alias Tuple!(real, "x", real, "y", real, "r") Circle; Circle c = Circle(0.1, 0.2, 0.3); c.r = 0.4;
Tupleでメンバの名前がつけられるとなると、競技プログラミングレベルではclassやstructを定義せずに全部Tupleで済ませてしまうことがかなり多くなるのですが、必要ならばもちろんクラスを作って使うこともできます。クラスの定義、使い方はJavaと同じです。 唯一の注意点としては、コンストラクタの名前は クラス名() ではなく、this() です。あとデフォルトは public です。
詳しくは他のもっと真っ当な解説などを。
void sort(int[] arr, bool delegate(int x, int y) ordered) { foreach(i; 0..arr.length) foreach(j; i+1..arr.length) if( !ordered(i, j) ) {int tmp=arr[i]; arr[i]=arr[j]; arr[j]=tmp;} } void main() { int[] weight = [9,3,4,7,1,6,2,8,5]; int[] arr = [0,1,2,3,4,5,6,7,8]; sort( arr, (int x, int y){ return weight[x]<weight[y]; } ); }
(int x, int y){ return weight[x]<weight[y]; } の部分が無名の関数です。周りの環境のweightという変数を使うこともできています。この無名関数を変数で受けるには、<b>delegate という型で受けます。構文は上の例のような感じ。
C++の<algorithm>ヘッダに相当する物は、Dでは std.algorithm モジュールです。std.range も見ておくと便利です（特に、二分探索系の機能はstd.rangeにあります）。機能としては基本的に <algorithm> をなぞったものが多いですが、よく見るとBoyerMooreとかlevenshteinDistanceなどが紛れ込んでいてちょっと楽しいです。
楽しいかどうかはさておき、std.algorithm を使うにあたって重要なポイントは、Range という概念です。C++ では iterator というものの上にSTLのアルゴリズムがすべて組まれていましたが、D言語では Range の上に全部のアルゴリズムが組まれています。
なにやら難しそうですが、要はぶっちゃけると Range は iterator の begin と end の組と思って下さい。Topcoderなどでも
#define ALL(c) (c).begin(), (c).end()
というけしからんマクロを書いている人をよく見ますが、確かに、この二つは常に組であつかった方が色々と便利なのです。
import std.algorithm; import std.stdio; void main() { int[] arr = [1,2,3]; auto r = find(arr, 2); writeln(r); // [2,3] }
[1,2,3] から 2 を探すと、最初に 2 が現れた位置より後ろ全体を指すRangeが返ります。別の例。count。
import std.algorithm; import std.stdio; void main() { int[] arr = [1,2,3]; writeln( count!((int x){return x>=2;})(arr) ); // 2以上のものの個数。2個。 writeln( count!("a>=2")(arr) ); // 同じ意味 }
関数を引数にとるタイプのアルゴリズムの場合、アルゴリズム名!(ここ)(range) に関数を渡します。周りの環境の変数をみないのであれば、"a"を引数と思った関数のbodyの文字列を書いても行けたりします。!() は C++ でいうテンプレート引数を渡している部分になります。
普通の配列を操作する＆走査するRangeは要するにただの部分配列ですが、Rangeという概念自体はもっと抽象的なものなので
import std.algorithm; import std.range; import std.stdio; void main() { string[] names = ["taro", "hanako", "toastman"]; int[] ratings = [3000, 4500, 4000]; sort( zip(ratings, names) ); writeln(names); // ["taro", "toastman", "hanako"] writeln(ratings); // [3000, 4000, 4500] }
二つの配列を並行して走るRangeをzipでその場で作ってそのRangeをsort、とやると元の二つの配列がpairとしての順序でsortされたりします。これは割と経験的に便利です。
別の例。二分探索。
import std.array; import std.range; void main() { int[] arr = [1,2,3,4,5]; auto sorted = assumeSorted(arr); int[] lw = array(sorted.lowerBound(3)); // [1,2]; int[] up = array(sorted.upperBound(3)); // [4,5]; }
Rangeを返値として返す関数の結果は大抵よくわからない謎の型になっていますが、auto で自動的に適切な型で受け取ることができます。あと、そのRangeをこれ以上他のアルゴリズムに渡したりしないので普通の配列にしてください、と思ったらstd.arrayのarray()関数でRangeを何でも配列化できます。
std.concurrencyのspawnという関数でスレッドを起動してsendとreceiveでやりとりします。最近のマシンは4コアや8コアは持っていたりするので、ローカルで実行する形式のコンテストでは、単純にテストケースを別スレッドで並行に実行するだけで8倍の高速化が達成できたりすることがあります。
import std.stdio; import std.concurrency; void compute_square(Tid parent, int n) { send(parent, n, n*n); } void main() { // 100個スレッド起動 foreach(i; 0..100) spawn(&compute_square, thisTid, i); // 100個返事が来るのを待つ int[] results = new int[100]; foreach(_; 0..100) receive( (int i, int result) { results[i] = result; }); writeln(results); }
スレッドを起動したりメッセージ通信したりするコードはこれだけです。
そして最近はstd.parallelismなどという物もできていました…知らなかった…
とりあえず、以上です。
D言語の言語機能の紹介としては、テンプレートとかテンプレートとかテンプレートとか契約とか契約とか契約とか特徴的な部分をごっそり省いているのですが、競技プログラミングでそこまで激しくその辺りの機能を使うことはなかろうということで省いています。「○○と同じです」で済ませた部分も本当は全然同じではなくて、同じ書き方をしたらだいたい同じに動くというだけで、同じでない書き方も色々できて面白いのですが、その辺りは他のまともな解説記事を読んでみてください。ではでは。
あとで | |
presented by
cafelier/k.inaba
under
D言語（余りの符号は割られる数に合わせる）:
-10 / 3 == -3
-10 % 3 == -1
Python（余りは割る数の符号に合わせる）:
-10 / 3 == -4
-10 % 3 == 2
仕様で未定義ということもなくて、この動作をする、と明記されている感じです。
void set_value(ref int x) { x = 6502; }
int hoge; set_value(hoge); // hoge == 6502
class Foo {
ref int foo() { return x; }
int x;
}
(new Foo()).foo() = 8086;
int[] arr = [1,2,3];
foreach(ref x; arr) x = x*x;
// arr == [1,4,9]
http://dlang.org/function.html#parameters
http://dlang.org/function.html#ref-functions
ところで、連想配列の箇所で誤記かと。
KeyType[ValueType] → ValueType[KeyType]
import std.conv;
import std.stdio;
import std.typecons;
// 除算の別の挙動の定義
int my_div(int x, int y) { int q = x/y; return q*y > x ? q-1 : q; }
int my_mod(int x, int y) { return x - my_div(x,y)*y; }
// 除算だけ変えたintっぽい型
struct modint
{
// コンストラクタ
this(int v){this.val = v;}
private int val;
// ほとんどの処理はintに転送
mixin Proxy!val;
// modint/int, modint%int の挙動を変更
auto opBinary(string op:"/", T)(T y) { return modint(my_div(val, cast(int)y)); }
auto opBinary(string op:"%", T)(T y) { return modint(my_mod(val, cast(int)y)); }
// int/modint, int%modint の挙動を変更
auto opBinaryRight(string op:"/", T:int)(T y) { return modint(my_div(cast(int)y, val)); }
auto opBinaryRight(string op:"%", T:int)(T y) { return modint(my_mod(cast(int)y, val)); }
// +-* なども、挙動変更後の型を返すように置き換え
auto opBinary(string op, T)(T y) { return modint(mixin("val"~op~"cast(int)y")); }
auto opBinaryRight(string op, T:int)(T y) { return modint(mixin("cast(int)y"~op~"val")); }
}
void main()
{
modint x = -10;
writeln(x / 3); // -4
writeln(x % 3); // 2
writeln(x*x*x % (1-x) > 0); // -1000 % 11 = 1 > 0 : true
}
こんな感じになります。詳しくはこちら:
http://dlang.org/phobos/std_typecons.html#Proxy
http://dlang.org/operatoroverloading.html
まず proper_div, proper_mod という名前で正しい挙動を定義し、任意の型で動くように変更することはできました。(型パラメータTに演算が入っていない場合は実行時エラーになるのでしょうか? コンパイルエラー出してくれるのですか?)
auto proper_div(T)(T x, T y)
{
T q = x / y;
if ((0 < y && x < q*y) || (y < 0 && q*y < x))
{
q -= 1;
}
return q;
}
auto proper_mod(T)(T x, T y)
{
return x - proper_div(x, y)*y;
}
上の方法で int を拡張したものを pint としていますが、proper(int) のような記法で任意の型へ変更を加えることはできるでしょうか。
また、少し話題が変わりますが、数値型のうち cent だけエラーになってしまいます。128ビット整数を使うには特別な操作が必要ですか?
質問ばかりですみません。
コンパイルエラーです。もうお試しになられたかとも思いますが、proper_div("string", "mojiretsu"); などとするとコンパイル時にひっかかります。
> proper(int) のような記法
できます。gistのコードでほぼOKです。class proper(T) ではなく struct proper(T) にするとうまく行くと思います。
D言語で解説した記事がとっさに思い出せなかったのでC#の記事ですが、classが参照型でstructが値型という違いがあります。http://ufcpp.net/study/csharp/oo_reference.html
class にする場合は proper!long(4) ではなく new proper!long(4) で値を作ることになります。
> 数値型のうち cent だけエラーになってしまいます。128ビット整数を使うには特別な操作が必要ですか?
残念なことに、centはキーワードだけ予約されていて、実装はまだされていません(^^;。現状、組み込みの整数型ではlongの64ビットが最大で、それ以上はstd.bigint.BigIntを使うことになります。
> bool[] is_prime = new bool[N];
がfalseで初期化されるので、その直後に
> is_prime[] = true;
などとtrueを突っ込む必要があると思います。