「ふつうのLinuxプログラミング 第2版」を読んだ

システムコールファイルシステムについての知識が全くなかったので夏休みに読みました。

以下,雑な読書メモと追加情報です。

GCCのバージョン番号

gcc -v でもバージョン番号らしき表示はされるのですが,明らかに --verbose 的な出力だったので,不便だなぁとは思っていました。

gccコマンドラインのオプション引数の書式が無法地帯だった時代を引きずっているようで,こういうのがいくつかあります。

Unix domain socket

p.41 の記述です。リバースプロキシとアプリケーションサーバーをUnix domain socketでつなぐのをISUCONで初手でやっているので気になりました。追加調査をしたいですね。

ディレクトリの実行権限

答えを知らない人はここを読みましょう。

unix.stackexchange.com

askubuntu.com

superuser.com

本で指摘されなかったら永遠に+xの意味を分かっていなかったかもしれません。

バッファリングモード

std::endl は毎回 flush() が呼ばれてしまうので \n を使ったほうが速い」みたいな話がありましたが,ちゃんと計測し直したほうが良いかもしれません。

stdio

open/close で fd を使った操作をしていると「じゃあFILEって何だ…?」という疑問が湧いてくるのですが,その答えが載っていて助かりました。

とはいえ,普段の操作では fopen() からの fileno() で fd を取得するほうが安全かもしれません。

getc/putc はマクロで実装されていて fgetc/fpuc は関数で実装されているという違いがあるそうです。

Filesystem Hierarchy Standard

どういうファイルはどの場所に置けばよいかがわかりやすく書かれていてよいです。

「shareって何を共有しているんだろう…?」というのは長年の謎でした。

ハードリンク

superuser.com

ハードリンクを使うことがほとんど無いので役に立つかはわかりませんが…

シンボリックリンク

シンボリックリンクはパス(つまりシンボル)だけを持っているリンクなので,存在しないパスへのリンクを作ることもできるし,指しているファイルやディレクトリが消えても残り続ける。

実行ファイル

稀に gcc -S でアセンブリを見ることがあるのですが,「.text ってなんだろう… 実行される処理が書いてあるっぽいのにな…」 とずっと思っていました。

いつか使うことがあるかもしれません。

fork

よく知らずに使っていました。

dup/dup2

signal

これは覚えられる気がしないです。

credential

必要になったことが今まで無かったのでよくわかりませんでした。

ネットワーク

manかどこかに書かれているはずなんだけどな〜 と思っていたのですが,まさかetcに置いてあるとは…

所有しているコンテストTシャツの紹介

実家に帰省したら,コンテストTシャツを整理するように言われたので,ついでに写真に撮って整理しておくことにしました。

SuperCon 2011

Supercomputing Contest 2011 - Supercomputing Programing Contest Official Site

f:id:kujira16:20180812110721j:plain

f:id:kujira16:20180812110803j:plain

初めて参加したオンサイトのコンテストだったので思い出深いです。

ACM-ICPC 2013 Asia Aizu Regional

kujira16.hateblo.jp

kujira16.hateblo.jp

kujira16.hateblo.jp

f:id:kujira16:20180812112143j:plain

f:id:kujira16:20180812112206j:plain

f:id:kujira16:20180812112229j:plain

f:id:kujira16:20180812112258j:plain

f:id:kujira16:20180812112330j:plain

初めて国内予選を突破したICPCだったので思い入れがあります。

THE INVISIBLE GAMEとはいったいなんだったのか,今でもよく分かってないです(なにか元ネタがあるのでしょうか…?)

Recruit Programming Contest

kujira16.hateblo.jp

weekly.ascii.jp

CODE FESTIVAL の前身といえるコンテスト。

f:id:kujira16:20180812111026j:plain

青コーダーなのに海外に行かせてもらってありがとうございます!!

ACM-ICPC 2014 Asia Tokyo Regional

kujira16.hateblo.jp

f:id:kujira16:20180812112423j:plain

f:id:kujira16:20180812112437j:plain

f:id:kujira16:20180812112516j:plain

f:id:kujira16:20180812112535j:plain

2回目のICPCアジア地区予選。TopCoderのレーティング的には,このときが一番強かったっぽい…?

CODE FESTIVAL 2014

kujira16.hateblo.jp

f:id:kujira16:20180812111219j:plain

とにかくすごかったです(小学生並みの感想)

立命合宿2015

f:id:kujira16:20180812111425j:plain

f:id:kujira16:20180812111442j:plain

うん…

CODE FESTIVAL 2015

f:id:kujira16:20180812111721j:plain

f:id:kujira16:20180812111737j:plain

f:id:kujira16:20180812111850j:plain

f:id:kujira16:20180812111907j:plain

f:id:kujira16:20180812111328j:plain

