読書記録（2022）

kotatsugame.hatenablog.com

1月

  • 2日
    D級冒険者の俺、なぜか勇者パーティーに勧誘されたあげく、王女につきまとわれてる3
  • 3日
    VRゲーで最強無双の少年、現実にステータスが同期し人生逆転
    劣等眼の転生魔術師6
  • 4日
    クラスで2番目に可愛い女の子と友だちになった
    エプロンの似合うギャルなんてズルい
  • 5日
    神狩1〈上〉
  • 6日
    公務員、中田忍の悪徳
  • 7日
    機械音痴な幼馴染が我が家でリモート授業を受けているのは、ここだけの秘密。
  • 8日
    最強魔法師の隠遁計画14
  • 9日
    いずれ水帝と呼ばれる少年
  • 10日
    私立シードゥス学院III
  • 12日
    『ずっと友達でいてね』と言っていた女友達が友達じゃなくなるまで
    友人に500円貸したら借金のカタに妹をよこしてきたのだけれど、俺は一体どうすればいいんだろう
    転生魔王の大誤算4
  • 13日
    前世は剣帝。今生クズ王子3
  • 15日
    俺は星間国家の悪徳領主！2
  • 16日
    俺は星間国家の悪徳領主！3
  • 17日
    俺は星間国家の悪徳領主！4
    西野 ～学内カースト最下位にして異能世界最強の少年～9

週記（2022/01/10-2022/01/16）

01/10(月)

先週の週記を投稿してからの話。結局この日は徹夜っぽい感じに過ごすことになった。

午前中の間は、他の人の日記を遡ってずっと読んでいた。書いた人が考えていることが伝わってくる文章で、読んでいてとても楽しかった。わが身を振り返ることにも繋がる。自分の考え方との違いを探ってみたりして、ああこの人も生きているんだなあ、というようなことを感じた。僕は基本的にTwitterしか見ないし、Twitterで積極的なコミュニケーションを取るわけでもないので、最近はアカウントを血の通った人間が動かしているということがあまり実感できなくなった気がする。

昼からは本を読んでいた。眠い目を擦りつつ何とか1冊読了。「私立シードゥス学院」3巻。シリーズ最終巻らしい。最後まで読んでみたところ、なんと1年目のクリスマス前で終わっている。なんと中途半端な時期か。しかし学院のイベントが盛りだくさんなため、それぞれで1つずつ話を作ったらこのような感じになってしまったのだろう。実のところ、話に出ていたものすべては回収できていないような気もする。最終話の主題は主人公三人組のうち獅子王琥珀ただ一人で、ほかの二人についてはシリーズ全体を通してあまり掘り下げられた感じがしなかった。そのためか二人の区別があまりついておらず、今回もセリフの発話者を逐一確認しないとすぐよくわからなくなってしまって読むのが大変だった。内容的には特に感想が見つからない。

CodeChefの1月Longが終わっていた。先週この↓ようなことを書いたが、結局今日、本を読みつつ格闘して最終問題も何とか通ってくれた。レートの変動はやはりなさそう。CodeChefのレーティングシステムがよくわかっていない。

月曜日の夕方まで開催されているので、問題には言及できない。今のところ最終問題が解けていない。

週記（2022/01/03-2022/01/09） - kotatsugameの日記

https://www.codechef.com/JAN221A

RIFFLESはしばらく実験していたが、functional graphということに気づけばループを見るだけでよい。XOREDはよくわからない。1\dots N-3をまず固定して、残りの状態で場合分けした。2^{17}は常に使えるので、それを使って当てはめられるならよし、そうでない場合は2^{17}+2^{18}を使ったりしている。残り2要素のXORが0になってしまった場合はN-3も弄っている。MASTERは左から重複を抜いていったとき各要素が残るような区間の選び方を考えるとよくて、式を整理するとkの係数と定数項の2つで表せる。両方区間SUMのセグメント木で管理する。

GENECYCは難しかった。まず1の辺だけでサイクルを成している必要がある。これをサイクルに分解した後、間に浮いている辺でサイクルを切っていってvertex inducedな状態にすればよい。サイクルで切るときの操作コストは、多角形の三角形分割を考えると3倍がちょうど満たされる。しかし数回試して通らなかったので絶望していた。眠気でシバシバした目でコードをにらみつけてもよくわからない。これまで、間に浮いている辺があるかのチェックと同時に、重複する頂点が存在する場合はそこでも切るようにしていたが、重複する頂点のチェックをしないようにしたらACケースが増えた。よくわからないまま、重複する頂点のチェック→浮いている辺のチェック、というように完全に順序付けて処理してみたら通った。

後から何が起こっていたかを理解した。重複する頂点がある場合、そこから伸びている辺であってすでにサイクルの別の場所で使われているものも、間に浮いている辺として検出されてしまう。そこでサイクルを切っていくといずれ2頂点のループを作る羽目になる。これ自体は辺のラベルを変化させないが、操作コストが増えてしまう。それでコストに関する条件を満たせなくなっていたようだ。実際、長さ2のサイクルは答えに含めないような処理を入れると、処理が順序づいていなくても通った。操作コストが超過している場合exit(1)する提出もあったのだが、どうやらこれはWAとして扱われてしまうらしい。

1の辺だけ見てパスを伸ばしつつ、パスに含まれる頂点と隣接した瞬間そこでサイクルを作って辺のラベルを全部入れ替える、という操作を繰り返す解法をTLで見た。シンプルで頭がいい。サイクルの集合がXORで閉じているという性質をより直接的に使っている。

午後7時就寝。

午前1時に目を覚ます。新春TechFUL Coding Battle 2022の結果が出ていた。全完だがペナ差が響き、なんとか8位に滑り込んだ……ように見えたものの、よくよくスレッドを確認すると問題に不備があったらしく、1問が採点対象外となっていた。順位表ではそれも含めた点数が表示されているため、まだ確定ではないようだ。順位表で僕の下にいるように見えた人たちも、1問解けなかったのではなく1問解かなかっただけなのかもしれない。これはマズいか。ともかく、ようやく各問題についての感想が書ける。

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

「Make Unique」の制約がよくわからなかった。コンテストサイトを信用していないので、0\le K\lt \sum A_iという制約から0\lt\sum A_iを読み取ってよいのかがよくわからない。恐々投げたら通ったが、実際ほとんど関係ないコードではある。「Mex Sum」は難しかった。i=0\dots Mについて1\dots iを全て含む列の数を数え、足し合わせると答えになる。しかし肝心の列の数は重複組み合わせを使った包除原理の式になってしまう。しかしここで、出現する重複組み合わせが符号を含めてほとんど同じ形をしているため、何回出現するかを数えればよいことに気づいた。具体的には(-1)^i{}_{M-i}\mathrm{H}_Nが\sum_{j=i}^M {}_j\mathrm{C}_i回出現する。この和はWolfram|Alphaに投げると{}_{M+1}\mathrm{C}_{i+1}と閉じた式で表せたのでよい。この問題には14分強かかっており、なんとかタイムボーナスは満点だったものの、解答時間の総和ではかなり遅れを取ってしまった。

「楽しいすごろくゲーム」の四捨五入の部分は、以前のTechFULの経験から何も考えずsetprecision(2)するとよいということが分かっていたので、それで投げた。数値計算の誤差がヤバいはずなので問題文がかなり怪しいと話題になっていた。テストには誤差で答えが変わりうるケースが入っていないと聞いたが、特に問題文に記載はない。そもそもTechFULにはスペシャルジャッジの概念がないため、仕方なく四捨五入をさせるような出力形式になっているらしい。「Domino Tiling」はやるだけ、だが最初に変な貪欲を書いて時間を浪費した。「複雑なあみだくじ」はインデックスのペア(i,j)があみだくじを辿った後に(k,l)になっている場合の数、というのをまとめて行列累乗で計算できるので、適切に足し合わせると解ける。しかしこの問題が不備によって採点対象外となったものなので、せっかく解法がすぐ見えたのに意味なし。

ここから追加された問題。「01-prefix」はTrie木でprefixごとにカウントするだけ。「Kが日」は合わせるのに大変時間がかかった。未証明だがAlien DPだろうという予想はついて、dpも意味のある遷移がN\times 51種類しかないので間に合う。しかし答えが全然合わなかった。まずペナルティはdoubleで考える必要があって、しかもちょうどK回ペナルティが発生する場合があるとは限らないので、真の値を得るためにはペナルティに使った回数ではなくKを掛ける必要があった。それをroundにかけて出力したらやっと通ったが、3ペナと80分を使っている。実は最近のABCでもAlien DPが出ていたらしい。未ACで解説も読んでいなかった。

布団でしばらくラノベを読んで、午前5時に再度就寝。

01/11(火)

午後0時起床。学食で昼食を摂った。今年初めてとなる。帰省から帰ってきてずっとパックご飯にインスタント味噌汁で耐えていた。

帰宅したらFHC Tシャツが届いていた。袖の部分に「TOP 200」と書いてあるのが、上位200人の特典のようだ。

ABD1の43ptで82位。R2を59位で通過したとき、Tシャツにバッジが付くのがR3の上位200人であることを知って残念に思っていたが、結局R3でもそれなりに良い成績を残せた。

週記（2021/10/04-2021/10/10） - kotatsugameの日記

先週土曜日のABC234-Dの最短コードが取られていた。答えが単調増加になることを利用すると、全体で線形時間で解けるようだ。うっかりしていた。

atcoder.jp

はてなスターの仕様変更があった。ビジュアルや操作感はかなり向上している。特に、スターを付けると目に見える動きがあるのがうれしいところ。一方、記事内の特定の文章にスターをつけるためには、その部分を選択した状態でページ最下部のボタンを操作する必要があるようで、結構難しくなったと感じる。

star.hatenastaff.com

しばらくラノベを読んで、午後4時からインターン先定例会のための進捗報告スライドを作り始めた。月曜日が休日だったので火曜日にずれている。年末年始は本当に何もやっていないうえに、今週もゼミ発表があって木曜日までは動けなさそう。さらに金曜日に1on1の予定があって、しかも同じく金曜日は年末から残していた業務の期限になっているらしい。ひたすら怠惰。

いつもの時間になっても始まらず、よく見たら予定がいつもと微妙に異なっていた。思いがけず時間が空いたため、せっかくなので少しだけ業務を進めていた。しばらくして定例会が始まる。自分の現状を赤裸々に報告するとメンターさんに大変に心配して頂いて、申し訳なさがすごい。実際はちゃんとやれば間に合うはずなので、そんなにマズいわけではない。

勉強会について。今日の発表に対して自分が行った質問は頓珍漢なものだったので、反省のため少し詳しいことを書いておく。テーブルデータの学習について、ある項目がどれくらい予測精度に貢献するかを探る話。素直に考えれば、ある値を無視して学習を行いその精度を比較する方法があるが、これは項目ごとに都度学習を回す必要があって計算時間的に嬉しくない。そこで、その項目の値を全データでシャッフルし、学習済みのモデルで再度評価した精度を見てもよいらしい。こちらは追加で学習を回す必要がなくて嬉しい。自分は「学習」と「評価」を混同していて、何が嬉しいのかよくわからず質問したのだった。

布団に入ってラノベを読んでいたが、午後7時半に寝落ち。午後10時過ぎに少し目を覚ましたものの、またすぐ二度寝した。

01/12(水)

午前1時起床。

ラノベを1冊読了。「『ずっと友達でいてね』と言っていた女友達が友達じゃなくなるまで」。非常に良かった。この巻は終始距離感が近すぎるヒロインに悶々しつつ進んで、その様子も微笑ましかったが、終盤でお互いがお互いへの好意を自覚し、両片思い状態に突入した。そのまま進めば2巻では学校生活も描かれるはずで、楽しみ。

Pythonの講義の課題が昨日出ていて、そのうち講義のキーワードを抜き出すものの期限が今日になっているので、忘れないうちにと提出しておいた。その後午前2時からゼミの発表準備を始め、午前6時前に切り上げて布団に入った。しかし布団の中で2時間くらいYouTube shortsを見続けてしまい、すっかり日が昇ったのを見て諦めて起きていることにした。YouTube shortsは自由に動画を探すのが難しく、特に次の動画に進む操作をするとYouTubeが勝手に選んだものを見ることになる。これがむしろ時間を溶かすのに向いているようで、冷静になると全然興味がない動画も何となく見てしまうことになって常に新鮮な刺激が得られる。

ラノベを1冊読了。「友人に500円貸したら借金のカタに妹をよこしてきたのだけれど、俺は一体どうすればいいんだろう」。良かった、はず。主人公が無自覚モテ男であるという設定が好み。イラストも好きだった。しかしそれ以外のストーリー的な良さを探そうとしても見つからず、何をもって良いと感じたのかは謎。

今日これまでに2冊ラノベを読んだが、どちらも秋ごろの新刊である。最近買うペースよりも読むペースのほうが速いため、ついに積読の山に手が伸びるようになった。特に1冊目のラノベはすでに2巻の発売が間近に迫っていて、TLに感想が流れてきてもいたため、気になっていた。

雪が降る中学食に向かい、昼食を摂って、注文していた本を受け取ってきた。

帰宅して、午後2時くらいまでインターンの業務を進めていた。コミュニケーションのため昼間に進める必要がある部分を終わらせ、次にゼミ準備を再開。ラノベを読みつつ進めていて、途中で1冊読み切った。「転生魔王の大誤算」4巻。終盤は展開に引き込まれ、ゼミ準備の手が完全に止まっていた。主人公の前では内気な少年だがそれ以外の場所では冷酷無比という描かれ方をしていたサ藤というキャラがいて、この巻はずっと彼に焦点が合っていた。いつか何かやらかしそうという印象だったが、友人を得て人間的に成長した。展開としても好みのシーンが多く、最後はキッチリ主人公の無双で締めていて大満足。

ゼミ準備のラストスパート。ルジャンドル記号の話で、(n\mid p)（テキストでは横に書いていた）を求めるのにn^{(p-1)/2}\bmod pを求めるのは大変だから、m=\sum_{t=1}^{(p-1)/2}\lfloor tn/p\rfloor+(n-1)\times\frac{p^2-1}8を計算して(-1)^mとしてもよいですよ、ということが書いてあった。しかしこれは別に楽になっていないだろう。というわけで、それがなぜかということについて余談という形で話すことにした。前者がO(\log p)で計算できるのは明らかだが、実は後者もfloor_sumを使えば同じくO(\log p)で計算できる。肝心のfloor_sumを説明するためにブログ記事などを読んでいた。計算ステップ数については、オーダーこそ同じなものの、明らかに定数倍から前者のほうが高速になるはず。一方後者はpではなく2で割ったあまりを求めることになるので、非常に大きなpに対しては後者のほうが高速になるのかもしれない。

floor_sumのアルゴリズムの初出を聞かれるかもしれないと思ってそれについても調べていたが、結局よくわからなかった。Library Checkerには一番最初からある問題のようで、特に説明などもない。

午後7時半くらいに完成。とりあえずホスフィンに投げつけ、見直しは明日起きてからする。今週の頭から溜めていた日記を書き進めた後、午後10時就寝。

01/13(木)

午前9時前に起床。昨日の夜にチュウニズムで激ヤバリザルトが出ていたのを知った。

