02/07(月)

先週の週記を投稿してからの話。しばらくハーメルンを読み続けて、午後4時前に購買に行った。しかし先週金曜日から春休み期間だったようで、購買が午後3時で閉店してしまっていた。コンビニで菓子パンやおにぎりを大量に購入して帰宅。スライドを作ってインターン先定例会に臨んだ。日曜日は午後11時とかいうアホみたいな時間に起きたため、何とか徹夜に成功した。

先週の進捗は、火曜日に頑張ったもの一つのみ。僕の最近の稼働状況から見たらかなり進んでいると思ってしまいがちだが、社会人は最低限としてあの日と同じだけの時間毎日働いていると考えると震えが止まらなくなる。まあ話すことはあるし見せるものもあるので、ある程度自信を持って発表できた。

また、ふとしたことからAlphaCodeの話が盛り上がって、僕も先週の週記の最後に書いたように「slow positives」のことが気になっていたので議論の俎上に載せたりしていた。preprintをちょっと読んだ感じではまだかなりTLE解が出ているようで、しかし算出されたCFのレートへの影響はよくわからない。こうなると、数学的な問題が比較的得意というのも実際は愚直解が生成できているだけではないのか、と邪推してしまう。何度も言うように、そもそも問題文から動くコードが作られているというだけで驚くべきことである。

かなり話が長引いたので今週の勉強会はなくなった。終わってからまたしばらくハーメルンを読んで、午後9時半就寝。

02/08(火)

午前3時半ごろ起床。今日はこのまま午後9時半に寝落ちするまでずっと布団でハーメルンを読んでいたらしい。Chromeの閲覧履歴を見るに、午前9時から午前11時のあたりも眠っていたようだ。今読んでいるハーメルンは1話あたりが長く、注意深く履歴の間隔を確認しないと寝ているのか普通に読んでいるのかわかりにくい。

02/09(水)

午前5時起床。

今日締め切りのレポート、それもテストも課題もないレポート一発の講義のものが残っているのに、昨日まる一日をハーメルンに捧げてしまった。今日もずるずると午前10時まで読み続けて、1作読了。「正体不明の妖怪(になった男)、情緒不安定な百獣の腹心になる」。

syosetu.org

過去の話もワノ国の話も原作がどうなっていたのかわからないし、主人公も完全に悪役側だしキャラが謎だけれど、文句なしに面白かった。というのも主人公が最強だからだ。この一点だけでやはり安心感が違う。またワンピースはキャラクターの実力が懸賞金という明確な形で表現されるので、これがインフレしていく様子も見ていて興奮する。ネットでちょっと感想を見て知ったことには、主人公の介入によって原作と比べ百獣海賊団の隙がなくなっているらしい。そういうこともしっかりわかるとより楽しめたのだろうなと思う。文字を大きくする特殊タグを多用しているのが気になっていたが、読んでいくうちに理解した。原作の漫画っぽい表現に近づけようとしていたらしい。特に幹部級が勢ぞろいするときなど、キャラクターの発言の直後に肩書＋二つ名（＋懸賞金）を大書されているのはかなり印象深い形式だったのですぐ思い出せた。

昨日の昼前くらいにTシャツが届いていたのを放置していた。開けると予想通りCGRの商品だった。このうちCGR15のものは、胸のワンポイントが刺繍で施されており、裏地の薄くて白い布（接着芯）も含めなんとも洗濯しにくそうな感じがしている。本来ならネットに入れるべきだろうところ、生憎持っていないのでとりあえず単独で洗濯機を回してみた。案の定糸の塊が出てきて厳しい。着ないようにしたい。

Tシャツ届いてた pic.twitter.com/7PjwUMHBTJ
— こたつがめ (@kotatsugame_t) 2022年2月9日

レポートから逃げたいあまり別のハーメルンを読み始めた。午後1時半に閉店間際の学食に滑りこんだりしつつ、ずっと読み続けていた。夕方当たりにレポート提出をほぼ諦め、午後8時半に寝落ちした。

