12/19(月)

午前8時少し前に起床。今日から集中講義である。夜中に降った雪が多少残っていたので、登校に原付を使うのは避けることにした。結構早めに起きたのでそれでも間に合うくらい。

徒歩で大学に向かい、川内北キャンパスのいつもの学食で朝食を摂ったあと、さらに隣のキャンパス、つまり川内南キャンパスに移動。以前場所をチェックしておいた文学研究科棟の講義が行われる教室にたどり着いた。思ったより小さな教室に思ったより沢山の人がいて、始まるころには席が完全に埋まっていた。

文学部のキャンパスに足を運んでみた。集中講義のための偵察である。教務課に突撃して教室がある建物を教えてもらって、実際に足を運んで確認。
週記（2022/11/28-2022/12/04） - kotatsugameの日記

いよいよスタート。講義のタイトルは「理論言語学研究演習I」であり、月・火・水は1限から4限まで、木は3限までの全15回の予定。初回の今日は、午前中は自己紹介とイントロダクション、午後は基礎知識のおさらいだった。

自己紹介によれば、自分以外の全員が文学部・文学研究科の言語学を専攻する学生らしい。院生は当然研究テーマを持っているし、学部生でも自分の卒論テーマがあったり、少なくとも興味のあることを説明できていた。

その中で自分は全くの興味本位の履修ということもあり、ちょっと腰が引けてしまう。自然言語処理というキーワードに惹かれたと説明したが、それもよく考えれば自分の専攻と関係ない。また言語学関係の講義を受けたことがないのもほぼ自分だけのようだ。

イントロは……理解できたのかどうかがわからない。計算心理言語学・計算神経言語学についての講義であること、この学問は人間の言語処理を計算機上でモデル化しようとするものであること、講義は言語処理の要素ごとに人間の処理と機械の処理を比較して進められることが説明された。日本語にすればこれだけだが、実際に何をやるかということは全くイメージできなかった。

昼休み。朝しっかり食べたのであまりお腹が空いておらず、また正午過ぎということで学食が非常に混んでいたため、総菜パンを買って済ませることにした。

午後は言語学、数学、神経科学の基礎だった。まず言語学について、この講義では音韻論、形態論、統語論、意味論と分けて扱うらしい。順に、音声→文字列→単語列→構文→意味という言語処理の流れの矢印に対応するという認識をしている。これらが言語処理の要素であり、人間と機械に共通するということで、明日明後日の午前・午後で一つずつ解説していくようだ。

これで言語学の基礎は終わりらしい。身構えていたので少し拍子抜け。次の数学の基礎は確率論についてで、講義スライドはベイズ統計などいろいろ書いてあって思ったよりレベルが高いなと思ったが、説明されたのはベイズの定理だけで非常に簡単だった。異世界転生したような気分。先生が板書で積の記号としてなぜかアスタリスクを使っており、しかも悪筆なので足し算に見えたのが印象的だった。

最後に神経科学の基礎。脳波の図がいろいろ出てきて理科のようだった。眠くてそれ以上の印象は残っていない。

午後4時過ぎに終了。またキャンパスを移動し、いつもの購買で予約していたラノベを買って帰宅した。

家に到着したころにはインターン先の定例会が始まっていたので、遅れて参加した。先週のうちに遅刻すると連絡しておいたが、思ったより早く参加できてよかった。先週の進捗は金曜日の1on1で行ったペアプログラミングのみで、今週も特に何もしませんと報告して終了。

勉強会はGitを自分で作ってみるという話。最近投稿された以下の記事と関係あるかなと思ったら特になく、現在のGitの仕様をいくつか再現したコードの解説だった。Gitの作法やテクニックについては何度か勉強会で扱われた記憶があるが、実装に踏み込むというのは目新しい。仕様の細かい話が聞けて良かった。

Gitは最初1244行しかなかった

集中講義の教室変更の連絡が来ていた。今日ですら満員だったのに明日からの教室はもっと小さいらしく、急遽別の部屋を取ったようだ。新しい教室は川内北キャンパスにある。近くなったのは嬉しい。

深夜までずっと先週の週記を書いていた。午後11時過ぎにひとまず書き上げて投稿。当然校閲も何もしていない。CFに間に合わせようと必死だった。

少し空いた時間で帰省の日程を考えた。12/28がICPC二日目で、いったん仙台に帰ってくる。その後Good Bye 2022が12/30らしいので、12/29に帰省することにした。慌ただしいが頑張りたい。

午後11時半からCF #840 div.2に出た。

