HUPC2020 2日目

一日目はこちら
yamadさん、とまとさんと yamad as a Serviceで出場しました。
yamadさんが助っ人サービスになる時代…
通した順に書いていきます。

内容

A

3秒くらいオーバーフローどうするんだろう…って悩んでいました。素直に0を出力するだけでした。

B

とまとさんがやりたくないーって少しバグらせつつもしっかり通してくださりました。問題文をチラ見しましたが、本当にやりたくない見た目をしていたのでスルーしました。ごめんなさい。

C

yamadさんが解けないーって言っていたので参戦しました。
二項係数っぽいとかいろいろいいながら、手計算でのケースまで計算し、OEISに投げた結果を見て「ただのDPじゃん！行列累乗じゃん…」と二人で反省しつつyamadさんが通しました。

G

気づいたら通っていました。とまとさんがダブリングとか言っていて、それをyamadさんが通したっぽい？これもB同様問題をチラ見だけしましたが、内容が頭に入ってこなかったのでそっとじしていました。

M

それぞれの頂点にあるグランディ数を求めるのに、かかるんですがbitsetで高速化できると思います、と考察をyamadさんに話したら通るはず、と言われたので書きますがWA。
内容を再び細かく説明するお、グランディ数はには収まらずくらいなので、bitsetの長さを100から1000にしたら今度はMLEしました。きちんとを計算しなおして317にセットし、ようやくACしました。通れば正義

J

とまとさんに面白そうですと紹介されたので読んでみると、セグ木でDPしたくてたまらなくなりました。
考察を少しすると、この問題にほとんど似ている形に帰着できます。
この問題は、WUPCでも似た問題を作問していて、その既出判定の際にピックアップされた問題だったので記憶に新しく、あとはサクサクと実装できました。ひゃどみん、あの問題を作問してくれてありがとう！

D

yamadさんととまとさんがずっと考えていましたが全然わからず、ただ気づいたら通っていました。内容は知っていましたが、自分が解いたら解ける自信はないです…

I

最初、三分探索という話があがりそれをとまとさんが実装しましたが、30ケース目と31ケース目でずっとWAが出ていました。
その後、想定解をyamadさんととまとさんが思いついたらしく書いていましたが、5ケースしか通りませんでした…
と、残り10分前後で、実は逆行列を求めるパートが間違っているのでは？という話になり、僕がkoprickyさんのライブラリを見つけ、それを使ってみるとなんとAC…
ちなみに解法はなんとなくしか理解しておらず、いまだにふわふわしているので線形代数を勉強する必要がありそうです。koprickyさんありがとうございました。

My Algorithm : kopricky アルゴリズムライブラリ

結果

もう一声欲しいですね。

反省

C問題等、変なところでつまるのが多かったです。yamadさんのICPC力をフルに生かすには、僕がもう少し簡単枠をサクサク倒していかないといけないかなと感じました。
ライバル視している後輩チームの1つにペナ差で負けたので悔しいです(途中まで2完差ついていたので、さすがに負けないだろうと思っていました)。

おしまい

明日はまたるぎうさんが復帰するので、 Give us sociabilityをボコボコにしようと思います！