01/09(月)

午後2時過ぎ起床。半から指導教員の先生が海外の先生とオンラインでミーティングをするのに同席させてもらった。

かなり辛かった。話の流れでこういうことになったはいいが、あくまで先生の専門であって自分が今勉強しているグラフ理論からは微妙に遠い。事前に頂いた資料もあまり目を通せておらず、理解度が微妙な感じになった。終了時刻が決められていないのも応えた。結局2時間程度で終了。海外の先生が退室されてから指導教員の先生と少し話し、辛うじて理解できた部分について少し質問したりした。

じゃりみちさんのゆっくり実況シリーズ「ありきたりな惑星緑化」の最終回が投稿された。このシリーズは最初から最後までほぼリアルタイムで追っていた。終盤は単調な作業がかなり続いていそうだったが、動画ではほぼ全てカットされている。駆け足だったという印象もあるものの、最後まで濃密な内容が楽しめたのは嬉しいことだった。

www.youtube.com

夜までずっと週記を書いていた。午後10時投稿。相変わらず校閲はできていない。

食事してセミナー準備。今回から平面グラフの章に入る予定で、明日のセミナーではその準備としていくつか幾何学の用語の定義をしたり性質を見たりする。直感的に明らかなことでも直感を使わず示す必要があって、その匙加減が難しい。何が言えて何は言えないのかがうまく掴めず、結局二つほど証明を完成させられなかった。準備の時間も限られているため諦めることに。

午前4時頃終了。布団に入るもうまく眠れなかった。しばらくハーメルンの更新を読んでいたら午前5時半ごろに寝落ちした。

01/10(火)

午前9時過ぎ起床。布団から出るのに30分くらいかかった。

外は雪がちらついているようだが昼からの降水確率は低め。帰りには晴れているだろうと見込んで、冬タイヤに履き替えていない原付で山に登ることにした。午前10時ちょっと前に到着。すぐ教室に向かえば間に合うところを、空腹に耐えかね購買でパンを買ってから向かった。先生も少し遅れていて、数学棟の1階で鉢合わせた。

購買にて。年明けから生協の組合員証がスマホアプリに切り替わっている。アプリ登録は全員行う必要があって、そのアプリで決済もできるため便利というわけらしい。自分はスマホにそういう機能を持たせるのを嫌っていて、以前のカードも一部のレジで使えるという話だったから決済時はそうしようと思っていた。しかしこの「一部のレジ」というのは本当に一部らしく、今日寄った購買には置いていないようだ。仕方なくスマホで決済した。

【重要】HagiCo・ミールの利用には大学生協アプリの登録が必要になります | 東北大学生協

スマホをカードの代わりにすることを嫌っている理由についての自分語りをする。自分は、自分が組合員証などのカード類を忘れる・落とす・無くす確率より、スマホの充電を切らす確率のほうが高いと見積もっている。なぜなら、カード類は自分の注意力次第でどうとでもなるのに、スマホの充電に関しては何もできないから。満タンで家を出ても切れるときは切れる。

午前10時過ぎから午後0時半までは同級生のセミナーだった。今日はラムダ計算のη-変換。Unlambdaをやっているとき、λx.fxをS(Kf)Iではなくfと書けるということでかなりお世話になったが、これこそが関数の外延性であるということは意識していなかった。η-変換のほうが弱いように感じてしまう。

昼食を買いに購買へ。昼休みも半ばなのにかなり混んでいてびっくりした。どうやらレジ待ちが長いらしい。見ると、2台あるレジのうち片方を一人が結構な時間占有していた。スマホアプリでの決済に苦労しているようだ。その人が悪いわけではなく、レジが悪いわけでもなく、アプリが悪い。いろいろ不具合があることはTLに流れてきて知っていた。

食事をとっとと腹に収めてすぐ、自分ではなく博士課程の方のセミナー。証明にグラフを持ち出す定理があるらしく、昨年末から話だけは聞いていた。今日は大量に登場した添え字を追うのに時間を使ってあまり進まなかったが、終盤、本に書いてあるものと論文に書いてあるもので定義に食い違いがあっておかしいということを発見し、指摘した。来週に持ち越し。

セミナー中に外を見たら思いっきり雪が降っていてひっくり返った。原付を押して帰らなければならないのだろうか。

午後3時過ぎに終了し、その後休憩なしで自分のセミナーを行った。今日は準備してきた量も少なく、また後述する理由で急いでいたため、1時間半で話し終えてしまった。昨日完成させるのを諦めた証明二つについては、片方は議論しているうちに思いつくことができたが、もう片方は何もわからず。自分で考えるのも苦しいためネットで誰かに尋ねたいところだ。

セミナーの終了を急いだ理由は、午後5時に閉まる山の下の購買で予約したラノベを受け取りたかったから。教室を出た時点で残り20分くらいで、歩いていては間に合わないような時間だった。幸い雪が降っているとは言え路面には積もっていなかったため原付に乗って移動。下り坂で神経をすり減らしつつ何とか閉店前に滑り込むことができた。無事受け取りに成功し、学食で食事して帰宅。

生協でラノベを20万円分くらい買ってるので、もう顔パスで注文した本が出てくる
— こたつがめ (@kotatsugame_t) 2023年1月10日