Dashboard - Codeforces Round 840 (Div. 2) and Enigma 2022 - Cybros LNMIIT - Codeforces

Aはbitごとにソートする感じ。Bは高々 $O(k)$ 回のシミュレートでダメージを与えられなくなるか全員を倒せる。

Cは難しい。隣接する2要素に対して2回操作すると0を作れて、それと最大値を組み合わせて操作できれば一番よい。これを使って、 $n\ge 4$ の場合は必ずすべての要素を最大値に揃えることができる。 $n=2$ の場合は簡単。 $n=3$ の場合がどうしようもなかったので、思いつく限りの操作を試すことにした。3WAしつつ何とか通した。

Dは $k$ を固定し、そこから $n-1\dots 1$ の順で左右どちらに並べるかdpした。1ケース当たり $O(n^3)$ だが定数倍が軽いのでかなり高速だった。

Eは強連結成分ごとに対応する三角数がreachableなペアに寄与する。unidirectionalなペアの数を最大化するには強連結成分を一直線に並べるのが最適。検索するとどんな非負整数も高々3個の三角数で表せるらしいので、それを全探索してみた。しかしWA。どうやら4個以上使うのが最適なケースもあるらしい。冷静になると単にdpするだけでも遷移が各状態からそれぞれ $O(\sqrt p)$ 通りしかないので、間に合う。

Fはかなり面倒だった。 $a$ と $b$ を結ぶどれかのパスに乗る辺であって橋でないものを数えたい。2頂点連結成分分解か2辺連結成分分解を使うはずで、前者は持っていないし詳しくもないので後者で考えることにした。成分に分解した後は木になるので、 $a$ と $b$ を結ぶパスが1通りになる。

謎の制約から、例えば $\infty$ のような形をした成分はない。よって2辺連結成分上のどの辺についてもそれを通るパスが存在するはず。よって唯一のパスの上にある2辺連結成分が含む辺数を数えればよいと考えた。しかしWA。2辺連結成分に入って同じ頂点から出ていく場合、その成分の辺を通ることができない。この原因がわかるまで4ペナ重ねた。

修正は気合い。分解するときに成分と成分の境界となるような頂点をチェックしておき、両端とLCAについてはクエリごとに処理、その間は前計算の時に考慮して数えることで対応した。コンテスト終了3分前に書き終え、提出したら通った。

かなり不安だったのでシステスを見守っていた。何とか全部通って全完8位。

午前2時過ぎに布団に入り、しばらくハーメルンを読んで3時前に就寝。

12/20(火)

午前8時起床。昨日と同様徒歩で登校し、学食で朝食を摂って教室に向かった。先生が迷ったらしく、講義開始は少し遅れた。

午前は音韻処理の話。うずまき管という器官で音を周波数要素に分解しているがこれはフーリエ変換であるとか、異なる種類の音素を聞いたとき脳の異なる領域が活動しているので、音素の分類には人間の都合以上にしっかり意味があるとかの話が面白かった。

人間は音を一定時間ごとに区切って認識しているようなので、機械で音声認識する場合もそうやって区切り、区間ごとに特徴量を抽出してそれぞれ音素に当てはめることになる。この時直前までの音素も参考にして、認識したい言語としてどれが一番もっともらしいかを調べるそうだ。直前の音素のみを考慮することで隠れマルコフモデルとして扱い、ビタビアルゴリズム等で決定する。あるいは最近だと再帰的ニューラルネットワークでやってしまうのが主流らしい。

午前10時から1時間は先生が会議に参加するため休憩となった。この間寝ていたら休憩後もずっと眠気が取れなかったので、昼休みはずっと本を読んでいた。満腹による眠気を避けるため昼食も摂らなかった。

午後は形態処理、つまり形態素解析の話。MeCabだ！と思ったらMeCabという単語は一切登場しなかった。

人間が単語を目にするときと耳にする時では、その情報が脳に到達するまでの時間が異なるのに、その後の脳の活動が経過時間も含め次第に似たようなものになるらしい。つまりその辺りが形態処理以降を司っている部位なのだが、まるで集積回路のクロックのように時間が揃うのは面白いなと思った。

機械の形態処理は音韻処理の時と同じで、音素を決定する代わりに品詞を決定するだけ。最初に単語を一般的な形にする前処理を行った後、隠れマルコフモデルにしたり、再帰的ニューラルネットワークでやってしまったり。あまり目新しいことはなかった印象。

今日はちょっと早めの午後4時前に終わった。予約していたラノベを買って帰宅。しばらくTLを見たりYouTubeを見たりした後、再度外出した。

