06/17(月)

午後3時過ぎ起床。半からインターン先定例会に出席した。

普段使っている進捗報告スライドを開いたら、フォントが変わっていて仰天。調べてみると、どうやら英数字で使われていたArialというフォントが日本語にも適用されてしまっているようだ。しかもなぜか使っているテーマのフォントを更新できない。どうしようもなかったのでそのままのスライドで報告した。Arialで表示した日本語はなんだかクネクネしていてへなちょこ。

ちなみに報告する内容はなかった。先週は勉強会準備に全力投球してしまった。業務をまともに進められていないのに勉強会だけ熱意マシマシで取り組むのはかなりの罪悪感がある。しかし準備が楽しすぎて止まらない。

さて、進捗報告が終わるといよいよ勉強会。今日のテーマは「ミラー・ラビン素数判定法」だった。質疑応答を含めて1時間強の発表。多くの聴衆から発表の構成やスライドの体裁についてお褒めの言葉をいただき、非常に嬉しかった。時間をかけた甲斐があるというもの。解散後にスライドを公開した。

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

勉強会をしました。今日のテーマは「ミラー・ラビン素数判定法」です。スライドを公開します。https://t.co/LsVCbeNQXj
— こたつがめ (@kotatsugame_t) 2024年6月17日

このテーマを設定した経緯について話すことにする。実は最初は「脱乱択」を扱おうと考えていた。COSS2023の三日目で講義を受け、また最近になって集中講義で触れたり熨斗袋さんが記事を書いていたりしたので、そのあたりをまとめるつもりだった。しかし調べ始めてすぐ、自分がこの分野に対しあまりにも無知ということを実感。何かの資料のコピペにしかならないと思いテーマを変えることにした。

noshi91.hatenablog.com

乱択アルゴリズムのWikipediaを眺めていたら「ミラー・ラビン素数判定法」という単語を見つけた。そういえばwitnessとして $\{2,7,61\}$ だけ調べれば実用上OKという事実がある。知識として知ってはいるものの、その背後にどういう理論があるのかは分からないから、これを調べてみることにした。

以上が動機である。結論から言うと、答えは「恐らく全探索」である。明言できるほどの記述は探した限り存在しなかった。良いwitness候補を見つける古い研究は理論と探索の組み合わせで取り組んでおり、詳細を把握するのが難しい。しかも肝心の $\{2,7,61\}$ は論文の末尾にサラッと書かれているだけで、どのような探索が行われたのかの詳細が不明。

新しい研究はもっと不明瞭で、基本的にはGPUを使って探索しましたとしか書かれていない気がする。昔構成された理論が役に立っているようにはあまり見えなかった。さらには論文化されているものも少なく、個人のウェブサイトで発表されてリンク切れになっていたりと、そもそも探しにくかった。

というわけでスライドの後ろのほうはしょうもない事実の羅列になってしまった。こんなことになるなら、ACLの実装コメントの論文にあるようなハッシュを使った方法にも触れればよかった。どうせ全探索しているだけだろうと放置しているうちに存在を忘れてしまったが、この論文は全探索する前の理論的な話も結構しっかり書いているようだ。

大学生協に行ってラノベ受け取りと夕食をこなし帰宅。日付が変わるまで先週の週記を書き、投稿した。先週末はずっと勉強会準備をしていたためほとんど週記を書けておらず、結局スカスカのまま公開することになった。その後うっかりハーメルンを開いて2作読了。

「まぁ我慢強い勇者ならどんな苦難も乗り越えてアイドルを推せるだろう」。原作準拠なのかもしれないが、ヒロインが妊娠する展開には慣れない。慣れないどころかはっきりと苦手なようだ。恰好良くて「我慢強い」オリ主が、自分もヒロインも高校生だということを忘れて孕ませるわけないだろうと思う。

syosetu.org

「VTuberって凄えよな、だってやりたいことなんでも出来るもん」。非常に面白かった。特に配信シーンが面白い。そのようなシーンは当然これまで読んできたVTuberモノにもあったが、基本はVTuberたちの為人を知り、キャラに愛着を持ったうえで面白さを感じていたように思う。ところがこの作品は配信それ自体が面白かった。現在の技術で再現できそうなギミックと小説ならではのテンポの良さがうまく組み合わさっている。