今日はまず1冊出てきたので「あと8冊あるはずですが……」と言い放ち貫禄を見せつけた
— こたつがめ (@kotatsugame_t) 2023年1月10日

実は今日はインターン先定例会の日でもあった。昨日が休日のためずれていた。会議に接続すると勉強会の発表の終わり際で、その後の質疑応答だけ1時間ほど聞いた。線形代数とニューラルネットワークの話らしい。スライドを見るだけでもかなり難解な内容だったのがわかる。そんな中でも質問を通して何かを学び取る参加者のテクニックが印象的。自分からは、ニューラルネットワークの数式表現がうまく解釈できなかったので、何かノードと矢印の図はないかと聞いた。

しばらく部屋の掃除をしていた。以前言及した家飲みの日が明日である。注文した酒類やボードゲームは無事すべて到着した。

01/11にホスフィン・たいぺーと遊ぶ。いつものように外で食事してから我が家で家飲み。そのための酒類やボードゲームをいくつかAmazonで購入した。
週記（2023/01/02-2023/01/08） - kotatsugameの日記

午後8時過ぎからCF #843 div.2。開始が10分こどふぉった。

Dashboard - Codeforces Round #843 (Div. 2) - Codeforces

A1は全探索できる。A2に15分かかった。正確には、A2で入力される文字列がaとbしか含まないということに気づくのに15分かかった。今日は難しい回か、と思ってのんびりやっていたのが馬鹿すぎる。順位表を見たらみんなBどころかCまで通っていて一気に冷や汗が出た。解法は、両端以外にaがあればそれだけを真ん中にする、なければ両端1文字とそれ以外に分ける。

Bは $a$ を元の数列全体、 $b$ を $a$ から一要素取り除いたものとして条件を満たせるかチェックする。Cは $m$ を増やすことで $n$ の下のbitから順に消していく。次に消すbitを決めると $m$ をどんな値にすればよいかがわかる。

Dは各素数を表す超頂点を作り、それと数の間に辺を張った。復元がかなり面倒。数値からインデックスを求めるあたりが辛そうと考え、最初に $a_s=a_t$ のケースを取り除いておいたら、 $a_s=a_t=1$ かつ $s\ne t$ のケースにやられてしまった。

Eは二分探索。マイナスのために使った値は次はプラスのためにしか使えない。逆も然り。

Fは苦労した。 $u=1$ のケースは何とでもなるため問題は $u=2$ 。自分は最初「 $n$ より少し小さい長方形を作り、足りない分を付け加える」という方針で解こうとしていたが、これだと例えばサンプルの $n=7$ で、 $3\times 3$ の左上と右下を消したような形を数えられない。

今何気なく使った表現「 $3\times 3$ の左上と右下を消す」が解法。つまり、 $n$ より少し大きい長方形を作って過剰な分を消せばよい。ラボの形は凸だと思ってよく、この場合の周長は元となった長方形と一致する。長方形の縦横と、その長方形が答えの元になりうる $n$ の組み合わせは、ギリギリ全探索できるくらいの個数らしい。

あとは長方形とそこから消すブロック数に対し、凸を保つような消し方の数を求める方法について。凸を保つためには四隅から消し始める必要があって、実は四隅をそれぞれ独立に考えてよい。気になるのは消し方が干渉しないかだが、もし干渉するほどたくさん消せるなら元の長方形としてより小さなサイズのものが取れるため、考慮する必要がない。

同じ理由で長方形のサイズも気にしなくてよいので、まず削るブロック数に対して消し方を数え、上で述べた全探索の際にそのテーブルを見ることにする。四隅の一つについて解き、それを多項式と見て4乗するとテーブルが作れる。消すブロック数は最大で1000にも満たないようなので、これはどちらも特に工夫のないdpなり畳み込みで行える。

1度目の提出はWAだった。そこから30分近く理由がわからずに苦しんでいたが、適当に探索範囲を増やして出しなおしたら通った。元となる長方形のサイズが $n$ の上限 $4\times 10^5$ を超え得るのを見落としていたようだ。

遅めの全完で47位。Eは二分探索の判定をよく見ると貪欲でよいようだ。さらに実は、累積和の最大から最小を引くことでも答えが求まるらしい。累積和を取った状態での操作を考えると分かった。衝撃的。

全完に2時間かかってしまった。本当はとっとと切り上げてゲーセンに行こうと考えていたが、もはやそのような時間ではない。明日家飲みの前に行くことにする。

チュウニズムデュエルが終わっていない。01/11までにあと10クレほどプレイする必要がある。
週記（2023/01/02-2023/01/08） - kotatsugameの日記

明日に備えて早く寝るべきだが、今日の深夜に新春TCB2023が終了して結果が出るということで、その時間までTLを眺めたりYouTubeを見たりしつつ起きていた。

https://techful-programming.com/user/event/3814

午後11時55分に終了し、結果は4位。1問テストケースの不備で採点対象外になるので、もしかしたらずれるかもしれない。全完者の中では結構時間がかかっているほうだった。失点は124ptで、すべてタイムボーナスを失ったことによるものである。3位は遠く、5位は近いので、ペナルティを出さなかったのはかなり偉かった。以下各問題の感想。

