うにゅーん、って感じだ

だいたいのコンテストサイトで橙か赤です、よく C#を書きます。

yukicoder No. 1308 ジャンプビーコン　解説（tester 解）

yukicoder Advent Calender Contest

問題概要

問題ページを参照してください

yukicoder.me

この問題は Advent Calendar Contest 2020 の 5 日めの問題で、自分は tester をしました。 adventar.org

yukicoder.me

tester 解

まず、以下のような DP を考えます

DP[i][j]  := x_i まで訪問して今ビーコンが頂点 j にあるときのコストの最小値

このとき、DP の更新式は以下のようになります。

DP[i][j] = min_k( DP[i-1][k] + cost )
  cost := dist[x[i-1]][x[i]]  ( j == k のとき )
  cost := min( dist[x[i-1]][j], C + dist[k][j] ) + dist[j][x[i]]  ( j != k のとき )

これをそのまま実装すると {O(N^{2} Q)} になるため、高速化する必要があります（ここまでは yukicoder の方の解説に書いてあることと同様）。

上の DP の遷移をよく見ると、以下の値がわかっていれば遷移が減ることがわかります。

D[i][j]  := x_i まで訪問して、今ビーコンがどこにあっても良くて自分が頂点 j にいるときのコストの最小値

実際の遷移は以下のようになります。

DP[i][j] = min( DP[i-1][j] + dist[x[i-1]][x[i]], D[i-1][j] + dist[j][x[i]] )

ここで、D[i][j] は以下のように求められます。

D[i][j]  = min( min_k( DP[i][k] ) + dist[x[i]][j] ), min_k( DP[i][k] + C + dist[k][j] ) )

まだ {O(N^{2} Q)} のままなので意味がありません。

ここで D[i][j] に思いを馳せると、これは例えば以下のような問題と同等な最短路問題のような形をしていることがわかります。

あなたは N 頂点 M 辺のグラフで表される町にいます。

各頂点ではメダルが売られており、頂点 j で売られているメダルの値段は P_j です。
また、各辺には通行料が定められており、辺 j の通行料は C_j です。

各頂点 1, ... , N について、その頂点からスタートしていずれかの頂点でメダルを買う、という行動にかかる金額の最小値を求めてください。

この問題はどうやって解けばよいでしょうか。結論から言ってしまうと、これは全頂点を始点とする Dijkstra をすることで {O(M \log M)} で求めることができます（超頂点を用意し、その頂点から各頂点 j に対し長さ P_j の辺を張る、というように考えてもよいです）。

よって、D[i][j] も全ての j に対し {O(\log N)} で求めることができ、全体で {O(NQ \log N)} で求めることができました。

なお、解説で触れられている「遠回りをしてビーコンを設置することはない」という事実を用いて、最短路を x[i] に近づく方向にのみ更新することで {O(NQ)} にすることも可能です（想定解は {O(NQ)} でかつそもそもの定数倍がそこそこ重いため、C++ 以外の言語では {O(NQ \log N)} だと通すのは難しいと思います）（tester したときは {N, Q \le 5{,}000}, TL: 2 sec だったため、C++ でも {O(NQ \log N)} は通らなかった）。

ソースコードは以下です

{O(NQ \log N)}

yukicoder.me

{O(NQ)}

yukicoder.me

まとめ

全頂点を始点とする Dijkstra、よく考えるとそれはそうなんだけど始点を増やしても計算量が変わらないのは少し非直感的？

yukicoder で testlib を使うためのメモ

yukicoder

この記事は

この記事は yukicoder での作問において testlib を用いて簡単に正確な入力の検証、およびスペシャルジャッジ作成をしよう、という記事です。 また、ローカルでの作業に Rime を使うことを想定しています。

実際のコードについては以下を参照してください

github.com

testlib とは？

testlib は、Codeforcces の admin の MikeMirzayanov 氏が作ったライブラリ（C++ のヘッダーファイル）です。

github.com

codeforces.com

主に以下を行う際に便利な関数が含まれています。

  • 入力生成器 (generator) の作成
  • 入力検証器 (validator) の作成
  • 出力検証器 (checker / judge) の作成

