えびちゃんの日記

えびちゃん（競プロ）の日記です。

TTPC 2019 参加記

TTPC 2019 に参加してきました．

atnd.org

atcoder.jp

Day 0

前日入りして晩ごはんを食べた後うたた寝してしまい，夜寝られなかったのでこどふぉをやっていました．

Day 1

「Day 1」とか言って，"TTPC" は一日だけなんですけどね．

前日にこどふぉをやっていたので朝早く起きられませんでした（おばかさん？）．

会場に入り，しるにゃんを見つけたので，肩をとんとんしてほっぺにつんってするやつをしたらかわいい反応をしてくれました．

かわいい写真を撮りました．

HUPC のときと同じで，しるにゃんとそすうさお姉ちゃんとチームを組みました．

りあんさんの「わかるなぁ〜」を聞けたのでほぼ満足です．タグつけ忘れたけど．

こんてすと

おしゃべりしてたら開始ギリギリだったので，前回と同じでお姉ちゃんに A を任せて，えびちゃんが B，しるにゃんに C をお願いするやつをしました．

お姉ちゃんが A をやるだけと言って，提出欄コーディングをして WA を出して泣きそうになっていました，かわいそう．

B は正規表現でやるだけに見えたので Python でやりました． 一瞬ジャッジが遅くなったので，こどふぉで数回経験した「Python の正規表現で適当をすると TLE するやつ」を踏んじゃったかと思って焦ったけど無事 AC． えびちゃんはえらいので，提出言語を C++ に戻すのを忘れずにやりました．

お姉ちゃんが入力読み忘れに気づいて直して AC．お姉ちゃん泣きそうになってた．

D はゲームらしくて，お姉ちゃんと一緒に考察を進めます． 双子素数の年上だったらどうとか，7 が特殊だねーって話をして，結局 Nim に帰着できてやるだけじゃんってなりました．

お姉ちゃん「えびちゃん，Grundy 数が 0 のときどっち？」

えびちゃん「サンプルを見て，合う方です」

E を見たお姉ちゃんが「構築いやなんだけど」とか言ってえびちゃんに投げてきたので，えびちゃんががんばります． 誤読（というか無読）をしていて，各列・各行ごとに，mod N での値が distinct だと思ってやるだけだと思ってました（戦犯）．

しるにゃんの C，お姉ちゃんの D が通ったのがたぶんこの辺り？ 嘘 E を実装して，嘘に気づいてからしるにゃんにコーディングを譲る最悪をしてしまいました．

お姉ちゃんに読むのを任せつつ，しるにゃんと一緒に E の構築を考えてもらいました． 「偶数のときできるのかなぁ」とか「最悪 assert で調べるか」とか話してたら，えびちゃんが次のようにして構築できるのに気づきました．

0 1 2 3 4
1 1 2 3 4
2 1 2 3 4
3 1 2 3 4
4 0 0 0 0

0 1 2 3 4 を各行で作った後，左の行と下の列を swap するだけで気づいたのはコンテスト後でした（残念）． 実際はもっときたない実装をしてしまいました．

N が奇数のときに 0 から N-1 までの和が 0 と合同になるのには早めの段階で気づいてたんですが，偶数のときに構築できないことを証明できなかったので，puts("No"); assert(N % 2 == 0); をする一般的なテクをしました．

あと，N2 であるべきところに 0 を出力してしまっているのに提出直前にちゃんと気づいて直しました，えらいえらい．

F はグラフで，最小全域木（全域ではない）（木でもない）を求めるやつっぽい． 「フロー？ 最小費用流で...」とか言ったら二人に嘘と言われて悲しくなったんですが，えびちゃんも嘘だと気づいたので満場一致です（？）．

お姉ちゃんが DP でやるだけと思ってたらしいけどサンプル 1 で合わないっぽい？

ある点まで別々で，途中で合流して，ある点で分離するよくあるやつだねーってしるにゃんが気づいてくれました．各パートは空になりうるねーって言うとそうだねーって言ってもらえました．

で，合流までのコストを調べて，そこから配っていくといいねーってなって（その前にまたえびちゃんが嘘を言ったんですが，指摘してもらいました），分離した後のコストは逆辺のグラフを考えるとよくて，できたねーとなりました．