天邪鬼な石取ゲームは、 $\max a$ が $\sum a$ の倍より大きいなら先手がその山を選び続けることで勝てる。それ以外のケースは実は全部の石が取られ、 $\sum a$ の偶奇だけで決まるのではないかとエスパーした。変なケースが思いつかなかったので出したら通った。制約が微妙に小さいため結構怖かった。

Restricted Gridは結構難しかった。条件を式で書き眺めていたら、全部足すことで答えの $M\sum x+N\sum y$ を上から抑えられる。勝ったなガハハ！と思っていたらサンプル4が合わなかった。冷静になるとそんなピッタリにはできない。さらにしばらく式を眺めて、 $\sum y$ を全探索すると全部計算できることに気づいた。少し時間オーバーして-5pt。

Sum Mod M againは非常に難しかった。まず $i$ が固定されているとして、 $j$ を求めることを考える。これはつまり全体を $B$ で割ろうとしている。すると $Ai+C$ が $\gcd(B,M)$ の倍数という条件が出てくるが、これを満たす $i$ はある $q$ 、 $r$ と適切な範囲を動く $k$ によって $i=qk+r$ という形で表せる。この $i$ を元の式に代入することで $B$ で割ることが達成できる。今の操作は問題を $B=1$ のケースに帰着したことに相当する。

$i$ と $j$ を入れ替えてもう一度行えば $A=B=1$ にできるぞ！と思い込んだが、残念ながら $B$ を変えるときに $A$ も変わるためうまくいかない。しかし実は $B=1$ とできた時点で解けていた。 $i$ を固定すると、 $Ai+j+C$ は $Ai+L_2+C$ から $Ai+R_2+C$ までの値を取る。このうち $M$ の倍数であるものの個数は冷静になると $\lfloor(Ai+R_2+C)/M\rfloor-\lceil(Ai+L_2+C)/M\rceil+1$ と表せて、 $i$ に関する和を取るのがfloor_sumで行える。

考察が一直線には進まず、迷走していた時間が長い。86分かかったようだ。タイムボーナスはすべて溶け消えて-56pt。ここまでは日曜日のECR前にやっていた。特にこの問題が解けたのは15分くらい前と結構ギリギリだった。タイムボーナスが残っていないからあまり関係はない。以降はECR後。

初夢スコアアタックは一つ前の問題と難易度が同じなのに、非常に簡単だった。使える限り多くの魔法を使いたい。使える魔法を増やす方向で考えると計算量が抑えられないが、減らす方向で考えれば、単に使えなくなったものを消していくだけでよい。問題文を把握するのに少し時間がかかるも14分で解けた。

Worst Conjectureはもう大変。 $c$ と $T$ で2重積分する。被積分関数の形が複雑なので、それを決定できるよう $c$ と $T$ の範囲を細切れにしてそれぞれ計算する。行った工夫としては $(c,T)$ の代わりに $(c,2T-c)$ で積分したことが挙げられる。 $X$ に関する条件がこの2数の間にあることと書けて便利。

$2T-c$ の積分を外側に持ってきたのは失敗だった。 $c$ の範囲に対する期待値はサンプルに書いてあるが、これをデバッグに使えず自分で積分計算する羽目になった。しかも結構最後のほうまで条件の不等号を逆だと誤読していて計算がやり直しに。非常に苦しみながら4時間と計算用紙10ページをかけて通した。当然タイムボーナスはないので-63pt。

しばらくTLを見て午前1時過ぎ就寝。

01/11(水)

午前8時半起床。布団から出るのに30分かかった。準備して出発。

まずゲーセンでチュウニズムデュエルを終わらせにかかった。「凛として咲く花の如く」の理論値が出た。曲も譜面も好きなので結構うれしい。時間的に7クレしかできず、クリティカルが全く出なかったためデュエルは終わらなかった。昼食後にまた来る。

凛として咲く花の如く理論値 pic.twitter.com/yvDiofitpJ
— こたつがめ (@kotatsugame_t) 2023年1月11日

午前11時半前にたいぺー・ホスフィンと待ち合わせして、ホスフィンが予約してくれたフレンチの店に入った。今日はフルコース。量的にはそれほどでもないなと思っていたが、2時間かけてゆっくり出てきたので満足感はかなりあった。ツイートに記された料理の名前は説明を聴き取れなかったりして不正確である。

食事
・いろいろ温野菜の菜園風サラダ
・ソーセージ、パテ、スモークサーモンのマリネ
・パン
・きのこのポタージュ pic.twitter.com/FoyNtJhdD3
— こたつがめ (@kotatsugame_t) 2023年1月11日

・メカジキのソテー
・牛ハラミのステーキ
・デザート（ガトーショコラ、りんごとカスタードのケーキ、ムース）＋紅茶 pic.twitter.com/XiQLVaf9do
— こたつがめ (@kotatsugame_t) 2023年1月11日

