TTPC2015の運営

この記事はCompetitive Programming (その2) Advent Calendar 2015の$8$日目の記事です.

TTPC2015がどのように運営されていたかを書いていこうと思います.

メンバー

メンバーは以下の通りです

  • camypaper
  • tokoharu
  • piroz
  • shimomire
  • yosupo

体制

問題$1$つに$2$人,基本的には原案者と誰かもう$1$人がテスターにつくという形でやりました.

それぞれの問題には以下のようなものが用意されました(例外あり).

  • 問題文
  • 入力生成器(テストケースを出力するプログラム)
  • 入力検証器(テストケースが制約に沿っているかどうか判定するプログラム)
  • 出力検証器(出力された答えが正解かどうか判定するプログラム)
  • 想定解
  • 別解
  • 愚直解(あるいは嘘解法)

入力生成器や,検証器は主にtestlibが用いられました.

問題のテストはrimeからやろうという話になっていましたが最終的に以下のような体制になりました.

  • rime: tokoharu, piroz, shimomire
  • SOJ: yosupo
  • spica: camypaper

こういう体制になると,他の人がテストしたりしづらいのでやめましょう.

オンサイトイベント

Google社の泉さんにお願いしたところ快く引き受けていただけました.本当にありがとうございます.初めてのイベント運営ということもあり不手際が多かったかもしれません.以下のことはしっかりチェックしましょう.

  • 席はどれくらいか?
  • WiFiは使用可能か?
  • タップは足りているか?
  • 参加者はどこに集合させるか,どうやって会場まで誘導するか?
  • 飲食物やおかしはどうするか?
  • 会場側の制約で何か特殊なものはあるか?

活用したサービス

TTPC2015の運営において,基本的に活用されたのは以下のサービスです

  • Slack
  • Bitbucket
  • Google スプレッドシート

Slack