まずみどりの窓口に行って帰省用の新幹線の切符を買う。学割証だけはICPC用の切符を買うときに発行してあった。混むだろうからと指定席を取るよう言われている。仙台駅内のネット回線が込み合いすぎて時刻表を開けなかったので、窓口で遅めという希望を伝え探してもらった。あと10日もないしもう席が残っていないかもなと思ったら全然そういうことはなく、無事いい感じの時間の新幹線が取れた。

みどりの窓口を出てから駅の隅に仁王立ちし、今日の昼休みに読み進めて残り僅かになっていた本を読了。「池袋ウエストゲートパーク」15巻。

今日読んだのは短編四つのうち最後の一つだけで、他三つはかなり前に読んでいた。確か8月末のオンサイトに持っていって、その帰りだったはず。どれも嫌みではない含蓄があって非常に面白かった。それはシリーズ全体を通して言えること。

アクションシーンでも解決のシーンでもタカシの出番がたくさんあって嬉しい。特に二つ目の短編「西池袋ドリンクドライバー」のラストは解決の流れも含めかなり粋。普段見えないタカシの人間味がサラッと出てきて、読んでいてじんわりとした感動があった。

駅を出て本屋に寄り、さらにラーメンを食べてからゲーセンに向かう。午後7時半から午後11時くらいまで遊んでいた。今日は14+のAJが四つ。また手元をいくつか撮った。

PUPA 21-0-0 手元 pic.twitter.com/ZSufZg0J2T
— こたつがめ (@kotatsugame_t) 2022年12月20日

スマホアームを忘れて店を出てしまい慌てて戻る一幕がありつつ、帰宅。シャワーを浴びる気力を蓄えるために、結構な時間TLを眺めてボーっとしていた。

撮った動画をツイートしてから布団に入り、午前1時半就寝。

12/21(水)

今日も午前8時起床、徒歩で登校、学食で朝食。

午前は統語処理、つまり構文解析の話。脳のどの領域が構文を捉える役割を果たすか調べるのに、普通の文と比較して「構文は正しいが意味を持たない文」を使う。そういう文のことを「ジャバウォッキー文」というらしい。鏡の国のアリスに出てくる「ジャバウォックの詩」に使われたいくつかの英単語が、ルイス・キャロルの創作だったことが由来。

機械の構文解析の話は、人間の言語を文脈自由文法で記述することから始まった。実際にはもう少し制限が弱いらしいが、ともかくこの文法をもとに構文木を作る。この制限の話の際、チョムスキー階層について言及されてオッとなった。

文章からボトムアップに木を作るのは区間dpで解けるなと思っていたら、紹介されたCYK法がまさにそのもののアルゴリズムだった。変換規則の出現確率を元に最もそれらしい構文木を作るのも、dpだと思えば自然な拡張。

ニューラルネットを使う場合は、dpテーブルをそれで埋め、構文木の復元自体はCYK法と同様に行うようだ。確かに、出力としてわざわざ木をエンコードするのは無駄か。

昼休み。今日も昼食は摂らず、ずっと本を読んでいた。

午後は意味処理の話。いろいろな観点で単語を分類し、それぞれ見せて脳のどの領域が活動するか調べた結果、脳全体に分散して意味というデータが保持されていることが分かったらしい。一方、脳の特定領域が委縮してしまった人が、意味性認知症というその名の通り意味をうまく記憶できなくなる障害を負うことが知られている。

つまり、意味が脳全体で表現されているとしても脳の一部で表現されているとしても矛盾してしまう。そこで現在は、分散して表現されつつもそれを繋ぐハブとなる領域が存在する、ということになっているらしい。正直身も蓋もないという気持ちになった。

機械の意味処理については二つの手法が紹介された。一つは述語論理とラムダ計算によるもので、単語にラムダ式や述語を対応させ、パースした構文に沿ってそれらを関数適用していくことで、文全体を表現するラムダ式を得るというもの。命題論理、述語論理、ラムダ計算とβ簡約などがサッと解説され、知っていることだらけで初日以来の異世界転生気分になった。

もう一つは単語ベクトルによるもの。隣接して現れる単語をカウントするだけでそれっぽい特徴量になるらしい。ベクトルの足し引きで意味の計算が行えるのもよく聞く話。本題とは関係ないが、aardvarkという英単語が何度か登場して面白かった。辞書順最小の一般名詞だからだろうか。実際に最小かどうかは知らない。

午後4時過ぎに終了。今日も今日とて予約していたラノベを買った。その後、学食の夜の部が午後5時からだと思っていたら30分早くなっていたので、開店を待って夕食を摂ってから帰宅した。