どれも明らかに美味しかった。サラダは飾りのドレッシングのほかにも野菜に薄く塩味がついているようで、丁寧な作業に感動した。きのこのポタージュは一口飲めば非常に濃厚なきのこのうま味が口の中に広がって圧倒された。たまにインスタントのスープパスタを食べていて、これもきのこが美味しいなと思っていたが、やはりモノが違う。牛ハラミのステーキは横の橙色のソースがわさびのソースだった。結構辛みが強く、わさび醤油が好きな自分にとっては非常に嬉しかった。

クノール®スープDELI® ポルチーニ香るきのこのクリームスープパスタ（容器入）｜商品｜味の素株式会社

食後、二人がドンキに買い出しに行っている間にゲーセンでチュウニズムデュエルを終わらせた。追加で2クレ使った。TiamaT F:minorはラストまでかなり上手かったのに、つまらないアタックやミスを出してSSS+もフルコンも逃してしまった。

あああああアウトロで切ったあああああ pic.twitter.com/gSXsPCi32C
— こたつがめ (@kotatsugame_t) 2023年1月11日

帰宅して飲酒開始。

飲酒します pic.twitter.com/k5AGKMEW7I
— こたつがめ (@kotatsugame_t) 2023年1月11日

購入したボードゲームをプレイした。最初は「ギャンブラー×ギャンブル！」。結構面白かった。各プレイヤーが0または1のカードを場に出し、その総和が当たりの数字になっているプレイヤーがコインを獲得する。獲得したコインで自分の当たりの数字を増やしたりしつつ勝利条件を満たすゲーム。カードを出す際には実際はもうちょっと手順があって、考えようと思えばいろいろ考えられる。出すときにブラフで何か言うだけでもかなり戦略ゲームっぽくなって楽しかった。

このゲームは3人または4人用とされていたが、3人だとゲームの展開が制限されると感じた。本来はゲームが進むにつれ手持ちのカードに2や3が増えるようだ。しかし3人でプレイしていると、それらのカードを手持ちに入れるメリットはあまりなさそう。似通った展開になるのを避けるため、最初から2を持ってみたり、少しルールを変えて何度かプレイした。

次に「タギロン」。個人的にこれは大当たりだった。数字と色の書かれたタイルが20枚あって、3人プレイだと一人5枚配った後、互いに質問し合って残りの5枚を特定するというゲームになる。残りの5枚に対しては何も質問できないため相手二人が持つタイルをすべて特定する必要があって、結果として誰か一人に質問が集中してもそれだけでは勝敗は決まらない。このバランスの取り方に感動した。

質問は、場にある質問カードを一つずつ消費しそこに書かれた内容を聞くことで行われる。数字に関する質問より色に関する質問のほうが少なく、それを一人にほとんどぶつけた結果もう一人の色がなかなかわからず苦労するという場面もあった。

購入したボードゲームは3種類で、最後は「ito」。1から100までの数字を一つずつ持ち、その大小をお題に沿って言葉で表現することで、大小関係がどうなっているのかを特定するゲーム。プレイ人数10人までのところを3人でプレイしたためか、前二つに比べるとちょっと微妙という感想。もしかしたら単にお題が合わなかっただけかもしれない。95と96の順番を当てた回があって、かなり嬉しかった。

一通りプレイしてからはいつものようにおすすめ動画（MAD）を見たりまたボードゲームをプレイしたりしていた。今日見たMADで印象深いのは以下の三つ。

www.nicovideo.jp

「背中の傷は剣士の恥ィ」。これは自分が紹介したやつ。最近結構な頻度で見ている。何もかもが好き。「ウソップはこの島に置いていく！帝京魂！」のセリフが特に意味不明で良い。

www.nicovideo.jp

「みゃー姉が死んだ回」。原作では死んでいないらしい。ホスフィンによる各シーンの解説があって、構成の巧みさに驚かされた。RubikunさんのTwitterアイコンになっているキャラはこの作品由来らしく、アニメではアイコンで見たことのない表情も多く違和感がかなりあった。

www.nicovideo.jp

「デスノートで人が死んだ回」。出オチ。先ほどの作品とさらにその元作品「おジャ魔女どれみで人が死んだ回」を見た直後だったため、落差で笑いが止まらなかった。

午前4時頃にラーメンを食べに行った。腹が減っていると思ったものの、食べたら食べたで少し気持ち悪くなってしまった。その後解散。正確には、たいぺーとは帰り道で別れ、ホスフィンとは帰宅して一休みした後別れた。

今日はキレートレモンやお茶をたくさん用意し積極的に飲むようにしたため、このように全員で外に出るような元気を残すことができた。今後も心掛けたい。用意したお酒のうちではカルーアミルクを結構な量飲み残してしまった。ミルク系の甘いお酒は好きだがだからと言ってたくさん飲めるわけでもないようだ。

47度のジンが一瓶空いたのはびっくりした。このジンをストレートで口に含んでみたところ、よく小説などで目にする「喉が焼けるような」という感覚を得ることができた。そんな感じだからきっと飲み切れないと思っていたのに、適当にジュースと混ぜると苦みがなく非常に飲みやすいお酒になってどんどん杯が進んだ。

少し部屋の掃除をして午前6時くらいに布団に入った。何かスマホを触ろうとした記憶はあるが、すぐ寝落ちした。

01/12(木)

