週記（2021/02/01-2021/02/07）

02/01(月)

日曜日は週記を投稿してから比較的すぐ、午前6時半くらいに寝た。Chromeの履歴によれば、3時間後と5時間半後にそれぞれ少しずつ起きていたらしい。特に2度目の覚醒時、ICPCアジア地区横浜大会の暫定競技ルールが公開されたのを見つけ、少し確認していた。

2020 Regional Special Rule 暫定版 | ICPC 2020 Asia Yokohama Regional

実際に起床のツイートをしたのは午後4時前であった。夢を見た。前半部分はかなり喪われ気味であったが、数学的な用語が夢に登場するのはそこそこ面白く感じられたので、適当に復元してツイートした。

最近Chromeのタイムゾーン設定がバグっていてUTC -9らしい。この影響でせっかく埋めたAtCoder ProblemsのHeatmapが穴だらけになっていた。諸行無常を体現している。

yukicoderのほうでゴルフが盛んに行われているようだったので、粗探しをしていた。自分の手元のRakuはいまだに2016年1月版（これはAtCoderの言語アップデート以前の処理系に合わせていた）で、現在の環境に合わせてゴルフするのには向かない。いったん削除し、改めて入れなおすことにした。前回はインストーラ経由で入れたようだったが、今回はファイルを展開したらそのまま使えるようになっていた。Program Files下に移動させておく。cygwinからexeファイルへのフルパスを叩きつつ、やはりファイル名に空白が入っているのは正気の沙汰ではないという気持ちになった。

昨日上げたゆっくり実況について、ゆっくりの喋る速度がもっと速いとうれしい、という意見が来ていた。これについては僕も薄々感じていたこと、オタク早口は伊達ではない。今度動画を作る際には少し弄っておくことにした。

yukicoderでのゴルフに熱中していたところ、サークルの解説会の開始時刻である午後8時になっているのに気づかなかった。いつも僕がGoogle Meetで会議を立ててURLを共有しているのだが、今日は僕が15分経っても応答しなかったので、急遽ホスフィンが代わりに立ててくれた。気づいたのは午後8時20分で、慌てて参加した。1問ぶん聞き逃した。他にも、今週は僕が発表していないのだが、サークルメンバーが増えたと見るや否や解説役をサボっていると解釈され得るので気が気でない。決してそういうわけではなくて、僕もF問題の解説をしてやろうという気持ちはあったが、単純に何もかもを忘れてしまった。準備も始めてすらいなかった。

4年次ゼミの割り振りについて、現在僕が第一希望にしているゼミは定員より多い人数が希望しているため、何人かを第二希望以降に回す必要がある。

来年のゼミの希望を出すために教科書を眺める。最初は公理的集合論がよさそうだと考えていたが、整数論の教科書にメビウスの反転公式とかが書かれているのを発見して一気に興味を惹かれる。これを第一希望にすることにしよう。

週記（2021/01/11-2021/01/17） - kotatsugameの日記

その関係で簡単なアンケートが来ていた。ゼミで読みたい本の希望と、自分の将来のイメージと、現在の総取得単位数・残っている必修単位数。読みたい本の希望はいいが、自分の将来のイメージとはなんだ。この年になって夢を語るというのか。いくつになっても夢がある人間は強いですよ、といった意識高い系の話かもしれない。また3つ目の単位数に関する話も僕にとっての鬼門で、カウントする作業はいつやっても面倒で気が滅入る。

EMLauncherを解いた。黄diffは残り1問である。そこそこ時間をかけてコーディングしたところ、1発ACした。やはりすべて整数の範囲で計算したのがよかったのだろう。やること自体は明らかで、偏角ソートをある半直線を基準にして行うのがつらかった。書いているうちに微妙に怪しいところを見つけたので、このコードは最初のACのものではないが、実装方針は変わっていない。詳細を記しておこう。

atcoder.jp

ある点pを選ぶ。まずこの点に向けてビームを打ち、残りの線分は偏角ソートすれば区間スケジューリングの要領で計算できる。つまり、原点から点pへ伸ばした半直線と線分の交差判定、交差しない線分の（片方の）端点による偏角ソートができればよい。点qと点rを結ぶ線分を考える。前計算として、外積cross(q,r)が非負となるようにswapしておく。制約から線分は原点を含まないので、いい感じになる。偏角ソートには点rを使用することになる。

X=cross(p,q)、Y=cross(p,r)と置こう。X=Y=0の場合を先に処理する。このとき点pと点qの内積の正負で判別でき、負のとき半直線と交差しないので、線分を集合Rに追加する。

それ以外ならば、X<=0<=Yのとき、線分は半直線と交差する。このとき原点から見ると点q、点p、点rの順に並んでいて、しかも点qと点rの間の角度は180度未満（線分は原点を含まない）だとわかるからである。交差しないような線分に対しては、Y>0のとき集合Lに、Y<=0のとき集合Rに追加しておく。

集合Lと集合Rをそれぞれソートする。各線分に対してcross(p,r)の符号で分けているので、各集合内では単に外積の正負で順番を決定できる。集合Lの要素は集合Rの要素よりも先に位置するため、そのように連結すれば偏角ソートができたことになる。区間スケジューリングにおいてもまた半直線と線分の交差判定が必要になるが、同様にできる。

この問題の制約ならatan2を使用してもソートできるらしい。誤差の評価についてはmaspyさんが教えてくださった。

最後の黄diffである天下一最短路コンテストを考えていたが、解けない。午前2時半ごろに布団に倒れこんだところ、即座に寝落ちした。

02/02(火)

午前9時前に目を覚ました。ゴミをまとめて出す。久しぶりにポストを確認すると電気代のハガキが入っていた。先月は8000円弱だったらしい。エアコンをガンガン稼働させながら寝落ちしていたのが効いているのだろう。

mod上の逆元リストを必要に応じて生成する方法についての議論があった。前から作成する方法は、オーダーだけ見ればO(N)だが、実際は変数による除算や連続的でない配列アクセスなどがある。その点、後ろまで作ってから1回だけ逆元を計算する方法は、O(N+log mod)と変なのがついていても、定数による除算しか行わなかったりシーケンシャルアクセスが保たれたりと良いこと尽くめ。必要に応じて生成する場合も、倍々に増やしていくことで対応できる。これに関しては、呼び出しごとにif文による分岐が入るのが気になっていたが、分岐予測がかなり効くだろう、という話を聞いた。

形式的冪級数の逆元を初めて知った。うまく定義されるんだなあ。

paper.dropbox.com

朝の時点では計算方法に関してあまり考えていなかったが、冷静になるとO(N^2)かかるように見える。いくらか調べたところ、これもうまいこと計算できることを知った。

qiita.com

布団に転がって「東方遺骸王」を読み返していたところ、耐え難い眠気に襲われたので昼寝。閲覧履歴によれば午後3時半ごろから午後8時半ごろまで寝ていたようだ。

午後9時からサークルのバチャ。CF 698だったが、これはつい最近行われたコンテストで、C問題の解法をTLで見て覚えていた。最遠点を取り続ける解法。A問題はかなり詰まってしまったが、何とか1点を固定して差をとってgcdを見ればよいことが分かった。B問題は後ろから見ることに気づけば一瞬だった。Dを読んでいたが全然わからなかったので、終了までハーメルンに逃げていた。

東方の二次創作をいくらか読んで東方に関する知識を増やした後、再度「東方遺骸王」を読み返すと、話のいたるところに東方の影が見え隠れしていたことに気づいた。アハ体験みたいで面白い。「東方遺骸王」は東方の二次創作という形式ではあるものの、普通に読んでも非常に面白いと思っている。かなり長いので気軽なお勧めはしにくい。

syosetu.org

そのまま午前3時ごろまで読み続け、そのあと起きてシャワーを浴びて日記を書いた。溜めていた月曜日の分も含めて書き終わったら午前6時だった。布団に入り、また読み返し続ける。午前9時前に就寝。

どこかの時間で日曜日に出した動画を再度見返していたのだが、BGMの音量を絞りすぎたことに気づいた。これまでは元ファイルの25%設定で、今回はちょっと大きいかなと感じて15%にしたのだが、変えなくてよかったらしい。

02/03(水)

午後2時半、目を覚ます。布団に転がってハーメルンを読んでいた。寝足りない気がしたのでなんとなく寝ようとしてみたところ、午後4時半くらいに再度就寝。次に、午後6時半に起床した。このタイミングで起床報告のツイートを行った。

さらに1時間程度ハーメルンを読んだ後、布団を脱出して食事し、パソコンの前に座る。今日もサークルのバチャがある。始まるまで少し時間が空いたので、ようやく残っていたレポートに手を出すことにする。とりあえず講義資料を見なければ話にならない、ということで見ようとしたら、文章ではなく動画だった。非常につらい。

少し視聴して、途中で出されていた問題を1つ解いたらバチャの時間になった。今日はCF 604。ABCd（D1のこと）の4完だった。なかなか良い成績であったようだ。

A問題はよい。B問題はサンプル1みたいな構築しかしなくてよいものと決めつけてみたら通った。冷静になると証明もできる。0があったときに、離して置く必要性は薄い。実装方針もかなり当たり気味。C問題はつい最近のABCで見たような、スタートに戻る期待値DP。ちゃんと文字で置いて計算してみるとかなりきれいな形の式になった。分母は積で、分子は一次関数の合成になる。どちらもDisjoint Sparse Tableで持てるが、結局チェックポイントを持つのにsetを使うので、logは落ちない。

D1問題は、マッチを左右から貪欲にすることにすれば、あとはマッチしうるペアを全て試し、寄与を足し合わせればよい。ペアを試すのにO(N^2)、また寄与は二項係数の積の和になるのでさらにO(N)かかる、が、よく見ると定数倍がかなり軽そうに見える。実際Rubyで最悪ケースだと思わしきものの計算回数を求めてみると、6e8くらいになった。剰余などもあるので安心はできないが、とりあえず定数倍に気を使って書き、最悪ケースを試してみたところ、1secかからなかったので提出。サーバでも1secで通った。ここからD2につなげるとっかかりは見えず、またE問題も多く通されていたが、わからずじまいだった。

また講義動画に戻る。1回ぶんの動画時間が70分とか80分とかあってかなりつらい。飛ばし飛ばし見る。途中でレポート問題が挟み込まれるが、見落とさないか心配でたまらない。第4回まで視聴し、ふと期末レポートの問題を確認したところ、どうにも最低限の問題は既に解けそうであることに気づく。まだ少しは先に進む必要があるだろうが、全15回を全て見る必要はなさそうだ。これは朗報である。

ただ、途中に挟み込まれるレポート問題も評価に入るのだから、時間の許す限りは見ておかなければならないだろう気もする。期末レポートを出さなければお話にならないが、では期末レポートを出したとき、他のレポートはどれくらいやっておかなければならないのか？評価はこの際Cでも構わないので、最低限のラインを狙っていきたい。

金曜日の午後11時が締め切りである。まだ多少の余裕があるように見えるので、午前5時くらいに眠くなったのを受け、素直に寝ることにする。寝ている間に理解が進んだりしないかなと思うものの、成功した試しはない。それはそうで、数日漬けで何とかしようとしている内容は夢の中で考えられるほど定着していない。

布団に入ってから1時間程度ハーメルンを読み、午前6時就寝。

02/04(木)

正午、目を覚ます。二度寝しようかとも考えたが、レポートによる焦りもあってそのまま起きることにした。

今セメスターの講義の評価がいくつか出ていた。

自分のこれまでに得た単位と4年生になるための単位を比較して、今セメスター何が必要かをリストアップしてみた。

週記（2021/01/25-2021/01/31） - kotatsugameの日記

現在、幾何学序論Aと代数学概論Cの単位が来ている。先週のツイートと照らし合わせて、残り線形代数学Bの単位が来れば4年生になれるようだ。今見返したところ、代数学概論Cと幾何学概論Bのどちらか片方が必要と言ったのは間違いで、実は両方落としても4年生にはなれるようであった。この2つは選択必修の科目で、現時点では位相数学Bという講義の単位を同じ選択必修として持っているが、4年生になるにはこの1講義で十分らしい。卒業するためには2講義ぶん必要で、これが「どちらか片方が必要」の正体である。

また、今絶賛レポート取り組み中の幾何学概論Bには演習が存在するが、課題の締め切りはとうに過ぎ去っていたようだ。結局何一つ提出しないまま終わってしまい、評価はDではなくN/A（？）だった。

昨日の続きで、また講義動画を視聴する。夕方、第7回くらいまで見終わったところで、昨日言及した期末レポートの最低限の問題全てに答えられる状態になったことを確信する。講義動画の途中に挟まれるレポートについては、見終わったと言った動画であっても計算の重そうなものは飛ばしてしまっているが、とりあえずこれからは期末レポートを完成させることを第一目標にして動こう。

最低限の問題というのは4問あり、うち2問は語句の定義に関してまとめよというものだ。証明や計算ですらない。まずこれについて書く。推敲が必要に思えるため、TeXで書くことにしよう。結構頑張って講義動画を解釈し、自分なりに納得を得た上で、定義に必要な準備から書いていったのだが、見返してみると結局講義で示された式を丸写ししているのと変わらない内容になってしまった。これはどうしようもなくて、わざわざ講義で使っている文字から変える必要もないため、本当にそのままの式になっている。

途中嫌になって本を読んだりしていたものの、なんとか2問書ききる。もう2問あり、片方は頑張って計算するもの。もう片方は証明だが、これは実は講義でやった。後者にまず取り掛かる。と言っても本当に同じことを講義でやっているので、これも丸写しと変わらない内容になってしまう。一応証明の方針だけ見て埋められそうな行間は自力で埋めてみた。講義で行った証明のほうが簡潔だったので何が違うのだろうかと考えていたが、講義では集合の等号を示そうとして片方の包含しか示していないように見える。

最後の計算が残って非常につらい気持ちになるが、実は期限まではあと1日ある。生活リズムも良くて、起きたら提出期限ギリギリだった、とかいうことにはならなさそうなので、これは明日に回してもよいだろう。Google Classroomをいろいろ見ていると、最初にこの講義についての説明があることに気づいた。PDFを読むと、レポートの提出形式についても書いてあって、「A4サイズの紙に解答を書き、スキャンしてPDFファイルにして提出する」とあった。まずい。TeXで書いたのを紙に写す作業が待っているのか……。

諦めきれず、今度は説明の動画で該当する箇所を視聴する。聞いている限りでは、PDFファイルを提出することが重要であるらしく、それ以外の要素についてはあまり触れていない。多少希望が出てきたので、いっそのこと直接確認することにして、教員に質問を送っておいた。

布団に入ってハーメルンを開いたところ、「このすば*Elona」が更新されていた。今話はかなり長めで、展開が非常に良い。主人公の見せ場直前、周囲のキャラクター視点の語りが続いて気持ちを昂らせ、そこで次の話に続く！とはならず本題の見せ場まで描かれている。満足。

午前4時就寝。

02/05(金)

午後1時半起床。学食に行く。

開いていなかった。写真をよく見ると短縮営業している店舗もあることがわかるが、この時間はすでに閉まっていた。仕方ないので購買に行くも、パンが全滅していた。どうしようもないためお菓子を買って当座をしのぐ。その後生協に入っている床屋に行った。

帰宅して、コンビニで購入したパンを食べ、レポートを進める。期末レポートの最後の1問。

ある単体的複体のホモロジーを具体的に求めよというもので、講義では次元が1以下の単体のみを含むものについて計算していたので、同じ感じでやろうとする。ところが、今考えている多面体は次元が2の単体を含むので、ちょっとまずそう。H_1を求めるときに、境界準同型のKerもImも簡単な形にはならない。とはいえ、何らかの定理を適用するのもよくわからないので、とりあえず式で書いてみることにした。するとものの見事に係数が一致して、H_1が0の一点集合であることが明らかになった。かなりびっくり。

期末レポートはこれで完成である。手書きでなければならないかを問うコメントへの返事がまだ来ていないが、今更紙に書き写すのも面倒でしょうがないので、とりあえずこのまま出しておくことにする。期限までに返信が来てダメだと言われたら、またそのとき考えよう。

ラスボスを倒してしまったので気が抜けるが、まだいくらか時間はあるので、講義動画を見つつ途中のレポートを解く作業に移る。しかし、第8回を見て1問解き、また以前の講義に戻って飛ばした問題を1問解いたところで完全に気力が尽きる。第8回までで残っているものは1つだけ、また残りの講義は5回ぶんしかないので、（1回の講義でレポートが複数出る可能性はあるものの）多分全体の半分は解いただろう。提出作業に移る。せっかく問題ごとに分けてスキャンしたのだが、提出するときは1つのファイルにまとめなければならなかったようで、PDF結合のWebサイトを探してきてくっつける。ちなみに昨日の日記には「A4サイズの紙に」と書いたが、正確には「A4サイズのレポート用紙または電子ノート」とある。翻って自分はコピー用紙にレポートを書いてしまっている。まあ罫線の有無で採点をしてくれないほど心の狭い教員ではないだろう、ということでこれもそのまま提出。

以上でこの講義の課題についてはすべて終わったものとする。これにて春休みである！

評価がN/Aになってしまった演習が気になってClassroomを調べたところ、一番最初に授業についての説明PDFがあって、課題の提出期限も書いてあった。実は1/14が締め切りだったようで、何もかも間に合っていない。

途中でサークルに届いていた入部メールに気付いて返答した。9日間放置していたらしく、非常に申し訳ない気分になる。しかもそろそろ春休み期間で活動がお休みになるため、その前の数少ない活動に参加させてあげられなかったということでさらにつらい。

yukicoderに出る。7完。かなり面白いセットだった。

Aはよい。Bは前のほうから到達可能にしていきたい。Cはよくわからないが、aとbの符号を決めて貪欲に取ったら通った。解説が非常に賢い。Dは左と右から累積maxみたいな感じでやる。耳DPするというのを見た。Eは難しいが、実験すると適当に0で埋めて残りを110100の繰り返しにすると結構できることがわかる。

Fは非常に面白い。まずiとN+iがペアになることが分かって、そのペアの間でどのような操作に対しどのような結果になるかを観察すると、いい感じにできる。2回やると大体もとに戻るのが面白かった、が、これはペアに関する遷移で見ていたから非自明に感じられるのであって、元のxorで考えれば明らかかもしれない。GはDP。

直後のCF 699 div.2にも出た。5完トップで5位。Eで2WA吐いてかなり厳しい気分になっていたが、A-Dが爆速だったらしい。

Aはよい。Bはk<=1e9を見て考察を始めてしまった。頑張ればいろいろ1e9オーダーで解けそうだったが、冷静になって制約を見るとシミュレーションすれば解ける。Cは後ろから見る。面倒。Dはギャグ。Eは区間maxのセグ木……と思ったらWA。後ろのほうの塊をそのまま残すケースをうまく計算できていなくて、直すのにもミスして結局2WA。Fは少し考えたが嫌になって止めてしまった。

「あくまでも探偵は」という本を読んだ。良かった。キャラクターが良い。ミステリとして見るには、どうだろう。探偵役が秘密主義すぎて、いろいろ唐突に感じられてしまう。この本に限った話ではないが、連作短編をいくつか集めて大きなストーリーを1つ作るような本の構成だと、扱う事件の全てで黒幕が共通していて、ちょっと気になる。

部屋が非常に寒い。エアコンは23℃設定でガンガン利かせているつもりだが、エアコンと僕がちょうど部屋の対角線の両端に位置するような位置関係のため、温かさが伝わってこない。何か電気ヒーターみたいなものを購入して近くに置いておくのがよいかもしれない。

食事して日記を書こうとしたら、Twitterの貼り付けが一時うまくいかなくなっていた。今日の冒頭の部分を書いているときにはその状態で、書き進めて今この文章をタイプしている時にはすでに直っている。今日はTwitterのリンクを2つ挿入したが、再度貼りなおしておいた。

月曜日からバグり続けているChromeのタイムゾーンを直す。ちょっと調べたところ、Windowsのタイムゾーンを一度切り替えてもとに戻すとよいらしい。念のためすべてのタブを閉じてやってみたところ、無事直った。たったこれだけの手間を惜しんで、1週間ずっと頭の中でUTC -9からUTC +9に変換し続けていたのかと思うと、やるせない気分になる。

午前5時就寝。

02/06(土)

正午、起床。布団でゴロゴロしていたが眠れないので午後3時に起床報告のツイートをした。ハーメルンを1作読んだ。

syosetu.org

文章がカスだし未完。おススメはしない。以前からめちゃめちゃ長生きの主人公が好きだという話をしていたが、これの作者も同じ嗜好らしく、主人公が事あるごとに年齢マウントを取ってくる。

月曜日の続きで天下一最短路コンテストに取り組む。数日空いたが、その間たまに考えを巡らしたりしていた。考えていたのは次のような方針だ。

嫌になったので解説を読む。最初のほうだけチラっと見ると、2x50という文言が目に入る。実際そのように配列して、番号を上手いこと割り振ることを考えると、タクヤ君が最後までいかずに戻ってくるような辿り方をしてしまうケースを作れることに気づいた。非常にシンプルな解法で、これが思いつかなかったのは意味不明。サンプル2を発展させようと夢中になっていたが、何の関係もなかった。

ともかくAC。これで黄diffがすべて埋まったことになる。

橙diffに進み、食事したりシャワーを浴びたりしつつさらに2問解いたところでABCの時間になった。

全完59位。Fに3000万年かかった。ペナルティもしょうもないことをして出している。