最近コンテストがなくてすっかりご無沙汰だったCodeChefのレーティングシステムが新しいものになったらしい。今は古いものと新しいものの2種類のレーティンググラフが表示されている。自分のレートはこの更新で2832→2889(+57)となったようだ。新しいレーティングシステムでも現在がhighestである。

Rating system update - Elo MMR final migration - announcement - CodeChef Discuss

明日は木曜日なので、いつも通り5限にTAがある。集中講義は3限で終わる予定なので、多少長引いたとしても余裕は十分にある。明日発表される資料が上がっていたので、読んでコメントをつける作業をした。

午後9時くらいに布団に入った。昨日も今日も眠くて仕方なかったので、今日こそたっぷり眠るつもり。本当は12時間睡眠をキメる予定だったのにすでに破綻しているし、その上布団でラノベを1冊読んでしまった。

「名探偵は推理で殺す」。バトルロイヤルに推理がどう関係するのかという点で、作中では推理が効くというルール自体を推理で導いていたが、ここがかなりこじつけに見えてあまり納得できていない。その他の推理シーンも同様。ではバトルそのものはというと、強そうな技を取りそろえる主人公であっても無双するわけではなく、自分の好みからは外れた。

さらにしばらくなろうを読んだため、結局就寝は午後11時半だった。

12/22(木)

午前7時半起床。二度寝するか迷っていたらそんな時間も無くなってしまい、午前8時前に布団から出た。いつも通り徒歩で大学に向かい、学食で朝食を摂る。今日は雨が降っていた。

午前は言語獲得の話。これは人間と機械の比較というよりそれぞれについての解説だった。

人間の文法はすべてを経験から獲得するということができない。なぜなら、経験する文はすべて文法的に正しいはずで、正しくない文、いわゆる非文は原理的に経験できないから。これを刺激の貧困という。経験しない文は非文であると考えると、今度はやたら複雑な文も全部使えなくなってしまう。よって人間は生まれつき文法に関する何らかの知識・仕組みを持っているはず。

これについて、一定の原理といくつかのパラメータを持っているとするモデルが紹介された。経験から強化学習のようにパラメータのオンオフを切り替え、言語特有の文法に合わせていくというもの。1文経験するごとにパラメータの学習が行われると文法がブレまくって不自然だから、バッチ処理が行われているらしい。またこのモデルの正しさを裏付ける証拠として、より多く経験する文法がより早い成長段階で獲得されるという事実がある。

余談的に「袋小路文」が紹介された。文法的に正しく意味のある文章だが、パースが難しく混乱してしまう文章のこと。大人はパースに失敗したら戻って再解析することができる一方、子供はそれができないらしい。

機械の言語獲得に関してはいろいろなニューラルネットワークが説明された。ただの再帰的ニューラルネットワークでは文章中の長距離依存をうまく記憶できないので、それを何とかするためにLSTMを使ったり、Attension機構を取り入れたり。

前者のLSTMについては名前だけ聞いたことがあって、今日Long Short Term Memoryの略だということや長距離依存を記憶する仕組みを備えていることが知れてよかった。後者はいわゆるTransformerで、インターン先勉強会のためAlphaCodeのpreprintを読んだときに少し調べたことがあった。

最後に、文章から直接意味を抽出するようなニューラルネットワークでも、どうやら層ごとに形態素解析・構文解析など普通の言語処理をやっていそうだという論文が紹介された。どうやってそういうことを調べたのかは知らないがかなり興味深い。

2限終了の時刻から30分ほど遅れて昼休み。今日も絶食して本を読んでいた。

3限はポスドクの方の講義で、脳情報を解析する話だった。データを処理するのにMATLABやPythonを使い、評価にRを使ったらしく、かなり情報工学的な内容だった。それ以上はよくわからない。

その後まとめとレポート課題の説明があった。期限は01/13。〇〇について思うことを書けという曖昧な題意で、何を書いたものかよくわからない。講義の記憶が薄れないうちに手を付けたいとは思う。午後3時頃に今日の講義、ひいては集中講義の全日程が終了。

購買で菓子パンを買って食べた。さらに予約していたラノベを買った後、空き教室に入って5限まで本を読んでいた。1冊読了。

「貴族令嬢。俺にだけなつく」。主人公の前世の意識が今の身体に憑依したのが18歳時点で、すでに学園での評価が憑依前の横暴な性格で固定されてしまっていた。そこから数日でヒロインに受け入れられるというのはかなり違和感がある。この点は自分にとって受け入れがたく、以降の展開も冷めた見方をしてしまいうまく楽しめなかった。