午後3時起床。シャワーを浴びて準備し、大学に向かった。TA。

年が明けて初めての講義となる。内容は昨年最後の講義で行われた発表の続きからだが、その時特に難しいことをやったわけでもないため復習などはなかった。

30分次の人の発表を行ったところで時間になった。これで今年の講義は終わり。
週記（2022/12/19-2022/12/25） - kotatsugameの日記

超多面体の話。特に $n$ 次元の特別な超多面体に含まれる $k$ 次元単体の個数を数え上げるのがメインだった。 $n$ と $k$ に関する漸化式を立てて、それを解く。解くと言っても答えは教科書に載っているため、適当に帰納法で示すだけになる。

変数が二つあって混乱しているようだったので、その周りでいくつか指摘したり助言したりした。シンプルに $n$ だけ見ても解けるし、変わり種として $n+k$ についての帰納法を使ってもよい。そもそも前者がおぼつかない様子だったので、後者については特に何も言わなかった。

午後6時過ぎに終了し学食に向かった。5限終了直後でもないのに3台稼働しているレジにそれぞれ10人弱並んでいて驚愕。一体何をしているのかとよく見たら、現金払いが多いらしい。生協のアプリ登録に失敗した人々だろうか。またアプリを用意していた自分も決済バーコードの読み取りに微妙に時間がかかって、まんまとレジの詰まりに寄与してしまった。どうしようもない。

午後7時帰宅。メールを確認したらABC277の賞金が届いていた。アマギフ60000円分だった。この回は賞金がかなり高額な回だったらしい。額面がメール文面に書いていなかったためびっくりした。

生協のアプリについては今もTLにそこそこ愚痴が流れてくる。そんなツイートの一つに以下のようなリプライがついていた。これが本当なら少しだけ納得も同情もできる。不便になったのは覆しようのない事実のため、もうちょっと何とかならなかったのかとは思うが。

失礼します。大学生協で学生理事をしていたことがある者です。
もはや学内から人がいなくなり、生協の経営が悪化しました。これまでの野村総研のPOSレジは保守費用が高額だったので、簡易なレジを導入することになりました。そのため、電子マネーがカードからスマホアプリになりました。
— えぐっちー (@soki124) 2023年1月12日

日記を書いて午前6時就寝。

01/13(金)

午後1時45分起床。15分後から1on1。

結局年末年始は何もしなかった。その間に自分ができるタスクがいくつか用意されたらしく、今日はその説明。まず一つ、昨年後半に携わっていたコードで大きなエクセルシートを処理すると実行が終わらなくなってしまうことの解決。二つ、昨年末に話題に上がったツールを本格的に使い始めるための下調べ。前者がかなり難題で、もっぱらそれを解決する方針決めに時間を使い2時間ほどのミーティングとなった。

大きなシートといっても真っ当にデータが多いわけではない。手作業のミスによって右・下方向限界ギリギリのセルに値が入っているようなシートが存在して、それを処理できないらしい。読み込みにはopenpyxlというライブラリを使用していて、そのデータにすること自体までは特に時間もかからない。なぜなら、値が入っているセルのみをdictとして保持しているだけだから。

しかしそこからうかつに行を取得したり列を取得したりした瞬間、一番端のセルに合わせてその間の値が入っていないセルも全部新たに作成してしまうらしい。この一番端というのは取得した行・列の一番端という意味ではなく、シート全体の一番端という意味である。つまり、セル $(1048576,16384)$ に値が入っていれば、すべての列が高さ1048576になるし、すべての行が幅16384になる。

こういう大きなシートでは、端にあるセルは単に無視することになった。しかしそれを実装するだけでも値が入っているセルだけを一つ一つ見ていく必要があって大変。そういうことをするメソッドは用意されていないようだったため、外から触られることを想定されていなさそうな_cellという変数を直接見ることになった。

たいぺーが水曜日に空けたジンの瓶を引き取りに来た。可愛いので取っておきたいらしい。洗って乾かしておいたのを引き渡し、ついでにその他の瓶をゴミ捨て場に持っていく手伝いをしてもらった。キレートレモンの空き瓶が10本あって一人では面倒だった。

午後4時40分からサークルバチャ。5問目はかなり最近の問題だから覚えていて、6問目は条件をいくつか集めたら通って、7問目は「二つの要素が同じタイミングで操作されると以降どちらが先に並ぶかは半々」というクリティカルな考察がスムーズに出てきた。結果35分で全完し、Estimated　Performanceが5029と見たことのない数字になった。

https://kenkoooo.com/atcoder/#/contest/show/57415d67-4fc2-4e97-a222-3e24052aaecd

解説をチェックしたりして時間を過ごし、バチャ終了後に少し感想戦をして解散。

日付が変わるまで今日期限のレポートと格闘していた。昨年末に受講した集中講義「理論言語学研究演習I」の課題である。最近の自然言語処理はニューラルネットでポンという感じで、言語学的知見が活かされているとは言えないとのこと。活かすにはどうすればよいか意見を書けという課題だった。

