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つの内容について書かせてもらおうと思います。
1つ目のOB/OGの会の紹介については、簡単に宣伝させてもらおうと思います。一応、メインは2つ目の方です。台湾で急いで記事を作ったので、適当な部分もあるかもしれませんが、楽しんでいただければ幸いです。
ACM-ICPC OB/OGの会の紹介
今回、アニメネタだけで終わろうと思ってたのですが、アジア地区も終わったということで、この場を借りて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のホームページをのぞいてみてください。
- JAG ホームページ：http://acm-icpc.aitea.net/index.php?FrontPage
- JAG メンバー募集ページ：http://acm-icpc.aitea.net/index.php?Join
競技プログラミング問題にみられるアニメ作品
今回のカレンダー、どういう内容で書こうか迷っていたのですが、2Dということで競技プログラミングとアニメを絡めた感じの内容で書くことにしました。趣味丸出しなので、アニメ系が無理という方はここからは見ずに最後にとんでください。
さて、最近競技プログラミング界隈では、rimeという便利な作問ツール、AOJのコンテストシステムやAtCoder等ができて、プロコン参加者の方が気軽に問題を作成できるようになってきました。その関係で、いろいろな人が問題文を記述するようになり、非常に個性豊かな問題文が増えてきています。その中でも、代表として挙げられるのが、作問者が好きなアニメ・ゲーム等の作品の内容を盛り込んで書かれた問題文です。
ただ、いろいろなネタを問題文に入れても、プロコンはプロコンです。どれだけ問題を速く理解して解けるかを競っているので、必要のない部分はほとんど読み飛ばされてしまいます。作問者としても、ネタを入れてもそれに反応してくれなくて、寂しいことがあります。実際に解かなければならない問題自体が大切なので、反応してもらえないのは仕方ないですけどね。
そんなわけで、今回は、競技プログラミングの問題にどれぐらいアニメネタが盛り込まれていたかというのを実際に問題を挙げながら紹介したいと思います。ただ、僕が勝手にアニメネタだと思い込んで、間違えて紹介する場合もあるので、ご了承ください。あと、ここに挙げるものは、AOJの日本語問題のみです。
問題紹介
アイドルマスターは、よく知られたアイドル育成ゲームが原作のアニメです。
僕がアイドルマスター好きなので、僕が作問した問題も結構多いです。
ゲームシステムに関する問題
以下の2問は、ゲームシステムをもとに作られた問題です。アイマスのゲームでは、3つのアピールパラメータがあります。ちなみに、AOJ 2434は、skyさんが書いたものです。skyさんも、アイドルマスター好きです。
高槻やよい
やよいは、僕のイチオシのキャラです。家が貧乏なので、金額の最小化とかの問題に登場させてあげると、やよいが喜ぶかもしれません。あと、高い場所が苦手だったりします。
萩原雪歩
雪歩は、かわいい天使です。人が入れるほどの穴を一瞬で掘ってしまうほどの穴掘り名人です。あと、犬が苦手なので、犬から逃げる問題とかに登場させてあげるといいかもしれません。
ラブライブは、最近アニメ化されて、爆発的に人気が出たアイドルアニメです。
アイドルマスターXENOGLOSSIAは、原作のアイドルマスターとは全く違った世界感で描かれたロボットもののアニメです。何故か、この作品において、アイドルとは隕石除去ロボットのことを指します。
μ’sがロボット訓練
アイドルつながりで、2つの作品をくっつけてしまおうとして生まれた問題がAOJ 2506です。u’sというグループが、BYDOLというロボットに乗って訓練する問題になってます。問題文作成は、ラブライブ好きの僕の先輩です。
とある魔術の禁書目録のスピンオフ作品です。作品中では、いろいろな能力をもったキャラクターが登場します。
御坂美琴 & 一方通行
AOJ 1053で登場する彼女は、御坂美琴だと思われます。彼女の能力は超電磁砲(レールガン)です。さらに登場する、最も強力な超能力者とは、一方通行(アクセラレータ)という、ベクトル変換の能力をもつ能力者でしょう。この両者の能力名を合わせてタイトルを考えられてるみたいですね。
佐天涙子
佐天さんは、この作品では珍しく能力をもたないレベル0のキャラクターです。問題文の冒頭にも書かれています。問題名に、佐天さんの名前が使われているのも面白いですね。
軽音楽部の女の子たちの日常を描いた超大ヒット作です。僕はみおをおしてます。でも、みんなあずにゃんが大好きでペロペロしてるらしい。
平沢唯
主人公の唯は、頭が悪いので、こんな登場のさせられ方をします。なかなかかわいそうな子です。ちなみに、問題文中で出て来る桜が丘女子高等学校は、作品中で唯が通っている学校です。
人類がほぼ絶滅しかかっている未来の話。主人公のわたしちゃんと、現人類である妖精さんたちが巻き起こすドタバタを描いた作品です。
AOJ 2421は、僕の後輩のutisam君が書いた問題で、「人類は衰退しました」というタイトルをもじって作った、構文解析の問題です。問題文の始まり方が小説っぽくてよさげなのですが、問題文がやたら長くて、誰も寄り付きませんでした。残念。
魔法少女アニメです。本当かどうかは、ご自身でご確認ください。
以下の問題は、2011年JAGの夏合宿のときに、京大チームが作成したセットです。素晴らしいことに、このセットの問題文は、全てまどかマギカネタで書かれています(10問分のストーリーを考えるのはかなり大変そう)。
AOJ 2310のように、グリッド入出力の問題でキュウべぇを登場させると、問題を解く人をイライラさせることができるので、オススメです。AOJ 2314の入力にも、実はQBという文字が隠れています。
- AOJ 2310 Rose Garden Witch
- AOJ 2311 Dessert Witch
- AOJ 2312 Magical Girl Sayaka-chan
- AOJ 2313 Box Witch
- AOJ 2314 Scribbling witch
- AOJ 2315 Shadow Witch
- AOJ 2316 Mermaid Witch
- AOJ 2317 Class Representative Witch
- AOJ 2318 Set-constructing Witch
- AOJ 2319 Soul Gem Game
仮想空間を舞台とした新世代ゲーム、ソード・アート・オンラインをプレイする主人公。現実へ戻るため、生き残りをかけてゲームを進めていく物語。
「ソード」を「コード」に変えれば、ちょうどいいタイトルになったので、このネタでAOJ 2423を僕が書きました。
逆境無頼カイジ1期の続編です。カイジでは、限定ジャンケン、Eカード、チンチロ、等のギャンブルゲームがいろいろ登場するので、それらを使って問題を作ると面白いかもしれません。AOJ 2363は、僕の先輩slipさん作の問題です。
麻雀天才少年である赤木しげるの伝説を描いた物語。
AOJ 2422は、アカギで登場した透明牌混じりの麻雀、通称鷲巣麻雀を題材として作成した問題です。これは、僕の先輩のkioa先輩が作成しました。
ラノベ原作。洋菓子専門店ストレイキャッツで働く主人公と女の子たち＆猫耳少女の、ハートフルラブコメディ。
問題文中にも、ストレイキャッツの店名が出てきています。
作品のタイトルをそのまま直訳して、「迷い猫、走った」
ちなみに、アニメの第1話のサブタイが、「迷い猫、駆けた」
これは、問題文の冒頭に書いてある通りの内容です。半額ベントーを求めて、超人的なバトルを繰り広げます。
誰もが知ってる有名作です。
この問題のタイトルは、ドラゴンボールではなくドラゴソボールです。
ERATOの方々が作られた、お姉さんがただ全探索を行うだけの10分ほどのアニメです。そのあまりのバカらしさから、Twitterでリツイートの嵐、数週間ニコ動のランキング上位にあがっていた程のすごい作品です。
AOJ 2425には、全探索お姉さんが登場します。これは、~shiokawaとtokoharuさんのセットのときの問題です。AOJ 2507は、僕の先輩のkioaさんが、そのままの問題を作りました。ただ、サイズは小さいです。
入力にネタが隠れている系
以下の問題の入力を見ていると、結構面白いです。
実は、アニメの作品名や、アニメのキャラクター名が入力に隠れています。アイマスのキャラクターの名前も隠れてるので、探してみましょう。
ライブ系
アニメ関係のライブやイベントについて、問題文を書いてみたり。
YOKARI TAMURAは、かわいい王国のお姫様です(AOJ 1086)。
AOJ 2285と2420は、アニサマを参考にして作りました。
女子中学生たちの、少しゆるめのゆり展開を描いた作品。
この作品の自称主人公である赤座あかりは、主人公らしからぬかげの薄さで、アニメ中でもたまに透明になることがあります。そんな彼女は、うすしおが大好きです。
以下の問題だけ、TopCoderの問題です。TopCoderに登録しないと、問題を見られないかもしれません。
問題の紹介は以上です。本当は、AtCoderの方も調べたかったのですが、かなり時間がかかりそうなので、今回はこれぐらいにしておきたいと思います。また機会があれば、他にもどれぐらいネタがあったか調べてみたいと思います。
どうだったでしょうか。これらの問題を見て面白いと感じた方は、是非自分の趣味を入れた問題を自分で作ってみてください。それもまた、作問をするときの楽しみとなるでしょう。ただ、「問題文が長くなりすぎると、参加者に嫌がられる」ことがあるので、問題に関係のないストーリー部分は、必要最低限におさえましょう。これ大切。
終わり
ではでは、長くなってしまいましたが、以上2Dでした〜。
今日、日本に戻る予定です。この2週間、ICPCの会津大会、ベトナム大会、そして台湾大会に参加していた皆さん、お疲れさまでした。そして、観戦してくださった皆さん、応援ありがとうございました。
明日、2日目 12/2 のAdvent Calendarの担当者さんは、
- nodchipさん
- kou_miyamさん
のお二人です。
お楽しみに！！