02/10(木)

午前1時半起床。意識を取り戻したらレポート提出期限が過ぎていて、罪深い解放感を覚えた。そのままハーメルンを読み続ける。午後1時からのゼミ前に一旦寝たいと思っていたので、午前6時半に寝た。

午前9時半起床。今日のゼミは最終回ということで、ちょっとだけ話したいことがある。そのために発表資料を作る必要があってこの時間に目覚ましをかけておいた、とはいえ眠気も強く、ダラダラハーメルンを読んでいたら午前11時くらいになってしまった。シャワーを浴びてパワポでスライドを作り、午後0時半くらいに完成。ちょっと空いた時間に学食に行こうと思っていたが、雪が降っていて原付が使えないため間に合わないと判断し、スライドを手直ししつつゼミの開始を待つことになった。

午後1時からゼミ。僕の話したい内容というのは、以前発表したときに出てきたルジャンドル記号の値を計算するアルゴリズム2種類の性能比較である。演算をどれも1ステップと考えれば、どちらも素数 $p$ に対して $\left(\frac n p\right)$ を $O(\log p)$ で計算できる。しかし一方は定数倍こそ軽いものの $\bmod p$ で計算する必要があって、他方は $\bmod 2$ でよい。この条件なら、 $p$ が小さいところでは前者が、大きいところでは後者が高速だと考えた。実際にプログラムを書いて、その様子を確認した。結果は以下にリンクを貼ったスライドに載っているが、概ね想定通りの挙動をしている。また $p$ が大きくなるにしたがって演算の計算量が顕在化していく様子も見える。実験に使ったコードも掲出しておこう。

ルジャンドル記号の高速な計算方法.pdf - Google ドライブ

test.py - Google ドライブ

このような形で余談を発表する人も多く、最終回らしい名残を惜しむようなゼミになった。最後に先生に促されて全員がカメラをオンにしたりして、なるほど1年間の終わりなのだと実感を得た。

ゼミが終わってからもまたハーメルンを読み続けて、午後6時半に1作読了。「ヒエヒエの実を食べた少女の話」。

syosetu.org

これも非常に面白かった。相変わらず主人公最強で最高。こちらの主人公はどちらかというと善で、残酷な描写に苦しめられることもなかった。しかし直前に読んだ作品もこの作品も、主人公はロジャーが生きていた時代から海賊として活動している。その経歴があってこそ主人公が最強の状態で原作の時間軸に突入できるのだが、過去編も新世界の話もよく分からないのはやはり寂しい気持ちがある。また原作の流れに合わせるためにどうしても発生せざるを得ない事件も多く、止められたはずなのにと苦しくなったりしがち。

そういえば今日の朝方にHHKBが届いていた。ABC235の商品である。早速開封して、サブのUbuntu機に使っていなかったBluetoothドングルを差して接続してみた。

人間工学的に肩が開いて良い pic.twitter.com/bENLp2jTvC
— こたつがめ (@kotatsugame_t) 2022年2月10日

ただ設定にかなり手間取った。メイン機では左Ctrlを英数キーに、左FnをCtrlに置き換えて使用しているので、それに合わせたい。英数キーを押したとき、一般に半角/全角キーを押したように入力を切り替えられるようにしたいが、そのままでは半角英数に切り替わってしまった。Mozcのプロパティから半角/全角キーと一致するように英数キーの挙動を変える。どういう原理かはわからないものの、とりあえずIMEの有効化・無効化を割り当てればよいらしい。それをして完了かと思いきや、なぜか毎回CapsLockが発動してしまう。ここでCapsLockキーを無効にするとダメで、英数キーも無効化されてしまった。調べたところ以下のブログ記事が見つかった。英数キーになぜかCapsLockキーが同時に割り当てられているようで、設定ファイルを弄るとようやく意図したとおりの動作になった。

