12/04(月)

書く

あらすじ

Yandex Cup決勝のためカザフスタンに行った日本人5人のうち3人が発熱。こたつがめの明日はどっちだ。

12/05(火)

午前5時半くらいに目が覚めた。体感で発熱を確信。測ってみると38.8度、39度は超えていなかったのでそこまで重くなくて良かったなあという気持ちになった。発熱時は体温計の写真をツイートするのが鉄板だが、成田空港から仙台まで移動してきた翌日ということでかなり迷った。最近はこのあたり世間一般でかなりゆるゆるになっているはず、と信じてツイートした。

GG pic.twitter.com/CA9TEJ35xC
— こたつがめ (@kotatsugame_t) 2023年12月4日

コロナのワクチンの時に買ったイブクイックを飲んで再度就寝。今度は午前10時半に目覚ましで起きた。今行われているDMOJのコンテストは今日の午後2時までなので、参加するならこれがラストチャンスである。薬が効いたのか結構楽になった感じがあり、体温を測ると37.3度、それ以外の自覚症状もなかったので参加を決めた。

ところで、カザフスタンへの同行者の一人が病院に行ってコロナ陽性判定を受けたとSlackに書き込んでくれていた。じゃあ自分もコロナだろう。金曜日のセミナーはオンラインで発表すると先生にメールを送っておいた。ついでにYandex Cupの結果も伝えた。

カロリーメイトだけ腹に入れ、午前11時ギリギリになってコンテストのwindowを開始。それが終わってすぐコンテスト自体も終了するため、当然ここに感想を書くことができる。

DMOPC '23 December Contest - DMOJ: Modern Online Judge

1問目から構築で体調悪い時にやめてくれよ……という気持ちになる。左から右、上から下に埋めてみるとピークが右下1マスしかなかったので、あらかじめ $(1,1),(2,2),\dots,(K-1,K-1)$ に $N^2,N^2-1,\dots$ というピーク確定の値を置いて、残りをその方法で埋めてみた。

2問目も構築でさすがに逃げ帰りたくなった。頑張って手を動かしたら一発で当たりを引いたらしい。ナイトを2x2の形に配置すると結構広い範囲が埋まるが、そこから6x4の長方形だけ取り出して使う。理論的には24マスを四つでカバーしているので個数 $N^2/6$ くらいで足りそう。端はちょっと重ねて置くことにしてやってみると、なんと $N=14$ 以外全部解けた。 $N=14$ だけ端の処理を変えて終わり。

3問目は項ごとに解く。とりあえず二分探索して72点、各値の最も近いところだけ見て二分探索すると92点、初手で新しい値かどうかをチェックすると100点満点が取れた。何も考えず手癖でそれっぽいものを投げただけ。値の種類数を $\sigma$ として $N\log\sigma$ から $N+(N-\sigma)\log\sigma$ になっているらしい。 $\sigma$ が大きいと改善され、 $\sigma$ が小さいとそもそも回数がいらないという話か。

4問目は全方位木dp。辺を1回通るか2回通るかだけ考えると、あとはそのタイミングで適当に往復すればよい。よってその辺の先に行ってから戻ってくるか戻ってこないかという話になり、遷移が書ける。バグったらデバッグ不可能だなと思いながら必死で書いたらWAが出てひっくり返ったが、頑張って読み直したらデバッグできた。「戻ってこない」遷移のときに「戻ってくる」値を採用しても矛盾ではないから、ここはこの二つのMAXを見るべきだった。

5問目は解法自体はすぐわかる。全員まとめて並べ、男女を $\pm 1$ にして累積和を取ると、隣り合う人の間の距離が最低いくつのペアに寄与しなければならないかわかる。またそれが達成可能なので最適。よって長さ $2N-1$ の数列 $c$ に対し「区間 $\pm 1$ 加算」「 $\sum|c|\times d$ 取得」が解ければよい。平方分割でできる。理論的には。