syosetu.org

日記を書いたりラノベを読んだりしていたら朝。先週行ったICPCチーム登録の完了通知メールが来たので、チームメンバーに転送した。ついでに連絡先のラベル付けを行ったので、今度からはもっと楽にできるだろう。また、ゴミを出した。

Amazonの定期おトク便で購入しているお茶の消費スピードが上がってきたので、頻度も3週間おきから2週間おきに上げることにした。しかし次の配送が07/01なので現在ある分では足りない。個別に購入することにした。ついでに切れかけのA4コピー用紙500枚も購入。およそ10か月前にも同じものを買っており、手計算メモとしての消費がほとんどでもそれだけのペースだったらしい。

午前10時就寝。

06/18(火)

午後5時半起床。ICPCの競技用ID・パスワードのメールが来ていたので、さっそく昨日用意したラベルを使ってチームメンバーに転送した。

セミナー準備を始めたが、サラッと書かれている同値性が示せない。論文の参照先にも単なる知識として書かれていて、さらにその参照先を調べると教科書の一部だったため辿れなかった。諦めて午後8時過ぎに外出。今日はヨドバシカメラとゲーセンに行く。地下鉄で仙台駅の一つ奥、宮城野通駅まで行き、まずその近辺のラーメン屋で腹ごしらえした。

ヨドバシカメラには書画カメラを探しに来た。これは主に本などの紙資料を映すカメラで、競プロ動画の手元撮影にも便利そう。ただタイピングしたり手計算したりするだけの高さが確保できるか気になるので、実物を見に来たのだ。しかし残念ながら取り扱いがなかった。秋葉原店にならありますと言われて乾いた笑いが出た。

仕方がないので退散。アンパンマンの石像を撮り、ゲーセンに移動。

仙台駅を庇い石にされてしまったアンパンマン pic.twitter.com/eNNSk31UV5
— こたつがめ (@kotatsugame_t) 2024年6月18日

まずサープラで6クレ遊び、閉店後に歩いてタイステのクリスロード店に移動しさらに5クレ遊んだ。今日はツユ曲の称号を集め、アプデで消えるマップを完走した。おそらくアプデ前最後のプレイとなるだろう。

アプデで消える称号のうち「うっせぇわ」のスピソニAJが条件になっているものは未取得である。1クレだけ挑戦してみたが全然ダメだった。譜面を覚えていないため手をジタバタさせることしかできず、まるでろくな準備をしていないセミナー発表直前のような気分になって、気持ち悪い冷や汗が出た。この場違い感のようなものをねじ伏せて詰めるだけのモチベーションはなく、ついでに詰め切る時間的余裕もなかった。

立ち食いそばを食べ、ドンキに寄って午前1時帰宅。シャワーを浴びた後はラノベを読んでいた。

「彼とカノジョの事業戦略」を読了。登場人物が軒並み経営者で、天才コンサルとして知られる主人公が活躍する話。またこの設定を二十歳になるかならないか程度のキャラ達で展開している。読み始めは年齢を反映した経営者らしからぬ口調に眉をひそめたものの、そもそも経営者という設定が好みなので楽しく読み進められた。主人公によるTOBがクライマックスかと思ったらもう一捻りあり、冒頭のシーンも反映した決着になったのは良かったと思う。

ところで作中の試験における評価がすでにインフレ気味で気になった。金額で表されるのだが、予選通過のボーダーラインが100億円だったところ、主人公はスタート時にすでに1000億円の評価を得ており、終盤まで目立った動きをせず少し追い抜かれたところで全く問題なかったようだ。しかもこれで7位だという。ちなみにボーダーラインは20位で、突破者の間でも差は激しい。

あとがきでシリーズの公式Twitterがあると知り確認してみたところ、作者の意向で2巻まででシリーズの刊行が中止されたことを知ってしまった。余計なことを知ってしまい出鼻をくじかれた気持ちになりつつ、そのまま「彼とカノジョの事業戦略」2巻も読了。冒頭で予選1位通過者の評価が1兆円だと明かされた。