いわゆるチャットツールですが,TTPCは基本的に全てSlack上で進んでいたと言っても過言ではありません.以下のようなチャンネルが主に活用されました.

  • 全体連絡(#general)
  • 問題についての議論とか(#mondai_an,#easy_problem,その他各問題チャンネル)
  • 雑談(#random)
  • 会議(#日付-meeting)
  • 日程調整(#nittei-chousei)
  • Bitbucketとの連携(#progress)
  • clarの処理や,コンテストの実況(#clar,#jikkyo)

基本的な使用方法は,

  • あとで閲覧したい情報(重要な情報,問題概要とか)はpinする
  • 全体に伝えたいことは#generalに書く.
  • 問題案は#mondai_anに投げてとりあえずpinする
  • 簡単な問題は#easy_problemに投げる(難しい問題ばかり集まったので必要になった)

の$4$つです.これを繰り返して,問題案を集めてワイワイするイメージです.棄却されたものを含めると計$32$問ぐらい問題案はあったようです.

ある程度進んできたら全員でオンライン会議をするというのを繰り返していたのですがその日程調整には#nittei-chouseiが用いられました.使い方は空いている日かダメな日を適当に書き込むだけのガバガバさでしたが,人数が少なかったのでなんとかなりました.

Bitbucket

ソースコードホスティングサービスです.以下のように使われました.

  • ソースコードの共有
  • 解説スライドやデータセットの公開
  • Slackと連携してコミット時に通知

git力がなさすぎてブランチを切ったりは全然しませんでした.

通知機能は誰がいまどのくらい仕事をしているのか分かるのでとても便利でした.

Google スプレッドシート

表です.以下のように使われました.

  • 問題の難易度,ジャンルとかの一覧表の作成
  • 進捗チェックシート

いまどんなジャンルや難易度の問題が集まっているか$1$目でまるわかりだったので便利でした.チェックシートもどこまでできているかがわかるので便利でした.

所感

僕の思ったことです.当てはまらないところも多いかもしれません

  • 少人数で進める場合,$1$人あたりの担当範囲が広いので全体の様子が分からないということはまずなさそう
  • 問題案は集めまくって損することはないのでどんどん溜めたほうがよい.
  • C++以外の言語も書ける人がいると,他の言語だとどのくらいの時間がかかるのかも分かって便利
  • 問題のテストとかはサーバに投げたらいい感じにやってくれるみたいなのがあるととても便利そう
  • 直前でいろいろやろうとすると,体調不良になったりするので$1$日前にはやることがなくなっているようにすべき
  • 個々人で使うツール(例えば問題のテストツール)が違うのは本当にダメ
  • 誰か$1$人はものぐさでなく,外部とちゃんと連絡を取ったり会議の調整とか進捗を煽ったりできる人間がいるとよい

明日はnullさんの記事です.お楽しみに.

CODE FESTIVAL 2015 参加記

CODE FESTIVAL 2015に参加しました.時系列順の参加記を書きます.(コードは載せません).

7:30 起床

まぁ多少はね✌

8:30 出発

余裕を持って出発

9:00 ACアダプタを忘れたことに気づく

♨🏊♨

マスコットよりACアダプタを忘れないようにしましょう.

10:55 会場入り

どうでもいい話.このあと会場にいる人たちとだらだら話す.ネットワークの不調でΩ\ζ°)チーン.

12:40ぐらい コンテスト開始

A: やるだけやんけ.ホイ
B: 貪欲を感じる.怖いのでDPを書く.doubleで書いたらWA♨->思考停止decimalにする.AC🔥

C: 貪欲を感じる.怖いのでDPを書く.TLEしたので状態を一つ消す.AC✌

D: 区間スケジューリングを$k$回やればよさそうじゃない???みたいな謎考察をする.冷える.放っておいてEへ.

E: $v$を突っ込んだときに,$-v$,-1,0,1,$v$にしかならなさそう.submitデバッグしながら適当に書く.AC.

D: もう一度Dを見る.stary sky tree + 全探索やんけ~~~~.AC

F: 考える.(´ε`;)ウーン…こういうのは地頭ゲーっぽい.捨ててGへ.

G: $N \leq 256$を見て区間DPを感じる.オイラーツアーを考えると区間と部分木を対応させるのは余裕でできる.兄弟達の値が昇順になるようにしないといけないところで悩む.今頂点$l$に着目しているときに,dp[$l+1$,$r$]で森を表せば良いことに気づく.デバッグしながら書く.AC.めっちゃ興奮した.

F,H: FとHを見る.Hはデータ構造問題?よく分からない.とこはるさんが,G通してすぐFを通している(これは実際にはもっと前から提出していろいろやっていたらしい)のを見てFへ.

F: 泥沼♨.

コンテスト終了6完37位.あと1問解きたかった…悔しい.

コンテスト後

sugimさんと一緒にけんしょーさんのトークライブを見る.
Saiko~ No Contesutoについてはsorry(atcoderに出すにはクソすぎる気がして頼みづらい)

最前列に移動してlaycurseさんのトークライブを見る.
作問の仕方が面白かった.サインをもらうのを忘れてた><

ごはん

寿司: ♨
カレー: ♨
だったので,肉巻きおにぎり,やきそば,おでんを食べた.主食チケット余ったのつらい.

エキシビション

よすぽくんを応援してた.おさけーさんが来てて面白かった.

チーム分け

みさわさんのチームだ.twitterアイコンは見たことがあるけど知らない人が多くて┣¨キ┣¨キしていた.

ホテルでホイ

sigma425さんとn_vipさんをご飯に誘う(焼肉チャレンジは最高).結局みんなでマックにいった.よすぽ部屋にみんなで入るのおもしろすぎでしょ.


2日目

余裕の起床.

朝プロ

middleに参加しました

C: 貪欲かDP?とりあえず飛ばす

D: 凸な形の細いところから削れば良さそう.実装したくない…

A: ソートしてホイ.なぜかWAする.適当に直してAC.$k$の下りいるのかなぁ…

B: ちょっと悩む.気づいたらライブラリをペタリ.なぜかWA♨.意味がなさそうと思ったところをいじって提出してAC.なんでや…

C: よくよく考えると$N$が奇数で,戦略を感じる.dequeを使った貪欲を書く.AC.

D: ┣¨ハマリ(◞‸◟)

21位.いまいちな成績.いろいろバグったからなぁ…

昼食

焼肉弁当的なアレを食べる.脂っこいのはダメ.LTか何かを逃して冷える.

りんごさんのトークライブ

きゅうりさんと一緒に見る.なんだこれは…

チーム対抗リレー

Iを担当した.見て1分でDPを感じる.適当に考察したら状態が落ちるDPでできた~と思う.書いたらTLEして♨♨♨.マジで頭が真っ白になる.みさわさんと交代してその間にいろいろな人と相談しながら考える.

なんとか直してAC.本当に戦犯になりそうで危なかった…

その後

hadroriさんたち(ここでは複数のhadroriさんを指す)とpirozくん,shimomireさん,sugimさんとご飯に行こうとなる.

気づいたら,hadroriさんたちは消えていたので,4人でご飯をしながらだらだら作問とかについていろいろ話して解散

まとめ

めっちゃ楽しかった.一方的にフォローされている人に話しかけられて雑な対応をしてしまっていたらそれは人見知りなだけです.本当にごめんなさい.

なんかめっちゃ生きる活力みたいなものが出たのでまた来年も出たい(次はスイーツバトルができる実力になりたいゾ)

もっといろんな人(スタッフの人々とか)と話したかったけど,できなかったのでそれはまた今度ということにする.

TTPC2015 J. 指さし 講評

問題

https://ttpc2015.contest.atcoder.jp/tasks/ttpc2015_J

解説

https://bitbucket.org/ttpc2014/ttpc2015/overview

想定解法

残り人数とサイズ$K$のサイクルのありなしでDPあるいは,残り人数と最大サイクルサイズでDPのどちらかです.

前者は$O(N^2)$,後者は$O(N^{2}log(N))$で解くことができます.

提出者の解法

前者と後者,どちらも結構多かったように感じました.

感想

いい感じに正答者が多くて嬉しいです.$O(N^2logN)$解をベースに考えていたので$150$点にしましたが,$O(N^2)$解のことを考えると$100$点でも良かったですね.正答率は低いけど,部分点もあるしそのせいですかね?$O(N^3)$解法とかもキッチリ落とせたし,テストケース作成も楽で最高でした.

正直OEISに載っているとは思いませんでした(全く探さなかった訳ではないですが,見つけられなかった).まさか$2$つパラメータがあっても引っかかるとは…

TTPC2015 H. 包囲 講評

問題

https://ttpc2015.contest.atcoder.jp/tasks/ttpc2015_h

解説

https://bitbucket.org/ttpc2014/ttpc2015/overview

想定解法

幾何+全探索です.

$2$点を結んだ線分上に原点がないならば三角形を作ればよいです.
線分上に原点があるときは.その線分で残りの点群を上と下に分けて上と下で三角形を作ってくっつけた四角形を作ればよいです.$O(N^3)$でできます.

提出者の解法

幾何+全探索よりも偏角ソートしてDPが多かった印象です.全くもって想定外の解法でした.

よくあったミス

幾何+全探索の人は、線分と点の交差判定が間違っている人が多かったように見えます.同じ直線上に載っているかどうかを判定するだけではダメです.

よく引っかかったケース

原点を通るある直線上に全ての点があるケースや,原点を中心とする正方形のみからなるケース,原点の周りに原点を線分上に含む点が2点だけあり残りの点はランダムにバラまいたケースで落ちている人が多かったと思います.

感想

思った以上に解かれませんでした.答えが三角形か四角形になるという考察が思ったより難しかったのかもしれない.$100$点問題で幾何というのも敬遠された原因かな?ライブラリを持っていない人にはとても厳しい問題だったかも.

evimaさんの言うとおりWAが大量に出ていて手は出しづらかったかもしれない.想定解法までたどり着くとバグらせる要素が(ほぼ)ないので,人々がなんでこんなにWAを出すのか本当に分からず頭を抱えていました.

やっぱり考察が重かったかも?サンプルに四角形が答えになるケースは入れておいたが…

幾何問題は本当に全然解いたことがないのにこの問題を作ったので他の解法を作ったりができず結構不安だった.テストケースもどんなものを用意するかイマイチ分からなかったので思いつくケースをとにかく突っ込んでしまった.少ない数のテストケースでありうる嘘解法を撃墜するようなケースを網羅するのは本当に難しい.

想定解法までの考察パートはやや重め,実装は幾何にしては非常に軽い問題で,16問セットの中でもいい存在感のある問題だと個人的には思っています.

TTPC2015 C. おおおかやま 講評

問題

https://ttpc2015.contest.atcoder.jp/tasks/ttpc2015_c

解説

https://bitbucket.org/ttpc2014/ttpc2015/overview

想定解法

実装問題です.考察すると,ある長さの良い文字列は必ずある答えになることが分かります.長さを$100$から$3$まで動かして、$S$中に含まれるものをまとめて変えるととても楽に実装ができます.$O(|S|^{2})$でできます.

提出者の解法

問題文通りにやっている人がほとんどでした.予想通りです.賢くやっている人もそれなりにいたので結構嬉しいです.

感想

面倒なやるだけ問題として解くか,考察を続けて楽な$O(|S^{2}|)$解で解くかという二択の問題になっています.実装が得意な人は前者で解いて大丈夫だと思いますが,不安な人はもう少し考察を続けても良かったと思います.個人的には面白いバランスの問題になっていると思っていて結構気に入っています.

テストケースは若干弱かったようです.こういう問題のテストケースを作るときは境界っぽいところはちゃんと作らなくてはダメですね.

TTPC2015 まとめ

TTPC2015でwriterをやりました.とても楽しかったです.全部を振り返ると無限時間かかりそうなので,当日だけの話をします.

8:30 起床

おきました.

10:20 六本木到着

くりんぺさんはオンサイト参加者ではなかったし,多分別人物です.

10:30 六本木ヒルズ森タワー到着

よすぽくんときゅうりさんとおいしく朝ごはんを食べました.pirozくんとshimomireさんと合流し(とこはるさんは体調不良のためおやすみ),きゅうりを残してスタッフは会場入り.sorry きゅうり.
このあとG社の人と会場のシステムについて聞く.むずかしい.

12:10 受付開始

受付を始める.ちゃんと余裕を持って来ている人がいてよかった.(特に理由のない)遅刻はダメ.エレベータで会場のフロアに送る仕事をする.これが大変だった(特に大変ではない).

運営の不手際sorry.バタバタしていて本当に余裕がありませんでした.許してください.何でもはしません.

13:00 コンテスト開始

しません.(特に理由のない)遅刻と連絡なしのドタキャンはやめて.

13:15 コンテスト開始

ちょうどevimaさんをエレベータで送ったとこだった.遅刻はダメ.

13:30 受付終了

控えめに言って疲れた.この時点ですぬけ(rng_58)さんがJ(僕が原案の問題)を通していてヒエッとなった覚えがある.

14:30 1時間ほど経過

ちょっとみんなプロすぎない???250点問題もまばらに正解者がいる感じで,いい感じだった.C問題(僕が原案の問題)は皆思考停止やるだけで解いていた.H問題(僕が原案の問題)は開始から30分ぐらいにまーすさん,すぬけさん,lyozさんから提出があった.まーすさんはWA,すぬけさんがACでFA,lyozさんはTLEだった.すぬけさんの解法が想定解と違って焦る.

15:10 2時間ほど経過

全完の危険を感じ始める.Jがバカスカ通される一方HにあまりACが出ず申し訳なくなる.想定解を知っているからか,人々がなぜWAを出すのかまるでわからなくて困る.そもそも想定解じゃない方法で解く人が多すぎて焦る.

15:45 お菓子

交代のときにshimomireさんにお願いしてスタッフのご飯とコンテスタント用のお菓子を買ってきてもらう.お菓子を食べた人はアンケートに答えるか参加記を書くかどちらかはやってください.どっちもやるとよりグッドです.オンサイトによすぽのお金で買ってきた焼肉はないです.もち最中はとてもおいしかったそうです.スタッフルームでJの解説を書く(といってもO(N^2)解の説明を書くだけ)

16:20 3時間ほど経過

全完はともかくとして誰かP正解してくれ頼むという感情が芽生え始める.

17:10 4時間ほど経過

P問題が解かれるのかどうか,ドキドキタイムが始まる.順位表の動きもそろそろ落ち着いてきた?

18:00 4時間40分ほど経過

すぬけさんしかいない.解説の統計を書くのがとても困った.Pが解かれる気配がない.

18:15 終了

おつかれさまでした.

18:30 解説開始

タッチパッドの効かない僕のPCを使って解説をした.完全にミス.

19:00 参加者解散

おつかれさまでした.最高のコンテストでしたね.

20:00 スタッフ撤収

おなかがぺこぺこでした.

このあとの話はだらだら帰っててきとーなことをつぶやいていただけです.

HAPPY DAY 解説

問題

概要

グレゴリオ暦の2015年において、日の数字和が月の日付と等しい日がいくつあるか数えよ.

解説

スライドをご覧ください.

https://onedrive.live.com/redir?resid=814464FFDDC244AC!51726&authkey=!ADJod29NAPCaw_g&ithint=file%2cpptx



Bubble Cup8 Finals F. Bulbo

問題

概要

はじめ位置$x$にいて,$N$回のイベントがある.
イベント前にある整数座標上の点に移動できる.移動した距離だけコストがかかる
各イベントごとに区間$[l,r]$の整数座標の点が光る.
光っている点のうち,現在位置ともっとも近い点までの距離だけコストがかかる.

コストを最小化せよ.

制約

  • $1 \le N \le 5000$
  • $1 \le x \le 10^{9}$
  • $1 \le l \le r \le 10^{9}$

解法

値の取りうる範囲は広いが,実際に訪れる必要があるところは少ない.
座標圧縮する.

次に各イベントごとに,$dp[i]=$ある位置$i$にいるときの最小コストとしてDPを行う.
遷移はある位置$i$から$i+1$に移動する遷移と,$i$から$i-1$に移動する遷移と,$i$に留まるという遷移の繰り返しで表せる.
ここで往復するのは意味がないので左から右に向かう遷移と,右から左に向かう遷移を別々に試す.

その後,点灯する区間と位置までの最短距離を加算してやればよい.

計算量は$O(N^{2})$.

コード

テンプレート部,ライブラリ部は省略する.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
public class Solver
{
public void Solve()
{
var n = sc.Integer();
var p = sc.Integer();
var xs = new List<int>(); xs.Add(p);
var L = new int[n];
var R = new int[n];
for (int i = 0; i < n; i++)
{
var l = sc.Integer();
var r = sc.Integer();
xs.Add(l); xs.Add(r);
L[i] = l; R[i] = r;
}
xs = xs.Distinct().ToList();
xs.Sort();
var dp = Enumerate(xs.Count, x => 1L << 50);
dp[xs.BinarySearch(p)] = 0;
for (int i = 0; i < n; i++)
{
for (int j = 1; j < xs.Count; j++)
dp[j] = Math.Min(dp[j], dp[j - 1] + xs[j] - xs[j - 1]);
for (int j = xs.Count - 2; j >= 0; j--)
dp[j] = Math.Min(dp[j], dp[j + 1] + xs[j + 1] - xs[j]);
var l = xs.BinarySearch(L[i]);
var r = xs.BinarySearch(R[i]);
for (int j = 0; j < xs.Count; j++)
{
if (j < l) dp[j] += xs[l] - xs[j];
if (r < j) dp[j] += xs[j] - xs[r];
}
}
IO.Printer.Out.WriteLine(dp.Min());
}
static T[] Enumerate<T>(int n, Func<int, T> f) { var a = new T[n]; for (int i = 0; i < n; ++i) a[i] = f(i); return a; }
}

まとめ

座圧してDPするだけだけど,ちょっと考えてしまった.

Bubble Cup8 Finals H. Bots

問題

概要

2台のロボットがある.
$2N$ターンのうちどちらかを$N$ターン,もう一台を$N$ターン動かすという処理を行う.
各ターンごとの状態数の総和を求めよ.

制約

  • $1 \le N \le 10^{6}$

解法

ナイーブにやってOEISに投げたら解けてしまった.
順列とその逆元を$O(N)$で構築して投げる.

コード

テンプレート部,ライブラリ部は省略する.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Solver
{
public void Solve()
{

var n = sc.Integer();
ModInteger ans = 0;
var table = new ModTable(2000050);

n += 1;
ans = 2 * table[2 * n - 1];
ans *= table.inv[n] * table.inv[n - 1];
IO.Printer.Out.WriteLine(ans - 1);
}
}

まとめ

OEISは偉大

Bubble Cup8 Finals D. Tablecity

問題

概要

2行1000列のグリッドがある.このグリッドのどこかに泥棒がいる.

泥棒の初期位置は分からないが,2015ターン以内にこの泥棒を捕まえたい.

1ターンごとに泥棒は,右上,右,右下,左上,左,左下のどこかのマスに移動する.

1ターンごとに,ある2つのマスを指定できる.指定したマスに泥棒がいれば勝ちである.

解法

逃げられないようにするには2行どちらも抑える必要がある.
次に1ターンごとに泥棒のx座標は必ず1変化する.
すると,1,2,3,…..1000と見たあと,1000,999,….,1と見ると,必ず捕まえることができる.

簡単な証明:
泥棒の初期x座標が奇数のとき,1手ごとに泥棒との距離は2小さくなるか,変化しないかのどちらか.1000手以内に距離が必ず0になる.

泥棒の初期x座標が偶数のとき,1手ごとに泥棒との距離は2小さくなるか,変化しないかのどちらか.最初の1000手では捕まらないが,残りの1000手のどこかで距離が必ず0になる.

コード

テンプレート部,ライブラリ部は省略する.

1
2
3
4
5
6
7
8
9
10
11
public class Solver
{
public void Solve()
{

IO.Printer.Out.WriteLine(2000);
for (int i = 1; i <= 1000; i++)
IO.Printer.Out.WriteLine("{0} 1 {1} 2", i, i);
for (int i = 1000; i >= 1; i--)
IO.Printer.Out.WriteLine("{0} 1 {1} 2", i, i);
}
}

まとめ

output onlyのパズルのような問題.面白かった.