2021-12-24

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で実験した結果を眺めていたところ、どうも連分数による近似が関係しているがそれだけではない模様。さらに眺めていると残りの規則も発見できました：

f:id:n_e:20211224230233p:plain

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

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

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

感想

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

2020-12-24

Xmas Contest 2020に出ました

@pepsin_amylase さんとチーム Weihnachten としてXmas Contest 2020に参加しました。
Weihnachtenというのはドイツ語で「クリスマス」という意味だそうです。

自己紹介

tahという名前でAtCoderをやっています。
今年は上半期調子よくて黄色になれそうだったんですが、下半期やる気を失ったため結局なれませんでした。(プロフィール→ https://atcoder.jp/users/tah)

コンテスト参加の経緯

私「今年も一緒にやりませんか」
Amylase「いいですよ」

コンテスト感想

…解けそうな問題がない！
とりあえずちょこちょこ考えてみて、一番どうにかなりそうだったB問題にとりかかっていました。

考えていたこと

期待値が正か負かで様子が分かれるっぽい。(期待値が正なら無限個、負なら有限個、0のときは調べてみないとわからない)
負のときに調べるべきnの上限を知りたい。
とりあえず実験を試みたが、どうも精度が悪い気がする(ここでpythonのFractionalの存在を教えてもらう)
いろいろな値を調べてみて、ほとんどの場合は750くらいまで計算すれば大丈夫そう。それに当てはまらない場合のみ別扱いして提出→1WA、13くらいTLE
がんばって調べるべき場合を減らす→1WA
「WAかどうか調べたい箇所で入力待ちするとWAじゃなくなる」という手法を教えてもらい、原因を特定。無事AC(このときすでに3時間38分)。

amylaseさんはI問題にとりかかっていて、考察はできたようでしたが実装が終わらなかった模様…
他の問題はどれもよくわからず、残り20分とくにやることもなくコンテスト終了。お疲れ様でした。

感想

チームの正の得点に貢献できてなによりでした。

2019-12-25

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くらいの例は得られたらしいので見せてもらう。ぐっとにらむ。
脳内にこういう絵が形成される…
f:id:n_e:20191225035712j:plain
＼の線の本数が|S|、／の線の本数が|D|だな…
→全体を「カタマリ」だと思って同じ形で配置すればよさそう
→|S|>|D|を満たす集合X,Yについて、{10000a+b : a∈X, b∈Y}も|S|>|D|を満たしそう*1
pepsin氏によれば要素数が8から100ぐらいまでは乱択でどうにかなるらしい。↑の性質を使うとそれらの積はok。中途半端なところをどうするか？
→ちょっとくらい集合の要素を間引いても大丈夫かも？→ビンゴ！
あとは実装をpepsin氏に任せ、Dの検討に戻る。

再度D

Wikipediaで調べた内容を雑にまとめて考えた内容を共有。
f:id:n_e:20191225035801p:plain
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

ジグソーパズル用のインターフェースが貧弱すぎるのであきらめました。

E

n!の素因数の個数だな
→(いろいろ考えて)1からNまでの素数の個数が高速に計算できればよさそう
→ググる
 素数を高速に数えるコードが見つかったときには残り8分くらいになっており、ぼくの手には負えませんでした。残念

どこかのタイミングでC1を手作業で解いたんだけど忘れてしまった。

結果

B(100)+C(7)+G(100)+J(100)で307点、30位でした。
各々得意なところがうまくかみ合って貢献できたと思うのでとても満足。楽しいコンテストでした。

*1:正確にはウソですが、10000の代わりに「十分大きな数」だと思って読み替えてください

2018-09-29

二人じゃないと、走れない！ - サイドカーレース百合概論アニメ「つうかあ」

グーーッドモーニングはてなブログーー！！！

はじめまして、id:n_eです。つい最近アニメ「つうかあ」を見たんですけど、それが猛烈に素晴らしいアニメだったので、いてもたってもいられなくなってこのエントリーを書いています。

アニメ「つうかあ」とは

2017年秋クールに放映されました。制作は「ブレイブウィッチーズ」「田中くんはいつもけだるげ」のSILVER LINK.です。SILVER LINK.10周年記念作品とのこと(にしては攻めすぎ感がありますが…)。
三宅島を舞台に、レーシングニーラーというモータースポーツに青春を賭ける女子高生たちの姿が描かれます。キャラ原案はTivさんで、みんなとても可愛いです。

そもそもレーシングニーラーとは

二人乗りサイドカーのレースで、ドライバー(運転する人)とパッセンジャー(バランスを取る人？(←よく分かっていない))のペアで速さを競うらしいです。
正直なところ、私もこのアニメを通じて得た知識しかないので、詳しいことは分かりません。
とにかく、二人羽織的な感じで車を運転するという、百合オタクが悪ノリで考え出したみたいな、実在するスポーツです。
私はあんまりわかってないので、レーシングニーラーと言ったりサイドカーレースと言ったりすると思いますが、広い心で読んでください…

で、アニメの中身は？

レースをする？→あんまりしません。
日常もの？→違う気がします。
主人公ペアの成長を描く？→中盤まではそういうのもないです。

…ないないづくしですが、実は本筋らしい本筋もないのです。
じゃあ何をやってるかというと、いわゆるキャラ回ばかりで構成されています。特定のペアの話を2話かけて描く、というのがメインの流れです。
この構成は本当に、本当に天才的で、結果としてこのアニメはサイドカーレース百合概論になっています。なんだそりゃって感じですが、本当なんです。想像つきますか？私ももちろん全く想像できませんでした。
サイドカーレースにおいて大切なことを百合から学び、百合において大切なことをサイドカーレースから学ぶ、そんなとんでもない講義がここに成立しているのです。
あと、全体的に、悪ノリっぽい箇所が多い気がします。まぁ、そもそもの題材からしてオタクの悪ノリみたいな競技だし、多少は仕方ありませんね。

キャラクターの紹介……ではなく、各話内容の紹介

ここでキャラクターを紹介していきたいんですけど、先述の通り内容はほとんどキャラ回なので、いっそのこと各話紹介をしてしまいます。
一応以下はネタバレ注意！です。ちょっとでも気にする方は今すぐ本編を見よう！(→つうかあのアニメ見放題 | dアニメストア )

1話キャラ見せ&主人公ペアの背景

ちょっと行儀悪いですが、画像は公式サイトにあるものです。
この二人が「主人公ペア」で、一応この二人の話がメインの話となります…が、このアニメは2話から怒涛のキャラ回大攻勢が始まるので、結局終盤で1話の内容の復習が入ります。1話はいったい何なんだ。私にもよく分かりません。
キャラ見せをやるんですが、なんと7ペア14人を一気に紹介します。いっぺんに全員分紹介されても覚えられない！となるんですが、これからゆっくり掘り下げていくので覚えなくても大丈夫です。気になるペアがいたらチェックしておきましょう。
1話ではキャラ見せの他に、主人公ペアの事情が紹介されます。「コーチ」なる謎の男性が出てきて、放映時は百合詐欺かと心配になった人もいたんじゃないでしょうか。少なくとも私の周りでは「コーチ不要では？」みたいな意見も見ましたし、私自身も最初に見たときは「え？」ってなりました。たしかにヘテロ前提ではあるのですが、「女と女の強い感情」をやるための前振りなんです。つうかあを信じてそのときを待ちましょう。

2-3話お嬢様(?)ペア編

この二人が2-3話の主役です。お嬢様学校に通う二人ですが、どうやら相手のことを信用していないようで…？というお話。つうかあは信用できるアニメなので、「パートナーを信用できるか？」という話から始めるわけです。サイドカーレースを題材にとったうえでまずこの話から始めるの、天才だと思います。
さて、劇中ではレースの参加者は三宅島の民宿(ゆりとめぐみの生家です)に泊まるという流れになっています。なのですが、ペアごとに宿泊するのではなく、敢えてのドライバーとパッセンジャーに別れて宿泊するという形になっています。これも天才で、ペアの事情を知るうえで超重要ポイントになっていると思います。
このエピソードの最後にみんなで「花火」をするシーンがあるんですが、これがまた天才。始まったとき完全に悪ノリかと思って笑ってたんですが、最終的にきっちり名場面に昇華してくる手腕が凄まじいです。

4-5話 SMペア編

4-5話の主役はこの二人です。いずみちゃんがSっぽくてなぎさちゃんがMっぽいということだけ覚えててください。
ドライバーとパッセンジャーの主従関係を掘り下げようというのがこのエピソードのテーマです。一見ドライバーが「主」でパッセンジャーが「従」に見えるわけですが、果たしてどう転ぶか…？このテーマをSMっぽいペアに絡めて、さらにキャラクター性を損なわない解決をしてくるんだから天才です。
詳しくは見てもらうとして、4話のアバンは本当にキマっています。初見時はめっちゃテンション上がりました。

6-7話双子編

この二人が6-7話の主役です。写真だと区別付きませんね。たぶん同じ画像だと思います。そんな「全く同じ」双子の2人ですが、なにやら悩みがあるようで…？
この回はかなり難しかった気がしていて、何がテーマかパッと言えません。とはいえ、最終的にキャラクターに合わせた問題解決をしているところは非常に好感が持てました。4-5話のSMペアもそうなのですが、「安易な解決法はとらない」「キャラクターの個性を大切にする」という姿勢が見え隠れしているところがこのアニメの魅力的な点です。

8話放送部編

この回の主役はこの二人。なんとレーサーですらありません。ここまでキャラ回ばっかりだったのに、ここにきてさらにレース実況者の回を入れてくるとは！しかしよく考えてみると、「サイドカーレース概論」をやるにあたって、ともすると忘れられがちな、レースを成り立たせるのに必要なレーサー以外の人々にスポットライトを当てることは、とても重要なことではないでしょうか？
実際、この回はこのアニメの白眉だったと思います。レーサーにならなかった人がどのような目でレーサーを見ているのか。私は一撃食らわされて、8話で完全につうかあの虜になりました。

9話突然の総集編！

さて、9話ですが、(ほぼ)総集編です。今までメインストーリーというものは特に進んでいないんですが、総集編です。体力回復はとても大事。
後半ではコミカルパートとシリアスパートが交互に挟まって、振れ幅がすごい話数でもありました。

10-12話いよいよ大会！

待ちに待った本番のレースです。主人公ペアとコーチのお話に決着がつきます。
もうこちらから言うことはほとんどありません。「雨の中で女同士が感情をぶつけ合うシーン」が好きな人、「女が女をグーで殴るシーン」が好きな人、今すぐ見てくれ…！！

他のペアについて

さて、当番回がなかった人たちをかるーく紹介してみます。

関西弁

出てくるたびに和みました。サイドテールの子(かなえちゃん)がわりと好みでした。

ゴスロリ

可憐なる煉獄の斬撃(←マシン名)しか印象に残ってないです。スミマセン。

宝塚

毎回意味あるんだかないんだかわからないショートコントを繰り広げていました。2人の絆は、フォーエヴァ〜〜♪

ぶっちゃけ他のペアに関してはあんまり書くことがないですね。やはり彼女たちも掘り下げられるべきではなかろうか。ということで、OVA待ってます！！

二人じゃないと、走れない！

つうかあというアニメ、私は異常に好きになってしまったのですが、世間的にはそうでもないようで、グーグルでちょっと検索してみると、候補に「つうかあつまらない」「つうかあイベントガラガラ」とか出るんですよね…(ちょっと君たちそこに並びなさい)。私だってイベント行きたかったです。テレビ放映時につうかあを信じられてさえいれば！しかし、過ぎたことを悔やんでも仕方ありません。つうかあを見始めるのに、遅すぎるということはありません。たぶん。ということで、サイドカーレース日和とでもいうべきこれからの季節、アニメ「つうかあ」を通してサイドカーレースの世界、そして百合の世界への知見を深めていってほしいと思います。それでは皆様、良いつうかあライフを！