ICPC2019 Yokohama スタッフ参加記

ACM-ICPC」と書こうとしましたが、今は単に「ICPC」なのでした。
ブログ書くの久しぶりです。

もう大会から2週間経過しようとしていますが、気が向いたので参加記を書いておきます。

1日目

6時
起床。

8時前
横浜駅着。天気が良かったので、横浜駅から会場まで歩きました。画質悪くてわからないけど横浜の富士山スポットです。

9時
現地入り

9時〜12時
机に封筒置いたり、会場の養生したり、風船膨らませたりしました。

14時〜
練習コンテストで、プリンタの前に座って紙切れてないか確認したり、風船と印刷物を配ったりしました。
あとは練習コンテストの解散後に、会場の後片付けして、1日目は割とあっさり終了。


写真ないけどスタッフのみんなと中華街で食べました。
中華街は店が多すぎて、どこ入っていいかわからないけど、10人以上でいきなり突撃しても大体入れるから助かる。

23時
家に帰宅後、即就寝。

2日目

5時
起床。

7時前
横浜駅着。天気が良かったので、自転車で会場まで行くことにしました。
最初の30分、150円で走れます。
docomo-cycle.jp

7:45
会場入り。コンテストの準備しながら、頑張ってくれと願いつつ後輩チームの机を記念に撮影。

9時半
色々準備してる内に、コンテスト開始。
始まってしまえば、問題を読む暇はあまりなく、ひたすら印刷物と風船を運んでいました。

順位表を見ながら後輩を応援している様↓


みなさん、コンテストお疲れ様でした。

15時〜
コンテスト終了後、パーティ会場に作り変えるため、スタッフ総動員で会場の片付けが始まります。
PC・ディスプレイと机・椅子を全部片付けて、床のケーブル類の養生を剥がして、ケーブルを巻き巻きして、懇親会用の机配置して、という超大掛かりな作業が、スポンサースピーチや表彰式の裏で行われます。
片付けが終わった頃には、超ヘトヘトです。

片付けしている最中の写真を撮ろうと思ってたのに、片付けた後の写真しか残ってません。全てのケーブルを綺麗に巻いて、長さごとにカウントされています。
f:id:Respect2D:20191127232136j:plain

17時頃
パーティ。昔馴染みの人たちとたくさん会って喋れて楽しかったです。ヘトヘトだったけど。
いつものw↓

あとは最後に、Secretaries(ほぼJAGのOBで構成される団体でICPC運営の中心的存在)に入らないかと誘われました。
偉い人たちにヤンキー座りで迫られてしまい、Yesというしかありませんでした。

いえ、嘘です。自分から進んでです、多分。
自分は、学生時代にICPCがあったおかげでまともに生きられたと思ってるので、その恩返しの意味を込めて毎年JAGスタッフとしてボランティア参加してましたが、これからもゆるゆる続けていけたらと思っています。

22時〜
帰宅してお酒飲んで、あとはぐっすり寝ました。

11日目

Indeed社でICPCスタッフに参加した人たちの焼肉会に、blue_jamさんからいきなり声がかかったので神保町で肉を焼きました。

そしたら、酔った勢いでD氏と一緒に横浜大会のD問題のモノマネをやらされました。

f:id:Respect2D:20191127221929p:plain
icpc2019yokohamaD

自分の方は割といい出来なのではないかと思います。
楽しかった。

D問題のモノマネについてよくわからない方は、こちらをご覧ください。
darsein.hatenadiary.org

感想

ICPCのスタッフ、毎年すごく疲れますが、出身大学の後輩たちが頑張っているのを見たり、現役時代に精進し合ってた人たちと会って話したりしてると、来年もまた頑張ろうという気になれます。

来年も、立命からアジア地区進出できるといいな。

10/31 企業競プロ合同プロコン 参加記

今回、ドワンゴさんのオフィスで行われた「企業競プロ合同プロコン」という今まであまりなかった感じのイベントに参加してきました。
秘密裏に行われていて気になっていた人もいると思うので、参加記を書いておきます。
写真の1枚も撮って来ればよかったのですが、残念ながら何も撮ってないので文字だけの参加記です。

企業競プロ合同プロコンとは

複数の企業の競技プログラミング部で集まって、一緒にプログラミングコンテストの問題を解こうという試みです。
僕の知っている限りでは、これが2度目の開催だと思います。

略して「合コン」。

参加記

時系列順で書きます。

参加者募集

開催日の1ヶ月前くらいに、ドワンゴの社員の方(JAGスタッフで繋がりを持っている方)からTwitterにDMをもらいました。競技プログラミング部の方をお誘い合わせの上ご参加ください、みたいな内容で調整さんのリンク付きでした。
最近、弊社の競技プログラミング部はほとんど活動していなかったのですが、モチベーションを高めるという意味も込めて、普段あまり競プロをやってない人も含めて何人か誘っていくことにしました。

イベントの参加者は、最終的に10企業から40名ほど集まりました。

イベント開催直前

イベント開催当日、調整さんにチーム分けが発表されました。42人の参加者が4〜5人編成の10チームに分けられていました。

チーム戦なんてICPC以来だったし、チームメンバーには赤い人がいてまともに協力できるか不安だしで、結構緊張しながら会場に向かいました。

18:00 集合

