ARMERIA

Rubyと競技プログラミングの話　AtCoderやCodeforcesの問題解説記事が多め。

TTPC2019 オンライン参加記

プログラミング競技プログラミング AtCoder

f:id:betrue12:20190905012051p:plain

てんぷらさんとチームpurameriaで出場しました。オンライン参加でしたが、せっかくのチーム戦だったので記事を書こうと思います。

はじまり

アルメリアさんへ
TTPCチーム組みませんか
てんぷら
— てんぷら (@tempura_cpp) August 1, 2019

ご指名いただきました。やったー！

本番まで

特に何もしていなかったのですが、コンテストでてんぷらさんが異常パフォーマンスを出す一方で私は停滞していたので内心（こんなんでチームメイトが務まるのか…）と焦っていました。

有志コンで要求されそうなちょっと強いライブラリをこっそり整えたりしていました。結局使いませんでした。

今日は帰ったらAho-Corasickを書きたい
— アルメリア (@armeria_betrue) August 26, 2019

HL分解とかそろそろ書いておいたほうが良い気がしている
— アルメリア (@armeria_betrue) August 28, 2019

前日

チームアカウントを作ったらてんぷらさんが魔改造しました。

TTPCはこれで出ます！よろしくお願いします！ pic.twitter.com/vT7oB7Vno5
— てんぷら (@tempura_cpp) August 30, 2019

プラメリアとプラナリアって似てるよね。トポロジー一緒だし。

コンテスト当日

SlackのDMで相談しながらやりました。1台実装ルールがちょっと難しいかな？と思っていたけど、ちゃんと宣言して書けば意外と困りませんでした。

A: めり（2:00）
B: ぷら（4:42）
C: ぷら（12:39）
D: めり（22:33）
E: ぷら（25:51）

までは流れで。私がFを考えててんぷらさんがGを実装し始める…も中々解けない。

f:id:betrue12:20190905001128p:plain

Fはこの後しばらく放置されることになります。てんぷらさんがサクっとGを通していました。

G: ぷら（58:37）

ここで私がIを誤読（戦犯）

f:id:betrue12:20190905001436p:plain

さらに誤考察がシンクロしてしまったのでIも放置することに。Mもほぼ解けているんですがしばらく放置されます。

f:id:betrue12:20190905001615p:plain

そんなこんなでしばらくACが停滞するんですが、私がFを考えている間にてんぷらさんが上のほうをバシバシ考察していました。

f:id:betrue12:20190905001936p:plain

L: ぷら（122:20）

ここでついにFをAC。結局わりと地道なDPを書きました（これは公式解法が天才）

f:id:betrue12:20190905002313p:plain

F: めり（129:59）

てんぷらさんがOのデバッグ、私は数え上げのJを考える…も糸口が掴めない。てんぷらさんに投げようと思う（正解）

f:id:betrue12:20190905002644p:plain

O: ぷら（169:20）

後回しにしてた実装キュー消化とてんぷらさんの考察により、ここで怒涛のACラッシュ。

f:id:betrue12:20190905003006p:plain

f:id:betrue12:20190905003156p:plain

J: ぷら（199:18）
M: めり（202:49）
H: ぷら（234:33）

Mはオイラーツアー＋区間加算セグメント木でゴリゴリと。Hは終了後に提出を見に行ったら動的セグ木の二分探索で解いていました。

ここで残りは「I - I hate P」「K - サーキュレーション」「N - 瓜二つ」の3問。Iについて私が $O(Q (\log R)^{2})$ を思いついたけど、てんぷらさんが $O(Q \log R)$ を思いついたのでそのまま実装してもらうことに。

f:id:betrue12:20190905003753p:plain

しかし制約が厳しい…

f:id:betrue12:20190905004135p:plain

てんぷらさんの移動中に私も小手先の改善をやってみたけど、因子 $0, ..., Q-1$ ごとに登場個数を数える方針だったので結局最後に $O(Q \log R)$ かけて累乗しなきゃいけないんですよね。きびしい。

終了10分前くらいに中国剰余定理というワードが出て、ダメ元で実装RTAしたけど時間切れ。後から考えると、素冪に分解したところで $P$ の逆元があるとは限らないから無理でした…

f:id:betrue12:20190905004707p:plain

結果

ということで結果は12完の2位でした！

よすぽさんがやばいけど全体2位なので満足、アルメリアさんありがとうございました！！！ pic.twitter.com/fkGgmiHdRV
— てんぷら (@tempura_cpp) August 31, 2019

知らない間にてんぷらさんが上のほうをバンバン考察していてビビりました。私の最大の貢献は簡単枠とされている（そして実際かなり通されていた）のに2人とも詰まっていたFを何とか通したことですね。それでいいのか橙コーダー。

私目線での反省はKをちゃんと考察して私が通すか、Hの実装を引き取っててんぷらさんにIを詰めてもらうか、ができればよかったかなと思います。でも1400点はたぶん取れてないでしょう…

私はチーム戦の経験はほとんどない（2回目）のですが、とても楽しかったです。通したり通してもらったりしたときにはいつも以上に嬉しいですね。

褒め合う文化すき pic.twitter.com/TbDGSKqC8Q
— アルメリア (@armeria_betrue) August 31, 2019

5時間15問、耐久レースかと思ったけどあっという間でした。問題も楽しかったです。運営の皆さん、てんぷらさん、ありがとうございました！