入力検証器、出力検証器は作らなくても問題を出題することはできますが、問題を用意する際には必ず用意するべきだと考えています。

なぜ入力検証器が必要なのか

入力検証器とは、生成した（または手で作った）入力ファイルが入力フォーマットを満たしているかを判定するプログラムのことを指します。

競技プログラミングに参加する人の多くは C++ を使っており、問題の準備において writer / tester による想定解が C++ のみしか用意されない、ということも少なくありません。 ところで C++ の istream（std::cin 等）は半角スペース、改行等を自動で読み飛ばしてくれます。

よって、例え制約等は assert 等でチェックしていたとしても、以下のようなケースを検出することができません。 そして、そのようなケースで正常に動作しないような言語は存在するため、コンテスト中に指摘された場合は入力を修正してリジャッジを行う必要が出てきます。 （以下は全て実際のコンテストで遭遇したことがあります）

  • 行頭または行末に不要な半角スペースが含まれている
  • 問題文中では空白区切りで入力されると書かれているが、実際には改行区切りで入力される

なぜ出力検証器が必要なのか

出力検証器とは、提出されたプログラムの出力が正答であるかを判定するプログラムのことを指します。

基本的には事前に用意した想定出力との diff を取ることで判定することができますが、最近は多くのジャッジで不要な半角スペースや改行を許容するジャッジになっていることが多く、これはそのような判定プログラムを書くことで実現しています。 また、想定出力が複数あるような場合は単純な diff では判定できないため、その場合も判定プログラムを書く必要があります。

これも C++ 等で普通に書けば良いような気がしますが、以下のようなケースで正常に判定できないことがあります。

  • プログラムの出力が足りない場合
    • std::cin は EOF に到達した状態でさらに値を読んでもなんらかの値を返すため
  • 実数が出力されるべきところで nan と出力された場合
    • 実際に、誤差ジャッジにおいて nan と出力して AC となってしまったような問題が存在しました

現在 testlib に関する詳細なドキュメントは存在しません（上に貼った Codeforces のページが一番詳しく、それ以上の情報は実際の実装を読むしかありません）。

自分もそこまで詳しくはないので、誰か複数人で非公式 doc でも用意できればいいんですが……

Rime とは？

Rime は、JAG（日本の ICPC の OB/OG 会）が作成した、プログラミングコンテストの問題作成支援ツールです。 ドキュメントやブログ記事が詳しいので詳しくは以下を見てください。

github.com

rime.readthedocs.io

beet-aizu.hatenablog.com

なぜ Rime なのか

Rime 以外にも作問支援ツールは多く存在するため、特に Rime を使う必要はありません。他の作問支援ツールについてはいくつかは以下の issue で触れられています。

github.com

その中で、今回は以下の理由から Rime を用いました（別に他のツールでも良いと思います）。

  • 大学合宿コンテスト等の有志コンテストの準備においてよく用いられている
  • 他の作問支援ツールに比べて機能が多い

yukicoder で testlib を用いる

最近、yukicoder の環境で testlib.h が使えるようになりました（ありがとうございます！！）。

ただ、実際には testlib (or Rime) で想定されている用い方と yukicoder の仕様が異なるケースも多く、そのまますぐスペシャルジャッジ等に使えるというわけではありません。

よって、この記事では以下を実現することを目的とします。

  • yukicoder 上で testlib を用いたジェネレータ、スペシャルジャッジ、リアクティブジャッジ、スコアリングジャッジを作る
    • バリデーターについては現状 yukicoder でバリデーターを登録する機能がないため、通常の AC コードの入力を受け取る部分を testlib に置き換えることで対応する必要があります。
  • yukicoder と Rime で同じコードでジェネレータ、スペシャルジャッジ、リアクティブジャッジ、スコアリングジャッジが動くようにする
    • ジェネレータについては、同じケースが生成されるようにする

詳しくは以下の README を参照してください！（あとでもう少し情報を追加するかもしれません）

github.com

各バケットに区間のindexを持たせる平方分割

結論

まぁ本質以外もちょこちょこ書きかえなきゃいけなくて結局そこでバグらせるんですが……