1巻では主人公が本領を発揮し、順当に活躍するという展開だった。一方2巻では手ひどい失敗が描かれる。1巻で大事にしていた「win-winの関係」という題目に足元をすくわれた形で、ピンチを脱する救いの手もまた1巻から大事にされていた「自分の思い描く世界」というキーワード。失敗の傷はそこそこ大きいが、今後また頑張っていこう……というところで終わる。

作者があとがきでさんざん言っていたように、確かにこの2巻まででシリーズのプロローグとなっていた。ただし先が出ないことを知っている身としては、2巻の主人公がいいところなしで悲しいだけ。好きな設定だったし今後のストーリー展開もかなり準備されている様子が伺えただけに残念。

しばらく日記を書いていた。日が高くなるにつれ暑さが耐え難くなってきたので、今夏初めてエアコンをつけた。午前11時就寝。

06/19(水)

午後8時起床。セミナー準備を諦め、先々週と同じ資料を添付して参加者にメールを出した。1日で話しきれるとは思えない量がすでに用意してあるため、とりあえず明日は大丈夫。

せっかくなので論文の続きを読み進めるのではなく数値計算をしてみることにした。SageMathの豊富なライブラリを使うと結構簡単に実装できる。調べて出てきた信州大学のチートシートを片手に書き進め、計算を回しながらラノベを読んでいた。

「恋愛魔法学院」を読了。主人公がかなり好み。ストイックさ、隔絶した強さ、見た目の良さ、モブキャラへの無関心さなどどれを取ってもお気に入りだった。そういう主人公だから貴族の集まる学院でも、また冒険者稼業においても周囲に煩わされることなく行動できていて、非常に気持ちよく読み進めることができた。主人公の前世は大学の研究員でAIが専門だったらしいが、そこまで決まっているということは後々効いてくるのだろうか。

シャワーを浴びて午前9時就寝。

06/20(木)

午後0時半起床。寝る前の計算は終わっていなかったが、現在の出力を集めてセミナーに持っていくことにした。原付で登校し、少し時間に余裕があったので学食で昼食を摂った。

午後1時半からセミナー開始。冒頭で現在行っている数値計算について話し、出力を少し説明した。予想と異なる結果が出ており興味深い……と言うつもりだったが、自分のコードがバグっているかもしれないと思い始めた。次回までには小さいケースで手計算しチェックしておきたい。あとは普通に発表。端折れるほど論理の構造を覚えているわけではなかったので全部説明してしまい、あまり進まなかった。このペースなら今用意してある分だけであと2回はセミナーできてしまう。

その後先生の発表。スライド発表の練習だったのであまり時間はかからなかった。最後に論文の手直し。自分が引用した論文の1本がつい最近アップデートされ、そこで自分の論文を引用してもらえたことを知った。非常にうれしい。

修論でも引用した論文の著者が4月に新しく論文を出しており、やっていることが自分の修論と非常に似ているらしい。
週記（2024/04/29-2024/05/05） - kotatsugameの日記

ただ残念なことに、名前がTakahashiではなくTakashiになっていた。Yandex Cupでも間違えられたので、もしかしたらロシア語圏の人にとってTakahashiは耳慣れない名前なのかもしれない。自分も論文を書いているときに人の名前を間違えて、先生に指摘されたことがあるし、まあ難しいよなあ。

タカシくん pic.twitter.com/LCit4Zj89e
— こたつがめ (@kotatsugame_t) 2023年12月2日

午後6時過ぎ解散。後輩と学食に行き、食後もずっと路上で立ち話していて、午後9時を回ってから帰宅した。帰ってからはPCを触ったりスマホを触ったりしてグダグダ過ごしていたが、日付が変わってからはラノベを読み始めた。2冊読了。

