チームで参加しました。 Oxojo は C, E, F を担当しました。

内容

取り組んだ順です。

E. Encountering a Friend

一番簡単な問題っぽく、読んだのが私だったので私が解きました。

これを覚えていたので、この通りにやって 2 人が出会うまでの最小ラウンドを求めて、あとは $2$ で割るとか適当にやればいいと思っていたのですが、$n = 1$ のコーナーケースを見落としていてペナルティを出してしまいました。

F. Forgot to Refuel

KeioPC でゴリゴリの組合せの問題を担当したので、今回もゴリゴリの組合せの問題を担当しました。

見た目は分割数だったのでそちらからのアプローチを考えていたのですが、うまくいかず包除原理のアプローチに転換したところいい感じに $O(L \log{L})$ に落ちる形を見つけられたので、その方法で通しました。

C. Cell Flip Game

線形代数ができる人がやってほしいということで、こういう数学は私の担当なので私がやりました。

こういうのは Lights Out というゲームらしく、$nm$ 個のマスの状態を $\mathbb{F}_2$ 上の行列で持ってあげると、それに関する連立方程式系を解けばよくなります。ただ、今回は $nm$ の値が大きくなりそうなのでそんな愚直にはできなさそうです。ということでガチャガチャ実験をしたところ、最初の 1 行目の操作を決め打つことができれば、2 行目以降の操作もそれに応じて一意に定まるということが分かったので、これにより $nm \times nm$ だった行列の大きさを $m \times m$ まで抑えることができて、これなら System of Linear Equations を時間内に求めることができます。あとはうまく計算をしてあげれば解くことができました。

感想

Taichung Regional を終えてから Ucup に出ることが少なくなってしまい、今回が久しぶりの Ucup だったんですが、そこそこ善戦できてよかったのかなと思います。次の日は ICPC ミラーの予定だったのですが、彩燕祭と被った関係でミラーできなくなってしまったので、代わりに良い練習になったと思いました。

あとは数学問と向き合うのが結構楽しいのでこれからもこういう系の問題はいっぱい担当していきたい気持ちがあります。いっぱい出るのか分からないですが......

H, L みたいな Interactive とも言い切れないよくわからない問題は今まで見たことなかったので対応できませんでした。特殊なタイプの問題にも物怖じせず対応できるようにしたいです。

おわり

おわりです。