A、Bはよい。Cは、まず黒と白の境目の数を数えて、次にその境目が2つ並んでいるような場所の数を引けば、辺の本数がわかる。Dは気合い。Eは自明。Fは適当に部分集合を選んでそのgcdかつmin(A)より小さいもの、という条件であることがわかる。ここから、数列の先頭からありうるgcdを全部持って順に計算していくやつを4回くらい投げて全部TLEだった。バカ。どういうケースでめちゃめちゃ時間がかかるのか全然想像できなかったのが良くない。残り30分くらいになったので、とりあえずA問題のコードゴルフをして、再度考え直すと解けた。数列の各項について約数を全列挙できて、同じ約数を持つ項全部のgcdがその約数と等しいか判定すればよい。これは、できる。

コードゴルフをする。A問題はコンテスト後にさらに縮んだ。最初はVT<=D<=VSを(VS-D)(VT-D)<=0と変形して場合分けする解法。実はVT<=D<=VSはT<=D/V<=Sになる。ここから同様に積の形にして場合分け1回にまとめるよりも、うまいこと比較を2回するほうが短くなった。最初の比較に成功したら次の比較をするが、失敗したときも次の比較によってスタックが変な状態にならないように調整する。具体的には、文字列と数値を<または>で比較しようとすると、結局何もせず（スタックもいじらず）終わるという仕様を利用する。ここで!<や!>を使うと必ず成功してしまうのでまずい。

atcoder.jp

Bは全完後にAWKで20Bを出してニコニコしていたが、蓋を開けてみるとVimの13Bに蹂躙されていた。Vimを使うことに思い至れば20Bは切れただろうが、13Bのコードはよくわからない仕様を使っていて、自力ではたどり着けなかっただろう。Cはx20さんとバトル。負け。文字列のbit演算を使うという発想で、最初xorしていたのをandに直すことでキャプチャをなくした。

Dはよくわからない。まず有理数で頑張った。sqrtがまずいようで、全然通らない。結局そこは整数に直してbsearchで求めることにした。ところが1e4を掛けて整数で計算する解説の通りにやったところ、普通に短くなってしまった。ちなみにこちらでもsqrtの代わりにbsearchを使っている。Eはやっていない。FはTLが厳しく、Crystalを持ち出すことになった。Pythonみたいに等式・不等式をつなげて書くことができてびっくりした。

コードゴルフをしていたら午前3時になったので、SRM799に出る。午前2時開始だったのが別のコンテストと被ってさらに遅くなった。人権がない。

Medの1完。Easyを落としてしまったが、レートは2389→2404(+15)でhighest。Easyは、再帰的に計算するのはよかったが、分割した後それぞれ独立にできるわけではないことに気づかなかった。

Medは、直径の両端を全探索する。直径を与える組が複数あるような部分木については、頂点番号で何とかすると何とかできそう。ここまで考えたところでとりあえずO(N^3)のコードを書き、サンプルを試した。通ったのでさらにbit全探索のチェッカーを書き、ウニグラフっぽい直径を与える組がたくさんある木を試してみる。これも通ったので、ようやく高速化に着手した。2つの列で両方条件を満たすような場所の個数を探す必要があって、データ構造ではちょっと難しそう。ここでbitsetを思いつく。探索の順番をうまいことやる（直径の小さい順に調べる）ことにすれば、1回の計算はbitsetのandとcountで済む。直径を与える複数の組の頂点番号に関する条件もよさそうであることを丹念に確認し、実装して先ほどと同様のテストケースを試したところ、システスに通った。変わらずO(N^3)だが、64倍高速になる。

橙diffを1問読んで布団に入る。解けたあと少しなろうを読んで就寝。午前8時だった。

02/07(日)

午後2時くらいと午後3時くらいに2度、中途覚醒。別の橙diffを開いて考えながらまた寝た。結局起きたのは午後6時半だった。

yukicoderがあるので、それまで解けたはずの2問の実装をする。実際解けていて、通った。そのあとシャワーを浴びてyukicoderに臨む。

途中キーボードの接続がうまくいかずコーディングできない状態になったりしたものの、5完。全体的についている星よりも難しかった。

Aはよい。Bは飛ばそうかと考えたものの、少し立式したら解けた。ギャグの類。Cは難しい。dijkstraを元に考えると、最長路を計算することになってまずい。実際は街をソートして、到達可能性だけUFで扱う。UFに一緒に集合内の最大値を持たせる。

Dも難しい。まずAを小さいほうから試してmapでカウントしていく。B>=2なるペアが作れなくなったところで打ち切る。これは三乗根とかが出てくるので小さい。で、mapの要素を見ながらB==1の場合を足し引きしていく。具体的には、B==1なるペアが作れるAの個数が求まって、またmapの要素のうちB==1でも実現可能なものが判別できればよい。前者は二分探索でできる。後者は、A(A+K)=Xを式変形してA=(sqrt(K^2+4X)-K)/2になるので、このsqrt(K^2+4X)が求められればよい。K<=1e18なので__int128を用いて二分探索した。

EはNとMの両方が偶数の場合の構築ができたので、これで提出したところ、サンプル以外全ケースでWA。ここでいったん冷静になって、どうせ全部にコーナーケースが入ってるんだろ？というメタ読みをしてN=M=1の場合分けを入れたものを再度投げると、AC。

Fに取り組んでいる間に時間切れ。結局4分後に通った。純粋に式変形を頑張ると解けて感動。これに関してはしっかり解法を記録しておこう。

まず「円に内接する三角形」で検索して面積を求める公式を調べる。すると、辺の長さの総積/4であることがわかる。そこで点iとjを結ぶ辺の長さを計算してみる。

\displaystyle\sqrt{\left(\cos\frac{2\pi T_i}{L}-\cos\frac{2\pi T_j}{L}\right)^2+\left(\sin\frac{2\pi T_i}{L}-\sin\frac{2\pi T_j}{L}\right)^2}=\sqrt{2\left(1-\cos\frac{2\pi(T_i-t_j)}{L}\right)}

なので、3点i、j、kがなす三角形の面積の4倍（分母はいったん無視）はp_i=\frac{2\pi T_i}{L}と置いて次のように表される。

\displaystyle2\sqrt{2(1-\cos(p_i-p_j))(1-\cos(p_j-p_k))(1-\cos(p_k-p_i))}

1-\cos(p_i-p_j)=2\sin^2\left(\frac{p_i-p_j}{2}\right)なので、根号が外れて8\left|\sin\left(\frac{p_i-p_j}{2}\right)\sin\left(\frac{p_j-p_k}{2}\right)\sin\left(\frac{p_k-p_i}{2}\right)\right|となる。

ここでi、j、kが偏角の順i<j<kであったことにして、点jを固定してみよう。\alpha=\frac{p_j-p_i}{2}、\beta=\frac{p_k-p_j}{2}と置くと0\lt\alpha,\beta,\alpha+\beta=\frac{p_k-p_i}{2}\lt\piであるから絶対値が外れ、8\sin\alpha\sin\beta\sin(\alpha+\beta)になる。さらに式変形を進める。以下でスタイルが変わっているのは、eqnarrayを使おうとしたらpreタグが必要になったから。

\displaystyle
\begin{eqnarray*}
8\sin\alpha\sin\beta\sin(\alpha+\beta)&=&8\sin\alpha\sin\beta(\sin\alpha\cos\beta+\cos\alpha\sin\beta)\\
&=&8\sin^2\alpha\sin\beta\cos\beta+8\sin\alpha\cos\alpha\sin^2\beta\\
&=&8\left(\frac{1-\cos 2\alpha}{2}\frac{\sin 2\beta}{2}\right)+8\left(\frac{1-\cos 2\beta}{2}\frac{\sin 2\alpha}{2}\right)\\
&=&2(\sin 2\alpha+\sin 2\beta-\cos 2\alpha\sin 2\beta-\cos 2\beta\sin 2\alpha)\\
&=&2(\sin 2\alpha+\sin 2\beta-\sin(2\alpha+2\beta))\\
&=&2\sin(p_j-p_i)+2\sin(p_k-p_j)-2\sin(p_k-p_i)
\end{eqnarray*}

公式解説ではこの変形について特に触れていないが、自分はなぜかめちゃくちゃ時間がかかった。

三角形の面積の総和、つまり任意のi<j<kに渡る上の式の総和を考えると、各i、j（ただしi<j）の組について\sin(p_j-p_i)が総和に寄与する係数が求まる。三角形をなす残りの1点kとして、i<k<jなる点を選ぶかそうでないかで符号が変わり、実際の係数は点の添え字を0-indexedとしてN+2i-2jとなる。\sin(p_j-p_i)もさらに分解することで、結局(N+2i-2j)(\sin p_j\cos p_i-\cos p_j\sin p_i)のi<jを渡る総和になる。展開して4つの項に分けると完全にiとjが分離できて、各項についてjを動かしながらiに関して和を取れば線形時間で求まる。あとは無視した係数を戻したり、期待値なので場合の数で割ったりすればよい。

まとめると、まず1つの三角形に注目して角度の差3つの式を作り、式変形してそれぞれ分離し、1つの角度の差に注目して寄与を計算し、さらに分離して「角度の差」ではなく「角度」の式にしたということになるのか。ここでいう分離とは、おおむね線型になって分配法則などが適用できる状態になること、を指す。三角関数の中で差を取ってるのがダメなことを自覚していなくて、うっかり文字で置いてしまったのが見えなくなった原因かもしれない。実際、根号が外れたところの式をWolframAlphaにぶち込むと最後の式が出てくる。

直後にこどふぉ。今日はCF 700 div.1だった。Aを落としてB1B2C。predictorによれば2675→2633(-42)。

Aは、区間の左端がその1つ左より小さく、右端がその1つ右より小さい、という状態を維持して区間を半々にしていく。落ちた原因はこれ。

はやく人間になりたい！

B1は、基本的にランレングス圧縮したあと個数と2のminを取ったものの総和になる。2個以上あるものだけ抜き出したときに同じもの（pとしておこう）が隣り合う場合は、間の1個しかないものを適当に動かして何とかする。何とかできるフラグをミスして1WA。正解は、問題のpとpの間に「1個しかないものであってpではないものが2つ連続している」ことが動かして何とかできる必要十分条件。

B2は左から見て列の右端を管理する実家DP。片方は必ず今見ているものが右端に来るので、もう片方を持つ。更新は全体に1足したり全体のminを取ったりするので、遅延セグメント木を使う。全体に加えられた値と全体のminを持っておけば、データ構造がなくてもできそう。Cは気合い。頭がバグっていて端数の処理に5万年かかった。D以降はやる気がない。

週記（2021/01/25-2021/01/31）

01/25(月)

午前9時半、起床。昨日していた誤読に気づいたので無事解けた。1<=i<=nなるすべての整数iについて成り立つという仮定を、i==nについてのみ成り立つものと読み間違えていたらしい。さらにレポートを解き進める。

閉区間[-1,1]上の実数値連続関数全体をベクトル空間として考え、そこに積の積分でHermite内積を定義する。このとき、x^0からx^4までの5つの関数にSchmidtの直交化を行えという問題があった。クソつまらない。ただの積であれば偶関数・奇関数の性質を用いて計算量を減らしたりなど頭を使う部分もあるが、この問題には続きがあって、今度は内積の定義が(f,g)=\int_{-1}^1 f(x)g(x)e^{-x}dxになっていた。手計算をやる気がないのでWolframAlphaに逃げたが、それでもすぐにグロい式が乱れ飛ぶようになって、早々に諦めた。これは何か良い性質があるのか？

AttraqtiAという曲があって、ジャケ絵の特徴的な髪・目からEnjiさんの手になるものだとわかる。実際ArcaeaのWikiではEnjiさんと明記してあったので、どこかに公式情報があったのだろう。EnjiさんのTwitterやPixivには特にそういう投稿は見当たらなかったが。

週記（2021/01/18-2021/01/24） - kotatsugameの日記

ツイートがあった。やはり良い。

昼、学食に行く。帰ってきてから布団に入り、ハーメルンを読む。1作読了。

syosetu.org

また東方の古代スタートもの。最近立て続けに読了している気がするが、この作品は日記に書いたものの裏でチマチマ読み進めていたものである。200話ちょっとあってボリュームリッヒ。読むのに間を開けてしまったのが悪かったのか、あんまり記憶に残るようなシーンはなかった。

作者の活動報告にあとがきがあった。読むと、「東方空狐道」という作品の影響を受けていたらしい。検索するとハーメルンにあった。「古代スタート」のタグはついていないが、ちょっとだけ読んだところそうであるとわかる。次はこれを読もう、と思ったが昨日寝落ちしたせいで日曜日の日記を書いていないことに気づく。書いて投稿。

さらにサークル解説会の準備をする。今日はABC188またはキーエンスプロコン2021の予定だが、いまだ解説役に立候補している人が誰もいない。開始まで2時間あるので、キーエンスプロコンのA-C問題の解説スライドを作成することにした。終わって少し時間が空いたので、ちょっとだけハーメルンを読み、解説会。

解説会自体は20分くらいで終了した。解説スライドのアップロードやサークル公式サイトでの記事作成などもササッと終わらせる。今週はリンクでも貼ってみよう。

競技プログラミング | puzzleknot 公式サイト

ツイッターやブログで何か言ってもサークルメンバーには当然届かない。正直僕が頑張って活動が成り立つならそれでも良いと思っているので、あんまり改善する気もない。ただ、上のツイートを読んで、解説会の解説役でもやってやろうと同じく東北大学の競プロerが新しく入部してくれたので、かなりびっくりした。ありがたい話である。

微妙に眠いし明日は期末テストがあるしで、こどふぉdiv.3の参加について少し考えたが、出ることにした。div.3だしすぐ終わるだろうという見込み。コンテスト開始まで時間があるので、ハーメルンを読んだりレポート問題を少し考えたりする。2度の延期を挟んで、結局真夜中にコンテスト開始。

序盤でかなり詰まってしまった。また開始13分後くらいからジャッジも詰まり、結局D以降のジャッジ待ちの間に全完。27分だった。全部一発で通って安心。トップは14分で全完しているので、かなり典型力の差を感じる。または、このあたりの問題群になると英語・ロシア語ネイティブとの差がはっきりしてくるのだろうか？他にもテンプレートを使用するなど、まだ縮みそうなポイントはいくつか存在する。テンプレートに関しては宗教的な理由で使用するつもりはないが、英語問題文を読む速度はまだまだ改善できそう。

問題に関してはあまり言うことはない。

ジャッジが動いてすべて通ったのを見届け、布団に入る。目覚ましをセットし、ハーメルンを読んでいたら寝落ちした。午前1時半だった。

01/26(火)

午前8時起床。目覚ましより1時間くらい早いが、うっかりハーメルンを読み始めてしまって二度寝できなかった。期末テストは午前10時半に開始。あまり早く着いても時間をつぶす場所がないから、という考えもあったが、主にはハーメルンを読むのを止められないという理由で、家を出る準備は午前9時半から行った。

購買で羊羹を買って食べたりしたところ、ちょうど開始の20分くらい前に講義室に到着。適当に席に座る。使用不可能な席がかなりたくさん設定されていたので、あとから来た人は別の講義室にも移っていった。期末テストの対策を何もしていないように見えるが、これは別に有り余る才能で何とかするやつではなくて、最近この講義と演習で3回分のレポートを提出したから改めて勉強しなくても何とかなるだろうという考えだ。しかしスマホを触りながら周りの会話を聞くに、だんだん不安になってくる。手元に講義資料がないし、Google Classroomにアクセスしようにもスマホには東北大学から付与されたGoogleアカウントを登録していないので、今更講義の内容を振り返ることもできない。あきらめてハーメルンを読み、判決の時を待つ。

しょっぱな、既約元と素元の定義を聞かれて手が止まりそうになるが、何とか捻り出すことができた。結局問題がどれも解けなくなった瞬間はなくて、時間いっぱい考えていられたので、手応えは感じられる。ただ冷静になってカウントするとおよそ半分の問題にしか回答できていない。僕が書くのが遅いのか、そもそも自明なので考察フェーズが存在しないのか、すべて解けることを想定されていないのか。まあ講義資料で見たことあるな～と思いつつ証明を復元できなかったので飛ばした問題もあるので、しっかり勉強していれば書くだけみたいな問題も多そう。

期末テスト終了後、学食に行く。午前12時10分くらいだったが、死ぬほど人がいてびっくりした。意味が分からない。食事のあと、先週木曜日と同様せっかく地下鉄に乗るのだからとゲーセンに行く。今日は先週木曜日の続きで、触っていない譜面を埋める。

maimai・オンゲキとの連動イベントの曲を解禁するため、それぞれ1クレプレイする。オンゲキにアクアテラリウムという東方vocalアレンジが入っていてびっくり、かなり好きな曲で泣きながらプレイした。EXP譜面は何とかなったがMAS譜面はボロボロだった。しかし良い曲なのでOK。調べると2018年から入っていたらしい。気づかなかったか、あるいは当時はまだ知らない曲だったか。

連動イベントの曲は13+が2つで、「Alea jacta est!」は何とかSSSが出たが、「Viyella’s Tears」は無理。

「チャージマン研！」とのコラボイベントで、「殺人レコード恐怖のメロディ」が収録されている。譜面が本当にクソで、嫌になって放置していたのだが、さすがにそろそろSSS乗せておくかと思ってプレイした。

このフリックのリズムが全然わからなくて非常に苦労したが、何とかSSSを出すことができた。フリックのほうは範囲内を全力で擦り、ホールドに集中する。見事に1-0を踏んでしまい、さらに腹が立った。

この譜面の譜面製作者名は「CHUNITHM第16話 殺人レコード恐怖のMASTER」となっていて、具体的に誰かはわからない。これは、上位譜面に見られるような譜面製作者が集結して作り上げた高難度譜面というわけではなくて、譜面製作者に殺害予告などが送られないようにするためであると考えられる。実際プレイしていて不快な気持ちにしかなれない。早く削除されてほしい。

先日解禁した「Cyaegha」をAJした。非常に良い曲だった。最後のフリックで2回散ってそこそこ大変な思いをした。

7時半くらいにゲーセンを離脱し、ラーメンを食べて帰宅。以前は24時間営業だったはずが、感染症対策で午後8時閉店になっていて危なかった。帰り道、電車内でハーメルンを読む。1作読了。

syosetu.org

月曜日から読み始めたが、41話でエタっていてすぐに読み終わった。内容自体は非常に面白かったが、原作イベントとしては諏訪大戦が終わって因幡てゐと出会ったくらいで止まっているので、消化不良気味。似たような作品が読みたいと思って、作品名で検索したところ、「東方乱力録」と「東方青狼伝」が挙げられていた。次は「東方乱力録」を読もう。こちらはArcadiaで連載され、完結している。

障害の影響があった人は今日の小テストでは評価せず、別の課題を出すことにしたらしい。回答も提出したので正直これで評価してもらっていいのだが、何らかの措置を講じてもらうようお願いしたのはこちらなので、ありがとうございますとしか言えない。

週記（2021/01/18-2021/01/24） - kotatsugameの日記

これに関して、ゲーセンにいる間にメールが来ていた。結局小テスト2問のうち当日の講義内容と深く関係があった1問を採点しないことで対応するらしい。僕は逆にそちらのほうしか解けていないが、そういう理由で採点する問題を変えてほしい場合は再度メールを送ってくれ、とのことだ。帰宅してからメールを送った。

サークルのバチャに出場する。CF Round 614。なんだか調子が悪く、C問題は終了1分後に通った。木の頂点を2つ組で持ってDPするが、このときペア(u,v)の更新に「uから見たvの親」と「vから見たuの親」が必要になる。そもそもこのDPにたどり着くまでが遅かったので、焦って適当にmapの添え字にいろいろ持たせてみたところ見事にTLEした。冷静になると添え字ではなく値のほうに紐づけておけばよい。

ABC189のC問題を縮められていた。

atcoder.jp

かなり謎で、どこから@1が出てきたのかわからない。コードテストで適当に試してみても@{0until 1}は@1にアクセスしないのだが……。

水曜日の正午が提出期限のレポートがあるので、着手する。情報理学Ⅱという講義の最終レポートだ。講義スライドに問がいくつか設定されているので、探して解く。探したところ5題あり、うち1つは「カルマンフィルターの実社会における応用例の1つについてA4一枚程度のレポートを書く」もので、これは面倒そうなのでやらない。ほかの4題はただの計算問題なので適当にやる。正直スライドを理解する気はあまりなくて、問の周りに書かれている定義や例を見つつ適当に式変形を行う。

1問よくわからない問題があったので講義動画を確認したところ、スライドには書いていないがmは正である、と言っていた。そういうクリティカルなことは最初から書いておいてほしい。結局それも含めて1時間半程度で完成した。やはり問題を1問無視したのは大きかったようだ。

このツイートを受けて思い出した本があったので、調べてツイートしようとしたが見つからなかった。何もツイートしないのもつまらない気分になったので、見つからなかったことをツイートしたところ、FFの方が似たような話を教えてくださった。

plaza.rakuten.co.jp

布団に入ってハーメルンを読む。明日は正午の期限に間に合うように山に登ってレポート提出しなければならないため、そこそこの時間に起きる必要がある。しかしArcadiaを読み続けてしまい、結局午前4時就寝。

01/27(水)

午前10時半起床。目覚ましによる。起きてすぐは自分がなぜ目覚ましをかけて寝たのかわからずしばらく呆然としていたが、だんだん意識がはっきりしてきた。レポート提出である。

前日は、もう雪も積もっていないようだし、ということで原付での登校も考えたものの、夜雨が降ったようで恐れをなして今日も地下鉄で向かうことにした。提出期限の20分くらい前には提出場所の棟の前に到着し、一緒に出そうと誘い合わせていたたいぺーを待つ。