「社畜剣聖、配信者になる」。思ったよりギャグ色強めで楽しく読めた。コメント欄がちょっと荒れてもすぐギャグに押し流されるので、焦げ臭くならない。また社畜剣聖を縮めた愛称「シャチケン」がなんとも軽くて良かった。どんなピンチでもそうと思えないような気軽さで解決するため、個々のイベントがスピーディーに回収され、1巻だけでも内容が盛りだくさん。2巻が6月の頭に出ていたらしいが予約していなかった。

「生放送！TSエルフ姫ちゃんねる」。地の文があまりなく、配信シーンはほぼ主人公のセリフとコメントの掛け合いのみで進行する。そのコメントもリアルさを追求してかほぼ同じ内容のものが並んでおり、内容としては薄い。掲示板シーンのすべてのレスに番号・名前・日時が付されており、それだけでページの大半が埋まっていることもその思いを強くした。読みやすくはある。

日記を書いて正午前に寝た。

06/21(金)

午後8時半起床。しばらくハーメルンを読み、yukicoderの直前になって布団から出た。午後9時20分から開始。今日はyukicoder 434。

yukicoder contest 434 - yukicoder

Aは提出期限が $31-A+B$ 日後。今日を含めて何日あるか数えてしまい1WA。Bは全探索。Cはdp。Dは左上マスにカメラを設置する必要があり、それが右を向いているか下を向いているかでヤング図形が端から切り落とされていく。これを続けると最終的には、左上マスからスタートして右または下に移動することを繰り返し、ヤング図形を出るまでの経路を数え上げる問題になる。

Eは $N=2,3$ を手計算。 $N=2$ に対しては $K^{A_1+2A_2}\left(\frac{K-1}K\right)^2\left(\frac{K+1}K\right)$ で、 $N=3$ に対しては $K^{A_1+2A_2+3A_3}\left(\frac{K-1}K\right)^3\left(\frac{(K+1)(K^2+K+1)}{K^3}\right)$ らしい。ここから一般項を $K^{A_1+2A_2+\dots+NA_N}\left(\frac{K-1}K\right)^N\prod_{i=0}^{N-1}\left(1+K^{-1}+\dots+K^{-i}\right)$ とエスパー。 $N=4$ で愚直と比較すると一致したため提出、AC。

Fは何もわからず5完、スコア差で1位となった。

ラノベ「君の先生でもヒロインになれますか？」2巻を読了。前半の義妹のふるまいがとにかく気に入らなくて、信じられないくらいイライラしながら読んでいた。主人公の都合を考えず四六時中メッセージを送ったり通話をねだったりする点が特に嫌だった。後半の展開を見るに、義妹にわざとヘイトを集めていたのではとも思う。しかしそれにしてもこの苛立ちは過剰。こちらが読む前から不機嫌だったとかそういうことはないはずだが……。

午前8時就寝。

06/22(土)

午後1時前起床。NPCAPC 2024に参加した。Universal Cupに収録されるとのことだが、Nyaanさんがテスターのため二人チームになった。こういう状況でちゃんと成績を反映してもらえるかはわからない。質問しても見落とされたのか今のところ返答がない。

NPCAPC 2024 - AtCoder

書く

食事した後、ハーメルンから「転生御曹司が恋愛マンガみたいな世界で恋と性欲と友情についてマジメに考えてみる青春ラブコメ」を読了した。といっても4話しかない。やはりこういう設定は好みだなあと再認識した。

syosetu.org

シャワーを浴びて午後9時からABC359。

UNIQUE VISION Programming Contest 2024 Summer (AtCoder Beginner Contest 359) - AtCoder

Aはgrep -cを使いかけたが、見つからなかった場合REすることを思い出してC++で実装。任意の文字列が与えられると思いわざわざ完全一致で判定した。Bは $A_i=A_{i+2}$ を数えると楽。Cは $y$ 座標を合わせ、足りない横移動を補う。位置を各タイルの左下に揃えて計算した。Dは後ろ $K$ 文字を持つbitDP。

Eは各prefixに対し後ろからの累積MAXの和が求まればよく、stackでできる。Fは有名問題で、 $d$ を貪欲にインクリメントしてよい。Gは $A$ が同じ頂点だけで圧縮木を作ってから考えようとしたが、書き慣れず手が止まった。いったん冷静になり木を圧縮した後にどうやって解くか考えたところ、木dpが思いついて、しかもマージテクを使えばすべての $A$ で同時に計算できることが分かった。