先ほど買ったラノベはその前の巻を読んでいないものだから、これで読む本がなくなってしまった。5限までの残り時間は日記を書いていた。

TA。今日の発表は、先週の講義後にかなり長い時間練習してもらったし、昨日も発表資料にコメントをしたので、かなりいい感じに進んだと思う。1時間程度で終了。聞きながら気になる点があって指摘してしまったが、これもちゃんと昨日の時点で気づいてコメントに含めておくべきだった。

その後30分次の人の発表を行ったところで時間になった。これで今年の講義は終わり。来年はおそらく01/12からになるだろう。この先数回の発表予定を決めて学生は解散。自分はその後先生と少し話して別れた。

学食で食事して帰宅。疲れ果ててしばらくTLを眺めた後、午後9時くらいにシャワーを浴びてからTCB54に参加した。

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

3問目まではよい。4問目は細かいことを考えるのが嫌だったので辺の通る順番と向きを全探索した。5問目は辺 $uv$ が奇閉路を作るかチェック。6問目はどこかで見たことのあるような問題で、連結成分内なら自由に値を移動できる。

7問目は、ただ入次数が0の種を数えてはいけない。強連結成分分解してから、入次数が0の強連結成分それぞれについて、含まれる種における個体数の最小値を答えに足す。

8問目はかなり面倒だったが一発で通ってハッピー。適当に根を決めて二つのパスをLCAで分割し、分割後の組み合わせ四通りについて解く。この変換をすると、パスが上下に伸びていると思ってよくなる。そのようなパス2本の共通部分は、下の頂点のLCAからスタートして上の頂点のどちらかに到達するまでなので、単純な深さの比較で書けてしまう。

9問目はちょっと大変。HLDをbeetさんのライブラリから窃盗してきて、セグ木を乗せた。コードを読んで演算の順序を確かめながらガチャガチャしていたらサンプルが合い、出したらそのまま通った。理論値獲得の制限時間21分のところ19分32秒だった。

Heavy Light Decomposition | library

ここまでは何とか理論値で通してきたが、10問目で大変なことになった。結論だけ書く。まず、 $2^k\mid A$ となる最大の $k$ （ただし $A=0$ の場合は $k=N$ ）を探す。 $B\leftarrow B\bmod{2^k}$ を考えて頂点 $0\dots 2^k-1$ を強連結にすればよい。どの頂点からも頂点 $0$ にはたどり着けるので、逆に頂点 $0$ から全頂点に行けるようにする。

$B$ のpopcountを $i=0\dots k$ とし、これで分類して考える。 $i=0$ すなわち $B=0$ の場合は明らかに $2^k-1$ 本の辺が必要。そうでなく $i=k$ のとき、 $u$ と $u\oplus B$ のどちらか一方につなぐのが必要最低限のため、 $2^k/2-1$ 本必要。この $-1$ は頂点 $0$ と頂点 $2^k-1$ のペアの分である。

$0\lt i\lt k$ のとき、立っているbitが $B$ に完全に含まれる頂点は、そうでない頂点からbitwise ANDでたどり着ける。よって $B$ で立っていないbitが立っている頂点 $2^i\times(2^{k-i}-1)$ 個について、 $i=k$ のときのようにペアのどちらか一方につなぐのがよい。ただし $B$ のbitwise ORによってたどり着けるペアは無視する。

単純に考えれば、先ほどと同様1ペアずつ無視できるので、 $2^i/2-1$ 本の辺が $2^{k-i}-1$ セット必要になりそう。しかし $i=1$ のとき $2^i/2-1=0$ となり何かがおかしい。実は $i=1$ のケースでは、無視するペアに $B$ のbitwise ORによってたどり着くための元となる頂点が存在しないのだ。よってこのケースのみは $2^{k-1}-1$ 本の辺が必要である。

複雑な和を閉じた形にするのはWolfram Alphaに投げた。以上のことを実装するとようやくサンプルが合ってそのままAC。制限時間24分のところ47分使ってしまい、-23ptとなった。

その後ICPCチーム紹介スライドの準備を始めた。今日が提出期限。コロナ禍前の2019年のスライドを引っ張り出そうとしたがどこにもなかったので改めて作り直す。チームメイトから意見を集めた結果それなりに満足のいくものができた。1点、ワードアートに創英角ポップ体が使えなかったのが残念。手元のWordには入っていないようだ。この辺りを調べていたら日付が変わってしまい、微妙に期限後の提出となった。

しばらく日記を書いて午前3時半就寝。

12/23(金)