この記事について

この記事は、平方分割の簡単かもしれない実装方法を紹介するものです。

平方分割って何？ という人には、以下の 3 つの記事がわかりやすいのでおすすめです。

www.slideshare.net caddi.tech kujira16.hateblo.jp

（本当はこの記事でも平方分割についてわかりやすい包括的な説明をしようと思っていたのですが力尽きました…）

実装方法

多くの記事では、主に以下のような実装がなされることが多いです。

[TODO: ここによくある実装を書く]

ただ、どうしてもインデックスをいじりつつ更新等をしていくことになるため、実装が煩雑になったりバグの原因になったりすることが多いです。

例えば、区間更新、区間 Max を平方分割で解くときに、区間 Max のクエリに対し、区間の一部が被っているバケットについてはそのバケット内の全ての値を更新した上で Max を求め、区間に完全に包含されているバケットについては値の更新はせずに区間に対する更新を適用した上での Max を求める、と言った処理をすることになり、それをインデックスをいじっている中で行うのはかなりつらいです（個人の感想です）。

実装方針

ここで、以下のような実装をすることを考えます。

  • 問題を解く関数側では、とりあえずそのバケットに区間に包含されているかは全く気にせず全てのバケットに対し更新、計算を行わせる。
  • バケット側で区間との包含関係（全く被っていない、完全に包含されている、一部が被っている）を求め、それぞれに応じた処理を行う。

これはかなりセグメント木に似てますね。 実際に平方分割は、セグメント木が 2 分木なのに対する √N 分木と考えることができるので、同じような実装ができるのも妥当とも言えそうです。

具体的な実装

ここでは、区間 Add 区間 Min の以下の問題を例にコードを示していきます。

なお、この問題は遅延セグメント木などを用いることでより良い計算量で解くことが可能であることに注意してください。

onlinejudge.u-aizu.ac.jp

骨組み

今回は、平方分割 class sqrt_decomp の中に、1 つのバケットを表すような class bucket を用意します。

class sqrt_decomp {
  class bucket {
    int l, r;
    vector<int> v;

  public:
    bucket(const vector<int>& a, int l, int r) : l(l), r(r) {
      v = vector<int>(r - l);
      for (int i = 0; i < r - l; ++i) {
        v[i] = a[i + l];
      }
    }
  };

  vector<bucket> v;

public:
  sqrt_decomp(const vector<int>& a, int bucket_size) {
    v = vector<bucket>();
    for (int i = 0; i < (int)a.size(); i += bucket_size) {
      v.emplace_back(a, i, min(i + bucket_size, (int)a.size()));
    }
  }
};

更新クエリ

まずは更新を書いてみます。

a_l, a_{l+1}, ... , a_{r-1} に x を加算するクエリを考えます。

バケット全体が更新区間に含まれる場合

まず、そのバケット全体が更新区間に含まれている場合を考えます。そのとき、当然その区間の値には全て x が加算されます。 ただ、そのバケット内の値を一つずつ変更していくと結局全体の計算量 {O(NQ)} になってしまうので、「そのバケット全体にいくつ加算されたか」という情報を持っておくことにします。

int add_val;

void update_all(int x) {
  add_val += x;
}

バケットの一部が更新区間に含まれる場合

次に、そのバケットの一部が更新区間に含まれる場合を考えます。 この場合は、以下の 3 つの処理を順番に行う必要があります（演算の性質によっては一部の更新をサボれることもありますが、ここでは割愛します）。

  1. バケット全体に対する更新を適用する (reflect_update)
  2. 今回のクエリでの更新を適用する
  3. バケット全体に対する回答クエリで答えるべき値（今回は最小値）を求める (reflect_calc)

1 番でバケット全体に対する更新を適用したら、きちんと「そのバケット全体にいくつ加算されたか」を初期化することを忘れないようにしましょう。

vector<int> v;
int min_val;
int add_val;

void reflect_update() {
  for (auto& i : v) {
    i += add_val;
  }
  add_val = 0;
}

void reflect_calc() {
  min_val = INT_MAX;
  for (auto& i : v) {
    min_val = min(min_val, i);
  }
}

