読書記録（2021）

kotatsugame.hatenablog.com

1月

  • 1日
    涼宮ハルヒの直観
  • 2日
    セプテムレックス
  • 3日
    いわくつき魔族教師と天使候補生
  • 4日
    人生∞周目の精霊使い
  • 5日
    クラスの大嫌いな女子と結婚することになった。
    僕はリア充絶対爆発させるマン
  • 6日
    僕はリア充絶対爆発させるマン2,3
  • 8日
    見習い巫女と不良神主が、世界を救うとか救わないとか。
  • 9日
    デスゲームから始めるMMOスローライフ
  • 10日
    デスゲームから始めるMMOスローライフ2
  • 11日
    デスゲームから始めるMMOスローライフ3

週記（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を求めるということができていなかっただけにも見える。

週記（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時になってしまった。

読書記録（2021）

kotatsugame.hatenablog.com

1月

  • 1日
    涼宮ハルヒの直観
  • 2日
    セプテムレックス
  • 3日
    いわくつき魔族教師と天使候補生
  • 4日
    人生∞周目の精霊使い
  • 5日
    クラスの大嫌いな女子と結婚することになった。
    僕はリア充絶対爆発させるマン
  • 6日
    僕はリア充絶対爆発させるマン2,3
  • 8日
    見習い巫女と不良神主が、世界を救うとか救わないとか。
  • 9日
    デスゲームから始めるMMOスローライフ
  • 10日
    デスゲームから始めるMMOスローライフ2
  • 11日
    デスゲームから始めるMMOスローライフ3

週記（2020/12/21-2020/12/27）

12/21(月)

午後4時に寝て、午後7時に起きた。目覚ましで意識を取り戻したはいいものの、そのままでは二度寝してしまっていただろう。ただ眠気を吹き飛ばすようなことがあって、無事起床に成功した。

今日提出のレポートが1つ残った状態で寝たのだった。この期限は今日の日付が変わるまでである、ということは確認していたのだが、教員が何を考えたか「採点を終了しました」と講評を出していた。

「提出していない人も多く」←期限より先に締め切っているのだから当たり前である。さすがに指摘したら修正されるはずなので、一応コメントを送っておいて、当初の予定通りサークルの解説会が終わった後にレポートを書くことにした。

サークルのABC185解説会は、ホスフィンがF問題を担当してくれるとのことなので、残り時間でEから遡ってスライドが作れた分だけ発表することにした。結構時間を食うので、結局DとEしか発表できなかった。

ABC186のゆっくり実況が2000回再生を突破していてかなりうれしい。

レポートを書く。練習問題を解くが、そのすぐ上でやっている証明を真似したら簡単に解けた、と思う。自分では正しいことを書いているつもり。送ったコメントには返信がないが、かまわず提出した。

AOJのレーティングが更新されていた。一週間で250くらい上げた週もあってすごい。現在は1265.08。

日付が変わって、教員からコメントが返ってきた。

受け付けてくれるようだが、講評にヒントを書いてしまったので公平になるよう何かの処置があるらしい。僕は「ヒントが出された後に提出して」「ヒントを一切見ずに解いた」のでかなり辛い。こんなだったら思いっきりヒント見て解いたんだが……。

「ラノベのプロ！」を読んだ。ストイックなラノベ作家が主人公。描かれる主人公のラノベ書きに対する取り組み姿勢は僕の理想的な競プロへの取り組み方に似ているものがあると感じて面白かった。ゲームを一切しないとか、健康に気を使っているとか。僕は今あまり健康に気を使えていない。

月曜日公開のyukicoder アドベントカレンダーコンテストの問題は、負辺ありの最小費用流だった。これまで毎回ベルマンフォードに書き換えていたのだが、ここらで一念発起してライブラリに負辺ありの場合を組み込むことにした。結局ポテンシャル計算だけ最初にベルマンフォードで行えばよいので、add_edgeごとに負辺かどうか判定して、min_cost_flow呼び出し時に負の辺が存在したらベルマンフォードを行う。負閉路があるとassertで落ちる。min_cost_flowを複数回呼び出すことは想定していない。

午前5時くらいに就寝。睡眠時間を短くすると生活リズムも正されるのかもしれない。

12/22(火)

正午前に目を覚まして、Game of Vampireを読み返していた。午後1時半くらいになって、学食が閉まりかけていることを認識して向かう。

今日はそこそこ早起きだし市街地に出かけようか、と思っていたのだが、購買で買ったお茶などを家に置きに帰ったところ、眠すぎて布団に倒れこんでしまった。そのまま2時間弱の睡眠を3回程度繰り返し、午後8時になってしまう。睡眠時間を短くすると生活リズムが正されるというのは真っ赤なウソで、実際は一日中眠くてどうしようもなくなるだけ。

午後9時からのサークルのバチャに参加する。今日はこどふぉ#543。

A問題から難しい。途中順位表を見ていたが、ACしている人数も少なめなので、自分がドハマりしているわけではなさそう。そのまま44分+2WAかけて通し、B問題に進む。アナウンスでBよりCDのほうが簡単だといわれていたようなのだが、見ていなかった。Bは結構素早くわかって証明もできていたはずが、実装ができていなかったためこれも2WA。

CはZalgoやるだけ、Dは木DPを頑張るだけ。確かにB問題よりも簡単といわれても納得。結局4完で、現在の順位表（リアルタイムの人と僕より先にバチャをやっていた人）では19位になった。

アナウンスを読むと、この回がかの有名な「unethical and ugly behavior」の回だということがわかる。19位という数字には、unratedだったのもあって人が少なかったことも影響しているのかな。

そのあとはまたGame of Vampireを読み返していた。午前3時くらいに寝落ちした。

12/23(水)

午前9時、目を覚ます。またYouTube流しっぱなしデスクライト点けっぱなしエアコン付けっぱなし部屋の電気点けっぱなしで寝ていた。

第32回TechFULコーディングバトルの解説が公開されていた。昨日の深夜から言及が可能だったようだ。僕もここで言及しておこう。

3問目からいきなり難しい。負の数の四捨五入がどういうものかよくわからないが、ググると0.5足して切り捨てればよいらしい。誤差が怖いので全体を10^4倍して整数で持っていたのだが、負の数を切り捨てるのに失敗していた。これに気付かず2WA出して、最終的にはdoubleで持ってsetprecision(3)をしてしまった。そのあと負の数を切り捨てるのを直したコードでも通った。丸め方向の関係でsetprecisionと自前の計算で異なる場合があると思っていたが、ないことが証明できるか、テストケースにそのようなケースが存在しないだけか……。

8問目は最初TLEしてしまった。自分がうっかりヤバい探索を書いていたのか、それとも向こうの環境が僕のlog2つに耐えられなかったのか。冷静になるとlogは1つでできるので、それを書いたら通った。

10問目もTLEしてしまった。うっかりNTTに帰着してしまったが、もっと冷静になると個数無制限ナップザックみたいな更新をすることで線形時間で更新できる。そんなところに重めのlogを置くと落ちるのは当たり前なんだよなあ。ただ、手元では最大ケースでも3秒ちょっとしかかかっていないはずなのにTL 5秒でTLEしてるのはさすがに環境が貧弱すぎるのでは。