たいぺーと一緒に提出して昼食を食べようと思っていたが、僕が大学に向かっている最中に起きたらしくてヤバそう。結局合流できたのは午前11時50分のことで、そこから急いで提出場所の研究室前まで行ってレポートを出した。

週記（2021/01/11-2021/01/17） - kotatsugameの日記

結局この日はさらに遅く、たいぺーが地下鉄の駅から出てきたのは提出期限の3分前だった。階段を駆け上がってなんとか間に合わせた。そのあと一緒に昼食を食べたが、時間帯は昨日とほとんど同じなのに、今日は全然人がいなかった。この差は何だったのだろう。たいぺーの誕生日が近いらしいので、購買でお菓子を買ってプレゼントした。

帰りにゲーセンに行く。昨日と同じ理由。Arcadiaを読みたくなってしまったので地下鉄の駅のベンチに座って読んでいたところ、なんやかんやあって、お菓子を買ってもらった。

チュウニズムをプレイする。今日は特にやるべきこともないので、12のスコアが低いものをちょっと伸ばしていく。「風仁雷仁」とか「一触即発☆禅ガール」はAJを出した当時のスコアがそのまま残っていて、それぞれ250点から300点くらい伸ばした。途中キャラ選択のUIが変わっていることに気づいて戸惑った。具体的には、キャラのレベル順フォルダが一定の範囲でまとめられてしまい、レベル10のキャラが多すぎてレベル11とか12のキャラにアクセスするのが難しくなっている。改悪であると感じたが、よく考えるとこれは僕がレベル10でいったん止めてしまう謎のキャラ育成をしているからっぽい。レベル10のキャラだけやたら持っている、みたいな変な人はそんなにいなさそうな気もする。

午後6時くらいになってたいぺーと合流し、しばらく遊んでから昨日と同じラーメン屋に行く。食事後、たいぺーとは別れたが、チュウニズムに関して何となく物足りない気分を感じたので、まだ帰らずゲーセンに戻ってさらにプレイを続けた。14の譜面で未プレイなものを埋め、銀ポゼッションの条件を達成した。OP的にはプラチナポゼッション手前くらいはありそうだが、全曲SSという条件はかなり難しい。今は14の解禁済みの譜面のうち5譜面がSにとどまっている。

そうこうしているうちにサークルのバチャが始まっていて、遅刻した。帰宅してシャワーを浴びると残り1時間くらいだったので、普通に解くだけ解いてバチャ終了後の話し合いに参加することにする。普通に解くと問題につけられたタグが見えてちょっと困った。それの影響もあったと思うが、1時間で4問解けた。

バチャを走った他の人と比べて、A問題のコードの速度にかなり大きな差があった。何かと思って時間をかけてコードを比較したが、結局文字列のsubstrを本当に必要な時以外計算しなかったことが効いたらしい。微妙な枝刈りだと最悪で10^6の2乗オーダーの計算量になりそうなものだが、それでも1500msで通っているのはすごい。D問題は2乗の木DP。久しぶりに見た感じがする。

夜、布団に入ってハーメルンを読む。久しぶりに東方遺骸王を読み返していた。228話から249話にかけて、主人公ライオネル・ブラックモアが月で無双するシーンだ。かなり眠気があったものの、久しぶりに読むと面白いということでギリギリの状態で読み続けていた。そのあともネット小説まとめサイトなどをいろいろ見て、東方の古代スタートものを探したりしていた。

最近読んでいたArcadiaの「東方乱力録」の作者は黒留ハガネさんだったらしい。おすすめのなろう小説まとめで「滅竜山くんの一生　～46億歳、全ての生命と魔の祖～」や「ノーライフ・ライフ」を紹介している、かなり好きな作者さんだった。びっくり。

午前6時頃就寝。

01/28(木)

正午、起床。なんとなく寝足りない気分を感じつつもずっとArcadiaを読んでいた。午後4時くらいに身を起こし、食事したりちょっとyukicoderでゴルフしたりした。

再度布団に転がってArcadiaを読み続ける。午後6時くらいにいったん意識を失い、再度起きると午後11時半だった。今日はCF div.1があるが、あまりの無気力に参加を断念。モゾモゾと起きだし、今週も溜めていた日記を書く。午前4時くらいまでかかって月曜日と火曜日の2日分書いたが、すでに6000文字を超えてしまってびっくりした。

LaTexの数式の記号一覧のサイトをよく使っていたのだが、日付が変わって1/29にアクセスしたらホームページのサービスが終了しており、かなりびっくりした。これからどうしようか困る。よく使いそうな記号が一覧になっていて非常に便利だった。

「U-Page+」サービス提供終了について|お知らせ|So-net

日記を書くのに力尽き、布団に戻ってArcadiaを読んでいたらまた寝落ちした。午前5時だった。

01/29(金)

午前9時半起床。昨日中途半端になっていた日記を書ききる。その後布団に戻ってArcadiaを読んでいた。午後3時頃、「東方乱力録」読了。

SS投稿掲示板

非常に面白かった。これまでいくつか読んできた東方古代スタートものの中でも一番古いもの。作品の評価などを見るに、これが東方オリ主最強TS過去転移ものの嚆矢となったとかならなかったとか。東方オリ主最強TS過去転移ものとは、東方Projectの二次創作であって、原作にないオリジナルの主人公が性別を変えつつ過去に転移し、非常に強い力を持つという作品のこと（のつもり）だ。

実は今日の午後5時が期限のレポートが存在する。期限の1時間半前になってようやく着手。コンピュータグラフィックスという講義の最終レポートで、前回のレポートから今までの講義から数題と、これまでの講義のまとめの問題がある。どれもスライドの文言を抜き出して穴埋めしたり答えたりの非常にヌルいものだが、これまでまともにスライドを読んでいなかったので、そこそこ苦労した。1時間くらいで完成し、提出。この講義はレポートを全部出したので単位は来るだろう。工学部向けの講義を自分の興味本位で取ったものだから、来なくても別に問題のない講義であった。

この勢いで、線形代数学Bのレポートを仕上げにかかる。15回の講義それぞれにレポートが出題されていて、1/20に9回分を、1/24から1/25にかけて5回分を解いて提出していた。

6時間くらいかけて9回ぶんのレポートを錬成し、今日はここまでとする。

週記（2021/01/18-2021/01/24） - kotatsugameの日記

ラスト1回、問題もそこそこ難しく、詰まってしまって放置していた。改めて考えてみたところ、無事解けたので記述。もう1問あって、そちらは最後まで解ききれなかったが、まあこれだけやれば十分だろうという気分になったのでそのまま提出した。これで15回分すべてのレポートを提出したことになり、それ以外の評価点などは存在しないため、おそらく単位は来るだろう。

1/20の日記でも書いていたが、線形代数学Bは必修科目で、僕が4年生になるために絶対に取らなければならない講義だった。1/20の講義の最終回まで一切手を触れていなかったので、いかにも万事休すといった趣であったが、取り掛かるのが一番難しいのであって、1回分錬成してしまえばあとはどんどん出来上がっていく。解放感から、自分のこれまでに得た単位と4年生になるための単位を比較して、今セメスター何が必要かをリストアップしてみた。

このうち、一番上の線形代数学Bは今全レポートを提出したものである。幾何学序論Aは↓なのでOK。ちなみに代数学概論Aとは、毎週金曜日にぐちぐち言っていた課題を当日投稿する講義のことで、これはもしかしたらただただ出来が悪くて落としてしまうかもしれない。

次の月曜日が締め切りで最終課題が出ている講義がある。これについて、成績評価に関するコメントが出ていた。曰く、これまで出した課題5つ（次の月曜日締め切りのものを含む）のうち、未提出または0点の課題が2つ以下で、かつ点数の合計が50点以上の人には少なくとも単位は出します、とのこと。これに照らせば僕はすでに単位が出ることが確定している。

週記（2021/01/18-2021/01/24） - kotatsugameの日記

代数学概論Cは今週火曜日に期末テストがあった講義で、幾何学概論Bは……まだ何もやっていない。2/5にすべての課題の締め切りがある。

かなり眠いし寒いので、しまってあった毛布を引っ張り出して布団に追加した。うっかりくるまってしまい、動けなくなってなろうを読んでいた。午後9時20分、yukicoderが始まるのに合わせて気合を入れて起き上がったところ、脱出に成功した。

yukicoderは全完。門松列というyukicoderの謎概念、嫌いではない。ABCはよい。Dはいじる場所の候補が結構少ないので適当に試すが、ちょっと詰まって考え込んでいたら意識を飛ばしてしまい、時間がかかった。Eは大小関係を固定してトポソ。Fは要素を昇順に見て、門松列としての形で場合分けして頑張ると解ける。

微妙に元気になったので、直後のえでゅふぉにも出たが、5完であまりよくなかった。ABはよい。Cで変な実装をしたらWAになったのでビビったが、実際は実装ではなくロジックの誤り。Dもよい。Eが問題で、まず誤読した問題を解いて時間を徒に溶かしてしまった。

サンプルの説明を読んでようやく誤読に気づくというありさま。そのあとも難しくて、僕の考えでは頂点をまとめることで辺を一気に張るトポロジカルソートをするのだが、このとき辺の削除をする必要性が生じる。次数カウントを無理やり弄って何とかしようとし、2WA生やしてどうにかこうにか通した。解説を読んだところ、パターンが互いに異なるためそれほど辺の本数は多くならず、わざわざ一気に張らなくてもよかったらしい。パターンとしてありうる種類数が少なそうに見えたので、ダブりがあると認識してしまっていたが、冷静になるとパターンは27^4通りあって十分多い。

Vimのコードゴルフが進んでいた。

夜中FのコードゴルフをしていたらA問題を縮められていた。Vimは試して縮まないと判断したが、全然なってなかったらしい。

週記（2021/01/18-2021/01/24） - kotatsugameの日記

atcoder.jp

このコードなのだが、Yes\nNoの間にpやPを2回行い、g*でそのうちどちらかにカーソル移動し、そこから3行削除することでYesとNoの一方を残すというアルゴリズムである。これは実は新手だったようで、適用できるものがいくつか縮んでいた。

さらにもう一つ。:se ri（:set revinsの省略形）とすると、挿入モードでの文字の挿入が通常と逆向きになる。このときレジスタの文字を挿入しようとすると逆順に入るらしく、その性質を用いると、これまで外部コマンドrevで実現していたような文字列の反転が短く書ける。これ関係でも2問ほど大幅に縮んでいた。

options - Vim日本語ドキュメント

こどふぉの直前にyukicoderでWAを生やしていたので、デバッグしていたが、全然わからなくなって布団に寝転ぶ。即座に寝落ちした。午前2時半であった。

01/30(土)

午前8時半起床。少しなろうを読んでいたが、やっぱりまだ寝ておくべきだろうという気持ちになって入眠を試みたところ、成功。追加で午後1時まで寝ていた。夢を見た。

昨日寝る直前にしていたデバッグに戻る。よく見ると変数名が違っていた。グラフHがあって、強連結成分分解した後のグラフをGとしていたが、計算にはHを使用していた。デバッグ中、試しに強連結成分分解をしないコードを書いていたところ、発覚した。

さらにyukicoderを数問解いて、ランキング4位に躍り出る。3位までは十問ちょっとで何とかなりそうな気がするが、それより上は100問単位で差が開いている。

1/26に縮められたABC189のC問題を縮め返した。最初はAWKで試していたが、お話にならなかったのでPerlに集中。popやpushの代わりに末尾のインデックスを管理する方法で、そのままでは短くならないが、ここで符号を反転して直接変数名にする（$-1や$-2を使う）と縮んだ。

atcoder.jp

ラノベを1冊読んだ。「転生魔王の大誤算2」。これまでたくさんラノベを書いてきた作家さんらしく、文章がこなれていて謎の語彙も豊富。話も面白いが、会話文のノリがキツい。主人公の魔王は自分がメチャクチャ強いのを自覚しておらず、周りにナメられないように必死になって頑張っていて、周りはメチャクチャ強い魔王様を信奉しているという設定。書いていて思ったが「ひきこまり吸血姫の悶々」とほとんど同じに見える。流行りなのか？魔王なら魔王らしく泰然自若としていてほしいと感じるが、そういう何のひねりもない魔王像はもはやありきたりすぎるのかもしれない。

ABC190に出た。2位だった。ABC189から2連続。Dで条件を間違えて必要なコードを消すなど迷走していたのと、あとはEの手数の多さにやられた感じ。

Aは難しい。最初の提出ではc?a>=b:a>bをさらに三項演算子の条件式に入れるコードを書いた。書いててa>b-cであることに気づき、すぐさまdcでコードゴルフ。現在も最短である。

BCはやるだけ。Dは等差数列の和の式を書くといつもの約数全探索だとわかる。Eはグラフから特定の頂点を抜き出して巡回セールスマン問題っぽいことをするやつで、頂点間の距離を求めるのにそれぞれの点からBFSなりDijkstraなりを行う。こういう面倒なだけの問題は何度も何度も見たことがある。Fもやるだけ。

コンテスト終了後に確認すると、Bのdc解が存在した。かなり上手いコード。何とか隙を見つけて1B縮めた。Cはbit全探索の代わりにproductメソッドを使うのがよさげ。Dは謎で、dcではTLEするためそれ以外を考える。Ruby50B、Perl45Bと来て、この日記を書きながらチェックしたところAWK50Bがあったので縮めてみたら44Bになった。これが現在の最短。Eのゴルフはしない。FはこれくらいだとBITを直接書いたほうが短くなって、とりあえずRuby132B。

そのあとABC190の動画編集を始めた。今回は全完まで16分44秒なので、カット・倍速なしで垂れ流しつつ合間合間でコードゴルフの話をするという、以前から考えていたスタイルが実現できそう。下のようなことを日記に書いていたが、これを受けて考えたスタイル。

等倍なら時間の感覚がある。しかしE問題とF問題で倍速を使用し、こちらは時間の感覚が破壊されてしまうため、なんとなく臨場感がなくなってしまう。かといってカットを多用するのは競プロの試行錯誤の過程を全部ないがしろにしてしまう感じがしてどうだろう……。悩ましいところだ。

週記（2020/12/14-2020/12/20） - kotatsugameの日記

C問題の途中でいったん切り上げ、日記を書いてハーメルンを読む。そこそこで切り上げ、布団に入り、コードゴルフの新手らしきもの（短くなるケースはなさそうだった）について考えを巡らせていたところ、うっかり寝落ちしてしまった。午前5時だった。

01/31(日)

正午くらいに目を覚ます。午後2時くらいまで布団でハーメルンを読んでいた。1作読了。

syosetu.org

東方二次創作のおすすめを列挙しているサイトから見つけてきたものだが、書いてある紹介文と内容が異なっていた。面白かったからよいが。しばらく後で、紹介文をそのまま検索してみると、合致する内容のものを見つけることができたが、そちらはたった2話しかなく、短編で完結という感じでもなかったので、適当に読んでおいた。

そのあと再度眠りに落ち、今度は午後4時に起床。食事をしてから動画編集、昨日の続きから進める。

完成したのは午前1時半だった。昨日から作業していることを考えると、今回のものはかなり時間がかかったようだ。

コーディングの合間にコードゴルフの話をする際、画面をゆっくり拡大・縮小して場所を開け、そこにテキストでコードを表示して見せる、という手法を採った。そもそも動画の3:48くらいにあるようなヌルッとした動きがゆっくりムービーメーカーで簡単に作れることを知らなかった。今考えてみれば、左下に寄せるよりは中央下に寄せたほうがよかったかもしれない。

また、これまではコードの特定の箇所に言及するとき、そこを無理やり読み上げるということをしていたが、今回は下に線を引いたり、コードの該当箇所以外をスペースに置き換えて一時的に隠したりしてみた。特に、スペースに置き換えるやり方は、例えば動画の11:29からのような、コードを内側から外側に向かって読み解いていくようなシーンでいい感じに表現できたのではないかと思っている（自画自賛）。

D問題のAWKによるコードを解説するパートを作成した後、そのコードが縮むことに気づいて、再度作りなおしになったのは結構辛かった。結局そのコードも動画の公開直後に縮められた（4Bも！）ので、踏んだり蹴ったりという感じだ。

カット・倍速なしでは、E問題のコーディングのたった6分間ですら、コードゴルフを微に入り細を穿って説明しなければ埋まらなかった。やはりこの編集スタイルは無理がある。ABC189は全完に24分くらいかかっているので、一度はこれもカット・倍速なしで編集しようとしたが、諦めることにした。そもそもいつABC189のスクリーンキャプチャがゆっくり実況になるかはわからないが。

動画編集に関しては以上である。D問題の縮められたコードを読んでおこう、と思ったらアルゴリズムの改善があってさらに4B縮んでいた。

atcoder.jp

このツイートをふぁぼっていて短くなることに気づいていないのはダメ。コード自体は非常にシンプルで、見ていて悔しくなる形をしている。

1月最終日なので読書の集計をした。今年はこんな感じのフォーマットでツイートしていこう。

今月の後半はハーメルンに全てを破壊されていた。それがなかったとしても、やはり1日1冊読むのは無謀で、今年は積読の増減を観察することにした。スタート時点、つまり今現在はラノベばっかり400冊くらいある。一時期古本サイトでシリーズまるまる買うのにハマっていたのが、一生残っている。

週記（2021/01/18-2021/01/24）

01/18(月)

午前6時、腹を壊して起床。トイレから帰ってきて布団に入ったが、うっかりTwitterやハーメルンを開いてしまう。1作読了。

syosetu.org

面白かった。幻想入りしてからはシュッと終ってしまった感じだが、主人公を周りのキャラクターから見た話なども多くて満足。

次の月曜日が締め切りで最終課題が出ている講義がある。これについて、成績評価に関するコメントが出ていた。曰く、これまで出した課題5つ（次の月曜日締め切りのものを含む）のうち、未提出または0点の課題が2つ以下で、かつ点数の合計が50点以上の人には少なくとも単位は出します、とのこと。これに照らせば僕はすでに単位が出ることが確定している。

まあ単位が確定しているなら最終課題やらなくてもいいかな……という気分になる。課題を、教員を用いて自分の実力を試す場と考えているような人にとっては別だが、僕はそんな意識が高くないので、出さなくてもよい課題は出さない。

こういう単位取得に関するコメントを掲出する理由は何だろう、というようなツイートを目にして少し考えてみた。受講者のうちいくらかが最終課題の提出を止めると、僕らみたいな学部生の書いたレポートを読む量が減るはず。これはおそらく教員のメリットになる。

bashのdcコマンドについて、僕のメイン機では1.3.95がインストールされている。AtCoderでは1.4.1で、この違いはかなり大きい。コードゴルフ関連でいろいろ便利になっており、週記で何度か言及したこともあるかもしれない。そういう関係で、これまでdcのコードゴルフはいつもコードテストで行っていたが、さすがに手元に用意しておくべきだろうと考えて、インストールを試みる。

最初のmakeは失敗した。ダイイングメッセージを読むとmakeinfoがなくて落ちているらしい。ということで入れる。僕はCygwinを使っているので、こういうのを入れるにはyumとかapt-getではなく、setup.exeを経由するのがデフォルト。setup.exeは実行ごとにほかのファイルもアップデートする。久しぶりに実行したので、例えばPython3のバージョンが3.8に上がっていたりと時間の流れを感じる。

ともかくmakeinfoを入れることに成功し、再度makeしたところ成功。ただ以前からのdcも残っていて、ファイルの場所の関係で古いほうを優先的に使用しているようだったので、aliasで対処することにする。dcを実行すると、今入れたほうのファイルへのフルパスを直接叩く。古いほうを消せばいいのでは？と思われるかもしれないが、yukicoderはいまだに1.3.95なので、需要が皆無というわけではない。

さて、いろいろやった後にコードを書こうとVimを立ち上げると、表示が微妙に変わってしまっていることに気づいた。

以前のキャプチャ画像は録画からとってきたものなので、画像サイズが違って見にくいが、色がついた文字が全体的に太く表示されている。できれば元に戻したいので、いろいろ頑張ってみた。

「勝手に太字」みたいなキーワードで検索してみると、highlight設定からboldを全部消すとよい、みたいなのが見つかる。どうやら現在の表示はctermの値が効いているようなので、cterm=NONEとしてみたところ、確かに太字は解除されたが、色もより暗いものに変わってしまった。

次に、TERM変数を設定しつつVimを起動するとよい、みたいな話を見つけたので、$ TERM=xterm-256color vimとして起動してみる。文字が太くなるのは解消されたが、色設定が全く別物になっていて困る。

色設定を変えたらもとに戻るんじゃないかと思って、デフォルトで付属しているものからこれまで使っていた色設定（一度も変更していないので、何かがデフォルトになっているはずだと考えた）から探す。どうやらron.vimがそれに該当するようだが、:colorscheme ronとしても太字なのは変わらなかった。（ちなみにこのときTERM変数は設定していない。設定してみればよかったかもしれない。）

TERM変数を設定する関連で、t_Coというオプションの値を変えるとよいというのを見つけて、8から16に変えてみた。ほとんど元通りになったように思えたが、visualモード時の選択範囲の表示がやたら薄かったりして微妙な気分になる。t_Coはターミナルで使用できる色の種類数（？）を決めるオプションらしく、これが少ない状況下においては表示をよりくっきりさせようとして太字になっていたのではないだろうか。

もう少し調べていたが、さすがにもう面倒になってしまったので、大まかにはt_Coの値を変更することで対処し、残りの細かい部分は個別にhighlight設定を変えることにした。visualモードに関しては、以前のように白色を強くすると後ろの文字が見えなくなることに気づいたので、薄いままにしておく。highlight設定を個別に変えるのにも苦労した。.vimrcに書くだけだと効かない。:highlight verboseで確認したところ、.vimrcのあとにsyncolor.vimというファイルから書き換えられるらしい。これも調べたところ、~/.vim/after/syntax/syncolor.vimで変更することで、元のsyncolor.vimの設定を上書きできるようだ。