void update_partial(int l, int r, int x) {
  reflect_update();
  for (int i = l; i < r; ++i) {
    v[i] += x;
  }
  reflect_calc();
}

呼び出し方法

上で作った関数を呼び出せば更新クエリは完了です。

呼び出し元からはそのバケットとクエリ区間との位置関係は気にせず全てのバケットに対して更新を走らせて、実際にどういった更新を行うかは中で判定するようにすると、問題に応じて書きかえる部分がシンプルになるので楽だと思います。

int l, r;
void update(int s, int t, int x) {
  if (r <= s || t <= l) {
    return;
  } else if (s <= l && r <= t) {
    update_all(x);
  } else {
    update_partial(max(s, l) - l, min(t, r) - l, x);
  }
}

ここまで書いたコードを全て bucket class の中に放り込み、sqrt_bucket class の方に全ての bucket に対して update を走らせる関数を書けば変更クエリは完成です。

vector<bucket> v;
void update(int l, int r, int x) {
  for (auto& i : v) {
    i.update(l, r, x);
  }
}

回答クエリ

次に回答クエリ（今回は最小値）を書いていきます。

a_l, a_{l+1}, ... , a_{r-1} の最小値を求めるクエリを考えます。

バケット全体が回答区間に含まれる場合

バケット全体がクエリの区間に含まれている場合、予め計算した最小値に対し、バケット全体への加算を足し合わせればその部分の最小値が得られます。

int min_val;
int add_val;
int calc_all() {
  return min_val + add_val;
}

バケットの一部が回答区間に含まれる場合

バケットの一部がクエリの区間に含まれている場合、更新の時と同じように以下のような 3 つの処理を順番に行います。

  1. バケット全体に対する更新を適用する (reflect_update)
  2. バケット全体に対する回答クエリで答えるべき値（今回は最小値）を求める (reflect_calc)
  3. 今回のクエリの区間に対する答えるべき値（最小値）を求める
vector<int> v;
int calc_partial(int l, int r) {
  reflect_update();
  reflect_calc();
  int res = INT_MAX;
  for (int i = l; i < r; ++i) {
    res = min(res, v[i]);
  }
  return res;
}
実は…？

実は回答クエリにおいて必ずしもバケット全体に更新を適用する必要はなく、以下のようにクエリと被っている区間のみ一時的に更新を評価するだけでも良いです。

この場合、更新クエリが一部分に被ったときにのみしか更新が伝播しないため、上記の実装よりも若干高速になることが多いです。

vector<int> v;
int calc_partial(int l, int r) {
  int res = INT_MAX;
  for (int i = l; i < r; ++i) {
    res = min(res, v[i] + add_val);
  }
  return res;
}

呼び出し方法

更新クエリと同様に、クエリ区間との位置関係は気にせず全てのバケットに対してクエリを走らせる方針を取ります。

int l, r;
int calc(int s, int t) {
  if (r <= s || t <= l) {
    return INT_MAX;
  } else if (s <= l && r <= t) {
    return calc_all();
  } else {
    return calc_partial(max(s, l) - l, min(t, r) - l);
  }
}

ここまで書いたコードを全て bucket class の中に放り込み、sqrt_bucket class の方に全ての bucket に対して calc を走らせる関数を書けば回答クエリも完成です。

vector<bucket> v;
int calc(int l, int r) {
  int res = INT_MAX;
  for (auto& i : v) {
    res = min(res, i.calc(l, r));
  }
  return res;
}

提出例

以上のコードをまとめたものが以下になります。 コード自体は長いけど部分部分は簡単……？

class sqrt_decomp {
  class bucket {
    int l, r;
    vector<int> v;
    int min_val;
    int add_val;

    void reflect_update() {
      for (auto& i : v) {
        i += add_val;
      }
      add_val = 0;
    }

    void reflect_calc() {
      min_val = INT_MAX;
      for (auto& i : v) {
        min_val = min(min_val, i);
      }
    }

    void update_partial(int l, int r, int x) {
      reflect_update();
      for (int i = l; i < r; ++i) {
        v[i] += x;
      }
      reflect_calc();
    }

