Xmas Contest 2019に出ました
@pepsin_amylase さんとチーム xmax09s126 としてXmas Contest 2019に参加しました。
自己紹介
tahという名前でAtCoderをやっています。
ここ2年ほど水色と青の境界を漂っています。(プロフィール→ https://atcoder.jp/users/tah)
普段は数学の研究をしています。
経緯
「アルゴリズムを考えるところまでは楽しいんだけど実装するのがつらい」
「アルゴリズム考えるからだれか実装してくれ」
みたいなことをTwitterでグダグダ言っていたところ、
pepsin氏に「チームで出れるコンテストに一緒に出ませんか？」と提案してもらい、今回参加の運びとなりました。
参加する前に過去問をチェックしてみたところ、
・問題はめっちゃ面白い
・が、なんもわからんので即座に解説を読む(面白い)
ということで過去問チェックはあんまり役に立たなかったんですが、とにかくクリスマスコンテストは面白い問題が出るっぽいという(モチベーション的にはかなり有益な)ことが分かりました。ぶっつけ本番でどうにかするしかない。
コンテスト開始
おおまかに時系列順で書きます。
まずはチームのアカウントでAtCoderにログイン。
pepsin「適当に登録したらタイポしてxmaxになっちゃったから気を付けて」
ぼく「はい」
全問に目を通し、とりあえず分担して考察しましょうということで、pepsi氏はB、ぼくはDを考察することに。
D
あ！過去問で見たやつだ！
→問題文にリンクが貼ってあったので、おもむろにXmas Contest 2013の回答を開く
→Liouville関数というらしい
→「Liouville function」でググり、Wikipedia熟読
→そうこうしているうちにBの進捗報告が来る
B
|S|=|D|、|S|<|D|の例は簡単に作れるが、|S|>|D|となる例を作るのが難しいらしい。
pepsin「クリコンだし|S|>|D|はMerry Christmas!なんじゃね？」→WA
乱択で要素数8～10くらいの例は得られたらしいので見せてもらう。ぐっとにらむ。
脳内にこういう絵が形成される…
＼の線の本数が|S|、／の線の本数が|D|だな…
→全体を「カタマリ」だと思って同じ形で配置すればよさそう
→|S|>|D|を満たす集合X,Yについて、{10000a+b : a∈X, b∈Y}も|S|>|D|を満たしそう*1
pepsin氏によれば要素数が8から100ぐらいまでは乱択でどうにかなるらしい。↑の性質を使うとそれらの積はok。中途半端なところをどうするか？
→ちょっとくらい集合の要素を間引いても大丈夫かも？→ビンゴ！
あとは実装をpepsin氏に任せ、Dの検討に戻る。
再度D
Wikipediaで調べた内容を雑にまとめて考えた内容を共有。
pepsin「TeXってそんなにカジュアルに生成できるのか」
ぼく「そういう仕事なんで……」
最後の式を検討。制約的にはdで和を取るべきというpepsin氏の意見
→Mertens関数とかいうのを高速に計算できればよいらしい
→「Mertens's function computation」でググる
→なんかそれっぽい論文とかそれっぽいMathOverflowのスレッドが出てきて、O(√x)で計算できるらしいがよくわからん
ここらへんで飽きたので別の問題へ移動。
G
Z[i]/(2+5i)とZ[i]/(5+2i)だな～
→それぞれのスタンプの押し方29通りしかないじゃんね
と気づき報告したところ、フローで解けるんじゃね？と言われ、あとすべて任せていたらACしていました。ありがたし
I
傾き-19/31の直線だな～
→こっちはよくわからず
「そろそろみんなが解いてるやつやるか」という話になり、AとJを検討。
J
自分はノータッチ。pepsin氏がいつのまにかカラクリを見破り(?)AC。
A
ジグソーパズル用のインターフェースが貧弱すぎるのであきらめました。
結果
B(100)+C(7)+G(100)+J(100)で307点、30位でした。
各々得意なところがうまくかみ合って貢献できたと思うのでとても満足。楽しいコンテストでした。
*1:正確にはウソですが、10000の代わりに「十分大きな数」だと思って読み替えてください