mac/linux/windowsに全対応した日本語入力切り替えキー - yhara.jp

日付が変わるくらいまで日記を書いて、それからハーメルンを読み始め、午前3時半就寝。

「論理華金」というツイートを見て、明日が祝日であることに気づいた。生協に予約していたラノベが届いているのに今日受け取り損ねたので、来週を待たねばならないようだ。残念。

02/11(金)

午後0時半起床。横たわったまましばらくハーメルンを読んでいた。

今週末は生協の弁当配達が休み。手軽に食べられるものが欲しいと思ったので、コンビニに行ってパン類を大量に買ってくることにした。普段は菓子パンをたくさん買うところ、今日は値段を気にして食パンも買うことにした。そのまま食べるのはさすがにうれしくないので、練乳も買った。これさえあれば今後食パンを買ってくるだけで甘い食べ物を生成できるということになる。

帰宅してインターンのコーディングを始める。今日は1on1が予定されているので、それに向けて何かしら進捗を産んでおきたい。今週はレポート締め切りがあったりゼミがあったりであまり動けないかもしれません、ということを言ってはいたが、結局ハーメルンに吸い込まれてレポートを消し飛ばしてしまったため、何の言い訳にもならなくなった。まあハーメルンを読んでいなかったらレポートをしていたはずなので、どちらにしても今週は動けなかったということにならないだろうか。論理的に考えればそうなるものの、ハーメルンのせいで稼働できなくなるという事実についてはかなり申し訳なさがある。

調べものばかりであまり進まないうちに1on1に突入。自分でもよく整理できていないことをいろいろ言って微妙な感じにしてしまった。作業中に1on1が始まっただけであって別にどこかで詰まっているわけではないのに、何とか見栄を張ろうとして「〇〇が難しいです」とか言ってしまう。少し調べたら解決することなのに。そうこうしているうちにかなりコミュニケーション不全という感じになって、そもそも自分が考えている設計を共有できていないようだったので、メンターさんが僕があれこれ言うのを書き留めた設計スライドを作ってくださった。

来週火曜日に次の1on1を設定して終了。今日の1on1はメンターさんが祝日でもOKですと言っておられたので入れてもらったのだった。社交辞令はわからないので、OKと言ったらOKだろうという精神。

その後ハーメルンを読むのを再開して、1作読了。「海賊らしからぬ海賊」。あまり好きではなかった。原作で最強格のキャラがホイホイ主人公の言うことを聞くのがあまり受け入れられなかった。ドンと構えていてほしいという気持ちがある。主人公はめちゃくちゃ強いし懸賞金も高いので、文句なしの主人公最強モノではある。ただそれだけで面白く感じられるというわけではないらしい。

syosetu.org

しばらくコードゴルフをしてから、TUPC2021のテスター作業を始めた。何時間か経って、しばらく考え込んでいたらうっかり椅子の上で意識を飛ばしてしまったので、急いでベッドに移動して就寝。午前2時だった。

02/12(土)

午前9時半起床。

2021年のCGRの結果が出ていた。自分は25位で、パーカーには惜しくも届かず。6回中4回ポイントがついているのはかなり良かった。ただそうやって定期的にそれなりの順位を取るよりは、1回でも高い順位を取ったほうが合計ポイントが高くなる。なかなか難しい。

Codeforces Global Rounds 2021: Final Results (GR13-GR18) - Codeforces

昨日の続きで夜までずっとテスター作業を行っていた。その合間の出来事が2つある。まず、正午にAHC008が始まった。

MC Digital Programming Contest 2022（AtCoder Heuristic Contest 008） - AtCoder

夕方、藤井聡太五冠が誕生したことを記念して「りゅうおうのおしごと！」が5巻まで半額になっていた。さすがに無料公開ではないらしい。5巻はシリーズの山場で最高に良い。

