最近オンサイトに 2 つ参加したので。
学生選手権2023 決勝
会場が三田だったが、中高は関西にいた影響でつい「さんだ」と呼んでしまう。
配点が 3-6-7-9-9-12-16 なので 7 まで通したいなあと思ってコンテストを始める。
A - Apple Addiction
2 乗は自明だが、遷移の高速化にかなり詰まってしまった。 dp[i] - a[i] を持たせるのかとか色々迷走した結果、セグ木を 2 種類も使う謎解法になってしまった。 40 分もかかったのかなり痛い。
B - Max Degree Sum
A で詰まったのもあって、こちらの方が体感としては楽だった。 k までを赤色で塗って、他を青色で塗って考えると赤同士を結ぶ辺、赤青を結ぶ辺の順に貪欲をするのが最適で、それぞれで使える数が実は dsu を使えば管理できるという話。
着実に一歩ずつ考察を進められたのでスムーズだった。
C - Power Convergence
x^k と x-1 が互いに素なので x-1 が N の素因数をどれだけ持つかを管理すると f の値も分かるところまでは良くて、実験すると N の素因数の種類数が少ないときだけ重たい解法になった。というわけで埋め込みを考えたが、コンテスト終了までに埋め込みが間に合わなかった。
約数で包除みたいな形になるので、それをちゃんと詰めた方が良かったかもしれない。
スポンサーのプレゼンの間にもパソコンを回したら20分ぐらい遅れて通ったので A をスムーズに行ければ間に合った可能性がある。やらかし。
結果
44人 / 55位。 C を 6 割近くが通してるのもだけど解くのが遅かったのが良くなかった。反省。
懇親会
食事が豪華だった。春のトヨタと違って50人ぐらいしかいないのでたくさん食べられた。
Yu_212 さんに筑波大セットの tester ありがとうございますと言われた。木上を移動する問題の実装がかなり大変でしたと伝えたら「実装枠です」と返された。まあそうだよねーみたいな気持ちに。
Maspy さんに「LCの準備できてなくてすいません」と伝える。許してもらえた。
帰った後、 22:00 - 3:00 に Ucup Stage 3 に出た。疲れた。
TTPC2023
1 週間ぐらい前にキャンセル待ちで compass に参加申し込みをしたらキャンセル出て行けることになった。割と直前に参加申し込みしたのでチーム決めのツイートを探したら、 riano_ さんが探していたので組みませんかと連絡を送る。結局 riano_ さんと riantkb さんと組むことになった。
会場が六本木ヒルズのメルカリオフィスだった。豪華。景色もいいしタダの自販機もあって良かった。
チーム名を始めるまで決めてなかったが riano_mtbc という案が挙がったのでそれにすることに。
A から C ですぐ実装できるのがあれば僕が書きますということで始めた。後ろを見ているが割と難しそうだし、お二人とも悩んでいそうなので A から C も難しいっぽい。
L は半分全列挙ですね、とりあえず 15 点は取れますね。というところはすぐだったので軽く粘着していたが進捗がない。その間にお二人が A から C を通してくださった。感謝。
気分転換に M を見てみると P を hash でとって有理数 mod の累積和を使えば解けそう。「p, q <= 1e5 だから P は 2e10 よりデカくしたいので __int128 ですね」と主張してそうですねーになったけど p <= q だったので別に __int128 を使う必要はなかったらしい。(が、有名素数は落とすようにしてたらしいのでラッキー)
あとは適当に書いて AC 。
H をみると LCP + SA で解けそうな見た目をしている。サンプル 2 の aba みたいなケースで a を正確に数えるのが少し大変で、特に今見ている index が元の文字列、 LCP 、 SA のどの index に対応するかが分からなくて頭が混乱した。こういうのをサクッと通せるようになりたい。
実装に詰まってる途中に riano_ さんから G の議論を確認してほしいと言われる。確かに式変形で綺麗な形になって、 prod(1-x^i) とか 1/(1-x)^n とかを高速に計算したい気持ちになる。
prod(1-x^i) がオイラーの五角数定理の主張なのでそれで行けませんかとなったが、有限項で prod を取ると次数が変わらないか？となった。が、実はそれで良かったらしい。しくじったー。
log と exp 使えば O(nlogn) なので 70 点は取れます。満点の線形時間は分からないです。と返して H の実装に戻った。もう少し G を見るべきだったかもだが、負の二項定理の話を知らなかったので結局無理だった可能性はある。
後は L の 15 点を回収した後に K を考えるが難しい。 20 点を取れそうな実装は思いついたがバグらせて時間切れ...
解説を開くと途中で riantkb さんが出した解法で 20 点は取れていた。やってしまった。
結果
15 位。そこそこチームに貢献できたかな？割としっかり考えられて良かった。
懇親会
去年の UTPC 運営に今度の UTPC の writer をしたいですと打診する。全体的に人手不足らしく歓迎ですと言われた。嬉しい。
恵比寿のサイゼリヤで打ち上げをした。楽しかった。
帰った後、 23:00 - 3:00 に Ucup Stage 5 に途中参加した。疲れた。
帰りに六本木ヒルズを出たら東京タワーが見えて驚いたが、そういえば S セメの間に大学の友人とこの周辺を散歩していた。懐かしい。
