team omorisuJoe(@omochana2, @risujiroh. @xuzijian629)で参加して5位（オンサイト2位）でした！

もともとteam Girigiriで参加すると思っていたのですが、ぼく以外のteam GirigiriのメンバーはTTPC2019募集開始日からすでに相手を決めていたらしく、会場であたふたしていたらすごすぎる2人組に拾われてチームが結成されました。

コンテスト中のムーブをまとめて行こうと思います。問題としては、A, C, F, Hを担当しました。

A (1:18)

[Joe] 貢献度0を回避するために無理を言って担当させてもらった。問題文を5文字ぐらいしか読まずにコーディングしてたらT年以降の開催年を求めるところをT回目の開催年を求めてしまい、一度すべてを書き直した。

B (3:16)

[risujiroh] これ提出時点で3位だったらしい。はやすぎる

D (13:39)

[risujiroh] ぼくのCがWAだったのでとりあえず先にやってもらった。

E (31:45)

[risujiroh] Cが永遠に通らないので先にやってもらう。

C (41:44)

[Joe] あまりにも合わないのでomochana2くんに投げようと思って問題を解説していると、 $a_i \le X$ の条件を見落としていることに気づいて発狂する。__builtin_clz(a)はa = 0のときに32が返ると思っていたら未定義動作っぽくて16000ぐらいの結果が返ってきてびびった。7 WAして戦犯になる。

G (1:48:26)

[omochana2] 1時間ぶりの進捗。いつの間にか解かれていたという感じでびっくりした。

F (2:03:33)

[Joe] あまりにも考察が進まないのでrisujirohくんにとりあえず考えたことを報告しているとグラフがDAGであることを告げられる。これまで担当している問題すべてで誤読していることに気づいて非常に厳しい気持ちになる。DAGだし愚直DPを考えてみると愚直DPができることに気づくので実装する。通る。

M (3:10:22)

[omochana2] 初め実装をぼくがするかみたいな流れになって、アルゴリズムを解説してもらっていたのだが、解説してもらっている途中によりシンプルな実装方針を提案したところomochana2くんが実装を継続することになり、通してくれた。全方位木DPは多分どちらかというと苦手な実装なので助かった。

O (3:42:11)

[risujiroh] 実装がだいぶ気合だったようで、正解かどうかパッと見でわからないし、ジャッジをすぐには書けなそうだったので提出デバッグするか〜という流れになった。WA連発するかなと思ったのに初提出から10分程度ですぐにACになってだいぶびっくりした (2 WA)。実装がうますぎる

H (3:59:03)

[Joe] UnionFind的な操作は見えるが、クエリ逆順とか先読みとかの方針でもなさそうなので、愚直に状態をマージできるかを考えると、だいぶ重いけどできることに気づく。Implicit Treapを改造すると、Priority Queueの機能追加版で上位k個の累積を好きなkに対して $O(\log n)$ 返せるデータ構造を作れるのだが（kが定数ならpriority_queueを2つ保持すれば実装できる。詳細はPrioritySum）、これをちょっとさらにちょっと改造して、Pをpriorityとして、Xの供給があるときに最大でどれだけ需要を満たせるかを効率的に求められるデータ構造を作った。これをUnionFindのノードに乗せてやればよい。実装の本質はPrioritySum部分だが、これは自分のもっていたPrioritySumを今回のpriorityに対応させるだけで済んだので実は実際の実装はだいぶ軽かった。

K (4:07:38)

[risujiroh] 初め、omochana2くんがFFTでは？という考察をしてくれて、risujirohくんと練っていたところ、bitsetでいけるのでは？という流れになり

int n; cin >> n;
string s, t; cin >> s >> t;
reverse(begin(s), end(s));
reverse(begin(t), end(t));
bitset<101010> a(s), b(t), mask;
if (a.count() != b.count()) {
    cout << "MuriyarokonnNaN" << '\n';
    return 0;
}

for (int k = 0; k < n; ++k) {
    int x = ((a ^ b) & mask).count();
    int y = ((a ^ b) & ~mask).count();
    if (y <= x) {
        return cout << k << '\n', 0;
    }
    bool t = a[n - 1];
    a <<= 1;
    a[0] = t;
    a[n] = 0;
    mask[k] = 1;
}

というすごい短いコードで一瞬でACしてくれる。この時間にしてオンサイトFAだったみたいです。

間に合わなかった問題

I

これ初提出が1:37:46でだいぶ序盤から考察されていた。結果的にrisujirohくんが序盤に高速化を諦めたのが吉だったみたいで、彼はその後さまざまな問題を通してくれたので助かった。ぼくがあとを継いでいたが、解説のように事前処理をしてO(Q)に落としこむ方法に結局もちこめず、積の中で $1 \le x \lt Q$ が何度現れるかをカウントする方針を高速化することを頑張ってしまった。

J

omochana2くんとrisujirohくんが終盤担当していた。答えが $x = 0, y = 1$ とした場合と $x = 1, y = 0$ とした場合の答えの線形結合で書けることをrisujirohくんがすぐに見出し、OEISしたり $O(N^2)$ の解法を二項係数とか使ってO(N)に落とせないか、という話をしている間にコンテストが終了した。だいぶいい線までいっていたようで(?)惜しかったなという気持ちになった

最後に

こうしてみてみると全員それなりに貢献できたんじゃないかと思う。序盤大量にWAを出してしまったことや誤読しまくったことや、コミュニケーション不足で気づいたらrisujirohくんもぼくもIを解いていた、みたいなことがあったが、自然と修正されて後半はかなりコミュニケーションがあった気がする。とりあえずオンサイト2位で非常にうれしいです。

楽しい問題を揃えてくれた運営の方々もありがとうございます。

そういや最近じ　ょ　え　た　ぷ　に　き　あ　く　ん　笑と対面で呼ばれる機会増えました。何？

う　し　た　ぷ　に　き　あ　く　ん　王　国　笑　っ　て　ど　こ　笑 pic.twitter.com/qi9NvAcels
— Joe@TTPC (@xuzijian629) August 31, 2019

Joeの精進記録

旧：競プロ練習記録

TTPC2019に参加しました