残りの二人が実装したくなさそうな感じを出しているのでえびちゃんが実装しました．

言うほど実装つらくなくない？ ところでサンプル 1 から合わないんですが．

お姉ちゃんの図と出力を比べるに，どうやら Dijkstra をバグらせてそう．えぇ...（困惑）． 最近グラフライブラリを更新したのでいろいろ用意できてないんですよね（おいおい）．

そこを直すとサンプルが合って，AC．えらいにゃん！

O はお姉さんのやつ．これは通さなきゃ．しるにゃんががんばって回路設計（？？）をしていて，「なんのコンテストなんだろう」とか言っていて，かわいそう．

4 ビットごとに区切って，256 倍する回路と，16 倍する回路と，0 から 15 の数を表す回路と，それらを合成する回路を作っていました．WA，どうして？

えびちゃんが気づいて，「実はこれ所望の回路になってなくない？」と言って直してもらいました．えびちゃんもえらいにゃんでしょ？ 直してもらって，AC．しるにゃんなでなで．

ところでえびちゃんの PC の電源がいきなり落ちてびっくりしちゃった．充電できてなかった...？ できてそうなのに...？ ちょっと不安．

J は，\(ax+by\) を考えたときに \(a\) と \(b\) を比べるとどうで... とか考えていたけどわからずにゃんこ．

I の数学の方がわかりそう？ シミュレーションしてみるけどつらそうで...．逆元を仮定できないから割り算できないのをちゃんと言えたのはえびちゃんえらかったはず？

K で MuriyarokonnNan を出力することはなさそうだよね〜って話をするけど，どちらにしても無理やろこんなんという気持ちに．

L は構文解析じゃん！ となるんだけど，これは解けない構文解析に見えたのでパス．チーム戦で構文解析に特攻しちゃうと幸せにならないことを経験的に知っているので（おいおい）．

N はこれ有理数とか無理数とか関係なくない？ と思っちゃって，なんなら整数でよくない？ とか思っちゃって，うーん．

「無理数リットル飲むの難しくない？」「濃度的な意味では有理数リットルの方が難しそう」「どちらにせよ決められた値を飲むのは不可能そう」「ところで分子の個数的な意味でつねに有理数なのでは？ 実質的には連続として扱ってるけど」...これは競プロの会話ではなさそう．

えー，M が一番解けそう？ 全方位木 DP？ えー，最初の木 DP パートはできるけど...

えびちゃんがつらそうにしてると，しるにゃんとお姉ちゃんがなでなでしてくれました．やさしい．

結局 M はわからなくて，コンテストおわり．にゃー...

f:id:rsk0315:20190903054941p:plain

（元ネタは HUPC のときの参加記を見てください．見てもわからないんですが．）

こんしんかい

う，えびちゃんのスマホの充電が無になっていますね...（ピンチ）．モバイルバッテリーがあってよかった．

えびちゃんがお願いしたえびちゃんピザをいただきました．おすしもおいしいね．

解説を聞いている間，すごいなぁすごいなぁと思っていました．頭よすぎの人たちなのでは？（それはそう）．

これすき．ところでなんで熨斗袋しゃんがいないんですか？ 泣いちゃいますが．

こんてすとで疲れちゃったのと，人が多くて頭がふらっとしちゃったので結局いつもの勢としゃべるやつをしてしまったんですが，それでも楽しかったので満足です．

すぬけさんに Scores つくってる人って認知されててわーいってなったりしました．

解散してホテルに戻った後はだいぶ夜ふかししてしまいました．

Day 2

えびふらいのしっぽちゃんはかわいい．

えびちゃんはおいしい．

そんな感じで終わって，帰ってきて，ABC に参加してレートを溶かしました． えびちゃんはまだまだ初心者なんですよね．

グラフライブラリを作り直したのでトポロジカルソートを貼るだけできずにバグらせました．泣きたかったです．

コンテスト中でも main() 内で適当をするよりもちゃんとライブラリを整備する気持ちで書いた方が，結局えびちゃん的にはよさそう？（競プロ向いてなくないですか？）

おわり

ねこねこ．

ところで睡眠に失敗しているんですが．