総合では5位だった。また1000円ゲットした。なんかTechFULのシステムがひたすら苦手らしく、微妙な順位しか取れない。といってもまだ2回しか参加していないからたまたま下振れしているだけかもしれない。

昨日は学食に徒歩で行ったら思いのほか時間がかかって学食が閉まりかけたので、今日は少し余裕をもって出発する。食事して帰宅、少しパソコンを触ってから今日こそ市街地に行こうとすると、電話がかかってきていたことに気づいた。折り返し電話をかけても通じなかったが、そのあとすぐさらに折り返してきてくださって、やっと会話できた。

リクルートの人事の方だった。インターン面接の結果発表。僕は一応合格ではあるらしいが、僕の適正を考え合わせると案内できる仕事がないので、冬のインターンには参加できないらしい。謎。

どうやら不合格をオブラートに包んでいるだけということはなさそうだし、インターンの面接に合格できただけで十分うれしい。つまり、自分の現在の能力や将来的なポテンシャルが評価され得るものであるということなのだから。インターンの面接に合格したという実績だけ得て実際の労働を回避した点でアドである、という指摘もあった。

実際どういう扱いがされるのか、またの機会に応募するとしたらどんなスキップができるのか（あるいはできないのか）は、何もわからないが、年明けに人事の方がまた面談をセッティングしてくださったので、そこで明らかになるだろう。

市街地に出る。まずはメロンブックスに行ってラノベの新刊を買う。「公女殿下の家庭教師7」と「辺境都市の育成者2」の連動購入特典を楽しみにしていたのだが、売り切れていた。12/19の発売日に行かなければならなかったのか、残念。他にも数店舗回って、チェックしてあった新刊で今日までに刊行されたものをすべて買い集めた。

ゲーセンにも行く。特に成果なし。午後9時からSRMがあるので、午後7時半くらいに切り上げる。ラーメンを食べて帰ろうと思い立つ。ラーメンパンチという店があって、移転したのだが、跡地もラーメン屋になったことをTwitterで見聞きした。そこへ行ってみたが、たまたま水曜日が定休日らしく閉まっていた。仕方なく一閃閣へ。無難。

今日買った本たち。

ふぁぼん氏と「このごろ毎月隣人のクール美少女と半同棲する本が出ている」との共通見解を得る。僕のラノベ遍歴においてはまず「お隣の天使様にいつの間にか駄目人間にされていた件」が出現したので、これがヒットしたことによる影響だと考えている。

SRM796に出る。EasyとMedを通して24位、2306→2328(+22)。

Easyは読解。読んでやるだけ。何がしたいのか意味不明。

Medも読解。重要な制約が2点、「ヘビは壁際にいない」「ヘビの頭は現在の胴体を跨がず空きマスのうち半分より多くに移動できる」とあった。前者はわかりやすく、想定では壁際を一周することがわかる。後者がよくわからなかった。

よく考えると、壁際のマスは8x8の盤面では28マスあるので、後者の制約を満たすためにはヘビの頭は胴体を跨がずに壁際のマスまで移動できなければならない。つまり、胴体の移動をシミュレートしなくても頭は壁際まで移動できるという話。

僕は胴体の移動もシミュレートして行動を幅優先探索し、13ステップで打ち切ったが、通った。あんまりよく考えていないが、ヘビの長さが最大の26だった場合は13ステップ以上移動すると全体で80回の移動回数制限に引っかかってしまうということから設定した。ヘビの長さがもっと短い場合を何も考えていない。

一年を振り返るブログ記事の構想を練っていた。読んだ本・なろうから何らかのランキングを作ることを考えていたが、一気読みして作中世界にどっぷり浸かるなろうに対して、新刊が出るたびに少しずつ読み進めるラノベは印象に残りにくいことに気づいた。もちろんシリーズ一気読みとかもあるんだけど、なろうと比較すればほとんど行わない。

午前3時くらいに就寝。

12/24(木)

いつから起きていたか記憶がないが、起床報告をする前から布団でゴロゴロしつつ二度寝しようとしていたはず。結局二度寝できずに午後3時に身を起こす。

学食の夜の部が始まるのを待って行く。午後5時くらい。店員さんは結構な人数がいるけど、客は全然いない。10人強くらいか。採算が合っていなさそうでつらい気持ちになる。ただ、帰宅途中にグラウンドの横を通ったら、部活をしている人が結構いたから、遅い時間になれば客の入りはそこそこ増えるのかもしれない。

午後7時からXmas Contest 2020に出る。最初に全体をざっと眺めていたが、今年はコードが極端に短くなるような問題はなさそう。真面目に取り組むことにして、最初にDの実験を繰り返していた。Nを固定してCをいろいろ変えながら出力を見ていたが、特に特徴的なことはなさそう。OEISに投げても反応なし。余因子展開して帰納的にできないか考えていたが、どうにもうまくいかなかった。

あきらめて順位表を見たところ、CのACが出ていたので、これを考えることにする。ナイーブにGrundy数を求めて出力してみたところ、0102101021021...というような出力が続く。01021と01021021で構成されているように見えるが、このどちらが出現するかはわからない。そこで、それぞれ010210→1、01021021→2と置き換えて出力してみることにした。今度は12122...となったので、さらに12→1、122→2と置き換えて出力してみる。

今度も12122...になったところで何となく予想がつく。おそらく再帰的な構造になっているのだろう。証明はしないことにする。そこで、それぞれのパーツの長さを下から順に求め、Grundy数を求めるときは上からどのブロックに位置するか求めていくコードを書いた。ナイーブな出力と突き合わせると一致したので、提出してみたところ、通った。

そのあと、H問題に挑んだ。制限時間が6secだったので、定数倍高速化だと考える。subsetに渡る和を取るのが非常につらいが、__int128を使って余りを取る回数を減らすと、手元で8sec弱になった。subsetのループを何とかする。具体的には、下6桁を64通り場合分けして、それぞれでループの内容を埋め込むコードを生成した。これはいったん和をlongに溜めたあと__int128に加算することができるのが効いて6.3secくらいになった。しかしどうやら手元よりAtCoderで動かしたほうが微妙に遅いらしい。まあそれがなくてもTLEなのだが、後から確認したところN=21のケースでは常にTLE打ち切りの6.6secになってしまっていて残念。

結局解けなかったので解説を読んだが、よくわからなかった。そもそもsubset convolution未履修。

「ラノベのプロ！」2巻を読んだ。ラノベの流行り廃りや打ち切りの方針に関する話が出ていて興味深い。こういうのは出版された直後に呼んだほうが当時のラノベシーンの空気感と照らし合わせてよかったな、と思う。打ち切りに関して、「昔はどのレーベルも2巻や3巻までは出して様子を見ていた」という発言がされていた。確かに、実感として2巻や3巻で終わるシリーズは非常に多い。どこかのあとがきで「3巻がシリーズ存続の山場」と書かれていたのを覚えている。しかし今はそうではなく、もっと早い段階で打ち切りの決定がなされるようだ。ところで、打ち切りの話をしている巻でこのシリーズ自体も打ち切られているのが皮肉的。