30分弱でノーペナ全完、4位。AとBをNibblesで解いておいた。

www.youtube.com

ラノベ「商人令嬢はお金の力で無双する」を読了。実家の領地が経営破綻しかけており、前世知識で立て直しに奔走する巻だった。タイトル通りのことができるのは次巻以降になるだろう。また女性の社会進出を阻む制度がかなり強調されていた。年齢を理由に軽んじられる話はたくさんあるが、性別はどうしようもなくて苦しい。侯爵という心強い味方が付いたのは不幸中の幸いといったところ。

午前2時ごろ寝落ち。

06/23(日)

午前6時半くらいに目を覚ましてラノベを読んでいた。午後1時過ぎに再度寝て、午後5時半くらいに起きた。今日はJAG模擬国内予選の内部コンテストがあったが、夜のコンテストに備えてサボってしまった。

午後6時からUniversal Cup Semifinals。

https://qoj.ac/contest/1708

順位表ではまずA、K、Cが解かれた。Aは全員で話し合ったのに、見事に $1,\dots,1,d,d,d$ のケースを見落として1WA。こんなシンプルな問題が既出でないわけはないし、実際自分は結論にも見覚えがある気がするのだが、チームメイトは知らないと言っていたのでただのデジャヴュらしい。次のCはrisujirohさんがサクッと通していた。

自分はKを担当。 $k=1$ で考えれば十分なことに気づくと、あとはbinary trieでぶん殴れる。感想戦で、差が1の2数のXORが決まった形にしかならないことを指摘されたが、結局計算量的には変わらないだろう。binary trieのノードも自動的に少なくなるので、定数倍による区別は不可能のはず。

このあたりで一瞬順位表情報がなくなったが、すぐGが解かれた。読むと前から二分探索したくなる。それまでの文字列が分かっていれば部分文字列の種類数も計算できて、これで判定が可能になる。手元で念入りにチェックして提出、AC。

ここから、順位表的にはJ、L、Mが解かれている状態でしばらくACのない時間が続いた。次に解けたのはM。数字が縦に二つ並ぶとその左または右がほぼ確定するという事実を発見し、もう少し一般化して、1（または2）が左2マスにあるブロックと右2マスにあるブロックがそれぞれprefixとsuffixになることに気づいた。

それらの境界を固定すれば、埋め方は貪欲でよい。また境界でちゃんと分けられていれば、ブロックごとにどんな埋め方をしてもブロックをまたいだ矛盾は発生しないため、数字が縦に二つ並ぶブロックができるだけ少なくなるよう境界を端に寄せることが正当化される。つまり境界として可能な位置を探したらその端だけ試せばよい。1の境界を左に、2の境界を右に寄せる方法と、その逆の2通りしかないので後は愚直に計算。

全部?の状態から5マス埋めて作ったランダムケースを使いチェックしたところ、落ちるケースが見つかってしまった。なぜ落ちるのか解を見てもよくわからなかったのでしばらくガチャガチャやっていたが、単なる実装ミス。答えの比較がバグっていた。直して提出したら無事AC。

NyaanさんがJの2乗解にたどり着いたらしい。任せて他の問題を見に行く。順位表で解かれているのはBとLのみだが、risujirohさんがHに取り組んでいて、見た目的にもとっつきやすそうだったので自分も参加した。結果的にはこれが大正解のムーブとなった。

普通にdpしようとすると両端の座標とインデックスで4乗の状態が必要になるから、何とかして左右に分離したい。これは操作の大胆な言い換えによって達成できた。選んだ人に向けて引き寄せるという操作を、左右にある幅1の区間を高々一つずつ消すものと読み替える。当然区間は直近のものが選ばれるが、遠く離れた区間からも選べることにした。

