Xmas Contest 2021に出ました

@pepsin_amylase さん、@osa_k さんとチーム lebesgueeee としてXmas Contest 2021に参加しました。

自己紹介

tahという名前でAtCoderをやっています。(プロフィール→ https://atcoder.jp/users/tah)

去年は黄色になれそうな青でしたが、そこからレーティングが線形に下がっていって水色になりました。悲しいですね。

今年はルベーグ積分の勉強会が行われていたのでそのあたりの人々を誘って参加する形になりました。

やったこと

E問題を解きました。

eの整数倍の小数部分が関係しているっぽいな…これはeの有理数近似の問題だ！！と思い、まずは連分数展開による有理数近似を調べることにしました。

https://oeis.org/A007676 とか https://oeis.org/A007677 と、小さいnで実験した結果を眺めていたところ、どうも連分数による近似が関係しているがそれだけではない模様。さらに眺めていると残りの規則も発見できました：

これが19時14分(74分経過)のことで、あと3時間くらいあるしダラダラ実装するか～と思ってやっていたところ、求められているn_K, a, bのうちn_Kについて全く調べていないことが発覚。一瞬慌てましたが、n_Kの階差数列を取って眺めるとそこそこ規則的だったのでどうにかなりました。

上の書き込みみたいな「適当に区切ると規則的」なやつは実装するのが面倒というか、焦ったら絶対ミスるだろうな～と思ったのでゆっくりダラダラやってましたが、結局1時間ちょいくらいで実装終了。なんかWAが出たりTLEが出たりしたので適宜配列を長くしたり高速化したりしてACできました。

無事通したので飯を食ったりしていたら時間が無くなったのでフラクタル迷路で余生を過ごしました(よくわからなかった)。

感想

今年も正の貢献ができてなによりでした。連分数展開を途中で止めたときに得られる分数p/qの分母と分子の満たすべき漸化式を学ぶことができました。