Tシャツのほうは企業ロゴも入っていないので普通に着れますね。

JAGのおしごと!

ICPC国内予選お疲れ様でした!アジア地区予選に行く人もそうでない人も、次の舞台での活躍を期待しています。

今年のICPCは私にとって、選手としてもコーチとしても関係の無いICPCで、国内予選の日にはJAGスタッフと一緒に模擬国内予選の打ち上げをしながら観戦者として楽しませていただきました。

ICPCを引退してからもICPCの動向を楽しむことができるのは、JAGを通して現役選手や元選手とのつながりが持てているからだと思います。このことを引退した元選手に話すと「JAGに興味はあるけど、どんな活動をしているのかよく分からないから参加しづらい」という声を聞くことがありました。

そこで、JAGにスタッフ2年目の私がJAGの1年間の活動を紹介します。

注意

ここで上げた全部の活動に関わらなければならない義務があるわけではないので、どの活動に関わるのかは各々のスタッフの裁量に委ねられています(例えば、私は問題の原案作成にはほとんど関わっていません)。

また、ここで紹介しているJAGの活動は、私が関わったことがある範囲のものに過ぎないので、これ以外のものも多数あります(入会・退会の管理、予算の管理、アジア地区予選の運営のサポートなど)。

JAGが開催しているイベント

模擬国内予選

ICPC国内予選の1~2週間前に行われる模擬国内予選とともにJAGの1年が始まります。

模擬国内予選はJAGが開催しているイベントの中で参加者の数が圧倒的に多く、参加者のレベルも幅広いです。

作問というと、難しい問題を作ることに目が行きがちですが、模擬国内予選のように幅広いレベルの参加者を対象としているコンテストでは「おもしろいA問題、B問題」を作ることも大切です。JAGでは初心者向けの教育的良問を作ることに関心がある方の参加を歓迎しています。

また、模擬国内予選ではJAGが開催している他のイベントとは違って、ICPC本番と同様のシステムを用いて練習会を開催しています。どうして本番と同じシステムが利用できているのかというと、予選システムの貸し出しが受けられる制度が用意されているからです。1年に1度しか触れることの無いシステムなので、模擬国内予選が時間どおりに始められなかったりデータセットがダウンロードできなかったりと、しばしば障害に見舞われています… JAGでは障害対応に強いインフラエンジニアの方の参加を切実にお待ちしています。

夏合宿

9月に代々木のオリンピックセンターで地区予選に向けた強化合宿を開催しています。昔は国内予選の成績を参考にした招待制だったそうなのですが、近年は希望すれば誰でも参加できるようになっています。今年は2018年9月15日(土)〜 9月17日(月)で開催する予定なので現役選手の方はぜひ来てください!!

夏合宿での作問が国内予選と大きく異なるのは、英語の問題文を提供していることです。「英語の問題文とか書くの無理でしょ…」と思っていたのですが、実際その通りで、私一人では書けません。英語が得意なスタッフにかなり手助けしてもらっています。

夏合宿はオンサイトのイベントなので、作問以外のタスクが無数にあります。現地スタッフだけ手伝いたいという方も歓迎しています。

  • 事前準備
    • 会場と宿泊施設の予約と利用手続きをする
    • プリンタ、電源タップなどの機材を準備する
    • モバイルWi-Fiをレンタルする
    • 参加者用のお弁当の注文をする
  • 夏合宿中
    • 問題文を印刷してホッチキスで留めて封筒に入れる
    • 風船を膨らませて配る
    • 印刷ジョブが飛んできたら印刷物をチームのところに持っていく
    • お弁当が届いたら参加者に配る
    • 問題の解説をする

模擬地区予選

アジア地区予選と夏合宿の間の期間が空いている場合に行われます。夏合宿と同様、問題文は英語で出題しています。

関東ではオンサイト会場を毎年用意していますが、関西では2015年以降はスタッフ不足によりオンサイト会場を用意できていないです。JAGでは関西で模擬地区予選オンサイトを開催したいという方の参加をお待ちしています。

JAGの作問フロー

問題の原案づくり