自分はまず、LSTMとAttentionという講義で扱われたニューラルネットのブレークスルーを達成した仕組みについて元の論文を当たり、本当に言語学的知見が活かされていないのか調べた。長距離依存という用語が出てきているのだし何かあるだろうと思ったのだ。しかし事実として何もなかったため目論見が崩壊。今更レポートの方針を変えるような時間もなく、適当なことをモゴモゴ書いてお茶を濁した。しかも提出が数秒間に合わなかった。まあこのくらいは十分許してもらえるはず。

その後はずっとラノベを読んでいた。午前3時頃「クラスで2番目に可愛い女の子と友だちになった」3巻を読了。ダダ甘。ついにヒロインたちとクラスでも関わるようになり、見せつけるような感じになって読んでいて非常にニヤニヤできた。タイトルにもなっているヒロインと恋人同士になったにも関わらず、結構な頻度でその友達を含む男1女3で行動していてこれも好きな展開。しかし主人公は一途なので、ちゃんと恋人を特別扱いしていた。偉い。

別のラノベに手を出したが、急激な眠気に襲われ午前5時くらいに寝落ちした。

01/14(土)

午後4時頃に冷凍弁当を受け取った。その前後1時間ほどは起きてスマホを触っていた記憶がある。二度寝した後、午後6時起床。

ラノベを読んで過ごし、午後9時からARC153に出た。

AtCoder Regular Contest 153 - AtCoder

Aは $(S_1,S_3,S_4,S_5,S_7,S_8)$ を辞書順に探索すればよい。6重ループを書いた。

Bは操作を把握した瞬間「全体をいくらかシフトして180度回転したもの」になるとの直感を得て、実際そうと確認できたところまでは順調だったものの、実装方針にかなり苦しんだ。何を計算すれば盤面の状態を表現できるのかわからない。最終的にはマス $(1,1)$ の行き先を追った。

Cは実装が面倒だと思ったら整理するうちにどんどんシンプルになっていった。最初の考察として、 $i\lt j$ について $(A_i,A_j)=(-1,+1)$ だと必ず $A_ix_i+A_jx_j\ge j-i$ になり、 $(A_i,A_j)=(+1,-1)$ だと $A_ix_i+A_jx_j\le-(j-i)$ になるというものがある。つまり、どちらかのペアだけで $A$ の要素をすべて使い切れた場合、条件を満たす $x$ は存在しない。そうでない場合を考えたい。

先ほどのような $i\lt j$ によって $(\pm 1,\mp 1)$ のペアを作った後、まだ $A$ が余っていればそれを使って調整、余っていなければ $(+1,-1)$ のペアと $(-1,+1)$ のペアを使って調整すればよさそう。ペアを適当に組むと考えにくいため、左からstackを用いる方法で固定した。これだと2種類のペアが固まって現れるため調整しやすい。

$A$ が余っている場合は簡単。例えば余っている要素で最も左にあるもの $A_j$ を選ぶと、ペアの作り方からそれより左はそこだけでペアが完結しているため、 $x_1\dots x_j$ から一気に $X\gt 0$ を引くことで、 $x$ が狭義単調増加であるという条件を満たしたまま $\sum_i A_ix_i$ から $A_jX$ を引くことができる。最も右にあるものを選んでも同様。最初に $x_i=i$ と決めておき、 $X=\left|\sum_i A_ix_i\right|$ としてどちらかを選べばうまくいく。

$A$ が余っていない場合も最初に $x_i=i$ としてみた。 $X=\sum_i A_ix_i$ が正だった場合のことを考える。 $(A_i,A_j)=(+1,-1)$ というペアを探して、 $x_j-x_i$ を今より $X$ だけ大きくすることで調整可能。ただし大きくしたときに他のペアと干渉するとまずい。

区間 $(i,j)$ が交差しないペアなら適切にずらせばよい。交差する場合、ペアの作り方から完全に内側にあるか、完全に外側にある。内側は関係ないため無視。外側はどうしようもないが、そもそも包含関係で最も外側にあるペアを選べばよい。復元はちょっと面倒だった。ペアに対して $x_j-x_i$ がいくつになるべきかという値を管理し、左の要素から順番にペアの相方と一緒に決めていった。

D。 $f(A_i+x)$ は $f(A_i)+f(x)$ から繰り上がりが起こった回数の9倍を引いた値となっている。また、 $A_i+x$ の計算時に $10^k$ の桁で繰り上がりが起こることと $(A_i\bmod{10^k})+(x\bmod{10^k})\ge 10^k$ であることが同値。さらに $x\ge 10^9$ のとき $x\leftarrow x\bmod{10^9}$ としたほうが得だと示せたため、繰り上がりの起こる桁は $10^0\dots 10^8$ のみだと考えてよい。

よって $x$ を決めるごとに9回の二分探索で $\sum_i f(A_i+x)$ が求められるようになった。 $x$ としては、ある $i$ に対して $A_i+x$ の下数桁を0にする最小の値だけが候補になると考えたが、証明できない。とりあえず書いてみたらサンプルは合ったものの、出したら当然のように落ちた。

$x$ の下5桁を全探索し、上4桁はデータ構造で決めるという方法を考えていたら、頑張ればできることに気づいた。こうやって別々に考えるとき問題になるのは下の桁からの繰り上がりが上の桁の繰り上がりに関係するケース。例えばサンプル4なら下5桁が46847以上のとき、そうでない場合に比べて上4桁が「8で終わる」「68で終わる」「468で終わる」「8468で終わる」ものそれぞれに対し繰り上がりが1回ずつ追加される。