ここまでの1時間で徐々に体調が悪化してきている。正直今は絶対にやりたくない。しかしこの位置にある実装問を落とすと順位がとんでもないことになってしまうのでやらざるを得ない。とりあえず甘えて $\log$ を付けたら普通にTLEしたが、バケツソートの要領で $\log$ を落としたら一発で通った。奇跡的にほぼバグらなかったため何とかなってくれた。

6問目は苦しい。各会社をその頂点をすべて含む極小な部分木だと思ったとき、取り除く会社の共通部分は非空で、残った会社は交差するかしないかが同値関係になっていればよい。部分点1はパスグラフで、列と区間の問題になるためまずこれを考えた。

1点を固定してそこを含む区間を全部取り除くことを考える。すると列は左右に分かれ、それぞれで前計算しておけばよい。これは同値類ごとの共通部分を管理しながら端から貪欲することで可能。重い腰を上げて実装したら75%しか点が来ずひっくり返ったが、他同値類の区間との交差判定ができていなかった。直したらちゃんと10点が来た。

部分点2も理論的には可能に見える。中心を含む会社を全部取り除くケースとそうでないケースに分け、あとはパスグラフのときの処理をひたすら頑張る。しかしさすがに実装する元気はなかった。残り20分ほどだったので、もし体調が万全でも間に合うとは思えない。

結果は510点。6問目の部分点2を諦めてしまい後悔……と思ったら2位で、1位のtouristも同点だった。レートは2880→2978(+98)。今日体調不良を押してコンテストに出たのは「Ratedはめったなことで休まない」という自分の信念を貫き通すためという理由がほとんどだったので、まさかここまでうまくいくとは思っていなかった。

ところでその体調不良だが、コンテストの3時間で覿面に悪化してしまった。頭痛、関節痛、悪寒、38.6度の発熱。布団に転がってTLでDMOJの言及を探したが見つからなかった。午後4時くらいに寝たと思う。

午後10時半くらいに再度目覚ましで起床。これはCF div.3に向けてのものである。しかしこの頃から喉の痛みが出て飲み物を飲むのもゼリー飲料を食べるのも一苦労になってしまった。Ratedでもないしさすがに出る気力が消滅。またすぐ寝た。熱は39.4度だった。

12/06(水)

この日はずっと寝ていた。時たま起きて喉の痛みに耐えながらゼリー飲料を食べたりお茶を飲んだり。

時刻	体温
4:31	38.6度
13:03	38.3度
19:41	38.2度
23:46	37.5度

12/07(木)

12/06 午後11時半に起きたタイミングから木曜日ということにする。この時の体温は上に書いたように37.5度で、昨日一日でかなり快方に向かった。

ずっとスマホをいじっていたが、午前1時頃急にTLにAlphaCode 2の話題が流れてきた。パーセンタイルで参加者の85%くらいに位置するというのだけ最初に知って、ふーんまあそんなもんかと思いつつ動画を視聴。

www.youtube.com

ここで紹介されている問題はCodeTON Round 4-Gである。当時の日記を見に行くと……解けていなかった！時間が足りなかったとかではなく、解説をガン見してupsolveしたとも書いてある。85%とはいったい何だったのか。まあこのあたりの問題が常に解けたらほとんど人類を越えているので、解けた中での最高diffを持ってきたのだろう。

Gは解けず6完29位
週記（2023/03/27-2023/04/02） - kotatsugameの日記

それからこのニュースはどんどん競プロerに知れ渡っていき、界隈の中でプロ驚き屋や競プロの未来を悲観視する人が現れたわけだが、ずっと寝ていて正確な時間がわからないため、日記に書きたい関連する話題は全部ここにまとめておく。

AIで競プロが終わるかという話については、自分は終わらないと考えている。そう考えなければならない。自分の自尊心は競プロに依っているため、ここがなくなるとちょっとやっていけない。よって競プロが終わるという未来を予想すること自体自分にとって無意味である。終わらないことに全賭け。

