2024-08-09

ICFPC 2024 参加記

2024年6月28日から7月1日にかけて開催された ICFPC 2024 に参加した。

icfpcontest2024.github.io

チーム

例年通り Gon The Fox (総計7名) で出場した。当チームは2019年頃からメンバーを多少変えつつ参加しており、私自身は2020年から毎年参加している。

問題概要

ICFP Language という関数型言語の仕様が与えられる。 ICFP の式を送ると ICFP の式が返ってくるような HTTP endpoint が提供されており、それを使って以下の5カテゴリに分かれた問題を解く。

hello
- ICFP を使用した基礎的な通信を行う
lambdaman
- 2次元グリッド上の全空きマスを通る経路を求める
spaceship
- 加速・減速できる宇宙船を使った2次元 TSP
3d
- 競プロ (algorithm) のような問題を、 Befunge に時間遡行を足したような言語で解く
efficiency
- 与えられた ICFP 式を評価した結果の整数を求める

実際には最初からすべての問題が公開されている訳ではなく、ある程度提出が進むと新たなカテゴリが解放される。

コンテスト参加記録

コンテスト開始前から終了までに取り組んだ様子を記録しておく。

開始前

チームで使う Discord server と GitHub repository を作成した。例年弊チームでは特に作戦などを決めておらず、各メンバーが個別のディレクトリをもって自由な言語でプログラムを書いていたが、今年はせめて Rust だけでもコードベースを統一しようと思い ~~職権を濫用し~~ repository に Cargo の設定ファイルと Rust の CI をセットアップしておいた。

1日目

ICFP Language の仕様が公開された。まず文字列のやり取りができないと問題文すら取得できないので、文字列の encode / decode 関数、次いで shell (ユーザーが入力した文字列を encode して POST し、レスポンスを decode して表示するプログラム) を実装した。

この時点では lambdaman と spaceship が解放されていた。問題の入力はいずれも文字列なのだが、サーバーから取得できるのは ICFP の式である。式が単に文字列リテラルである場合は decode すれば良いが、「評価すると文字列になるプログラム」である場合もあった。そのため (比較的 interpreter 実装経験のあった) 私が ICFP interpreter を実装することになった。

ICFP Language 概要

ICFP Language は簡単に言うと型無し Lambda 計算であり、以下のような特徴を持つ。

データ型は boolean、多倍長整数、文字列の3種類
組み込みの単項演算子と二項演算子、IF 文を持つ
具象構文はスペース区切りのポーランド記法

interpreter 実装

Rust で call-by-need 評価戦略の interpreter を実装しようとした (後から考えれば、call-by-need はおそらく過剰であった)。数時間粘ったが再帰 (Y combinator) が動かず、一旦就寝した。

2日目

起床後改めて interpreter に取り組み、昼過ぎに再帰が動くようになった。ほとんどの問題は decode できるようになったが、実行すると再帰が深く stack overflow になる問題が1つだけ存在した。これについては ICFP のプログラムを読解し、ループを使った Rust のプログラムに書き換えることで decode することができた。

チームメイトが lambdaman と spaceship および解放された 3d のソルバーを着々と実装していたのでしばし休憩を取る。

夕方頃に efficiency が解放され、言語の問題のようだったので取り組むことにする。

efficiency

概要

評価すると整数になるような ICFP Language のプログラムが与えられる。評価結果の整数を求めて提出する。判定は正答と誤答だけで、最適化などの目標は無い。全13問。

やったこと

問題1は入力を intrepreter に与えるだけで解答が得られたが、それ以外の問題はすべて stack overflow になった。 interpreter の実装ついでに ICFP を Lisp のような言語に変換するプログラムを書いていたので、それを使って他の問題を解読していく。

問題2・3

無駄な再帰と加減乗除があるだけなので、再帰を除いて計算する。もしかして interpreter に定数畳み込みなどを実装しないといけないのか？という疑念に駆られる。

問題4

再帰で40番目のフィボナッチ数を求めるプログラムなので、フィボナッチ数を検索して提出した。

問題5

以下の条件を全て満たす整数 x を線形探索で求めるプログラムになっている。

x > 1000000
x は素数
x+1 は2の冪乗

(定義は異なるが) メルセンヌ素数を調べて提出する。

このあたりで機械的な最適化では解けないことを悟り、全て人力で解読する方針を固めた。