上4桁を逆順に並べてインデックスとすると、これは区間加算で対応できる。例えば「68で終わる」数はインデックス $[8600,8700)$ に対応する。下5桁を昇順に試しながらこういう更新をしていけば答えが出る。逆向きにしたり68や468といった繰り上がり直前の値を求めるところで頭を壊してしまい、残念ながら5分ほど間に合わなかった。

結果は3完120位。今回は画面録画に加えマイクに向かって喋りながらコンテストに出ていたのだが、結果がひどいため動画データは即座に消去した。コードゴルフはAのみ。99999を足すと $S_1S_3S_4S_5S_7S_8$ という6桁の数が得られるため、適切に数字をコピーして求める数を作るという解法。Vimで実装した。

ずっとラノベを読んでいた。午前5時に「黄金の経験値」を読了。やはり面白かった。以下、微妙に書籍の先のネタバレを含む感想。

なろう版からの大きな修正として、ブラン視点がすっかりカットされていた。これは個人的には読みやすくなって良かったと思う。物語が軌道に乗る前から複数の、それも独立しているように見えた視点があると、それはほとんど別作品を並行して読んでいるのと変わらなくて話の進みが遅くなりちょっと辛い。

なろう版を読み主人公レアのキャラクター性を知っている状態で最初から読むと、ちょくちょくあったそれらしい描写を見つけることができて非常に楽しかった。レアのキャラクター性というのは、自分の捉え方ではわがままだったり、肝心なところでポンコツだったりというもの。この主人公、いかにも魔王然としたビジュアル・行動なのに性格にはそういうところがあって、そのギャップが可愛らしい。

また作品の設定も改めて上手いなと思った。PCとNPCの違いは「システムメッセージを受け取れるかどうか」のみであると最初に明確に説明され、以降の設定はすべてここに絡んでいる。例えばNPCがリスポーンできないのは、リスポーン用のシステムメッセージが受け取れないから、だろう。これが他キャラに「使役」されると自動的にリスポーンできるため、NPCも不死身になる。

別のラノベを読んで午前9時前に就寝。

01/15(日)

午後6時起床。食事してしばらく日記を書き、午後9時からコンテストに参加した。

今日は午後9時からABC285があり、午後9時5分からCF #844 combinedがあった。両方参加した。

AtCoder Beginner Contest 285 - AtCoder

Dashboard - Codeforces Round #844 (Div. 1 + Div. 2, based on VK Cup 2022 - Elimination Round) - Codeforces

まずABC。Aはよい。Bは $i$ ごとに $l$ をインクリメントしながらチェックすると高速。Cは適当にやれば合う。Dはよくわからなかったが、雰囲気から $S_i-T_i$ 辺にループがあるかどうかで判定できるだろうと思った。

Dの実装中にCFが始まってしまったが、A問題のページ読み込みに時間がかかっていたのでこれ幸いと書き上げた。結局ABCは4完の状態でCFへ。

Aは上方向の移動は必ず必要なので、それを無視して平面の問題として解く。床・天井を表す長方形のどれかの辺にタッチしつつ2点間を移動することになり、どの辺にタッチするか全部試せばよい。

Bは人数を全探索する。 $k$ 人だとすれば、 $a$ が昇順に並んでいるとして $a_k\le k-1$ かつ $a_{k+1}\gt k$ が必要。合わせるのに少し手間取った。

Cは何種類の文字を使うか全探索。 $k$ 種類だとすれば $k\mid n$ が必要で、各文字は $n/k$ 回ずつ使う。元の文字列における出現回数が多い順から $k$ 個使うことにして調整すればよい。復元が面倒。

Dは平方数になる最小のインデックスを $i$ とすると、適当な $x$ 、 $t$ によって $a_i+x=t^2$ と表せることになる。このときもし $j\gt i$ なる $j$ について $a_j+x$ も平方数となるなら、ある $d\gt 0$ が存在して $a_j+x=(t+d)^2$ 。展開して $t^2$ を先ほどの式で置き換えると $a_j-a_i=d(2t+d)$ となる。

すべての $j\gt i$ に対して $t$ の候補を求め重複を数えると、 $a_i+x$ とともにいくつ平方数にできるかがわかる。 $t^2\ge a_i$ が必要なことに注意。これを $i$ を全探索して行う。 $O(n^2)$ 回10⁹オーダーの値の約数を列挙するのは十分間に合う。

Eは面倒。覆う面積の最大値なんて簡単にわかりそうもない。自明な上界としてもともと覆われていた面積があって、実はこれが達成できるのでは？と考えたら達成できた。まず高さ2の長方形だけ考えて、覆う面積を変えないようにしつつ重ならないように変化させる。長方形を一つずつ追加することを考え、追加の際完全に覆うものは取り除き、他と重ならないよう縮めるという方法で行える。