もう1冊読む。「両親の借金を肩代わりしてもらう条件は日本一可愛い女子高生と一緒に暮らすことでした。」という題名。題名・あらすじ・イラストに惹かれて買った。「ラノベのプロ！」によれば、これはラノベのパッケージングが僕に刺さったということ。ただ文章がどうにも合わなかった。外側だけ見て買っているのでそういうことはある。主人公の発言がほとんど地の文になっているのがなんとも読みにくい。

デレマス㊙情報というTwitterアカウントが今年も企画をやっていたので、一連のツイートを読む。去年も読んだなと懐かしい気分になる。毎年面白い。

Tamer's Mythology書籍版の続刊が決定したらしい。非常にうれしい。次は第2部ということか。あと一押し、3巻まで出てくれればフィルが王都に帰るのを読めるかもしれない。

金曜日は2限の時間帯に小テストがあるらしいので、起きる必要がある。布団でなろうを読んでいたら午前6時になってしまったので、午前10時半に起きることを強く念じつつ就寝。

12/25(金)

10時の目覚ましでは起きれなかった。10時半の目覚ましで起床。よく考えると、小テストの開始時に起きるのはまずい。慌てて顔を洗い、ブラックサンダーをかじりつつ投稿された小テストを確認する。

45分間より少し短い時間、頑張って解いたつもりだが、半分しか解けなかった。シンプルに演習不足。あとここ3週間分の講義内容に目を通しておらず、後半の問題はそもそも理解ができなかった。せっかくなので講義スライドを読んでから布団に戻り、午前1時ぐらいから二度寝した。

次に起きたら午後7時半だった。何らかの睡眠負債が溜まっていたのかもしれない。

ima.goo.ne.jp

話題になっていた記事を読んだ。創作物における天才のテンプレートみたいな感じですごいなあという気分になる。

高評価がついに100件に到達した。非常にうれしい。

こどふぉでICPCのミラーに出る。午後8時半からの5時間コンテスト。適度なところでやめるつもりだったのに意味不明なくらい好調で、結局5時間フルに参加してしまった。結果は全完で全体7位、個人としてはtouristに次ぐ2番手だった。戦略としては、1問解くたびに順位表を確認してその時点で最も解かれている問題を読む、というものを採用したのだが、1度も詰まらず毎回読んだものを通すことができた。以下、解いた順番に言及していく。

Eはやるだけ。最も簡単だった。Nもちょっと怖い見た目をしているが、やるだけ。Cもやるだけ。Fは平行で180度逆なベクトルのペアを数えればよい。Kは面倒なことを考えずに障害物の候補を全探索。判定を間違えて1WA。Dは貪欲だが、条件などの±1をミスって2WA。よくわからなくなって貪欲の順番を変えたりしていたが、大きいほうからと小さいほうから、どちらでもよい。

Jはクラスカルっぽくやるだけ。AはLISの先頭と間に大きな要素をはめ込む形になるので、はめ込める要素が存在するかをDSTで判定、LISは二分探索できないのでsegtree。セグ木は値とインデックスをペアにして区間maxだが、インデックスを反転しておかないとダメで、1WA。Iはよくわからないが、ベクトル2つを互除法みたいにして片方のx成分を0にしたあと、平行四辺形の内部の格子点を出力したら通った。

Mもよくわからない。値ごとにそれを含む集合のインデックスを持つことにして、それを調べる。ある集合を見るとき、それに含まれる値でループして、今見ている値を含むインデックスを舐め、以前に出現したかチェックする。ただしこれは最悪ケースでO(N^2)になるので、各集合について「それを含むインデックスの個数が最も大きな値」を調べるのだけ後回しにし、逆に「これまで出現したインデックスがそこにも出現するか」を調べることにしたら通った。いろいろ考えたけど最悪ケースもよくわからない。920msだったので、もしかしたらヤバいケースが入ってなかっただけかもしれない。3TLE。

Hは消す要素の小さいほうから(K-1)/2個目と大きな方から(K-1)/2個目の間に消さない要素が存在すればOK。Gは最初目との角度を持っていたが、どうも誤差が怖いので外積で判定することにした。目と並行な道を歩いている場合に注意。中途半端な場所から隠れる場合は正弦定理で求めたが、これと同じ処理を行うと0除算が発生する。Lは素数のべき乗をチェックしたいが制約が1e18なので、何とかする。具体的には、同じ素数のべき乗を2つ持ってきて、指数に関して互除法っぽいことをすると1e9以下にできる。それが終わったら気合いで場合分け。素数のべき乗を全部入れていいのか、それともちょっと減らさないとダメなのか、2個ペアしか作れないのにKが奇数の場合はどうするのか……など。最初の、指数に関する互除法っぽいところでミスしていて3WA。

最後1時間を残してB問題に突入した。solved数はいまだに一桁だった。K_iについて考える。まずsum=0とし、j日目はA_j-K_iを足す。sum<=0になったら、前回sum<=0になった日との差を計算してsum=0に戻す。最後まで終わったら、計算した日の差の最大値が答え。これをK全部について一気にできればよさそう。

足す値は狭義単調減少なので、sum<=0になるのは右端までの区間だとわかる。K_iはインデックスごとに不変なので、K_iの係数とA_jの和をもっておけば、全体にA_j-K_iを足すのは遅延セグメント木でできて、sum<=0となる区間の左端L_jも二分探索で求められる。このL_jを日ごとに記録しておく。sum=0に戻すのも、作用素にリセットのフラグを持たせればできる。

最後に、日の差を計算するフェーズが残った。K_{m+1}=infと考えると、このときは毎日売り切れるので、以降はL_jを降順に見て、隣り合う売り切れない区間をどんどんマージしていくとできる。マージするたびに最大値を更新すればよい。見えるのはすぐだったが手数が多くて実装に苦労した。サンプルは結構すぐに合ったので提出したが、ジャッジが詰まっていて10分くらい待たされた。終了10分前にジャッジが始まって、そのままAC。

今年度の新歓期間は12月の半ばまであったが、それが終了したので、サークルの名簿などに更新がある場合報告せよとのメールが来ていた。名簿を更新して提出した。

「辺境都市の育成者」2巻を読んだ。これ（というかこの作家の著作全部）は文章やセリフに非常に癖があって読みづらいが、設定は大好きなので喜んで読んでいる。「公女殿下の家庭教師」より読みづらかったと感じたが、なぜだろう。今のところは、「キャラが多くてほとんど『弟子』というポジションなので差がわかりづらい」からだと考えている。

午前7時半くらいに寝る準備を済ませて布団に入ったが、明日のAGCに向けた睡眠調整を考えるともう少し起きていたい。なろうを読みつつゴロゴロしていた。途中空腹に耐えかねて少し物を食べた。午前9時半、就寝。

12/26(土)

午後4時半くらいに少し目を覚まし、トイレしたりTwitterを見たりしていたが、もう少し寝ようと思って二度寝した。午後7時起床。シャワーを浴びてコンビニに行き、パン・おにぎり・お菓子を買ってくる。これは今日明日の食料になる。

bashで1000ACした。ここ一か月ずっとやっていた。

ついでにHeatmapもそこそこ埋まったようなのでツイート。All ACの欄はまだ少し薄緑が残っているので、これも消えたぐらいでもう一度ツイートするだろう。