今日が期限のレポートが手つかずで残っている。しなければならない。今回はtexで書くことにする。今回の問題はかなり難しいと感じた。

大問を2つ終わらせた段階で眠気覚ましにシャワーを浴び、サークルの解説会に出る。今週の活動は先週できなかったぶんを発表するので、特にスライドの用意などを新しくする必要はなかった。滞りなく終了し、スライドの公開やサークルのwebサイトへのページ作成、サークルの公式Twitterでツイート、までパパッと終わらせる。

レポートに戻る。さらに1問解けて、これでレポート提出の最低限は達成できたようだ。もう1問解こうと頑張ってみたが、どうにもわからなかったので、その部分については少しだけ書いて提出することにする。いうなれば3完半か。半分も解けていないような気がする。

少しコードゴルフをした後、先週の週記の残りを書いて公開した。これまでは広義日曜日には投稿できていたが、生活リズムの乱れやレポート提出などでかなり遅れてしまった。本当は先週の日曜日は生活リズムの狭間に消し去るつもりだったのが、うっかりTROCに出てしまったせい。

投稿するといくつか言及してくれる人がいてうれしくなった。日記という体裁をとっているが、人に見られることを意識した文章を書いている。読まれているのがわかるとうれしい。

午前3時、就寝。

01/19(火)

午前11時起床。ゴミを出す。僕が住んでいるあたりは回収がやたら遅いので、この時間に出してもまだごみ収集車が来ていない。こういうのも住所バレにつながるんだなあ。

せっかく昼から活動できるような生活リズムになっているので、学食で昼ご飯を食べた後、市街地に出た。まず本屋に行って本を買う。

次に、ゲーセンに行く。チュウニズムの大型アップデートを2日後に控え、今日は削除される譜面に関係する称号を集める作業をした。チュウニズムにおいて一定の条件を満たす（例えばある譜面でSSSを出す、あるいはある譜面の全難易度をプレイする等）ことで得られる称号は、その譜面が消えても使えなくなったりはしないが、取得機会は消えてしまう。複数人でマッチングする必要のある称号は取れないが、それ以外をあらかた集めた。残りはAJ称号だけである。Elemental CreationをAJするのはさすがに難しいだろうが、Evansは1-0出したことがあるし行けるのではないか？と思い、粘着することに決めた。

出たのはいいが、5時間くらいかかった。エアーが多くてかなり疲れる。省エネのつもりでエアーを上げるのを適当にしていたところ、序盤のエアーでアタックを出し、そのまま残りをAJしてしまったことがあって、かなりつらかった。この週記が公開される頃には削除される譜面だが、一応何を考えてプレイしたか記録しておこう。

f:id:kotatsugame:20210123152017p:plain
55小節

この配置は頻出だが、僕はかなり苦手にしている。今回もだんだん癖がついて勝率が下がってきたので、擦りに切り替えた。周りはエアーの上げ下ろしなどもあってかなり忙しく手を動かしているが、その意識のまま擦ると折り返しでアタックが出る。めちゃくちゃ遅め意識。

f:id:kotatsugame:20210123151904p:plain
57-58小節

58小節の最初の赤タップのうち、左のほうを巻き込む。巻き込んでいることに気づくのにまず20プレイくらいかかった。スライド持ち替えによる非交差運指をお勧めされたので試してみたが、どうにも慣れない。スライドをとった左手で直後にもう一回タップするのが特に難しい。結局、交差はするが、手を途中で固定してスライドをなぞらないようにすることで対処した。

f:id:kotatsugame:20210123152821p:plain
75-76小節

これだけ見ると何てことない配置だが、この直後から右手8分連打が始まり、入りが非常に難しい。擦りを試してみたが、なんとも微妙な速さのため折り返しのあたりでアタックが出た。むしろ何も考えないほうが勝率が高いが、癖がつくとまずいのでそうも言っていられない。結局右手の赤タップ3つをガチガチに意識して、直後の黄タップから切り替えて連打するとそこそこうまくいくようになった。

f:id:kotatsugame:20210123153421p:plain
79小節

言わずと知れた最難関。ここで10回くらいAJを逃した。両手トリルは、ノーツがずれているとか以前にそもそも追いつかなくなってダメ。遅めの全押しで餡蜜してみたが、直前の配置から微妙に間が開くこともあってどうにもタイミングがつかめなかった。結局気合いで押した。左手トリル6回+右手8分3回、直後に手を入れ替えてもう一度。ここは逆に何も考えない状態では絶対に通らなくて、確固たる意志を持ってトリルに集中しなければならない。焦りすぎるとそのあとの黄タップも難しくなる。

休憩のため立ち食いそばを食べ、ゲーセンに戻ると、数学科の友人と会った。来年度のゼミ選択についてしばらく話した。別れた後さらに少しチュウニズムをして、帰宅。

何とか間に合ったのでこどふぉdiv.2に出る。5完8位。Eで2回もWAを生やしたのでかなり破滅した気がしていたが、そうではなかったようだ。

Aは上の桁から貪欲に決める。Bは難しいが、冷静になると素数p、qがあってp^3またはpqのみ考えればよい。コンテスト後のTLによれば、さらにベルトランの定理を用いることでpqのみでよいことが証明できる（つまり、p>=d+1のもとでp+d<=q<=p^2なるqが存在することが分かればよくて、これを示せる）。

Cは最大のものを取っていけばよい。実装に悩んだ。TLは1secである。数の出現回数をカウントすると、毎ケースの初期化に時間がかかって間に合わなさそう。結局multisetでlogをつけて提出したが、かなり時間に余裕をもって間に合った。また、出現回数のカウントでも、変更したところだけゼロクリアするようにすれば、毎ケースの初期化がO(N)で済むらしい。

Dは左と右から累積的に調べておいて、各スワップごとにそれを用いて定数時間で判定すればよい。Eは最初の提出で考慮できていたことが2回目の提出で考慮できておらず、2WA。置換とか入れ替えの話は頭が壊れがちで、正しくイメージしにくい。出力に関しても毎回紙に書いて計算しないと正しいかわからない。

布団に入ってしばらくハーメルンを読んでいた。午前5時就寝。

01/20(水)

午後6時起床。ここ最近の睡眠負債が一気に来て生活リズムが終了した。布団でラノベを読んでいたところ、サークルのバチャをブッチしてしまった。

まず1冊。「デスゲームから始めるMMOスローライフ」の4巻。2巻と3巻も、日記に書いてはいないだけで読んでいた。内容は1巻からずっと変わらず一生ヒロインとイチャイチャしていて、4巻のラストも特に何かあるわけではなかった。

次に「江戸の花魁と入れ替わったので、花街の頂点を目指してみる」。かなり面白かった。体ごと持ってきたらしく、現代で摂取したワクチンが有効らしい。ワクチンの江戸時代におけるチートっぷりを話し始めてびっくりした。天然痘ウイルスに対しては逆に無力なので、自力で種痘をしていた。多分この描写があって冒頭に注意書き「フィクションなので作中の医療行為を真似しないでください」が入ったのだろう。まあそれは本題ではない。

もう日付が変わってしまった。1/22提出のレポートがあるが、あんまりやる気はない。これはまた明日頑張ることにするが、じゃあ今日は動画編集でもするかというと、そううかうかもしていられなさそう。線形代数学Bという必修科目を履修していて、これは今セメスターで何が何でも取らなければならない単位だが、毎週出されている課題に期限が設けられていないこともあって、いまだに何一つやっていない。これのまずさがだんだん分かってきて自分の意識を占有しだしたので、進めることにした。

さすがに本来であれば1年生が取る講義だけあって、内容自体はかなり簡単。ほかの講義などでも触れた内容なので既知である気もするが、そんな自信があるわけではないので、念のため講義動画も見つつビシバシと手書きレポートを書いていく。

6時間くらいかけて9回ぶんのレポートを錬成し、今日はここまでとする。

布団に入ってハーメルンを読んでいたが、どうにも腹が減って眠れないのでパックご飯を食べた。世間はすでに木曜日で、チュウニズムの大型アップデートは完了している。新曲の譜面動画が回ってくるのでいろいろ見ていた。AttraqtiAという曲があって、ジャケ絵の特徴的な髪・目からEnjiさんの手になるものだとわかる。実際ArcaeaのWikiではEnjiさんと明記してあったので、どこかに公式情報があったのだろう。EnjiさんのTwitterやPixivには特にそういう投稿は見当たらなかったが。

正午、就寝。

01/21(木)

午後11時、起床。昨日は主観的には水曜日で、金曜日提出のレポートまではまだ2日あるという認識でいたが、起きてから冷静になってみると、木曜日はあってないようなものなので実質1日しかない。しかも山に登って数学科の事務室まで提出しに行かなければならない。レポート問題にはこの期限に関して一切書かれていないが、これまでの経験からどれだけ遅くても午後5時だろうとあたりがつく。残り18時間しかない。

取り掛かる気分になれないので、しばらくGoogle Classroomを眺めて時間をつぶしていた。よく見ると一切手を付けていない科目は昨日やり始めた線形代数学Bだけではない。非常にまずいようだ。

食事して、ようやっと取り掛かる。これに関してもTexで書くことにしよう。推敲が簡単なのがかなりうれしくて、図表を挿入する必要がないならTexで書くのは便利。内容自体は、演習のレポートをすでに2回こなしているので何とかわかる。最初の2問は結構簡単だったが、3問目からもう逃げたくなってくる。何とか5問くらい解いたところで完全に飽きて、布団に寝っ転がってハーメルンを読んでいた。

syosetu.org

これは過去編がメインで幻想入りしたあとすぐに完結を迎えてしまったが、どうやら続きの話、つまり幻想郷での出来事は別の作品で描かれているらしい。今すぐ読みたいが、さすがにレポートを書かないとまずいのでぐっとこらえる。

とりあえず全部で7問あるうちの6問を解いた。実は金曜2限は今日が最終回で、授業の後半は小テストがあるらしい。これまで週記で毎週「課題を当日の朝に投稿する」など愚痴を言っていた講義だ。最後の小テストもいっちょやってやるかと思ってGoogle Classroomを開こうとすると、読み込みが終わらない。かなり焦ったが、とりあえず自分だけの問題でないことを確認しておこうとTwitterで検索したところ、ほかにもGoogle Classroomが見られなくなった人がいる。親切な方からステータスダッシュボードのURLをもらったので見てみると、確かに障害が発生しているらしい。このことを教員にメールして、何らかの対処を願う。

結局僕の環境では午前11時頃から見られるようになったので、最後の講義資料も見れるし、小テストにも問題なく回答できた（ただし解けたとは言っていない）。これでこの講義ともおさらばか～と気を抜いていたところ、教員からメールが来た。障害の影響があった人は今日の小テストでは評価せず、別の課題を出すことにしたらしい。回答も提出したので正直これで評価してもらっていいのだが、何らかの措置を講じてもらうようお願いしたのはこちらなので、ありがとうございますとしか言えない。

レポートの作業に戻る。最後の1問はどうにもわからないが、諦めることにする。印刷の前に文章全体を読み直したところ、結構直すべき箇所が見つかったので直す。普段はこういう読み直しをしている時間もやる気もないので、いつも書きあがったら即座に提出している。直し終わったので印刷し、ホッチキスで止め、地下鉄に乗って提出しに行く。せっかく地下鉄に乗るのだから、と音ゲーのための軍手なども持って出た。

もし提出期限が正午とかだったらヤバいな～と思っていたが、期限は午後5時だった。提出に成功。山の上の学食は午後1時半で閉まったらしく、購買でお菓子を買って済ませる。また地下鉄に乗って今度は市街地のほうまで出る。

さすがにお菓子だけでは腹がふくれないので、立ち食いそば屋で食事する。そのあと本屋に行った。火曜日に行ってからそれほど日が開いていないが、20日あたり発売の富士見ファンタジア文庫などもあり、買うべき新刊があることは確認していた。しかし置いていなかったので、結局何も買わずに出た。よく行く本屋はなぜか富士見ファンタジア文庫を全然置かない（新刊が入っていても棚差しになっている）のだが、何か理由があるのだろうか。

ゲーセンに行く。木曜日が大型アップデートで、今は世間的には金曜日だが、人が全然いなかった。アップデート直前のプレイでずっとEvansをプレイしていて、その譜面が削除された影響でリセント枠がガタ落ちしたのか、レートが14.56になっていてかなりびっくりした。

新曲を埋めていく。最初のほうはかなり眠くて精度が全然取れなかったが、やっているうちに慣れてきていい感じになった。この日は4時間半くらいで帰宅。新曲を触るよりもスコア詰めに集中した。13のAJが4つ、13+のSSSが1つ増えた。Grievous Ladyで1-0を出してしまった。AJが出るとは思っていないので、最後のほうは実は譜面がよく見えていない。

夜ごはんも立ち食いそばにしようかと考えたが、以前から気になっていたラーメン屋に入れそうだったので入る。

おいしいとは思うが、卓上に一切調味料を置かなかったり、謎の水を使用していたりと意識の高さが肌に合わない。

家に帰って布団に倒れこむ。すぐにでも眠れそうな眠気だが、やはり汗をかいていることもあってシャワーくらい浴びておきたい気持ちになる。何とか浴びて、布団に入ってちょっとハーメルンを開いたところ、一瞬で寝落ちした。午後8時過ぎだった。

01/22(金)

生活リズムの狭間に消えた。

01/23(土)

午前6時、目を覚ます。もっと寝たいが、なんとなくハーメルンを読み始めてしまい、眠れなかった。木曜日に読了したやつの続編を読んでいたが、途中で同じ作者の別の作品に浮気して、そちらは16話で完結していたのでサッと読み終わった。

syosetu.org

これを読み終わったことを切っ掛けとして布団から身を起こす。正午だった。食事して日記を書く。今週もかなり溜めてしまっており、3時間くらい書いていた。生協から弁当の配達が来たので受け取り、日記を書くのも一段落し、眠気も結構すごいことになってきたので、ABCに備えていったん仮眠をとることにする。布団に入ってなぜか1時間くらいハーメルンを読み、午後6時くらいに就寝。

午後8時、目覚ましで起床に成功。相変わらずかなり眠いが、この上さらに寝るのはまずい。ハーメルンを読んで何とか耐える。1作読了。

syosetu.org

木曜日に読了したやつの続編である。未完のままエタっている。

ABC189に出る。23分全完で2位。スクリーンを録画していた。録画して出場したABCとしては最高の出来だったので、課題が一段落して動画編集するタイミングができたら、まずこれを編集するのもよさそうだ。

AはFA。こういうのはsedでやるのがよくて、他の言語も短くはならなさそう。BとCはやる。Dはかなり簡単な式になる。Eは難しい。最初、とりあえず回転だけ実装しようとして2x2行列を持っていたが、それではダメなことに気づいて3x3行列になった。配列ではなく、個々の係数をそれぞれ変数に持つ。さすがに9個持つのはまずいが、よく観察すると上の2x3の部分しか変化しないため、そこの値を6つの変数で管理すればよい。提出したところ600msかかってびっくりした。おそらく入出力だろう。Fは何回も見たことがある、期待値DPを1次式の形で行うやつ。

1位とは4分、3位とは6分差があって、集団から1歩抜けた結果でうれしい。2位を取れたのも今回は喜ばしくて、順位によるビンゴは8位を残すのみとなった。

F問題の誤差評価が難しいという話題を目にした。

コードゴルフに関する話。B問題はdcで解けるので、これが一番短くなる。30B。ただ、-1を出力する切り替えに余計な手間をかけている気がしてならない。縮みそうな気配はある。C問題はO(N^2)解法ではそもそもPyPyしか通らない。Pythonゴルフをチマチマやっていたところ、最大長方形のアルゴリズムをRubyで実装したコードに一瞬で抜かされた。アルゴリズムをパクってPerlで書き直したところ90Bまで縮んで、今のところはこれが最短。DはRubyでもPerlでも25Bになって、まあこれで終わりかな……と思っていたらRubyの24Bコードに抜かされた。文字列を文字数で分類することで、直接数値として扱えるようになっている。EとFはゴルフしていない。

夜中FのコードゴルフをしていたらA問題を縮められていた。Vimは試して縮まないと判断したが、全然なってなかったらしい。

布団に入ってハーメルンを読む。午前5時就寝。

01/24(日)

正午、起床。今日はAtCoderもこどふぉもない週末。ToDoリストに入っているものを消化する。

まず、サークル紹介パンフレットの原稿を提出する。昨年のものをほとんどそのまま使うが、それもまた更に昔のもの（碧黴さん作成）をほとんど丸写しして作った覚えがある。昨年は文章の位置なども多少手直ししたはずだが、今年は活動実績と活動内容だけ書き換えるにとどまった。

今年はオンサイトもなければICPCアジア地区横浜大会も開催前で、活動実績に書くことがない。最初は昨年の実績をそのまま書いていたが、さすがにまずいだろうということでホスフィンと相談した結果、今年のICPC予選の結果も書いておくことにした。僕の印象として予選でn位と横浜大会でn位というのの間にあまり差があるとは思わないが、非競プロerから見たときには予選の実績は劣って見えるかもしれない。ほかにも、個人の実績について、順位だけ見るならば企業コンの1桁位が存在するが、ここにはオンサイトのことを書いておきたいだろうとこだわって昨年と同じく第二回全統プ王を書いている。

活動内容にはオンラインが主体であることを書いた。昨年の原稿提出はちょうど1年前の1月終わりで、まだ新型コロナウイルスが騒がれておらず、教室を借りて集まると書かれていた。結局今年度はICPC予選以外では一切集まらなかった。

次にレポートを書く。今週月曜日の日記に「次の月曜日が締め切りで最終課題が出ている講義がある」と書いていたが、この課題を終わらせた。月曜日の時点でこの講義の単位は確定しており、やる気がないなどと書いていたが、なんとなく興が乗ったのでレポートを書いた。謎。

なんとなく眠くなってきたので布団に入り、ずっとハーメルンを読んでいた。途中TechFULからアマギフが1000円届いた。午後7時前にいったん寝落ちし、次に起きたのが午後11時だった。

布団でゴロゴロしている間に昨日のB問題が縮められていた。28B。

atcoder.jp

出力する値を-2する必要がある。この-2を、特別な出力-1の場合にも使おうとしたとき、どうにかして1を用意する必要がある。ここで差がついたようだ。まず前提として、vして0が残るか消えるかで場合分けができる。

僕の30Bのコードでは、まずスタックにx+1 xを置いておく。x-2または-1が出力すべき値だ。vして0が残る場合はx-0-2を、消える場合は(x+1)-x-2を出力していた。上のコードでは、わざわざx+1を置いていない。0が残る場合は0Rでxを持ってくる、消える場合はzRで1を持ってくる、最後に2を引く、で答えを出力している。1をスタックの下のほうから持ってくるという発想に度肝を抜かれた。そこに1があることは、言われてみなければわからない。

別のレポートを書き進める。線形空間の基底を取って{v_1,...,v_n}などと書くとき、n==0となるのは許されるのか？どれくらい場合分けしておけばいいのかわからない。これに関しては許されるだろうと思って書いたが、ほかにも0本の一次独立なベクトルに適当にベクトルを付け加えて基底にする操作が必要になって、これはちょっと微妙そうだなと思って場合分けした。記述量が倍になってげんなり。もしかしたらいらなかったかもしれない。

解き進めているうちに問題を誤読したらしく、詰まってしまって嫌になったので布団に入る。ハーメルンを読んでいたら午前5時くらいに寝落ちした。

週記（2021/01/11-2021/01/17）

01/11(月)

先週の週記を投稿してから寝るまでの話。これ毎週書いてる気がするな。

実は、「前に1進む確率がpなら期待値は1/p」と「後ろ向きならx_i-x_to+1のコストで戻ってこれると考えてよい」でO(N)で計算できるらしい。

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

これに関して、じゅぴろさんのブログ・ソースコードを読んだり教えを乞うたりして一通りの理解が得られた。自分の考察とともに書き記しておこう。dp_iはiまで行くときの期待値、p_jはjが出る確率、また以下ではiがfixされていて、dはiからi+1に進むための出目とする。

まず、自分が考えていた、左辺と右辺に同じ文字を置かない計算方法について。iからi+1に進む確率がp_dのとき、その回数の期待値は1/p_dである。つまり、1/p_d-1回はどこか別の場所に戻ってから再度iまでたどり着いていることになって、 dp_{i+1}=dp_i+1+(\frac{1}{p_d}-1) \sum_{j\ne d} \frac{p_j}{1-p_d} (dp_i-dp_{戻る位置}+1)が得られる。

次に、じゅぴろさんから教えてもらったもの。戻ったところから直接i+1に行くための式を立てることにより、 dp_{i+1}=dp_i+p_d+\sum_{j\ne d} p_j(dp_{i+1}-dp_{戻る位置}+1)が得られる。

どちらも\sum p=1を用いて式変形すると同じ式になる。以下にじゅぴろさんのブログへのリンクを貼っておく。

jupiro.hatenablog.com