午後0時半起床。買ってあった菓子パンを食べて午後1時から1on1に臨んだ。

今週も特に何もない。こちらの進捗は当然ないし、振れるタスクもほぼないらしい。これから使いそうなツールが紹介されて、それを少し触ったり、運用についてアイディアを出したりするのが年明けまでのタスクとなった。1時間程度で終了。

少しコードゴルフした後布団に戻り、しばらくなろうを読んで、午後3時半ごろ寝落ちした。

起きたら午後5時半だった。今年最後のサークル活動をサボってしまい後悔が押し寄せる。目覚ましもかけてあったし、何ならそれを止めた記憶まである。しかし身を起こすことができなかった。

そのまま布団でなろうを読み続けていた。午前1時半頃寝落ち。

12/24(土)

午前9時に目を覚ました。ハーメルンの作品の書籍版情報が二つほど出ていた。

『アラサーがVTuberになった話。』
第2巻は2023年2月28日発売予定です
予約特典情報は別途お知らせ致しますhttps://t.co/1105Rj8c6F
— とくめい@アラサーV3巻7/28発売 (@hameln_tokumei) 2022年12月23日

作者が嬉しいお知らせです。
「バスタード・ソードマン」がKADOKAWA ファミ通文庫様より書籍化される運びとなりました。
イラストレーターはマツセダイチ様です。
発売日などはまだ未定ですので、続報をお待ち下さい。

とうとうリッチマンの作品が紙になる…。

(ヽ◇皿◇)ﾔｯﾀｰ　(・∀・* )ﾜｰｲ
— ジェームズ・リッチマン (@Jms_richman) 2022年12月22日

「バスタード・ソードマン」のほうは最近常にランキング上位にいるのに読んでいない。いい機会なので書籍版で読んでみたいと思う。作者が「東方遺骸王」の人なのでかなり期待している。

3時間ほどなろうを読んでまた寝た。次に、目覚ましで午後2時に起床。Xmas Contest 2022に出た。

Xmas Contest 2022 - AtCoder

Bだけ解いてDがわからず撤退。Dはカタラン数の母関数を $C(x)$ として $[x^m]C(x)^n$ が高速に取得できれば解けると分かったが、そこから先に進めなかった。 $m$ 階微分して $x=0$ を代入する方針は見込みが薄そう。

Bは、結論から言えば $S$ の先頭 $2k-1$ 文字のうちAが多いかBが多いかと $P$ と50の大小で決まる。エスパー気味に解いたが後から自分なりに理由を付けられた。

与えられた $S$ について、 $f_k(P)$ でくろうさが $k$ 問先取する確率を表す。ここで $P$ は入力の定数ではなく変数と考える。明らかに $f_k(50)=1/2$ 。また $f_k(P)$ は $P$ に対して単調な関数となるだろう。ここは直感的にそうだからとしか言えない。

以上のことから、 $f_k(0)$ あるいは $f_k(100)$ を考え $f_k(50)=1/2$ との大小を調べることで、一般の $P$ について $f_k(P)$ と $1/2$ との大小がわかる。先に確率1で $k$ 問先取するうさぎが現れるなら単純だし、そうでない場合はどちらが多くの問題を先取したかで決まる。整理すると先ほど述べた判定になる。 $2k-1$ 問しか出題されないなら両方が $k$ 問先取することはない。

撤退したのが午後5時前で、それからずっと日記を書いていた。午後9時からABC283に出た。

UNIQUE VISION Programming Contest 2022 Winter(AtCoder Beginner Contest 283) - AtCoder

Aはdc。確かにこういう問題もfor文が解禁されないと出題できなかったのか。Bは言われた通りに実装。最初からAWKを使うか迷って、結局C++で書いた。Cは00を1文字に置き換えて文字列長を答える。bashでsedとwcを使った。Dはビットで箱に入っているボールを表現し、これをスタックで管理した。

Eはちょっと面倒なdp。上の行からflipするか決めていって、直近2行の状態を持てば次の行として可能な操作が決まる。直近1行でよいと勘違いしたりして、実装には少し手間取ってしまった。

Fは端から順に見て行って、自分より右にある要素と左にある要素をそれぞれセグ木で管理。インデックス $P_i$ に $i+P_i$ や $i-P_i$ を乗せ、区間MAXや区間MINを適切に取得すればよい。

Gは $A$ の各値を $\mathbb{F}_2^{60}$ と見て、最上位bitがバラバラになるように基底を取り上位桁から決めていけばよい。いわゆるnoshi基底で十分だが真面目に対角行列を作った。