残りは高さ1の長方形で、上の行と下の行それぞれ独立に先ほどの操作をすればよい。長方形を取り除く際、それが高さ2だった場合高さ1に縮めるという処理に置き換わる。面倒に見えて、同じことを3回やるだけなので実装は案外簡単だった。入出力が閉区間なのに注意。サンプル1が強いので適当に投げてもペナになりにくい。

ここまで1時間で、現在20位台。あらかじめこの辺りでABCに戻ろうと思っていたため、Fを頭に入れてからABCのEに戻った。

Eは曜日1を休日と固定してよい。休日1日とそれに続く平日何日かをまとめて生産量を計算し、それを組み合わせる遷移でdpした。

Fはかなり苦労した。結論から言えば、区間 $[l,r]$ が昇順に並んでいること、区間 $[1,l)$ と $(r,N]$ に $S_l$ より大かつ $S_r$ より小な文字が存在しないことが条件となる。セグ木にいろいろ乗せるとできる。具体的には、区間の両端の文字、区間にどんな文字があるかのデータ、昇順に並んでいるかどうか。

焦っていたら条件列挙も実装もミスしまくり、5ペナの末コンテスト終了4分前に通った。うっかりABCに30分弱も使ってしまったがCFに戻る。

Fは括弧列をいつもの累積和に直すと、 $x$ を取り除き、その位置に確率 $p$ に応じて $x,x\pm 1,x$ を挿入するという操作になる。これを3分木みたいに見ると状態がまとめられるのではないかと考えた。ノード $x$ があって、それ以下の部分木で $k$ 回操作するという場合、まず1回操作してノード $x,x\pm 1,x$ を作り、それらで残り $k-1$ 回操作するということになる。 $k$ を固定する必要があるため特に畳み込みにはならない。

ノードを選択する確率が計算できず困ってしまったが、冷静になると操作方法に依らず $i$ 回目の操作では $\frac 1{2i-1}$ となる。これを最後に掛けるだけでよい。

フレンド順位表を見てH1に進んだ。 $k=0$ は単なる包除原理でよい。 $k=1$ もシグナルのバウンディングボックスのサイズを決め打ち、シグナルを表示するために少なくとも1マス消灯させる必要のある領域を調べてこれまた包除原理を行うと求まる。しかし $k=2$ がどうにもならなかった。

6完29位で2841→2887(+46)。昨年秋にドカンと下げたのを多少は取り戻せただろうか。点数の差がかなり詰まっていたので、Fをもう少し速く解けるだけでも順位はそこそこ変わったようだ。この順位帯だとレート変動も大きく変わる。途中でABCに戻ったのは、やる前から明らかだったことだが悪影響しかなかった。

後悔しているかは微妙なところ。なんだかんだ言ってCFのレートは結構上がったし、ABCも250位でそこまでみすぼらしい順位というわけではなかったから。ただしABCに無理して参加した目的であるコードゴルフ的には、もう全然ダメだった。以下はそのコードゴルフの話。

Aは $2a\le b\le 2a+1$ という条件を見て縮まないなあと言っていたが、 $a=\lfloor b/2\rfloor$ でよい。明らかにdc。Bは愚直に書くとRubyもPerlも間に合わないところ、Perlで文字列XORをした後ヌル文字を探す方法だとかなり高速になった。その周りをかなり縮められて負け。Cは自分が見たときにはすでにコードゴルフされきっていて、言語を変えても縮まなかった。DはAWKでこれも大敗。以降は手付かず。

時系列は前後するが、CFの終了直後にABC-Gをupsolveした。結構素早く解けたとは言え10分ちょっとかかっているから、コンテスト中にGに進んでも間に合わなかっただろう。

そのまま二部マッチングにすると2を使い切るという条件がうまく表現できなかったため、頂点を倍加してみる。すべての2を使うようなマッチングが存在すればよいと考えた。ここは注意が必要で、 $1\times 2$ のタイルを置く際は覆う2マスを倍加したものが互いにペアになっていてほしいのに、そうでない可能性がある。

しかしこれも適切に修正できそう。そういう食い違ったペアを辿っていって、もし途中で途切れたらそこから遡って修正していけるし、サイクルができたら偶閉路だから全体を一気にずらせばよい。出したら通った。Nyaanさんのユーザ解説が同じことを言っている。

昼間までずっと日記を書いていた。合間にラノベを2冊読了。

1冊目は「ガリ勉くんと裏アカさん」。クラスのアイドルであるヒロインが裏垢女子であることに気づいて……という導入。しかしむしろ裏垢云々以外の部分が面白い。特に主人公のキャラクターが好み。自分の中に一本芯があって、いろんなことを自分には必要ない・関係ないとして排除するというかなり極端なものだが、自分にとっては望ましいものだった。

2冊目は「迷子になっていた幼女を助けたら、お隣に住む美少女留学生が家に遊びに来るようになった件について」2巻。1巻を読んでから10か月、2巻が出てから6か月くらい経っているが、昨年末に出た3巻にかなり好みのシーンがありそうだったため今更読むことにした。周囲の人間の行動が主人公にとってかなり都合が良いと感じるものの、それ以外の部分は良い。日記を読み返すと1巻を読んだ時はネガティブな印象を抱いていたらしく、それを忘れ去っていたのも良い方向に作用しただろう。

正午就寝。