週記を公開したところ、`の使い方が気になるという言及があった。僕は僕の感覚で使っているので、厳密にソースコードに該当する箇所以外でも多用している。特に直すつもりはない。あと、普通の改行が存在せず常に段落分けしていることも気になるが、これは普通の改行を書くのが面倒（空白2個を入れる必要がある）だからである。

午後2時に就寝し、午後6時起床。目覚ましによるものである。昨日立てたIssueについて、良さそうというコメントと修正の方針をもらった。書いておいたコードもそういう修正をしていたので、プルリクを送る。

github.com

サークル解説会の準備が一切できていないので、する。ABC187のD-F問題の解説スライドを作成したところで午後8時になり、Google Meetを開いて参加者を待ったが、10分くらい誰も来なかったので終了した。せっかく作ったスライドは来週に回す。もしかしたら大学はすでに期末テスト・課題ラッシュなのかもしれない。いまだに中高生時代の感覚のままなのでそういうものは2月の終わりにあると感じてしまい、わからない。

ラノベを読んでいたら送ったプルリクがマージされた。

先週の週記を受けて、sugarknriさんから(a+sqrt(b))^nを求める問題を3問紹介されていたので、うち2問だけ解いた。Google Code Jamの問題はあまり解く気がないので無視した。

https://projecteuler.net/problem=721

https://onlinejudge.u-aizu.ac.jp/challenges/sources/VPC/WUPC/3162

水曜日提出のレポートがあるがやる気が一切出ない。いやになって布団に転がる。次のようなツイートをしたりハーメルンを読んだりしていたら、午前2時のツイートを最後に寝てしまった。

01/12(火)

午前8時半起床。外を見ると雪が降っていてびっくり。

昼頃チュウニズムの大型アップデートの告知が来た。これまではPOPS&ANIMEのフォルダからしか曲が消えていなかったのに、今になって初めてVARIETYにジャンル分けされていたコナミ音ゲーからの移植曲が消え始めた。曲に興味はないが、未AJの譜面が消えるのはちょっと嫌な気もする。せっかくなので消える前にAJ称号を狙っておきたいが、それまでにゲーセンに行く機会はあるだろうか。

途中午後4時半から午後8時くらいにかけて意識を失っていたが、結局この日は午前1時までずっと布団の上でハーメルンを読んでいた。1作読み終わった。

syosetu.org

「古代スタート」というタグで検索したものから1つ。非常に面白かった。「主人公が世界で一番長生き」という設定だけでパスタが3皿くらいいける。主人公の男オリキャラに原作キャラが好意を寄せる描写は、二次創作でも読む人を選ぶのかもしれないなと感じた。東方Projectの原作に特に思い入れはないため、僕は積極的に受け入れることができた。

「古代スタート」タグのハーメルンは大体東方Projectの二次創作であるように見える。また別の作品をあさりそうになったが、強い意志で布団を這い出てレポートに着手しようとする。しかし食事をしたり淫夢実況を見たりしてしまい、提出期限の正午まで9時間くらいしかなくなった。

www.nicovideo.jp

たいぺー曰く、今回はそれほど難しくないとのこと。講義スライドは6回ぶんあったが、ざっと眺めて問題になっている場所だけ抜き出したところ、1つを除いて証明問題だった。先にそれを片付ける。

1つは定義式を見てもよくわからないし、講義の録画を聞いても「やるだけ」としか言われてなかったので、よくわからない式を書いてお茶を濁してしまった。しかし他の2問はすんなりできたので拍子抜け。

このあたりで午前5時になり、レポートも3題書けたことだしいったん寝ようかとも考えたが、このまま徹夜することにした。徹夜することにしたら一気に時間に余裕ができたため、ハーメルンを読みつつレポートの最後に残した1問に手を付ける。

離散フーリエ変換をΘ(N^2)とΘ(N log N)の2つのアルゴリズムで実行し、計算時間をグラフにして考察せよという問題。Θ(N log N)のほうはnumpy.fftで実装されている関数を用いる。Nは2べきだったので、多分Θ(N log N)だろうが、ドキュメントを読んでも明言はされていなさそうだった。よくわからない。

Θ(N^2)のほうも適当に実装したが、速いPythonの書き方を知らないので、効率は悪いのかもしれない。ただグラフにするとピッタリy=ax^2（aは適当な定数）と一致したのでかなりびっくりした。

午前11時過ぎに家を出て東北大学に向かう。たいぺーと一緒に提出して昼食を食べようと思っていたが、僕が大学に向かっている最中に起きたらしくてヤバそう。結局合流できたのは午前11時50分のことで、そこから急いで提出場所の研究室前まで行ってレポートを出した。セーフ。その後一緒に食事し、購買を冷やかし、図書館でハーメルンを読んだ。

午後1時過ぎに分かれて数学棟の資料室に行き、来年のゼミの希望を出すために教科書を眺める。最初は公理的集合論がよさそうだと考えていたが、整数論の教科書にメビウスの反転公式とかが書かれているのを発見して一気に興味を惹かれる。これを第一希望にすることにしよう。第三希望まで出す必要があるが、三つ目に悩む。正直どれも興味がないが、ホスフィンに2つおすすめされたので、そのうち1つを選ぶことにする。そんな適当な決め方をして、もしそれに振り分けられたらことだなと思った。

帰ってきて布団に倒れこみ、ハーメルンを読む。午後3時くらいに寝落ちした。

01/13(水)

午後10時に起きる。ハーメルンを読み続ける。かなり文章がカスでセリフのノリもキツく、さらに後書きでキャラクターと作者が掛け合いしたりしていて、ネット小説の悪いところを凝縮した感じになっている。しかし設定や展開は好みなのでそれを頼りに読んでいる。

150話くらいまで来て、ようやく半分。僕は小説を書いたりしたことがないので文章力と言ってしまうのはちょっと気が引けるが、ともかく文章が読みやすくなっていることは確か。キツいノリもほとんど見られなくなった。誤字・誤用は相変わらず多いままだが、このあたりまで来ると展開に集中できて、ストーリー上の大きな山場を乗り越える際主人公が弱体化してしまったことに心を痛める。

午前10時くらいになったので、シャワーを浴びて学食に向かう。そういえばそろそろ共通テストがあるので学食の営業時間が変更になっているかもしれない、と考え調べてみたところ、今日も変わらず営業しているどころか朝の8時から開いていたことを知って愕然とする。待つ必要はなかった。デザートとして薄い青もしくは緑色をしたクリームの小さなケーキを購入したが、これはチョコミントと呼ばれるものだったらしい。思っていたより歯磨き粉でびっくりしてしまった。

帰宅して面談。このとき↓にセッティングされたもの。

年明けに人事の方がまた面談をセッティングしてくださったので、そこで明らかになるだろう。

週記（2020/12/21-2020/12/27） - kotatsugameの日記

30分くらいで終了した。まず自分の院進学周りのことを聞かれたが、何も決めていないし何も調べていないので、うまく答えられない。次の夏のインターンに関しても、院試で参加できない可能性が無きにしもあらず……など不明瞭なことを言う（そのあと調べたら東北大学の院試に限っては特にかぶっていなさそうだった）。また、数学で院に進むのか、どういう専攻を考えているのかなど進路相談みたいな質問が続くが、どれも全く考えていないため何も言えない。

結局、イベント（アルバイト等）の情報や職種に関して継続的に人事の方とコミュニケーションをとっていきましょう……みたいな感じになった。それと、自分の進路に関していろいろ調べておいてくださいとも。競プロも頑張ってくださいと言われた。具体的なことは何も決まらなかったが、これ自体はまあ僕が将来のことを何も考えていないせいなのでどうしようもない。ひたすら主体性・当事者意識がなくて困る。

またハーメルンを読み、午後2時半くらいに寝落ち。

01/14(木)

午後10時起床。コンテストに参加できない感じの生活リズムでヤバい。

1時間ちょっとハーメルンを読んで、えでゅふぉ102に出る。5完。

ABは自明。Cは難しい。後ろ2(n-k)+1個の山はどういう順列を持ってきても転倒数が変化しないため、そこを上に凸の山ではなく下に凸の山にするのが辞書順で最も大きくなる。Dも自明。

Eがわからず、Fに行ってもわからず、再度Eに戻ってきて解いた。コスト2倍の辺を1回とコスト0倍の辺を1回通るときの最短経路を求めればよくて、例えば0倍にする辺を2倍にする辺より先に通るとすれば、多点スタートのdijkstraを3回やるとできる。逆も同様。コンテスト後のTLを見て気づいたが、これは拡張dijkstraとして見ることができた。

Fは最後の最後で燃やす埋めるに気づいたが、MLE。フローが悪いのではなくて、辺を減らすことができるのが本質だったらしい。かなり悔しい。

そのあともハーメルンを読み続け、午前4時半に1作読み終わった。約1,500,000文字を2日弱で一気読みした。ストーリーが非常に良かった。序盤の文章が壊滅的なのでおススメはしにくい。

syosetu.org

「古代スタート」タグに東方Project二次創作が多い（調べると247/264だった）ことについて、少し考えた。最近読んだ2作品について、まず最初に八意永琳や蓬莱山輝夜と出会い、次に洩矢諏訪子と八坂神奈子に出会うことが共通している。これは原作の設定（ピクシブ百科事典調べ）にあるイベントのうちこの2組に関するものが他を引き離すほど古い時代の出来事だからだろうが、このように非常に古い時代の話でも大まかな出来事がわかることが影響していると考えられる。ほかに、妖怪や神様など長命種がたくさん出てくることも関係していそう。

溜めていた日記を書く。久しぶりに記事中にtexで数式書くかと思ったら、_をエスケープしないとならない罠にハマってちょっと辛かった。ちなみにそれはこの記事の月曜日の箇所であるから、木曜日も終わりになってから4日ぶん一気に書いているということだ。こういう適当なことができるのも週ごとの更新の利点。

世間的には金曜日の朝である。午前9時くらいに寝ようとしたら、ちょうど「午前11時半から小テストをしますよ」という通知が来てキレながら起きる。今セメスターのはじめから課題を締め切りの当日に投稿していたことで有名な代数学概論Aである。さすがにちょっと勉強しないとヤバいので、ここ数回分の講義PDFに目を通しておく。最新まで追いついて、しばらくハーメルンを読んでいたら小テストの時間になった。

小テストの具体的な内容は書かない。どういう道具が存在するのか知らないが、何とか全列挙できるくらいのサイズの対称群の問題だったので、全部書いた。置換の表記法には上下に並べるものと巡回置換の積を書くものの2種類あることが知られているが、特に巡回置換のほうはどういう記法なのかよく覚えていなかったので、ひたすら上下に並べるやつを書きまくった。置換の積の計算方法に関してもあんまり自信がない。どちらが先に来るのかとか、何を見て入れ替えるのかとか。これらはすべて自分の演習不足に帰着されるが、演習する気がないのでこのままだと一生扱えないんだろうなという気分になった。

小テストが終わって正午、布団に入ってすこしハーメルンを読み、就寝。午後1時半であった。

01/15(金)

午後9時起床。yukicoderに出る。全完。

A問題はtrコマンドが最も良い。FAかつ最短コード。B問題はa op b=ab+a+b=(a+1)(b+1)-1をよく見ると交換法則・結合法則が成り立つことがわかる。よって操作の順番によらず最終的な値は一定。まれによく見る。

C問題はギャグ。1円ずつ動かせることがわかる。D問題はやるだけ。E問題は難しかったのでいったん飛ばし、F問題に行った。F問題は行列累乗。何も考えずに書いてしまったが、andとorが普通の積と和のような性質を満たすことについて一切注意を払っていなかった。見たことある気がしたのでスキップしたが、見たことがあったのはandとxorである。

Gは難しい。よく見ると最小費用流で解ける。普通に辺を張るとO(N^2)本必要になるが、頂点を4倍くらいにするとO(N)辺で再現できる。この辺りもなかなか面倒で、(A,C)をペアにした状態でAでソートして隣接する頂点に辺を張り、Cでソートして隣接する頂点に辺を張るなどインデックスがややこしい。自前のライブラリでは通らなかったが、ACLだと通った。速すぎる。

Eに戻る。Wikipediaなどを見る限り10^n-1がNで割り切れるような最小のnを求めればよさそうで、これはオイラーのφ関数の約数を全探索すれば求まる。最初カーマイケル関数を実装したが答えが合わず、一度消して書き直したのだが、実は素因数分解の途中で値が変わった変数をずっと使っていたのが悪くて、カーマイケル関数の実装には問題がなかったようだ。

All ACも含めて一面が濃い緑で埋まったので、再度ツイート。毎日虚無を10ACくらいするのが日課になっていて、意識的に止めない限りずっと続いてしまうだろう。Streakとかも同じ要領で、ちょっとした努力による継続が必要なものは一度軌道に乗ると今度は止めにくくて仕方がない。日記はコストが高いのですぐに溜めてしまうが。

試験管の黄色diffが10問ちょっと残っているので、埋める。最初に埋めようとした問題で必要になったので、良い機会であるとBaby-Step Giant-Stepのライブラリを作ろうとする。うしさんのライブラリを参考にしようと思ったら、思っていた実装よりだいぶ面倒そう。これは合成数modにも対応しているらしい。読めなかったのでTLに投げたらsugarknriさんに教えてもらえた。感謝します。

x^k \equiv y \pmod Mを満たすようなkを求めたい。まずm=\lfloor \log_2(M) \rfloorまで全探索する。xとMに共通の素因数がある場合、k>=mについてx^kは十分大きいため、Mとの共通の素因数は全部出そろっている。つまり、\gcd(x^{k+1},M)=\gcd(x^k,M)がこの先ずっと続くということだ。この段階でg=\gcd(x^m,M)を求め、割っておく。x^mは適宜mod Mしながら計算してもよいことが、互除法を考えるとわかる。

この段階でyがgの倍数でなかった場合、kは存在しないため終了。倍数だった場合はこれもgで割る。以降は\frac{x^m}{g}\times x^k=\frac{y}{g} \pmod{\frac{M}{g}}を求めればよく、ようやく普通のBSGSみたいな見た目になった。ここで逆元を求めるのに拡張ユークリッドの互除法を使ってもよいが、それより\frac{x^m}{g}\times x^{at}=\frac{y}{g}\times x^b \pmod{\frac{M}{g}}としてm+at-bを答えるようにすれば、逆元の計算が必要なくなる。かなり頭がいい。

自分のライブラリのリポジトリにプッシュして、oj-verifyが回り始めたが、すぐ落ちてしまった。エラーメッセージを見ると存在しないCargo.tomlを探して死んでいる。otherlangというフォルダを調べているようだったので、かなり嫌な予感がしたが、的中。otherlangというフォルダに入っていたverifyするつもりのないRustのコード片を解析しようとして落ちていた。対処法として別のリポジトリに移したところ、ちゃんとテストが回った。

そのあと朝までやって試験管黄色diffを7問くらい解いた。昔見たときは苦労した覚えがあったのに、今見るとバッサバッサと倒せて非常に爽快。

寝ようとしたらTechFULからメールが来た。年始のコンテストの商品は、上位者から順番に好きなものを取っていく方法で割り振られるため、自分がこのまま無視して寝ると僕より後の人に迷惑がかかる。残っている商品は6つ、商品名を見てもよくわからないので布団から出てそれぞれ調べ、結局マウスを選択した。トラックボールのマウスらしい。6つの商品の中では群を抜いて興味を惹かれた。

メールを返信して就寝。午後0時半であった。

01/16(土)

午後3時くらいに目覚ましでいったん起きて、生協の弁当の配達を待つ。午後3時半くらいに届いたのに何とか気づき、受け取りに成功。そのあとすぐ寝なおして、午後8時に起きた。今日はARC。

ABCEの4完だった。Dに見切りをつけるのが速かったので大失敗は避けられて、パフォーマンス2549、レートは2704→2690(-14)。

Aは難しいが冷静になると解ける。Bも解ける。Cはそこそこびっくりしたがシュッと解けた。移動するときに、通らなかったマスが左か上にあるから、そこを考慮して係数に掛ける。文字が書き込まれていないマスを毎回数えていると到底間に合わないので、累積の配列を持って更新しつつ遷移していく。解説の2/3を掛ける方法は天才みがある。言われてみれば……といった感じ。

Dは難しい。結局解けなかった。録画を確認したところ、15分考えて何もわからなかった時点でEに移っていた。偉い。Eはすぬけ君の操作を遅延させることで区間DPができて、区間を広げていこうとすると初期位置に応じてN+1回計算する必要があるが、区間を狭めていくことで一気に計算できるようになってAC。

Dに戻り、プログラムを書いてN==3の場合を構築した。この時点で0の位置を固定してしまったが、これをすると解法にたどり着く道筋が限られてしまうようだ。具体的には、popcountでなんやかんやする解説の方法。popcountがどういう文脈で出てくるのかいまだにわからないが、うまくいく理由は理解している。つまり人iとjが同じグループになる回数がiとjによらないことを示せばよくて、これはparityを取ることから二項係数の半分の和が出てきて、結局全体の半分くらいになる。

コンテスト終盤は、N==3の場合の解を直接検索欄に打ち込んで検索し、出てきた結果を眺めていた。Symmetric BIBDという単語が出てきて、これは問題で問われていることの一般化となっている。画像検索のほうをいくつか見てみたらアダマール行列に触れているものがあったので、もしかしたら検索で辿り着けた可能性もある。

ところで、現在のD問題の最短コードはアダマール行列を利用した解法になっている。

atcoder.jp

hadamard(N)でNxNのアダマール行列を生成している。言語機能で殴っている感じでかなり面白い。

C言語で埋める作業をし、200ACくらいした。これで1000ACの言語は10個。

埋めている最中にARCのA問題が縮んだ。

atcoder.jp

ずっとコードゴルフをしていた。今はARCを古いものから順に見ている。

週記（2020/08/31-2020/09/06） - kotatsugameの日記

実はこの後すぐコードゴルフから微妙に離れてしまい、結局ARCは全然見ていない。もちろん言語アップデート後に1周はしたが、そこから数か月で得られたテクニックについてはまだ確認していない。今回の更新もそれなので、そろそろちゃんと見ておかないといけないなという気分。

昼になって、今から寝るのもな～という気分になっていたら、yukicoderでコンテストがあるのに気付いたので、出る。6完。

Aは解法が降ってきた。Bは難しいが、シュッと思いつけてハッピー。こういうのハマる人はめちゃくちゃハマると思うんだけど。Cは全然わからないので1e8個くらい調べたら通ってしまった。嘘解法だと思っていたが、これが正当な解法らしい。理論保証もある、どころかTLで見たことのある話だった。

https://artofproblemsolving.com/wiki/index.php/Chicken_McNugget_Theorem

Dは普通のDP。Eはかなり面倒な実装。Fは似たような問題をちょっと前のyukicoderで見たことあるなと思ったが、そちらはNORだった。こっちのAND/ORだと後ろから貪欲に決まってびっくり。Gにチャレンジしたが全然合わなくてあきらめた。これがFPSになるのかなりびっくり。また、階差をとるとOEISにあったらしい。それでもオーダーを落とす作業が入るらしいが。

午後6時くらいになって寝ようかな～としていたところ、TROCがあることに気づく。午後10時から。せっかくの赤チャンスだしできれば出たいなと思い、とりあえず目覚ましを午後9時半にセットして就寝。

01/17(日)

午後9時半起床に成功。TROC18に出場し、全完7位でレートは2439→2528(+89)。このコンテストサイトは2500から赤なので、達成。

後半の微妙な難易度の問題はそこそこ面白いが、前半のギャグad-hocがかなり嫌らしい。full-feedbackなのは非常に素晴らしい。

Aはやるだけ。Bは4x4が埋められて、埋めてよさそう。Cは全然わからないのでプログラムを書いて全探索したところ、ソートして2番目を末尾にもっていけばいいらしい。意味不明。

Dは非常に難しい。答えは3または4になる。最初はNが平方数のとき3を出力してWA。正三角形を4つに分割することを考えると、N==kで3ならばN==k+3でも3。N==1とN==6は見つかって、N=2 mod 3が見つからなかったので出すとWA。もうちょっと考えると、16枚のタイルで作る正三角形のうち9枚分のタイルを1つにまとめることで、N==8が達成できる。よってNが2または3または5なら答えは4、それ以外は3。

Eはサンプルがサイレント修正されて最悪だった。まず普通に書いてセグフォ、原因を調べると謎の数列が入力されているので、これは最初Cの初期値も入力で与えようとしてたな？と思ってそのようにプログラムを書き直す。今度はサンプルが合わなくなったので、ふと気づいてページを更新したら入力から数列が削除されていた。プログラムをもとの状態に書き直して、さらにいくつかデバッグをして提出。

Fは最近のARCで見たことがあるなと思ったが、どうも合わない。答えが0かどうかの判定をデバッグするためにARCに提出しに行ったりした。もうちょっとしっかり考察すると、結構自由度があることが分かって、謎のDPを頑張ってAC。

Gも最初は全然わからなかったが、上のbitから決めていくとかなり自由にできることがわかる。自由にできない場合は次のbitを見ればよくて、これは高々log A回。残り8分でACして一安心。

月曜日の午前8時50分が期限のレポートがある。今から再度寝ると起きられない可能性があるので、今のうちに出しておこうとして解いた。さらに勢いづいて4年次ゼミの希望も出す。月曜日提出のレポートはほかにもう1つあって、せっかくだしそれもどんなものか見てやるか、と思ったら全然わからなくて途方に暮れてしまう。

あきらめて布団に入り、ハーメルンを読んで就寝。午前3時半だった。

週記（2021/01/04-2021/01/10）

01/04(月)

先週日曜日は、寝ようとしていたら両親が起床したので一緒に朝ご飯を食べて、さらにレポートを1問進めてから寝た。午前11時半のことであった。

午後6時、起床。夕食は外で食べるということが予告されており、また起こしてもらったため起床に成功した。回転寿司の店に行き、帰りに本屋に寄って帰ってきた。前回本屋に行ってから1週間も経っていないので新刊が出ていたりはしなかったが、棚を入念にチェックして3冊買ってきた。

夜、レポートを進める。大問は7まであるが、6以降は発展的な問題に位置づけられており、解かなくてもよさそう。また、最低でも3問は解くようにとのことだが、この基準はすでにクリアしている。それでもさらに大問4くらいは解けそうなので、頑張って書いた。

午後10時、完成。父にスキャンしてもらう。その間に風呂に入ったりしており、提出は午後11時だった。今日はこどふぉのdiv.3があり、レポートがあったのであきらめていたが出られそう。出る。

全完した。15位だった。

Aは自明。Bは適当に場合分け。Cは後ろから計算する。Dは値の降順に選べばよい。Eは誤読していて時間がかかったが、まずh<=wを満たすように交換してよくて、このもとでhの昇順に並べた後wの最小値を管理すれば特別なライブラリは何もいらない。

Fは最初入力で与えられるのが白マスかと思っていたが、さすがに違う。よくわからなかったので偶奇を保ったまま座圧して二部マッチングした。座圧周りがかなり怖かったが何とか通った。Gは遠い順に見ればよい。

コンテスト後のTLで見たが、Fは左から2個ずつ黒マスをペアにして見ればよいらしい。1つのタイルで偶数マス埋まることを考えると、一番左の黒マスについて、その上または下のマスは黒マスまたは1x2のタイルの左のマスに対応している必要がある。次に2番目の黒マスでこの状態は解消され、同様にしてペアにした黒マスの間はそれ自体で完結しなければならない。かなり頭が良い。

今日は本を買ったので、買った本の記録をつける必要がある。ちょうどいいのでこれも年ごとに切り替えることにしよう。

kotatsugame.hatenablog.com

このとき気づいたのだが、今年の読書記録に2020年と書いていたようだ。そのままツイートしたので非常に恥ずかしい。ただせっかく元旦に投稿したので固定ツイートは変更せず、2020年のままである。

「人生∞周目の精霊使い」を読んだ。最近は「一億年ボタンを連打した俺は……」や「……は時の牢獄で最強を超える」など人の身では不可能な期間の修行を理由にしたチートが多くて、そういう系列の本だと思って購入したが、1巻は結局ほとんど修行時代の話で終わった。マジで修行シーンを書いているとは思わなかった。ループの中で行動を変えたり、緊急回避的にcontinueしたりしていて面白い。こういう無限に強くなれる系の話は修行の辞め時が見つからなさそう、と思っていたが、この作品では「始原の神霊」と契約したところで精霊使いを極めたと判断して修行を終えている。次のループから物語が動きだして、そこで今巻は終わり。

AndroidのTweetDeck用ブラウザがTLに流れてきたのでダウンロードしてみた。かなりよさそう。最近公式のクライアントが落ちやすくて困っているので、乗り換えてもいいかもしれない。通信量削減のために画像や動画のサムネイルを読み込まない設定がほしいな、と思ったが、そもそもTweetDeck自体が通信量的に激重かもしれない。

もう1冊ラノベを読み始めた。「パソコンにおまけでついてるゲームね。爆弾を解除するやつ」「いつも一手目で爆弾を爆発させちゃうから、ゲームは嫌いよ」という発言があった。これに違和感を覚えて調べてみたところ、Windows Vista以降の付属マインスイーパは初手の瞬間に盤面を生成するため、一手目は必ず爆弾ではない（どころか周囲8マスに爆弾は存在しない）ようだ。より古いバージョンでプレイしているのかもしれない。または盤面のリプレイをしているだけかも。

両親が起きたので今日も朝ご飯を食べ、午前8時半に就寝した。

01/05(火)

午後7時、起床。昨日読み始めた「クラスの大嫌いな女子と結婚することになった。」というラノベを読み終えた。かなり面白かった。YouTubeに投稿されていた（？）漫画が原作らしい。これは今週の月曜日に買った本の1冊だった。つまりラノベの刊行予定を見ながら行っている新刊チェックに漏れていたということだが、表紙・タイトル・あらすじを総合してかなり良さそうだったのに何で買ってなかったのだろう。

こどふぉでメッセージが来ていた。昨日のE問題のコードがわからないから教えてくれというもので、どこがわからないのか書かれていなかったのでコード全体にわたってそれっぽいことを頑張って書く。30分もかかり、終わったのは今日のこどふぉdiv.1の直前だった。コンテストが始まってからありがとう見たいなメッセージが来た。

4完して2656→2675(+19)。

AはTLが1secだが気合を入れてlogをつけた。このlogはpriority_queueによるものなので、400msくらいで通った。

Bは難しいが、結局xyが平方数のときにxとyがadjacentであるらしい。もうちょっと考えると、素因数分解した後各素数の指数をmod 2で考えて、完全に等しいペアがadjacent。さらにこの関係は推移律が成り立つので、数列はグループに分かれる。0秒目におけるグループのサイズが偶数である場合、総積が平方数となるため、同じく平方数となった別のグループとくっつく可能性があるが、1秒目におけるグループはそのあと永遠に変化しない。また、グループが分裂することはない。

よって、0秒目におけるグループの様子さえわかればw==0とw>=1の2通りが計算できてよい。素数の指数をbitで持ったりvectorにしたりすることを考えたが、冷静になると素因数分解する前に戻せばint1つで表現できる。後から知ったことだが、これは整数をsquare-freeにする操作と同等。

Cはパッと見どんな感じに変化するのかわからなかったので実験コードを書いた。いろいろ試していたが、ふと数列のpを中心とする区間が単調になることに気づく。あとは単調になっている区間を探せば二分探索で中心が求められそう。単調になる範囲は質問クエリごとに2増えるようなので、それを間に挟めないような幅で順に聞いて回ればよい。ちょうどpの位置を聞いてしまうとまずそうなので、毎回隣り合った2マスを質問することにする。かなり怖いのでチェッカーを書いて、oj t/rで試す。oj t/rに慣れていないので、ちゃんとオプションを指定できていないのにコードの間違いを探し続けたり、テストが実行できたら楽しくなって無為に何百回も遊んだりしていたが、どうやら通りそう。提出しつつ時間を見ると残り40分になっていてかなり焦る。順位表を見てもCがかなり通されていて、さらにDのほうが簡単らしくヤバい。

まあ40分もあるんだし、とDを読む。二部グラフが思い浮かんで、奇閉路が問題となるが、これもできる。結局連結でさえあればよさそう。問題は構築で、最初条件を勘違いして教師が隣接しても構わず出力していた。結局貪欲に取っていくしかなくて、そこで幅優先探索ではなく深さ優先探索をすること、教師を置いたらその瞬間に隣接する頂点をマークすることさえしておけばよい。提出したら通って、Eは全然通されていなかったので諦めてTwitterをしていた。

heno239がLGM到達していてかなり感動した。で、伝説……。

「僕はリア充絶対爆発させるマン」を読んだ。直截的な表現が多くてびっくり。

明日（狭義今日）は朝の10時半からコンテストがあるので、寝なければならない。しかしなかなか寝られず布団でハーメルンを読んでいた。午前4時半就寝。

01/06(水)

午前10時起床。目覚ましでも起きたし、前日に朝からコンテストがあると伝えていた母も起こしに来てくれた。朝ごはんもゆっくり食べていい感じ。パ研合宿2020第1日「SpeedRun」に出る。

Oが解けなかった。最初はコードゴルフをしつつだったが、途中からコードゴルフしている場合ではなさそうなことに気づき、必死に考察したものの届かず。そのあと他の人の提出を見ていろいろ縮め、昼ご飯を食べようとしたときに解けた。基底を取ることは考えていたが、AとBを別々に考えてしまっていた。以下、各問題について。

AはText。改行が必要らしい。Bはget.comb.max.sayが最短となっている。さすがにこんなはずはないだろうといろいろ考えてみたが、見つからなかった。CはRakuで∩演算子を使う。これはASCIIコード範囲では(&)と書ける。どちらも3Byteだが、パースの関係で空白が必要なくなる∩のほうが短くなることがある。今回はどちらも同じ。

Dは場合分け。答えを4通り用意してK/Nでインデックス付けするとよさそう。dcではrotate操作で実現できる。Eも場合分け。AWKで書くと短くなった。Fは見つからなかった場合のエラー処理が必要かと思ったが、-1を出力するケースは存在しないらしい。P==1の場合分けを頑張る。dc。

Gはゴルフしていない。HはRubyで書いた。他の言語ではあんまり考えていない。Iはゴルフしていない。Jでは.²というのが出た。$_²と同じ。これを適用して縮む問題がほかにあったので縮めつつ、変数の初期化などで改善して最短を奪取。4,6...だと$_を初期化しておく必要があるが、これは8,16...とすれば回避できる。出力する値には余裕があるので、公差を大きめにしてもACできる。

Kはゴルフしていない。Lはdc。すでに相当短いものが提出されていたが、隙を見つけて奪取した。MNOはゴルフしていない。

昼から4時間程度塾に滞在した。帰省のたびに顔を出している。

今日も塾に行く。採点のバイトをするのだ。水曜日もやたら長く塾に滞在したのは、話の流れで同じく採点していたからだが、今日は初めからバイト目的で向かう。

週記（2020/08/24-2020/08/30） - kotatsugameの日記

今日は年末年始の休み開けであるから、宿題の採点が追い付かないことが予想されていて、手伝いが必要なようなら採点バイトに入るくらいの気持ちで行った。数人とんでもない量の宿題をこなしてきた生徒がいて、僕は任された分が間に合わずヒィヒィ言っていた。結局先生にいくらか戻したが、先生はほかの生徒の指導をしつつ素晴らしい速度で採点しており、年季が違うなあという気持ちに。生徒への指導にしても、今日は言葉に迷うことが多くて残念な結果となった。

対面で指導する（僕が採点している前のテーブルに来て質問したりする）のは感染リスクが高めだなあと感じた。マスクをとる必要がないのでギリギリセーフか。

帰ってきて新春 TechFUL Coding Battle 2021に追加された3問を解いた。逆転チャンスと銘打たれているが、上位陣にとっては当然満点を取らなければならないレベルの難易度。まんまと1ミスしてしまい非常に厳しい気持ちになった。逆転（される）チャンスなんだなあ。

明日の夕方からドカッと雪が降るらしく、土曜日に予定があるので、明日のうちに仙台に帰ることにする。今日早起きだったので昼のうちに新幹線に乗れるだろうという計算。

「僕はリア充絶対爆発させるマン」の2巻と3巻を読んだ。シリーズ完結。正直なんの面白みも感じられなかった。本当は2巻を読了した時点で日付が変わっていて、早く寝なければならなかったのだが、3巻だけ持って仙台に行くのもなんだかなと思って無理して読んでしまった。

午前4時就寝。

01/07(木)

午前10時半起床。食事して荷物をまとめ、家を出る。

母に車で黒部宇奈月温泉駅まで送ってもらう。切符を買おうとしたら、12/23でみどりの窓口の営業が終了しており、学割を適用できない。あきらめて通常料金で買おうとしたところ、駅員さんに「みどりの券売機プラス」という機械の存在を教えてもらう。起動するとどこかのセンターにつながり、学割をカメラで読み取ったりして普通にみどりの窓口で行うようなやり取りののちに学割を適用した切符を発券してもらえた。10分くらいかかった。今日は結構時間に余裕があったので良かったものの、ギリギリだと間に合わないだろう。混んでいる場合もまずそう。今度からは事前に買っておくのがよさそうだ。

ホームは非常に寒い。外を見ると風が結構出てきていることがわかる。駅から自宅まで車で帰る母のことを心配しつつ、乗車。コンセントとフリーWi-Fiを確保し、今日の昼からのパ研合宿2020第2日「パ研杯2020」に備える。

6完で全体8位だった。終盤、部分点を狙うのを完全に忘れていた。

A問題はdc。空白区切りではなく改行区切りにしても通った。B問題は短くならなさそうなので、H問題のマラソンに行ってしばらくコードゴルフをしていた。

B問題は01BFSで書いたが実際はDP。C問題はいくらか考えると入次数と出次数の差がポイントになることが分かった。D問題はトポロジカルソート。E問題は各点についてそれが乗る直線の個数を数えたくなって、これは直線の傾きをsqrtで分けて処理すればできる。制約が2secなのでかなり不安になりつつ出したが、450msとかなり速かった。

Fを頭に入れて、部分点の考察ができた段階で乗り換えをした。移動の合間も考えていた。レートはある程度自由にやり取りしてよさそうだが、2倍にできるものの範囲は考える必要がある。今度も自由席にコンセントがついている車両だったため、先ほどと同様のセッティングをした後にもうちょっと考察をしたら解けた。

基本は二分探索で、判定問題を解く。LとRを混ぜて順に処理する。Lを処理するときは、時系列のLにレートを全部置いていく。Rを処理するときは、まず対応するL以前に置いていかれたレートを全部回収して2倍にする。足りていれば余計な分をRに置いていく。足りない場合は、ほかに置かれたレートを回収してつじつまを合わせるが、このとき時系列順で最近置かれたものから取っていくのが直感的に良い（なぜなら、より古いものはより多くの人に2倍で回収され得るから）。

以上のことを区間0クリアと区間和の遅延セグメント木で処理した。つじつま合わせは二分探索で行った。これを提出したところ、WAがたくさんとTLEが1つ出た。どうやら倍になりすぎてオーバーフローしたらしい。全員分に相当するレートが確保した時点で打ち切ると、TLEが1つだけ残った。オーバーフローを解消したら直ると思っていたが、普通に間に合っていないようだ。

冷静になると、上の操作はdequeで実現できる。L以前のレートを回収するのはpop_frontで、つじつま合わせはpop_backで書ける。これを実装すると爆速で通った。

C問題をゴルフする。Rubyで書いていたが、Perlに書き直すと速度でもコード長でも大幅な改善が見られた。謎。残り30分で順位表を見ると、G問題が思ったより通されていた。慌てて考え始めるも、CHTが見えたあたりで嫌になり始める。オイラーツアーも必要に思えてきて、どうしても実装が間に合いそうにないなとなった。

今日の新幹線はかなりガラガラだった。緊急事態宣言と大荒れ直前の天気のダブルパンチで移動する人が極端に少なかったのだろう。

仙台について、ゲーセンに行く。素手でチュウニズムを頑張る。新曲の99AJ埋めをした。午後8時くらいに夕食を食べようとラーメン屋に行った。

ラーメンパンチという店があって、移転したのだが、跡地もラーメン屋になったことをTwitterで見聞きした。そこへ行ってみたが、たまたま水曜日が定休日らしく閉まっていた。

週記（2020/12/21-2020/12/27） - kotatsugameの日記

ここは今日はスープがなくなったらしく、もう閉まっていた。かなり残念。だし廊というラーメン屋に行った。

ゲーセンを変えてさらにチュウニズム。ちょっと理論値を狙ってみたが、非常に厳しい。何でもないようなノーツでもぽろぽろ落としてしまう。最後に怒槌を数回プレイして、なんとかSSに乗せた。終盤は有名な擦りや餡蜜があるのでそれをした。密度が高すぎてどれだけ失点しているのかわからない。しかし前半がとにかくボロボロ。

帰るときになって、壁のチラシでチュウニズムにおいて200円3クレイベントが開催されていたことを知る。今日は結構お金を使ったのでつらい。

帰りはかなり雪が降っていた。マスクから出る息でメガネが曇って前が見えない。

FHCのTシャツが届いていた。

今日のH問題の最短が奪われていた。p [100]*4e4にしてWAになり首をかしげていたが、p *[100]*4e4である。なぜこれに気付かなかったのか。マラソン典型である。非常に悔しい。

帰省前の自分は相当丁寧に部屋の食糧を食べつくしていっており、夜中にお腹が空いてつらい思いをした。午前4時就寝。

01/08(金)

午後6時半起床。親から実家の屋根の写真が送られてきた。めちゃめちゃ積もっていて、ちょっと見たかったなあという気持ちになった。土曜日の予定が、コロナのせいか雪のせいかはわからないが消滅した。

パスタをゆでて食べた。yukicoderに出る。D以外の5完。Bは直後に追加されたチャレンジケースで落ちてしまった。

Eは式を根から各頂点とそのLCAまで、それぞれの距離に分解して計算すればよい。適当にガチャガチャしていたら合わせるのに時間がかかってしまった。Fは既出。

Problem - F - Codeforces

2*(区間長)<=総積が正しい条件らしい。次のように証明できる：

週記（2020/12/07-2020/12/13） - kotatsugameの日記

証明に関してはこれ（引用の続きの文）でよい。当時のコードをコピーして少し書き換え、提出したところ、WA。ちょっと計算量がヤバいことは知っていたのでTLEするかもなとは考えていたが、WAとは……。

探してみるといろいろバグが見つかる。そもそも上の問題は+とか*をそのまま出力する問題なので、書き換えでミスしていた。それと制約の違いを直し忘れていたのと、オーバーフロー。それでもWAが取れなかったので、コードの根幹部分を一気に書きなおしたところ、通った。謎。ちなみに計算量がヤバかったのも直している。間の1が連続する箇所は切り分けるが、その区間の演算についてもbit全探索していた。そこは抜いておいて積に相当するか和に相当するかで変えればよい。

チャレンジされて落ちているBを放ってこどふぉdiv.2に出る。Eにめちゃくちゃハマってギリギリ全完。今日もスクリーンキャプチャしていた。

Aはギャグ。先頭は98にするしかなく、このとき8を境に折り返すことで989にできて、一番よい。Bは値の総和を求めるのだと勘違いしていた。hillやvalleyだけを取り出したvectorを作ってそこだけ見たところWAで、冷静になると値を隣に合わせるのがよく、このとき差分は回りを少しだけ見れば計算できるのでよい。

Cはそれぞれの総和と最小値だけ持ってうまいことやる。AtCoderで似た問題を見たことがあったが、今回の場合難しいのはそこからだろう。リンクを貼るために問題を探していたが、ABCで出題されたと思い込んでいたため見つからず、TLに聞いた。

atcoder.jp

Dは明らか。Eは同じ値の頂点のペアに対して、それぞれを根にしたときのもう片方の頂点以下の部分木に入る頂点に1加算して、最後に0だった頂点を見つければよさそう。適当に根付き木にしたとき、加算は木上のimos法でできる。ペアの列挙については、同じ頂点を何回も見る必要がないのでペア数はO(N^2)ではなくO(N)になる。部分木の頂点をmapに入れて保持し、更新時に同じ値の頂点が見つかったら1加算の操作を行う。マージテクで間に合う。

根付き木にしたときに、ある頂点とその部分木に含まれる頂点のペアを処理するところでミスし続けていた。imos法において-1してキャンセルしなければならない頂点は、上にある頂点ではなく、そこから1歩ペアの頂点に向けて進んだ頂点でなければならない。これは部分木をマージしてから処理するのではできず、マージ前に部分木ごとに行う必要があった。

「見習い巫女と不良神主が、世界を救うとか救わないとか。」を読んだ。ストーリーはそこそこいい感じだが、ひたすら読みにくかった。三人称視点で書かれているのに急に主人公の一人称視点で感情が書かれたりするからだと推測したが、ではどう書けばよかったのかとか、他の三人称視点の作品ではどうしているのかは知らないので、これが本当に的を射た指摘であるかはわからない。

振り返ってみれば、本を読んでも内容にはほとんど触れず、読みやすかっただの設定が好みだのしか言っていない気もする。読むときに何も考えていないからそうなってしまうのだが、これからは意識的に内容に触れる感想を書くようにしたいと思った。

布団に入ってハーメルンを読み、正午就寝。予定が消滅したので思うさま生活リズムを崩壊させているが、レポート提出などで昼に起きなければならない用事はほかにもある。

01/09(土)

午後6時半起床。目を覚ましてしまったものは仕方がないが、もう数十分くらいは寝ておきたかった。この時間から二度寝するとまずそうなので起きる。

コンビニに行って食べ物を買う。サラダを2つと菓子パンを4袋、あとお菓子を少し。かなり空腹だったのでうっかり山ほど買ってしまった。

ARC111に出た。5完23位。パフォーマンスは3079でレートは2654→2704(+50)。大成功。直前まで作業していたため、画面を録画するのを完全に忘れていた。

Aは解法が降ってきた。C++でコーディングしたら結構時間がかかってしまったが、このくらいだったら最初からdcで書いてもよかったかもしれない。提出してからB問題に進む前にdcでコードゴルフしたところ、12Bになって現在も最短コードである。難易度的には、ABCの300点問題というよりはAGCの300点問題だろう。

Bは既出。UFに辺の数も持たせようとして、ライブラリを書き換えるのではなく最初からフルスクラッチしようとしたら、typoしてしまった。1WA。

Cは置換なのでサイクルに分けることを考える。2頂点以上のサイクルがあったとき、そこにすでに疲れた人がいるとダメで、そうでない場合はできそう。実際、一番体重の重い人はサイクル内のどの荷物を持っても疲れないので、この人を使ってサイクルを縮めていけばよい。

Dはパッと見難しいが、制約がこれでもかというくらいに「解が存在する」ことを主張しているので、まあそれを使うんだろうなあとわかる。冷静になると、異なるcを持つ頂点を結ぶ辺の向きは決定できて、そうでないものはループの一部にならなければならない。あとはループになるように辺を向きづけるが、これは、できる。ある頂点からdfsすると、どこかのループに乗ってスタートした頂点まで戻ってこれる。そのループを縮約して同様に進める。実際には縮約せず、ただのdfsでできる。

Eはとても面白かった。まずA+BiとA+Ciの差を考えることでiとしてあり得る範囲が求まる。その中で(A+Bi)//Dと(A+Ci)//Dの差は0または1。こういう考察はABCで見たことがあったので、すぐにたどり着けた。floor_sumをちゃんと使っているのも面白い。

atcoder.jp

A+BiがDの倍数のとき、困る。僕は拡張ユークリッドの互除法で解いて実際に個数を求めたが、A+Biの代わりにA-1+Biを使えばよかったらしい。

Fは解けなかった。要素ごとに考えて、更新クエリがk回来たときある値になる場合の数を計算する。maxとminがいい感じに補い合い、1..M-1のどれでも同じくM^(k-1)(2^k-1)通りだと分かった。あとはクエリの区間についての処理だったが、できなかった。インデックスiが含まれる場合の数はi(N+1-i)だが、これのi=1..Nにおけるj乗和をj=1..Qにおいて求める必要が出てきた。式変形の方針を間違えたのだろう。ほかにも考えなければならないことは残っていて、これができたとしても解けたとは思えないが、ともかくコンテスト中はこれにかかりきりになって終わった。

シグマが絡む計算の式変形が苦手であることが分かってきた。何とかしなければならない。

SRMに出るので、それまでラノベを読んでいた。

午前2時からSRM797。EasyとMedを解いて18位、レートは2328→2389(+61)。highestである。画面の録画をした。

Easyはどこまで上がるかを全探索した。最初、あんまり上がらなくても回り道すると行けるということを完全に見落としたまま実装し始めてしまい、ちょっと時間がかかった。

Medは難しい。期待値の関係を行列にして解くやつかと思って行列ライブラリを貼ったが、サイズが5000x5000になるので違う。冷静になると、行列の各行の非ゼロ要素は高々10個で、また関係する項の添え字もiに対してi+1以下となるため、iの小さいほうから順に計算していける。

具体的には、iを計算する際にj<iなるx_jをa_j*x_i+b_jという形で保持しておく。このとき、x_i=a'*x_{i+1}+b'*x_i+c'という式にまとめられるので、ここからx_i=a*x_{i+1}+bに直して、それをj<iなるjの式に対して代入する。これで次にi+1を計算する際も同様の条件が満たされたままにできる。Nを項の数としてO(N^2)。実は、「前に1進む確率がpなら期待値は1/p」と「後ろ向きならx_i-x_to+1のコストで戻ってこれると考えてよい」でO(N)で計算できるらしい。すごい。

遷移関係を求めるのも少しややこしいが、こちらにもO(N^2)かけてよいので、やりようはいくらかある。僕はZ-algorithmを使用して判定を定数時間で行えるようにしたうえで全探索した。やっていることはKMP法のfailure-functionなので線形時間でも可能らしいが、名前を知っているだけで内容は知らないため実装できない。

自作のmodintを貼ったらコンパイルエラーが山ほど出て、結局直せなかったので普通にmodを取りつつ書いた。

Hardは意味不明。サンプルを手で解いて実際に条件を満たすことを確認するのに30分くらいかかった。

ラノベを1冊読んだ。「デスゲームから始めるMMOスローライフ」。スローライフ系の話は実はほとんど興味がなく、この作品は特に主人公やヒロインがチートだったりもしないので、完全に僕の趣味・嗜好からは外れていた。買ったのがもう4年も前なので、当時何を考えていたかはわからない。当時はちょうど、毎月新刊をチェックして新作を買うことを覚えたころだったが、資金は潤沢ではなかったので、現在のように「積んでいる本の続刊を買ってさらに積む」みたいなことはあまりしていなかったらしい。このシリーズは4巻まで出ているが、2巻までしか買っていなかったので、最近古本で3巻と4巻を購入して揃えた。

設定におけるSAOとの類似性がいくつもあってモヤモヤしたが、まあデスゲームを書くなら大なり小なり似てしまうのだろう。内容的には主人公がヒロインとずっと戯れているシーンが続くだけで、僕は面白くないと感じたが、続刊の帯によれば重版したらしい。

yukicoderの問題をいくつか解いた。

No.1200 お菓子配り-3 - yukicoder

この問題はA、B、Cが正整数であると書いてあるのを見落としてWAしてしまった。自分の最初のACコードが落ちるケースを発見したので、試しにほかの提出を確認してみたところ、いくつか落ちるコードが存在したので、チャレンジしておいた。

布団に入ってハーメルンを読む。最近は紙の本に注力していてネット小説はあまり精力的に読んでいなかった。今日やっと1作読み終えたが、これも1か月くらいかかった。

syosetu.org

東方Projectのオリ主系、好きかもしれない。

週記（2020/12/07-2020/12/13） - kotatsugameの日記

これを受けて読み始めた作品だったはず。1話の冒頭で東方先代録という作品が紹介されているが、これは途中で止まっている。

上位存在・長命種が人間の発展を見守ったり導いたりする話が好きだと言っている

週記（2020/09/28-2020/10/04） - kotatsugameの日記

「古代スタート」というタグがよさそうであることに気づいた。

午後1時、就寝。

01/10(日)

午後3時くらいに腹を壊してトイレに駆け込んだ。午後8時起床。ABC188に出る。

全完したが、Fに非常に時間をかけてしまった。今日も画面録画をしたが、どういう動画にするのがよいか迷う。コードゴルフの作業も結構録画してあるので、そちらをメインに動画を構成するのもいいかもしれない。

Fの2WAはビットシフトのオーバーフロー。1LLではなく1と書いていた。久しぶりにやらかしたので結構びっくりしている。↓と同じ問題であることに気づけなくて残念。AtCoderでメモ化再帰が頻出しているような気がする。そんなに使うとは思わなかった。

atcoder.jp

コードゴルフは現時点で全勝。Aはrangeとかminmaxとか考えてしまうが、差の絶対値を見ればよい。符号付のままでも、絶対値に関して切り上げ除算することで-2..2を-1..1に圧縮すれば次の問題と同じになる。

atcoder.jp

BはRakuで書くだけだが、全完後にちょっと書き直したら1B縮んでびっくりした。遅きに失したかと残念がっていたが、蓋を開けてみれば最短だった。

Cは最初から左半分と右半分のmaxを比較する方針を取れたのがよかった。Dはコンテスト中は座圧してから解いたのでコードゴルフする気はなかったが、解説を読んでイベントソートでよいことを知り、縮めた。

Eは制約が優しいので順に見ればよい。辺をソートすると隣接リストを作らなくてもよくなる。Fはさすがにコンテスト中の方針（桁DP）でコードゴルフする気にはなれなかったが、解説でメモ化再帰解を知り、縮めた。Rubyでゴリゴリ縮めた後、仕上げにVimに移植したら一気に8B削れてびっくり。

1000ACはこれでAWK、bash、bc、C++、Haskell、Julia、Pascal、Perl、Rubyの9言語。次はCでも狙おうか。

言語別AC数のページを見るたびに、Perl6とRakuが区別されてしまっているのが非常に気になるので、とりあえずIssueを立てた。プルリク用のコードもすでに書いたが、最初からプルリクを送り付けるのがなんだかためらわれて、まずお伺いを立てる感じ。別にそんな変な遠慮いらないのかもしれないと今になって思った。

github.com

新春 TechFUL Coding Battle 2021が終了した。最終順位は5位。12問目は非常に難しく、最初はO(3^N)にいくらかゴミがついた計算量で通そうとしていたものの、断念。遷移をもうちょっとよく考えると、ビット列を左から順に処理していってもよいことに気づき、i=1..Nに対してi桁目だけ処理するO(2^N)のループを書いたら解けた。15問目はS==Tで1WA。

yukicoderを数問解いた。

yukicoder.me

(1+sqrt(2))^nの整数部分を求める問題、みたいなのをTLで見たことがあるはずだが、肝心のアイディアを思い出せなかった。何らかの数とペアにして、そのペアの数の絶対値が非常に小さいことを利用することまでは思い出せたのだが……。結局解説を読んでAC。考察メモを見返した感じ、a+bとabを利用してa^n+b^nを求めるということができていなかっただけにも見える。

買った本の記録（2021）

kotatsugame.hatenablog.com

kotatsugame.hatenablog.com

1月

見習い巫女と不良神主が、世界を救うとか救わないとか。
クラスの大嫌いな女子と結婚することになった。
人生∞周目の精霊使い
キグナスの乙女たち
あくまでも探偵は
江戸の花魁と入れ替わったので、花街の頂点を目指してみる
転生魔王の大誤算2
剣と魔法の税金対策
盤上の向日葵 上,下

2月

継母の連れ子が元カノだった6
友人キャラの俺がモテまくるわけないだろ？4
幼馴染で婚約者なふたりが恋人を目指す話1
日常ではさえないただのおっさん、本当は地上最強の戦神7
暇人、魔王の姿で異世界へ12
裏社会最強の男、終末異世界を愉しむ。
魔王2099
薬屋のひとりごと10
シェアハウスで再会した元カノが迫ってくる
最強魔法師の隠遁計画12
数学者の夏
りゅうおうのおしごと！14
義妹生活
ホラー女優が天才子役に転生しました2
ワールド・ティーチャー14
ねえ、もっかい寝よ？2
西野 ～学内カースト最下位にして異能世界最強の少年～10

3月

ひきこまり吸血姫の悶々4
現代社会で乙女ゲームの悪役令嬢をするのはちょっと大変2
暗殺者である俺のステータスが勇者よりも明らかに強いのだが4
ブラックな騎士団の奴隷がホワイトな冒険者ギルドに引き抜かれてSランクになりました3
転生王女と天才令嬢の魔法革命3
幼馴染の妹の家庭教師をはじめたら3
公女殿下の家庭教師8
神々に育てられしもの、最強となる5
転校先の清楚可憐な美少女が、昔男子と思って一緒に遊んだ幼馴染だった件
お隣の天使様にいつの間にか駄目人間にされていた件4
文字渦
櫻子さんの足元には死体が埋まっている17
美少女と距離を置く方法2
時々ボソッとロシア語でデレる隣のアーリャさん
義妹生活2
ライアー・ライアー7
アサシンズプライド13
ロクでなし魔術講師と追想日誌8
スパイ教室 短編集01
ソードアート・オンライン プログレッシブ7
友達の妹が俺にだけウザい7
僕が答える君の謎解き
元カノとのじれったい偽装結婚
賢者の孫14
いつも塩対応な幼なじみだけど、俺に片想いしているのがバレバレでかわいい。1
犯罪社会学者・椥辻霖雨の憂鬱
カネは敗者のまわりもの1,2,3
新世の学園戦区1,2
レーゼンシア帝国繁栄紀1,2
わたしの知らない、先輩の100コのこと1,2
幸運なバカたちが学園を回す1
サディスティックムーン
超高度かわいい諜報戦
古き掟の魔法騎士I
賢者の贈り物
さよなら僕のスツールハウス
超・殺人事件
探偵AIのリアル・ティープラーニング
レジまでの推理
氷の令嬢の溶かし方2
精霊幻想記19
「私と一緒に住むってどうかな？」1
新妹魔王の契約者XIII

4月

叙述トリック短編集
この世界、わたしに都合がいいようです！
D級冒険者の俺、なぜか勇者パーティーに勧誘されたあげく、王女につきまとわれてる2
居候先の三姉妹がえっちなトレーニングを求めてくる
やはり俺の青春ラブコメはまちがっている。14.5
薬屋のひとりごと11
俺は星間国家の悪徳領主！3
剣と魔法の税金対策2
大親友が女の子だと思春期に困る
メイジアン・カンパニー2

5月

元スパイ、家政夫に転職する2
両親の借金を肩代わりしてもらう条件は日本一可愛い女子高生と一緒に暮らすことでした。2
株では勝てる俺も、カワイイ女子高生には勝てない。
クラスの大嫌いな女子と結婚することになった。2
午後九時、ベランダ越しの女神先輩は僕だけのもの2
辺境都市の育成者3
恋は双子で割り切れない
雪中の花は、軍神を偽る
魔王2099 2
学園キノ7
隣のクーデレラを甘やかしたら、ウチの合鍵を渡すことになった2
才女のお世話1
ひきこまり吸血姫の悶々5
痴漢されそうになっているS級美少女を助けたら隣の席の幼馴染だった4
クール美少女の秘密な趣味を褒めたらめちゃくちゃなつかれた件
ホーンテッド・キャンパス18

6月

私立シードゥス学院II
紫ノ宮沙霧のビブリオセラピー
黒牢城
探偵はもう、死んでいる。5
クラスに銃は似合わない。
スパイ教室05
異世界でチート能力を手にした俺は、現実世界をも無双する8
VTuberなんだが配信切り忘れたら伝説になってた
ネトゲの嫁が人気アイドルだった1
神様の罠
ソードアート・オンライン プログレッシブ8
史上最強オークさんの楽しい種付けハーレムづくり5
転生魔王の大誤算3
四元館の殺人

7月

invert 城塚翡翠倒叙集
サイレント・ウィッチ
ブラックな騎士団の奴隷がホワイトな冒険者ギルドに引き抜かれてSランクになりました4
嘘と詐欺と異能学園
サベージファングお嬢様
幼馴染で婚約者なふたりが恋人をめざす話2
キグナスの乙女たち2
日本語が話せないロシア人美少女転入生が頼れるのは、多言語マスターの俺1人
浅草鬼嫁日記 九
ロクでなし魔術講師と禁忌教典19
古き掟の魔法騎士II
お隣の天使様にいつの間にか駄目人間にされていた件5
俺は知らないうちに学校一の美少女を口説いていたらしい1
グッバイ現実世界
西野 ～学内カースト最下位にして異能世界最強の少年～11
わたしの幸せな結婚 五
転校先の清楚可憐な美少女が、昔男子と思って一緒に遊んだ幼馴染だった件2
きみは本当に僕の天使なのか
ライアー・ライアー8
元カノとのじれったい偽装結婚2
幼馴染の妹の家庭教師をはじめたら4
公女殿下の家庭教師9
大罪ダンジョン教習所の反面教師
推しが俺を好きかもしれない
炎舞館の殺人
時々ボソッとロシア語でデレる隣のアーリャさん2
義妹生活3

8月

継母の連れ子が元カノだった7
友人キャラの俺がモテまくるわけないだろ？5
ねぇ、もういっそつき合っちゃう？1
いっつも塩対応な幼なじみだけど、俺に片想いしているのがバレバレでかわいい。2
最強魔法師の隠遁計画13
祈る神の名を知らず、願う心の形も見えず、それでも月は夜空に昇る。
恋は双子で割り切れない2
俺の姪は将来、どんな相手と結婚するんだろう？
前世は剣帝。今生クズ王子1
友達の妹が俺にだけウザい8
英国カノジョは“らぶゆー”じゃなくてスキと言いたい
クラスのギャルが、なぜか俺の義妹と仲良くなった。「今日もキミの家、行っていい？」
両親の借金を肩代わりしてもらう条件は日本一可愛い女子高生と一緒に暮らすことでした。3
辺境都市の育成者4
転生王女と天才令嬢の魔法革命4
死物語 上,下
密室館殺人事件
かくりよの宿飯 一,二,三,四,五,六,七,八,九,十,十一
また殺されてしまったのですね、探偵様
クラスの大嫌いな女子と結婚することになった。3
転生ごときで逃げられるとでも、兄さん？2
神々の権能を操りし者
剣と魔法の税金対策3
現代社会で乙女ゲームの悪役令嬢をするのはちょっと大変3

9月

りゅうおうのおしごと！15
「私と一緒に住むってどうかな？」2
ひきこまり吸血姫の悶々6
プリンセス・ギャンビット
お見合いしたくなかったので、無理難題な条件をつけたら同級生が来た件について2
精霊幻想記20
王様のプロポーズ
デート・ア・ライブ マテリアル2
VTuberなんだが配信切り忘れたら伝説になってた2
スパイ教室06
自称Fランクのお兄さまがゲームで評価される学園の頂点に君臨するそうですよ？11
株では勝てる俺も、カワイイ女子高生には勝てない。2
ワールド・ティーチャー15
やはり俺の青春ラブコメはまちがっている。結1
探偵は教室にいない
僕が答える君の謎解き2

10月

プログラマの数学
異世界でチート能力を手にした俺は、現実世界をも無双する9
この世界、わたしに都合がいいようです！2
公務員、中田忍の悪徳
クールな月城さんは俺にだけデレ可愛い
ソードアート・オンライン26
剣と魔法の税金対策4
ネトゲの嫁が人気アイドルだった2
宅録ぼっちのおれが、あの天才美少女のゴーストライターになるなんて。
前世は剣帝。今生クズ王子2
古き掟の魔法騎士III
ロクでなし魔術講師と追想日誌9
友人に500円貸したら借金のカタに妹をよこしてきたのだけれど、俺は一体どうすればいいんだろう
変人のサラダボウル
蜜柑花子の栄光
賢者の孫15
迷探偵の条件1
ブラックな騎士団の奴隷がホワイトな冒険者ギルドに引き抜かれてSランクになりました5
痴漢されそうになっているS級美少女を助けたら隣の席の幼馴染だった5
転生魔王の大誤算4
俺は星間国家の悪徳領主！4
虚構推理短編集 岩永琴子の純真
サイレント・ウィッチII
『ずっと友達でいてね』と言っていた女友達が友達じゃなくなるまで

11月

隣のクーデレラを甘やかしたら、ウチの合鍵を渡すことになった3
転校先の清楚可憐な美少女が、昔男子と思って一緒に遊んだ幼馴染だった件3
最凶の魔王に鍛えられた勇者、異世界帰還者たちの学園で無双する1
家事万能の俺が孤高（？）の美少女を朝から夜までお世話することになった話
初恋だった同級生が家族になってから、幼馴染がやけに甘えてくる
英雄と魔女の転生ラブコメ
叫びと祈り
メイジアン・カンパニー3
護衛のメソッド
恋人全員を幸せにする話
俺の姪は将来、どんな相手と結婚するんだろう？2
信長転生
江戸の花魁と入れ替わったので、花街の頂点を目指してみる 二
メイデーア転生物語5
米澤屋書店
妖し
僕らのセカイはフィクションで
公女殿下の家庭教師10
サベージファングお嬢様2
ライアー・ライアー9
探偵はもう、死んでいる。6
ノーゲーム・ノーライフ11
ログアウトしたのはVRMMOじゃなく本物の異世界でした
王立魔術学院の《魔王》教官I

12月

俺は知らないうちに学校一の美少女を口説いていたらしい2
ひきこもりの俺がかわいいギルドマスターに世話を焼かれまくったって別にいいだろう？1
灰原くんの強くて青春ニューゲーム1
才女のお世話2
いずれ水帝と呼ばれる少年
何と言われようとも、僕はただの宮廷司書です。
時々ボソッとロシア語でデレる隣のアーリャさん3
天才最弱魔物使いは帰還したい2
嘘と詐欺と異能学園2
カワイイけど慎重すぎるお嬢様の笑わせ方
虚構推理 逆襲と敗北の日
両親の借金を肩代わりしてもらう条件は日本一可愛い女子高生と一緒に暮らすことでした。4
クラスのギャルが、なぜか俺の義妹と仲良くなった。2「おかえり、キミを待ってたよ」
スパイ教室 短編集02
美少女とぶらり旅
機械音痴な幼馴染が我が家でリモート授業を受けているのは、ここだけの秘密。
西野 ～学内カースト最下位にして異能世界最強の少年～12
クラスの大嫌いな女子と結婚することになった。4
義妹生活4
犯罪社会学者・椥辻霖雨の憂鬱2
ホーンテッド・キャンパス19
私立シードゥス学院III
公務員、中田忍の悪徳2
日本語が話せないロシア人美少女転入生が頼れるのは、多言語マスターの俺1人2
VRゲーで最強無双の少年、現実にステータスが同期し人生逆転
お見合いしたくなかったので、無理難題な条件をつけたら同級生が来た件について3
お姉ちゃんといっしょに異世界を支配して幸せな家庭を築きましょ？
D級冒険者の俺、なぜか勇者パーティーに勧誘されたあげく、王女につきまとわれてる3
劣等眼の転生魔術師6

週記（2020/12/28-2021/01/03）

12/28(月)

先週の週記を投稿してからAGC051Cのupsolveをした。不変量だとわかっていれば解けたかというとこれも微妙。解説の最後の方で出てくる「実は操作は1種類しかしません」というのに気づけたか自信がない。今回は数分考えてわからず、その部分まで解説を読んでしまった。

布団に入ってハーメルンを読む。午前10時、就寝。

夕方に一度目を覚ましたあとも即座に二度寝してしまい、結局午後9時に起床した。第5回PASTの過去問が公開されているのに気づいたのが意識覚醒の決めてだった。

急いでパソコンに向かい最初の数問を通す。A問題は自明すぎて公開直後に最短コードが出ていた。B問題は似たような「解法」が既出なのでそこから最短コードを拾ってくる。

atcoder.jp

タイトルが洒落ていて印象深い。ちなみにどちらも（文字列の前処理をしたあと）「2つある文字を見つけて先に出現する方を削除する」ことを繰り返すと解ける。ただ僕の頭ではこの2つが同じ問題だとは思えない。

次にC問題。36進数への変換は、そういう機能がある言語を使えば良い。dcやbcは16進数までしか対応していない。正確には、より大きな基数だとアルファベットになってくれない。今回はRakuが短いだろう。

get.baseとすると、getがStr型であるためメソッドが存在せずRE。+getとしてInt型にする必要がある。これは(+get).base(36)ではなく+get. base(36)と（空白を入れつつ）書いても動く、という発見があったらしい。これは面白い。ただもっと短い書き方があって、base +get: 36。method a: b,c...と書くとa.method(b,c...)と同じ意味になる。+をつけるために括弧が要らなくなって短い。

Dはよくわからないので、とりあえず通しておいてから最短コードを見る。特に面白いことはやっていないが、隙があったので縮めておく。E以降を見てもあまり簡単に短くなるようなものはなさそうなので、再度D問題に戻ってくる。

文字列としてのソートをすると、0が先頭に多いほうが先にくる。このあと数値としてstableなソートをすると良さそう。そう考えてbashやVimで試していたが、どうにもうまく行かない。ランダムケースを生成して試すことにした。mt19937 rng(114514)というコードでランダムケースを生成したら全部一緒のテストケースになるなどのヘマをやらかしつつ、落ちるケースを見つけることができた。0と00などを比較するとまずいらしい。確かに、この場合は0が少ないほうが先頭に来る。

そこで、各行の末尾に適当な文字、今回は'1'をつけてソートしてみることにする。このもとで、bashだとsort -n1回でうまく行った。Vimの:sortを使うと、末尾に文字をつけていてもうまく行かないようだが、文字列の処理はVimに軍配が上がる。Vimからbashのsortを呼び出すことで27Bになった。

ここでECR101があったので出た。1時間ちょっとで全完して6位。

Aは左から'('、右から')'で埋めて判定。与えられる文字列に'('と')'がそれぞれたった1つしかないことを読み落とした人がたくさんいたらしい。太字で書いてあるんだよなあ（ただ'('と')'がクオートされていないので、見にくくはあった）。

Bはやるだけ。Cは上下の端を持って順に見るだけ。Dはsqrtを使って小さくしていく、と思ったらWAを出した。5を3で割ると2になる。3>2なのがまずかった。こういう場合はもう一度割るようにして、それでも2e5において操作回数をはみ出ないことがわかったので提出、AC。もしかしたら微妙なケースで落ちるのかもしれない。

Eは難しい。しばらく考えていたら急に「長さkの部分文字列をbit反転したもの全てのmex」だとわかった。下20桁だけ持てば良い。Fは当たり前。誤読してk番目に遠い頂点のことを考えていた。この場合kを越える最小の部分和を考える必要があって困っていた。読み直すと解ける。

今回もスクリーンキャプチャを撮っていたが、あとからコンソールやブラウザを拡大していないことに気づいた。まあ見えるか。

終わったのでTwitterに戻ってきたら、PASTのD問題が縮められていた。くっつける文字は'A'でも良かったようだ。ちょっと試してみたところ、別にもとの数字と間が空いていても良かったので、文字列処理を工夫してさらに-2B、25Bになった。

真夜中だが、第31回TechFUL Coding Battleの入賞商品のアマギフが届いた。深夜までお疲れ様です。当時バチバチに暴言吐いたのに、運営側の人に引用RTでおめでとうございますと言われて気まずい気分になる。気まずいだけで僕が間違っているとは思わないが。

午前6時半くらいまでかけてECR100の動画編集（セリフ付け）をしていた。終わったと思ってニコニコしていたらゆっくりの表情を変えなければならないことに気づいて呆然。今度から効果音付けも含めて同時に作業するようにしたい。

同時に帰省準備も進めておく。具体的には持ち帰るノーパソのアップデートなど。あと、久しぶりに最短コードをクロールし直していた。Rubyでフィールドの内容にCRLFが含まれるcsvファイルが読み込めず、非常に困った。出力のときに\rを削除するようにして、念の為もう一度クロールし直したら、1000個ほど処理したあとこの提出を処理しているときに落ちてしまった。

atcoder.jp

invalidなUTF-8を含む文字列でgsubとかdeleteとかのメソッドを呼び出すと落ちるらしい。対処法をいろいろ調べて、結局scrubを噛ませることにした。本当は不正な文字列は\x??みたいにバイト表記をしたくてscrubにブロックを渡してガチャガチャやっていたが、どうにもうまく行かず、結局素のまま。

ゴミ出しとかもやっていたら、気づけば午前10時を回ってしまっていた。これから寝ると帰省できない可能性が生じるので、このまま徹夜で新幹線に乗ることにする。エンコードした動画を投稿して、適当にノーパソと本を持って出発。

仙台駅についてお金を下ろし、切符を買ってからどこかで食事をしようと歩いていると、動画でゆっくりの声が聞こえない部分があるとの指摘が来た。慌ててフリーWi-Fiを捕まえて当該箇所を確認すると、確かに聞こえない。後ろに表示していたはずのクレジット表記も存在せず、BGMだけが流れる中ゆっくりが交互に口パクする恐怖映像となっていた。まあ挨拶してるだけなので声が聞こえないのはいいが、クレジット表記が見えていないのはまずい。かといって今から修正もできないので、動画の概要欄に書き足しておいた。

丸亀製麺で食事する。セルフサービスの店は客がいろいろ触れる必要があってヤバそうという気持ちになる。あとシンプルに混んでいた。

ゲーセンにも行っておく。普通に2クレ、スマホアームが設置されている台に移動して1クレ。動画を撮ったので、帰省してから投稿した。

新幹線に乗る。

仙台始発の東京行きやまびこに乗る。1両にどれくらい人がいただろうか？仙台を出発するときは1両に1桁人しか乗っていなかったが、東京に近づくにつれて単調に増加した。僕は大宮で降りたが、このときも別の車両からは10数人降りていて、思ったより多いなあという感じ。 大宮で乗り換えの待ち時間が20分発生した。1つ飛ばしで座るベンチは、空きが少しだけある。平常時とは比べるべくもないが、そこそこの人がいる。 大宮からまた自由席に乗る。今度は最初からかなり人がいる。1列に1人くらいか。これは目的地・富山に着くまで単調に減少し、僕が降りるとその車両にはもはや1人しか乗っていなかった。

週記（2020/08/10-2020/08/16） - kotatsugameの日記

今回も仙台駅始発。人数に関してはあまり変わりはない。大宮では、今日は1時間の待ち時間が発生した。僕が降りた駅でも数人乗ってきて、ここから金沢まで新幹線か〜という気持ちになった。

途中ECR101のhackフェーズとシステスが終了して、4位となっていた。E問題でロリハを使った人がたくさんいたらしく、衝突させられていた。僕の解法だとそういう文字列マッチング系統のアルゴリズムを使う場所がないのでかなり謎に思っている。

新幹線内（と帰ってきてから数ページ）で「放課後探偵団2」を読んだ。特に「願わくば海の底で」という短編が良かった。東日本大震災から5年後を舞台に、当時を振り返りつつ行方不明の人が最期にいた場所を探す話。ちゃんとミステリー風味になっていて、またお話としても面白い。

SASUKEを見つつTwitterをしていた。SASUKEを見ながらTLを眺めると、同様にSASUKEを見ている人が浮かび上がってきて面白かった。カクテルパーティー効果。ところで、この時間は絶対無駄なのにテレビの前から動けなかった。やっぱりテレビは最悪の家電。

微妙に元気なのでこたつで寝落ちせず、風呂に入ることができた。出ることができなくなりかけたが、ギリギリ脱出。するとまた微妙に目が覚めたので本でも読むかと思ったが、今度こそ寝落ちしそうになったので慌てて就寝報告した。午前1時だった。

12/29(金)

昨日の日記に吸収された。

12/30(土)

午後2時起床。13時間も寝られて偉い。途中、謎の高齢男性が謎の音を発しているのが聞こえた気がして一瞬目を開けた。これが現実だと認められなくて再度寝た。

床屋に行って、本屋さんに寄って帰ってきた。今日も新刊を2冊買った。

レコード大賞がテレビで流れていたが、知っているのが「香水」しかなかった。LiSAは名前を聞いたことあるぞと思ったのに歌が「紅蓮華」じゃなくて謎、と思っていたら今日歌うものも鬼滅の刃関連の歌らしい。

PASTの残っていた問題を解きつつラノベを1冊読んだ。「強気なお嬢様が俺の料理で甘々に」。かなり面白いと感じた。主人公の、料理にしか興味がなく他の物事を一切無駄だと断じる様が気に入った。ただラノベの宿命としてヒロインに興味を持ち始めてしまう。それはそれで、一般的なラブコメと同様に楽しめる。

このような感想をツイートしたところ作者に拾われた。ラノベを新刊で買って読むと、最近は結構作者のTwitterアカウントに補足される。僕もそれをわかっていて作品名とともにツイートしている。ファンレターを書いたことはないが、ツイートするだけで作者に届き得るのは面白い。本を出す人は結構雲の上の人という感じがあるが、実はそうではないというのが最近わかってきた。

こどふぉのGood Bye 2020に出るので、環境を整える。今年は実家のデスクトップではなく持ち帰ってきたノーパソを使おうと思う。

異なるサイズのディスプレイを同時に使うのは難しい。マウスの移動が直感的でない。設定でずらしたりすればいいのかもしれない。試しにということでPASTの問題を最後まで解いたが、HHKBに慣れてきた状態でHHKB以外のキーボードを使うと破滅する。

PASTの問題に関しては感想はない。今回は特別簡単なように感じたが、最終問題に関する言及をTLで見てしまったからかもしれない。前の有志コンで出た云々というツイートに心当たりがあって、まああれだろうな……と思っていたら確かにそれだった。

Good Bye 2020は7完で135位。Hに崖がある状態でGに無限にペナを付けてしまった。predictorは+9なので、最近微妙に違うのを勘案してもIGMのまま年を越せそう。

Aはよく読めなかったがサンプルを見て完全に理解。(0,1)を(1,0)に読み間違えていた。Bは前からやるだけ。Cは、こういうのは貪欲に変えていいはずだったが証明ができないのでとりあえず書いた。サンプルがあったので提出。うっかり1WAしたがアルゴリズムに問題はなく、次で通った。冷静になるとこの貪欲は当たり前。

Dも自明。Eもバラすだけなのに丁寧に紙で計算していた。結果を見て初めて気づく。Fは出力が辞書順最小でなければならないことを見落として1WA。そもそも根本的にアルゴリズムを変更する必要があった。最初はUFの連結成分に1点だけの頂点を含むかフラグを持とうとしていたが、これはUFの実装に手を加える必要があった。もうちょっと考えると、超頂点を設定するだけで良いことに気づけた。

Gは再帰的にやる。1を2つに分けようとすると1がそのまま残ることに気づかず、別の部分を高速化していた。最初にs_0とマッチングするのは、「任意の1文字」を含むパターンマッチなので難しい。2乗だと間に合わなさそう。畳み込みの方法は流石に大げさなので、以前PCKで見たbitsetを用いる方法で実装した。ある文字を見たときに、それがパターンのどの文字と一致するかを前計算しておいて、今何文字目までマッチしているか？を表すbitsetに&=する。あとはそれをシフトしつつやっていけばよい。

終わってからラノベをもう1冊読んだ。「姫騎士征服戦争」。古めのやつで1巻打ち切り。なんとも言えない。

日記を書いている間にシステスも全部通ってハッピー。ただしもう午前6時なのはいただけない。結局午前7時就寝。

12/31(木)

午後4時半、起床。昨日のこどふぉのレート更新が来ていた。2643→2656(+13)だった。年末なのでレーティング変化をまとめてツイートしておく。

チュウニズム、別に辞めたわけではないが、レートが一切上がっておらずびっくりした。確かに既存曲の新規鳥はご無沙汰かもしれない。

去年より2167問多く解いた。AtCoderで1000問弱、あとはCodeforces、yukicoder、AOJで300〜400問くらいの新規ACか。AtCoderはOther Contestsを巡回したのが効いたのだろう。ABCで毎週6問増えるとはいえ、それでも300問にしかならない。

競プロ流行語大賞の発表があった。僕が関係するものでは、Vec<Vec<Vec<Vec<Camera>>>>とペペロンチーノの作り方がそれぞれ1ptと2ptでランクインしていた。ありがたいことだ。

kotatsugame.hatenablog.com

「百億の金貨と転生者」を読んだ。そこそこ面白かった。設定とかはいい感じ。

紅白が始まる。概ね読書をしていて、興味のある歌手の出番だけ見ていた。「香水」とGReeeeNと「夜に駆ける」。GReeeeNは最初黒いシルエットで出ていたのに、歌い始めたら急に顔まで鮮明になったのでビビった。最初は放送ミスを疑っていたが、どうやらそういう演出らしい。戸惑っている間にキセキを歌い始めたので、慌てて歌に集中した。

「夜に駆ける」は非常に良かった。歌っている場所も気になっていたが、あとからツイートで流れてきた。

「雪には雪のなりたい白さがある」を読んだ。短編5本。どれもちょっと陰鬱なスタートで、そこからなにか希望を得たりする過程が描かれる。創元推理文庫から出ていたが、特に日常の謎の話ではないようだ。あらすじに「約束の真実が明らかに」と書いてあったのでそういうつもりで読んだのだが、純粋に人の気持ちとかの話だった。ともかく、面白かったことに違いはない。

このあたりで買ったり読んだりした本に関する記録の12月ぶんをつけ、1年を通して合計した。

去年は290冊読んだらしいので、減っている。買った本の冊数は去年は記録しておらずわからない。先週の週記に書いたことが達成できてよかった。

現在は366-105冊なので、あともう6冊読んで、せめて1年で366-99冊読んだことにしたい。

週記（2020/12/21-2020/12/27） - kotatsugameの日記

日付が変わったあと、2020年に読んだ小説・なろうからおすすめを10個くらい選んでブログ記事にまとめようと挑戦してみたが、本の選定から躓いてしまった。その本がどのくらい好きかなんてふだん一切考えないから、「印象に残っているか」をもとに判断しようとしたのだが、それはシリーズ全体として見て巻数・文章量が多ければ当然印象に残る。かといってシリーズの中途半端な巻を挙げようとしてもそんなピンポイントに覚えていないし、冊数の少ないシリーズに絞るのもなんだかな、という感じ。

あとは、実際に挙げてみたら思ったよりラノベが少なかったというのもある。一般小説の数倍ラノベを読んでいるはずなのに、絞り込んでみれば半々になってしまった。ラノベが一般小説よりも低俗であるという認識は拭い去り難く、今も心の奥底にこびりついている。これを如実に物語る結果となったので、表に出すのには気持ちの整理がつかない。

部屋にある読了本を実家に持って帰ってもらうことにする。

週記（2020/11/09-2020/11/15） - kotatsugameの日記

これが部屋に置かれていたので、本棚に詰める。詰める前に一旦全部出して床に積み、写真を撮った。その後本棚に詰めたあともう一度写真を撮っておいた。カウントしたら126冊だったが、棚を前後2列で使って収納したら2段にも満たなかったのが衝撃。

午前5時、就寝。

01/01(金)

午後3時半、起床。昨夜からずっと涼宮ハルヒの直観を読んでいて、午後10時半くらいに読み終わった。誤植が話題になっていたのを思い出して探してみようかと思うも、面倒になってツイッターで検索。直接何ページなどと書いたツイートは見つからなかったが、電子書籍で購入した人が全文検索の結果をツイートしていたので、それの前後の文章をもとに誤植の箇所を特定し、ツイートした。

本の感想はあんまりない。単体で読んでも十分面白い話だとは思うが、徹頭徹尾「涼宮ハルヒシリーズの続刊」という意識で読んでしまって、読めただけで大満足という感じ。

主人公の発言がほとんど地の文になっているのがなんとも読みにくい。

週記（2020/12/21-2020/12/27） - kotatsugameの日記

以前このようなことを書いた。涼宮ハルヒの直観も、キョンの発言はだいたい地の文になっているが、こちらは格段に読みやすい。この違いはなんだろう。結局誰がどこを喋っているかがわかるのが重要で、その点涼宮ハルヒシリーズとは長い付き合いだからセリフから発話者を特定しやすいということだろうか。

読書記録のブログ記事は12000字を超えてしまい長過ぎるということで、ちょうど年も変わったことだし新しく作ることにする。

kotatsugame.hatenablog.com

昨日から、1階のWi-Fiルーターから2階の自室に電波が届かない！とイライラしていたが、Wi-Fiルーターに問題があったようだ。父が1階のパソコンからインターネットに接続できないことに気づき、ルーターを再起動したところ直った。

日付が変わってから午前4時半くらいまで寝ていて、一旦起きたあと再度入眠できなかった。この寝落ちの前後ではTechFULの「新春 TechFUL Coding Battle 2021」を進めていた。どれが何点だったかは公開してよい情報だったはずだ。

今回はかなり注意深くコーディングを進めており、結果として最終問題以外のスコアは理論値を出せたと思う。タイムボーナスというのがあって、これは目標タイムより速く正解できればその分スコアが高くなるものだが、スコアの計算式を忘れたので何分以内に解ければ最大にできるのかわからないのが怖い。このせいでひたすら焦ってしまう。

結局、最終問題でめちゃくちゃ詰まってしまった。煩悶しているうちに夜が明け、親が起きてきてしまった。朝ご飯を用意してもらったはいいものの、その時点でまだ解けていなかったので食卓につけず、申し訳ない気持ちになる。それから10分くらいでなんとか正答にたどり着くことができたのは良かった。それまで1位だった人のスコアは990点で理論値だと思っていたのだが、どうやら今回は問題数が多かったらしく、僕のスコアはそれを上回る1001点になって、この日記を書いている現在は全体1位だ。

食事してちょっとラノベを読んだあと、夜のABCに向けて再度入眠。午前11時半だった。

01/02(土)

午後7時起床。午後3時くらいに一瞬起きて書き残した夢日記が下書きにあったので、投稿。いわゆる初夢である。

食事・入浴を済ませたらすぐABC187が始まった。優勝した。A問題のコードゴルフには1分くらいかけたが、それ以外は特にすぐ短くなりそうな問題がなかったので、最後まで突き進んだ。解法も全問すぐにわかったのでよいタイムが出せた。

A問題はdcが短い。BはRuby以外試していない。CとDはPerl。ここまではコードゴルフの話。

E問題は任意の点対でやろうとするとLCAが必要になるが、今回は辺の両端が対象なのでどちらが根に近いかわかればよい。これは深さを計算しておくとわかる。

F問題はO(3^N)が思い浮かぶが、N<=18なので少し怖い。そこで、遷移の際にあるbitを必ず含むようなものだけを考えた。計算量解析はしない・できていないが、3^Nよりは少し小さくなるだろう。最大ケースがサンプルにあって、十分な速度で通るので提出、AC。冷静になるとO(3^N)をそのまま書いても良かったようだ。

B問題に関しては、x+yiという複素数に関してy.abs<=x.absを調べるところで大幅な改善があって最短を取られた。((x+yi)**2).real=x**2-y**2>=0で良いようだ。

「セプテムレックス」というラノベを読んだ。7つの大罪のそれぞれを背負う悪魔が出てきてなんやかんやする話。各悪魔には特殊能力がある。「怠惰」の悪魔が主人公。

槻影「堕落の王」も似たような設定。これは僕のラノベ遍歴のほとんど最初期に購入した作品でかなり印象に残っている。僕が初めて読んだ槻影さんの作品でもある。これ自体は2巻で打ち切りになってしまったようだが……。

将来について少し考える機会があった。生きていくだけなら、学部卒でプログラミングの仕事をすれば大丈夫だろうと楽観視している。ただ、高校の先生から言われた「お前は将来なにかすごいことをすると思っている」という言葉や、数学で興味のある分野を探すこともできていないのが未練として残り、数学科にしがみつこうとしている。4年生になるとゼミが始まるので、そこで何らかの結論が出せるだろうか。「とりあえず修士には行く」は正解なのだろうか。

考え始めると嫌な気持ちになるので、考えたくない、が、考えなければならない。

1/4が提出期限のレポートが存在する。12/22に掲出されてからずっと放置していたが、そろそろ手を付けなければマズい。演習のレポートだが、この科目は講義も演習も今セメスター一度も勉強していないためである。講義資料が11回ぶん上がっているので、頑張って目を通していくが、Twitterやってる時間と半々くらいになってしまう。結局途中からラノベを読み始めてしまい、この日は第4回の冒頭で終了。レポート問題も少し眺めてみたが、1つ目の大問の(3)で詰まってしまった。一応2つ目の大問は解けそうだが、焼け石に水。

布団に入ってから更に1時間ちょっとハーメルンを読んでいた。意味不明。午前7時半、就寝。

01/03(日)

午後6時起床。帰省してから有意に睡眠時間が伸びている気がする。非常に困る。基本的に7時間くらい寝たら起きるだろうという見込みで一日のやりたいことを考えているのに、実際はもう全然ダメで、何もできていない。

とりあえず夕食を食べてラノベを読む。「いわくつき魔族教師と天使候補生」。著者の柳実冬貴さんといえば代表作は「対魔導学園35試験小隊」だろう。本棚に4年積んである。

読み終わったら午後9時だった。講義資料を読む作業に戻らなければならない。残り8回。このあと6時間くらいずっとPDFファイルとにらめっこしていて、第10回まで目を通した。第11回を読む前にレポート問題を見直すと、大問1が何を言っているかについてはわかるようになっているので、ここで一旦レポートを作ってみることにする。

似たような問題が例として講義資料で紹介されているので、それを見ながら書く。「〇〇のガロア群が位数4の巡回群となっていることを示せ」にどう答えるかひとしきり悩んだ。どう悩んだか言語化するために講義資料を見直していたら、わかった。ガロア群の元がある多項式の根の間の置換と見れることを納得できていなかったようだ。そういう補題も講義資料にちゃんと書いてあった。ここが怪しかった（例から多分そういうことをすれば良いだろうというのはわかっていた）ので、議論がフニャフニャしていた。

大問2まで書いたところで切り上げる。そこから先は問題を読んでいなかったので、とりあえず今日は読むだけにして明日やろう。明日が期限。もう午前6時になってしまった。