Exはfloor_sumという発想がスッと出てきた。 $X$ を二進数表記したとき、 $2^k$ の位が $\lfloor X/2^k\rfloor-2\lfloor X/2^{k+1}\rfloor$ と表せる。考えているすべての $X$ についてこの和を取るのはfloor_sumで行えて、 $k=0\dots\log_2 N$ についての和を求めればよい。

40分6秒で全完し、7位。上に5人の日本人学生がいて賞金獲得ならず。6位の方は40分ちょうどだったので、6秒差で罰金2万円ということになる。悔しかったので、上で「迷って」「手間取って」「真面目に」などタイムが縮む余地のあった部分を強調したコメントを書いていた。ちなみにCを解いた後1分ちょっとVimのコードを検討している。結局縮まなかったしこれが一番無駄だった。

コードゴルフ。Aは当然dcの3Bが最短で、FAは取れなかったが最短は取れた。BはやはりAWK。Cは最初に書いたbashが最短だった。Dは後述。Gはnoshi基底を使うコードをRubyで縮めておいた。他は手付かず。

Dは嘘解法が通っていた。閉じ括弧の度に箱を空にするという、正直目を疑うようなもの。とはいえ通るならそれで縮めない道理はない。この嘘解法が通るということを念頭に置けば、答えがNoとなる条件が「文字列中に同じアルファベットが間に閉じ括弧を挟まず現れる」になるため、正規表現で一発で判定できる。sed。

朝までずっと日記を書いていた。今週は全然書けておらず今日だけで月曜日から金曜日まで一気に仕上げることになった。月曜日はICPCのための準備に充てたいので、今日明日の分もしっかり明日で終わらせるようにしたい。

午前7時半ごろあさかつに参加した。数分遅れたが何とか優勝。5問目はグラフが非連結というコーナーケースをしっかり踏んづけてしまった。

https://kenkoooo.com/atcoder/#/contest/show/8afdf612-a5c4-47a8-a170-04f08a508103

午前8時半くらいに布団に入り、1時間ほどなろうを読んで寝落ち。

12/25(日)

午後3時半頃に一瞬起きてなろうを読んだ。昨日の時点でほぼ最新話までたどり着いていたので、すぐ1作読了。

https://ncode.syosetu.com/n2861ht/

「現人神様の暗躍ライフ」。非常に面白かった。世界の裏で暗躍するチート主人公というだけでも好みなのに途中から配信者要素が出てきて、好きなものてんこ盛りという感じ。設定上演劇として暗躍しているだけあって、地下のバーから組織のアジトに繋がっていたり、いちいち壺にはまる描写が多かった。

午後6時半起床。食事してしばらく日記を書き、午後9時からAGC060。

AtCoder Grand Contest 060 - AtCoder

Aはド典型。長さ3以下の部分文字列だけチェックすればよいので、直前2文字を持つdpで解ける。この事実は知っていたが念のため証明も付けた。

Bは謎。曲がり角に1bitずつ置くことでそのマスを通ることを強制することが思いついたが、提出したいのをぐっとこらえ順位表を確認するとかなりペナが出ていたため、考え直す。例えば $2\times 3$ のマスをRDRと通るとき、曲がり角が二つあるので $K\ge 2$ が条件かと思いきや、 $K=1$ でもできるようだ。通るマスだけ、あるいは通らないマスだけに1を置くとよい。

通らないマスに置くのは拡張できそう。障害物を置くことで曲がる方向を制限するというイメージだ。1歩進んで曲がるのを2回繰り返すとき、曲がり角に置くと2bit必要なところ、障害物を置くと同じ値が使えて1bitで制限できると考えた。これを提出、しかしWA。

冷静になると、1歩進んで曲がるところが2連続している必要はなく、1か所あればその前後の曲がり角を障害物に置き換えられる。端の処理をしっかり考えて再提出し、何とかAC。

Cはかなり迷走した。ヒープで深さ $A$ の左端の要素と、深さ $B$ の右端の要素のどちらが大きいかを聞いている。隣の子とマージして1段上がるのを繰り返し、挿入dp的に自分が木の中で何番目に小さい要素かを考える方針が思い浮かぶが、木の要素が多すぎて現実的でない。また、1回マージしただけで確率の式が複雑な形になってしまった。この方針から抜け出すのに結構時間がかかった。

$UV$ パス上の頂点の大小関係を考えることにした。ヒープ条件から、根、つまり頂点 $1$ を中心とする大小関係があるが、さらに左右の子の間でも調べるため、頂点 $1$ から左右の値が小さいほうにどんどん伸ばしていく。これで大小関係を固定することができるので、それぞれ確率なり場合の数を求められれば解ける。