3月から4月にかけては、言語アップデートに備えてOther Contestsの未ACを埋めていた。アップデート後は0msが出せなくなることが分かっていたため、今のうちに0ms出せるものは出しておこうという魂胆。ただし、Streakを意識しだすと切りがないため、わざわざ週に1回切っていた。逆に意識していないか？毎日新規で数十ACしている中で1日何もしないのは苦痛だったことを覚えている。でもうっかり続いてしまうよりはマシかな。

AGC050に出場した。結果はBCDの3完で72位、パフォーマンス2829でレートは2675→2691(+16)。

最初の1時間はずっとA問題を考えていたが、結局解けなかった。あきらめてBに行く。まず実験して規則を見ようと考える。添え字mod 3ごとに1の個数が等しければOKかと考えたが、反例が山ほど見つかる。ほかにも少し試したが、どうにもわからない。冷静になって制約のN<=500を見ると、これは区間DP。実際に区間DPできるので、できる。

Aに戻ろうかとも考えたが、今更通してもどうしようもないのでCに行く。すぬけ君が動くのを邪魔するようにブロックを置くのがよくて、すぬけ君は左にも右にもブロックがある状態になったらその中間地点にいるのがよい。ブロックを置くたびに区間の幅（すぬけ君が動けるマスの個数）-1がどう変化していくのかを見ると、BS...(k個)...SBS...(l個)...SBというターンのとき、min(l,k//2)になる。-1することによって'S'の個数と対応付けられ、式に±1が出なくてかなり綺麗。

結局、2べきごとに幅が0になるまでの手数が変わることがわかるので、0...20くらいまで持っておけばDPできる。累積和を同時に計算しておいて、それで一気に更新。'B'が出現する位置より左からは更新できない。最初に'B'が出現するときも別に処理しておく。

最初0...19で提出したらWAだったが、すぐに間違いに気づけて良かった。まあサンプル2つ目はそこそこ強そうだし、これで間違えるようならあとは制約に関することかmodを間違えているだけだと見当がつく。

Cを通したが、あまり順位がよくなかった。残り一時間、やはり今更Aが解けてもどうしようもないので、とりあえず30分くらいDを考えようとする。よくわからない制約。制約だけ見れば半分全列挙だが、この問題に対してはどうしようもなさそうなので、やたらめったらキーを持つDPだと睨む。遷移がループしそうに見えたので、連立方程式を解くタイプかと思ったが、ループはしない。具体的なDPのキーを考える。

対称性がそこそこあるので、今具体的に誰が残っているかは知らなくてよい。「今i人目を見ていて、j回目のターンで、残りの商品はk個で、すでに抜けた人はl人」くらいあればよさそう。ちょっと考えるとl==K-kが言えるので、キーは3つになる。この時、実際に商品を獲得できる確率はk/(K-j)となるので、確かに計算できている。(i,j,k)に対して、残っているN-(K-k)人それぞれの確率を計算する。つまりDP配列は4次元になる。コードを書きながら遷移を考える。

(i,j,k)から遷移するのは、(i+1,j,k-1)と(i+1,j,k)。正確にはこれらを計算した後に貰ってきて合算する。ただしi+1==Nのときは人が一周するので、例えば(i+1,j,k)の代わりに(K-k,j+1,k)を呼び出すことになる。この時、残っているN-(K-k)人をK-k...N-1にマッピングしている。今見ている人が商品を獲得できなかった場合はK-k...N-1それぞれを今のDP配列に足す。商品を獲得できた場合は、人数が1人少ないDP配列が戻ってくるので、自分の場所で分割してk/(K-j)を割り込ませる。

しばらくガチャガチャやっていた。サンプル1は比較的早い段階で合ったのでオッとなったが、サンプル2が合わない。いろいろ修正して、最後に割り込ませる処理の添え字が少し違ったのを直したら合った。サンプル3を試すと実行が終わらなくて顔面真っ青になるが、よく見るとメモ化できていなかった。そこを修正したらなんとサンプル3も合って、提出したら爆速で通った。これで64位まで浮上した。残り30分である。

solved数を見ると、やはりCもDもかなり解かれている。これは解けるべき問題だったので、チャレンジしてよかった～という気持ち。EFはもうペンペン草も生えない不毛の荒野と化しているので、満を持してA問題に再度向き合った。無向辺のつもりでa->bとb->aを両方張ると一瞬で終わることに気づく。2べきで一生考えていたが、どうにもうまくいかない。そもそも、ループを2つ組み合わせたらそれ以上新たにつなげるのが難しくなる。残り5分で3のべき乗じゃないかと考え、三角形をたくさん作ってみたが、全然うまくいかず、絶望のうちにコンテスト終了となった。

Dに取り組んでいるあたりはコンテスト時間足りないと感じていたが、終わってみればAが結局解けなかったので、むしろこの時間で終わってよかったという感じ。TLに流れてきたi->2i,2i+1という解法を目にした瞬間、あまりのシンプルさに絶望する。これでAGC-Aは2連敗。

コードゴルフをしていたところ、A問題は1..Nを2回出力すればよいことに気づく。これは0-indexedで2i,2i+1を出力している。実現する方法はいろいろあって、Rakuは18B、dcでffと2回出力するのは17B、Vimでseqの出力をヤンク&ペーストするのは14B。ここで打ち止めかと思ったが、sedで11Bを達成できた。

atcoder.jp

面白い。まずs/^/seq /でNという入力をseq Nに変える。eオプションで、シェルスクリプトとして実行した結果に置き換える。これで1..Nが得られた。そのまま処理を終えるときに1回出力されるが、2回出力する必要がある。pコマンドを使ってもよいが、s///に存在するpオプションが（文を区切る必要がなく）短い。置換が行われたときだけ出力してくれるが、今回のコードでは必ず置換が行われる。

EとFも読んでおく。Fはまあよくわからないなあという感想しか抱けない。Eの問題設定のシンプルさはすごい。これに1800点がついて、3時間半で0ACなのはいっそ感動的ですらある。

ラノベを2冊読んだ。まず「異世界でチート能力を手にした俺は、現実世界をも無双する7」。テンプレチーレム無双。爽快感はあるので好き。

次に「隣のクーデレラを甘やかしたら、ウチの合鍵を渡すことになった」。これは非常に面白かった。最近よく見る「隣人のクール美少女と半同棲する」話。ただ序盤から一気に溶けていくので、クール美少女過激派にはおススメできない。なろう発でもなさそうだし電撃大賞の応募作品でもなさそう。どういう経緯で出版されたのか気になる。続きも気になる。僕は実は溶けてからが好きだったりするので、続刊で描かれるだろう学校での交流とかも非常に楽しみ。かなり売れてそうなので間違いなく続刊は出るだろう。

これで今月読んだ本は31冊となった。1日1冊。年単位で集計したら全然足りない。現在は366-105冊なので、あともう6冊読んで、せめて1年で366-99冊読んだことにしたい。3桁と2桁の違いを気にしている。

ECR100の録画の編集を始めた。まだF問題を解いていなかったので、解説を読んでACしておいた。全然考察できていなかったな、という感想。特に周期の長さが決まることに気づいていないのはよくなかった。勘付くくらいはしてよかったはず。C問題の途中までセリフを入れたら午前10時になったので、いったん切り上げる。

布団に入って少しだけハーメルンを読み、就寝。午前11時。

12/27(日)

午後6時くらいに目を覚まし、そのあと二度寝できずに午後7時くらいに起床。食事をしてシャワーを浴びる。AGC051。

AB二完で177位。パフォーマンスは2255、レートは2691→2654(-37)。ひどい、が、仮にもBは800点だったので、Aで3回ペナを生やしたにしては最悪ではないはず。

まずA問題。一目見てわからない。正方形と正三角形は分割できるので、どんな正整数dでも1通りはありそう。ここで順位表を見るとみんなペナを生やしているので、全部1ではないだろうと感じる。何を思ったか、dが2べきでないと作れないと考えてしまう。さっきの考察をすべて放り投げてこれを提出し、当然のようにWA。次に疑心暗鬼になり、全部1を提出して同じくWA。このあたりでようやく真面目に考える。

d=2の場合をよく見ると、内部の状態は正方形と正三角形がずれて2通りあることに気づく。これだ！と飛びついて2^(d-1)を提出し、WA。さすがに顔面真っ青になってよくよく見ると、内側に行くにしたがって辺の長さが(a,b)から(a-1,b)または(a,b-1)になることがわかる。これはcomb(2d,d)で、いちばん外側の回転を考えるとcomb(2d,d)/2。ようやくAC。

B問題に進む。Lの鏡映の形に並べるとよさそうに見えるが、実際に計算するとどこまで大きくしても2倍弱にしかできない。それでは、とこれをくっつけて繋げても同じ。そこで、Dからは全部見えるようにちょっと離して3つ並べることを考えると、どうやら再帰的な形になりそう。比も2倍を超えた。さらにもう一段階大きくして計算した結果、見える個数の比が指数的に増えることが分かったので、実際にフラクタルな図形をプログラムで生成してチェッカーに投げた。良さそうなので提出し、手元の出力を再度確認していたらすぐACが帰ってきた。

そのあとCに2時間、Dに1時間半をかけたが、どちらも解けなかった。Cは最初、2x3の長方形だけじゃなくて3x2の長方形も使えるとなぜか考えてしまっていた。これだと全部の黒マスを左上に集めて全探索できるので、誤読に気づいた後も端に集めることをずっと考えていた。解説にある不変量らしきものも発見していたが、僕はこれを具体的に操作した結果として得ていたため、それを不変量だと認識したうえでの考察ができなかった。ある黒点(x,y)は(0,y mod 3)、(0,y)、(x,y mod 3)に変換できるが、こういう操作で考えると（操作前も操作後も）x==0を特別扱いする必要がある。Dはマジで何もわからない。適当に変数を2つおいて立式したら二項係数3つの積の和が出てきて、WolframAlphaに投げたり計算量が少ないとうれしいなと思ってサンプルを試したりするにとどまった。

僕と同学年の競プロ事情に関する話題が出てきたので、夏季セミナーの写真や情報オリンピックの名簿を見たりして懐かしい気持ちになる。夏季セミナーにおける僕のふるまいは思い返してみれば黒歴史にふさわしいものであったので、深く考えないことにする。

今日もラノベを1冊読んだ。「痴漢されそうになっているS級美少女を助けたら隣の席の幼馴染だった」3巻。読みづらいと感じながら読んでいたが、この読みづらさはセリフをしゃべっているキャラが即座に判断できないことに起因しているように思う。原因の多くは自分の読書姿勢に帰属していて、「場面におけるキャラの（物理的な）立ち位置を想像せずに読んでいる」「そもそもキャラと口調をまともに覚えていない」がある。

月曜日はこどふぉに出たらすぐ寝て、火曜日の帰省に備えたい。それまでに動画も完成させたい（実家には編集環境はない）ので、明日の夕方が勝負どころか。

週記（2020/12/14-2020/12/20）

12/14(月)

前日の午前10時に就寝、午後6時に起床。土曜日に届いたはずの生協の弁当5食を2日で消費してしまい、食べるものがない。いや、パスタのストックはあるんだけど、茹でたりする操作が面倒で仕方がない。冷蔵庫にりんごがあったので食べた。貰い物だ。

サークルの解説会の準備をする。今日はARC110の予定で、A問題とD問題は解説役に立候補してくれた人がいるので、B問題とC問題を準備する。C問題を用意している途中で解説会の時間になってしまったため、先にD問題をやってもらうことにしてその間に作りあげようとする。

D問題は組み合わせを使用する場合の数の問題だ。僕は解説の方法（言い換え）で解いたので、マス目の経路の数え上げに帰着する方法は解説会で初めて聞いた。こっちもかなり天才的だと思う。形式的冪級数はいまだに手を出すタイミングをつかみ損ねているテクニック。

布団に倒れこんでいたらJOI二次予選の問題が公開された。コードゴルフをしようと思って見に行ったが、難易度的にそんな縮めるような問題ではなかったので、ゆっくり解くだけにした。TLでいくつか言及を目にしているので、全部1から考察というわけではない。

A問題はいうことなし。B問題はゴールから幅優先探索だ。古代ICPCみたいな問題だな。C問題は祭りをスキップする理由がないことに気づけば簡単。D問題みたいな問題は大体担当する場所が区間になるので、今回もそうだろうと信じると通る。

E問題はTLで盛んに言及されていた問題。3-SATの形に直してもいいことは何もないので、意味をもとにして考えることにする。自由度的に考えればスパイじゃない人ができるだけ多いと嬉しくて、ではスパイでなければならないのは？というのをいろいろ試してみると、結局AもBもスパイのときにCもスパイになるのが唯一の場合であるとわかる。新たにスパイになった人を検出するとその周りだけ調べる、という風に更新すれば十分高速。

3-SATの形にすると各クローズは￢A∨￢B∨Cの形で書けるが、このように全てのクローズで否定されていない変数が1個以下であるようなSATをHorn-SATというらしく、線形時間で解けるらしい。解説スライドによれば、E問題を解くのに使ったアルゴリズムと似たようなことをするそうだ。

https://onlinejudge.u-aizu.ac.jp/solutions/problem/0314/review/5059171/kotatsugame/C++14

無向グラフの全域木の個数を数え上げる問題に落ちる。これをググると行列木定理というものに行き当たったので実装したら通った。かなりびっくり定理だと感じる。こんなのPCKに出したって検索なしなんだから解けないだろ……。

mizuwater0.hatenablog.com

証明を探したらあった。自分でも追えるレベルで書かれていてうれしい。証明方法を忘れたとしても、主張だけでもちゃんと覚えておく必要がある。

AtCoderの解説作成ボタンが復活したらしい。

ラノベを読む。「羽月莉音の帝国」1巻。信じられないくらい面白かった。設定が僕の好みにピッタリ合致していてたまらない。序盤急成長しすぎじゃないか？と思うこともあったが、最初にちまちまやっているのはいくら現実的だとはいえラノベとしては面白くないのだろう。

雪が降るなかゴミ出しをした。思いっきりパジャマで外出したのに人目に触れてしまって失敗。もっと朝早くに行く必要があった。

昼前までかけて「羽月莉音の帝国」を一気に4巻まで読んだ。奥付を見ると刊行ペースが異常に速くてすごい。3か月に1冊以上のペースである。面白いのでまだまだ読んでいたいが、火曜夜はサークルでこどふぉバチャがあるのでそろそろ寝ておかなければならない。

正午、就寝。

12/15(火)

午後8時、起床。食事してすぐサークルバチャに参加する。今日は#549。本当は#545の予定だったが、これはコンテスト時間が2時間半で、午後11時半から予定されているリアルタイムのコンテストと間がないため2時間のものに変えてもらった。#545は明日に回される。

Bはダブリング。先頭の値さえ決めてしまえば、順列pを対応させるためにどれくらいシフトすればよいかわかるので、できる。あとはそこから2個ぶん、4個ぶん、……と先に進めていけばよい。

Cはずっと考え込んで、実は放物線が条件を満たすかチェックする場所は少ないのではないかと思って実装した。頂点から左右に離れるにしたがってy座標が2乗のオーダーで増えるので、左右に1000も調べれば事足りそう。分数で持とうとしたらオーバーフローしかねなかったので、そこも含めていろいろ注意して書くと通った。

想定解を読んでみた。放物線の方程式y=x^2+bx+cを式変形してbx+c=y-x^2に直してみると、座標(x,y-x^2)における直線を表していることになって、そのように変換した頂点集合の凸包の上に乗る直線をカウントすればいいらしい。天才的。

こどふぉdiv.3に出る。ふと思い立ってコンテスト中の画面を録画してみた。Bandicamの試用版を使っていたのだが、制限がかかっていて10分ごとに切れたのでちょっとびっくりしてしまった。E2で誤読した結果初手が違うのを修正するのに非常に時間がかかってしまった。

録画したものはゆっくり実況に仕立てて投稿することに決めた。なぜならやってみたいからだ。早速ゆっくりムービーメーカー3を落としてくる。

なぜかmp4を読み込んでも動画が映らなかった。いろいろ試行錯誤した結果、wmvファイルに変換してみたところうまくいった。とりあえずexoファイルに出力してAviUtlに持っていけるかどうかまで確認することにしたら、今度はAviUtlで動画が読み込めない。wmvが悪いのかと思ってaviファイルに再度変換してみても動かない。

結局AviUtlに入力プラグインを入れたら一瞬で解決してしまった。AviUtlってくらいだからデフォルトでaviファイルはなんでも読み込めるものと思っていたが、いろいろあるらしい。このあたりの話は全然知らないので必死でググっていた。

何とか動画の書き出しまでできたようなので、本格的に実況動画を編集していく。ゆっくりムービーメーカーの倍速はあんまり安定しないみたいで、そのあたりを確認しながらセリフを合わせるのはあきらめることにした。7時間くらいぶっ通しで編集し続けて、午後10時前にひとまずの完成を見たため、AviUtlで動画を書き出してみた。

死ぬほどずれていた。まずスタートから違うし、後半はほとんど静止画像になってしまっていた。原因がわからず途方に暮れていたのだが、AviUtlのほうで動画の詳細を確認すると、再生開始のフレームなどの値がおかしなことになっていることが分かった。ゆっくりムービーメーカーで編集するのはあまりよくないらしいので、泣く泣くAviUtlのほうで全部手作業で修正することにする。

セリフはすでに時間まで指定して置かれているため、そこに動画を合わせようとしたところ、どうにも合わない。ゆっくりムービーメーカーのほうで再生したものと突き合わせて比べてみてもよくわからないが、どうやらゆっくりムービーメーカーのほうでは全体的に時間の進みが速かったようで、その微妙に速い再生速度に合わせてセリフが置かれていてどうしようもない。泣く泣く1.3~1.5倍速くらいにして尺を合わせるが、どうしても想定していたセリフとズレてしまうシーンが出てきてしまった。そんなのを全部修正するのはさすがに絶望的なので、初めてだし……と自分を納得させて諦める。

そんなこんなで全体の修正が完了したのが11時。動画の書き出しに30分くらいかかるので、その間に学食に行っておく。帰ってきて書き出された動画を最後にチェックし、まあゆっくり実況の体裁をなしていたので投稿した。

見返すたびに粗が見つかる。自分が重要だと思ったものをいくつか書き残しておこう。

  • 話題が切り替わるときはセリフの間をしっかり開ける
  • 無理してセリフの末尾に読点を入れなくてもよい
  • コンソールの文字がつぶれて見えない
  • 考察を全カットするのはまだしも、実装をほとんどカットするのはよくない
  • ゆっくりがしゃべっている間でもコーディングは倍速しておくのがよさそう

録画環境も含めてまた何とかしておきたい。動画はまだ出したいという気持ちがある。午後3時、就寝。

12/16(水)

午後8時半、起床。昨日学食に行ったときに買っておいたパン等を食べて、こどふぉバチャに備える。今日は#545。

Aは座圧。適当に実装したら1000ms以上かかっていてビビる。BはZ-algorithmでどれだけ重ねられるかを調べるが、この時の判定で頭のおかしなことを書いていたため1WA。

CはSCCして気合い。本当は全頂点で週のそれぞれの日スタートの最大値を求めたいが、さすがに間に合わない。そこで、強連結成分ごとに1つ代表する頂点を決めて、それだけ計算しておく。他の頂点については、代表する頂点との距離をいくつも（ループを周回すると変わるので）求めておいて、それで日数を補正して計算すればよい。

解説を見たら頂点と曜日を組にしてSCCしていてびっくりした。確かにそうであることだなあ。サークルバチャの反省会でSCCって言われたのはこのことかと納得。僕は自分の解法が絶対的に正しいと考えて喋っていたので、公式解説の解法を念頭に置いていた人とは話が食い違っていたのかもしれない。

D問題は制約が1000で動かせる駒が10個あるから2^10を何か利用するのだろうなと思っていたが解けなかった。適当に実装したがずっと2番目のテストケースが突破できなかった。あきらめて解説を読んだところ、駒は3つでもよかったらしい。天才的すぎた。泣きながらupsolveしようとしたら80番目のテストケースでWAしてさらに涙が止まらなくなった。

昨日言っていた録画環境について少し考える。いろいろキャプチャソフトを調べていたところ、NVIDIA GeForce GTXシリーズのグラフィックボードを使っていれば使用できる公式のキャプチャソフト「ShadowPlay」があるらしいので、それを利用することにした。完全無料である。素晴らしいではないか。

GeForce Experience - NVIDIA GeForce グラフィックス カードの強力な支援ツール | NVIDIA

マイクラをすると思って買ったグラボだったが、今まで塩漬けになっていた。こういう形で役に立てることができてうれしい。

同時にゆっくりムービーメーカーもバージョン4に切り替える。ShadowPlayで録画したmp4を試してみたところちゃんと読み込めたのでうれしい。AviUtlとの連携も上々。

朝になって外を見たら結構雪が積もっていて楽しい気分になる。家から出る用事がないのでなんの心配もない。雪が降っているのを見るのは好きである。ただどうにも粒が小さい。とても大きな雪が灰色の空からゆっくりゆっくり落ちてくるのを口を開けて眺めるのが究極かつ至高な雪の眺め方であると信じてやまない。

昨日のこどふぉを確認してみたところ、E1が落ちてしまっていた。それに伴い順位もとんでもないことになっていた。せっかく動画を作ったのに、その回で落ちるのは非常につらいものがある。順位も「そこそこ良い」みたいな言及をしたくせにそこから転がり落ちたので決まりが悪い。

先週のABC185は、B問題とF問題がclimpetさんに取られたままになっていた。頑張って粗探しをする。B問題については言語をAWKに切り替えることで縮んだ。数値を1つずつ、符号を切り替えながら処理しようとすると長くなるが、2つ組にして処理すると短かった。F問題はPerlのまま更新できた。もともとサブルーチンでループしていたところを、再帰呼び出しに変更した。かなり遅くなると思っていたが、ギリギリTLEしなかった。

午前12時半、就寝。

12/17(木)

午後8時半、起床。起き抜けにヒカキンに24時間密着する動画を視聴した。動画最後のじゃんけんに負けて辛く悲しい気持ちになった。

食事をして、PCKの問題を1問解く。昨日のキャプチャソフトのテストもかねて録画しておいた。ゆっくりムービーメーカー4の設定をする。こちらでゆっくりを動かすのは、ほとんどプリセットされていたバージョン3に比べて少し難しい。

えでゅふぉ100に出る。100回目！5完だった。D問題で深く考えずに特攻したら思ったより難しくて時間を使ったように感じていたが、実際D問題を解いた直後に順位表を見ても1ページ目にいたので、みんな爆発していたのかもしれない。そのままE問題もそれなりの速度で解いて、システス前の順位は11位くらいだった。今回もスクリーンキャプチャを録画した。

えでゅふぉは後回しにして、まずPCKの問題を解いた録画をゆっくり実況にする。今回はテストの意味合いが強いと思っているので、長さもなるべく抑える。

ゆっくり魔理沙の語尾は「～だぜ」を代表とする男口調が一般的だと考えているが、ゆっくり霊夢の語尾は悩む余地がある。1本目の動画を作成した時には、できるだけ「～だよ」「～だね」を使用して中性に寄せていた。これは、ゆっくり霊夢と動画投稿者（自分）を同一の存在とする認識が根底にあったからだ。しかしこれはちょっと難しいと感じていた。ところどころ、不自然な（書いていて真っ先に思い浮かぶものではない）語尾を使用することになっていた。そこで今回は、自分とゆっくり霊夢を別個の存在であるとして、ゆっくり霊夢には女口調でしゃべってもらうことにした。それほどあからさまではないが、「～わよ」「～ね」などの語尾が現れるようになった。そういう決定を下したのは編集の終盤だったから、最初のほうは普通に「～だよ」が連打されているが、そこまで直す気力はなかった。台詞を結構詰めているので、発音にかかる時間が変わると全体が少しずつずれてしまう。

設定として、実際にゆっくり霊夢がコーディングしているところにゆっくり魔理沙が口出しするようなものを考えているので、視点は相変わらず自分と同一である。

今回の画質はフルHD、1920×1080だ。動画時間は1本目の半分なのに、ファイルサイズは2倍になっていた。縦横2倍なので当然のこと。きれいな比例関係だ。

今回も効果音は一切ないが、ゆっくりの表情をいくらか変更した箇所がある。ゆっくり霊夢は目を閉じ、ゆっくり魔理沙はジト目をするようになった。ほかの表情はたくさんありすぎて使えなかった。

4時間くらいで編集が終了し、午前7時すぎにアップロードが終了した。

前回自分で指摘したポイントはすべて考慮したが、今回もさらに自分で直したいポイントを見つけたので、列挙しておこう。

  • 喋ることを決めてから動画の尺を合わせるように倍速編集をする
  • 解説をするつもりならちゃんとする
  • 特に二分探索で区間の両端は何を表すか、セグメント木に何を乗せるかには言及したかった

最初にコーディング風景を4倍速にすることに決めて、画面に合わせるようにゆっくりのしゃべる内容を決めてしまったが、これはあまりよくなかったのだろう。

正午くらいに就寝。

12/18(金)

午後8時くらいに起床。昨日上げた動画にミスの指摘があった。ローリングハッシュにおける素数と基数の関係を「互いに素であればよい」としていたが、これは誤り。

じゃあ1と素数-1はダメだよ、と書いておくか……と修正したが、これも正確には違うようだ。乗法群における位数が大きければ大きいほど良い基数となるらしい。どういう風に書けばよいかわからなくなったので、間違っていることだけ書いておくことにした。

ラノベを読む。「羽月莉音の帝国」は、昨日と一昨日で5、6巻を読んでいた。7巻と8巻を読む。信じられない勢いでスケールアップしていて非常に爽快。1巻のはじめでは借金300万がどうのという話をしていたが、桁が8つ違う。信じられないくらいのサクセスストーリーで非常に面白い。10巻の完結までもう秒読み、いよいよ展開は最終局面を迎えたように感じられる。この後どのように話が閉じられるのか、すごく気になる。さっさと読んでしまおう。

朝方、TechFULコーディングバトルの32回に出た。この週記が公開されるのはイベント終了前なので、詳しいことは書けない。ただ、今回はシンプルに僕の実力不足で不本意な点数を取ってしまった。

えでゅふぉ100の録画も、全完はしていないが編集して投稿したいと思っている。しかし土曜日にはABCもあり、こちらも録画しておきたい。動画編集はかなり時間を食うことが分かったので、こういう風に溜めたりしてモチベーションを少しでも失えば、途端に投稿しなくなってしまうだろう。帰省で編集できる環境から離れても同じことが起こると思われる。

昼になって布団に入り、ハーメルンの更新を確認していたところ、「このすば*Elona」の更新が来ていた。およそ4か月ぶりか？うれしい。1話ごとの長さが長めなのもうれしいところ。

この日は寝落ちした。ブラウザの閲覧履歴を見るに、11時半ごろだったらしい。

12/19(土)

午後3時くらいに目覚ましで目を覚まし、そのあと30分ごとに寝たりうつらうつらしたりして弁当の配達を待つ。午後4時半ごろに配達されたのに何とか対応することができた。今日は午後6時半ごろからこどふぉがあるが、それまで微妙に時間が空いている。かなり眠いけどそのまま起きているかもう一度眠るかかなり迷った。迷っていると目が冴えてなかなか寝られない。

普段ならあきらめて起きてしまうところだが、今回はこどふぉよりもそのあとにあるABC186を見据えて、こどふぉを寝過ごすことも視野に入れてちゃんともうひと眠りすることにした。1時間半後の午後6時、問題なく起床できた。これは目覚ましによるものである。

こどふぉはABの2完で終わり。Bは1004が通ることをなぜか信じられなくてずっともっと速い解放を考えていたため、かなり遅くなってしまった。そのうえC問題が解けず最悪。BとCの間に結構な崖ができていた。2707→2642(-65)。

こどふぉは午後9時まで言及が禁止になっていたので、こどふぉとABCの間の30分は無になった。ABC186である。これは録画してまたゆっくり実況にするつもりだ。

AからDまではかなり速かったと自負しているが、EとFはそこそこ時間をかけた上にペナルティまでつけたので、終わってみると順位はそれほど良くない。ただA問題のFAが取れたので、動画映えはするだろう。全完後のコードゴルフの模様も録画しておいた。

D問題は過去に出題された問題とほとんど一緒である。コンテスト中に45Byteの解を作って提出した後、過去の問題のShortestを参考にしようと思って最短コードを見てみたところ、46Byteだった。深く考えず同じコードをこちらにも提出してしまったが、そのあとこれはまずいのではないかと認識する。とりあえずatgolferのbotを確認したところまだ拾われていなかったので、急いでサーバーをシャットダウンした。

自分ではそんなに悪いことをしたという感覚がない。このことについてツイートして、自分でもいくらか考えてみた。そもそも過去の既出問題であってもコンテスト中に書いたのと全く同じコードを提出するのがダメで、コードゴルフに関連する形で問題が表出したから感情的に反発しているのだろう。

日付が変わったあたりから、今日のABCの動画編集を初めて、午前7時くらいに完成した。動画を出力してYouTubeにアップロードしたところ、ファイルサイズが大きすぎるとはじかれた。不思議に思って動画ファイルのプロパティを確認したところ、150GBもあった。15分の動画なのにこれはおかしい。YouTubeのトラブルシューティングで「ファイルサイズの制限に引っかかる」みたいな項目を見ると、エンコードをしろと書いてある。

僕は動画ファイルを出力するのがエンコードだと思っていたけど、実際はデフォルトで無圧縮の出力がされていたらしい。ちょっと調べてエンコーダを導入し、出力してみたところ、なんと66MBになった。本当にびっくりした。これまで投稿した2本の動画はどちらもファイルサイズが数十GBだったが、これは無圧縮だったからのようだ。問題なく投稿できるどころか、以前はアップロードの待ち時間が30分くらいあったのに今度は一瞬である。

今回は効果音がついているし、霊夢と魔理沙の表情も幾分豊かになった。テキストを用いて見えにくいコードを表示したり、考察をtexで清書して表示したりといろいろやってみている。解説もそこそこ丁寧にやったつもりだ（特にF問題）。今回の教訓は以下。

  • 字幕を幅いっぱい書くと動画にしたときに見切れる
  • 相変わらず倍速してから尺に合わせてしゃべっている

C問題以降のコードゴルフはダイジェスト式に編集したが、これはよかったのではないかと思う。

A問題からD問題までは3分もかかっていないので、ここは等倍でそのまま流した。等倍なら時間の感覚がある。しかしE問題とF問題で倍速を使用し、こちらは時間の感覚が破壊されてしまうため、なんとなく臨場感がなくなってしまう。かといってカットを多用するのは競プロの試行錯誤の過程を全部ないがしろにしてしまう感じがしてどうだろう……。悩ましいところだ。割り切って編集スタイルをどちらかに寄せるのがよさそう。ただ自分で見てるとバグったコードを必死に書いている時間は滑稽なんだよな。

今回、ゆっくり霊夢の口調は完全に「～わ」「～ね」に振り切っている。「～わ」が連続してしまう箇所がいくつかあって、そこでは「～よ」を適度に挟んでいる。

「羽月莉音の帝国」の9巻を読んだ。いよいよクライマックス。というか予定されていることを考えるとあと1巻でシリーズが完結するのが信じられない。どのような過程がどのように描かれてどこに着地するのだろう。いろんな想定がありえて、10巻を読むのが怖くもあり楽しみでもある。10巻の扉近くのページだけ読んでいたが、これまで各巻の主要人物が紹介されていたページに革命部5人だけしか描かれなくなっていて非常に不穏。

寝る前まで定期的に投稿した動画の再生回数を見ていたが、すでに200回再生に届こうとしている。やっぱりABCってだけで耳目を集めるのだろうか。こどふぉとかやってる場合じゃないな。他にはA問題のFAをプッシュしたのもよかったのかもしれない。

正午近く、就寝。

12/20(日)

午後9時起床。昨日投稿した動画がかなり伸びている。1000回再生を突破していてびっくり。やはりAのFAが注目されているようだ。動画のURLツイートの引用リツイートを見たり、リツイート先を見に行って言及を確かめたりしていた。

動画の冒頭に置かれているから、数秒で当該シーンを視聴することができる。さらに2、3分見るだけでD問題までの速解きを把握できる。見るだけで何が特徴的なのかわかる物事は動画映えする。ただ「速い」だけ。

ただ、これを認めてしまうと、競プロ実況動画がなかなか作成できなくなってしまう。そういう目に見えて特徴的なことが起こるコンテストなんてそうそうないだろうし、「解説しながら解く」タイプの動画に落ち着いてしまうのだろうが、それは文章でよい。そもそも図を作成するのを面倒がっているため、解説動画の作成は致命的に向いていない。まあ自分は腐っても日本で上位50人に入るプレイヤーであるから、そういう人間がどのようにコンテストに参加しているのかを実況することに何らかの需要があると信じて続けていきたい。

ラノベを読みつつ、日付が変わった直後のこどふぉを待って、参加した。pretest時点ではABCDが通っていたが、C問題はシステスで落ちてしまった。3完で2642→2643(+1)。

Aはルークの動きをイメージするのが難しいので純粋に数字の入れ替えの問題として捉えるべき。Bは直感的に11...00か00...11の形しかないことがわかるが、念のため示した。

Cは実験するとかなり何でもできることがわかる。僕は下から偶奇でつじつま合わせをしていったが、これは誤りで、上のほうの桁を変えると全部反転してしまう。正解は上から貪欲らしい。各桁で使える個数がたくさんあるのに、なんで貪欲ができるのかよくわかっていない。

Dは無限場合分け。1つだけ2種類両方試さないといけないことに気づいて、それに対応するためにコードを思いっきり書き換えたのがよかった。試すための関数を別に用意して、それを何回も呼び出す。これまでifとelseを連ねていろいろ分類していたが、条件を満たす場合を全部計算してしまうことにするとより安心できる。

Eは全然わからなかったが、Grundy数は最大でO(sqrt M)くらいになるらしい。これ何回も見たことあるな。あとは確率の遷移行列を書いて何かするんだろうけど、実はそこから先はTLで解法ツイートを見なかったのでわかっていない。

「羽月莉音の帝国」の10巻を読んだ。非常に良かった。終わり方もかなり良い。ネタバレは絶対にしたくないので、何も書かない。著者の至道流星さんはほかにも経済ラノベをいろいろ書いているようなので、買いあさりたい。

シリーズの途中で主人公の羽月巳継が「ネットはそれほど強い力を持たない」といったことを言う。そのあたりは微妙に不穏な空気が漂うシーンだったので、ネットが何かの障害となる伏線かと思ったのだが、特にそのようなことはなかった。結局、この発言はラノベが書かれた2011年ごろの認識によるもので、今（つまりネットが実社会に強く影響を及ぼすようになった時点）から見ると違和感があるというだけだった。

月曜提出のレポートが2つある。朝までのCGレポートと、夜までの幾何学序論。とりあえずCGを片付ける。

幾何学序論は前回のレポートを書いてからの講義内容をまずチェックしなければならない。チェックした後レポート問題を読んだが、なぜか急にやる気を失ってしまいハーメルンを開いてしまった。Game of Vampireを読み返していた。やっぱりこれ好きだなあ。

冷静になると、夜のサークル解説会はまだ1問も解説役が決まっていないのでスライドを用意しておく必要がありそうだし、レポートも1文字も書いていなくてかなりまずい状態。とりあえず寝ようと思って、寝る前に日記を書いていたら午後3時半になってしまった。シンプルにヤバい。