AtCoderでのコンテスト主催者向けのツール紹介 (Competitive Programming (その2) Advent Calendar 2015 Day 17)

この記事は、Competitive Programming Advent Calendar(その2)の17日目の記事です。カレンダーについては、以下参照。

こんにちは、2Dです。最近は、あまりガチで競技プログラミングをしていないので、知らない人も多いかもしれません。2008-2012年くらいにICPCに参加してた者です(内2回アジア)。今は、ACM-ICPC OB/OGの会で問題作成やコンテストの運営に関わってます。

今回は、主にコンテスト主催側の人達が使えそうなツールを紹介するので、選手として参加する人たちにはあまり関係ない記事になると思います。すみません。ここでは、以下の2つのツールについて紹介します。

AtCoderクラー Slack通知ツール atcoder-clar2slack

そもそもクラーとは?

AtCoderでコンテストに参加したことのある方はわかると思いますが、AtCoderにはコンテストについてわからないことを質問するためのフォームが存在します。こんなの↓

f:id:Respect2D:20151215233005p:plain:w400

このフォームから送られてきた質問のことを "clarification"、略してクラーと呼んでいます。質問された内容は、コンテスト運営者専用の画面で、以下のように確認することができ、それぞれのクラーに対して返答を行うことができます。

f:id:Respect2D:20151215235026p:plain:w500


コンテスト運営にとってのクラー

クラーの中には、問題の不備について教えてくれるような重要な質問が存在する場合があります。

例えば、「サンプル1の出力は1ではなく2ではありませんか?」のような質問がよくあります(よくあっていいとは言っていない)。このクラーを送った人の勘違いならいいですが、このクラーの不備が事実であるならば、大変な事態です。選手は、最低限サンプルが一致しなければコードの提出ができないので、問題文のサンプルが間違っているだけで、選手の貴重な時間を削ってしまうことになります。

上のはちょっとした一例ですが、選手に無駄な時間をとらせないためにも、コンテスト運営者は、クラーが来たことになるべく早く気付き、なるべく早く回答を行う必要があります(そもそも、不備がないように問題作れよという話ですが、いくら慎重に作っても不備は出るものなのでそのツッコミはなしで)。

ちなみに、ツールができる前は、クラー画面を常に監視する係を決めて、クラーが来たことに気付いたらチャットルームに知らせるという原始的なやり方で、クラーに気付くのが遅れたりして、残念な感じでした。


通知ツール作った

ということで、自動でクラーをSlackに通知してくれるツールを作りました。

github.com

何故かScala (sbt)で書きました。理由は、ただ単にScalaを書く練習をしたかったからという、そんな単純なものです。とりあえず初回起動が非常に遅いです。ごめんなさい。使い方は、チョロっとREADMEに書いてありますが、こっちではもう少し詳しく説明したいと思います。


設定・起動方法

sbt インストール

