今年初登場の企画。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を。

概要

事の発端

予選

DAY 1

本戦

反省

大陸対抗トークライブ

休憩

フードコーナー

コネクションハント