年に一度、チュウニズム（を含む音ゲー3機種）の全国大会があって、それの予選として用意された3曲がついに通しで理論値陥落したらしい。昨年は不正な操作で一瞬理論値がランキングに出たことがあったが、今年は真っ当に理論値が出されている。また達成の瞬間が動画に収められていたらしく、別の人からツイートされている。この動画も、世界で一番チュウニズムが上手い人の体の動きが見られるという点で非常に貴重なものである。一般に上からの手元動画は星の数ほどあるものの、横からの手元動画になると途端に数が少なくなり、全身が見られるものなどはほとんど存在しないはず。一方チュウニズムが上手い人は手元が落ち着いていると言われており、これについては横や後ろから見たほうがわかりやすいので、上手い人の体の動きが見られる動画は嬉しい。

昨日作ったスライドについてホスフィンからありがたくもフィードバックをもらったので、それに沿って少し修正。紙に印刷して見直ししつつ、教科書に書いてあるのに書き忘れたこと、また他に伝えておきたいことがないかを調べて書き込んでおく。それも終わったので、しばらくラノベを読んでから正午に家を出た。雪が少し残っているので、地下鉄で山に登る。確か2019年の冬だったか、原付の冬用タイヤを購入したのだが、次の春に普通のタイヤに戻してからこれまで1回も交換していない。昨年はコロナでほぼ山に登らなかったからで、今年も同様。週に1回しか山に登る用事がないうえに実際に積雪するのは数週間程度ともなれば、タイヤ交換代より地下鉄を連打するほうが安くなると気づいてしまった。

遅刻もせず、ちょうどいい時間にゼミの教室にたどり着いた。コロナが最近また蔓延し始めたため、次回からオンラインに戻ってしまうらしい。原付のタイヤを交換しなくて正解。発表はかなり下手くそで、何度も言葉に詰まってしまった。また勢いで正しくないことを口走ることも多い。もちろんすぐに訂正するとはいえ、伝わりにくさに一役買っているだろう。昨日の日記に書いていた計算量の話をするため、控えめな分量で用意してきたはずだったのに、3分の1くらいが終わらなかった。計算量の話は図を黒板に書きつつ説明したかったので、キリのいいところで切り上げてそちらに移ったが、これもまたずいぶんと下手くそだった。式変形を追うだけだとよくわからないアルゴリズムだと思っていて、グラフを書いて格子点を数える話に持ち込み、図を横から見ることで計算量のトリックが理解できますということを言いたかったのに、どういう図を描くかを全然考えていなかった。ただまあ、最後の黒板発表で好きなことを喋り散らかせたので、そういう満足感はある。終わってから黒板を消す前に写真を撮った。

発表用スライドもここに置いておく。

Apostol_Chapter9_9.1-9.6.pdf - Google ドライブ

ゼミ後、今日もまた部屋を移動してボードゲームで遊んだ。今日が最後になり、寂しい。ずっとスカルをプレイしていた。今日も適当にかなり大きな数でチャレンジして遊んでいた。この場合場に1枚しかない状態で早めにチャレンジを始めると成功しやすい感じがしたので、自分から積極的にチャレンジをしに行った。すると、もっとタイルを重ねたい人もいたようで、後半、初手は2枚重ねて出すという独自ルールを入れて遊んだりもした。そうやってプレイしていると頻繁にチャレンジ失敗するので、自分のタイルがどんどんなくなってしまう。5人いるのに2人消え、1人も残り1枚になってしまうという状態が2回発生したが、こうなると理詰めで必勝パターンがありそうだったりして、スカルってそういうゲームだったのか……みたいな気持ちになった。

眠くて途中一瞬寝てしまったのを見られたりしつつ、今日は名残惜しむように午後8時まで4時間近く遊んでいた。当然学食も閉店しているため、コンビニでパン類を購入しつつ帰宅。眠気に耐えつつ今朝読んでいたラノベを読み進め、午前2時前に読了。「前世は剣帝。今生クズ王子」3巻。主人公の自分語りが多すぎるといって1巻の印象は悪かったものの、それから自分の中での評価が単調に増加している。おそらく、ストーリーが進むにつれて主人公の対外的な露出が増え、実力を発揮するシーンが多くなってきたからだろう。一般に主人公が無双していると面白いのだ。

午前2時半就寝。

01/14(金)

午前9時起床。

眠気がかなり強く、午前中はYouTubeを眺めていたら終わってしまった。最近またデュエルマスターズの対戦動画を漁り始めてしまい、よくない。「しゃまのデュエマちゃんねる」に上がっている、「かんぜさん」との対戦動画が、その空気感も含めて好き。実はしゃまさんはつい最近YouTuberを引退されたらしく、それについての動画がYouTubeでおすすめされて、熱が再燃したという事情がある。

www.youtube.com

学食に向かうも、明日から共通テストということで今日は休講日らしく、空いていなかった。仕方なく購買で惣菜パンを購入。ついでに、倉庫からの出荷メールが来て数日経過していた本が入荷していないか確認した。ちょうど明日が発売日の本。これまで、予約した本の出荷自体は発売日の数日前に行われるも、入荷メールは毎回発売日後に届いていたので、実はメールが届いていないだけで本はあるんじゃないかと思ったのだ。しかし本自体も届いていなかった。一般の本屋なら発売日の1日前から並び始めることが多いと思っているが、そのあたり大学生協はかなり律儀らしい。本を1割引きで売れる理由も含め、良くも悪くも普通の本屋ではないということか。

大学生協の本はなぜ安い？ 〜書籍の再販制度を問い直す〜 - THE KINGDOM POST

帰宅してしばらくインターンの業務を進め、午後1時半から1on1。進捗こそほぼないものの、今後の動きを確認しているうちに話が弾み、いい感じの雰囲気のまま午後3時まで話していた。また業務に戻り、午後5時前にほぼ完了。何とか期限内に終わらせられた。Slackを見ていると、サークルの定例バチャが行われていることに気づいたため、急遽参加した。

https://kenkoooo.com/atcoder/#/contest/show/c9be0204-c369-489f-91df-6342eb964c77

なんとなくPythonで参加した。全問、素のPythonで通るコードが書けている。ABC132-Fで商が同じになる除数の区間を求める必要があるが、これを\sqrt Nで分けてごちゃごちゃするのではなく、単純な一つのループで統一的に求める方法が美しくわかりやすいため、バチャ後の感想会で強くおすすめした。下の提出の3行目から9行目である。Nを割った商がqになる最大の数は\left\lfloor\frac N q\right\rfloorである、という事実に基づいている。

atcoder.jp

日記を書こうとしつつボーっとしていたら、たまたま以下のツイートを目にした。コードゴルフの時間だ！

急いでコンテストページに飛び、上の問題からなぎ倒していく。案の定最初のほうは非常に簡単で、これはコンテストの存在にいかに早く気付くかだったな～と思いつつ最短コードを確認したら、昨年末からの提出がたくさんあってさすがにひっくり返った。どうやら本にでもURLが記載されていたのか、トップページに載ってこそいないものの以前からアクセスできたコンテストだったらしい。そ、そんな……。URLで検索したところ、以下のツイートが引っ掛かった最古のものだった。これは辛い。

それでも全然ゴルフし切れていない提出が山のようにあるため、午前4時までノンストップでコードゴルフし続けていた。問題自体が簡単なため特に見るべきものはない。グラフ問題のTLが1secになっていてnetworkxが死ぬほどTLEした。また3問ほどテストケースに改行がついていなかったり変な風になっていたので、報告しておいた。面倒なことが目に見えていたため飛ばした問題もそこそこある。

CFを開いたらメッセージが来ていた。Good Bye 2021の商品として、仮想通貨「NEAR」がちょびっと貰えるらしい。コンテストのAnnouncementによれば僕は「Ⓝ4」貰えるはずで、検索したところ価格が2300円弱と出たから、素直に考えればおよそ9000円か？かなり高額であると感じる。しかし受け取るためにはウォレットを作る必要があるなど、実際に日本円にするまでが非常に面倒そうだったので、放置することに決めた。いつだかのTCO Regionalの交通費もPayPalに塩漬けになっている。今調べたら18694円だった。とにかく面倒である。

午前5時就寝。

01/15(土)

午後1時前に少し起きていた記録があるが、しばらくしてまた寝たはず。午後8時起床。睡眠負債がたまっていたらしい。

atcoder.jp

5\times 10^5文字の括弧列がvalidか判定する問題。拡張正規表現の再帰機能を使って判定する方法があるが、さすがに間に合わないだろうと試しもしていなかった。爆速で通っていてびっくり。

atcoder.jp

\left(\frac{N(N+1)}2\right)^2を例の素数で割ったあまりを求める問題。それほど大きくない値だからと素直に2乗してから余りを取っていたところ、この演算に|コマンドが使えるのをすっかり見落としていた。今日更新されているのを見てかなり衝撃を受けた。

食事してシャワーを浴び、午後9時からABC235に出た。

HHKB Programming Contest 2022（AtCoder Beginner Contest 235） - AtCoder

Aは少し考えると111\times(a+b+c)とわかる。dc。Bはやるだけだが短い書き方がわからず、AWKで適当に出したら2ペナついてしまった。CはとりあえずRubyのgroup_byを使った。ここからC++。DはBFS。Eは一瞬、パスに含まれる重み最大の辺を探しそうになるが、冷静になるとクエリごと重みでソートしてクラスカル法をすればよい。Fは桁dp。最初場合の数だけ数えていて、あとから急いで総和を求めるdpを付け足した。計算量が\sigma=10としてO(\sigma 2^\sigma\log N)、つまりおよそ108に定数倍がかなり付くため、700msを超えている。Gはしばらく方針ガチャを回し、包除原理を引き当てた。\sum_{i=0}^A {}_n\mathrm{C}_iみたいな値を0\le n\le Nで求める必要があるが、n\rightarrow n+1と計算すると毎回定数時間で差分更新できる。この着想は、パスカルの三角形において1段下がることに対応→2つ用意してずらして足し合わせるとよい、という観察から得られるし、具体的な値を\sum\left({}_{n+1}\mathrm{C}_i-{}_n\mathrm{C}_i\right)=\sum{}_n\mathrm{C}_{i-1}から導くこともできる。

Exはすんなり解けてしまった。グラフが木ではなくてびっくりしたが、最小全域木さえ取ればよい。クラスカル法のマージ過程を表す木で木dpをする。操作を行った回数に対して場合の数を持ち、その列を畳み込むような遷移になる。ただし、今見ている集合のすべての頂点を赤く塗る場合は1回で操作できるので、それを足して代わりにマージ前のそれぞれの集合を1回ずつ赤く塗る場合を引く更新を加える。2乗の木dpの亜種で計算量がO(NK)になるというのが、つい最近のOpenCupで出た。うっかり固定長配列を毎回O(K^2)かけて畳み込んでしまったので提出直前に計算量解析が壊れていることに気づき、ACLのconvolutionで書き直した。畳み込みの高速化は今回の場合あまり意味がないものの、便利ではある。

2乗の木dpで配列をKK番目までで打ち切ると、計算量がO(NK)O(NK)になるという話を聞いた。

週記（2021/11/22-2021/11/28） - kotatsugameの日記

全完14位。学生5位に滑りこんだかと思って喜んでいたものの、トップページを確認すると4位以下は飛び賞しかなくがっくり。これはBの2ペナがなくても変わらない。

Dは1からではなくNからBFSすると値の大きさに気を使う必要がなくなって簡単。Fはこの計算量が想定解でびっくりした。G問題の解説では、経路の数え上げに帰着して差分更新を行う方法が記載されていた。結論こそ同じであるものの、経路に帰着する方法はあまり成功した覚えがない。かろうじてカタラン数のような途中の値に制限がある問題を解いた記憶だけがある。

コードゴルフ。ABはコンテスト中のものが最短。CはAWKで書くと短くなった。a_i=0が存在するので、$++iを条件式にするとループを最後まで回すことができない。これまではi++<NFを使っていたところ、今日新たに$++iに空文字列を連結して無理やり文字列にする方法が出た。値を出力するときに散々使ったテクだが、ループの条件式に出現したのは初めて目にした気がする。この更新で取られた。DはPerlで、BFSを深さごとに区切って一段一段進めていく書き方をしたら縮んだ。Eはコンテスト中に出ていたPerlコードに隙がない。以降は手付かず。

午後11時半からCF #766 div.2に出た。全完13位。

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

Aはよい。BはTinaが四隅のどこかに座ることが分かって、最も遠い隅への距離を各マスについて求めたら、その値が小さい順に塗っていくのが良い。すると、出力は小さい順にソートした列そのものになる。Cはなぜか辺の重みがdistinctである必要があると勘違いして1WA。次数3以上の頂点があるとダメで、そうでない場合、つまり直線グラフは2と3を交互に塗っていくとよい。Dは10^6\dots 1の順にそれがgcdとして出現できるかをチェックした。倍数が列にあるかは愚直にチェックしても調和級数で押さえられて、倍数のうち最小のものとそれ以外でgcdを計算してチェックしたのでlogが2つついているが爆速だった。Eは気合いでdp。最小になり得ない値を削除しておけば、はしごに至るまでのコストは直左と直右から計算するだけで十分になる。Fは行を行き来する切り離し方に気付かず1行ずつ見るdpを必死に書いて1WA。切り離すラインは(0,0)から(K/2,K/2)までグリッドを辿る移動とそれを180度反転したものになるので、いくつのペアが分かれるかをカウントして最短経路問題を解く。途中で交差してしまうような経路は最短にはなり得ないため、これでよい。

Eを実装している途中に津波注意報のエリアメールが来てびっくりした。地震速報かと思って身構えたが、特に揺れもないし沿岸部でもないので一旦無視。全完後に調べたところ、遠く離れた火山の噴火によるものだったらしい。

次のようにすると、Dのlogを1つ落とせるらしい。

午前3時半から日記を書き始めた。実は月曜日の前半を書いてからずっと放置していて、今この部分まで書いたところで午前10時半になった。実に7時間かかっている。

火曜日に出ていたPythonの講義の課題に取り組んだ。日曜日が期限になっている。今週はニューラルネットに三角関数を学習させるというもの。Kerasを使って一通り動くようなコードが与えられて、改善する例が示されているので、組み合わせて精度を高めるらしい。適当に層を増やしたり素子数を調整したり活性化関数をReLUにしたり、組み合わせ方は星の数ほどあるが、面倒なのでちょろっと試して一番良かったものがいいですね～という感じでお茶を濁した。しかし、一番良かったはずのモデルも再度動かしてみたら他のものとあまり変わらない結果になってしまったので、これまでの学習は実質乱数のご機嫌伺いをしていただけだったらしい。足元を崩されたような感覚を得た。

ラノベを1冊読了。「俺は星間国家の悪徳領主！」2巻。すでになろうのほうで読んでいて、さらに2巻は（というかこのシリーズは全部）文庫がぶ厚かったので、微妙に読むタイミングを逃した後はずっと本棚に安置してあった。1巻を読んでから丸一年空いてしまったようだ。非常に面白かった。良質な勘違いもの。僕の知る勘違いものは、どうしても主人公の自己評価が低くなりがちで、そういう意識を持つ主人公という視点から見ていると何となく場違いさを感じてしまう。この本では「悪徳領主のつもりが名君」という勘違いを主軸に書かれるため、主人公のふるまいも堂々としていて、読んでいて安心できた。展開というか勘違いの伏線もそれなりに手が込んでいるように感じられて驚かされる。

3巻に手を出すも急激に眠くなり、午後3時半就寝。

01/16(日)

午後10時半起床。食事してシャワーを浴び、午後11時半からECR121に出た。

Dashboard - Educational Codeforces Round 121 (Rated for Div. 2) - Codeforces