藤井聡太五冠が誕生したので約束どおり『りゅうおうのおしごと！』も５巻まで半額にしておいたぞ（破産）

amazon https://t.co/U738a6gGN1

BOOK☆WALKER https://t.co/22gKR47OYj pic.twitter.com/eJOK9VPzcZ
— 白鳥士郎 (@nankagun) 2022年2月12日

最近、藤井聡太竜王の四冠記念で4巻まで期間限定で無料公開されていました。もし五冠を達成したら5巻まで無料公開されるのでしょうか。そこまででもぜひ読んでほしいシリーズです。
今年読んだ本のまとめ - kotatsugameの日記

テスター作業が一段落してから、AlphaCodeのpreprintを読み始めた。これを要約して、来週月曜日のインターン先勉強会で発表する予定。しかしかなり難しい。機械学習のことをほとんど何も知らないので、モデルや評価の細かい話が全然分からない。とりあえず大本になっているtransformerというのは検索して調べておいた。

Competitive programming with AlphaCode | DeepMind

午後9時からABC239……のはずが、10分ほど前にAtCoderのサイトに繋がらなくなった。DBへの負荷が原因らしい。まず1時間延期されて、CGRと被るが大丈夫かと心配していたら中止になった。来週また行われるようだ。そうして空いた時間でpreprintを読み進めて、午後11時半からCGR19に出た。

Dashboard - Codeforces Global Round 19 - Codeforces

Aは、数列がソートされていなかったら、ソートした数列と異なる要素のうち先頭のものの直後で分割すればよい。よってソート済みかどうかをチェックする。Bは区間を伸ばすより1個ずつに区切ったほうが得なので、各部分列に対するvalueが部分列の長さと含まれる0の個数を足したものとなる。これをすべての部分列に対して求める。 $O(n^3)$ が通る制約なので愚直に求めたが、結局0が何回カウントされるかさえわかればよいので $O(n)$ でも解けるはず。Cは、奇数の山にはどこかから1持ってくる必要がある。持ってこれる条件を整理すると、真ん中が全部1か $N=3$ かつ真ん中が奇数なら-1で、それ以外は $\sum_{i=2}^{N-1}\lceil a_i/2\rceil$ となることがわかる。オーバーフローで1WA。Dは式を整理すると答えが $(n-2)\left(\sum a_i^2+\sum b_i^2\right)+\left(\sum a_i\right)^2+\left(\sum b_i\right)^2$ になって、右2項の最小値を求めるには部分和dpをすればよい。

Eは $cnt$ の種類数が $O(\sqrt n)$ になるので、組み合わせを全探索しても $O(n)$ になる。 $cnt_x$ と $cnt_y$ を固定すると、後は $x+y$ を最大化すればよい。 $x$ の降順に見て $y$ の降順に調べる。badでないペア $(x,y)$ が見つかったら $x$ を次のものに進めることと、最大の $y$ にペアができたら $x$ の探索を終了することを行えば、全体の探索回数が $O(m)$ で抑えられるので間に合う。badなペア $(x,y)$ の管理はTLEが怖かったのでvectorで行った。 $cnt_x$ に対して $(cnt_y,-x,-y)$ を昇順に持っておくと、昇順に $cnt_y$ を固定するとすれば探索中の要素がこの順で出現するので、先頭から比較していくことでbadなペアを検出できる。Fは、まず塔を建てるのは葉だけでよいとわかる。 $\max h_i$ がefficiencyとなるような塔が2本あって、それ以外の頂点はその塔のうち1本と別の塔によってカバーされることになる。そのような塔のefficiencyは、 ${\rm argmax}\;h_i$ を根とし、部分木にある塔のefficiencyの最大を持つような木dpをすれば求まる。最後に $\max h_i$ がefficiencyとなる塔を2本用意して終了。