まずは、sbt(http://www.scala-sbt.org/download.html)をインストールしてもらう必要があります。リンク先に、インストール方法が書いてあるので、そちらを参考に、コマンドラインから sbt コマンドを使えるようにしてください。

設定ファイル

atcoder-clar2slackをcloneしてもらうと、 src/main/resources/ ディレクトリの中に application.conf というファイルがあるので、以下を参考に設定を行ってください。

  • atcoder.url
  • atcoder.userId:コンテスト運営用のクラー画面を閲覧する権限を持つユーザのIDを入力してください。
  • atcoder.password:↑のユーザのパスワードを入力してください。
  • slack.webhookUrl:後で説明します。
  • clar.sleepTime:最新のクラーを何ミリ秒ごとに取得するかを指定できます。この間隔でAtCoderにアクセスするので、細かくしすぎるとBanされるかもしれません。
slackのwebhookUrlについて

Slackに通知するために、webhookUrlというものが必要になります。webhookUrlは、 https://my.slack.com/services/new/incoming-webhook/ から取得できます。アクセスすると、こんな感じの画面が出てきます。

f:id:Respect2D:20151216005003p:plain:w400

ここでは、クラーを通知させたいチャンネルを1つ指定してください。Addすると、次のような画面が出てきます。

f:id:Respect2D:20151216005857p:plain:w500

  • Post to Channel: クラーを通知するチャンネルを設定できます。
  • Webhook Url: このURLをコピーして、application.conf のslack.webhookUrlに書き込んでください。
  • Descriptive Label: 無視して大丈夫です。
  • Customize Name: 通知Botの名前を設定できます。JAGでは、「かしこいかわいいクラーちか」と設定しています。
  • Customize Icon: 通知Botのアイコンを設定できます。JAGでは(ry

Save Settingsをクリックして終了です。

起動

コマンドラインで以下のコマンドを打って、ツールを起動します。

$ sbt run
https://jag2015summer-day4.contest.atcoder.jp の監視を開始します。
管理者アカウントでログインしました。
最新クラーチェック...
最新クラーチェック...

application.confの設定した値が正しければ、上記のような感じでメッセージが表示されます。


動作確認

実際にどのような動きになるのか、紹介します。

クラーを送信したとき

クラーを送信してみます。
f:id:Respect2D:20151215233005p:plain:w400

f:id:Respect2D:20151216020445p:plain:w300

Slackの先ほど設定したチャンネルに、以下の内容が通知されます。

  • クラーのID
  • どの問題に対してのクラーか(問題文へのリンク付き)
  • クラーを送ってきたユーザ名(ユーザへのリンク付き)
  • 質問の内容
  • 質問回答ページへのリンク
回答を返したとき

クラーに回答してみます。
f:id:Respect2D:20151216021220p:plain:w400

f:id:Respect2D:20151216021312p:plain:w300

以下の内容がSlackに通知されます。

  • どの問題のクラーか(問題文へのリンク付き)
  • クラーを送ってきたユーザ名(ユーザへのリンク付き)
  • 質問の内容
  • 回答の内容
  • 全体公開にしているか(Noならば、クラーを送ってきたユーザのみが回答を閲覧できる。Yesなら、選手全員が回答を閲覧できる)
  • 質問回答ページへのリンク

今後

以上、AtCoderクラーのSlack通知ツールについてでした。

今後やりたいこと。

  • コンテスト参加者が使えるクラー通知(Chrome拡張でデスクトップ通知するのを新しく作った方がよさげ)
  • AOJコンテストの通知に対応させる(会津合宿・立命合宿での需要)
  • オンサイトのユーザがACしたときに通知(風船配布管理ツールに入れた方がいいかも)
  • できれば、風船配布管理ツール(この後説明)へ統合?
  • 複数のwebhookUrlへのメッセージ送信

風船配布管理ツール BalloonFusenSystem

次は、hasiさんが作った風船配布管理ツールを紹介します。

風船ってなんだよ

まず、知らない人からは風船とは何かというツッコミを受けると思います。大学生向けのプログラミングコンテストとして有名なACM-ICPCでは、いくつかの問題が出題され、1問解けるごとに、1つ風船が届けられます。風船が浮かんでいるこんな風景↓を見たことある人は結構いるのではないでしょうか。風船がたくさん浮かんでいれば、そのチームは多くの問題を解いていることを表します。

f:id:Respect2D:20151217010533p:plain

写真の奥の方に写っていますが、各問題ごとに風船の色が決まっていて、解けた問題に対応する色の風船が配布されます。


風船配りは大変

風船配りのプロ集団と言われるACM-ICPC OB/OGの会ですが、ICPCに向けた模擬コンテストで風船配りを行う度、実は非常に苦戦しています。何が大変なのか?いろいろ大変なんです。例えば以下のようなことが。

  • 模擬コンテストでは、風船を配るべきオンサイト参加のチームと、配らなくていい外部(オンライン)参加のチームがごちゃまぜでランキングが表示されます。そのため、正解したチームがオンサイトなのかオンラインなのか、正解が出るごとにいちいち見極める必要があります。結果、配るべきチームを見逃すということも。
  • どのチームにどの風船を配ったか、という情報を正しく記録しないと、風船の配り忘れや配り過ぎ(配りに行こうとしたら、すでに配ってた)などのトラブルが発生します。

ちなみに、ツールを作るまでは、Googleスプレッドシートなどを使って、どのチームのどの問題の風船を配ったかというのを、人力で管理していました。人力なので、見逃しとか結構あって、辛かったです。

他にもいろいろありますが、まとめると「どのチームにどの風船を配ったかを一目で把握したい」「オンラインチームのノイズを取り除いて、オンサイトのチームのことだけを考えたい」の2点が叶えば、風船配りが非常にラクになり、間違いも少なくなると考えました。


風船配布管理ツール作った

ということで、そんな願いを叶えてくれるシステムをhasiさんが今年のJAG夏合宿のときに作ってくれました。

github.com

僕はあまり把握できてないですが、AtCoderからの情報取得を行っている部分がpythonで書かれていて、風船配布システムに関する部分はphpで書かれているっぽく見えます。


設定・起動方法

起動方法については、READMEを参照してください。AWSのEC2で動かすと、READMEに書かれているコマンドをそのまま打てばいいだけなので、ラクです。AWSを使ったことがないという方は、スペックが低いサーバであれば、1年無料で使うことができるので、是非さわってみてください。

風船システムは、AtCoderとAOJに対応しています。それぞれの設定方法について説明します。

AtCoderの場合の設定

stands/contest.txt を開きます。1行目に、AtCoderのコンテストのURLを書きます。2行目に、コンテストの名称を書きます。2行目はわかりやすければ何でも構いません。例えば、こんな感じです。

https://jag2015summer-day4.contest.atcoder.jp/
JAGSummerDay4

あと、stands/passwd.txt というファイルを作って、ここにユーザIDとパスワードをコロンで区切って書きます。

id:pass
AOJの場合

stands/contest.txt を開きます。1行目に、AOJのAPIのURLを書きます。2行目に、コンテストの名称を書きます。2行目はわかりやすければ何でも構いません。例えば、こんな感じ

http://judge.u-aizu.ac.jp/onlinejudge/webservice/contest_standing?id=ACPC2015Day1
ACPC2015Day1

1行目の ACPC2015Day1 は、コンテストのURLにidがついているので、それをコピーすればいいです。こういうのの末尾についているID→ http://judge.u-aizu.ac.jp/onlinejudge/contest_standing.jsp?id=ACPC2015Day1

AOJの場合は、ユーザID/パスワードは必要ありません。


動作確認

風船システムでは、どんなことができるか紹介します。

オンラインチームを取り除く

オンサイトチームの情報だけを見られるようにするために、オンサイトチームかそうでないかを選択できるページがあります。ただ、このページにアクセスする導線がなさげです(今気付いた)。「システムのURL/ranking.php?contest_name=コンテストID」でアクセスできます。http://XX.XX.XX.XXでシステムが動いていて、JAGSummerDay4のチームの管理をしたいなら、

http://XX.XX.XX.XX/ranking.php?contest_name=JAGSummerDay4

みたいな感じです。

このページを開くと、コンテストに参加しているチームの一覧が表示されます。

f:id:Respect2D:20151217025029p:plain:w350

チーム名をクリックすると、オンサイト参加者と外部参加者のフラグが入れ替わるようになっています。ちょっとわかりづらいですが、オンサイト参加者は、表の上側に表示されるようになっています(後でもう少し見やすく直した方がよさそう)。上図では、kog_115さんから上はオンサイト扱い、SoMin_Munさんから下は外部チーム扱いになります。

ログインしてみる

f:id:Respect2D:20151217024743p:plain

ログインします。名前を入れれば誰でもログインできます。

コンテストを選ぶ

f:id:Respect2D:20151217024802p:plain

ログインすると、コンテスト一覧が表示されます。ここで登録されているのは、JAGSummerDay4の1つだけなので、このコンテストを選んでみます。

風船配布管理画面

f:id:Respect2D:20151217025647p:plain:w350

このシステムの一番メインの画面です。各行が、正解1つ=風船配布1回に相当します。この画面には、先程オンサイトに設定したチームしか表示されないようになっているので、前まで鬱陶しかったノイズが一切ありません(オンサイトチームの設定が正しければの話ですが)。

このシステムにおいて、風船の配布状態として、以下の3種類が存在します。

  • 風船を配っていない&まだ風船を配布する担当が決まっていない=誰か配る宣言をする必要があります

   f:id:Respect2D:20151217030634p:plain:w350

  • 風船を配っていない&風船を配布する担当は決まっている=あとは担当者にまかせておけば安心

   f:id:Respect2D:20151217030819p:plain:w350

  • 風船を配り終えた=無視してよし

   f:id:Respect2D:20151217030828p:plain:w310

風船を配る宣言をする

f:id:Respect2D:20151217030634p:plain:w350

このチームの風船の担当がまだ決まっていないようなので、自分が風船を配る担当に名乗り出てみます。「風船を配る」ボタンを押すと、自分が担当としてアサインされ、以下のような画面が表示されます。

f:id:Respect2D:20151217031818p:plain:w200

この画面で、「done」ボタンを押せば、風船を配り終えたことになります。今は、まだdoneボタンを押してなくて、担当者が決定しただけなので、風船配布管理画面を閲覧すると、次のように表示されます。

f:id:Respect2D:20151217030819p:plain:w350

風船を配り終える

風船をチームのもとへ無事に配り終えた後は、先程の画面で「done」ボタンを押します。そうすると、風船配布管理画面では、以下のように表示され、風船をすでに配り終えたことがわかります。

f:id:Respect2D:20151217030828p:plain:w310

今後

ということで、風船配布管理ツールについての紹介でした。このツールができてから、風船の配布であたふたすることがなくなって、非常に助かっています。自動化万歳。

今後できるといいこと

  • オンライン参加登録ページ
    • 今は、コンテスト運営側でオンサイトチームかそうでないかを見極めてランキングページで設定していますがそれも面倒。コンテスト参加者が、自分のチームはオンサイト参加であることを登録できるようなページがあると運営の手間がはぶけてよさそう。
  • 風船配布ページを開いていると、正解が出たときにデスクトップ通知してくれる
  • ビジュアルもう少しわかりやすく

まとめ

ということで、コンテスト運営向けのツールを2つご紹介しました。どちらも即席で作ったツールでまだまだ作りかけなので、こういう機能あるといいんじゃない?ここ直した方がいいのでは?みたいなのがあれば、issue/PR、大歓迎です。

あと、宣伝です。ACM-ICPC OB/OGの会(http://acm-icpc.aitea.net/)のスタッフを絶賛募集中です。作問したい人はもちろん、今回紹介したようなツールの開発に関わりたいという方も大歓迎です。一緒に、ICPC現役のみんなを応援しましょう。

以上で終わります。明日は、その1が skyaozora さん、その2が cielavenir さんです。お楽しみに〜。

会津大学競技プログラミング合宿2015 参加記

イベント詳細: 会津大学競技プログラミング合宿2015 : ATND

社会人になってから、立命会津の合宿には参加できていなかったけど、今回はシルバーウィークに重なっていたので、せっかくだから参加した。
たまには参加記を書いてみることに。

n日前(1 <= n <= 10)

ホテルが必要だけど、どこを調べても全部埋まってた。
前日まで、毎日チェックしてたけど、どのホテルも空かない。
どうも、シルバーウィークに加えて、会津まつりというのがあるらしく、それでホテルが埋まってしまってたみたい。

結局、ホテル取れないまま当日に。

1日目

初めて高速バスに乗った。
高速がかなり混んでて、1時間以上到着が遅れる。

ちょうど同じ時間に着いた___Johnielさんも宿が取れてないらしく、ホテルが空いてないか、一緒に駅前のホテルに直接確認しに行ってみることに。
運のいいことに、ツインがまさかの2泊分空いてたので、___Johnielさんと2人で泊まることに。

ホテルが取れて安心したので、会津大学へ。
共感する人が多いみたいで、めっちゃfavられた↓

お菓子がいろいろ置いてあって、準備がいい。

参加者のみなさん(立命会津の人が大半)や、yutaka先生と会った。
立命のメンバーは、顔がわからない人がほとんどになっていて、老がい感を味わう。

1日目は立命館大学セットで、僕も若干作問に関わっていたので、ジャッジサイドで参加。

  • A:解ける
  • B:こどふぉに出てきそうなやつ
  • C:Bから難易度が結構上がってDP。BとCの間くらいの難易度の問題が必要だったかもしれない。
  • D:少し数学チック?もともと、W, Hは10^6だったけど、僕が提供したジャッジ解の計算量O(W+H)をACさせないために、10^9に上がった。
  • E:この問題だけ校正が不十分で、クラーが結構とんでしまった(クラーのほとんどは、climpetさんが送ってくれた)。僕は問題解く能力があまりないので、ジャッジ解作るより問題文チェックの方に力入れるべきだったかもしれない。
  • F:完全に既出だったっぽい。OEISでeggと調べるだけで出て来るような数列だったらしい。調査不足だった。

オンラインでは全完が結構出たけど、オンサイト組のAC数は最大でも4問だったから、オンサイト的にはこれぐらいの難易度がちょうどよかったと思う。
僕は、ほとんど作問に関われてないけど、僕が現役の頃に作った問題なんかより余程いい問題が作れていて、後輩たちはすごいと思った(こなみ)。

あと、JAG夏合宿のときに作った、AtCoderのクラーの通知をSlackにとばしてくれるシステムをAOJ用に改造した。
リストに書かれたチーム名(オンサイトのチームとか)のACだけ、Slackに通知してくれるようなシステムも作った。

コンテスト終了後は、駅前の中華料理屋の黄鶴楼へ。
適当に席に座ってよかったから、ICPC引退勢(社会人)が同じテーブルに集中してしまって、シルバーシートができあがっていた。
Yazatenさんやkazu0x17などの現役勢も座ってきてくれて、若々しい会話をきくこともできた。

懇親した後は、富士の湯で疲れを癒し、酒を飲み就寝。
立命のみなさん、作問お疲れ様でした!

2日目

黄鶴楼で朝食を取る。
久々にちゃんと朝食を食べた。

会津大へ。
2日目は、参加者サイドで、チーム戦が可能だったので、___Johnielさんとlawliet3110さんと一緒にチームrougaigar(ロウガイガー)として参加した。
名前の由来は、老害ガオガイガー

  • A=僕、B=lawlietさん、C=___Johnielさんで担当分けてAC。
  • D=僕がダイクストラしてAC。
  • E=僕がDを書いてる内に、lawlietさんが考えてくれててAC。
  • F=他のチームが解いてないのでとばす
  • G=___Johnielさんがフローによる解き方を考えてくれたのでそれを___Johnielさんが実装。負辺とか考えないといけなかったっぽくて、蟻本をそのまま写経するだけでは無理そうで苦戦。lawlietさんの協力もあり、デバッグに時間がかかったけど、解くのに2時間程度かかってAC。
  • H=前半、全く上位陣に解かれていなかったため、一旦とばしてしまった。開始3時間くらいで見直して、普通にDPやるだけだったので、僕がGと並行して実装。GがACした数分後にこっちもAC。
  • I=座標圧縮とか、セグメント木を使おうとか考えてて、絶対バグらしてコンテスト終了する未来が見えたので、結局実装することなく終了。
  • J=Gを解いた後に見て、残り40分くらいしかなかったので、すごく適当な解法で___Johnielさんが実装し始める。STLのlistでは機能が足りないからといって、リスト構造を自分で実装し始めたりしてやばかった。がんばったけど、C++特有のコンパイルエラーが出まくって、終了時間までに間に合わなかった。
  • K=問題読んだだけ。
  • L=問題読んだだけ。解説だけ聞くと、割とわかりやすいDPだったので、解法を考えなくてちょっともったいなかった気がした。

オンサイトでは、僕たちのチームが一番問題を解いて、老害にも関わらず賞品をもらってしまった。
___Johnielさんが持って来てくれたやつだった。

コンテスト終了後は、懇親会のためにワシントンホテルへ。

さすがワシントンホテル、いい部屋へ通される。
マイク付き。

2日目も、シルバーシートができあがっていた。
料理も、ホテルのちゃんとしたコースで、どの料理もすごくおいしかった。
しかし、最後のフルーツで出てきたドラゴンフルーツだけは、味のないキウイみたいで、おいしくなかった。
懇親会終わった後は、ホテルでダラダラ。←イマココ

会津大のみなさん、作問おつかれさまでした。
みなさん徹夜だったようなので、ゆっくり寝てください。

3日目

北大のセット

そういえば、書いてなかったことに気づいた(2015/12/16)

Windowsでのplatexのインストール

概要

Cygwinplatexインストールするのに、2~3年前までは このページ とかでうまくいってたのですが、最近インストールしようとしたら setup.ini が読めないっぽいエラーが出てインストールできなくなってたので、他の方法でインストールしました(該当のページにはsetup.iniちゃんと置いてあるんだけど何で失敗するんだ...)。

インストール方法

このページ で、platex系のパッケージをまとめてインストールしてくれるexeがあったので、それを使って、platexをインストールしました。
Windows環境変数にも勝手にパスを通してくれるのでとてもラクです。

実行

すでにパスを通してくれてるので、Cygwinで試しにplatexが動いてるかだけ試す。

$ cat hello.tex
\documentclass{jarticle}
\begin{document}
こんにちは\LaTeX。
\end{document}

$ platex hello.tex
This is e-pTeX, Version 3.14159265-p3.6-141210-2.6 (sjis) (TeX Live 2015/W32TeX) (preloaded format=platex)
 restricted \write18 enabled.
entering extended mode
(./hello.tex
pLaTeX2e <2006/11/10> (based on LaTeX2e <2014/05/01> patch level 0)
Babel <3.9l> and hyphenation patterns for 79 languages loaded.
(c:/w32tex/share/texmf-dist/tex/platex/base/jarticle.cls
Document Class: jarticle 2006/06/27 v1.6 Standard pLaTeX class
(c:/w32tex/share/texmf-dist/tex/platex/base/jsize10.clo))
No file hello.aux.
[1] (./hello.aux) )
Output written on hello.dvi (1 page, 356 bytes).
Transcript written on hello.log.

$ ls
hello.aux  hello.dvi  hello.log  hello.tex

dvioutで確認。

f:id:Respect2D:20150409173548p:plain:w300

大丈夫そう。
終わり。

競技プログラミングの作問進行法 (Competitive Programming Advent Calendar Div2014 Day 2)

Intro

初めての作問。作問の作業ってどう進めればいいのかわからない。
そんな人のために、今年は作問についての記事を書くことにしました。
特に、ACM-ICPC OB/OGの会 (通称JAG)の作問の仕方を例に書きます。そのため、作業者が複数いて、ネット上で全てを進めるような作問形態の例となります。その形態と違う方は、自分の環境に合わせてやり方を変えてみましょう。

目次

実際の進行方法と同じように書きます。

  1. コンテスト概要を決めよう
  2. 原案を出そう
  3. 問題選定をしよう
  4. 作業担当者を決めよう
  5. rime&testlibでコード作成
  6. Google docsを使って校正
  7. 最終段階
  8. JAGに入ろう!(番外編)
  9. おわりに

コンテスト概要を決めよう

まずは、「どのようなコンテストを開くのか」決めましょう。これが決まっていなければ、どのような問題を作っていいのかわかりません。決めるのは、次のようなことです。

コンテストの目的

「目的」がなければ、どんなコンテストを開いていいかわかりません。
「ただ、たまった問題を放出したい」という簡単な目的でも、「ICPC国内予選の対策としてコンテストを開きたい」というJAGのような目的でも、何でも大丈夫なので決定しましょう。これが決まっていると、コンテストの概要を決めるヒントになります。

出場者のレベル

「選手のレベル」が決まっていると、自然と問題のレベルも決まってきます。
例えば、TopCoder Div2程度の出場者を対象と決めているなら、Div1 Hardレベルの問題を作る必要はない、とかそういうことです(というか、作れないけど...)。

コンテスト時間・問題数・難易度・ジャンル

目的や出場者のレベルが決まっていると、自然に「コンテストの時間」「問題数」「問題のレベル」「問題の難易度」「問題のジャンル」が決まってきます。
ICPC国内予選対策を目的としてコンテストを開くならば、出場者のレベルは初心者から上級者まで幅広い出場者のレベルが考えられます。ICPCの過去のコンテストの傾向も合わせると、以下のようなコンテスト概要ができあがります。

  • コンテスト時間:3時間
  • 問題数:6~7問
  • レベル
    • プログラミングを始めたばかりの人でも解けるようなレベルの問題を入れる
    • 競技プログラミングの「プロ」が、時間内に解けるか怪しいレベルの問題も用意する(さすがに0perasanレベルは対象外)
  • ジャンル
    • やるだけ 2~3問
    • 探索・DP 2~3問
    • 幾何 1~2問
    • 文字列操作・構文解析 0~1問

原案を出そう

概要が決まりました。さあ、作問作業の始まりです。
まずは、コンテストの概要に合うような問題「原案」をたくさん考えましょう。実際にコンテストに出題するような、しっかりした問題文でなくても大丈夫です。適当な問題案でも、思いついたら片っ端からメモしましょう。

JAGでは「pukiwiki」を使用して、以下の図のように原案を1問1問まとめています(以下の図は、テンプレートです)。

f:id:Respect2D:20141202015231p:plain

図の説明

  • タイトルと問題の概要
    • 問題の作成者や、問題のジャンル、難易度等を書きましょう。コンテストに採用すべき問題かどうかが、一目でわかるので便利です。
  • Problem Statement
    • 図中に書いてある通りです。適当でもいいですが、他人が見て理解できる程度の問題文を書きましょう。
  • Input, Output
    • 入出力のフォーマットについての説明を書きましょう。Outputに「Special Judge」と赤太字で書いてあります。これは、出力が一意に定まらないような問題のときに、必ずメモしておきましょう(例えば、この問題)。Special Judgeの場合、問題準備に一手間かかるので、この情報は大切です。
  • 解法
    • 原案が思い浮かんだ時点で解法がわかっている場合は、詳しく書きましょう。書いておくと、誰かが間違いを発見してくれたり、もっと良い解法を考えてくれる場合があります。
  • 推薦
    • コンテストに出題するかどうかを、JAGではこのように推薦という形で決めています。「この問題を次の模擬国内予選のA問題に推薦します」みたいな感じで記入したりします。
  • 議論
    • 解法の相談や、問題についての意見は、この欄に記入し議論します。

問題選定をしよう

原案をたくさん出しました。
次は「問題選定」を行います。原案の中から、コンテストの概要に合うような問題を適切に決定しましょう。

選定の作業を行った結果、実は原案が足りていないと発覚することがあります(例えば、ICPC国内予選のような問題セットを作りたいと思っていたのに、原案がA~D相当の問題しかなくて、E~Gに置ける問題がない、みたいなことが)。その場合は、今足りていないジャンル、難易度を明確にして、原案を作る作業を再度行いましょう。

このように、選定で結構手間取ってしまうことが多いので、「原案出しと問題選定作業はなるべく早めに」行うようにしましょう。

作業担当者を決めよう

問題がでそろったので、各問題に担当者をつけましょう。JAGでは、以下の図のように「1問につき最低3人体制」の形で作業を進めています。

f:id:Respect2D:20141202030710p:plain

各担当者の意味

  • データセット・解答作成
    • データセットというのは、入力データのことです。間違った解答をなるべく落とすことができるような入力データを作る仕事です。
    • 解答作成は、入力データを受け取って、解答の出力を行うプログラムを作る仕事です(つまりは、皆さんがいつもコンテストで書いているプログラムを作る仕事)。
  • 問題文・入力検証器・解答作成
    • 問題文作成は、どういうストーリーにするか、入出力仕様はどうするか等を考えて、問題文全体を書く仕事です。
    • 入力検証器作成は、データセットが入力仕様通りであるか確認するプログラムを作成する仕事です。
  • 問題文チェック
    • 問題文の校正作業を行う仕事です。
    • 第三者しか気付けないようなことがたくさんあるので、大事な仕事。
    • この人が仕事することで、Clar率が断然減ります。

JAGでは、このように3人に仕事を割り振っていますが、多少割り振り方を変えても問題ありません。ただし、以下の注意点は守っておくのをオススメします。

  • 解答作成者は最低でも2人」設けましょう。Outputを複数人で確認することで、バグを見つけることができるようになります。解答は、多ければ多いほど信頼度が増すので、自分の担当問題以外でも是非作成しましょう。
  • データセット作成と入力検証器作成は必ず別の人」にしましょう。同じ人が作ってしまった場合、データセットの間違いに気付かない可能性があります。
  • 問題文校正は1人目・2人目とは別の人が望ましい」です。全く問題を知らない人が問題文をチェックすることで、より多くの間違いを指摘することができます。

ちなみに、仮に全部1人だけで1問を担当した場合、次のようなことが起こり得ます。

  • そもそも自分の想定解法が間違っている場合がある
  • Outputを誰とも比較することができず、バグを発見できない可能性がある
  • わかりづらい問題文ができあがりやすい

筆者も1人で全部作ったことがありますが、コンテスト中に2つ目が発覚して、冷や汗した経験があるので、1人だけで作るのだけは絶対やめましょう。

rime&testlibでコード作成

担当者が決まりました。では、実際に「コード」を書きましょう。
って言っても、どういうコードを書けばいいんだ?って思うかもしれません。作問では、いつもみたいに、解答コードを書けばいいだけではありません。

rime

そんなとき役に立つ作問ツールが「rime」です。
JAGもrimeを使用して、作問作業を行っています。rimeを使って、どのようなコードを書けばいいかは、詳しいことがリンク先に説明が記載されているので、そちらをご参照ください。実際のrimeを使った例もこちらにあがっているので、これも必見です。

testlib

さらにJAGでは「testlib」というライブラリを使用しています。
rimeが有名で、こちらはあまり名前を聞かない人もいるかもしれませんが、testlibはデータセット作成プログラムや、入力検証器プログラムで大活躍します。

例えば、AとBの整数 (1 <= A, B <= 1000)が次のような形式で1行で入力される問題を例にしましょう。

A B

この問題の入力検証器をライブラリなしで書こうとするとどうなるでしょう?たったこれだけの検証なのに、本当に正しくチェックしようとしたら、結構面倒だと思います。
もし、この入力検証器をtestlibを使って書くと、次のように簡単に書くことができます。プログラムも直感的でわかりやすいのではないでしょうか。

#include "testlib.h"
using namespace std;

#define MIN_AB 1
#define MAX_AB 1000

int main(){
  registerValidation();

  inf.readInt(MIN_AB, MAX_AB); // 1以上1000以下の整数
  inf.readSpace();             // 間に空白1つ
  inf.readInt(MIN_AB, MAX_AB); // 1以上1000以下の整数
  inf.readEoln();              // 最後に改行
  inf.readEof();               // ファイルの終わり

  return 0;
}

もし、間違った入力が与えられた場合は、エラーをはいてくれます。もっと詳しい使い方は、リンク先を参照してください。

Google docsを使って校正

問題文が書けた、コードもデータセットも全部用意した。これでコンテストを開けるぞー!なんて、舞い上がってはいけません。必ず「問題文の校正」を行いましょう。

「え?日本語の問題文だし、必要ないでしょ」なんて思った人、あまいです。
いくら、自分が良いと思う問題文を書いたつもりでも、他の人が見てみたら全然問題の意味がわからなかったとか、実は入力の制約やサンプルの値がちょっと違ってたみたいなことがよくあります。いくら見直しても足りないくらいです。

そんなことがないように、しっかり校正を行いましょう。ここでオススメしたいのが、「Google docs」です。JAGでも、docsを使用していて、複数人による問題文校正に向いていることがわかっています。
例えば、以下のような感じで校正をしています。

f:id:Respect2D:20141202054142p:plain

図の左側は、pukiwiki等で仕上げた初稿の問題文をコピーしてきたものです。右側は、コメント欄です。docsでは、図中のように、ある選択された領域に対する「コメント機能」があります。これが校正のときに非常に便利で重宝します。また、図中の伊織ちゃんのように、あるコメントに対して返信することもできるので、docs上で議論を進めることも可能です。

それ以外にも、「提案モード」というものがあり、ある選択された領域を別の文章に変更するように提案することができます。図中の、置換:〜と書かれたコメントは、そのモードで書かれたものです。提案コメントに表示されているチェックボタンを押すと、その提案を採用することができます。

このように、docsを使用すると、複数人による校正をスムーズに行うことができるので、作問のときに進んで使ってみましょう。

最終段階

これで、本当にコンテストに必要なものが全て揃いました。作問は、最終確認の段階に入ります。最終確認とは、具体的に何をすればいいでしょうか。

まずは、本番のジャッジシステムでの動作確認が必要です。AOJやAtCoder、使うジャッジシステムは人それぞれだと思いますが、以下のようなことを必ず本番環境で確認しましょう。

  • 問題文が意図した通りに見えているか(文字化けの発生、コピーミスして問題文の一部が消えていないか等)
  • 想定解、想定誤答を投げて、意図していないレスポンスが返らないか (TLEを想定していたのにWAが出る、ACのはずがWAが出る等)。
  • メモリ制限、タイムリミット制限が正しい値になっているか。
  • 開始時間、終了時間、凍結時間、その他の設定が正しく行われているか(AtCoderだと、これらの設定メニューがあるので要チェック)。

他に簡単に確認できることとして、問題文の入力仕様と、入力検証器の仕様に不一致がないかの確認があります。例えば、問題文には1 <= A, B <= 100と書いているのに、入力検証器では0 <= A, B <= 100のチェックになっているなんてミスが、よくあります。このような些細なミスでコンテストが失敗することがあるので、最後の最後に入力チェックは忘れないようにしましょう。

あとは、コンテストが成功することを祈って、解説スライドを作成しましょう。コンテストが始まる前に作っておくと、コンテスト終了後にすぐ解説を公開することができるので、オススメです。ちなみに、コンテスト中にスライドを作ろうとすると、Clar対応等で忙しくて結局作れなかったなんてことがあります。

JAGに入ろう!(番外編)

ー 宣伝は忘れない ー

記事内容とは全く関係ないですが、JAGではスタッフを募集中です。問題バリバリ作りたいという人はもちろん!作問はできないけど、英語ができる人、オンサイトのスタッフとして参加したいという人も募集中です。興味のある方は、JAGのjoinページからメールを送信ください。
ICPCを引退した方も、ICPCに出場していなかったけど競技プログラミング好きな方も、是非JAGへ入って、現役のみんなを応援しましょう!
OB/OG会一同、歓迎します。

f:id:Respect2D:20141202063912p:plain

↑JAGのマスコットキャラクターです(嘘)。

おわりに

以上、競技プログラミングの作問の進め方でした。
いかがだったでしょうか。この記事が、これから作問しようと思っている方々のお役に立てればうれしいです。読んでいただいてありがとうございました。

明日のCompetitive Programming Advent Calendarの担当は、JAGで数々の問題を生み出してきたnodchipさんです。お楽しみにー。

Code Festival 2014 予選B

Welcome to CODE FESTIVAL 2014 予選B - CODE FESTIVAL 2014 予選B | AtCoder

久しぶりに記事書いてみます。

結果

4完 (4 AC / 0 WA)

  • A: 00:39
  • B: 04:26
  • C: 32:12
  • D: 83:06

CとD、書くの遅すぎる。
本戦進出圏内ですが、社会人は出られません。
社会は厳しい。

Problem A - あるピアニスト

2つintとって、maxするだけ。
ehaさんがAtCoder最速の9秒だったっぽいです。
さすが響のプロデューサーは違う。

Problem B - 歩く人

aiを順番に足して行って、K以上になったときの、(i+1)を出力すればいい。

Problem C - 錬金術

とりあえず、「S1とS2からN文字ずつ取る」という制約は抜きにして実装。

  • 文字列S1から貪欲に、S3に当てはまる文字を取れるだけ取る。
  • その後に、同じようにS2から貪欲に取れるだけ文字を取る。

上記の計算で、S3を作るためにS1から取り出した文字数をa1、S2から取り出した文字数をa2とする。
もし、(a1 + a2 != |S3|)ならばそもそもS3を作れないので、NOを出力。

あとは「S1とS2からN文字ずつ取る」という制約。
上記の計算後、a1かa2どちらかが大きい(もしくは等しいが、その場合はYES)。
大きい方が、文字を余計に使っているため、そっちから、文字が足りない方へ、a1=a2になるまで文字を譲ってあげればいい。
AからZまで見て、譲ってあげられそうな文字を譲って、それでもa1=a2にならないのであればNO、なるのであればYES。

Problem D - 登山家

昔同じような問題を解いていたっぽいのですが、この方法で解きませんでした(解いたことあるの忘れてた)。
PKU : 3250 - Bad Hair Day - Respect2Dの日記

↑の解き方覚えてない思考。
僕の解き方やってる人、他にいるんだろうか。

  • 1番低いやつは同じ高さ以外のものは何も見られない。
  • 2番目に低いやつは、1番目に低いやつを見ることができる。
  • 3番目に低いやつは、1番目に低いやつも2番目に低いやつも、同じように自分より低いものとして扱うことができる。
  • ...
  • i番目に低いやつは、i-1番より低いやつを全て同じように低いものとして扱うことができる。
  • ...

この考え方が最初に浮かんで、低いやつから順番に考えて消していけばうまいこと解けるんじゃね?と適当に考えて、とりあえずソート。

[3 2 1 2 3]という数列で考えます。
とりあえず、一番低いやつ(1)を処理。

f:id:Respect2D:20141026233717p:plain:w300

2以上から見たら、1はないものと等しく考えられるので、これ以降は1を飛ばして読めるようになります。
図中の矢印のように、これ以降は[1]の右は[3]、[3]の左は[1]であるように考えればよくなります。
(これによって、計算量を落とすことができる)

次に、2を処理。

f:id:Respect2D:20141026234147p:plain:w300

これで、2以下は考えなくてよくなって、[0]の右は[4]、[4]の左が[0]になる。

と大体こんな感じのやり方をしました。
うまく書けば、O(n)になると思っている(思っているだけなので本当かわからない)。
あ、ソートのO(n log n)を除けばです。

説明めっちゃ適当なので、詳しくはコードを読んでください。
Submission #258604 - CODE FESTIVAL 2014 予選B | AtCoder

TopCoderのプラグイン導入

いつも参考にさせていただいていたプラグインの導入サイトが見られなくて困っていたので、備忘録としてここに残すことにします。同じように困っている人は参考にしてください。

Arenaのダウンロード

まずは、Arenaのダウンロードを行う。以下のページから、直接Arenaのjnlpをダウンロードすることができる。直接開けない場合は、「TopCoder Arena」で調べれば出てくる。

https://community.topcoder.com/contest/arena/ContestAppletProd.jnlp

ContestAppletProd.jnlpを適当なフォルダに置いてから、実行&ログインする。

C++プラグイン (CodeProcessor+TZTester+FileEdit)

プラグインのダウンロード

Plugin紹介ページから

  • TZTester.jar
  • FileEdit.jar
  • CodeProcessor.jar

をダウンロードする。これらを適当なフォルダに入れる。

プラグインの設定

Arenaの上部メニューから「Options → Editor」を選ぶ。「Editor Preferences」というタイトルのウィンドウが開く。
「Browse」ボタンを押して、先ほどダウンロードしたTZTester.jar, FileEdit.jarのパスを追加する。
「Add」ボタンを押すと、「Enter Plugin Information」というウィンドウが出てくる。ここで、次のように各項目を入力する。

Name: CodeProcessor
EntryPoint: codeprocessor.EntryPoint
ClassPath: CodeProcessor.jarのパスを「Browse」で参照して追加

「OK」ボタンを押すと、「Editors」のメニューの中に今入力した項目が追加される。追加された項目の「Default」チェックボックスと「At Startup」チェックボックスにチェックを入れる。
「CodeProcessor」が選択された状態で、「Configure」ボタンを押すと、「CodeProcessor Configuration」というウィンドウが開く。
次の項目を記入し、「Configure」ボタンを押す。

Editor EntryPoint: fileedit.EntryPoint

「FileEdit Configuration」というウィンドウが開く。
「General」タブの「Enter directory to read/write problems to」に自動生成されるプログラムを置かせたいパスを指定する。このパスは、絶対パスもしくは、ContestAppletProd.jnlpが存在するパスからの相対パスで指定することができる。つまり、「./」と入力した場合、ContestAppletProd.jnlpと同じディレクトリに、プログラムが自動生成される。

「Code Template」タブに移り、Templateファイルを記述する。
筆者の場合は、以下のように記述している。

// ζ*'ヮ')ζ < 落とさないでくださいぃ...
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <algorithm>
#include <set>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cctype>
#include <climits>
using namespace std;

typedef long long ll;
#define foreach(itr,c) for(__typeof(c.begin()) itr=c.begin();itr!=c.end();itr++)

class $CLASSNAME$ {
public:
$RC$ $METHODNAME$($METHODPARMS$) {

}
$TESTCODE$
};
// BEGIN CUT HERE
int main() {
  $CLASSNAME$ ___test;
  ___test.run_test(-1);
}
// END CUT HERE

「$TESTCODE$」を書いておくと、サンプルをテストするプログラムを自動生成してくれるので、非常に便利。上記のようなmain文を書くことでテストを実行することが可能。
「// BEGIN CUT HERE」から「// END CUT HERE」までは、プログラムをTopCoderに提出する際に自動的に削除されるようになっている。提出してはまずいコードは、この中に書くようにすること。

Templateのコードが書けたら、「Save」ボタンを押して設定を保存する。「Close」ボタンでこのウィンドウを閉じる。

「CodeProcessor Configuration」のウィンドウで、さらに次のように入力する。

Processor Class: tangentz.TZTester

「Verify」ボタンを押して、foundが3つ出ていればOK。

以上で、設定は終了。
「Save」ボタンを押して、「Close」ボタンを押して、設定のウィンドウを全て閉じる。

使用方法

Arenaで解きたい問題を開く。
そうすると、設定時に指定したフォルダに、Templateのプログラムが自動生成される。
このプログラムをローカルで編集して、保存してから、ArenaでCompileを行うと、「BEGIN CUT HERE - END CUT HERE」部分を切り取ったコードがArenaにも読み込まれる。
ローカルでCompileして実行すると、サンプルをテストして、正しい結果が出ているか確認してくれる。

参考

Javaプラグイン

  • TODO: 書ければ

Competitive Programming Advent Calendar Div2013 Day 1

はじめに

どうも、2Dです。今日はICPCのコーチとして台湾に遠征に来てます。台湾の結果は、

  • 3位:東大のwakaba
  • 4位:京都大 YellowYell
  • 5位:東工大 FCCPC_alpha
  • 6位:筑波大 pipe.txt
  • 7位:会津大 oshieteZukky

という結果でした(順位は大学別順位です)。ちなみに、1位は、終了の1時間以上前に11問を圧倒的全完してしまったTwT514でした。

というわけで、台湾から「Competitive Programming Advent Calendar 1日目」の記事を書かせていただきます。
この記事では、当初の予定に内容を加えて、以下の2つの内容について書かせてもらおうと思います。

  • ACM-ICPC OB/OGの会の紹介
  • 競技プログラミング問題にみられるアニメ作品

1つ目のOB/OGの会の紹介については、簡単に宣伝させてもらおうと思います。一応、メインは2つ目の方です。台湾で急いで記事を作ったので、適当な部分もあるかもしれませんが、楽しんでいただければ幸いです。

ACM-ICPC OB/OGの会の紹介

f:id:Respect2D:20131201040103p:plain:w400
今回、アニメネタだけで終わろうと思ってたのですが、アジア地区も終わったということで、この場を借りてACM-ICPC OB/OGの会(ACM-ICPC Japanese Alumni Group、通称JAG)の宣伝をさせてもらいたいと思います。JAGは、ICPCの現役生たちがより良い成績を残せるようにサポート活動を行う、ACM-ICPCを引退した有志達によって構成される団体です。最近では、ICPCのOB/OGだけでなく、ICPCに参加していなかった方でも、団体に所属できるように変わりつつあります。

JAGの具体的な活動内容は、以下のようなものがあります。その年によって、活動内容は変更される可能性があります。

  • 国内予選に向けた「模擬国内予選」の開催
  • アジア地区予選に向けた「夏合宿」の開催
  • アジア地区予選に向けた「模擬アジア地区予選」の開催
  • 世界大会 or 国内予選に向けた「冬・春コンテスト」の開催
  • ACM-ICPCのアジア地区予選やオンサイトイベントのサポートスタッフ

JAGでは、主に次のような仕事があり、それぞれに担当を割り振り、プロジェクトを進めていきます。

  • プロジェクトリーダ:コンテスト開催のプロジェクトを代表で進めていきます
  • 原案者:新しい問題を考えます
  • 問題文作成者:原案の問題文にストーリーをつけます
  • 解答作成者:問題を解くプログラムを作ります (ここは皆さんが今までやってきたところですね)
  • 入力作成者:間違った解法が通らないように、強いデータセットを作ります
  • 英文校正者:問題文の英語が正しいかどうか校正を行います
  • 渉外:スポンサーやコンテストサイト(AtCoder等)と、メール等でやり取りを行います
  • オンサイトスタッフ:風船配り、印刷物運び、食べ物の買い出し、解説等を行います

JAGは、作問だけをやる団体と思われがちですが、作問以外にも活躍できる場がたくさんあります。問題を解くのは苦手でも、オンサイトを手伝って風船を運んでワイワイやりたいという人、英語が得意だから校正を手伝えますという人、そんな人も募集中です。もちろん、原案・解答作成バリバリやりたいという人、大歓迎です。

もし、この記事でJAGに興味をもたれた方は、JAGのホームページの入会申込ページから申込を行ってください。
アジア地区で残念な結果に終わり引退される方、ICPCに出たかったけど結局出ないまま社会人になってしまった方、是非この機会にJAGに入りましょう!JAGのメンバ一同歓迎します。

ただ、ICPCの参加権がまだあるという方は、現役でがんばって出場し続けてください。「どうせもう、ろくな成績とれないだろうから」と諦めてJAGに入ることだけはしないでください。私たちは、そんな方々でも活躍できるように、必死にサポートしていきたいと思っているので、どうか諦めず現役のまま頑張り続けてください。

JAGの紹介は以上です。
この記事に書かれていないこともたくさんあるので、是非JAGのホームページをのぞいてみてください。

f:id:Respect2D:20131201034122p:plain:w400

競技プログラミング問題にみられるアニメ作品

今回のカレンダー、どういう内容で書こうか迷っていたのですが、2Dということで競技プログラミングとアニメを絡めた感じの内容で書くことにしました。趣味丸出しなので、アニメ系が無理という方はここからは見ずに最後にとんでください。

さて、最近競技プログラミング界隈では、rimeという便利な作問ツール、AOJのコンテストシステムやAtCoder等ができて、プロコン参加者の方が気軽に問題を作成できるようになってきました。その関係で、いろいろな人が問題文を記述するようになり、非常に個性豊かな問題文が増えてきています。その中でも、代表として挙げられるのが、作問者が好きなアニメ・ゲーム等の作品の内容を盛り込んで書かれた問題文です。

ただ、いろいろなネタを問題文に入れても、プロコンはプロコンです。どれだけ問題を速く理解して解けるかを競っているので、必要のない部分はほとんど読み飛ばされてしまいます。作問者としても、ネタを入れてもそれに反応してくれなくて、寂しいことがあります。実際に解かなければならない問題自体が大切なので、反応してもらえないのは仕方ないですけどね。

そんなわけで、今回は、競技プログラミングの問題にどれぐらいアニメネタが盛り込まれていたかというのを実際に問題を挙げながら紹介したいと思います。ただ、僕が勝手にアニメネタだと思い込んで、間違えて紹介する場合もあるので、ご了承ください。あと、ここに挙げるものは、AOJの日本語問題のみです。

問題紹介

f:id:Respect2D:20131130124713p:plain:w300
アイドルマスターは、よく知られたアイドル育成ゲームが原作のアニメです。
僕がアイドルマスター好きなので、僕が作問した問題も結構多いです。

ゲームシステムに関する問題

以下の2問は、ゲームシステムをもとに作られた問題です。アイマスのゲームでは、3つのアピールパラメータがあります。ちなみに、AOJ 2434は、skyさんが書いたものです。skyさんも、アイドルマスター好きです。

高槻やよい

やよいは、僕のイチオシのキャラです。家が貧乏なので、金額の最小化とかの問題に登場させてあげると、やよいが喜ぶかもしれません。あと、高い場所が苦手だったりします。

双海亜美 & 双海真美

亜美と真美は、双子のアイドルです。2人で行うゲーム問題に登場させてあげるといいでしょう。今年の模擬国内予選の問題文はpesさんが書いてくれました。

菊地真

真は、自転車が大好きです。登場させるときは、サイクリングとかさせてあげるといいかもしれません。

萩原雪歩

雪歩は、かわいい天使です。人が入れるほどの穴を一瞬で掘ってしまうほどの穴掘り名人です。あと、犬が苦手なので、犬から逃げる問題とかに登場させてあげるといいかもしれません。


f:id:Respect2D:20131130130248p:plain:w200
f:id:Respect2D:20131130130239p:plain:w180
ラブライブは、最近アニメ化されて、爆発的に人気が出たアイドルアニメです。

アイドルマスターXENOGLOSSIAは、原作のアイドルマスターとは全く違った世界感で描かれたロボットもののアニメです。何故か、この作品において、アイドルとは隕石除去ロボットのことを指します。

μ’sがロボット訓練

アイドルつながりで、2つの作品をくっつけてしまおうとして生まれた問題がAOJ 2506です。u’sというグループが、BYDOLというロボットに乗って訓練する問題になってます。問題文作成は、ラブライブ好きの僕の先輩です。


f:id:Respect2D:20131130132348p:plain:w180

とある魔術の禁書目録のスピンオフ作品です。作品中では、いろいろな能力をもったキャラクターが登場します。

御坂美琴 & 一方通行

AOJ 1053で登場する彼女は、御坂美琴だと思われます。彼女の能力は超電磁砲(レールガン)です。さらに登場する、最も強力な超能力者とは、一方通行(アクセラレータ)という、ベクトル変換の能力をもつ能力者でしょう。この両者の能力名を合わせてタイトルを考えられてるみたいですね。

佐天涙子

佐天さんは、この作品では珍しく能力をもたないレベル0のキャラクターです。問題文の冒頭にも書かれています。問題名に、佐天さんの名前が使われているのも面白いですね。


f:id:Respect2D:20131130132738j:plain:w200
軽音楽部の女の子たちの日常を描いた超大ヒット作です。僕はみおをおしてます。でも、みんなあずにゃんが大好きでペロペロしてるらしい。

平沢唯

主人公の唯は、頭が悪いので、こんな登場のさせられ方をします。なかなかかわいそうな子です。ちなみに、問題文中で出て来る桜が丘女子高等学校は、作品中で唯が通っている学校です。


f:id:Respect2D:20131130134327p:plain:w300
人類がほぼ絶滅しかかっている未来の話。主人公のわたしちゃんと、現人類である妖精さんたちが巻き起こすドタバタを描いた作品です。

AOJ 2421は、僕の後輩のutisam君が書いた問題で、「人類は衰退しました」というタイトルをもじって作った、構文解析の問題です。問題文の始まり方が小説っぽくてよさげなのですが、問題文がやたら長くて、誰も寄り付きませんでした。残念。


f:id:Respect2D:20131130135211p:plain:w300
魔法少女アニメです。本当かどうかは、ご自身でご確認ください。

以下の問題は、2011年JAGの夏合宿のときに、京大チームが作成したセットです。素晴らしいことに、このセットの問題文は、全てまどかマギカネタで書かれています(10問分のストーリーを考えるのはかなり大変そう)。

AOJ 2310のように、グリッド入出力の問題でキュウべぇを登場させると、問題を解く人をイライラさせることができるので、オススメです。AOJ 2314の入力にも、実はQBという文字が隠れています。


f:id:Respect2D:20131130143730j:plain:w300
仮想空間を舞台とした新世代ゲーム、ソード・アート・オンラインをプレイする主人公。現実へ戻るため、生き残りをかけてゲームを進めていく物語。

「ソード」を「コード」に変えれば、ちょうどいいタイトルになったので、このネタでAOJ 2423を僕が書きました。


f:id:Respect2D:20131130145139j:plain:w150
逆境無頼カイジ1期の続編です。カイジでは、限定ジャンケン、Eカード、チンチロ、等のギャンブルゲームがいろいろ登場するので、それらを使って問題を作ると面白いかもしれません。AOJ 2363は、僕の先輩slipさん作の問題です。


f:id:Respect2D:20131130145228p:plain:w150
麻雀天才少年である赤木しげるの伝説を描いた物語。

AOJ 2422は、アカギで登場した透明牌混じりの麻雀、通称鷲巣麻雀を題材として作成した問題です。これは、僕の先輩のkioa先輩が作成しました。


f:id:Respect2D:20131130145737j:plain:w300
ラノベ原作。洋菓子専門店ストレイキャッツで働く主人公と女の子たち&猫耳少女の、ハートフルラブコメディ。

問題文中にも、ストレイキャッツの店名が出てきています。
作品のタイトルをそのまま直訳して、「迷い猫、走った」
ちなみに、アニメの第1話のサブタイが、「迷い猫、駆けた」


f:id:Respect2D:20131201014652p:plain:w150

これは、問題文の冒頭に書いてある通りの内容です。半額ベントーを求めて、超人的なバトルを繰り広げます。


f:id:Respect2D:20131201015038p:plain:w250
誰もが知ってる有名作です。
この問題のタイトルは、ドラゴンボールではなくドラゴソボールです。


f:id:Respect2D:20131130142525p:plain:w250
ERATOの方々が作られた、お姉さんがただ全探索を行うだけの10分ほどのアニメです。そのあまりのバカらしさから、Twitterでリツイートの嵐、数週間ニコ動のランキング上位にあがっていた程のすごい作品です。

AOJ 2425には、全探索お姉さんが登場します。これは、~shiokawaとtokoharuさんのセットのときの問題です。AOJ 2507は、僕の先輩のkioaさんが、そのままの問題を作りました。ただ、サイズは小さいです。

入力にネタが隠れている系

以下の問題の入力を見ていると、結構面白いです。
実は、アニメの作品名や、アニメのキャラクター名が入力に隠れています。アイマスのキャラクターの名前も隠れてるので、探してみましょう。

ライブ系

アニメ関係のライブやイベントについて、問題文を書いてみたり。
YOKARI TAMURAは、かわいい王国のお姫様です(AOJ 1086)。
AOJ 2285と2420は、アニサマを参考にして作りました。


f:id:Respect2D:20120405182057j:plain:w200
女子中学生たちの、少しゆるめのゆり展開を描いた作品。
この作品の自称主人公である赤座あかりは、主人公らしからぬかげの薄さで、アニメ中でもたまに透明になることがあります。そんな彼女は、うすしおが大好きです。

以下の問題だけ、TopCoderの問題です。TopCoderに登録しないと、問題を見られないかもしれません。


問題の紹介は以上です。本当は、AtCoderの方も調べたかったのですが、かなり時間がかかりそうなので、今回はこれぐらいにしておきたいと思います。また機会があれば、他にもどれぐらいネタがあったか調べてみたいと思います。

どうだったでしょうか。これらの問題を見て面白いと感じた方は、是非自分の趣味を入れた問題を自分で作ってみてください。それもまた、作問をするときの楽しみとなるでしょう。ただ、「問題文が長くなりすぎると、参加者に嫌がられる」ことがあるので、問題に関係のないストーリー部分は、必要最低限におさえましょう。これ大切。


終わり

ではでは、長くなってしまいましたが、以上2Dでした〜。

今日、日本に戻る予定です。この2週間、ICPCの会津大会、ベトナム大会、そして台湾大会に参加していた皆さん、お疲れさまでした。そして、観戦してくださった皆さん、応援ありがとうございました。

f:id:Respect2D:20131201025318p:plain:w500

明日、2日目 12/2 のAdvent Calendarの担当者さんは、

  • nodchipさん
  • kou_miyamさん

のお二人です。
お楽しみに!!