    void update_all(int x) {
      add_val += x;
    }

    int calc_partial(int l, int r) {
      reflect_update();
      reflect_calc();
      int res = INT_MAX;
      for (int i = l; i < r; ++i) {
        res = min(res, v[i]);
      }
      return res;
    }

    int calc_all() {
      return min_val + add_val;
    }

  public:
    bucket(const vector<int>& a, int l, int r) : l(l), r(r), add_val(0) {
      v = vector<int>(r - l);
      for (int i = 0; i < r - l; ++i) {
        v[i] = a[i + l];
      }
      reflect_calc();
    }

    void update(int s, int t, int x) {
      if (r <= s || t <= l) {
        return;
      } else if (s <= l && r <= t) {
        update_all(x);
      } else {
        update_partial(max(s, l) - l, min(t, r) - l, x);
      }
    }

    int calc(int s, int t) {
      if (r <= s || t <= l) {
        return INT_MAX;
      } else if (s <= l && r <= t) {
        return calc_all();
      } else {
        return calc_partial(max(s, l) - l, min(t, r) - l);
      }
    }
  };

  vector<bucket> v;

public:
  sqrt_decomp(const vector<int>& a, int bucket_size) {
    v = vector<bucket>();
    for (int i = 0; i < (int)a.size(); i += bucket_size) {
      v.emplace_back(a, i, min(i + bucket_size, (int)a.size()));
    }
  }

  void update(int l, int r, int x) {
    for (auto& i : v) {
      i.update(l, r, x);
    }
  }

  int calc(int l, int r) {
    int res = INT_MAX;
    for (auto& i : v) {
      res = min(res, i.calc(l, r));
    }
    return res;
  }
};

提出例です https://onlinejudge.u-aizu.ac.jp/solutions/problem/DSL_2_H/review/4879712/rian_tkb/C++17

抽象化について

せっかくなので抽象化して中身をいじらずに様々な問題に適用できるようにしたいのですが、平方分割は遅延セグメント木などに比べて自由度が高く、上手い抽象化方法が考えれらていない状態です。 上手い抽象化が出来た方はぜひ教えていただけると助かります。

類題

  • 区間代入区間 Min (AOJ)
  • 区間 Add 区間 Sum (AOJ)
  • 区間代入区間 Sum (AOJ)
    • 上のコードとほぼ同じようなコードで AC できると思います。
    • こちらも遅延セグメント木で解くことができます。
  • Range K-th Smallest (Library Checker)
    • 蟻本の平方分割の項に載っている問題です。が、制約がかなり大きいので通りません（かなり頑張って高速化をすれば通るかもしれませんが…）
    • 記事中では reflect_calc において「答えそのもの」を求めていますが、実は「答えを高速に求めるための情報」を求めるようにすることでより多様な問題に対応することができ、この問題もそのような問題の一つです。
    • この問題では「各バケット内の値をソートしたもの」を求めておくことで、「そのバケット内に x 以下の数が何個存在するか」という、クエリに依存する値を高速に求めることができます。
    • TLE ですがコードです https://judge.yosupo.jp/submission/25166
    • 素直に領域木を書いたりウェーブレット行列を使ったりしましょう。
  • HUPC2020 day1-G Freqs (AOJ)
    • Range K-th Smallest で用いた「x 以下の数が何個存在するか」というクエリに chmin, chmax, add で更新しつつ答える問題です。
    • そのバケット全体に chmin, chmax, add が飛んできても元の要素の順序関係が崩れないので、各要素に更新を伝播しなくとも二分探索で「x 以下の数が何個存在するか」を求めることができます。
    • そのバケットの一部分に chmin, chmax, add が飛んできたら、そのバケット全体を更新してからもう一度ソートしたものを再計算すれば良いです。その操作にかかる計算量は {O(\sqrt{N}\log{N})} で、一部分に更新クエリが被るようなバケットの個数は 1 つの更新クエリに対し高々 2 個なので、クエリあたりの計算量は {O(\sqrt{N}\log{N})} となり、間に合います。
    • バケット 1 つあたりのサイズに対して {\log} がかかるため、バケットサイズは 100 ~ 200 程度にすると速いです（計算量的には変わらないはず…？）。
    • コードです https://onlinejudge.u-aizu.ac.jp/solutions/problem/3170/review/4880051/rian_tkb/C++17
  • Range Chmin Chmax Add Range Sum (Library Checker)
    • segment tree beats で解けることで有名な問題です。
    • 上の問題のコードを少し変えるとこちらも解くことができます。
    • 「ソートしたもの」の他に「ソートしたものにおける累積和」を持っておくことで、「chmin, chmax により値が変わらなかったもの」の総和を {O(1)} で求めることができ、上の問題と同じ計算量で解くことができます。
    • コードです https://judge.yosupo.jp/submission/25173