E869120さんのツイートでAlphaCode 2がどのようにしてコードを生成しているのかまとめられていた。自分がインターン先勉強会でpreprintを読んだ無印のAlphaCodeと変わっていないらしい。最初に生成するコードの数も同じ。ただコンパイルが通るものやサンプルに正解できるものの割り合いは劇的に増加しているようだ。無印ではC++の35%がCEとか、サンプルに通るのが千個から1万個とかいう話だった。

とりあえず，今話題の競プロ AI (AlphaCode 2) が何をやっているのかをまとめてみました。間違っているところがあったら教えてください。 pic.twitter.com/pSxdQS3piu
— E869120@本発売 (@e869120) 2023年12月7日

勉強会0214.pdf - Google ドライブ

元の時系列に戻る。布団に転がってスマホでハーメルンを眺めたりしていた。途中喉の痛みが治まった気がしたが、これは気のせい。ただ調子が良くなってきたのは確かで、久しぶりにシャワーを浴びて食事した。カロリーメイト、パックご飯にふりかけとインスタント味噌汁。喉が痛くて味覚障害が発生しているのかよくわからない。何か変でしょ、と言われたら否定できないくらいだった。

午前10時くらいに熱を測ったら36.1度。ようやく平熱に戻ってきたらしい。その後もスマホでYouTubeを眺めたりして正午あたりに寝た。

オンラインで開催される大学院の奨学金プログラム説明会のため、午後4時半に目覚ましで起床。37.3度で熱がぶり返していた。しかも午後3時からセッティングしてもらっていた1on1を寝過ごしてしまったらしくもう最悪。慌ててSlackで謝罪した。まあずっとぶっ倒れていたので進捗もないし、まだ喉が痛くて会話も難しい。じゃあキャンセルしておけよという話だが存在を完全に忘れていた……。

説明会はいつも使っているGoogleカレンダーに、1on1はOutlookの予定表に登録していたというのが二つの違い。また海外旅行→体調不良で現実世界のことが完全に頭から抜けてしまっていた。これからは1on1もGoogleカレンダーに登録するようにしたい。

ところで説明会については冒頭の出願説明で英語試験の成績を要求されると聞いてやる気を失ってしまった。残り時間はせっかく縦になったのでメールをポチポチ送信していた。

まず今週末に迫ったMeta Hacker Cupのため顔写真を送信。Yandex Cupで撮ったものが使えればよかったのだが、会場の照明がピンクや緑で顔だけ取り出したときに違和感がすごいことになるため避けて、夏の京都・二条城で撮ったものを送った。そこまで遡らないとまともな自分の写真がなかった。

二条城に行きました pic.twitter.com/Z0tFzzgDlS
— こたつがめ (@kotatsugame_t) 2023年8月8日

次に先生に明日のセミナーは喉が痛くて発表できないとメールした。するとセミナー自体がキャンセルになった。

解散後、AHC027に適当な解を投げた。一応参加だけはしておきたかったのでコーディングするタイミングを探していた。

HACK TO THE FUTURE 2024 (AtCoder Heuristic Contest 027) - AtCoder

布団に戻ってカクヨムを読んだりYouTubeを見たりしていたら結局日付が変わるまで眠れなかった。この間に35.9度と平熱に戻ったり、大家さんからロキソニンを頂いたりした。ロキソニンは鎮痛剤で喉の痛みに効くらしい。

また布団を脱出し午前1時からSRM851に出た。

https://community.topcoder.com/stat?c=round_overview&er=5&rd=19718

Easyはコスト関数が意味不明だが、おそらく乱数のつもりだろう。bitDPできるのですればよい。バスを1台運行するごとに人のいる街が一つずつ減っていくので、余計な状態を持たなくても何番目のバスかわかる。