パスに乗らない頂点はいくつかの部分木に分かれて、それらの内部でどのように並んでいるかは確率計算に関係ない。ただし部分木の外とどのような順番にあるかは考える必要があって、これは根から伸ばしていく向きだと考慮できない。パスを縮めていく向きに考えることで対処できる。現在のパスの端点から先にある部分木二つと今新たに足す部分木の頂点たちを並べる方法なら求められるということ。

この段階で一度コードを書いてみた。パスの両端点の深さを持つ $O(N^2)$ 状態のdpだ。 $P_U\lt P_V$ を満たすものに制限して計算した値を、制限を外して計算した値で割ることで確率が出る。サンプル3までは $2^N$ オーダーの数のcombinationを求められるので、とりあえず答えが出せる。無事合っていた。

遷移をぐっと睨むと、dpの値が多項係数のようになっていることに気づいた。ただし微妙に違う。 $\binom{a+b}{b}\times\binom{(a+b+1)+c}{c}=\frac{(a+b+c+1)!}{a!b!c!(a+b+1)}$ のようになるので、補正のため $a+b+1$ で割っておく必要がある。逆にそれ以外の部分、つまり階乗が必要な値は $P_U\lt P_V$ の制限があってもなくても等しいため割り算するときに打ち消されるようだ。従って最初から無視してもよい。これもサンプル3まで通った。

dpの遷移がある数で割ることで行えるようになった。この数はだいたい2べきから1引いた数、あるいはその数二つの和で表される。998244353の倍数にならないことを祈ってサンプル4を試すと、何とか通ってくれた。遷移の度に逆元計算があるので5secちょっとかかっているが、TLがかなり長いので間に合うだろう。出したら通った。

Cに1時間半かけて残り1時間しかない。Dを読んで、とりあえず挿入dpで小さい値の答えを出してみた。挿入dpのテーブルの値などがOEISに載っていないか調べてみたところ、そもそも答えが載っていることに気づいた。しかししばらく調べてみたが当たり前のことしか書いておらず、高速な計算方法も見当たらなかった。そのままコンテスト終了。

A060350 - OEIS

3完79位でパフォーマンス2806、レートは2882→2875(-7)。赤パフォでレートが下がり厳しい気持ちになった。

Bの自分がとった方針は証明を付けられないので神に祈るしかなく、通せたのはラッキー。しかしペナを出した部分については最初の提出前に気づけても良かったので悔しさもある。

Cはまずdpを書いたのが良かった。dpを書いて高速化するというのは失敗することの多い方針だが、今回は遷移を整理することだけが必要だったのだ。正しいことを確認しながら一歩一歩進む上で、小さなサンプルが三つもあるのはかなりありがたかった。

Bだけコードゴルフした。整理すると、文字列中のDRあるいはRDを重ならないように取れる最大数が $K$ 以下であればよくなる。基本的に曲がり角の個数を数えていて、1歩進んですぐ曲がるケースだけ、具体的にはDRを取った後2文字目のRを次のRDに使えないため、個数が減る。入力回りで差がついたAWKが現在の最短。

TCB54が終了していた。今回はダメかと思っていたらそもそも全完が少なく、点数差で優勝できた。

日記を書かなければならないのに全くやる気が出ず、ラノベを2冊読了。

1冊目、「この教室は、武力に守られている」。微妙。裏社会で活躍する主人公ペアが学園に潜入して護衛任務をするというあらすじだが、学園の描写も護衛任務の描写もほぼ完全に独立していて、それぞれ中途半端な印象を受ける。授業中にテロリストが攻めてくるというよくある妄想が描かれるのを勝手に期待していた。ただし主人公ペアの正体がバレてしまうため、シリーズが続くことを考えると難しいのかもしれない。

2冊目、「異世界でチート能力を手にした俺は、現実世界をも無双する」12巻。面白かった。伏線などあってないような感じで毎巻新しいストーリーが展開され、しかも大体がその巻で一段落してしまうスピード感のため、内容がかなり濃く感じる。そんな中でシリーズ最初のほうの記述が少しずつ回収されているのが上手い。どこからかスクールアイドルの導入が生えてきたので、それが次巻描かれるかそれ以降か知らないが楽しみである。

しばらく日記を書いて午前7時過ぎに布団に入った。今日は土曜日の部分しか書けていない。明日に残すのは避けたかったが、生活リズム的にもこの時間に布団に入るのが最優先だった。1時間ちょっとネット小説を読んで就寝。