AtCoder Text(cat) 傾向と対策

AtCoder IQ1

これは IQ1 Advent Calendar 2019 の 2 日目の記事です
adventar.org


これは 2019/12/02 当時の情報で、ここから更新する気はあまりないです。
ここには 103 問存在していると思います

AC 時の得点が一意である問題

答えが一意である問題

答えが一意でない問題

AC 時の得点が一意でない問題

答えが一意である問題

  • そんなものはない

答えが一意でない問題

ジャッジが正常でない問題

ジャッジが壊れている問題

ジャッジが用意されていない問題

その他

マラソンならば Text(cat) で AC できる？

その他

  • 一部の問題はジャッジが壊れて WA や IE しか出ない状態になっていたりしており（おそらく言語アップデートの影響？）、本来 Text(cat) で AC できるのにできないようになっている問題が存在する
  • Text(cat) の言語 ID は 2 種類存在する
    • 言語アップデート時に振り直されており、アップデート前は 17、アップデート後は 3027
  • Text(cat) で AC 可能な問題を探すため、全問題に対し Text(cat) の AC 提出があるかクローリングするプログラムを書いた
    • AtCoder への負荷を減らすため最低限 O(問題数) くらいの fetch しかしないようにはしているが、それでも問題数が多いのでどうしようかなとなっています

東京工業大学プログラミングコンテスト2019 (TTPC2019) の運営

AtCoder TTPC

東京工業大学プログラミングコンテスト2019 (TTPC2019) がどのように運営されたかを書いていこうと思います。
atcoder.jp

メンバー

主犯

  • riantkb

Writer/Tester

カッコ内は今回のコンテストで使用された問題における writer/tester 数

  • rickytheta (3/2)
  • riantkb (3/11)
  • noshi91 (1/6)
  • goodbaton (2/1)
  • abc050 (3/1)
  • mikit (1/1)
  • kcvlex (0/7)
  • arkark (1/1)
  • ninja7 (1/2)

オンサイトお手伝い

  • Ashurnasirpal
  • monman53

テストプレイ (OB)

  • camypaper
  • tokoharu

体制

Writer 陣のレートが低くなかったため、基本的には原案者がそのまま作問までやる方針になりました。
各問題 Tester は最低でも 1 人、基本的には 2 人以上つくようにして、また少なくとも 1 人は橙以上が Writer または Tester に含まれるようにしました。

全ての問題のテストは Rime を使って行われ、かつ全ての問題に対し testlib.h を用いた generator/validator が用いられました。

github.com
rime.readthedocs.io

Rime, testlib に対する知見がかなり溜まったので、そのうち余裕があったら何か記事を書くかもしれません（一生書かなさそう）。

みんなレートは高いんですが作問経験がほぼなかったので（しいて言うと自分が yukicoder で 15 問くらい作ったことがあるのと別の場所で作問のおしごとをしたことがあるくらい）、基本的に自分が問題準備のやり方を整備してみんなに準備してもらい、細かい問題文の修正などについては全て自分がやるようにしました（これは自分に半角英数字の前後は必ず半角スペースを開けたい、みたいなこだわりが色々多かったのも理由にあります）。

オンサイトイベント

tsukammo さんに多大なご協力をいただき、オンサイトイベントを同時に開催できることになりました。本当にありがとうございました！！！

atnd.org

活用したサービス