もともと $[a_1,a_1+1),[a_1+1,a_1+2),\dots,[a_n-1,a_n)$ という区間があって、位置 $p$ にいる人を選ぶと「左の区間」 $[l,l+1)$ 、「右の区間」 $[r,r+1)$ （ただし $l+1\le p\le r$ ）を選んで消せるものと思う。ただし残っていなければ当然選べない。どんな選び方でも可能かは知らないが、何となくそれっぽさを感じて突き進んだ。

今は人に対して区間を選んだ。これを逆に見て、各区間について「左の区間として選ばれた」「右の区間として選ばれた」「選ばれなかった」の3種類に分ける。すると適当に選び方を組み替えることで、「左の～」がprefix、「右の～」がsuffixになるようにできる。また列 $a$ のvalueは選ばれなかった区間の個数だが、これを最小化したとき割り当てが一意に定まることを信じた。ここも未証明。

ただしこれを信じると、いよいよ左右を分離できる。答えを求めるには選ばれなかった区間 $[m,m+1)$ を $0\le m\le 800-1$ から一つ固定し、それが実際に選ばれないような $a$ を数え上げて足し合わせればよい。位置 $m+1/2$ より左に並んだ人は必ず「右の区間」を選べるので、考えるべきなのは「左の区間」を選べなかった $m$ より左に並んだ人。よって左からdpできる。右も同様。

例えば左に対しては「 $m$ 」「 $m$ より左に何人並んでいるか」「いくつ区間が余っているか」を持ってdpする。 $W:=800$ として $O(nW^2)$ であり、左右のマージも同じ計算量で行える。書いたら即座にサンプルが合ったので、半信半疑ながら提出してみることにした。dp配列を3次元ぶん確保してしまったためMLEを出してしまったが、二つ用意してswapすることで容易に改善でき、なんとAC。オンラインのほうではFAだった。

残り時間はLの最小費用流を考えていた。それっぽい解法を提案するもWAで終了。直後にCFがあることだけ覚えていたが、確認するとdiv.3だったためこれもサボって感想戦をしていた。Cは概要を聞くと想像がついたものの、細かいところを合わせるのは微妙に面倒そう。

Jは値の小さいほうから見て区間に覆われている具合を観察すると、まったく覆われていないインデックスが二つ以上出現した瞬間に破綻するため、高々一つ持って計算できるらしい。すると算数で $O(n^2)$ 状態のdpが書けて、実家dpにできるとのこと。各値についてそれがMAXとなる極大区間を見ることになるが、 $p$ がランダムなので十分高速。ただ2べきの計算が多く、そこでTLEして辛そうだった。

解散後はオンサイトの配信を見ながらラノベを読んでいた。

www.youtube.com

「黄金の経験値」4巻を読了。普通に面白い。あくまで普通で、書籍版で再読したことによる面白さの再発見は起こらなかった。錬金術による配合が主題だと思うが、これまでゲームの仕様を丁寧に調べてきたのと比べると、どうしても行き当たりばったりに見える。ただ、では配合テーブルを真面目に検証してくれれば面白かったかというと、それもまた違うだろう。難しい。天使のビジュアルがあまりにも醜悪でビビった。

オンサイトの配信では参加者へインタビューしながら同じセットを走ったときの録画を流していたので、5h経ったらYes/Noのような結果発表があるものと考えていた。しかし何事もなく、凍結も解除されずに終了。結果が気になって仕方がないので残念だった。

ちなみにオンサイトではUSA1が我々より早くHを通していたらしい。しかし結局その1ACだけだった。オンライン側で見つかっていなかっただけの可能枠だったら困るな、と思っていたので安心。またオンサイトの順位表を見ると、DとEにもACが出ていたようだ。Hを避けてそちらに行っていたらどうなっただろうか……と言いつつ、基本的には順位表情報に従うのが正解のはず。

まだ凍結は解除されていないが、オンサイトとマージされた順位表をじっくり眺めて計算した結果、最も悲観的なシチュエーションつまり凍結後に提出された問題がすべて通っていたという仮定の下でも、我々のチームはFinals未進出勢のうち8位に滑り込んでいる。決勝進出！！！

シャワーを浴び、日記を書いて午前8時半くらいに寝た。