Gは、実験すると2べきに揃えるのだろうと予想がつく。 $N\ge 3$ なら必ず可能。 $N$ 以上で最小の2べきの数を $2^b$ としたとき、 $2^b$ が $N-1$ 個と $0$ が $1$ 個作れる。 $0$ を使うと2手で値を2倍できるため、つじつまを合わせつつ再帰的に解く。まず $N=2^b$ の場合は $N\leftarrow N-1$ に対して解けばよい。そうでないとき、 $r=N-2^{b-1}$ とすると、 $2^{b-1}+1,\dots,N$ と $2^{b-1}-1,\dots,2^{b-1}-r$ を一対一対応させることで $2^b$ と $2,4\dots,2r=(1,2,\dots,r)\times 2$ が得られる。さらに $s=2^b-N-1$ として $1,2,\dots,s$ も余る。 $r\ge 3$ または $s\ge 3$ ならば $0$ を作ってこれて、もし $1$ や $2$ が余ってもそれも2べきなので、 $0$ を使って値を倍々にしていけば求める2べきの値に揃えられる。そうでない場合は $N\le 6$ なので、手で回答を作って埋め込む。少し前のCodeChefの問題を思い出すような方法だった。

NN以下で最大の2べきを2b2bとすると、2b…N2b…Nと2b−(N−2b+1)…2b−12b−(N−2b+1)…2b−1（の逆順）を対応させることでbitwise ANDが0であるようなペアばかりを作ることができ、その上残りもまた1…N′1…N′の形をしている。
週記（2022/01/24-2022/01/30） - kotatsugameの日記

7完21位、レートは2735→2849(+114)。前回の-156が大きすぎる。

布団に入って寝る前にハーメルンの更新をチェックしていたら、耐え切れず寝落ちした。午前5時だった。

02/13(日)

午後0時半起床。ハーメルンを読んだりYouTubeを見たりした後、布団から出た。

結構前に「今日ヤバイ奴に会った」というチャンネルの動画をいくつか見ていたことがある。インドの屋台飯を扱うYouTubeチャンネル。コロナウイルス感染症拡大の影響で撮影ができなくなったという説明動画を最後にしばらく見ておらず、今日久しぶりにおすすめ動画に登場した。今はもう結構普通に撮影していて驚き。ただチャンネルの投稿動画を見てみるとコロナ禍の中でもちょくちょく新しい屋台が出ているようなので、ただ自分の興味が離れていただけかもしれない。

www.youtube.com

昨日の続きでAlphaCodeのpreprintを読む。昨日は4章の途中で止まっていた。この4章前半が学習についての細かい話で、予備知識のなさに絶望したものだったが、それ以降は正答率の評価や改善が話のメインになってかなり読みやすくなった。集中を切らしつつもどんどん進んでいって、夕方、6章まで一通り読み終えた。7章から9章は読み物なので飛ばしてよさそうで、10章の付録は時間がなく読まないことにしたため、これでとりあえず発表スライドを作る準備が整ったと言えるのではないだろうか。

ラノベの新刊チェックと予約をした。とりあえず03/01発売までの19冊。3月に入ってからは大学生協の営業時間がどのようになるのかわからないし、自分の帰省がいつになるかも決まっていないので、確実に受け取れそうな発売日のラノベだけ予約したということ。参考までに昨年3月の営業時間を調べようと思ったら、生協の営業時間告知ページはファイルが上書きされているようで見られなかった。Googleに残っていたキャッシュによれば、普通に営業していそうではあるが。

午後7時から負荷チェックコンテストに出た。

負荷チェックコンテスト - AtCoder

とりあえずseq 20で最短を取る。あとは1要素ずつ三分探索でもすればいいかなと思って適当にポイポイ投げていた。3要素目くらいで、最小・最大の2数に対する結果が分かれば復元できることに気づいたので、残りはそれで埋めた。計算が面倒だったので、各要素が決まったらその状態での点数確認（これは本来前の結果から求まる）のため提出していた。そのため満点を取った時には56ペナついていた。26位。