Aは2文字あるものを1文字ずつ左右に並べ、その間を1文字しかないもので埋めた。今書いていて気付いたが、文字列をソートするだけでよかった。Bは足して桁が減らない場所があればそのうち一番右のものを選び、そうでない場合は一番左の2文字を足すとよい。Cは問題文を読んですぐdpに飛びついたものの、遷移を書くのがかなり面倒なことに気づいて方針を変えた。貪欲っぽいことをしてよいはずで、ダメージの棒グラフがなす三角形をstackを使ってシミュレートする。直前のspellからリセットできない限り、それをpopして三角形のサイズを合わせるのを繰り返した。Dは度数分布に直した後、左右それぞれのサイズとして何を使うかを全探索した。この時中央のサイズは小さければ小さいほど良いことが言え、またそのサイズのみが答えに関係するので、左右から被らず決めたサイズをオーバーしない範囲で貪欲に取れる。この貪欲は毎回計算しても間に合うところ、尺取りの要領で少し高速化している。

Eはひたすら面倒で、しかも日記のこの部分を書いている間にHackケースを思いついてしまった。黒い頂点を適当に1つ根にする。根の直接の子のうち、部分木に黒い頂点を含むものが2つ以上あるか、もしくは1つであってもその部分木に黒い頂点が2つ以上、祖先関係にあるように存在すれば、どの頂点の答えも1になる。要するに、黒い頂点を3個以上含むようなパスが存在するかをチェックしている。それ以外の場合は、黒い頂点に隣接する頂点から伸びる「分岐」だけ1にしてよいはず。ただ、この分岐というのを検出するのが難しく、何とか熱烈場合分けで対処しようとしていたものの、本質的にdfsを遡るような更新が必要なことに気づいてしまった。

Fは微妙に難しい。まず、1から16までそれぞれ割る・割らないでどう変化するかをまとめたい。これは{\rm lcm}(1\dots 16)=720720で割ったあまりで場合分けすればよい。樹形図みたいな分岐を考えて、そこに属する「場合の数」と「現在の値の総和」を持っておく。各段、その後の分岐がさらにnのべき乗あるのを掛けつつ答えに足す。1段進める際は、値が変わらないn-1通りと値が減る1通りをそれぞれ求めればよい。ところが、実装が終わって提出しようとしたらこどふぉのサイトが落ちていた。これは結局コンテスト終了まで復活しなかった。後から出したら通った。

ラノベを1冊読了。「俺は星間国家の悪徳領主！」3巻。相変わらず面白く、爽快。ただ主人公の婚約者となったヒロインの背景設定がかなり重かった。特定の血統に連なる人をネチネチ虐める組織が存在するというのは、スケールの違いこそあれ、読んでいて辛くなるタイプのR18作品の設定を思い出してしまう。最終的には主人公の力ですべて解決してハッピー。

しばらくコードゴルフをした。「アルゴリズムと数学　演習問題集」で金曜日飛ばした問題からいくつか解いた。幾何の問題で、線分と点の距離を求めることになって、場合分けが多くて面倒かと思っていたらかなりきれいに書けた。簡単のため、原点と点a(\vec{a})を結ぶ線分と、点b(\vec{b})を考えることにしよう。まず点から線分（を延長した直線）に降ろした垂線の足を求めることになる。これは\vec{a}と\vec{b}がなす角を\thetaとすれば、原点から点aの方向に|\vec{b}|\cos\thetaだけ進んだ位置になる。点aまでの距離に対する割合に直せば、|\vec{b}|\cos\theta/|\vec{a}|=\vec{a}\cdot\vec{b}/|\vec{a}|^2になるので、この値に\vec{a}を掛ければ求まる。今回は直線ではなく線分を考えるので、垂線の足がはみ出す場合をケアしなければならない。実はこれも、先ほど出した割合を0と1でclampすればよいだけ。肝心の割合も、aとbをそれぞれ複素数と見ると、なんと{\rm Re}\;b/aで求まってしまう。逆にここまで単純化すれば、やっていたことが「線分を単位長に合わせつつ実軸に揃える」→「点から実軸に降ろした足を見る」だけだったとわかる。

atcoder.jp

金曜日に公開されたコンテストの影響でShortestが1800問をとっくに通り越していた。またそういう虚無みたいな問題を積極的に埋めているからか、AC数も過去最高の順位を記録している。真面目に精進して難しい問題をバッタバッタ解いている人に引け目を感じないこともない。

週記（2022/01/03-2022/01/09）

01/03(月)

先週の週記を投稿したあとは、すぐ布団に入り、ラノベを少しだけ読んだ。冒頭に主人公がカツアゲされるシーンがあって、どうせ後々復讐の機会があることはわかっているけれど、それはそれとして精神的なダメージを受けてしまった。しかし30ページくらい進んだところですぐやり込めるシーンが出てきた。インスタントに力を得ているのが気になるものの、ストレスフリーなのは助かる。ほどほどで切り上げて午前6時就寝。

午後1時半ごろに起こされて昼食を摂り、また寝た。次に起きたのは午後6時半だった。寝てしかいないがなんとか夕食を詰め込み、ラノベを読んだ。2冊読了。

1冊目、「VRゲーで最強無双の少年、現実にステータスが同期し人生逆転」。展開は好みだったが、主人公がVRゲームで最強無双である理由が「一人だけステータスの伸びが異常で滅多矢鱈にスキルを覚える」というもので、受け入れられなかった。それはずるいだろ。そうするくらいなら、もともとトッププレイヤーだった等でいいのに。ただ、どこに「ずる」の境界があるかを考えているうちに、よく分からなくなってきた。プレイスキルの話でないなら結局何らかの形で運営から優遇されている必要があって、程度の問題に見えなくもない。主人公の状態の理由はまだ明かされていないが、ストーリーの根幹に関わっていそうな描かれ方をされているので、そのうちわかるのだろう。

2冊目、「劣等眼の転生魔術師」6巻。実はこれに限らず柑橘ゆすらさんの書くラノベはあまり好きではない（が、このシリーズは1巻を買ったのでそのまま購入を続けている）。テンプレな主人公TUEEEが多く中身がスカスカに感じるというのがその理由である。さて、この巻の後書きで、もうそろそろこのシリーズを完結させるというようなことが書いてあった。小説を未完のまま放り投げたくないという思いがあるそうだ。この作家は多作なので、そのほとんどをちゃんと完結まで持っていけていると知り驚いた。コテコテのテンプレ展開を書いてもちゃんと続刊できるほど売れているのは凄い。多作な作家は売れないシリーズに見切りをつけてぶん投げがち、という偏見もある。

入浴し、午後11時半からHello 2022に出た。

Dashboard - Hello 2022 - Codeforces

Aから題意を掴むのに苦労した。1マスずらしてもルーク同士が互いに攻撃し合わないという条件らしい。1行おき・1列おきにルークを配置する必要があって、対角線に並べておけば最大を達成できる。Bは左右両端にくっつく区間のうち最も安いものを持っておく。ただし両端を同時に達成できる区間は別に考える必要がある。どちらも前から舐めつつ更新できるが、丁寧に書いていたら結構時間がかかった。Cはサンプルを見るとわかって、未定の場所を連打してループを探せばよい。

Dにかなり時間がかかった。ある行を引っこ抜いてある列に挿入するという流れを考えると、これを達成するために必要なパスと、引っこ抜いたり挿入するときのために余分に確保する隙間がいくつかの長方形の組み合わせで書ける。実は考察ミスでちゃんとコストを計算できていなかったが、実際のところある8マスのうちどれか1マスを除雪すれば良かったようで、それをコスト計算に含んでいたため通った。この事実を知ってから改めて必要な場所を眺めると、確かに8マスのうちどれか1マスは必ず使っていることがわかり、驚愕。

Eは実装が面倒。クラスの年齢の平均値と先生の年齢をそれぞれ降順に並べると、先頭から順に対応させられればよい。生徒が一人消えるのは、クラスの列から1つ引っこ抜いて別の場所に挿入することに相当するため、1つ前後にずらして対応させたものも前計算しておけば、いくつかの区間をチェックするだけで答えられる。区間のチェックは累積和で行う。クラスの年齢の平均値を扱う代わりに総和と人数を持って頑張っていたが、切り上げ除算すると楽というのを聞いてかなり感心した。

Fは場合分け。0が隣り合っている箇所と1が隣り合っている箇所を数え、それの大小を見る。1が隣り合っている箇所が多いなら、0を消して11を増やしたり、あるいは両端の0を含めて追加で操作してもよい。0が隣り合っている箇所が多い場合は、...10...01...となっている場所をいくつ...101...まで持ってこれるかを数えて、その分だけ追加で操作してもよい。

Gは間に合わなかった。増加列を数えるためのBITを2本用意して、1本目から2本目にどんどん値を移していくことで寄与を数える。ただし「iを含みjで終了する」ような部分列の数を引く必要がある。この条件はO(N)個あるが、実はjでまとめてA_i\lt A_k\lt A_jなるkだけ考慮してみると、そのようなkもO(N)個である。Aの降順で並べると、jの決め方から各要素がkとして高々1回しか現れないとわかるからだ。よってiとjの間の増加列の個数は愚直に計算してよく、左側は前計算できるので、ちゃんと引く値が求まる。システス後に投げたら通った。

結局6完78位で、predictorによれば-15である。2900を割ってしまったが、Dでかなり詰まっていたことを考えれば耐えたほうとも言える。

しばらく日記を書いてから、C++のコードゴルフを行った。boostライブラリを使うもので、手元にコンパイル環境がないしテザリング状態で落としてくる勇気もないので、コードテストでちまちまやっていた。なにもわからない。append関数の第2引数の型を第1引数から推測する、みたいなことはできないらしく、またinitializer_listを直接渡してもどうにもならないようだ。point_xyに暗黙的に変換可能な型も見当たらない。

atcoder.jp

布団に入ってしばらくラノベを読んだ後、少しだけハーメルンを読んで、午前7時前に就寝。

01/04(火)

午前11時半に目を覚ます。

眠れないままハーメルンを1作読了。「さよなら愛しき記憶たち。」。以下少しだけネタバレになる。前半、悲しみの中にも少しずつ希望の光が見えてきたと思っていたのに、ちょうど真ん中の話でまた絶望の底に叩き落とされた。同じことを2回するのかなとも思ったが、今度はもっと速いペースで希望→絶望のサイクルが繰り返され、ヘトヘトになりつつ、なんとかハッピーエンドまでたどり着いた。正直バッドエンドもあり得ると思っていたので、救われた気持ち。ともかく感情を大きく揺さぶられる話だった。良い。

syosetu.org

今日の夕食に向けて、起きているなら今のうちに昼食を摂っておく必要があると考え、用意してもらった。食べ終えて布団に戻り、また眠れないままハーメルンを1作読了。

「好きな人を幸せにする能力【一話完結】」。1話ごとが長いものの、5話で諸々すっきりまとまっていて良かった。しかしハーメルンにおける他者の評価ほどには感じられなかった。必要最小限の情報だけを書いているという意味で、この作品は上手であるはずだが、作中の世界に浸りたい自分としては短い作品はあまり、ということかもしれない。

syosetu.org

その後もいろいろハーメルンをあさり続けている間に夕方になり、夕食のため出かけた。

4年ほど前、高校卒業・大学入学祝ということで連れていってもらった店（の本店）に、今日はこちらが両親を連れてきた。連れてきたと言っても車の運転は父だったが、会計は僕が持った。インターンで、初めて正式な契約を交わして金銭を得たので、そのお祝いという意味もある。少し早いが、初任給でネクタイを贈るのと同じ気持ちだ。僕が13時間働いたくらいの金額になったものの、今年も頂いてしまったお年玉と相殺された感じがする。

懐石料理で、メインディッシュの肉を目の前で焼いてくれる。出た料理は上のツイートとそのリプライに記録してある。各料理の見た目や味は自分には評価できないが、例えば煮物に入っていた里芋について、外が崩れていないのによく中まで火が通っているということを母が言っており、なるほどそういう点もやはりプロなのかと感心したことを覚えている。肉を焼く際には仕上げにフランベが行われるので、これを動画に収めようと画策していた。4年前に行った店では事前に撮影タイミングを声掛けして頂いたので、今回もそうだろうと期待して席でちんまり待っていたら、一言もなくにわかにマッチを取り出されたので、慌ててスマホを構えた。結果、少し遠いものの思った以上に上手に撮影できており、その中の1フレームを上のツイートに添付している。

本屋に寄って帰宅。睡眠不足と長時間車に乗った疲れから、日付が変わるまで2時間ほどこたつで寝てしまった。起きてから、01/06の夜が期限になっているレポートのために講義動画の視聴を始めたが、最後までいかないうちに家のWi-Fiからインターネットに接続できなくなってしまったので、諦めて自分の部屋に戻った。

昨日コードゴルフしたC++コードが縮められているのを見つけ、1時間ほど格闘したがどうにもならなかった。appendの代わりに内部のコンテナにアクセスしてpush_backすれば推論が効くようになったが、微妙に伸びてしまい不発に終わった。

布団に入ってラノベを2冊読了。1冊目は「クラスで2番目に可愛い女の子と友だちになった」。非常に良かった。冒頭でヒロインと初めて会話を交わしてからお互いに急接近し、なんと1巻の間にお互いの想いを確かめ合うシーンまでこなしてしまうハイスピードでありつつ、しかしいろんな過程をすっ飛ばしたわけではないという印象で、満足感があった。主人公は友だちの作り方を知らないぼっちという設定だったが、それでいてあまりもじもじし続けることはなく、締めるところは締めてくれて、その点も気持ちよく読めた。

朝食にラーメンを挟みつつ、2冊目は「エプロンの似合うギャルなんてズルい」。ヒロインと主人公は疎遠になっていた幼馴染で、序盤から小動物みたいなイメージのヒロインと主人公のいちゃいちゃが描かれていたが、ヒロインの重めな設定が明かされるにしたがって、甘いだけのラブコメではないというような印象に遷移した。

さらにラノベを開いたり、複数のハーメルンに手を出したりして、午前10時就寝。

01/05(水)

午後7時半起床。即座に着替えて、帰省の度に訪れている塾に今回も少しだけ顔を出した。

帰ってきてレポートの続きをしようと思ったら、まだインターネットへの接続ができないままだった。たまに一瞬繋がるらしいが、それでは意味がない。父が回線速度を計ると、3.5Mbpsだったようだ。家に引いている固定回線でそれは、流石に旧石器時代との謗りを免れないだろう。ルーターもかなりの年代品なので、そこを取り替えればマシになる可能性があるかもしれないが、いっそのこと回線から契約を切り替えてくれるそうである。次回の帰省までには改善していることを願う。

父が身を切ってテザリングしてくれたので、そちらに接続してレポートを進めることにした。幸い動画自体は説明文から見なくても良さそうとわかったので、早速レポートに着手。Google Colaboratoryでコードを書いたりTeXを打ったりする。レポートのテーマは昨日の時点で考えていたが、スタートとゴールを決めず途中の何を計算したいかだけ考えていたため、かなり大変だった。適当なスタートを設定して、そこからBFSみたいにいろいろ計算して、なんとか結論っぽいものをひねり出しつつ、さも最初からそれが目的だったかのように書く。今気づいたが、これは論文を書くときにやってはいけないこととして最近TLに流れてきた記憶がある。

3時間ほどかけて完成。その後2時間ほどかけて日記を書いた。帰省先で読んだ本は当然仙台に持っていかないので、感想などこの場で書いておくのが望ましかった。