集合時間の30分前に会場に到着してしまい、完全に暇を持て余していました。
某社の人々は、間違えて違うビルに行ってしまったらしく10人ぐらいでぞろぞろと20分頃にやってきて面白かった。

18:20 懇親会

ピザ・寿司などの食事を用意していただいていたので、他社の人たちと交流しながらいただきました。参加者の中には数年ぶりに会うような人も結構いて、懐かしさでテンションが上がりました。
そして、なんと、懇親会にはお酒まで用意されていました。コンテスト前に酒を飲んでいいものかと悩みましたが、チームメンバーはみんな飲んでたので僕も一緒になって飲酒。さらにテンション↑↑↑

19:00 コンテスト開始

コンテストの問題は、hackerearchの過去問が使用されました。下記のページから見られるので、気になる人は解いてみてください。
https://www.hackerearth.com/en-us/challenge/competitive/august-circuits-17/problems/

コンテストは以下のようなルールで行いました。

  • 同時にコーディングできるのは1人だけ(ICPCルールに近い)
  • 問題を読んだりコードを眺めるだけなら、同時に複数のPCを使用してよい
  • ライブラリのコピペはOK
  • コンテスト時間は2時間
  • 飲酒OK

問題は基本的にAtCoderなどと同じような形式で、問題のジャンルに偏りもなく、簡単な問題もあり難しい問題もありとバランスのよいセットだった印象です。また、問題セットの中には、誰でも取り組みやすい内容のマラソン問題が含まれていて、初心者でもアイデアを出したり何かしら協力のできる問題セットだったと思います。
良い問題セットを探してきてくれた運営の方には感謝です。

コンテスト中、僕は基本的に問題を読んでいるか、他の実装者のコードを見ながら指摘するかどちらかでした。久々にペアプロをして、ICPCに出ていた頃を懐かしむなどしました。

あとは、もっぱら酒を飲んでました。

実装を1問もできなかったのがちょっと残念。

21:00 コンテスト終了〜解説

僕のチームは、ABDEFGの6問と、適当なCの解を提出して終了して、全体では確か3位でした。
各チーム最低2問は解けて、全問題を解いたチームもおらず、最後の問題はどのチームにも解かれないという結果で、難易度的に見てもいいセットだったのではないかと思います。

コンテスト終了後は10〜15分ほど休憩で、休憩中は解法のトークで盛り上がり。
解説は、解けたチームが前に出てホワイトボードで行うという形式でした。

22:00 解散

解説終了後は少し雑談しながら片付けをして、次の日の仕事もあるので特に飲みにもいかずそのまま解散な感じでした。

帰り道で、一緒に参加した弊社の人たちに感想を聞いた感じだと、雑魚すぎて全く何もできなかったという声や、競プロに対するモチベーションがアップしたという声など、人それぞれでした。

モチベーションアップしたと言ってくれた人は、競技プログラミング部の活動を再開してコンテストの問題を一緒に解きませんか、という提案もしてくれました。イベントに誘ってよかったです。

個人の感想

社会人になるとオンサイトに参加することができるコンテストの数が一気に減ってしまうので、どうモチベーションを保っていいかわからなくなって、どんどん非アクティブになってしまう人も多いと思います。
しかし、こういうイベントが定期的に開かれていると、イベントで活躍するために日々の精進にも熱が入りやすくて良いですね。
今後もこのようなイベントが開催されるのであれば、是非参加したいと思います。
今回のイベントを企画してくださったドワンゴのみなさん、ありがとうございました&おつかれさまでした。

雑記

ここから下はまとめるの面倒だったので、イベントについて思ったことを雑に書いてます。

社会人限定のイベントについて

  • 学生に遠慮して普段の競プロイベントにこないような人も参加しやすい。
  • 学生に比べると、社会人はオンサイトイベントの数が少ないので、こういう場があるだけで嬉しい。

チーム戦について

  • チーム戦をできるイベントは貴重。モチベーションアップにも繋がりやすい。
  • チームの組み方によっては、本当に何もチームに貢献できずに終わる人が出そうなので、運営がチーム編成を考える場合は慎重になる必要がありそう。
  • あまりチームの人数が多すぎると手が空く人が出そう。多くて4人?

問題について

  • 非公式のコンテストのためにわざわざ問題を作るようなリソースはないので、基本的に過去問から問題を用意する必要があるが、参加者がみんな楽しめるような過去問を探すのが大変そう。
  • 問題セットの条件
    • 参加者が誰も解いたことがない
    • 低難度から高難度の問題が揃っているセット
      • 今回のように、初心者でもアイデアを出しやすいマラソン系の問題が入っているようなセットは結構いいかも。人によっては嫌いな人はいそうだけど。

参加者の募集について

  • 今回はTwitterのDMで知り合いの企業に参加を呼びかける形式だった。
    • ほぼ知り合いの集まりになるので、参加者のレベルを把握・調整しやすい。
    • 「え、合コンあったの?自分呼ばれなかったんだけど。」みたいな人が発生する。

懇親会について

  • コンテスト開始前に懇親会が開かれるという珍しい形式。
  • コンテストが始まる前に、チームメンバーと交流することができるので、こういうのもありかも。
  • ただ、コンテスト終了後に問題の解き方について他の人と話しながらわいわい盛り上がる時間がなくなってしまう。
  • 運営視点で見ると、コンテスト中に懇親会の片付けができる。

飲酒コーディング

  • 学生向けのコンテストではできない。

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