ハーメルンを読んで時間を潰し、午後9時からARC135に出た。

AtCoder Regular Contest 135 - AtCoder

Aは実験すると2と3だけになるまで分割するのがよさそう。 $k$ 回目の分割では $\lfloor X/2^k\rfloor$ と $\lceil X/2^k\rceil$ の形の数しか現れない、ということがAGC044Aで出ているので、同じ数をまとめれば十分高速に計算できる。まとめるというか本当はメモ化再帰するだけで良かったのに、何を考えたかmapで分割をシミュレートしたりしてちょっと実装に手間取った。Bは $S_{i+1}-S_i=A_{i+3}-A_i$ なので、 $A_{4\dots N+2}$ を $A_{1\dots 3}$ からの差分で表せる。これで各 $A_i$ が正になるために必要な $A_{1\dots 3}$ の最小値が求まるので、 $A_1+A_2+A_3=S_1$ を満たせるかどうかをチェックすればよい。Cは実験すると2回以上の操作が無意味だとわかる。その前に上の桁の多数決など考えていたので、1回しか操作しなくてよいことが分かってからもそのまましばらく考え込んでいたが、実は操作後の総和がbitの各桁を見るだけで求まるので、操作に使う数を全探索できる。

Dはよくわからなかった。なんとなく右と下に押し付けるとよさそうと思ったので手で実験してみると、どうやら各行各列の交代和が現れるらしい。最小性について、よく見ると操作で交代和が保存されるので、操作後にどのような $A_{i,j}'$ になっても $\sum_{j=1}^W |A_{i,j}'|\ge\left|\sum_{j=1}^W (-1)^jA_{i,j}'\right|=\left|\sum_{j=1}^W (-1)^jA_{i,j}\right|$ 、つまり実験で出てきた交代和が $i$ 行目だけ見た時の最小だとわかる（ただしこれは全体が最小値であることを必ずしも意味しない）。押し付ける行と列を全探索しようと思ってしばらく考えるも、最後の微調整が必要そうで難しい。ここで、行と列に押し付けようとすると、行だけ・列だけ見た時の最小性は満たされるが全体としての最小性は満たされないことに気づいた。代わりに不変量となる交代和に注目して、それを作るように数を配置すればよさそう。市松模様のように符号を反転して考えると、ARC133Cの証明っぽく貪欲に置いていくことで最小値が達成可能。交代和が保存されていれば構築可能であることは示さなかったが、どうせできるだろうと投げたら通った。解説でその証明を見て納得。

C - Row Column Sums

残り時間はEを考えていた。実験してみると途中から等差数列になるようで、それがスタートするインデックスがだいたい $O(\sqrt X)$ で抑えられることも分かった。しかしこれでは、割り算を含むループなので6secでもさすがに間に合わない。高速化の手がかりが掴めないままコンテストが終了した。4完34位。

コードゴルフ。Aはメモ化再帰ということで素直にRubyで実装する。CもRuby。他は手付かず。

明日の勉強会で発表する予定の、AlphaCodeのpreprintの要約だが、それなりに頑張っているので発表スライドを公開しようと思っていた。著作権が気になっていろいろ調べてみたところ、どうにも要約は著作物の「翻案」に当たるようで結構注意を払う必要があるらしい。今読んでいるpreprintの著作権の扱いがDeepMindのページを見てもよくわからなかったため、微妙に怪しいかもしれない。図表をコピペしないということで何とかならないだろうか。

今週の週記は短めだった。週前半をハーメルンに吸い取られたのが効いている。文字数的には200万文字以上読んでいるので身動きが取れなかった一方、ネット小説を読んだ感想はどんなに長くても1作品ごとに書いているので日記の文字数に貢献しない。まああまり長くても読みづらいだろうし、編集画面が重くなったりするので、短いことは悪いことではない。