布団に入り、ラノベを1冊読了。「神狩1〈上〉」。巻数と上・下が同時に存在するので、読書記録などどう表記したものか迷った結果、背表紙に忠実に書いた。帯の推薦文に「厨二心を刺激される」とあって購入した。実際、戦闘シーンは丁寧かつスピード感あふれる潔さで書かれていて、なかなかものすごかった。ただ設定や描写は肌に合わないと感じてしまった。裏表紙にあるあらすじが、購入特典の短編に隠されて読めないまま購入を決めてしまったのだ。「魔王2099」を僕がおすすめする理由として、スチームパンクな世界観を支える設定に忠実な描写を挙げていたが、こちらも舞台こそ変われど同じことが言える。スチームパンクなら受け入れられて、江戸は受け入れられないというのは、ただの自分の好みらしい。

世界観の精密な描写に圧倒されます。

今年読んだ本のまとめ - kotatsugameの日記

明日新幹線に乗るため眠らなければならないのに、眠れない。TLに逆紅クイズというものが流れてきたので、引き込まれていくつか解いてしまった。本家をクリアした後、有志が作成したものにも複数手を出したが、やはり本家は謎解き要素も作りこまれているし、ちゃんと正解できる程度の難易度・順番が考慮されている分、格別に面白く感じられた。スマホで見ていると、問題文が折り返されてしまい文字数がよくわからなくなっていたが、逆紅クイズメーカーで作られた問題のほうには、文字を空白に置き換える代わりに黒い四角に置き換えるようにする機能が付いていて、そちらはわかりやすくて良かった。

クエスト「文字を取り戻せ」

午前8時半就寝。

01/06(木)

午後1時半起床。食事して、昨日読んだラノベの感想をさっと書き、荷物をまとめて車に乗り込んだ。仙台に帰る。仙台から持ってきた本が1冊、富山で購入した本が11冊で、そのうち10冊を帰省中に読んだので、持って帰る分は2冊だけとちょうどいい感じになった。

帰省ラッシュはもう終わったと思っていたが、それなりに人がいた。進むにつれてどんどん人が増えていって、大宮の手前でついに僕の隣にも人が座るようになった。

大宮につく直前にラノベを1冊読了。「公務員、中田忍の悪徳」2巻。この巻も良かった。それはそうと新しく登場したキャラクターがかなり嫌な人物で、これもまたラノベらしくない描かれ方をしていたように思う。さて、1巻からずっと異世界エルフのほうに注目していたが、全然コミュニケーションが取れるようにならない。いったいいつまでかけるつもりかと思っていたが、そもそも異世界エルフはこの作品の主題ではないということに気づいた。それもそうで、題名からして主人公・中田忍に注目するべきであるようだ。帯に書いてあった主人公のセリフ「俺は、変わっているのか？」は、自分が奇天烈な人間であるかを確認しているのではなく、自分が変化しているのかを確認していた。その変化こそが、少なくともこの巻の主題だったのだ。

大宮で乗り換えが30分ほど発生したので、ゲーセンに向かった。パラパラと雪が降っていた。ゲーセンについてチュウニズムのところに行くと、4台が全部埋まっている上に待ちも4人くらいいたので、即座に諦めて退店。別のゲーセンを探してみることにした。3年くらい前、同じく大宮でFFとエンカ（原義）したことがあって、そのときに遊んだ店を探しにふらふら歩いていたが、見つからなかった。しかしいい暇つぶしにはなったので、駅に戻って次の新幹線に乗り込んだ。

もう1冊のラノベを開くも、そちらは読み終わらず、仙台に到着。駅前でつけ麺を食べ、部屋のマスクが残り少ないことを思い出して購入し、ゲーセンに向かった。今年初めてとなる。今日は手袋もないので、新曲や通常解禁された曲をとりあえず埋めていた。目立った成果もなく、午後10時半に退店した。

部屋に帰り着いて、今月のスマホ通信量を確認。ギリギリ3GB未満に収まっているように見える。3GBからまた値段が変わる契約プランなので、少し気になっていた。

パソコンの前に座ると離れがたかったので、シャワーを浴びる前に新春TechFUL Coding Battle 2022に追加された4問を解いた。追加分のvisibleは2問で、その部分は何とかまた理論値を維持できている。その後1月発売のラノベ新刊をチェックした後、やっとシャワーを浴びた。

橙diffの問題を1問通した。「Two Snuke」。\prod_a aを\prod_a \binom{a}{1}と読み替えるテクで、答えが\sum_{l=0}^{(N-5)/2}\binom{l+4}{4}\binom{N-2l+5}{10}と表せることまではたどり着けたものの、そこから進めず解説を読んでしまった。dpに戻して行列累乗と知りびっくり。また僕が求めた式でも、Nの偶奇で分けたあと\sumの中身を展開すると、lの14次式、つまり和を取って(N-5)/2の15次式になるので、ラグランジュ補完で答えが求まる。それとは別に、2個組にして考えることで偶数という条件を満足させる方法があり、こちらは直接O(1)で求まるようで、これで最短コードを取っておいた。

atcoder.jp

JOI春合宿の問題を1問解いた。問題自体は簡単だが、形式が特殊で、指定されたヘッダファイルを読み込み、そこに定義されている関数を呼び出す形で解くため、CまたはC++でしか通せない問題。std::minmax_elementを呼び出すだけのC++コードが最短になっており、そちらも配列サイズを誤魔化すと縮んだが、それよりもJOI公式サイトから見られる想定解コードが上手だった。2要素ずつループで回して逐一更新していくと、高々定数個の変数でコーディングできるようだ。そちらをC言語で書いてしばらく縮めていたら、C++コードを容易く抜き去ってそれなりに短いコードが出来上がった。しかし、Compareという関数の呼び出しが3か所に存在するので、何とか別名をつけたくなった。これは関数ポインタを使用することで達成できる。普通に書くとint(*f)(int,int)=Compareとなるところだが、C言語のゆるさを存分に発揮すると(*f)()=Compareで動いてくれた。

atcoder.jp

布団に入って少しラノベを読むも、眠気が強すぎる。早々に切り上げて午前7時就寝。

01/07(金)

午後1時すぎ、腹を壊して起床。眠気こそまだかなり残っているものの、なぜか眠れない。

昨日少し読んだラノベに手を出して、読了。「機械音痴な幼馴染が我が家でリモート授業を受けているのは、ここだけの秘密。」。特に面白くもなかったが不快感もない、総じて記憶に残らない本だった。記憶に残っていないので何も書くことがない。

その後もスマホを触りつつゴロゴロしていたが、夕方になってどうにも眠れなかったことを受け入れ、ベッドから起き上がった。ゲーセンに行くことにした。地下鉄に乗って、まず仙台駅まで出てサイゼリヤに入店。今月の間違い探しは、初手からろうそくの長さが違うことに気づくなどかなり順調に進んでいたものの、最後の間違いが見つからず諦めてネットで答えを見てしまった。最初に見つけた間違いのすぐ左に、これまた微妙な違いが残されていたらしい。難しすぎる。

ゲーセンに入店。今日は午後6時半から閉店する午後11時半までいた。成果は14の99AJが4つ、AJが2つ、14+のSSSが2つ、SSS+が1つ、15のSSが1つ。14+のSSSはどちらも比較的最近追加・通常解禁された譜面で、数回ずつプレイしたらパッと出てくれた。15は未SSが2譜面のままずいぶん長いこと経過したので、久しぶりに頑張ったら両方伸びた。メタバースは連奏して順当に伸ばしていったが、混沌はこの日最初にプレイした回の前半がめちゃくちゃ上手くて減速トリルまでで7000点くらい残っていただけで、その後ホールドトリルなどが大爆発して998kに。さらに数回プレイして、今度は逆に前半がボロボロだったものの後半耐えて、下の画像に見える点数から数十点だけ更新してある。前半が上手くいって後半が上手くいけばSSにも乗りそうだが、今のところ前半に再現性が一切ない。

食事するため街をうろつく。一閃閣というラーメン屋は全席埋まって待ちが4人もいたので諦め、さらに歩いて油そば屋に入った。こちらは午前0時閉店で、その15分前に入店して大丈夫なのか心配になったが、店員さんに声をかけるとよさそうだったので入店。サッと平らげて、近くのドンキに入り、しかし何も買わずに出てきた。

帰宅。今日もまたスマホ通信量が増え、今2.99GBになった。多少は誤差があるだろうから、もう3GBをオーバーしているかもしれない。

ハーメルンを1作読了。「東方虚悪魔異聞（原作厨が原作キャラに憑依してしまう話）」。勘違いもので主人公の実際の戦闘能力はあまり高くないらしく、バトルは一切発生せずに会話主体で進む。小難しいことを言っているが特にヤマもオチもなく、あまり面白くなかった。

syosetu.org

シャワーを浴びて洗濯機を回し、しばらくパソコンを触っていたが、強い眠気に襲われてうっかり布団に入ったら即座に寝てしまった。午前2時だった。

01/08(土)

午後4時半起床。昨日結局干せなかった洗濯物をいまさら干した後、少しコードゴルフをして、さらに現時点で予約できる新刊ラノベをチェックしていた。今回は2月初旬までに発売されるラノベと、さらにいくつか買いそびれていたものを足して合計26冊になった。

日記を書いているうちに午後9時になり、ABC234に出た。

AtCoder Beginner Contest 234 - AtCoder

Aからよくわからない。手作業で展開していたが、あまり短くなりそうになかったので、普通に関数を定義してとりあえず通した。その後SymPyを使用して完全に展開。それはdcで書いても縮まなかったものの、f(f(t)+t)+f(f(t))を展開して最後にfを適用するコードは25Bになった。と、Aに20分ほど使ってからBへ。BはOctaveで書くのが良い。ただdispで出力すると精度が足りずWAになってしまったので、出力関数を間違えたのも合わせて2ペナついた。Cを開くとあまりにもコードゴルフしやすい問題でびっくり。bashで16Bを出しつつ、これは先に出されているだろうなと絶望していた。Dはsetのイテレータをちまちま動かす方法で書き、1200msくらいになってしまったが、通ったのでOK。Eは適当に探索。Fはdp。

Gは最初、総積ではなく総和の問題を解いていた。こちらはmaxとminに分けて寄与する回数を数えればよい。しかしコーディングを初めてから誤読に気づく。しばらく考え、とりあえず同様にmaxとminに分けてdpを考えることにした。この際配るdpを考えてしまう。更新が区間addと区間mul（ただし区間mulで一度係数が掛かった要素は以降変更されない）という形で、1点取得ができればよいが、実はこの更新は遅延セグメント木に乗せることができるようで、必死に合成関数を書いた結果、addされる要素・mulされる要素・addされてからすでにmulされた要素の3つを持つことになった。こねくりまわして何とかサンプルを合わせ、1700msで通った。残り20分もない中Hを読んで、適当に近い要素を見るようなコードを書くも間に合わない。それもコンテスト終了後に提出するとTLEしてしまった。

コードゴルフ。この部分に書いてこそいるが、この日の朝方までにあった更新を含んでいる。A問題はコンテスト中に25Bコードを2つ作ったものの、そのうち片方が-1Bされて最短を取られた。スタックをdupしてからその下の要素を取り出すd3Rは、いったんkで上の要素を退避するほうが短くなることもあるようだ。Bはコンテスト中のOctave。Cはコンテスト開始3分後に16Bが提出されており、どうあがいても負け。DはPythonの優先度付きキューで、一度取られたコードを再度取り返すことに成功した。先にキューに小さい要素を1つ入れておくことで、popと出力が同タイミングで行われるようにするとよいらしい。EはRubyで全探索。Fは制約が大きいためコンパイルする言語でないと通らず、ひとまずPyPyで書いて様子を見た。combinationは階乗を前計算せずともインクリメンタルに掛け算・割り算していく方法で必要な値が取得できる。しかし途中でmodを取らないと遅くてどうしようもなかったので、5000までの数の逆元が必要になった。毎回計算していると当然間に合わないが、しかし一つずつpow関数で求める方法でもTLEしてしまい、結局線形時間で求めるアルゴリズムを組む羽目になった。これはCrystalに写してからも同じ、というか、Crystalは整数のpow関数がないのでそうするしかない。

午前2時からSRM821に出た。

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

Easyは(i+j)\bmod 3=0,1,2のどれかを全部埋めれば達成される（実際はこれの左右反転したような形に配置した）。3種類の方法のうちどれかは自分で埋めるマス数の条件を満たすので、探して構築して出力。一瞬で見えたので慎重に確認してもそれなりに速かった。Medは二分探索で、判定は達成可能な区間を管理する。連続する区間を一つの要素にまとめると高速になると思って実装していた。また0と1はそれほどまとめられないように思えたので、bitsetで直接確認することにした。実際のところ、そのような小さいところでは区間が高々10^5/2個でイテレーション50回の判定なのだから、何もしなくてもTL 4secには十分間に合う。慎重に慎重にコーディングしていたら信じられないくらい遅くなってしまった。Hardを読み、多倍長整数として文字列を用意し開平法を実装し終わったあたりでコンテスト終了。

Medが落ちた。二分探索の上限をtargetにしていたが、これは大間違い。久しぶりに大ポカをして非常に悔しい。70位で2588→2455(-133)。

Hardの素数判定は適当に106まで用意しておけば十分じゃないかと思っていたが、実際のところ21桁の素数が登場するケースがあるらしい。long longでも扱えない整数でどうするんだと思っていたら、解説にはbashのfactorを使いましょうなど書いてあるらしく、信じられない。Hardを通している上位陣のコードを眺めてみると、JavaのBigIntegerやPythonを使っていたり、あるいは自作の多倍長整数ライブラリにミラーラビン法が実装されていたりして、本当にどうしようもない問題だった。

「最強魔法師の隠遁計画」14巻を読了。非常に満足感がある。序盤はファノン視点とアルス視点が交互に描かれて、ファノン視点では敵にいいようにやられていてつらくなり、一方アルス視点では恙なく生活している様子にモヤモヤしていたが、終盤になってついにアルスの戦闘シーンが描かれて開放感があった。まだ敵側はアルスのことを侮っているようなので、早く無双してボコボコにやっつけてほしい。やはり主人公最強は最高。

CodeChefでJanuary Long 2022 - Iが開催されている。まだLong Challengeに参加したことはないが、このコンテストはdiv.3限定なので自分はunratedらしい。そういう判定はコンテストの種類ごとのレーティングではなく全体のレーティングを見て行われるようだ。しかし物は試しということで参加を決めた。月曜日の夕方まで開催されているので、問題には言及できない。今のところ最終問題が解けていない。

https://www.codechef.com/JAN221A

Pythonの課題に取り掛かる。年末に出されたものの期限が日曜日、つまり明日までになっていた。今回はk-meansなどによるクラスタリングらしい。3次元の点集合を扱ったが、これをビジュアライズするコードがサンプルコードとして提供されていて、マウスで掴んでグリグリ動かせる形式だったのでびっくりした。以前、Google Colabでそのような表示をしようと試し、失敗した記憶がある。

午前11時半就寝。

01/09(日)

午後8時半起床。しばらく日記を書いて、午後10時からTROC #25に出た。

https://tlx.toki.id/contests/troc-25

Aは愚直。Bは達成可能な最小値と最大値を丁寧に求めた。Cは非常に難しい。まず\gcd(a,b)=1と決め打ってみる。その後aをNの周辺にしていろいろ試していると、a=2N+1のときにb=\frac{2N^2+N-1}{N+1}=2N-1と整数になることに気づいた。このときaとbは2離れた奇数なので、互いに素であり、仮定した条件を満たす。Dは縦で選んだ区間と横で選んだ区間を独立に考えてもよく、それぞれの区間で1の個数を計算すればそこから花が育つマスの数を求められる。片方を決め打つともう片方の1次関数になるので、最大と最小のどちらかを使えば十分。