TTPC2019 において活用されたのは主に以下のサービスです

Slack

主に以下のようなチャンネルが存在していました。

  • #general, #random
  • #problem_idea（問題案の投下）
  • #meeting-日付（Slack 上でのミーティング）
  • #nittei_chosei（ミーティングの日程調整）
  • #github（GitHub へのコミットやコメントなどが垂れ流される）
  • #ci（Travis CI のテスト結果が垂れ流される）
  • #ttpc2019_0831（当日の連絡用）
  • #jikkyo（コンテスト中の実況）

問題案については最終的には 30 問ちょいくらいありました。

Google スプレッドシート

色々な用途で使用されましたが、一番大きく使用されたのは問題案整理だと思います。

#problem_idea に書かれた問題案をシートに書いて、難易度や推薦度などの投票をしていました（結局この投票はそこまで意味を持たなかったですが…）

f:id:riantkb:20190902005907p:plain

あとはテスター進捗状況を管理したりするのに使われていました。

GitHub

問題準備には GitHub のプライベートリポジトリが使われました。

実際の使い方としては、問題を 1 問準備するときはその問題用のブランチを master から切ってその中で準備をし、ある程度完成したら master にプルリクを飛ばす、というようにしていました。
問題文や制約の修正提案などはプルリクのコメントで行われていたような気がします（ほんまか？）。
ちなみにマージされる条件は定義されておらず、コンテストが終わってこの記事を書いている現時点でもマージされていません。

各問題の作業ブランチが分離しているためわかりやすく作業もしやすい反面、generator/validator を書いているときに他の問題からコピーしてこようとするときや、実際にサーバーに問題をアップロードするときなどに面倒だったので一長一短だったような気もします。

Travis CI

rime test を CI で回していました。
どうせ GitHub にコミットする前に手元でテストをするのでそこまで必要感はなかったのですが、Tester の中で PC のスペックが異なるときの実行時間計測などにおいて一つの指標になった（有用かは置いておいて）のでまぁあってよかったかなという気持ちです。

Google スライド

解説を書くのに使いました。
各々で同時に編集ができるので、各問題で別々に作ってあとでマージする手間が省けて良いと思います。
数式が書けないのと PDF にエクスポートする時に微妙に崩れるのが難点。

所感

  • 問題案は集めまくって損することはないのでどんどん溜めたほうがよい
  • Java, C#, Python あたりをそこそこ自由に書ける人がいるとよい
  • きちんとスケジュールを立てて計画的に準備すべき（TTPC2019 では失敗しました）
  • 誰か 1 人はものぐさでなく、外部とちゃんと連絡を取ったり会議の調整とか進捗を煽ったりできる人間がいるとよい
    • しかし、それが 1 人だけだとその人に仕事の 95% くらいが集中して危険



おまけ（大まかな流れ）

2月初め

TTPC Slack, GitHub リポジトリが作られる

ゴールデンウィーク

作問合宿（大学に集まって問題アイデアを出しまくる会）が開かれる
確か N法陣、Inversion Numbers of Tree あたりはこの時に作られた気がします

7月中旬〜後半

日程が決まる
オンサイト会場も決まる
コンテスト時間は 4 時間のつもり
この頃から毎週末に Slack 上で meeting を始める
問題の準備の仕方が確立する（やっと！？）

8月初め

オンサイトの atnd を公開し、参加者の募集を始める
丸 1 日くらいで埋まってウケる
参加者に銀冠がいてウケる

8/18 あたり

大まかな採用問題が決まる
問題準備とテスターをがんばる

8/25 あたり

採用問題に嘘が見つかり冷える
制約を変更することで事なきを得る
採用問題が確定する
死ぬほど問題文を修正する
テストプレイをしてもらったら虐殺セットであることが判明した
とりあえずコンテスト時間を 5 時間にすることにした

8/30

銀冠に 3 時間で全完される恐怖に打ち勝ち、セットの中で一番難しい問題を抜いて Next TTPC（この日に思いついた）を入れた
問題の順序がずれたので死ぬ気で修正する
なぜか麻雀をした

8/31

本番
胃が痛い
なんとかなってよかった