JAGのページ (http://acm-icpc.aitea.net/) を見るとわかるように、JAGでは古き良きPukiWikiを活用しています。作問は最初に原案を考えるところから始まるのですが、スタッフ用のPukiWikiに専用のコーナーがあり、スタッフなら誰でもいつでも原案を投稿することができます。

f:id:kujira16:20180709003948p:plain

↑のスクショは今年の模擬国内予選のA問題「改元」の投稿です。この段階では問題文も制約も簡略な表記がされており、これをそのまま問題文として出題できる状態ではないですが、投稿はアイデア程度のものでOKで、実際に使われることにになったら手分けして詳細を決めていきます。

解法がわからないけど問題として使えそうなアイデアがあるという場合は、未解決問題を議論するSlackチャンネルがあります。問題を書き込むとプロたちが瞬く間に解法を考えてくれるので、解けることがわかって問題として採用されたり、解けないことがわかってお蔵入りしたりします。

問題選定

f:id:kujira16:20180709003442p:plain

コンテストの時期が近づくと、投稿された問題のアイデアをもとに問題を選定します。

JAGの内部Wikiに投稿された問題の一覧はGoogleスプレッドシートに転記されるような仕組みになっています。Wikiに投稿された問題を読んだ人は、問題の想定難易度(AOJ-ICPC 換算)と推薦度をスプレッドシートに書き込むことになっています。

私はこの難易度付けの作業がかなり苦手です… そもそもAOJ-ICPCをあまり熱心に埋めていなかったので、難易度の相場をよく分かっていないというのもあります。JAGではAOJ-ICPC埋めが得意な優秀若人や、問題の難易度を評価してくれる優秀若人を募集しています。

問題文作成

問題が選定されたら、原案をもとに実際の問題文の作成を行います。

近年では、競技プログラミング界の傾向として問題文からストーリー性が削られる傾向にあると感じています。しかしながら、ICPCでは今でもストーリー性がある問題文で出題されているという事実があるので、JAGでもそれに従って、ストーリー性がある問題文を出題するように努力しています。

f:id:kujira16:20180709004053p:plain

JAGスタッフの豊かな想像力により、このような問題文が生成されます。

ICPCの問題文では "ACM" や "ICPC" を頭文字とするような固有名詞がしばしば登場するので、JAGの問題文でも遊び要素として入れるようにしています。去年は "Industrial Convex Pillar City" (ICPC) や "Jumbo Amusement Garden" (JAG) などが生まれました。カッコいい固有名詞を思いついてくれる優秀若人を募集しています。

問題の原案を最初に考えた人が問題文も書く担当もやらなければならないというような義務はなく、手分けしてやっています。問題文の担当者の役割は、これまでに培ってきた競技プログラミングの知識を動員して、実際のICPCで使われそうなスタイルの問題文を書くことです。

私は作問力が低いので、原案づくりにはほとんど貢献できていないということもあり、だいたい問題文の担当をやっていることが多いです。

問題文の作成作業ではGoogleドキュメントを利用して行っています。出題ミスを減らすため、問題文の作成担当者のほかに校正の担当者も設定しており、Googleドキュメントのコメント機能を使ってやりとりしています。

データセット作成

データセットの作成は問題の難易度と関わる重要作業なので、問題文の作成担当者とは別の人が行っています。

作成されたデータセットの検証にはtestlibというC++のライブラリを使っています。これは、空白の有無や改行コードなどを検証を行うコードの記述を手助けしてくれるライブラリで、問題文の作成担当者が検証コードを書くことで、問題文に記載した入力のフォーマットと矛盾する入力が作られていないかチェックしています。

github.com

ジャッジ解の作成

問題文やテストケースが正しく作成されているという確認のために、いろいろな人がジャッジ解を作成することが望ましいです。

ICPCではC++の他にJavaPythonも使用可能なので、JavaPythonのジャッジ解も作成することが望ましいのですが、人手不足で十分に行えていません。また、正答するジャッジ解以外にも、TLE解、MLE解、嘘解法を作ることも必要です。JAGではJavaPythonでジャッジ解を書きたいという方や、嘘解法に精通した方を切実に募集しています。

Rimeと継続的インテグレーション

JAGではデータセットの生成・検証とジャッジ解の検証のためにRimeを使用しています。Rimeは昨年行った改修でPython3に対応することができました。ただ、Windowsでの挙動に怪しいところがあるという問題を抱えており、Windowsで動作するような改修を行ってくれるPythonに精通した人材を募集しています。

github.com

Rimeには、データセットの作成状況やジャッジ解の実行結果をPukiWikiにアップロードするプラグインが含まれており、JAGの内部Wikiで進捗が確認できるような仕組みを導入しています。

f:id:kujira16:20180709223355p:plain

f:id:kujira16:20180709005007p:plain

データセットやジャッジ解のソースコードはGitとGitHubで管理しています。昨年からの試みとして、継続的インテグレーションのサービスを利用して、GitHubにpushされたら自動的にテストを実行してPukiWikiの更新を行う仕組みを導入しています。

解説の作成

問題の解説は、問題の準備が一息ついてから行っている状況です。そのため、十分に時間をかけた分かりやすい解説にはなっていないかもしれません。競技プログラミングでの解説の公開方法に改善したいところがあるという方の参加を切実にお待ちしております。

まとめ

2年目のスタッフとして私から見えたJAGの活動を紹介しました。

JAGでは現役選手を応援したいと思っているすべての人を募集しています。