Eはしばらく次数の平方分割を中心に考え込んでいた。グラフが木であることに気づき、BFS順に頂点を並べなおすと区間add・区間sumでクエリを処理できるということを思いついた。Fは貰うdpを考えるとj\lt iかつ\gcd(j,i)=1なるjから遷移してくることになる。これを高速化する。iの約数であってsquare-freeなものpを列挙し、p\mid jなるjから\mu(p)（メビウス関数）を掛けつつ貰ってくることにすると、\gcd(j,i)=1の場合のみ係数が1で他は0になってくれる。素数を篩うときに素因数を保存しておくと十分高速に行える。この高速化はAtCoderで見たことがあるが、今回は包除原理を考えていたら思いついた。しかし包除原理とは微妙に違うように見える。

Gで、今増加中か減少中かを持つdpを書くも、最後のサンプルが合わずコンテスト終了。多段階に減少する列を列挙できていないようだ。6完13位で2651→2680(+29)、highest。評価が甘くて助かっている。

Gをupsolveした。yukicoderに似た設定の問題があるようで、それの解説を流用すると、どの要素まで使ったか・どの要素まで書き換えたか・何回書き換えたかを持つdpが作れる。遷移は区間加算になるので、imos法しつつ計算していくことになる。自分はその問題をよくわからない方法で解いてしまっていたし、当時の日記を読み返しても一言「dp」とあるだけで何もわからない。少なくとも僕の方法では書き換えの回数を勘案できないように見える。

No.1378 Flattening - yukicoder

「いずれ水帝と呼ばれる少年」を読了。あまり面白くなかった。文章が説明的すぎる気がして、引き込まれない。展開も今のところテンプレ通りに思える。

夜中から朝方にかけてyukicoderのテスター作業をした。年末に依頼されたものをずっと放置していた。結構数が多かったのでいくつかはまだ残っている。時間に余裕はあるらしいが、うっかりするとすぐ忘れてしまうので、注意したい。

週記（2021/12/27-2022/01/02）

12/27(月)

先週の週記を投稿した後はパソコンの前でずっとハーメルンを読み続けていた。1作読了。「アラサーがVtuberになった話。」。非常に良かった。配信者を初めてすぐ人気が出て云々というようなお手軽な話が好きなのでよく読んでいるが、たまにはこういう苦労する話も好き。主人公の設定または振る舞いが好きになれると自分の中で評価が高くなるし、この作品では加えて嫌なリアリティを感じるストーリーもよかった。嫌な、とは展開が苦しいという意味である。

syosetu.org

午前11時就寝。午後4時過ぎ起床。少し準備してインターン先の定例会に出席。当然ながらこれが年内最後となる。先週は1on1以外何もやっていないので、それについて書くしかない。このような貧弱な進捗を言葉で嵩増しして報告するのにも慣れてしまった。働くことが生活の一部になっておらず、時間があってかつ気が向かないと手が伸びない。非常にまずい。

何とか進捗報告を終え、勉強会も終了した。ゲーセンに行こうとしたが、すでに夜遅いので今から行っても2時間しかプレイできないのか……と思うと外出する気が失せてしまった。

少しコードゴルフをした。古いJOI春合宿の問題で、ML64MBのものだった。最初は気づかずスクリプト言語で提出しようとしており、MLEが出てびっくりした。しかしアルゴリズムを変えて頑張ると通ってくれた。以前はこのMLの厳しさからC言語が最短になっていたので、それよりは当然縮む。一応C言語のほうでも縮めてある。

しばらくハーメルンを読んでいた。相変わらずVtuberもの。しかしどうにも盛り上がりがなく話の面白さが見えてこなかったので、途中で読むのを止めてしまった。一応記録しておく。

syosetu.org

午後11時半からECR120に出た。5完38位。

Dashboard - Educational Codeforces Round 120 (Rated for Div. 2) - Codeforces

Aは分割した棒を縦と横にそれぞれ1本使うことしか考えていなかったところ、サンプルで落ちた。優しい。Bは0の場所と1の場所に分けて貪欲。Cは値のコピーをどれくらい行うかを全探索した。負の数の切り捨てが出てきて、頭を使うのが面倒だったので、普通にC++の切り捨て除算をした後分母を払った不等式に違反していたらデクリメント、とした。Dは最初dpが見えてしまい、全然解けないうちに数分意識を飛ばしてしまった。正解はbitが変化した最右インデックスを決め打つことで、左にどこまで伸ばせるかは尺取りしたが、制約から愚直に探索してもよかった。Eは難しく感じた。小さいほうに寄せるか大きいほうに寄せるかの2通りだな、と考えたところで、それをどちらに寄せるか全探索することを試しに考えると、絶対値記号を外してもよい（負になるなら寄せる方向を逆にすればよいため）がわかり、各問題の寄与が求まる。

Fは解けなかった。後からTLで解法を見た。実は答えはn-3以上で、n-3のときはnを使わないことがわかるらしい。この事実をエスパーなりなんなりして、残りは構築。Zobrist hashで頑張るらしい。自分はエスパーにしても答えがn-2以上だと思い込んでいたので、ボロボロ。その後へのk氏による証明を見た。天才的。

夜中、僕の今年の週記を掘り返して読んだネット小説の記録をかき集める作業をはじめ、3時間ちょっとで完成したブログ記事を公開した。

kotatsugame.hatenablog.com

明らかに読んでいる時期とそうでない時期に分かれていたが、それと物理的な本の読書量にはあまり関係がないように見える。どちらかというと、競プロの精進をしているかしていないかに関係がありそうだ。どうやら今年は熱心に橙diffを解いていた瞬間があったようで、その週は小説一般を全然読んでいなかった。ネット小説を多く読んでいた時期は主に1月、6月、12月で、1月は東方の古代スタートものをひたすら漁り、12月はモンハン・暗殺教室の二次創作と配信者モノをひたすら漁っていた。6月は1300万文字のドヤバいもの一つにすべてを破壊されていた。

ただ羅列するだけの記事でもよかったが、自分の好みであるものはわかるようにしておこうと少しコメントをつけることにした。しかし、相変わらず1年間に渡る記録から抜き出すのは難しい。1月に読んだネット小説は正直ほぼ内容を忘れている一方、12月に読んだものは読後感も十分覚えている。無理やりバイアスをかけて好みであると表示するものを選び出した。1年も前に読んだのなら、その1シーンでも覚えていれば十分印象に残ったと考えてよいだろう。

週記を漁っている過程で、「ストリエ」というネット小説サイトが復活していることに気づいた。名前もkakuzooに変わったようだが、これは復活とは特に関係なさそうである。

この小説投稿サイトは3月初めで終了してしまうらしい。

週記（2021/02/08-2021/02/14） - kotatsugameの日記

2021/04/18追記：終了していた。

週記（2021/02/08-2021/02/14） - kotatsugameの日記

storie.jp

しばらくパソコンを触った後、布団に入って少しハーメルンを読み返し、午前10時就寝。読み返したハーメルンはこれ↓である。一口サイズにまとまりつつ強い印象を残してくれたので、実はかなり好きだったようだ。

syosetu.org

12/28(火)

午後5時半起床。昨日出ていたPythonの講義の課題のうち、今日が期限であるものだけを手短に終わらせ、外出。

まず大学に行って帰省のための学割を得る。明日から休業で、証明書自動発行機も停止してしまうらしい。午後6時過ぎに大学に到着して、自動発行機が置いてあるところの電気が消えているのを見て絶望しかけたが、入ってみるとセンサーで電気が付いてくれた。まだ何とか動いていたようで、無事学割を入手できた。そこから地下鉄に乗って街に出て、蕎麦を啜ったあとゲーセンに向かった。蕎麦屋は先週行きそびれたところ。入ってみると立ち食い席のあるチープな蕎麦屋でちょっとがっかりした。

目星をつけていた蕎麦屋は営業時間短縮で午後8時に閉店していた

週記（2021/12/20-2021/12/26） - kotatsugameの日記

ゲーセン。今日は4時間ほど。新曲の14をAJしたのと、14+の新規SSSが1つ、理論値が1つ、他多少伸びたという成果。

30回くらいプレイしたうち少なくとも15回は捨てゲーしていたらしい。序盤が最難関で、そこを抜けるころにはもうボロボロになっていることが多く、残りをプレイしきる意思が保てない。今日試しにプレイしてみたら緊張からくる最後の最後でのミスでSSSを逃したので粘着を始めたという経緯があり、最初はそこそこできていた後半も、プレイする度ボロボロになっていく。しかしそちらは譜面をしっかり確認すると思ったより単純な配置をしていたので、押す指を決めるなりリズムを把握するなりするとそこそこ安定してくれた。最後のホールド＋スライド地帯は、タップが混じる前は気合いで押して、以降は全押し。全押しのリズムは有名なおせちんこ打法だ。ありえないくらい優秀で、全押しのくせに赤Jもあんまり出ない。

最後に何か理論値を出してチュウニズム納めとしよう、と思っていろいろ触っていたが、全然出なくて苦しい時間が続いていた。しかし適当に選曲したこれが一発で理論値出たのでハッピー。緊張に強くなったか？

今進行中のチュウニズムクエスト（指定キャラクターのレベルを上げて報酬をもらうもの）では、「限界突破」というキャラクターのレベルキャップを解放する操作が必要になる。これまで、ちょっとした逆張り精神もあって頑なに行ってこなかったが、クエストを進め損ねるよりはと、今日初めて実行を決めた。しかし、黒い画面に真上の照明が組み合わさるとすごい勢いで映り込んでしまう。

帰宅してSRMにレジろうと思ったらアプレットが開けなくなっていた。証明書の確認に失敗している、というエラーが出る。PCを再起動するといけるという話を聞いて試すも効果なし。結局、Javaの設定を変えて証明書失効チェックを「チェックしない」にすると開けた。レジって、待ち時間にシャワーを浴び、午前1時過ぎからSRM820。

https://community.topcoder.com/stat?c=round_overview&rd=18986

EasyはNA,NB,NC\le 5なるギャグ制約にどれだけ速く気付けるかゲーム。自明dpを書いた後、やっぱり怖くなったので慎重に慎重に確認した。Medはiが1でi\lt j\lt Nが0になるようなiを答えられればよい。そういう条件は、i\lt j\lt NのORを取ったあとNANDにかけることでNOTを取り、iとANDを取れば表現できる。ORを取る部分はセグメント木のように行えば最大5ステップで、そこから2ステップで答えが出そろう。あとは出力だが、各桁ごとにそのbitを立てる条件がいま求めた答えいくつかのORで表現できて、こちらは最大でも9要素のORを取るだけなので、4ステップかければ十分。都合11ステップで、とりあえずステップ数は制約を満たす。実際に構築すると論理ゲートの個数も十分少なくなった。

絶対に落としたくないので、提出前にチェッカーを走らせることにした。正直ミスなんてないだろと思っていたのに、論理ゲートの間違い1つと参照する値の間違い1つが見つかってびっくりした。直して、19ケースしかないのですべて試し、全ケースに通り制約も満たしていることが確認できてから提出。600点問題なのに点数が270点くらいで、遅かったかと後悔したが、思ったより解かれていなくて安堵。残り20分はHardを眺めて終了。このEasyでどうやって間違えるんだと思いながらチャレンジフェーズを放置していたら、謎貪欲が2人いてそれぞれ落とされていた。フローを流した人もいて、いろいろいるなあという気持ちになった。

システスでも落ちず、2完10位。レートは2552→2588(+36)と、7月に記録したhighestをようやく更新できた。touristが前人未踏のレート4000を突破したらしい。SRMのtarget（レート3000）は、僕が競プロを始めたころから今に至るまでずっとライン分けとしては最高レベルの基準だった気がするのに、そこから1000も上に行くとは……。

昨日の部分の日記を書きつつ、ERC120Fを通した。各値を素因数分解し、素数の集合と見てZobrist hashを求め、それの累積XORを取ると階乗に対応するHash値が得られるということらしい。Zobrist hashを使う問題は以前にyukicoderで解いたことがあるが、今初めて「集合のHash値を高速に求められる」ことの威力を思い知った気がする。……と言いつつyukicoderの問題を見てみたら、こちらも素数にhash値を割り振ったZobrist hashだった。

Submission #140962390 - Codeforces

No.1746 Sqrt Integer Segments - yukicoder

今日の分まで日記を書き上げ、午前6時半就寝。

12/29(水)

午前11時起床。

二度寝するか迷いつつハーメルンの更新を1つ読んだ。後書きで作者が他に動画作成も行っているということが書かれており、気になったのでYouTubeチャンネルに飛んでみると、ぽいんと氏だった。The Unusual SkyBlockのRTA動画とボイロ実況をいくつか視聴したことがある。そちらの方面ではかなり有名な人だと感じているので、まさかハーメルンに投稿までしているとは、とびっくり。

syosetu.org

帰省する。持ち物としてはノートPCとラノベが1冊あれば十分だろう。他に仙台の部屋でしか行えないことと言えば、インターン関連の作業が考えられる。特に、月ごとの作業時間を毎月まとめて提出しているので、ササッとメールを作成して送信しておいた。

仙台駅に向かい、まずみどりの窓口で学割を適用した切符を購入する。みどりの窓口は待機列がガラス戸からはみ出すくらい混んでいて、30分くらい並ぶことになった。次の新幹線まで十数分あるようだったので、立ち食い蕎麦屋に入ってカレーライスを食べ、出発。仙台始発ではないが、隣に人がいない席に問題なく座れた。

進むにしたがって微妙に人が増えてきたが、結局隣に人が座ってくることはなかった。大宮で降りる。今日は新幹線の時刻表を調べずに来たため、次に乗る新幹線をこのタイミングで探すことになる。どうやら50分程度の乗り換え待ちが発生するようだったので、ゲーセンに行ってチュウニズムを2クレプレイした。これが本当のゲーセン納めになるだろう。成果はなし。

駅に戻ってみると、ダイヤが微妙に乱れており、前後の新幹線が数分遅れになっていた。今日が帰省ラッシュのピークらしく、自由席車両にできた列が長すぎるということで、指定席車両のデッキや通路に押し込まれるらしい。ギチギチになって待つことしばらく、新幹線がやってきて、見事通路の真ん中で仁王立ちすることになった。

新幹線に乗っている間ラノベを読んでいて、1冊読了。「公務員、中田忍の悪徳」。ラノベらしからぬラノベという言及を見聞きした覚えがある。作者もラノベと一般文芸の中間を目指して書いたらしいが、そのあたりの機微はわからない。とは言え面白かったのは確か。現実主義的な考え方をするキャラクターたちと、非現実もいいところな異世界エルフの組み合わせが、もう悪い予感しかしなくて面白い。言葉の通じないエルフとなんとかコミュニケーションを取ろうとする過程もやたら理論的に、丁寧に描かれており、納得感がある。

移動中読む用のラノベを1冊しか持ってこなかったため、残り1時間強はハーメルンを読みながら過ごした。結局黒部宇奈月温泉駅で降りるまで自由席は埋まっていたので、ずっと立ちっぱなしだった。黒部でもちょっと見ないくらいの人が降りたので、これが帰省ラッシュか……と感心。Uターンラッシュは是が非でも避けるようにしたい。

親の車で実家に帰る。途中本屋に寄ってもらい、ラノベを7冊購入した。帰宅し、夕食を摂った後、思ったより疲れていたので深夜のコンテストに備えて一眠りすることにした。午後9時過ぎから午前0時ちょっと前まで寝ていた。入浴し、午前0時半からGood Bye 2021。