問題6

問題5と類似した構造で、以下の条件を満たす x を求める。

x > 30
x 番目のフィボナッチ数は素数

条件を Discord に書いたらチームメイトが答えを求めてくれた。

問題12

2重の再帰を行っていて複雑だが、あまり典型的な処理には見えない。愚直に Rust に移植して解こうとする。素朴な実装では再帰が多く実行が終了しないが、再帰の引数がほとんど変化しないことに着目して書き換えると解が得られる。

問題13

再帰で長い文字列を作ってその長さを求める。チームメイトが解いた。

問題7・8・9・10・11

急激にプログラムが大きくなり、変数も増えるが、類似した構造の繰り返しになっている。多数の条件式が論理積で接続されているので、SATっぽいという直観を得る。

改めて問題7・8を読むと、SAT の解を二進数で encode したものを求めるプログラムであることが分かる。一方の9・10・11は v11 ～ v99 の変数と v11 != v12 のような制約が多数あり、数独の解を九進数で encode したものを求めている。

解けそうなことが分かったところで、上記の考察を Discord に書き残して就寝した。寝ている間にチームメイトが全て解を求めてくれて efficiency の完答を達成した。

3日目

相対的に順位の低かった lambdaman に取り組むことにした。

lambdaman 問題概要

2次元のグリッドが与えられる。各マスは壁 (#)、空きマス (.)、スタート地点 (L) のいずれかである。プレイヤーをスタート地点から上下左右に移動させ、全ての空きマスを通過するような経路を求めよ。

提出

「U R D L からなる文字列」に評価されるような ICFP 式を提出する。 ICFP 式の長さ (バイト長) が短いほど上位となる。

lambdaman 提出状況

この時点でチームとして提出していた解答は大きく分けて以下の3種類だった。

経路の文字列をそのままリテラルとして埋め込む
経路の文字列を圧縮する (整数エンコード・ランレングス圧縮など)
ICFP 式を手で書く

1 と 2 についてはソルバーで短い経路を探すことが解答の短さにつながるが、この時点からソルバーに関わるのは難しそうなので 3 で解けそうな問題に取り組むことにした。

lambdaman の問題の中には規則的なグリッドのものがあり、例えば問題6 では R を199個連結した文字列で正答することができる。

また、競技中は、問題ごとに順位と全チーム間のベストスコアが閲覧できるようになっていた。

lambdaman ゴルフ

規則的な経路で解けそうな問題6・8・9に取り組んだ。当初は何らかの言語から ICFP へのトランスパイラを実装しようかと思ったが、efficiency の解読などをしている間に ICFP を普通に読み書きできるようになっていたので直接 ICFP を手書きすることにした (とは言え文字列や整数のエンコードは辛かったので途中で簡単なアセンブラだけは実装した)。

問題6

まずは前述の問題6を 92 bytes から 79 bytes まで削減したが、1位の 73 bytes まで削減する見通しが立たず苦戦する。するとここで、問題文に「壁に当たるような移動は無視される」という旨の記述があることに気付いた。 3日目に至るまで「壁に当たるような移動をしてはいけない」という誤解をしていたのは本当に致命的だったのだが、ともあれ問題6については R を216個連結した文字列を生成するコードで1位タイを獲得した。

問題9

問題9は開けた長方形のグリッドであり、 RR...RRDLL...LLD を繰り返して蛇腹状に降りていくことで正答できる。 114 bytes まで短縮して限界を感じていたところ、チームメイトが 110 bytes の解を提出し2位タイを獲得した。

問題8

問題8は螺旋状の細い道になっており、 DD...DDLL...LLUU...UURR...RR を繰り返すことで正答できる。色々試した結果、 DLDL...DLDLURUR...URUR を繰り返すと、処理する文字列が4種類 (D, L, U, R) から2種類 (DL, UR) に削減されてコードを単純化することができた。この方法で9位タイを獲得した。

その他の問題

壁にぶつかっても良いことを利用して、「何らかのパターンを十分な回数繰り返す」方法で小さな問題が解けるのではないかと考えた。しかしながら、試した範囲では同じところでループに陥ってしまい、正答には至らなかった。

lambdaman 全体を通した短縮テクニックとしては Y combinator による再帰や church 数による繰り返しを試みたが、結局文字列を繰り返すだけならダブリングのような手法が最も効率的であった。この方法では、例えば受け取った文字列を3回繰り返す関数を f として、 f(f(f(f(s)))) と呼び出すことで s を81回連結した文字列を得ることができる。より複雑な関数を使うと効率的に解ける問題もあったとは思うが、この辺りでコンテスト終了時刻になってしまった。

振り返り

個人として

言語処理系実装

24時間以内に処理系を実装できたので ICFPC 2020 の時よりはある程度成長したと実感したが、call-by-need に囚われなければもう少し速く実装は可能だったと思う。 Rust の module を適切に分けて設計した結果、チームメイトも処理系の一部 (演算子のパースなど) を実装してくれたり、提出ツールにもコードを再利用できたりした点は良かった。

efficiency

コンテスト内に完答できたので満足している。問題も取り組んだ中で一番面白かった。強いて言えば、処理系に最適化を実装するか悩んだ時間が無駄だったので、問題をよく分析することを優先すべきだった。

lambdaman

コードゴルフは普段そんなにやらない (特に関数型言語ではやったことない) が楽しかった。いつの間にか ICFP を普通に書けるようになっていたことは自分でも驚いたが、最終的にはもっとコードを書きたかったという感想を抱くほどであった。

終盤までルールを誤解していたことが本当に悔やまれる。

チームとして

3d のうちの1問を除いて全ての問題で正答を得た。

最終順位 16位

hello 1位タイ
lambdaman 25位
spaceship 10位
3d 22位
efficiency 1位タイ

ということで私が参加した中では最高順位を獲得できた。 spaceship や 3d についてはほぼ関与しなかったのだが、それぞれビジュアライザなどが実装されていて優秀だった。

チームワークの面でも今までで一番連携が取れていたように感じた (コンテスト開始前の下準備が功を奏したかもしれない)。来年以降も是非とも出場したい。

2020-04-02

Crane (POJ 2991) をセグ木コピペで解く

競技プログラミングセグメント木モノイド群

概要

本記事では、 Crane (POJ 2991) を、モノイドの和を計算する通常のセグメント木を使うだけで解く解法を解説する。

事の発端

蟻本を読む某氏「この問題はただセグメント木貼るだけでは解けなそう」
私「なるほど…いや良い感じのモノイド乗せたら出来ないかな…」

私「出来たわ」

2017-12-06

CODE FESTIVAL 2017 参加記

競技プログラミング

CODE FESTIVALは昨年に引き続き2回目の参加である。昨年は特に何も書かなかったが今年は最後の参加になるはずなので記録しておこうと思う。

予選

CODE FESTIVAL 2017 qual A - AtCoder

予選Aで大変調子が良く、4完、116th、レート1847→1979という結果で本戦進出を決めた。昨年は定員が倍以上だったのに予選Cのギリギリで通過だったので素直に嬉しかった。

DAY 1

本戦

CODE FESTIVAL 2017 Final - AtCoder

何だかんだでレートが1924まで下がっていたが、パーカー獲得と黄コーダー昇格を本戦の目標とした。しかし結果はA、B、Cの3完、パーカーは獲得したがレートは据え置きとなった。あまり満足はしていないが、レートが実力相応であることが分かった。

成績: 1200点 (40m12s) 81st Performance = 1924

反省

D問題で、「 $O(N^{2})$ のDPっぽい」「 $H_i+P_i$ の小さい順が良さそう」という直感を得たが、それらが結びつかず解法に至らなかった。もう少し整理して考察を深めるべきだった。
F問題が解けそうな気がしてこだわり過ぎてしまった。

大陸対抗トークライブ

聞き流しながら本戦のD問題を通した。

休憩

フードコーナー

スケジュール表に書かれた「お寿司、ピザ、お肉と「プロコンメシ」3種の神器が勢揃い。」の意味はよく分からなかったがいずれも美味しかった。あまり焦らなくても確保出来たのも良かった。

コネクションハント

今年初登場の企画。1つの質問を決め、他の参加者から回答を集める。私は「好きなプログラミング関連の本は？」という質問を20人に訊いた。最頻値は予想通り蟻本で5名。次点はアルゴリズムイントロダクション(CLRS)の3名であった。その他知っている本も知らない本も多く集まってなかなか面白かった。他の参加者に話しかけるきっかけを作るという意味でも良い企画だったと思う。ただし人の顔と名前を覚えるのが致命的に苦手なので全く覚えられなかった。 20人集めた賞品としてタンブラーを獲得した。

エキシビジョンマッチ

正直付いていけないので本戦のE問題、F問題を通した。海外勢が強かった。

チーム顔合わせ

DAY 2のチームリレーのチーム分けが発表され、顔合わせと自己紹介を行った。私はksun48、mjhun、satashun、pachicobue、PIandS、wafrelka、gazelle、pekempey、Juyiと共にTeam Bに割り振られた。

DAY 2

少し会場に早く着きすぎた。会場入りFirst Acceptを得た。

暇だったのでテンプレートテンプレート引数について調べて新しいコードテンプレートを作った。

template <class T, template <class, class> class C, class charT = char>
void vdump(const C<T, allocator<T>> &v, const charT* delimiter = ", ",
           ostream &stream = cout) {
  copy(v.begin(), v.end(), ostream_iterator<T>(stream, delimiter));
  stream << endl;
}

トーナメント戦

本戦順位の近い人同士で3ラウンドの勝ち抜き戦を行う。私はGroup5に振り分けられた。 1ラウンド30分～40分で2問、部分点の多い問題が出題される。昨年はRound1で0点で敗退したので、今年は積極的に部分点を取りに行く方針で臨んだ。

Round1

CODE FESTIVAL 2017 Elimination Tournament Round 1 (Parallel) - AtCoder

とりあえず両方の問題を読み、C問題の全探索を投げることにした。15分かかってしまったが200点を獲得。その後はD問題の部分点を取りに行こうとしたが実装が間に合わなかった。

結果として、200点 (15m13s)、18人中6位でRound2に進出した。

Round2

CODE FESTIVAL 2017 Elimination Tournament Round 2 (Parallel) - AtCoder

同じく両方の問題を読み、A問題の部分点を取りに行くことにした。まず第一の部分点(100点)を取ったが、直後に同じ方法で第二の部分点(100点)を取れることに気が付いて書き直した。ここはもう少し考えて最初からまとめて解くべきであった。その後は一度B問題を考えたが、すぐに実装出来ない気がしたので再び問題Aを考えた。第三の部分点の解法を提出したつもりだったが通らず、そのまま終了してしまった。

結果、200点 (19:23)、10人中7位で敗退した。結果論だがB問題を解きに行った方が良かったかもしれない。

Round3 (open)

CODE FESTIVAL 2017 Elimination Tournament Round 3 (Parallel) - AtCoder

一応問題は読んだが主にRound1、Round2の問題について考えていた。

総括

積極的に部分点を取りに行くという戦略はまあまあ上手く行ったと思う。あとは単純に考察力や実装の速度が足りなかった。

昼食

三種類の弁当の中からちらし寿司を選んだ。美味しかった。

三宅陽一郎氏トークライブ

CODE FES 2017 講演資料

CODE FES 2017 講演資料（後篇）

SQUARE ENIXのAI Researcherである三宅陽一郎氏の講演。ゲームにおけるAIの構造が分かりやすく解説されていて面白かった。

チーム対抗早解きリレー

Code Festival Team Relay (Parallel) - AtCoder

開始前

昨年は自分の担当が解けずに足を引っ張ってしまったので、とりあえず自分の問題を解くことを目標とした。

私たちのチームはまずすべての問題を本戦の順位に従って1人1問割り当て、必要があれば交換するという方針を取った。私はチーム内で8番目だったのでC問題を解くことになった。

また、計算用紙を1枚使って、各問題の進捗状況(解法が分かった、デバッグ中、Accepted等)を管理することになった。

前半

開始直後、全員にそれぞれの担当の問題を配った…が、封筒に英語の問題文が入っていなかった。少々焦ったが他のチームにも配られていなかったようなので、海外勢はチームPCで問題文を読むことになった。

私は予定通りC問題を読んで、すぐに解法を思い付いた。 A問題とB問題をJuyiとpekempeiがそれぞれコーディングしに行っていた(と思う)ので、紙の上で計算し、その後コーディングエリアに向かった。 1度目の提出が13m50sだったが、色々と間違えて結局3回WAを出した。 3回目の後はwafrelkaに協力してデバッグしてもらい、4回目の提出(32m20s)でようやくACした。

余談だが、3回目の提出の時、Windowsキー+数字でアプリケーションを切り替えようとしても新しいウィンドウが開く、カーソルの移動が範囲選択になるなどの現象に見舞われた。焦ってChrome上でEscを押したらChromeのタスクマネージャーが開いて更に焦ったが、Shiftキーが誤反応していることに思い至り、Shiftキーを連打したら解消された。

後半

C問題をACした頃にはほとんどの問題が解法が分かっているかデバッグ中になっており、自分に手が出せる問題が無さそうであった。一応デバッグ中の問題を読んだりしながら、ゴミの回収などの雑用をしつつ、コーディングエリアが空かないようにキューの管理に努めた。

これも完全に余談だが、隣のTeam Aにふと目を向けたらtouristがコーディングエリアで「お手上げ」のポーズを取るという貴重な光景を目撃した。

チームとしては最終的にmjhunが残ったH問題をACし、84m00sで全完、4位となった。徐々にチームの士気と一体感が高まっていくのを感じ、とても楽しかった。

反省

WAの原因 * 不等号の向きを間違えた * 二分探索の範囲の更新を間違えた * 二分探索の範囲の初期値が狭すぎた

1つ目はともかく、2つ目と3つ目は二分探索で自分がやりがちなミスなので十分に気を付けるべきだった。

それぞれのデバッグのコーディング時間はそんなに長くなかったと思うが、早く解こうとしてWAを出して結果的にコーディングスペースを占有してしまった。

良かった点

時間はかかったがちゃんと自分の担当問題をAC出来た。後半雑用しか出来なかったのは実力上仕方ない部分が大きいと思うが、雑用としてはそれなりにいい仕事が出来たのではないかと思う。

総括

とても楽しかった上、勉強になった。しかし、問題が解けなくて悔しい思いをしたので、今後も時間の許す限り精進を続けたいと思う。

関係者の皆様、ありがとうございました。

2016-12-19

競技プログラマーのためのOMake入門

競技プログラミング OMake

はじめに

本記事はCompetitive Programming （その2） Advent Calendar 2016の19日目の記事です。

www.adventar.org

この記事では、プログラムのコンパイルを自動化するツール、OMakeの使用方法を、競技プログラミングの実例に沿って簡単に解説する。

本記事の対象読者

(主にUNIX系OSで)コマンドラインを使ってプログラムをコンパイルしている人
- Windowsでも利用可能なようだが、インストールが大変
特に、OMakeに全く触れたことのない人

OMakeとは

OMakeとは、プログラムを簡単にビルドするためのツールの一種である。同様のツールとしてはMakeが有名だが、OMakeは基本的にこれを更に発展させたものとなっている。読み方はおそらく「オマケ」ではなく「オーメイク」だと思われる。

OMake プロジェクトページ

1. ガイド — OMakeマニュアル日本語訳

何ができるか

競技プログラミングへの応用例としては以下のような使い方が考えられる。

5行～20行程度の設定を書いておけば、omakeを実行するだけで必要なプログラムが全てコンパイルされる。
omake -Pをバックグラウンドで実行しておくと、ソースコードが変更された時に自動で再コンパイルされる(継続ビルド)。
新規にディレクトリを作成した時に、設定ファイルのコピーなどが必要ない。

OMakeのインストール

UNIX系OSでは、継続ビルドをする際にfamまたはgaminが必要になる。famは古いのでgaminの方が良いとのこと。継続ビルドを使わない場合はインストールの必要は無い。

Ubuntuの場合

$ sudo apt install omake gamin

Bash on Ubuntu on Windows (Windows Subsystem for Linux) においても同様の方法でインストールできるが、Build 14393ではomake -Pが動作しなかった。 Insider PreviewでBuild 14986を入れたら動作した。おそらくBuild 14926以降が必要となる。

OS Xの場合(動作未確認)

筆者はOS Xの環境を持っていないが、OPAMを利用するのが良いようである。

How to install omake on OS X · GitHub

Windowsの場合(動作未確認)

ソースコードをプロジェクトページからダウンロードし、INSTALLに書いてある内容に従ってビルドする。 OCamlをインストールしておく必要がある。

もしくはWSL(上記)、CygwinやMinGWを利用する。

OMakeの基礎知識

これらを踏まえておくと以下の記事が理解しやすいと思われる。

実行の流れ

omakeコマンドが呼ばれた場合、原則として以下の順序で依存関係の解析・ビルドが行われる。

OMakerootが存在するディレクトリ(ルートディレクトリと呼ぶ)まで親ディレクトリを辿る。
(通常OMakerootには.SUBDIRS: .が書かれているので)ルートディレクトリのOMakefileを読み、変数やルールを定義する。
.SUBDIRS:の後に記述されているディレクトリに移動し、OMakefileを読む。もしくは、ディレクトリ名の後に記述されているルールを直接読む。
これを再帰的に行う。

参考までにMakeにおける実行の流れを以下に示す。

makeが実行された(もしくはオプションで指定された)ディレクトリのMakefileを読む。
ルールに従ってコマンドを実行する。

すなわち、Makeの場合は他のディレクトリのMakefileを利用する場合は明示的にmakeコマンドを実行するルールを記述する必要がある。

主な構文

基本的にはMakeのものと類似している。シンタックスハイライトはMakeと同じものを使えば十分だと思われる。

インデントが重要な言語である。インデントのレベルによってコードブロックが判別される。
- インデントにはスペースではなく水平タブを使う必要がある。
- 本記事ではタブがスペースとして表示されてしまっているので注意。
#から行末までがコメントとみなされる。
変数定義は変数名 = 値、値の更新は変数名 += 値で行う。
変数の値は$(変数名)で参照する。
関数呼び出しは$(関数名引数1, 引数2)で行う。

コマンドラインオプション

コマンドラインオプションはomake --helpで表示することができる。もしくはマニュアルを読む。

実例

動作確認はUbuntu 16.04 LTS、OMake 0.9.8.5にて行っている。

以下のような構造のディレクトリにおいてOMakeを利用することを考える。言語はC++を例にしているが、コマンドによってコンパイルを行う言語なら利用可能である。コンパイラはg++を使用する。また、コンパイルオプションはそれぞれのジャッジシステムに合わせて、aojとatcoderでは-std=gnu++1yを、pojでは-std=c++98を使用することにする。

contest/
├─ aoj/
│   ├─ 0001.cpp
│   ├─ 0002.cpp
│   └─ ...
├─ poj/
│   ├─ 0001.cpp
│   ├─ 0002.cpp
│   └─ ...
└─ atcoder/
     ├─ abc/
     │   ├─ 001/
     │   │   ├─ a.cpp
     │   │   ├─ b.cpp
     │   │   └─ ...
     │   ├─ 002/
     │   │   ├─ a.cpp
     │   │   └─ ...
     │   └─ ...
     └─ arc/
          ├─ 001/
          │   ├─ c.cpp
          │   └─ ...
          ├─ 002/
          │   ├─ c.cpp
          │   └─ ...
          └─ ...

atcoder/以下においては、新たなコンテストが開催されるなどのタイミングでabc/xxx/のようなディレクトリが作られることを想定している。

この中の任意のディレクトリにおいて、omakeを実行すると現在のディレクトリ以下のプログラムが全てコンパイルされることを目標とする。

テンプレートの導入

プロジェクトにおいて最初にOMakeを導入する際には、プロジェクトのルート(この場合はcontest/)において

$ omake --install

を実行する。これによって、 contest/直下にOMakerootとOMakefileの2つのファイルのテンプレートが作成される。 OMakerootはほとんどの場合編集する必要がなく、今回も編集しない。 OMakefileにはC言語及びOCamlのプログラムをビルドするための設定がコメントアウトされた状態で書かれているが、今回はほぼ使用しないので中身は全て消して構わない。

`aoj/` `poj/`の設定

まずはこれら2つのディレクトリでビルドを行えるように設定を行う。

初めに、これらのディレクトリがプロジェクトの一部であるということをcontest/OMakefileに記述する。また、omake all、omake cleanを実行できるようにするためphonyターゲットを指定する。更に、引数無しでomakeが実行された際にはallをターゲットとして実行するようにする。

# contest/OMakefile

.PHONY: all clean

.DEFAULT: all

.SUBDIRS: aoj poj

次にaoj/OMakefile及びpoj/OMakefileに実際にビルドするためのルールを記述する。内容は主に

どのファイルを作るか
そのファイルをどのようなコマンドで作るか

の2点である。この場合、作成するファイルは「ディレクトリ内の全てのソースコードをそれぞれコンパイルしたもの」である。 (競技プログラミング用でない)通常のプロジェクトにおいてはターゲットと依存関係はあらかじめある程度決まっているが、今回の例では新たなターゲットが動的に作られるという点でこれと異なる。そのため、ワイルドカードを用いてターゲットのリストを生成する。

# contest/aoj/OMakefile

# コンパイラとコンパイルオプションを変数に設定
CXX = g++
CXXFLAGS = -O2 -Wall -std=gnu++1y

# srcs変数に全てのソースコード名を代入
srcs = $(glob *.cpp)

# srcsの内容それぞれの拡張子を取り除き、生成するファイル名をtargs変数に代入
targs = $(rootname $(srcs))

# コンパイルのルールを記述(後述)
$(targs): %: %.cpp
    $(CXX) $(CXXFLAGS) -o $@ $<

# omake all でtargsに含まれるファイルを生成する
all: $(targs)

# omake clean で生成されるファイルを削除する
clean:
    rm -f $(targs)

.DEFAULT: all

globはワイルドカードでマッチするファイル名を取得する関数。 rootnameは引数から拡張子を取り除いた文字列を返す関数。ターゲットを別の拡張子のついたファイルにしたい場合はreplacesuffixesを使うと良い。

このファイルの中で最も重要なのは

$(targs): %: %.cpp
    $(CXX) $(CXXFLAGS) -o $@ $<

の部分である。

このうち、1行目では%はワイルドカードを表しており、「targsに含まれるファイルのうち、%にマッチするファイルは%.cppというファイルから以下のコマンドを使って生成する」という意味になる。このルールの詳細はこちら。

2行目では具体的なコマンドを記述している。$(CXX)と$(CXXFLAGS)は定義された変数の値がそのまま展開される。 $@と$<はルール内で自動的に設定される特殊変数であり、それぞれ「ターゲットの名前」と「最初の依存ファイル」を表す。

C++以外の言語を使用する場合は、srcsとtargsの定義とこの2行を変更すれば良い。

poj/OMakefileもコンパイルオプション以外は同一である。

# contest/poj/OMakefile

CXX = g++
CXXFLAGS = -O2 -Wall -std=c++98

srcs = $(glob *.cpp)
targs = $(rootname $(srcs))

$(targs): %: %.cpp
    $(CXX) $(CXXFLAGS) -o $@ $<

all: $(targs)

.DEFAULT: all

clean:
    rm -f $(targs)

設定の集約

これでaoj/とpoj/についてはコンパイルができるようになったはずである。ここまでのことはMakeでもほぼ同じ記述でできる。しかし、ほとんど同じ設定を2か所に記述するのはプログラマーとしては避けたいものである。幸いにもOMakeではこの問題を簡単に解決できる。

設定内容を以下のようにcontest/OMakefileに移す。

# contest/OMakefile

.PHONY: all clean

.DEFAULT: all

CXXFLAGS = -O2 -Wall

.SUBDIRS: aoj poj
    # BuildInfo.omの内容を取り込む
    include BuildInfo
    targs = $(rootname $(glob *.cpp))
    $(targs): %: %.cpp
        $(CXX) $(CXXFLAGS) -o $@ $<

    all: $(targs)

    clean:
        rm -f $(targs)

    .DEFAULT: all

.SUBDIRS:の次の行以降にインデントしてルールを記述すると、サブディレクトリのOMakefileにルールを記述するのと同じ効果が得られる (.SUBDIRSの内容を並列化させる)。従って、ここで複数のディレクトリを指定しておけば複数のサブディレクトリの設定を1か所にまとめることができる。同時に、コンパイルオプションの設定も共通する部分は外に出している。

aoj/OMakefileとpoj/OMakefileは使用しないので削除して良い。代わりに、それぞれのディレクトリにBuildInfo.omというファイルを作成して固有の設定を記述し、contest/OMakefileから取り込む。 BuildInfoの部分は別の名前でも良いが、その場合はincludeの引数もそれに合わせる。

# contest/aoj/BuildInfo.om

CXXFLAGS += -std=gnu++1y

# contest/poj/BuildInfo.om

CXXFLAGS += -std=c++98

こうすることで設定がまとまり、設定の変更などもしやすくなった。

`atcoder/` の設定

atcoder/以下の設定に移る。こちらはサブディレクトリが新規に作られるという点で前の2つと異なる。そのため、Makeを使用する場合は通常ディレクトリを作る度にMakefileをコピーする必要があるが、 OMakeではそのようなことをせずに解決できる。

まず、atcoder/をプロジェクトに入れる。

# contest/OMakefile

.PHONY: all clean

.DEFAULT: all

CXXFLAGS = -O2 -Wall

.SUBDIRS: aoj poj
    include BuildInfo
    targs = $(rootname $(glob *.cpp))
    $(targs): %: %.cpp
        $(CXX) $(CXXFLAGS) -o $@ $<

    all: $(targs)

    clean:
        rm -f $(targs)

    .DEFAULT: all

# 追加
.SUBDIRS: atcoder

続いて、以下の内容でatcoder/OMakefileを作成する。要点は、先ほどaoj/とpoj/の設定を共通する親ディレクトリにまとめたのと同様に、 abc/001/、abc/002/などのディレクトリをまとめ、更にabc/とarc/の設定を一つにまとめて記述することである。また、ワイルドカードを用いることで、これらのディレクトリを明示的に列挙せずに指定することができる。

# contest/atcoder/OMakefile

CXXFLAGS += -std=gnu++1y

.SUBDIRS: $(glob D, *)
    .SUBDIRS: $(glob D, *)
        targs = $(rootname $(glob *.cpp))
        $(targs): %: %.cpp
            $(CXX) $(CXXFLAGS) -o $@ $<

        all: $(targs)

        clean:
            rm -f $(targs)

        .DEFAULT: all

    .DEFAULT: all

このコードでは、atcoder/*/*/にマッチするようなディレクトリ全てをサブディレクトリとして、そのディレクトリにおけるルールを定義している。 globにDオプションを指定するとディレクトリのみにマッチすることを利用する。各ディレクトリ内での設定は先ほどと同様である。

この設定によって、abc/やarc/以下へのディレクトリの追加に加え、例えばatcoder/agc/などのディレクトリの追加にも変更無しで対応することができる。

なお、

.SUBDIRS: $(glob D, *)
    .SUBDIRS: $(glob D, *)

の代わりに

.SUBDIRS: $(glob D, */*)

と書いても良さそうに思えるが、そうするとabc/やarc/がプロジェクト外となり、これらのディレクトリでomakeを実行できなくなってしまう。

まとめ

OMakeではMakeと比べてディレクトリ間の依存関係の記述に優れており、これを利用することで似た構造の複数のディレクトリのビルド設定を一括して行うことができる。また、-Pオプションを使用することでコマンドを実行する手間を省くこともでき、一刻を争うプログラミングコンテストにおいて有利に働く…かもしれない。

おまけ

OMakeにはここで紹介した以外にも

oshという対話的実行環境がついている
クラスがあり、オブジェクト指向プログラミングができる

などの変態強力な機能がある。興味があったら活用してみてほしい。 (筆者はそこまでは触れていない)

それでは良いOMake lifeを。

チーム

問題概要

コンテスト参加記録

開始前

1日目

ICFP Language 概要

interpreter 実装

2日目

efficiency

概要

やったこと

問題2・3

問題4

問題5

問題6

問題12

問題13

問題7・8・9・10・11

3日目

lambdaman 問題概要

提出

lambdaman 提出状況

lambdaman ゴルフ

問題6

問題9

問題8

その他の問題

振り返り

個人として

言語処理系実装

efficiency

lambdaman

チームとして

概要

事の発端

予選

DAY 1

本戦

反省

大陸対抗トークライブ

休憩

フードコーナー

コネクションハント

エキシビジョンマッチ

チーム顔合わせ

DAY 2

トーナメント戦

Round1

Round2

Round3 (open)

総括

昼食

三宅陽一郎氏トークライブ

チーム対抗早解きリレー

開始前

前半

後半

反省

良かった点

総括

はじめに

本記事の対象読者

OMakeとは

何ができるか

OMakeのインストール

Ubuntuの場合

OS Xの場合(動作未確認)

Windowsの場合(動作未確認)

OMakeの基礎知識

実行の流れ

主な構文

コマンドラインオプション

実例

テンプレートの導入

aoj/ poj/の設定

設定の集約

atcoder/ の設定

まとめ

おまけ

`aoj/` `poj/`の設定

`atcoder/` の設定