読者です 読者をやめる 読者になる 読者になる

学習の栞

学びたいことと、学ぶべきことと、学べることの区別がついてない人間の進捗管理

Distributed Code Jam 2016 について

はじめに

Distributed Code Jam R1に参加して、環境構築とか環境構築とか辛かった人を散見したので記事を書くことにした。

Distributed Code Jam とは

Distributed Code Jam (DCJ) とは、Google Code Jam (GCJ) に併設された分散処理のコンテストです。ざっくり言うと、100並列で競技プログラミングをやるコンテスト。2016年はGCJのRound2進出者に参加権がありました。

環境について

普段の競技プログラミングとは異なるところもあるので、思いついたところのまとめ。Mac/C++で参加しました。

並列化用ライブラリ

MPIっぽい関数を実装したライブラリがコンテストの運営から配られます。コンテスタントはそれを使ってプログラムを実装します。基本型の送受信用キューへの追加/読み出しと、送受信用キューの内容の送受信程度でしょうか。ライブラリの詳しい仕様を把握しないまま書いたら書けてしまったので詳しい仕様は言えない。

言語

C++Javaの二択。

入出力仕様

入力は関数を呼んで取得する。問題ごとに入力用の関数が用意されていて、入力用関数の仕様は問題文中で与えられる。problem_ name.h というヘッダファイルに実装されているので、それをインクルードする必要がある。ヘッダファイルはソースと同じディレクトリの中に置いてね。sample-inputをくれるヘッダファイルは問題文の下のほうにあるリンクからダウンロードできました。答えの出力はどこか一つのノードが標準出力に吐けばよい。

環境構築

Distributed Guideに書かれてある。

Linux || Mac

LinuxMacがメイン環境の人は環境構築がしやすいから幸せだ。DCJ 用のテスト用ツールを Distributed Guide に書かれてあるリンクから落としてくる。.tar.bz になってるので、 コマンドライン

tar jxvf dcj.tar.bz

とかやって展開する。あとはGoをインストールして、

cd src/parunner/
go build
cp parunner ../../executable/

とやると環境構築おわり。

config.jsonにどのコンパイラを使うかとかを指定するようになってるので、「コンパイラみつかんねーよ」と怒られたりしたらconfig.jsonを書き換えるといいかもしれない。sample-configsの中にいくつか設定例があったので、自分で書き換える必要が出てくることはないかも。テストを行うには、Distributed Guide に書かれてあるコマンドを打てばよい。

problem=prblem_name
srcfile=${problem}.cpp
${DCJ_UNPACK_DIR}/dcj.sh build --source=$srcfile
problem=prblem_name
runnable=${problem}
${DCJ_UNPACK_DIR}/dcj.sh run --executable=./${runnable} --nodes=100 --output=all

とか書いてスクリプトにまとめとくと便利。

Windows

Cygwinで環境構築しようとしたら失敗した。辛い。READMEとか読んだら「MinGWでやれw」って書かれてたから、MinGWでやったら上手く行くんじゃないかな。

提出

提出はGCJとは異なりソースコードのみを提出する。例によってsmallとlargeのデータセットがある。smallを提出すると、コンテストサイト側でテストが行われ2分後に結果が分かる。提出後の2分間は結果も分からないし、再提出することもできない。largeはsmallが通った場合に提出でき、コンテスト終了まで何度でも再提出できる。largeの採点はコンテスト終了後に行われる。

practiceについて

DCJは本番前にGCJR2進出者を対象にしてDCJ前にオンラインで練習会が開かれる。今年の場合、練習会の日時・URLはメールで告知され、コンテストスケジュールには載ってなかった。事前練習を行いたいひとはこまめなメールの確認を。

問題難易度

極端に難しい問題は出なかった印象。R2進出者であれば、シングルノード版の解法を書くことにはまず困らない。samllはシングルノードでも解ける程度の制約、largeは並列化しないと無理ゲーな制約。という印象をうけた。Distributedと名がつくだけあり、シングルノードでも解ける制約のsmallの配点がものすごく低い。