Dashboard - Good Bye 2021: 2022 is NEAR - Codeforces

実家の回線が貧弱すぎて開始から数分問題を見られなかった。慌ててテザリングをし、コンテスト開始。Aはよい。Bで1ペナつけた。狭義単調減少なprefixを取るべきと思っていたが、広義単調減少でよい。ただしs_1=s_2の場合の答えはs_1s_1になる。Cは短い区間を見て式変形してみると等差数列になっている必要があった。少なくとも2点は等差数列にそのまま乗せられるので、それを全探索すればよい。

Dは難しかった。実家dpで解いた。各インデックスに対し、和に関する条件を満たせる最も左のインデックスを求め、区間maxで取得して1点更新することになる。iに対し和に関する条件を満たせる最も左のインデックスを求めるときは、a_iやa_{i-1}を含む幅2、3の区間についてチェックした後、それより左になるようだったら以前に計算したものを使った。幅4以上の区間は幅2以上の区間の組み合わせで書けるからだ。Eはどのインデックスで大小を決定するかを全探索できる。操作のコストを計算するためにBITを使ったので、計算量は\sigma=26としてO(\sigma n\log n)になるはずだが、爆速で通ってくれた。

Fはよくわからない。いろいろ試しているうちに、条件が「3つの辺に塗られた色の番号の和が3の倍数」と表せることに気づき、その条件を全部並べた\bmod 3の連立方程式を掃き出し法で解いたら通った。連立方程式は最大257列で、行はn=23の完全グラフのとき1771行になるようだが、これも爆速で通った。掃き出す際、非ゼロ要素だけ抜き出して計算するという高速化を入れていたとはいえ、効果のほどは不明。そもそも非ゼロ要素だけ持つということも考えたものの、掃き出す過程でどんどん増えて無駄になりそうだと感じて止めた。

残り30分弱で、より多く解かれていたHに進んだ。しばらく考えているうちに、どうにも見覚えがあることに気づいた。いつだったかのOpenCupに似たような問題があったはず。チームのSlackなどをひっくり返して発見した。その日の日記に解法についても書かれていたので、それを真似して今回の問題に合うように直そうとするも、サンプルが全然合わない。そのままコンテストが終了した。

OpenCup-Iについて。

週記（2021/11/29-2021/12/05） - kotatsugameの日記

コンテスト後に、使っていたサンプルファイルが違う問題のものであったことに気づいた。正しいものに直して少しコードに手を加えると、見事に出力が一致した。投げると当然のようにAC。ペアのXORの大小を考える問題は、今回使ったような再帰関数の定義を思いつくまでが本質に見える。1ヶ月以内に同様の問題が出ていれば、ボス問なのにたくさん解かれるというのも納得だ。

布団に入ってラノベを1冊読了。「日本語が話せないロシア人美少女転入生が頼れるのは、多言語マスターの俺1人」2巻。1巻はまさにざまぁ系という感じで爽快な描写が大量に盛り込まれていたが、2巻は一転、1巻で解決しなかった問題に注力されており、読んでいて気持ちいいというよりは辛い部分が多かった。どこまで引っ張るんだろうなと思っていたら、この2巻でちゃんと解決してくれたのでハッピー。かと言ってシリーズ完結というわけでもないようなので、嬉しい。

その後もしばらくハーメルンを読んでいて、朝ご飯を食べてから午前9時過ぎ就寝。

12/30(木)

午後8時過ぎ起床。

夕食を摂った後、満を持して夏に碧黴さんから頂いた日本酒を開けることにした。赤達成のお祝いのもので、家族と一緒に飲んでということだったが、タイミングを外し続けてこのような時期まで持ち越されてしまっていた。まだ赤で本当によかった。

下世話だが値段を調べてみると、かなり高いようでびっくり。正直日本酒の味はわからない。父曰くちょっと甘口で口当たりがよいという話だ。そういうものかと思いながら飲んでいたら、確かにスイスイ飲めてしまうようで、もったいなくも1時間と少しで飲み干してしまった。すっかり酔っ払って倒れ込み、ラノベを読もうと開いたが数ページも進まないうちに寝落ちしたようだった。午前0時くらいのこと。

午前3時くらいに意識を取り戻した。とりあえず水分を補給し、またラノベを読み続けた。

午前6時半くらいに1冊読了。「お姉ちゃんといっしょに異世界を支配して幸せな家庭を築きましょ？」。あらすじに「異世界最強の支配者」と書いてあって、そういうファンタジー系無双モノを期待して読んだが、大ハズレだった。現実世界における都市伝説の話。話自体はいろいろ伏線が張られていて圧倒されたが、期待していたものではなかったという一点で自分の中での評価はあまり高くない。実際のところ、この話をあらすじでちゃんとまとめると面白さが失われる気がするので、そうやって内容と乖離してしまうのも仕方ないことではあるか。

また1冊読み始めて、朝ご飯を挟みつつ午前10時半に読了。「お見合いしたくなかったので、無理難題な条件をつけたら同級生が来た件について」3巻。両片想いがくっつく巻で非常に良かった。エピローグで、ヒロインが家族に対して自分の意見を述べるまでに6ページくらい葛藤があり、もどかしい思いをしたが、幼少期から抑圧されていたという設定を鑑みればリアルな間だったのかもしれない。ぜひ幸せになってほしい。後書きで、このシリーズがシンデレラモチーフであるということが明かされていた。以前このようなこと↓を書いたので、的中したとも捉えられる。

どうやら身分差のある恋を描いているらしい。そういうテーマは童話などではよく聞く

週記（2021/09/20-2021/09/26） - kotatsugameの日記

昨日のCFのレート更新が来ていた。結局6完55位で2887→2906(+19)。なんとか2900に乗せての年越しとなる。

その後ハーメルンを読み始め、午後2時前に就寝。微妙な頭痛があり、二日酔いが怖い。

12/31(金)

消えた。

01/01(土)

12/31 午後11時起床。頭痛が消え、体調は良好。年が変わりそうになっていたので、急いで今年のレーティング変動などをツイートした。去年もツイートしたもの。

年越しそばを食べて一息つきつつatgolferを確認すると、午後9時過ぎにPAST9の過去問が公開されていたことに気づいた。慌てて解き進めている間に年が明け、午前3時前に全問ACできた。代わりに、毎年年明けの瞬間にツイートを行っていたが、失敗した。

第九回 アルゴリズム実技検定 - AtCoder

Aは面倒。Bも面倒に見えるが、50円玉を使うかと5円玉を使うかさえチェックすればいいので、そこまででもない。Cは普通にやれば簡単だが、コードゴルフをするとなると出力順がちょっと面倒になる。Dはやるだけ。Eは丁寧に条件を書く。Fは頑張る。Gはびっくり制約で、愚直を通そうとしているらしい。Hは一見よくわからないものの、同じになる文字をわざわざ取る必要がないことを考えると、LCSのdpと同じ形式になる。Iは座圧してdijkstra。

Jは面倒。現在の座標(x,y)が元の座標(x_xx+x_yy+x_c,y_xx+y_yy+y_c)に対応するという情報の持ち方をして、気合いで更新していく。更新するときは2変数関数の合成っぽくなるので更に面倒。Kはやるだけ。Lはインデックスを上手く足し込むと狭義単調減少だったのが広義単調減少になるので、座圧してセグメント木に乗せる。Mは全然わからなかったので、クエリ平方分割して毎回平方分割をやり直し、バケットサイズガチャを回したら通った。バケットサイズ2000、つまりクエリ2000回ごとに文字列をソートし直して2000個ごとのブロックに分けると2500msくらいになった。

Nは共通部分もまた凸多角形になるので、境界に乗る点をかき集めて凸包を取った。つまり、Sの頂点であってTの内部にあるもの、Tの頂点であってSの内部にあるもの、SとTの交点、の3種類。しかし全然合わず、しばらくEPSを弄ったりしていたが、問題は線分の交点を求める部分にあった。平行で重なる2直線の交点を求めようとしてとんでもない値が出ていたらしい。自分のライブラリだと、重なる場合も交差すると判定してしまうので、平行は別に判定して弾かなければならなかった。Oは頻度配列を作って式を整理すると、片方を反転した畳み込みで計算できる形になる。

Lのインデックスを足した後はLISのような形になっているので、座圧の必要はなかったらしい。Mのwriter想定解は平衝二分探索木で、いよいよ出題されるようになったかと驚愕。ただしtrie木でも解けるようだ。

コードゴルフ。Aは速度とかではなく素直に負け。Bはdcで、負の数の割り算がC言語スタイルなので、B-Aの代わりにA-Bについて計算しても一箇所+を-にするだけで辻褄を合わせられる。rの必要がなくなり-1B。Cはbashで、sortの際に-sオプションでstableなソートをすると上手く行く。DはRubyだが、こちらはもともとstableなソートらしく、わざわざインデックスを比較する必要がないという更新で取られた。Eは適当にRuby。Hは制約が大きいので、Crystalで通しておいた。K、LもRuby。FGIJMNOは手付かず。

一段落付いたので、読書記録を整理した。去年は物理本を全然読めなかった。

また今年分の読書記録や買った本の記録の記事を作り、その後朝ご飯の時間まで溜めていた日記を書いていた。

kotatsugame.hatenablog.com

kotatsugame.hatenablog.com

毎年この時期は微妙な生活リズムの狂い方をしていて、ここ数年朝ご飯を家族と一緒に食べられた記憶がなかったが、今日は成功した。お雑煮とおせちを食べ、僕が寝る前にということで早めに初詣に行った。おみくじを引いたら大吉だった。

帰ってくる頃には眠気がかなり強くなっていた。布団に入ってラノベを開くも、うつらうつらしてまともに読み進められたものではない。01/03の夜中にあるHello 2022に向けて生活リズムを整えるため、頑張って午後5時くらいまで起きて、寝た。

01/02(日)

午前0時半起床。もうちょっと寝たいのに眠れない。

ハーメルンを1作読了した。「【完結】『金』の棋譜」。りゅうおうのおしごと！の二次創作で、短め。しかし設定に満足感があり、大きなイベントを描いてサッと完結させてくれているので良かった。

syosetu.org

しばらくハーメルンの更新を漁ったあと、「輝きたくて」という作品を最初から読み返し始めた。自分のハーメルン遍歴の中ではかなり初期に位置するVtuberモノなので、他にいろいろ読んだ現在の視点から再読すると何か新しい読み方ができそうだと思ったのだ。あとはまあ、単純に好きだし、ギリギリ手軽と言えなくもないサイズ。

syosetu.org

3時間半ほどかけて最後まで読み切った。やはり面白い。異性同士のコラボは燃えがちというテーマで2作品ほど読んだが、こちらではあまり触れられていない。しかし、より一般に「炎上」そのものはかなり作品の根幹に近いと感じた。また今回も終わり方が唐突であるという印象を抱いた。もうちょっと分析すれば、クライマックスの山場と最終話の間になんの変哲もない日常回が挟まっているのが原因と考えられる。

朝ご飯を食べ、別のハーメルンを少し読んで、午前9時半就寝。午後3時半起床。

紅白歌合戦の録画があったので、まふまふさんが出演しているところだけ観た。しばらくコードゴルフをして、夕食。今日は近所の寿司屋のテイクアウトだった。

入浴など済ませた後、新春TechFUL Coding Battle 2022を解いた。これについては今週どころか来週末にもまだ終了していないので、各問題の感想は再来週の週記に書く予定となる。とりあえず現在visibleな部分は理論値で通っている。

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

ラノベを1作読了。「D級冒険者の俺、なぜか勇者パーティーに勧誘されたあげく、王女につきまとわれてる」3巻。相変わらず軽快な文章が心地よかった。しかし、今巻は特に印象に残らなかったので、自分が何を思って「今年読んだ本のまとめ」で印象に残った本として挙げたのかがよくわからなくなった。主人公の無双シーンが足りなかったのだろうか？それならば、後書きによれば4巻はかなりいい感じになりそうだ。

夜中までずっとコードゴルフをしていた。PAST9がバカスカ取られていて厳しい。H問題は想定解のO(|S||T|)でもRubyやPythonではTLEしてしまう。昨日Crystalで書いて、今日取られてしまったので絶望していたが、Octaveの行列演算が相性がよく、1500msくらいで通ってくれた。dp配列を1次元にして、2次元目はループだけにして気合で遷移を書くのはCrystalから変わらず。しかし、遷移中に何をやっているかについての理解が深まったため、全体へ一様に加算したり累積maxを取ったりする操作で書き直せて、Octaveのコードはそれなりに短くなってくれた。

せっかく生活リズムをぐるぐる回したのに、回しすぎてまた午前5時に寝る準備を始める状態になってしまった。本当にまずい。宵っ張りな性分が一生直らない。

買った本の記録（2022）

kotatsugame.hatenablog.com

1月

クラスで2番目に可愛い女の子と友だちになった
エプロンの似合うギャルなんてズルい
神狩1〈上〉
最強魔法師の隠遁計画14
転生したら皇帝でした1
美少女エルフ（大嘘）が救う！弱小領地
恋は双子で割り切れない3
前世は剣帝。今生クズ王子3
お隣の天使様にいつの間にか駄目人間にされていた件5.5
友達の妹が俺にだけウザい9
ひきこまり吸血姫の悶々7
君は本当に僕の天使なのか2
青のアウトライン
辺境都市の育成者5
VTuberなんだが配信切り忘れたら伝説になってた3
デート・ア・ライブ アナザールート
純白令嬢の諜報員

今年読んだネット小説のまとめ

配信者

逆行要素あり。大好き。

俺ガイルの二次創作。

好き。

なかなかエモい。好き。

支配者

歴史を眺める要素もある。大好き。

好き。

上の「竜に生まれまして」の外伝。

おそらく今年一年で一番好きだったもの。設定と展開がすべて好みだった。ただめちゃくちゃ長いのでところどころの盛り上がりが希釈されている感じがする。

いわずと知れた超有名作。間違いない。好き。

経済

タイトル通り逆行もの。

東方Project二次創作

好き。

文章に難があるが、設定と展開が非常に好み。大好き。

「東方拾憶録【完結】」の続編。

好き。

古代スタート。記事公開時点で非公開設定。

好き。

「名探偵コナン」の二次創作。一口サイズでかなりエモい。大好き。

「東方古神録」の続編。

非常にエモい。大好き。

モンスターハンター二次創作

リオレウスに転生。

古龍と婚姻。

古龍に転生。好き。

「僕のヒーローアカデミア」の二次創作。

「ONE PIECE」の二次創作で主人公一味が古龍。

「僕のヒーローアカデミア」の二次創作。

「僕のヒーローアカデミア」の二次創作。好き。

「魔法科高校の劣等生」の二次創作。

暗殺教室二次創作

渚がTSしつつ逆行転生。好き。

好き。

「銃と私、あるいは触手と暗殺」の番外編。

「ゴルゴ13」とのクロスオーバー。

その他オリジナル

ゲーム運営のために合同会社を経営する話。かなり面白い。大好き。

日常の謎。

その他二次創作

「ハリーポッター」の二次創作。主人公は幼女戦記から。

「アイドルマスター」の二次創作。

「現代社会で乙女ゲームの悪役令嬢をするのはちょっと大変」の二次創作。

「ハリー・ポッター」の二次創作。主人公は霧雨魔理沙。

「ダンジョンに出会いを求めるのは間違っているだろうか」の二次創作。神様に転生・古代スタート。好き。

「デート・ア・ライブ」の二次創作。好き。

18禁

ストーリーも面白い。好き。

好き。

好き。

好き。