Medは3種類以上のインデックスならすべての文字をちょうど一つずつ消費することができる。よって最初は残っている個数が多いインデックスから3種類ずつ使い、最大タイが3種類以上出現してからはそれらを全て使うという貪欲を実装した。3種類ずつしか使わない場合これが正当なのは有名問題で、それ以上使えるようになったら必ず構築できるためOK。

Hardは答えを求める数が等差数列であることに意味はないはず。一つずつ調べた。 $b^k$ 、 $2b^k$ 、 $b^k+b^l$ という形しかないので、まず $k$ を固定。 $k$ 乗根を求めると $b$ の候補が得られるので本当に正しいかチェックした。 $k$ 乗根を求めるのは二分探索で、べき乗も愚直に行ったため $\log$ 三つ。二分探索の境界を $10^{18}+1$ に固定してべき乗しながらオーバーフローチェックを行ったら大きめのケースで普通にTLEしたので、あらかじめ求めたオーバーフローしない値を埋め込んでおいた。

満遍なく遅いし熱を測ったら36.5度に上がっているしでげんなりしていたが、チャレンジフェーズ・システスでHardがボコボコ落ちてくれた。全完2位、2862→2919(+57)。

ちなみにEasyに制約違反のテストケースがあってリジャッジが行われたが、しばらく前後で2回レートが更新された状態だった。隙あらばワクワクさせてくる。Rubikunさんが公式Discordで言わないと多分そのままだったと思う。

カクヨムで「異世界帰りの憑依能力者　〜眷属ガチャを添えて〜」を読了。珍しく主人公の顔が生まれつき良いという設定。主人公にケチをつけてくるちょっとした敵役が3章まで引っ張られるし、その結末もスケールが小さく、また他のシーンにそぐわない下品さだったのが気になった。

kakuyomu.jp

シャワーを浴びてしばらく日記を書いた後、布団に転がって2時間くらいスマホでYouTubeを見ていた。午前9時就寝。

症状についてここにまとめて書いておく。喉の痛みについては、冷たい飲み物が喉奥に触れると鋭く痛むが、それ以外はまあまあ平気という感じになってきた。今は飲み物は冷蔵庫から出し、室温に戻しつつ飲んでいる。また鼻水が出るようになった。今さら風邪の典型症状を持ってこられると困る。

12/08(金)

午後4時に起きて大家さんから追加の薬とゼリー飲料、さらに鍋いっぱいのうどんを頂いた。薬についてはパープルショットプラスをお願いしていた。これも喉の痛みに良いらしい。喉奥に直接スプレーするので効きそうという感じがかなりある。うどんは、部屋にパスタとパックご飯しかない中での食べやすい病人食ということで、ただひたすらありがたい。

うどんを食べて体調チェック。体温は35.5度、鼻水は黄色っぽい体調が悪い時のやつ、喉は……痛い。昨日寝る前は良かったのにどうして。布団に戻り午後5時半からまた5時間寝た。

起きたらなんだかクラクラする。また悪化したかと思って体温を測ると35.8度。ただの寝すぎらしく、セーフ。TLを眺めたりYouTubeを見たりしながらうどんの残りを食べた。

ABC330のアマギフが届いていた。

お世話になっております。トヨタシステムズプログラミングコンテスト運営事務局です。この度はコンテストへのご参加有難うございました。貴殿は本コンテストにおいて、優秀な成績を収められましたので賞品を授与します。

株式会社トヨタシステムズ

￥10,000
Amazonギフトカード
（たぶんABC330）
— こたつがめ (@kotatsugame_t) 2023年12月8日

あとは朝まで日記を書いていた。喉の痛みは寝起きをピークとして、起きてから時間が経つと良くなるらしい。しかし夜明け前くらいに咳が出るようになって意気消沈。なぜ症状が入れ代わり立ち代わり現れるのか。一気に来るよりはマシか……。

シャワーを浴びて布団に入り、今日もまた2時間YouTubeに溶かしてから寝た。午前9時半だった。