好き。

最新話に追いつく前に読むのが止まったもの

逆行転生・内政干渉。

「影の勇者の再冒険　～～Re-Tale of the Brave～～」の過去編。1回目と2回目の異世界転移の間の話。

俺ガイルの二次創作。

東方の二次創作。

東方の二次創作。

東方の二次創作。

東方の二次創作。

東方の二次創作。

東方の二次創作。

東方の二次創作。「阿礼狂いに生まれた少年のお話」の続編。

「ハリー・ポッター」の二次創作。

「デート・ア・ライブ」の二次創作。

週記（2021/12/20-2021/12/26）

12/20(月)

先週の週記には、12/20の昼前までのことを書いた。その後のことは今日のこの部分に書こう。

まず、別のハーメルンを読み始めた。これも暗殺教室の二次創作である。かなり面白く熱中して読んでいるうちに学食が閉まりそうになったので、急いで昼食を摂りに出かけ、帰りがけに注文していた本を受け取った。そのまま夕方くらいまで読み続けた後、週記を仕上げているうちにインターン先の定例会が始まった。

今週の進捗報告はヘナヘナ。実は先週の定例会がなくなっていたので、2週間分の進捗を報告できるはずが、もう本当に無でどうしようもない。しかもろくすっぽ内容を練れていなかったので、今週のどこかで久しぶりに1on1を入れてもらい、そこでもうちょっと詳しくお話できればとか何とか言って報告を終えた。

勉強会まで終わってから週記を投稿した。と、直後に特にFFでもなんでもない人にRTされた。不思議に思ってアカウントを見に行くと、先週読んだなろう小説「鷹は瑞穂の空を飛ぶ～プラスチックの専門家が華族の娘に転生したので日本は化学立国になります～」の作者の方だった。どうやって僕のブログ記事に記載があると知ったのだろうか。ツイートは容易に作者に届きうると考えて感想はポジティブなものしか書かないようにしているが、週記には、これを探し当てるほど熱心にエゴサしているならば覚悟もできているだろうと考え、かなりストレートな自分本位の感想を書いている。しかし実際に探し当てられたことを知って結構びっくりした。せっかくなのでリンクをもう一度貼っておこう。

https://ncode.syosetu.com/n1453gs/

久しぶりにがっつりコードゴルフをした。先週、1桁の整数を文字列から数値に直す際にto_iではなくhexを使うという短縮を行ったが、1桁でなくてもhexを使用できる可能性がある。数値の和や差などは保たれないものの、大小関係や等号だけは保たれるため、それしか使わないようなコードは縮む可能性がある。to_iという文字列を含む最短コードをすべて調べ上げて短縮できそうなものを探したところ、結構見つかった。特に、ほぼLISを求めるだけのような問題が7件見つかり、すべて縮んだ。以下はその一例である。

atcoder.jp

to_iを含む最短コード（正確には、僕がAC済みの問題の最短コードすべてのうち、to_iを含む行）は365件存在した。1件1件チェックしている間あまりの眠気で意識を失いそうになっていたが、何とか耐えきって提出までを済ませ、布団に入って寝た。午後9時だった。

12/21(火)

午前3時に起きてしまい、1時間ほどハーメルンを読んでいたが、生活リズムを整えるために強い意志で二度寝した。午前9時起床。夢を見た。

11/20に行われたABC228の賞金でアマギフが来ていた。10000円だった。19位だったから、おそらく7位～10位の学生応援賞に引っかかったのだろう。

今日もコードゴルフを始めた。最近やたら活動的な人がいて、atgolferがその人の更新で埋まっている。しかしいくつか見た感じ、どれも直前の最短コードの改行を1Bにしたり軽微な短縮をしているだけに見え、そのような自明な更新が残っている問題はたいていPythonかC++が最短コードになっているので、言語を変えるだけで縮む。過去何回も言っていることだが、AtCoderにおけるコードゴルフでPythonを使うには使うだけの理由が必要で、そうでない問題に対してはPythonはまったくもって無力である。昔はmod付きpowが強かったものの、言語アップデートでRubyにその利点を奪われ、最近はもっぱらheapqとnetworkxを使うための言語となっている。そういえばscipyというのもあったか。networkxとどちらが短くなるのだろうか、試す元気がないので試していない。

しばらくやっているうちにclimpetさんが僕の縮めたコードをさらに縮め、その過程でPerlに新手が出た。十分大きな値として1e9を使う代わりに\0、あるいは何らかのオブジェクトのリファレンスを使うもの。出力するとSCALAR(0x80007eed8)みたいな文字列が出るが、これは見やすく表示しているだけで、内部的に数値演算を行うと内側のアドレスだけが取り出されて、この場合だと34360258264になるようだ。これが効く問題もいくつかあったので、探して縮めた。

atcoder.jp

今日も学食が閉まりそうになったので滑り込みで昼食を摂り、床屋に寄って帰宅した。また少しコードゴルフをした。

atcoder.jp

まず、この問題は現在の計算機性能だと\Theta(N^2)が通る。その元で、列に挿入する方法と列から削除する方法があり、後者がかなり短くなった。1から順番に数列でその値のインデックスを探し、左右どちらが短いかを答えに足して、値を削除する。N回の繰り返しでfindとeraseに毎回O(N)かけるというアルゴリズムだ。挿入の方法だとソートだのが必要になってくるが、こちらではその必要はない。ただやたらと時間がかかるようで、RubyではTLEし、Crystalを持ち出してやっと1600msになった。少し書き方を変えるとまたTLEしてしまい辛かった。挿入の方法ではRubyで500msくらいと爆速になる。

今日はゲーセンに行く。午後5時くらいに到着して、途中夕食を挟み午後10時くらいまで遊んだ。成果としては、14+（特に旧13+）のSSS+が1譜面、14+のSSSが1譜面、14の99AJが5譜面、理論値が2譜面。A Site De La Rueは2回ある速い折り返しフリックのあたりでミスが出るので敬遠していたが、YouTubeの手元動画のコメント欄だったかで原因を知り、今日は1回も出なかった。肝心の原因というのは、フリック後の黄タップに判定が吸われていることで、対策としては思っているより速く擦ることだった。また、数えていなかったが理論値数はすでに2桁に突入していたようだ。

午後9時前にいったん離脱して夕食。目星をつけていた蕎麦屋は営業時間短縮で午後8時に閉店していたため、近くの家系ラーメンの店に入ったが、一口目で後悔した。ありえないくらい濃い。この店にはもう二度と来ないだろうし、より一般に家系の店では薄めを頼むようにしたいと強く思った。家系ラーメン特有の、ラーメンスープをすべて飲み干すことで特典が得られる「まくり」なる制度は頭がおかしいと思う。

午後10時、眠くて精度が取れなくなってきたので帰宅。

「時々ボソッとロシア語でデレる隣のアーリャさん」の重版ツイートが流れてきた。今年出たのにもう14刷らしい。「今年一番売れたラノベ」という3巻帯にあった称号は伊達ではないということか。こうして見ると、1巻の初版を逃したのが悔やまれる。

しばらくコードゴルフをして、午後1時に就寝。

12/22(水)

午前9時半起床。明日の昼に1on1の予定を入れてもらった。そのまま布団でハーメルンを読み続けていた。

途中少し起きて、昨日まで縮めてきた問題がまた更新されているのを見つけ、取り返していたが、これも1時間程度で切り上げてまた布団に戻る。学食にも行けず延々ハーメルンを読み続けていた。

ふとTLを見たらチュウニズム公式からアンケートが流れてきたので、答えた。大型アップデートでエアークラッシュという紫色のド派手なノーツが追加されたのだが、これの視認性が最悪なのでやめてほしいとの想いを込めた。

午後6時半、読了。「【完結】銃と私、あるいは触手と暗殺」。月曜日から読み始めた暗殺教室の二次創作である。非常に良かった。

syosetu.org

オリ主が元傭兵の女子中学生ということで、鍛え上げた戦闘能力で無双するのかと思っていたら、もちろん要所要所でそういう話も挟まれつつ、思いのほかがっつり人情ものだった。原作との絡め方もよい。基本的に起こる出来事はすべて原作準拠で、その中で大胆に確保されたオリ主の出番にも不思議と納得感がある。ネタバレになるが、ラストの殺せんせー生存エンドも非常に満足できた。原作もかなり綺麗に終わった記憶があるけれど、こういう原作の展開を打ち砕くIFは二次創作でしか楽しめないものだろう。エピローグも非常に健康に良かった。原作でもその後の話として1ページ漫画が4本くらい公開されていた記憶があるが、常々もっと読みたいと思っていたのだ。まあこちらでも1話だけだったものの、それでも満たされた気分になった。

ちょっと前にTwitterで、原作を知らない二次創作を読むのが躊躇われるという話を見聞きした。この作品では原作と同じ展開の箇所はほぼカットされていたため、原作の出来事を知らないと辛いものがあるように感じられた。しかしどうだろう、それは自分が原作を知っているからこそ抱いた感想ではないか？ちょっと前に僕のヒーローアカデミアの二次創作をいろいろ読んだときは、原作を知らないことでの疎外感を感じたりはしなかった記憶がある。知らない作品の二次創作を読んだときは、それなりの読み方があるのだろう。

先にツイートを引用したように、番外編があるらしい。見てみたら14話しかなくちょっとがっかりしたが、読み始めた。しかし午後7時半ごろに寝落ちした。

12/23(木)

午前0時半起床。

TCB43のランキング発表メールが来ていて、今回賞金を得られなかったことが確定した。TCB31から出場して、これまで実に12回連続で賞金を得ていたが、そのStreakが切れてしまった。全完を逃したのも初めて。

火曜日にあったPythonの講義の課題をこなした。実は毎週、水曜日までに講義スライドのキーワードを考えるという課題も出ていたのだが、うっかり忘れて木曜日になってしまった。幸いまだ受け付けているような様子だったのでしれっと投稿しておいた。今日の課題は主成分分析とやら。理論的な裏付けなど何もないしきい値を利用する、それっぽいコードを錬成して提出しておいた。

今日もコードゴルフをする。ハーメルンを読みつつ朝までかなり長いことやっていた。

atcoder.jp

文字列のペアとして一致判定をしたい。最初はローリングハッシュを使おうかと思っていたところ、直接文字列を用意して、それを要素にした配列のhashを取ることでも行えた。なんとなくスマートで気に入っていたのだが、その後適当な区切り文字を加えて連結したものを使ったり、果てには配列をそのまま連想配列に入れても間に合ってしまった。初期のコードではTLEしていたはずなのに、変形の過程で実行時間的にも改善されていたようだ。

朝方、昨日読了したハーメルンの番外編も読了した。「銃と私、あるいは放課後の時間」。どうやらもともと本編の合間にあったものを抜き出してまとめたようで、本編エピローグの余韻を台無しにしてしまうかと思ったが、おおむね日常回で純粋に楽しめた。ラスト数話は本編後の話で、これまた非常に健康に良かった。

syosetu.org

昨日の時点では生活リズムが崩れていないと信じて昼に1on1の予定を入れたのに、今日すでにこのような生活リズムになってしまった。ひと眠りする前に準備をしようと思って、1時間くらパワポをいじり、午前9時半に布団に入った。しかしさすがに今から寝て起きられる自信がなかったため、また別のハーメルンを1作読了した。「BEST ASSASSIN」。

syosetu.org

暗殺教室とゴルゴ13のクロスオーバー。ゴルゴが殺せんせーの暗殺依頼を受けるというストーリーだ。舞台こそ暗殺教室の世界でありつつ、文章や展開はゴルゴ13のそれだった。正直、展開は暗殺教室好きにとって辛いものだったが、非常によく練られていると感じた。

ちょうど読み終わったあたりで予定の時間になり、1on1。頑張って準備したおかげかかなりいい感じの報告をできたし、これからやることも明確化した実り多いものだった。実は自分の体感のみをもとに話しており、同じ業務に携わるほかの人の意見も聞いてみたいなと考えたので、それに向けて少し考え事をしていたら、今日も学食が閉まりかけたので急いで昼食を摂りに行った。

帰宅して布団に入り、またハーメルンを読み始めたが、午後3時半ごろ寝落ち。

12/24(金)

12/23の午後11時半に起床。思ったよりがっつり寝てしまった。HUPC2021の参加登録が始まっていたので、登録しておいた。

connpass.com

布団でハーメルンを読み続け、1作読了。「仁義ある暗殺」。これも暗殺教室の二次創作である。オリ主のヤクザ口調が過度に感じられてちょっと読みづらい。別のオリジナルキャラが登場するいい感じのところでエタっているのも嬉しくなかった。

syosetu.org

暗殺教室の二次創作は、もうビビッとくるものがなくなってしまった。ハーメルンを漁るのはこれくらいにしておこう。

今日もしばらくコードゴルフをして、午前5時くらいから日記を書き始めた。生活リズムがボロボロのため今週は丸々溜め込んでいて、ラノベを読んだりしながら書いていたらここまで書くのに6時間くらいかかってしまった。TCB43の話を書いている途中、ふと思い出して10問目の解説を探したら上がっていた。

Simple infinite series.pdf - Google ドライブ

へのk氏から「高度知識ではない」という助言をもらったが、コンテスト中に考えているうちに自力では解けないと屈服してしまったので、解説が公開されたら読むようにしたい。

週記（2021/12/13-2021/12/19） - kotatsugameの日記

絶対に形式的べき級数だと思っていたのに、全然違って愕然。高度知識ではなかったのは確かだが、まさかこのような方針だったとは……。ただこの式変形が自力でできるかというとそうでもない気がして、結局どうしようもない。

ハーメルンを1つ読了。「TS動画配信者の飼い猫♂になった件」。なんとなくHIKAKINとまるお・もふこっぽさを感じた。あくまでも猫として動いているので、設定に忠実ではあるが飼い主と通じ合えないもどかしさを感じる。

syosetu.org

学食に行って昼食を摂り、注文していた本を受け取って帰宅。先月末に12月に発売される本のうち購入を考えているものを軒並み予約したが、これですべて受け取ったことになる。次は1月発売のものを探そう、と思ってラノベの販売予定を確認していたら、12月発売のものもいくつか見逃していたようで愕然とした。改めてメモしておく。年末年始は帰省する予定のため、まだ予約はせず、いくつかは帰省先で購入して読むことにしよう。

12月発売のラノベをメインに23冊予約した。

週記（2021/11/22-2021/11/28） - kotatsugameの日記

少しコードゴルフをした。RubyでYesやNoなどの確定した文字列を出力する際は、クオートするのではなくシンボルとして:Yesなどと書くのが短いが、いずれにせよpメソッドではなくputsメソッドを使う必要がある。なぜかというと、pでシンボルを出力するとコロンまで表示されてしまうからだ。では、RubyをVimから呼び出す場合はどうだろうか？今日、出力されたコロンをVimのほうから消してもよいことに気づいた。このことを使うと、これまでputsだった部分をpに置き換え、代わりに出力直後に1文字削除のxコマンドを使うことになるので、都合-2Bできる。3つくらい適用できる問題があったため、縮めておいた。

午後1時過ぎに布団に入ってハーメルンを読みふけり、午後3時にさすがにまずいと思って就寝。といっても昼寝の扱いである。

午後6時からのXmasコンテストに向けて目覚ましをかけていたが、起きられず、午後7時過ぎに意識を取り戻した。このコンテストはまともに戦うことをハナから諦めているので、こうやって気の抜けた行動をしてしまう。

Xmas Contest 2021 - AtCoder

とりあえず布団から順位表を確認して、Bが通されているのを見て通した。頂点数と辺数が固定なので、できるだけ連結成分数を減らすためには森が作れればよい。実際サンプルのように配置するとループが発生しないので、この場合の連結成分数は(N+1)(M+1)-NMとなる。逆に連結成分数を増やすにはループをたくさん作ればよく、これまたサンプルのように配置するとよい。2行目、4行目、6行目……には\lfloor M/2\rfloor個ずつループの中心があり、3行目、5行目、7行目……には\lfloor(M-1)/2\rfloor個ずつあるため、適切に掛け算してループの総数を出し、最初の答えに足すと通る。

コードゴルフもする。(N+1)(M+1)-NM=N+M+1はよい。次にループの個数だが、N,Mの偶奇で場合分けして慎重に考えると、足す値が\lfloor(NM-N-M+2)/2\rfloorであるとわかった。これにN+M+1を足すと\lfloor(NM+N+M+4)/2\rfloorになるため、割ってから足すのではなく足してから割ることにすればコードが短くなり、結局dcで19Bを作れた。

次にF問題が通されていたので見て、頭だけではどう頑張っても無理そうだったので部分点を取ってみたら、結果がACになるようでびっくりした。Textで5Bであった。残りの問題も一通り眺めたが、何もわからなかったので諦め、しかし再度眠れるほどの眠気もなかったためずっとハーメルンを読んでいた。

1作読了。「ダクファン帰りのエルフさんは配信がしたい」。かなり面白かった。ハイスペック主人公が配信者になって人気を得るやつが好き。魔王とかの設定に絡んでちょっと不穏な話もあったが、今のところはのほほんと進んでいる。

syosetu.org

午後10時ちょっと前に起きだす。コンテスト終了を待って最短コードを確認すると、B問題は取れていたが、F問題は当然コンテスト開始すぐの5Bコードが最短になっていた。またハーメルンを読み続けて、午後11時半からCGR18。

Dashboard - Codeforces Global Round 18 - Codeforces

Aは操作回数を聞かないのが良心的。Bは立ち続けるbitを全探索するのはすぐわかったものの、算数パートに時間をかけてしまった。丁寧に実装していたら8分くらいかかった。Cは同じ位置同士でXORを取って、0と1どちらかを全部1回ずつ使い、他は使わないことになる。操作回数の偶奇が合っているかと、これでちゃんと使いきれるか、つまり元の文字列で0と1がそれぞれ半々になっているかを確認すればよい。正確には、XORを取ると各位置を使う回数の偶奇がわかるのだが、同じところを2回触っても操作回数が増えるだけで0と1の個数を変えたりはできない（適当に実験すると予想がつく）ため、無意味ということ。

Dは全部パリティにしたあと分かっている情報を重み01の辺にして、奇数長の閉路がなければよい。なかなか面白かった。Eは赤く塗る頂点数を全探索できる。毎回、各葉に対してそれを赤く塗ったときに青く塗れなくなる頂点数が最も多いものを選べばよいが、これはだいたい祖先の個数になるため、更新することを考えてもdfsで最初に一気に数えることができる。あとは青く塗る頂点数をスコアが最小になるように選び、それらの最大値を答える。ただし、葉を全部赤く塗ってもまだ他に赤にできる頂点がある場合は、追加で別に考える必要がある。Fは取る・置く操作をその位置で何回行いたいかを持ちつつdpすればよい。

残り1時間あって、solvedが多いHを考えてSlopeTrickだと思って実装していたが、DAGの分岐や合流にすべてを破壊されて終了。結果は6完37位で2837→3887(+50)。

F問題は、偶数番目だけbit反転すると01列の転倒数になるらしい。今年の夏にAtCoderで開催された有志コンで既出で、当時どうやって解いたのか見に行ったら、そちらでも隣接項のXORを取ってなんやかんやするという気合いで解いていた。こういう言い換えが自力でできたためしがなく、辛い。またコンテスト後にEがHackされた。先に述べた「別に考える」部分にミスがあって、うっかり葉を全部赤く塗らない状態を考えていたらしい。

atcoder.jp

ラノベを1冊読了。「美少女とぶらり旅」。シンプルな題名と題材が旅ということでキノの旅を思い浮かべつつ購入を決めた。あまり面白くなかった。高嶺の花とされるヒロインに対して平気で通じないネットスラングを使っているのが気に入らない。ヒロインの事情が重く、それが主人公との関わりによって救われるというストーリーだったが、主人公がかなり軽薄な人間に感じられてあまり納得感がなかった。

しばらく別のラノベを読み、布団に入ってハーメルンを読んで、午前7時半に寝落ちした。

12/25(土)

午後7時起床。第9回PASTの通常受験が終了したらしいことをTLで知ったので、またURLを推測して定期的にリロードする作業が始まるようだ。前回は数日後だった記憶があるが、今回はどうなるだろうか。

さらにしばらくハーメルンを読んで、布団から這い出し、午後9時からABC233に出た。今回からH問題ではなくEx問題になるらしい。確かにGとHの間に壁があるということはよく言われていたか。

AtCoder Beginner Contest 233 - AtCoder

Aはdc。FAだった。やはり最近問題文の難読化が激しく、なかなか意図が取りづらかった。タイムは25秒。Bはちょっと前のJOIにほぼ同じ問題があって、そこから最短コードをコピペしてくることも考えたが、それは自分のコードではないことを覚えていたためとりあえずC++で解いた。CはRubyのproduct。DはZero-Sum Ranges。Eは繰り上がりを考えずに桁ごとの値を求めて、後から正しくする。Fはグラフが木だと勘違いして2ペナ。森になるように取って、葉から順にそろえていけば、制約から毎回愚直にdfsしても間に合うし操作回数も足りる。Gは直感的に2次元で区間dpをしたら通った。今回のExは簡単で、答えを二分探索することを考えると45度回転した状態で正方形内部の点数を数えるクエリがある程度高速に解ければよい。セグメント木に列を乗せると、区間内である値未満の要素の個数を数えるクエリがO((\log N)^2)で解けるため、これを2回使えばよい。Xを座標の最大値とし、答えの二分探索と合わせてO(Q(\log N)^2\log X)で3250msくらいだった。

42分23秒で全完、4位だった。2ペナ生やしたが、それがあってもなくても順位は変わらなかったようだ。久しぶりにかなり成功したと言えるだろう。

コードゴルフをする。Aは最初の提出が10Bで、すぐスタック操作を弄って9Bに縮め、これが最短。Bは先にも言ったJOIの問題から拾ってきたコードを全完後にしれっと提出していたが、同じコードがすでに本人から提出されていた。Cは適当にPerlで書いておいた。Rakuならかなり短くなるだろうに、あえなくTLEしてしまった。DはAWK。Eは多倍長整数のまま無理やり計算するとどうあがいてもTLEしていたところ、10XからXの桁和を引いて9で割るというコードが通っていた。なるほど、確かに10^iの位は(10^{i+1}-1)/9だけ答えに寄与し、これを全部足し合わせると10^{i+1}の部分が10Xになるのか。これくらいなら多倍長整数で計算できるということらしい。Rakuで書くとTLEしてしまい、Rubyでは負けている。桁和をchars.sum(&:hex)で取るのではなく、普通に?+でjoinしてevalするとその周りも巻き込めてさらに短くなるようだ。残りは手付かず。

atcoder.jp

午後11時半からCodeChef。今日はDecember Lunchtime 2021。

https://www.codechef.com/LTIME103A

RMNTREVは手元で実験したらそれっぽい規則が見えた。変換を戻すのではなく変換後の文字列を求めようとしたり、細かい部分を詰めるのが微妙に遅くなった。OPTSORTは何かしらdpするかと思ったが、冷静になると触らなくてよい場所を巻き込む必要はないため、ちゃんとやると操作は一意に定まる。具体的には、すべての値の移動前と移動後のインデックスを組みにして、重なるものを全部マージしたものがそう。SLEEPTECHは、イベントソートすると「A\dots Bの値の部分和で[L,R)に収まる値が存在するか？」という問題を高速に解ければよくなる。使う値を1\le k\le B-A+1個とすれば、kA+k(k-1)/2\dots kB-k(k-1)/2が全部作れるようになるので、この区間と[L,R)の交差判定を考える。kA+k(k-1)/2\lt RかつkB-k(k-1)/2\ge Lが同時に満たされるようなkを探すということ。ここでkが絡む式がどちらも単調増加であることに気づけば、前者の式を満たす最大のkだけチェックすればよいことがわかる。最大のkは二分探索で求まる。INTREENCLRは面白かった。ウニグラフを考えたりすると、方針としてはN回のクエリで1頂点ずつ色を確定させ、のこりN/2回で色を揃えることになるだろう。最初に1回クエリを投げておき、あとは葉から順に色を確定していく。葉に対してクエリを投げると、直前のクエリとの差分から葉と親の色が同じか違うかわかる。クエリを投げた葉はどんどん削除していけばよい。頂点の色のグループはsetで愚直に持ち、データ構造をマージする一般的なテクでマージした。

NOL_LESSは解けなかった。どうやらAの制約がAB\le Dの形で与えられていたのが超重要らしく、このことからAの上限は高々O(\sqrt D)種類、しかもその総和は調和級数でO(D\log D)になっていたようだった。dpの遷移は愚直にやると2乗かかるが、畳み込みで高速化できる。4完30位でレートは2516→2518(+2)。何とか色落ちは免れた。

コードゴルフをする。スペシャルジャッジの問題で、出力の最後のほうに同じ値が連続するような出力を出すことになったが、試しに個数を増やしてみても通った。さては入力をまともにチェックしていないな？と思い、試しに1個だけ出力してみると、これも通ってしまった。恐らく問答無用でK回cin>>Rしていて、入力が存在しない場合は直前の値がそのまま使われてしまう、ということだろう。

atcoder.jp

ハーメルンを1作読了。「妹の配信に入り込んだらVTuber扱いされた件」。タイトルの通りのVTuberモノである。主人公のハイスペぶりが気持ちいい。セリフ回しがパロディ多めかつハイコンテキストでちょっと置いて行かれ気味だった。実際のところ企業系VTuberの実兄が定期的に配信に出演するようになって同期や先輩と仲を深めていたら大炎上間違いなしだろうし、作中でも微妙に燃えていたという描写はあるが、そこは創作なので気にしなくてよい。

syosetu.org

ラノベを1冊読了。「才女のお世話」2巻。今回もかなり良かった。1巻は良かったという記憶だけが残っていて、内容を忘れており、キャラクターの設定などが微妙にわからず困った。1巻はラストにハラハラするシーンがあった一方、今回は徹頭徹尾ラブコメで非常に良い。1巻のメインヒロインはあまり登場しなかったものの、出てくるたび嫉妬心を持て余しているようで可愛らしかった。みわべさくらさんのイラストも相変わらず良い。

日記を書きつつまたハーメルンを1作読了。「憑依系多重人格ライバーとは俺のことで私のこと！」。セリフのフォントで発話者を区別するのはなかなか見ないが、そもそもそうしなければ区別できないような文章を書くべきではない気もする。

syosetu.org

布団に入ってからも別のハーメルンを読み続け、さらに1作読了してから寝た。「男性Vがコラボするってよ【完結】」。炎上を題材にしているだけあって辛い展開が多かったし、特にラストの大会配信についたコメントなんかは直接的な物言いで心にキたが、ハッピーエンドでよかった。確かに話は一段落しているものの、正直これで完結するのは寂しい。続編も期待したい。

syosetu.org

午後3時半就寝。

12/26(日)

午後8時半起床。最近目覚ましをスヌーズすることを覚えたので、午後8時から10分ごとに意識を取り戻しつつ何とか覚醒できた感じ。午後9時からARC132。

AtCoder Regular Contest 132 - AtCoder

Aはちょっと実験すると確かに一意に定まってくれることがわかる。ここで実験のためのR,Cをソート済みにしておくと規則性が読み取りやすい。R_r+C_c\ge n+1であることが'#'である必要十分条件になるだろうと予想がつき、投げたら通った。Bは最初、操作によって必ずソートできるという条件をよく理解しておらず全然解けなかった。冷静になると操作のパターンが限られてくるため、全体を反転する必要があるかないかで場合分け、あとはどれだけシフトする必要があるかを調べた。サンプル3は反転を2回行うケースで、優しいなあと思っていた。CはbitDP。瞬殺。

残り100分をすべてDに捧げてしまった。何とか通ったはいいものの、Cまでがほぼ最速のため順位はあまり変わらず。まず「間にある」という条件を考えた。これは1だけを取り出してインデックスの対応を見ると、ちょうどその間のどこかに1が来ればよいということになる。そのもとで、できるだけ同じ文字が連続するようにしたい。実は「どこか」ではなく左端か右端と固定していいんじゃないか、追加として真ん中で現在進行中で連続しているものも1つ考えておけばいいんじゃないか、連続する文字数ではなく連続しなかった位置をカウントしないと貪欲できないのではないか、などしつつ5ペナと40分を溶かした。

ここでふと、そういうi文字目の1が位置すべき区間[l_i,r_i]に対し、[l_i-i,r_i-i]を考えると、「連続する値」ではなく「等しくなる値」を数えることになって扱いやすいのではないかと気づいた。区間スケジューリングを考えれば、これは貪欲で解ける。意気揚々と実装してみると、細かい値が合わない。どうやら端の扱いが難しいらしい。サンプルを睨みつけつつどうなってほしいのか手でいろいろ確かめて、何とかサンプル1、2まで合わせたが、3が合わなかった。この解き方だと1だけを取り出す代わりに0だけを取り出してもよく、そちらでは合う。逆にサンプル1だったか2が合わなくなったので、そちらをより細かく見て、やはり端の扱いを間違えていることに気づいた。値が端に揃った場合だけボーナスがあり、それを考慮しつつ貪欲するのは難しい。そのため、特にスタート地点である左端の扱いは2通り両方試すことにした。これでサンプルが全て合ったので提出、WAするも、適当に全部0とか全部1を投げると落ちてくれたので、それだけ別処理してようやくAC。

6ペナで4完ほぼ最遅、どうしようもない。コードゴルフをする。Aは適当にPerl。CはRuby。

Bは非常に頭の良い解答がいろいろあって、アイディアだけもらって縮めた。まず、僕はシフト回数を調べるのに1の位置を検索したのだが、これは数列を反転するかしないかで値が微妙に変わる。ここで驚くべきことに、nの位置を検索すると、数列がソート済みでない場合は場合分けが必要なくなる。自分でも何種類か手で試してみると確かにうまくいっていて、nのインデックスが0-indexedでiだとすると、答えは\min(i+1,n-i+1)になっている。ここからさらに縮む。実はこのiはp_1（数列の先頭要素）またはn-p_1と一致し、このどちらであっても\min(i+1,n-i+1)=\min(p_1+1,n-p_1+1)が成り立つ。つまり検索の必要すらなく、先頭要素（と数列がソート済みであるか確認するための2番目の要素）を読み込むだけで答えが出てしまうのだ！

ハーメルンを1作読了。「コミュ障ロリ魔王様のVtuber生活 in地球」。魔王様なので当然ハイスペックである。それを見せつけている序盤はよかったが、途中から過去の知り合いなど出てきて、そういう話はあまり好みではなかった。もっと無邪気に無双していて欲しかった、とはいえ、コミュ障克服というテーマゆえ仕方のないことか。

syosetu.org

その後また別のハーメルンを開いて、布団に潜り込んで朝までずっと読んでいた。さすがにまずいと思って起きだし、こうやって週記を書き上げた。次回更新は年明けか、それまでに今年読んだネット小説まとめを書きたいが……。