2022-07-04

週記（2022/06/27-2022/07/03）

06/27(月)

午前11時半起床。日付が変わるまでに先週の週記を書き上げて投稿したいので、微妙な眠気を抱えつつも起きてしまうことにした。

まず今日が提出期限になっている課題を済ませる。ゲーム理論。今週の課題も簡単で、定義に従って計算するだけ。ただ戦略形ゲームの表を埋めようとしたらこの計算をあと15回繰り返さなければならないので、ちょうどよい難易度の問題がなかったのかなと思ったりした。一応教科書も毎回目を通しているので、それで少し時間はかかっている。

課題を終えてちょうど昼過ぎになったので学食に行こうとしたら、天気が不安定らしかった。確かに外は曇っている。急に雨が降り出したら嫌なので外出を取りやめ、パスタを茹でて昼食とし、先週の週記を書き進め始めた。

午後2時過ぎに冷凍弁当が配達されたので受け取った。午後3時以降と指定したのだが、時間を勘違いされていたらしい。たまたま起きていてよかった。

生協の冷凍弁当の配達を月曜日に振り替えてもらえるようメールを出した。
週記（2022/06/20-2022/06/26） - kotatsugameの日記

午後4時になって一旦切り上げ、少し準備してインターン先定例会に臨む。先週の進捗もほとんどない。ないものを無理に膨らませようとした結果進捗報告の場でスライドに書いていない細部について触れようとしてしまい、喋る内容をまとめるのに失敗して尻切れとんぼの発表になってしまった。迂闊。ないならないで諦めること、ちゃんと喋る内容を考えておくことが重要。

今日の勉強会は数学の話で、特に測度論とルベーグ積分。さすがに1回じゃ無理だろうと思っていたが、発表は定義と定理の紹介だけで爆速で駆け抜けていった。論理の流れを概観するという意味では得るもののある発表だったと言えなくもない。ただ、スピードが速すぎる。講義で触れたことのある部分までは何とかなったものの、終盤は知らない物事が登場して、内容を把握するのすら間に合わなかった。これまでの僕の発表でもついていけなかったという感想が寄せられたことはあるので、今回僕自身が発表に置いて行かれたという経験を活かして今度から発表スライドを作ろうと考えた。

その後はずっと日記を書いていた。日付が変わる直前になって、何とか日曜日の就寝時点までたどり着いた。本来ならここから文章全体を読み直して表現を修正したり書き足す作業があるが、とにかく日付が変わる前にといったん投稿してしまうことにした。

間に合った解放感からしばらくYouTubeに意識を奪われるも、1時間程度で戻ってきて、そこから午前3時半までかけて全体を読み返し校閲を行った。せっかくなので保存しておいた初稿とdiffを取ってみた。以下のツイートに添付された画像において、左が初稿である。細々とした違いのほとんどが表現を少し改めた場所で、誤字はほとんどなかったはず。大きく異なっているのは文章を書き足したところで、特に日曜日の部分は急いで書いたため、改めて読んでいるうちに書き足したいことがたくさん出てきた。

diff pic.twitter.com/D8ewrcn1Ax
— こたつがめ (@kotatsugame_t) 2022年6月27日

ゴミを出して布団に入り、YouTubeを見ていた。レオス・ヴィンセントさんの初配信面白すぎる。ちょっとしくじったからといって自己紹介もしないうちに配信を終わろうとするのはあまりにも豪胆。「全部ダメなのに堂々たる態度だけは貫いてるのが余計面白い」というコメントを見て、ずっと大きな声ではきはき喋っていたのに気付いた。聞き取りやすくて非常に良い。

www.youtube.com

日曜日のARC143-Cの、選ぶ山がちょうど一つの場合の解法について。先週の週記では勘違いで解けたと言っていたが、別に勘違いではなかった。まず各山の石の個数について $A\leftarrow A\bmod{X+Y}$ としておく。すると $A\lt X+Y$ であるから、片方のプレイヤーが1度でも操作した山について、もう片方のプレイヤーはその山に対し操作できない。つまり、 $(a,b)=(\lfloor A/X\rfloor,\lfloor A/Y\rfloor)$ というペアがあって、高橋君がこのペアを選ぶとパス回数の猶予に $a-1$ が足され、青木君が選ぶと $b-1$ が足され、選ばれたペアは消えるとしたとき、どちらが先にパスを含め操作できなくなりますかという問題になる。 $a=0$ または $b=0$ の場合は先にもう片方のパス回数に足しておいて、あとは $a+b$ の降順に貪欲に取るのが両者にとって最適。

ハーメルンの更新を漁っていたら午前6時過ぎに寝落ちした。

06/28(火)

午後5時半起床。DMOJのコンテストが終了していた。参加直後に書いておいたコンテストの感想を貼っておく。

DMOPC '21 June Contest - DMOJ: Modern Online Judge

順位に影響しないがペナルティも記録しておく。

P1は先頭から貪欲。

P2は、swapによって $1$ を動かさない場合最初に $1$ が先頭に来るようにrotateしておけばあとは貪欲。これによって先頭が $1,2,\dots$ となる列が必ず作れるので、 $1$ を動かす場合は $2$ の直前に置かなければならないとわかる。そのためには $2$ の直前の要素と交換するか、または $1$ と $2$ を交換して達成するケースもある。それぞれ $2$ を動かさない場合と動かす場合に対応するので、これできちんと尽くされている。この場合分けを忘れて1WA。

P3は面倒。光がどの辺をどの向きに通ったかを状態とする01BFSで解ける、とエスパーする。光の道筋が交差したらどうなるのかはよくわからないが、そうじゃなきゃ解けないだろうと信じた。あとは気合いで実装。遷移をコピペしまくっていたら添え字の $\pm 1$ を忘れたり全部push_backにしてしまったりといろいろミスを重ね、そのせいでMLEになっているのにデータをpair<int,pair<int,int> >で持っているのが悪いんじゃないかとintに圧縮したうえでその圧縮もミスしたりで大変だった。4ペナ。

P4は最後のXORより後ろしか考えなくてよいとわかる。それより前を変更して達成できる値は、最後にXORを変更することでも達成できるから。よって後はANDとORだけの場合を考えればよい。後ろから見て「立っていなければならないbit」と「立っていてはならないbit」を管理すると、操作を一つ巻き戻したときの変化は、値の変更によって $0$ にするか特定の値がbitwise ANDされるかで記述できる。つまり各時点ですでに $0$ になっているかなっていないかの2通り、組にしても高々4通りの状態しかあり得ない。あとは愚直に書く。あまりにも愚直に書きすぎて10⁶個のmapを作ってしまいMLEしたので、mapを使いまわしてAC。

P5は解けず。まず $n$ を相異なる素数の積だとした。 $2^e+1$ という形の素数をたくさん集めると、どうしても $d(\varphi(n))\gt \varphi(d(n))$ になるようだ。よってさらに一般化し、それぞれの素数が $2^{e_2}\times 3^{e_3}\times\dots\times 13^{e_{13}}+1$ くらいの形をしているとして、条件を満たすものがないか全探索していた。結局コンテスト中には見つからなかったのだが、今見たら全探索のコードが間違っていて、修正すると $1244586078645=3\cdot 5\cdot 7\cdot 13\cdot 19\cdot 37\cdot 73\cdot 109\cdot 163$ が見つかった。これは80点相当である。残念。P6は見てもいない。

400点で現在1位。まあコンテストは始まったばかりなので、以降どれだけ下がるかという話になる。

……ここまでがコンテスト直後に書いたこと。最終順位は11位まで下がり、レートは2320→2625(+305)。当然highestである。

布団に横たわったままカクヨムを読んでいた。このまま二度寝しようかなあと考えていた矢先、TLにatgolferのツイートが流れてきた。見ると「第10回アルゴリズム実技検定」などと書いてある。いつの間にか過去問が公開されていたらしい。すぐさま起き上がって解き始めた。

第10回アルゴリズム実技検定過去問 - AtCoder

ABDFはよい。Cは題意を掴むのに苦労したが、桁数を見て上位数桁を取り出すだけで数学チックなことは何もしない。Eは実装を頑張る。Gは二分探索。Hはマージテク。Iは $x$ 軸で折り返すとき、 $y$ 座標が同じ点を集め、 $S$ における $x$ 座標の小さいものと $T$ における大きいものを順に組にしていくと、集合として一致するならどのような対応になるかが得られる。あとは本当にそれを実現する直線が存在するかのチェックで、組にした2点の $x$ 座標の和が全部一致しているか見ればよい。

Jは $A_i$ が $X$ になる確率と $Y$ になる確率をそれぞれ計算。ソートして上下に何個要素があるか考えればよい。タイブレークは適当でよい……と思っていたら、日記を書くとき制約に $A_i$ がdistinctとあることに気づいた。Kはさすがにド典型。Lは $\frac{10^D-1}9$ を行列累乗で計算。MはBinaryTrieでぶん殴ろうとしたら配列サイズをミスしていて、REが出たのでありもしないライブラリのバグをずっと探していた。Nは冷静になると畳み込み。Oは順列の要素の $\bmod 3$ を考えると連結成分ごとに二部グラフを $1$ と $2$ で塗り分けたか全部 $0$ になっているかだとわかる。 $1$ と $2$ でどれだけ塗るかをdpで計算。

特に詰まる問題もなく、簡単だったという印象。Mはライブラリで殴らない解法を考える前に解説を読んでしまったので、座圧BIT二分探索にどれくらいで気づけたかは永遠にわからないままとなったが、まあそれも典型に見える。序盤コードゴルフしていたのも含めて2時間程度だった。

今日が提出期限になっている離散数学の課題を瞬殺してから改めてコードゴルフをしていた。Eまで見終えて、午後11時半からのCF #803 div.2に出た。Writerが青で不穏。

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

Aはギャグで、数列のどの要素を出力してもよい。最近インドで似た問題を見たような気がしたが、あちらは1要素以外のXORの列が与えられていた。

https://www.codechef.com/LTIME109A/problems/LOSTARRAY_

Bもギャグ。 $k\ge 2$ のとき、どのように操作したとしてもtoo tallな要素は増えない。なぜなら、操作で $a_i$ がインクリメントされたときは同時に $a_{i-1}$ または $a_{i+1}$ もインクリメントされているから。よって入力の数列そのままの状態で数えて出力すればよい。あまりにギャグすぎて笑っていたら $k=1$ で1WAした。この場合は好き放題できるので答えは $\lceil(n-2)/2\rceil$ 個になる。

Cはちょっと面倒。数列をソート済みだとすると、 $a_1+a_2+a_3\ge a_1$ より $a_2+a_3\ge 0$ 、特に $a_3\ge 0$ が、同様に $a_{n-2}\le 0$ が言える。 $3\ge n-2$ の場合は面倒なので全探索することにして、そうでない場合 $0\le a_3\le a_{n-2}\le 0$ より $a_3=a_{n-2}=0$ となる。同時に $a_2$ も $a_{n-1}$ も $0$ とならなければならない。よって $a_1+a_n$ が $a$ に含まれるかだけチェックすればよい。Dは区間 $[l,r]$ を聞いて $l\le i\le r$ かつ $l\le a_i\le r$ なる $i$ の個数を数えると、これが奇数であることと $[l,r]$ に求めるインデックスがあることが同値になる。あとは $l=1$ と固定して $r$ で二分探索。

Eは最初、 $x$ と $y$ がインデックスだと思って解いてしまった。この時の解法は、 $i=1\dots n$ の順に $b_i\ne -1$ ならそれが $a_{[1\dots i+s]}$ に含まれるかチェック、そうでないなら $a_{[1\dots i+s]}$ で $b$ での行き先が決まっていないものの個数からこれまで見た $b_i=-1$ の個数を引いたものを掛ける。サンプルを試して答えが合わず、 $x$ と $y$ がインデックスではなく要素の値であることに気づいた。しかし機転を利かせ、 $a$ と $b$ を最初に逆順列にすることでコードを使いまわすことに成功した。

Fは難しい。操作で作れる辞書順最小の数列を正規形として、両方から高々 $n(n-1)/2$ 回の操作でそれに変形し、くっつけることで $n(n-1)$ 回以下の操作で一致させるという方針を考えたが、そんなことが可能なのか考えているうちにそれができるなら直接一致させられるよなあという気持ちになったので捨てた。次に、操作による顕著な不変量として数列の先頭と末尾、さらに値の隣接関係があるため、これらが一致していれば必ず可能と信じてそれを示そうとした。

数列 $b$ が先頭から $x,y,\dots$ となっているとしよう。数列 $a$ も $x,y,\dots$ なら $x$ を取り除いて次に進んでよい。そうでない場合、 $x$ と $y$ は数列 $a$ の後ろのほうで隣接していることになる。もし $\dots,y,x,\dots$ となっていれば、先頭の $x$ までの区間をreverseすることで $x,y,\dots$ とできる。 $\dots,x,y,\dots$ となっていた場合、必ずこの2要素を含むようなreverseができることが示せる。

隣接する値の順序なしのペアをシャッフルしていると考えるとわかりやすい。数列 $b$ の先頭のペア $\{x,y\}$ が数列 $a$ の途中に出現しているのだから、ほかのペアは $\{x,y\}$ の左右に振り分けられている。したがって数列 $b$ における $\{s,t\},\{t,u\}$ という並びのペア（ $\{s,t\}=\{x,y\}$ かもしれない）であって、数列 $a$ において $\dots,\{t,u\},\dots,\{x,y\},\dots,\{s,t\},\dots$ と左右に分かれたものが必ず存在するため、この $t$ を使ってreverseができる。

よって示せた。証明が解を構築するアルゴリズムになっているので、そのまま実装すればよい。

Gはわからず。貪欲に操作し続けて答えが見つかるまで待つコードを書いたが当然のようにTLEした。小さいケースで実験した感じ最大で $2^{|s|}$ ステップ必要そうだったので当たり前。システスは全部通って6完7位。なかなか難しい回だった。

PASTのコードゴルフを続け、朝方ひとまず全問見終わった。

AはRakuで結構念入りに縮め、満足していたらVim＋dcに負けた。入力を倍にして $[A,B,C,A,B,C]$ という列にすると、2個ずつ掛けるだけで3種類の値が得られるという方法。まったく気づかなかった。B、Cは自明なdc解が午後2時過ぎの過去問公開後すぐに提出されていた。僕が解き始めたのはそれから5時間後だったので、もう全然ダメ。DはOctave。EはRubyで日付計算するコードをVimから呼び出し。出力の成型もVimで行うとさらに縮んだ。

FもOctave。州と色を対応させる列の添え字に行列を使うことで各マスの色を表す行列を手に入れようとしたのだが、なぜかいくつかのケースで添え字とした行列のサイズが保たれず、比較の際にインデックスの対応が取れなくてREを出してしまった。結局これは解決できなかったため、色を表す行列をずらして比較するのではなく、州を表す行列をずらした後に色の番号に変換することにした。GはRubyの二分探索で、これもVimから呼び出すコードが僕が解く5時間前に提出されていた。HもRuby。リストのコピーがシャローコピーなので、各頂点から根のインデックスを経由することなく直接自身が含まれる頂点集合へアクセスできるようなコードが自然に書ける。具体的にはそのようなリストを各頂点で持っておけばよい。実際は参照なので頂点の追加も一斉に反映される。

IはRubyで実装したものの思いっきりTLEしたため放り投げた。JもRuby。公式解説より上で書いた僕の解法のほうが短くなりやすい。Lは $10^D-1$ を $\bmod{9M}$ で計算することで、直接 $9$ で割れるようにするテク。Rubyで実装した。dcではTLE。NはACLのconvolution。KMOは手付かず。

午前8時半ごろラノベを1冊読了。「スキルが見えた二度目の人生が超余裕、初恋の人と楽しく過ごしています」。タイトルから逆行モノだと分かったため喜び勇んで買ったが、面白く感じられなかった。前半は自分のステータスを伸ばすのに集中して、後半は出現したダンジョンで無双している。これでは逆行ではなく異世界転生に近いなと思った。多分、僕は逆行モノに未来知識を活用する描写を求めているのだろう。そういう観点を抜きにしても、やたら落ち着きなく見える主人公を筆頭に至るところの描写が好きではない。

日記を書いて、昼前に学食に行った。今日も納豆を2パックお盆に並べ、以下のように店員に申し出ることで1回で2個同時に会計してもらおうとした。ご飯特大が納豆2パックに値するかについては議論の余地があるが、明確な基準が示されていない以上ゴネ得である。

ご飯の量が多いなどの理由があればその場で申し出ることで対応してもらえもするらしい。
週記（2022/06/13-2022/06/19） - kotatsugameの日記

ところがそういう理由ではダメだと言われたため、電話で聞いた対応と違うと言ってその時通話した人を呼んでもらった。ここは少し危なかった。ちょっと電話しただけの人の名前など覚えているわけがないのだが、たまたまその人の名前が僕の一言カードに返事を書いた人と同じだったことは覚えていて、その一言カードについては写真を撮っていたため、その場でスマホから確認することで特定できた。やってきた担当者の方にレジの方から説明が行ったところ、やはり1会計1個のルールに違反するためダメだと言われた。

代わりに、レジを2周せずとも一旦お盆から出すなりすればその場で2回会計を行ってもらえることになった。今回以降ずっとこれで良いという確認は取っている。まあルールの文面だけ順守するならこれが完璧な正解なのだろう。その場では納得できずもうちょっとゴネようか考えたものの、今改めて思い返せば僕にとって何の不利益もない形の解決である。

納得できなかったのはたぶん、電話口で言われたような対応をしてもらえなかったと思ったから。しかし改めて考えてみると、申し出ることによる「対応」がその場での2回会計という意味だったのだろうと理解できた。それにしてもレジの担当者は2回会計すらしようとしなかったから、もともと存在しない対応だったと考えられる。電話口でそれを紹介しておいてレジ担当に伝えていないのは意味不明である。

帰宅してメールを確認すると、ABC257で日本人3位を取った時のアマギフ2万円が届いていた。受け取ってから布団に入りラノベを読んでいた。しばらくして切り上げ、寝る前に少しカクヨムを読もうとしたら即座に寝落ちしてしまった。午後1時半ごろだった。

06/29(水)

午後8時起床。なろうで1作読み始めた。この日は布団から出ず、午前2時寝落ち。

06/30(木)

午前6時起床。今日のセミナーの準備を何もしていなくてちょっとヤバい。まあ以前に準備した内容がずっと残り続けているので、再確認さえしておけば一応何とかなるだろうと考え、そのままなろうを読み進めていた。

午前8時半に読了。「やさぐれ執事Vtuberとネガティブポンコツ令嬢Vtuberの虚実混在な配信生活」。

https://ncode.syosetu.com/n0024go/

かなり面白かった。いわゆるロールプレイ勢、自分の設定を忠実に守るVtuberが主人公。普段の配信やライブ描写も面白いが、特に何度か行われた記念配信で展開されるVtuberとしての自分の設定を掘り下げる話は、準備段階の描写が制限されていたおかげで配信のシーンになるまで内容が一切わからずただただ期待感だけが高められ、読んでいる自分自身がリアルタイムで動画を見て他のファンたちと一緒にストーリーに巻き込まれていくような感じがして、のめり込むように読んでいた。

個人的には、設定を忠実に守るVtuberよりも、演者の感情がそれを突き破ってダイレクトにこちらに伝わるようなVtuberが好みである。人が感極まっている様子だったり、仲のいいコンビの感情を露わにしたやり取りを見るのが好き。そう考えると、この作品の主人公は自分の好みの対極に位置していることがわかる。演者の日常シーンで為人を把握し、Vtuberとしてのストーリーを文章でくまなく読めたことでようやく好きになれたのだと思う。前者がなければ無感情なVtuberには興味が持てないし、後者がなければわざわざ自分からストーリーを追おうとはしないはず。

上のような好みがあるのならなぜ生身の配信者の動画を見ないのか、という疑問が生じる。そもそも、ロールプレイ勢という言葉があるように設定をどれだけ守るかは人それぞれのため、ほぼ素のままのVtuberも多いはずで、そのようなVtuberと生身の配信者との間に我々視聴者がどのような違いを感じているかについては結構興味があった。この二つを絡めていざ自分なりに考えてみようとしたとき、そもそも生身の配信者についてほとんど何も知らないことに気づいた。だから先ほどの疑問に対する回答は「自分が先にVtuberに触れたから」というものになるのだろう。別にこれから生身の配信者を追うつもりもない。やりたいことが多すぎてすでにキャパシティーオーバーしている。

もう1作読み始め、午前10時くらいに読了。「妹から勧められて歌ってみたを投稿したら、大人気歌い手になってしまった件」。微妙に重い話があってびっくり。生配信のシーンはコメントの描写が少なめだったのであまり好みではなかった。楽曲名や作曲者名を思いっきり出しているのが特徴的。別に問題はないはずだが、ほかの作品では結構ぼかした書き方をされがちだと思う。

https://ncode.syosetu.com/n2206hg/

布団から起き上がって、セミナー準備のため教科書を読み始めた。今日発表しようと思っている部分の内容を改めて確認し、さらにまだ読んでいないところに手を付けて、午後2時半ごろようやく家を出た。

教室に到着してすぐセミナー。今日はあらかじめここまでと決めておいた部分のほとんどを発表しきることができた。午後5時過ぎに終了したため、もうちょっと粘れば最後の命題までたどり着けていたと思う。内容に関しては、ちゃんと準備してきたはずなのにメモ書きの意味が分からなくなって少し止まってしまったのがかなり残念。自分の中にグラフのイメージがあって、準備のときはそれに頼った考え方をしていたため、いざ黒板発表で紛れがないように説明しようとしたところでどう言えばいいかわからないことに気づき、焦りから準備当時の自分の思考すら再現できなくなってしまったということ。

やはり万全を期すなら発表練習をするのが最も良いのだろう。さすがにそこまで手間暇かけてはいられないため、今回であればちゃんと自分の中のイメージを表現する手段を考えておくこと、また黒板の前に立ってあっぷあっぷになった自分でも読めるようなメモにすること、以上の2点を心がけて発表準備をするべき。それができるかどうかはともかく。

学食で食事して午後6時過ぎに帰宅。

PythonのSciPyを使うコードのコードゴルフをしようとして、まず手元のCygwinにインストールしようとした。結論から先に書くと、日付が変わるまで格闘して結局ダメだった。ちょっと調べて出てくるような依存ライブラリは全部setup.exeから入れたはずなのに、OpenBLASがないと言われたり、プラットフォームがlong doubleをサポートしていないと言われたりして、調べても新しい情報が出てこなくなった段階で諦めた。Ubuntu機や、同じWindows上でもWSLにはすでに入っていたため別になくても致命傷にはならないということも大きい。

間にラノベを読み進めて1冊読了した。「許嫁が出来たと思ったら、その許嫁が学校で有名な『悪役令嬢』だったんだけど、どうすればいい？」。イラストでラノベを選ぶのはよくないと何度か主張しているのに、また懲りずにみわべさくらさんのイラストに惹かれて購入した。しかし真っ当に面白かった。そもそもみわべさくらさんがイラストを担当した作品で外れだったという記憶がない。もちろん全部買って読んでいるわけではないのだが。イラストの女の子は誰も、いかにも正統な美人という感じで落ち着きがありそうに見える。そういうイラストが合わせられた作品は自分の評価基準で減点してしまうような項目が少ないのかもしれない。また現代の恋愛モノでよく描いているイメージがあって、このジャンル自体に外れがあると感じていない。

内容について。実はいわゆる悪役令嬢モノをほとんど読まないので詳しいことはわからないものの、なろうで盛んに描かれるそれとは全く別であると感じた。精々口が悪いだけ。もちろんそういう態度にも理由があって、これについて主人公と関わりつつ踏み込んでいくという流れだった。苛烈な外面から推し量れるように、芯が強いヒロイン。彼女が校舎裏に呼び出されて女子3人に取り囲まれ主人公が助けに走るシーンがある。しかし結局はヒロインが口撃だけでやり込めてしまい、むしろそれを見てしまった主人公との間で一悶着あるという展開に、そういうことを特に感じた。この性質と自然に同居している寂しがり屋な態度が可愛らしい。あとは単純だがヒロインが多くて嬉しい。2巻以降でクローズアップされるだろう幼馴染たちに注目したい。

少し日記を書いて午前2時くらいに布団に入った。ネット小説の更新を漁っていたらすぐ寝落ちしてしまった。

07/01(金)

午前9時頃、目を覚ました。今日はゲーセンに行きたい。眠気が微妙に残っているものの、二度寝できるまで横たわっていたらどうせまた日が暮れてしまうので、もう起きてしまうことにした。

午前中はICPC模擬国内予選の参加記を書いていた。YouTubeに意識を吸い寄せられていた時間を含め4時間くらいかけて完成させて投稿し、また6月の読書記録をまとめてツイートした。先月は全然読めていないし、なぜそうだったのかすらよくわかっていない。ネット小説もそんなたくさん読めていなかった。

kotatsugame.hatenablog.com

6月の集計
買った：23冊
読んだ：4冊
積読：+19冊
積読（累積）：+66冊
— こたつがめ (@kotatsugame_t) 2022年7月1日

午後1時半に家を出発。実は前回ゲーセンに行ったのは06/08のことである。特に6月は1回しか行けていない。今日はその日以降に追加されたり通常開放された譜面を詰めた後、AJ狙いでいくつかプレイした。理論値+6、14AJ+1、14+AJ+1、15SSS+1。ゲーセンに行っていない間もずっとYouTubeの譜面動画を見てエアプしていたのだが、その時の体勢や顔の向きが実際の筐体でプレイするときと全然違うため、今日最初のプレイはかなり違和感があった。

フォニイ　理論値
最高です…… pic.twitter.com/EVRYiCeRRL
— こたつがめ (@kotatsugame_t) 2022年7月1日

最高すぎる。サムネのポーズに合わせて片手や両手が飛び跳ねる配置が多く、特に紫エアーと黄色タップでぴょんぴょんするところが信じられないくらい楽しかった。精度的には最初と最後の分割タップと、途中の拘束されながら一定のリズムでタップするところが難しい。前者は手を広げて片手で取ることで安定した。後者は指だけでなく手ごと、少し力を入れて押すことでリズムキープを図った。

泥の分際で私だけの大切を奪おうだなんて　理論値
最高です…… pic.twitter.com/B3AjKBZwa0
— こたつがめ (@kotatsugame_t) 2022年7月1日

全部腕押し。一所懸命にどついていたらすぐ出た。

テリトリーバトル　理論値
ツユ楽曲4つ揃った pic.twitter.com/nehmUc2HBk
— こたつがめ (@kotatsugame_t) 2022年7月1日

少し前のオリジナル楽曲の一つが音楽ユニット「ツユ」作曲だったらしい。それも含め、現在収録されている4曲について全部理論値を出してみた。

BlackFlagBreaker!! 5個！最高です pic.twitter.com/wf5P0W4bjG
— こたつがめ (@kotatsugame_t) 2022年7月1日

曲は最高。譜面はムズい。どこででも赤が出るので9950精度を出すのに大変苦労した。ところどころの微縦連でリズムが崩れてしまうのと、あとはYouTubeでMVをループしすぎたかリズムを勘違いしていて、どうしてもFASTを出してしまうノーツがあった。その場所を覚え意識して遅らせることで何とか正した。

ENDYMION SSS pic.twitter.com/N53oXzV0P2
— こたつがめ (@kotatsugame_t) 2022年7月1日

まさか出せるとは思わなかった。15の最高スコアを更新した。もう本当に大変。30回くらい連奏したらTシャツが汗まみれになってしまった。以下、運指を説明する。

16～27小節は分割ノーツが抜けまくるので、できるだけ手を大きく動かしながらお祈り。43、47小節は安定を取って擦った。51、53、55小節のくの字フリックは思ったより遅いので、手を速く動かすよりはちゃんとスライダーの端近くまで手を持っていくことを意識した。83、87小節と、89、90小節の最初のノーツは分割をないものと思って擦り、非交差運指とした。94～100小節は速すぎ。全力で手を動かしていたのにアタックが出てしまうし、しかも速すぎてどこで出ているのかいまいちよくわからなかった。結局よくわからないまま終わった。

117～118小節は手の位置を合わせる以外で譜面を認識しようとせず、あらかじめ決めておいた通りに手を動かしたら案外通った。実際のノーツ密度はそれほど高くないので怖がらないようにする。125～126小節は一瞬速くなる部分のリズムが取れないのと、直後に始まる激ヤバ配置に備えて手の動きを少なくしておきたいということから、擦りを組み合わせつつできるだけ交互に押すような運指を考えた。この二つについては詳しくは画像の通り。

あとは筋肉祭り。全力で右手を左手の上で反復横跳びさせる地帯と、全力で台パンする地帯。一回イヤホンが腕に引っかかって死んだため、それからイヤホンを外してプレイした。右手を反復横跳びさせるのはがむしゃらにやっていたら案外アタミスが出なかった。左手をできるだけ動かさないようにして右手の邪魔をしないようにすること、ある程度脱力することが必要。脱力に関しては腕を動かそうとしているのではなく、動いている腕を眺めているような感覚を覚えた。台パンは無理。フリックとエアーのせいでリズム崩されまくり。ちょっと力を抜いたらスカスカ抜けていったので、恥を投げ捨ててまさに全力で台パンしていた。音が酷くて申し訳ない。

Ai Nov AJ
緊張のあまり最後一瞬指固まってさすがに死んだかと思った pic.twitter.com/UIoxF0rKYz
— こたつがめ (@kotatsugame_t) 2022年7月1日

前から狙っていたやつ。後半ボロボロで道化師落ちしそうになっているが何とか通った。

閉店までプレイしていた。途中食事のため離脱したのを除いて9時間、53クレ分プレイしたらしい。体が痛い。ラーメンを食べて午前1時前に帰宅。

疲れ果てているのにYouTubeを見たりにじさんじの非公式wikiを読んでいた。動画は下のもので、wikiはレオス・ヴィンセントさん。

www.youtube.com

午前3時頃布団に入ってハーメルンの更新を読んだ。Vtuber小説のあとがきで、その小説の主人公Vtuberの名前がAIのべりすとから出力され、剣持刀也さんの配信に登場したということを知った。以下のツイートの通り。調べるとAIのべりすとの説明に「2022年初頭時点でネット上にある有意な日本語文章データを推定8割から9割程度読んでいる」とあったから、当然なろうの作品も学習していたのだろう。ちゃんとその主人公をVtuberだと認識しているのは面白いなと思った。

40分頃に出る『神坂怜』は私の書いているVtuberを題材としたweb小説に出てくる架空キャラの名前です。
剣持さん並びにファンの皆様の混乱を招いてしまい申し訳有りません。
私が謝っても仕方ない気もしますが
気が向いたら読んでもらえると嬉しいです。
後書籍化もするので何卒よしなに。 https://t.co/3L579j5Vva
— とくめい@アラサーV書籍化予定 (@hameln_tokumei) 2022年7月1日

AIのべりすと - ヘルプとwiki

午前4時半ごろに寝落ち。

07/02(土)

午前9時半に起きてしまった。YouTubeを見たり、「比企谷八幡　「・・・もう一度会いたかった」」を読み返していた。

www.youtube.com

syosetu.org

午後2時半に再度就寝。1時間後に冷凍弁当を受け取り、また即座に寝て、次に午後8時に起床。食事し、シャワーを浴びて、午後9時からABC258に出た。

AtCoder Beginner Contest 258 - AtCoder

Aから面倒。とりあえずC++で書き、以降も全部C++だった。Bは全探索。Cはどれだけrotateしたかを数値として持っておく。Dはどのステージまで1回クリアするか全探索し、そのうえで残りのクリア回数を $B$ が最も小さいステージで埋める。答えの最大値を $10^{18}$ にしていたら足りず、1WA。Eはダブリング。箱にじゃがいもが $N$ 個以上入るケースにサンプルを試すまで気づかなかった。

Fはまず大通りを通らないケースを答えの初期値にして、その後2点からそれぞれ4方向にまっすぐ進んだ先にある大通りに乗るとし、大通り上の座標間の距離を求めるのを $4\times 4$ 回行えばよい。マンハッタン距離にならないケースが存在するため場合分けして解く。場合分けの条件は入念に確認したのに、オーバーフローしていて1WA。Gはbitset。

Exは $X$ ではなく $Y$ を数えることにして、最後に追加した要素の偶奇を持つdpを考える。 $Y$ として使ってよい数を区間に分割し、それぞれで行列累乗することで高速化。新たに追加する数について偶数に対応する行列と奇数に対応する行列が異なるので、基本的には偶数と奇数をペアにして累乗し、前後を少し調整する形で求める遷移行列を得た。その前後が間違っていてデバッグに手間取った。

全完6位。今回は簡単め。Dは $B$ の累積MINを持たなくても、クリアした一番番号の大きいステージを連打すると考えてよかったらしい。確かに、どのステージまで1回クリアするか決め打ったとき、 $B$ のMINを達成するところで先に進むのを止めたほうが得になる。

コードゴルフ。Aはdc。0埋めするには $10$ で割った商と余りを見ればよいのによくわからないコードを書いていたため、そこを突かれて-1B。しかしまだ縮んだのでさらに-1Bしてギリギリ取り返した。BはRuby。CはPerlの最短コードをコンテスト後に縮めたらさらに-1Bされて、しばらく粘っていたらAWKで書き直すことでもう1Bだけ短いものが完成した。DはAWKでやっていたらdcに大敗北。

Gは隣接行列を2乗した後さらに隣接行列と要素ごとの積を取り、要素全体の和を $6$ で割ったものが答えになる。これをOctaveで実装したらかなり短くなったうえ3secにも間に合っているのに、行列積がバグっているせいでサンプル以外全部WAになってしまった。昔にもそういうことがあった。以下のケース以外にも山ほど正しく計算できないケースがある、どころか正しく計算できるほうが珍しいくらい。

[0 1 0 0 0 0 0 0
1 0 1 0 0 0 0 0
0 1 0 1 0 0 0 0
0 0 1 0 1 0 0 0
0 0 0 1 0 1 0 0
0 0 0 0 1 0 1 0
0 0 0 0 0 1 0 1
0 0 0 0 0 0 1 0]^2
を正しく計算できない
— こたつがめ (@kotatsugame_t) 2021年11月12日

結局この場ではnumpyが強い。Cygwinで動かすと $N=1500$ で9secかかるのに、Ubuntuだと爆速でびっくりした。インストール方法によって計算がSIMD化されるかどうかが違うというような話を聞いたが謎。また、行列の要素の型をintではなくfloatにしないと高速にならないのも注意。Cygwinでやっているときはどちらも同じくらい遅かったので短いほうのintを使ったコードを提出し、何回もTLEを食らってしまった。

午前5時から日記を書き、午前9時頃切り上げて布団に入った。新しく1作ハーメルンに手を出したら面白くて止まらなくなり、ずっと読み続けて正午過ぎに寝落ちした。

07/03(日)

午前3時直前に目覚ましで起床。即座にPCの前に陣取り、AHC012に備えた。開始と同時に問題を読み、とりあえず1Bの解をText提出して、あまりに眠いため布団に戻って二度寝した。

AtCoder Heuristic Contest 012 - AtCoder

結局その後の目覚ましでは意識こそ取り戻すものの起き上がることができず、コンテスト終了。せっかくの短期マラソンなのに何もせず終わってしまった。ちょうどコンテスト終了時刻にも目覚ましを設定していたため、布団で感想戦を眺めた後、昨日寝る前に読んでいたハーメルンを読み切った。

syosetu.org

「現代×アイマス×ポケモン」。非常に良かった。現実における戦術やポケモンの仕様を記憶したままポケモン世界に入り込む話はいくつか読んだことがあって、どれも主人公がポケモンバトルで無双するのでかなり好みである。ポケモンバトルで無双しているのは他で無双するのと捉え方が違う気がする。ほかの人より優れているのは真に知識だけ、かつそれで十分だと感じるからだろうか。この作品も同様の理由で好きだったのだが、シリアスなシーンの真っ最中にエタってしまったのは残念。

読み終えて、午後9時からさらに1時間半ほど寝ていた。起きて食事し、シャワーを浴びて午後11時半からCodeChef。今日はJuly Cook-Off 2022 div.1。

https://www.codechef.com/COOK143A

SEGFAULTはサンプルの説明がすべて。人 $i$ がthiefだったとすると、まず $i$ を含む区間が $N-1$ 人以上から主張されていなければならず、さらに $L_i\le i\le R_i$ であってはならない。この二つはサンプルの説明に書いてあって、しかも十分な条件になっている。両方満たされているならば $i$ を含む区間は自分以外の全員、ちょうど $N-1$ 人から主張されていることになるからだ。imos法で判定した。

LCMSEQは制約がカス。 $S$ としては長さ $M$ が $S$ のすべての要素を割り切るか、または全要素が等しい場合が思いつく。それ以外は少し試した感じなさそうだったので、この二つだけ数えることにした。前者は $M$ を全探索したい。後者は等しい要素をカウントして、 $A$ が $C$ 個あった場合 $2\le M\le C$ かつ $M\nmid A$ なる $M$ についてだけ $\binom{C}{M}$ を答えに足すと、先ほど数えたものをちょうど取り除けている。

前者で $M$ を全探索し割り切る要素をカウントする代わりに、約数を全列挙することにした。 $O(N\sqrt A)$ でギリギリ間に合いそうと思ったがTLE。もう一回別の方法で数えてTLEした後、いよいよ通らないため素因数分解して約数を列挙することにした。しかしこれもTLE。ここで、これまで見た数の約数たちをmapで数えていたところをvectorで持つようにしたら通った。こんなギリギリの制約で出すなという気持ちになる。

PQは簡単。まずスコアが負になる連続部分列は長さが $1$ であるとしてよい。ここで数列の最大値の係数が $+1$ になれるか考えてみると、その数列における2番目の最大値との差が $X$ 未満であればよいことが分かった。この時、数列全体を一つの連続部分列とみなすと全要素の係数が $+1$ となるため、得である。そうでない場合は最大値の前後で列を分け、それぞれ解く。クエリを $X$ の昇順に並べると、上のように数列を分割していく過程で決定したスコアがimos法で足せる。最後に順番を戻して出力。

STRBRKはなかなか気づけなかった。最初に適当に文字を対応付け、順列 $P$ を $1,\dots,N$ に一致させる問題にする。これでも解ける。正しい順番で隣接している数をブロックにまとめ、1手につき平均1個ブロックをマージできればよい。まず、 $P_1\ne 1$ の場合、その直前に来るべきブロックを探してくっつけることができる。具体的には $P_i=P_1-1$ なる $i$ を見つけてきて $\dots,P_i,P_1,\dots$ となるように操作すればよい。 $P_N\ne N$ の場合も同様。

さて、 $P_1=1$ かつ $P_N=N$ かつ $P\ne 1,\dots,N$ であるとしよう。このとき、先頭のブロックを $L$ 、末尾のブロックを $R$ 、また $L$ の直後に来るべきブロックを $l$ 、 $R$ の直前に来るべきブロックを $r$ とする。 $L,\dots,l,\dots,r,\dots,R$ と $L,\dots,r,\dots,l,\dots,R$ の2通りがあるが、どちらでも2手で $L,l$ と $r,R$ を隣接させることができるため、平均1個の条件が満たされる。具体的な方法を文章で書くのはややこしいだけなので、割愛。

残り30分ではこれ以上解けず、4完17位でレートは2730→2681(-49)。残念。LCMSEQはやはりvectorでできるところにmapを使っていたのが悪いらしい。コンテスト中最初に提出したTLE解をそこだけ書き換えて出したら通ってしまった。いや悪いのは僕ではなくwriterだな。

GRANDPAPA2の解法をTLで目にしたのでupsolveした。 $A$ と $B$ の両方のメジアンを固定しようとしていたが、 $A$ だけ固定すればよかったらしい。 $A$ のメジアンを $a$ とすると、 $A$ における $a$ 未満の個数が $\lceil N/2\rceil$ 未満、 $a$ 以下の個数が $\lceil N/2\rceil$ 以上となる必要がある。さらに $B$ における $a$ 未満の個数が $\lceil N/2\rceil$ 未満であれば、 $B$ のメジアンは $a$ 以上となって、問題の条件が満たされる。あとは辞書順に関する条件も入れて、 $2\times\lceil N/2\rceil\times(\lceil N/2\rceil+1)\times\lceil N/2\rceil$ 状態で遷移が定数個のdpを $N$ 回更新すれば答えが出る。これを $1\le a\le M$ で行えばよい。

計算量は $O(MN^4)$ で、定数倍が4分の1くらい。しかも任意modということもあり、念入りに高速化してギリギリで通した。例えば遷移の際に係数を掛けた値を変数に保存しておいて再利用したり、dpの次元を入れ替えてキャッシュがヒットするようにしたり。しかし一番効いたのは、驚くべきことに「dpの値が $0$ だったら遷移しないようにする」if文を一部外したことだった。辞書順の大小が決まっていない状態ではdpの値は多くの箇所で $0$ だと考えられて、分岐予測を失敗するリスクを取っても遷移を計算しないリターンのほうが大きい。一方辞書順の大小が決まっている場合、dpの値が $0$ になる箇所がほぼないためリターンが消え、ただリスクだけが残ってしまったのだろう。正直1secも変わるとは思わなかったが、いい経験だった。

明日の昼前が提出期限であるハードウエア基礎の課題が残っている。今週初めに終わらせていなかったのだ。確認すると、何やらIoTについてA4で1ページくらいのレポートを書けと書いてある。これまでの計算問題とは打って変わって曖昧な内容。こういう課題は嫌いなので、これまで毎回出してきたのだからと今回は見送ることにした。

午前4時から日記を書き始めたが、明日は昼からミーティングがあるため、午前8時くらいに切り上げて布団に入った。そこからなろうの更新を読み漁って午前9時就寝。

2022-07-01

ICPC模擬国内予選 2022 参加記

2022/06/25に開催された模擬国内予選にチームAobayama_dropoutで参加しました。今年のメンバーはha15さん・ホスフィンさん・僕です。

これで5年目、ついに最後のICPCシーズンとなりました。ほとんど僕のわがままのようなものですが、ずっと「Aobayama_dropout」として参加し続けることができたのはかなり達成感があります。僕と組んでくださった計4名のチームメイトの方々に感謝します。

jag-icpc.org

ha15さんは今日不参加とのことで、模擬国内はホスフィンさんと二人で参加しました。ホスフィンさんが大学の演習室を確保してくれて、そこに集まりましたが、部屋の窓以外3方向の壁にホワイトボードが設置されていたり、大きなモニターが運び込まれていたりして、望外に快適な環境でした。

今日の序盤の戦略は、ホスフィンさんにAとBを任せ、僕はC以降を読んでいくという割り振りでした。

C問題

まず、他の文字列の省略のされ方は関係ないことがわかります。よって、各文字列に対して最良の省略方法を独立に求めるという方針が立ちました。文字列の長さの最大値を $L$ （ $\le 30$ ）として、 $O(NL)$ で求められれば十分間に合います。先頭から残す文字数を全探索することを考えると、それで区別できない他の文字列の集合が求まり、それらを区別するために末尾から残す必要のある文字数を計算すればよさそうです。実装としては、最初に他の文字列それぞれについて「先頭から一致する文字数」「末尾から一致する文字数」を $O(NL)$ で求めると、先頭から残す文字数を決めるごとに $O(N)$ で決定できます。

実装し、off-by-oneエラーを修正してサンプルが合ったので提出しました。しかしWA。処理をコピペした部分で変数名が修正できていなかったところを見つけ、直し、出力が変化していることを確認して再度提出するも、これもWAでした。ここでようやく考察の抜け、最初の時点で文字数が異なる文字列はどのように省略されたとしても互いに区別できてしまうということに気づきました。上で言っていた「区別できない他の文字列の集合」を求める部分の条件にこの判定を加え、ようやくAC。13分＋2ペナかかってしまいました。

D問題

すでにA問題を通していたホスフィンさんからヘルプが来て、B問題がDPで解けることを指摘しつつ、D問題に進みました。問題の雰囲気だけからエスパーして、答えを達成するとき少なくとも1点は頂点に乗るんじゃないかと思いましたが、 $N\le 1000$ の制約がよくわからないのでちゃんと考えることにしました。実際これはサンプルで落ちます。

一周する時間を $O(N)$ 個の適切な区間に分割することで、それぞれの区間では各点が線分上を動くようにできます。つまり区間内では点の座標が時刻の1次式になります。それを使って三角形の面積を表現した式は、時刻の高々2次式に絶対値を付けたような形になりますから、これの最小値を求めればよいです。2次の係数の符号は式の形からはよくわかりませんが、どちらにしても区間の両端点と、 $0$ でない場合に頂点を見れば十分です。実装して40分時点でAC。

参加記を書いているときに気づきましたが、絶対値の中の式がちょうど $0$ になる場合を考察し忘れていました。実際にはこれも凸多角形であることから発生しません。

E問題

ここからは二人で取り組みました。まず $\gcd(M,x)=1$ という条件を無視すると、求める $x$ はある $0\lt x_0\lt T=M/g$ が存在して $0\le k\lt g$ によって $x=x_0+Tk$ と表せます。この $x_0$ は拡張ユークリッドの互除法で求められます。ここでとりあえず $\gcd(x_0,T)\gt 1$ の場合の答えを $0$ とする場合分けを書きましたが、実際にはそのようなケースは存在しません。

さて、ありえないことですが $T=1$ だった場合、この問題はオイラーの $\varphi$ 関数によって解けます。このことはホスフィンさんによって指摘されました。 $\varphi(n)=n\prod_{p\mid n}\left(1-\frac 1 p\right)$ という計算方法を考えると、素因数ごとに互いに素でないものを取り除いていることがわかります。同じような原理で数えることができて、答えは $\varphi(g)$ になるのではないかと考えました。ただし、素数 $p\mid g$ であって $p\mid T$ でもあるものについては、 $x=x_0+Tk$ は常に $p$ で割り切れませんから、考えなくてよいです。つまり $\varphi(g)$ を計算するときの素因数として $p\nmid T$ であるものだけ見ることになりそうです。

重複なく取り除けているかなど細かいことはわかりませんが、これで良さそうな雰囲気があったので、実際に書いて愚直と比較することにしました。diffが出て絶望しそうになりましたが、そのケースを確認してすぐに $g$ の素因数を求めた後 $T$ の素因数をちゃんと弾けていなかったことに気づきました。これを修正するとちゃんと愚直と一致したため提出し、AC。コンテスト開始から80分でした。

F問題

流量下限制約付きの最小費用流です。辺をあらかじめ $K$ 倍しておけば愚直に流すだけで解けます。流量の下限については確か事前に流しておけば普通の最小費用流になったはず、と思いつつ辺の張り方を調べて、 $N+2$ 頂点 $M(K+1)+2$ 辺のグラフに流量 $K+M$ のフローを流せば解けることがわかりました。とりあえずこれを書いてサンプルが合うのを確かめ、入力をダウンロードして計算し始めてから真面目に考察しようとしました。

10分くらい経ってから出力を確認すると、思ったより計算できていることがわかりました。大体20分で1ケース終わりそうです。ぶん回せば終わるということを確信してからまともに考察しようとする集中力が完全に切れてしまいました。その後も何とか考えるポーズを保っていると、辺のコストの取得時にすでに流れた流量を参照して計算すれば辺を $K$ 倍する必要がなくなり高速になるのではないかということを思いつきましたが、ライブラリをどのように書き換えれば良いか考えているうちに1ケース目の実行が終了したので提出してしまいました。

無事通ったので、2ケース目の実行を始めると同時にホスフィンさんのPCで逆順に計算し始めました。書き換えに手間取って結構遅れてのスタートになりましたが、最後10ケース分くらいはこちらの出力からコピーして、手作業でマージし提出。ここをミスると追加で20分ですから、二人で画面を睨みつけつつ丁寧丁寧丁寧に行いました。こちらも通り、136分時点で6完になりました。実は5完時点ではCのペナルティが響き、ギリギリで同じ東北大のチームであるsuzukaze_Aobayamaに負けていたので、抜き返すことができて一安心でした。

G問題

$C$ の累積和 $S$ を $S_i=\sum_{1\le j\lt i}C_j$ と定め、これでコストを書き直します。 $x_k\rightarrow x_{k+1}$ と移動するとき、 $x_k\lt x_{k+1}$ なら $S_{x_{k+1}}-S_{x_k}$ が、 $x_k\gt x_{k+1}$ なら $S_{x_k}-S_{x_{k+1}}$ が所持金に加えられます。よって、所持金の変化の総和を列 $S$ に係数を掛けて足したものと捉えると、その係数は $S_{x_1}$ と $S_{x_N}$ が対応するちょうど二つについて $\pm 1$ 、それ以外は $\{-2,0,+2\}$ のどれかになることがわかりました。またその係数列を達成するような移動が存在するためには、総和が $0$ になっていること、累積和が途中で $0$ より大にならないことも明らかに必要です。

ここまででいったんdpを書き、コストだけ求めることにしました。するとサンプルの $C=\{2,-3,4\}$ で $10$ が出てしまいました。手で試してみると、 $S=\{0,2,-1,3\}$ の係数列として $\{-1,+1,-2,+2\}$ を考えているようです。 $\pm 1$ がちゃんと最初と最後になれるように適当な場合分けを入れようとしましたが、もうちょっと考えて、より一般に係数列を達成するような移動がどこかで分割されてしまうと問題ということに気づきました。これを抑制するためには、累積和が最初と最後以外で $0$ になってはいけないという条件が良さそうです。書き直すとコストについては正しい値が出たので、あとは復元です。残り20分強。

dpの遷移元を記録しておくことで、係数列に関しては容易に復元可能でした。あとはここから具体的な移動を構築します。始点は $\pm 1$ に該当する2点のうちどちらでもよく、そこからスタートして最も近い折り返しできる場所を探し、折り返す、ということを貪欲に繰り返すことにしました。わざわざ遠いところまで行く必要はありませんから、移動が構築できるならこの方法でよいはずです。サンプルを試しつつ実装を修正し、REが出なくなったので入力をダウンロードして実行します。幸いこちらでは落ちることなく実行が完了し、提出すると通りました。2ケース目も同様にして、ついに170分時点でACしました。

コードを以下に貼っておきます。係数の符号を反転して実装しています。

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int N;
int C[3000];
long long S[3000];
long long dp[3001][6060][2];
int prv[3001][6060][2];
bool chmax(long long&a,long long b)
{
    if(a<b)
    {
        a=b;
        return true;
    }
    else return false;
}
int main()
{
    while(cin>>N,N)
    {
        S[0]=0;
        for(int i=0;i<N-1;i++)
        {
            cin>>C[i];
            S[i+1]=S[i]+C[i];
        }
        int now=0;
        for(int j=0;j<=2*N;j++)for(int k=0;k<2;k++)dp[now][j][k]=-1e18;
        dp[now][0][0]=0;
        for(int i=0;i<N;i++)
        {
            int nxt=i+1;
            int now=i;
            for(int j=0;j<=2*N;j++)for(int k=0;k<2;k++)dp[nxt][j][k]=-1e18;
            for(int j=0;j<=2*N;j++)for(int k=0;k<2;k++)if(dp[now][j][k]>(long long)-1e18)
            {
                if(j>=2)
                {
                    if(chmax(dp[nxt][j-2][k],dp[now][j][k]+2*S[i]))prv[nxt][j-2][k]=j*2+k;
                }
                if((k==1?j%2==1:true)&&j>=1)
                {
                    if(chmax(dp[nxt][j-1][1],dp[now][j][k]+1*S[i]))prv[nxt][j-1][1]=j*2+k;
                }
                if(j+2<=2*N)
                {
                    if(chmax(dp[nxt][j+2][k],dp[now][j][k]-2*S[i]))prv[nxt][j+2][k]=j*2+k;
                }
                if((k==1?j%2==1:true)&&j+1<=2*N)
                {
                    if(chmax(dp[nxt][j+1][1],dp[now][j][k]-1*S[i]))prv[nxt][j+1][1]=j*2+k;
                }
                {
                    if(chmax(dp[nxt][j][k],dp[now][j][k]))prv[nxt][j][k]=j*2+k;
                }
            }
            if(i+1<N)dp[nxt][0][0]=dp[nxt][0][1]=-1e18;
            now=nxt;
        }
        cout<<dp[N][0][1]<<endl;
        vector<int>coef(N);
        int nzc=0;
        {
            int j=0,k=1;
            for(int i=N;i>0;i--)
            {
                int njk=prv[i][j][k];
                int nj=njk/2,nk=njk%2;
                coef[i-1]=j-nj;
                if(coef[i-1]!=0)nzc++;
                j=nj,k=nk;
            }
        }
        vector<int>x;
        vector<int>usd(N,0);
        {
            int st=0;
            while(coef[st]%2==0)st++;
            x.push_back(st);
            usd[st]=1;
        }
        for(int t=2;t<=nzc;t++)
        {
            int pos=x.back();
            if(coef[pos]>0)
            {
                while(true)
                {
                    if(!usd[pos]&&coef[pos]==(t==nzc?-1:-2))
                    {
                        usd[pos]=1;
                        x.push_back(pos);
                        break;
                    }
                    if(!usd[pos]&&coef[pos]==0)usd[pos]=1,x.push_back(pos);
                    pos++;
                }
            }
            else
            {
                while(true)
                {
                    if(!usd[pos]&&coef[pos]==(t==nzc?1:2))
                    {
                        usd[pos]=1;
                        x.push_back(pos);
                        break;
                    }
                    if(!usd[pos]&&coef[pos]==0)usd[pos]=1,x.push_back(pos);
                    pos--;
                }
            }
        }
        for(int i=0;i<N;i++)cout<<x[i]+1<<(i+1==N?"\n":" ");
    }
}

コンテスト終了

残り時間はHを読んだだけで終わりました。僕らの後にもう1チーム7完が出て、最終順位はペナルティ差で3位でした。今回のコンテストはほとんどのタイミングで $n$ 完最下位だったので、やはり序盤に大量のペナを出すと辛いということを実感しました。結果的には過去最高の順位でしたが、たまたま完数で差をつけることができただけです。数年前はいつも最終的に $n$ 完最速に近い位置で終わっていて、もう1問が解けず悔しい思いをしていたのを覚えていますから、これも成長の一つでしょうか。

コンテスト後は本番の戦略について話していました。序盤・中盤の問題をどれだけ二人に振るかが問題です。例えば昨年の予選ではDとEをチームメイトに任せてFに特攻し、結局解けなかったのですが、しかしこれはムーブとしてはなかなか理想的な動きでした。今年もそういう感じで積極的に振ったうえで、自分もちゃんとコーディングできたらなと思っています。そのためにはFを解く必要があるので、解ける問題が出ることを祈っています。精進については……いろいろコンテストに参加してこそいるものの、upsolveすらできていない現状はかなり微妙ですね。

2022-06-27

週記（2022/06/20-2022/06/26）

06/20(月)

午後1時半起床。ここ最近覚えがないくらいスッキリとした目覚めだった。あとは今日中に週記を書き上げて投稿できれば完璧。

今週のチュウニズムのアップデート情報が流れてきた。「泥の分際で私だけの大切を奪おうだなんて」が追加されるらしい。少し前にMVを再生してドハマりし、数日ずっとループしていた記憶がある。歌が良いのは当然として、イラストの女の子の表情もどれも非常に良い。嫉妬したり、見下したり、憔悴したり。三つ目はもう少し別の表現もありそう。ジャケットやサムネになっている堕天後のイラストの表情を言っている。

【6/23(木) 「ツユ」コラボイベント開始！】
23日(木)より『くらべられっ子』『あの世行きのバスに乗ってさらば。』『泥の分際で私だけの大切を奪おうだなんて』の3曲がチュウニズムに登場！イベントマップではキャラクターやアイテムがゲットできるので、ぜひ遊んでみてね！https://t.co/2OHGGB6Wc1 pic.twitter.com/YFA5DPUeU5
— チュウニズム公式@6/23(木)『ツユ』コラボイベント開催！ (@chunithm) 2022年6月20日

www.youtube.com

生協に行ってパン類を買い、帰宅して午後3時半からミーティング。最近ペアプログラミングをしていた人が学習の進捗を報告するのを聞いていた。その人からかなりお褒めの言葉を頂いて嬉しい。自分からもいくつか意見や懸念点を伝え、これからどうするか話し合っている途中で1時間が経過したため、話を切り上げて定例会に移った。

定例会では特筆することはなし。最近ずっと少しコードを書き換えて学習を回すのを繰り返していただけなので、報告すべき進捗がない。ただここでも先ほどの方の進捗報告で僕の名前が出てきたので、それに便乗する形で少しコメントを加え、内容をかさ増しした。勉強会は自然言語処理の話。以前AlphaCodeの論文を読んだときもよくわからなかったし、今日の発表を聞いて理解が進んだかというと、あまり……という感じ。もちろん発表ではなく僕に問題がある。理解したければ手を動かす必要があるのだ。

課題レポートを錬成する。今日期限で残っているのはゲーム理論だけ。教科書の今回の章は前回同様発展的な内容が多く、課題の問題が発展的ではない部分、つまり章の残りカスみたいな部分からしか出ていなかったので楽勝。パパっと終わらせて日記を書き始める。午後11時を回って何とか完成し、投稿した。

先週日曜日のOpenCup代理コンテストの解説を読んだ。ただし取り組んだ問題だけ。特にA問題はいろいろ知見が得られたので、ここに書いておきたい。「頂点数 $N$ で辺が $2NK$ 本（以上）の無向グラフから、その部分グラフであって二部グラフかつ各頂点の次数が $K+1$ 以上になるようなものを構築せよ」という問題。今の表現は先週の週記に書いたものよりわかりやすくなったはず。

自分のアプローチは、各頂点の次数が $2K+1$ 以上になるようにグラフの頂点を削除した後二部グラフにするというものだった。逆で、二部グラフにしてからグラフの頂点を削除するのがよかったらしい。まず事実として「 $M$ 辺の自己ループを持たないグラフは『辺を $M/2$ 本以上持つ二部グラフ』を部分グラフに持つ」ということがあって、こうして作った辺が $NK$ 本以上ある二部グラフから次数 $K$ 以下の頂点を削除していくと、いつか全頂点の次数が $K+1$ 以上になっている。この操作でグラフが空にならないことは先週の週記でも書いた。Diestel Prop 1.2.2。

さて、先ほど登場した事実を示そう。といっても実は簡単。頂点をランダムに塗り分けると各辺が二部グラフに含まれる確率が一律で $1/2$ であるため、すべての塗り分けについて辺の数を数えたものの平均が $M/2$ 本となり、特に $M/2$ 本以上の辺を持つ塗り分けが存在することが言える。つい最近、次数に関してこうやって $\max\ge{\rm mean}\ge\min$ という議論を行った記憶がある。さらに $M\gt 0$ のとき $M/2$ よりstrictに大きくできること、また $M$ を固定していろいろグラフを変えたとき、「二部グラフとして持てる辺の数の最大値」の最小値が $M/2+O(\sqrt M)$ オーダーであることを熨斗袋さんに教えてもらった。以下のツイートとそのリプライ。あくまで $\Theta$ ではなく $O$ であるはず。

辺の数の評価ですが、全て片側に寄せるカットが大きさ 0 なので、M ≥ 1 のとき M/2 を超えるというのは言えると思います。
漸近的には M/2 + O(√M) で抑えられるはずです。2n 頂点の完全グラフのうち、辺の本数が M 以上となる最小のものを取ってくると示せます。
— 寝る (@noshi91) 2022年6月20日

そのような二部グラフの構築について、解説では乱択して適当に頂点を塗り分けた後1点flipを繰り返していた。しかしもっとオーダー良く決定的に解けるらしい。これまた熨斗袋さんのツイートによる。すでに集合に振り分けられた頂点への辺だけ考えると必ず半分以上を二部グラフに含めることができて、全部終わった時には $M/2$ 本以上になっているということ。

というのも、二部グラフを取るところで乱択ではなくて v = 1, 2, … の順に貪欲をしていけば deterministic に半分以上の辺を含む塗り分けを得られるため。
— 寝る (@noshi91) 2022年6月20日

来週月曜日午前中が期限の、ハードウエア基礎の課題レポートを錬成する。講義スライドは電気回路の計算を入念にやっていて、高校物理を忘却してしまった自分では何を言っているのか理解できなくなってきた。しかし練習問題と解答がいくつか載っていて、それをガン見しつつ手を動かすと課題で出るレベルなら何とかなった。スライドを眺めながら絶望していた時間が長く、課題を解くのはすぐできた。僕の理解では必要ないパラメータが問題文で与えられていたのが不安。

シャワーを浴びて2時間ほど日記を書き、布団に入った。TLでDMOJというコンテストサイトの話題が出ていて、ちょうど今Ratedのコンテストが開催されている様子。期間には余裕があるので、明日あたり出ようかなと考えた。午前7時就寝。

Home - DMOJ: Modern Online Judge

06/21(火)

午後1時半起床。

チュウニズムのアップデート情報がまた流れてきた。ありえないくらい最高すぎる。まず「フォニイ」の追加が嬉しい。ただそれよりも「BlackFlagBreaker!!」の追加に驚いた。音ゲー界隈と関わりの深い人たちが作った曲なのでいずれは追加されると思っていたが、さすがにちょっと速すぎて信じられなかった。もちろんこれも非常に嬉しいことである。

【6/23(木) 楽曲追加！】
6月23日(木)より、大人気niconico楽曲や、最新のPOPS&ANIME楽曲が合わせて3曲チュウニズムに登場するよ！ぜひ遊んでみてね！
「吉原ラメント / 亜沙」
「フォニイ / ツミキ」
「BlackFlagBreaker!! / 社築 × https://t.co/7H0EPjpRsQ」https://t.co/7Z0JyEHT0B pic.twitter.com/pFuUA4qTFE
— チュウニズム公式@6/23(木)『ツユ』コラボイベント開催！ (@chunithm) 2022年6月21日

昨日寝る前に見たDMOJにアカウントを作り、少し問題を解いてみた。CodeChefのとき日記に書いたような確認をここでもやってみたが、正直もう細かい仕様を覚えていられないので、AtCoder以外ではいつもlong longを使うし、main関数の型もしっかり書くようになっている。

今日はCodeChefのコンテストがあるらしい。先週気になっていると言ったばっかりだし、また今日はコンテスト尽くしの1日にしてみようという思いから、アカウントを作った。練習問題を3問ばかり解いて、どんな感じなのかを探る。main関数の型がなくてもCEにはならず、longは64bit整数らしい。
週記（2021/09/20-2021/09/26） - kotatsugameの日記

いったん大学生協に行って買い物。入荷メールが届いていたラノベを受け取ろうとしたら1冊が見つからなくて、しばらく探してもらっていた。オーバーラップ文庫。途中でこのレーベルが毎月25日発売日であるということに気づいたため、入荷メールの間違いということになった。最近予約でばかり買っているのでレーベルごとの発売日が頭から抜けてしまっている。

「奴隷」とか「ギルド」とか「Sランク」が含まれたタイトルを目の前で読み上げられ確認されてヤバかった。心臓に毛を生やしていなければ死んでいた
— こたつがめ (@kotatsugame_t) 2022年6月21日

帰宅し、午後6時ぐらいからBCI Programming Contest 1 Seniorに出た。4日間の期間が用意されていて、その中から適当な3時間を選んでコンテストに参加することができる。参加終了まで順位表は見られない。想像していたよりかなり難しかったし、順位表が見えないので本当に今取り組んでいる問題が難しいのかにいまいち自信が持てず大変だった。

BCI Programming Contest 1 Senior - DMOJ: Modern Online Judge

S1はまず $a_1$ を決定する。これまでに決定した数で作れるペアの和を全部削除しておくことで、その時々で最小のものが $a_1+a_i$ の形をしているとわかる。あとは繰り返し。

S2からもう難しい。 $0$ と $x$ の距離が $x$ に等しくなるような最大の $x$ は、 $p$ の小さいほうから二つを $p_1$ と $p_2$ として $L=\lfloor(p_1+p_2)/2\rfloor$ となる。また、 $0$ と $L+1$ の距離を聞いて $L-1$ か $L$ か判定することで、 $p_2-p_1$ の偶奇を特定できる。 $p_2-p_1$ が偶数のときは $L-1$ と $L+1$ が、奇数のときは $L$ と $L+1$ がそれぞれ $0$ から等距離にあるとわかる。もっと言えば、 $0$ から $p_1$ までの地点からは等距離にあって、 $p_1$ より右で2点より左（2点を含む）の位置からは等距離にない。よってこの範囲を二分探索することで $p_1$ が特定できる。 $p_1$ と $C$ の距離を聞くことで、 $p$ の最大値もわかる。

あとは内側を探索。ある開区間 $(l,r)$ について、その左右で最も近い $p_l,p_r$ がわかっているとして、 $(l,r)$ に別の $p$ があるかを判定するには、 $m=\lfloor(l+r)/2\rfloor$ と $p_l$ の距離 $a$ を聞けばよい。 $p_l$ または $p_r$ から直接向かうよりも短くなるなら $m-a$ または $m+a$ が $p$ の一つとなり、 $(m-a,m+a)$ には $p$ がないこともわかる。これで $(l,r)$ が二分割されるので、それぞれで再帰的に解く。1時間くらいかかった。

S3が初手から全く分からなかったので、S4に進んだ。 $A\oplus B$ と $0$ を場合分けしてXORする方針。 $A\oplus B$ のMSBと、 $A\cdot(A\oplus B)$ （ただし $\cdot$ はbitwise AND）のMSBが比較できれば良い。MSBを検出するため、ある数を右・下・左にずらしてbitwise ORしまくることでMSB以下のビットをすべて立てた数を作った。数 $X$ に対してそのような操作をした後の数を $f(X)$ とおくと、 $f(A\oplus B)\oplus f(A\cdot(A\oplus B))$ が非ゼロになるのとMSBが等しくないのは同値。こうして得られた数にさらに $f$ を作用させ、 $A\oplus B$ とのbitwise ANDを取ることで、 $A\lt B$ なら $A\oplus B$ になって $A\ge B$ なら $0$ になるような数が得られる。つまり、 $f(f(A\oplus B)\oplus f(A\cdot(A\oplus B)))\cdot(A\oplus B)$ 。

さて、 $f$ は計算用にレジスタを一つ破壊する。 $A$ と $A\oplus B$ を保存しておいて、さらに $f$ を同時に二つ持つ必要があるので、レジスタは五つ必要になって90点までの部分点が得られる。これを実装して提出。しかしWA。自前でチェッカーを書いても全然落ちなかったので、試しに $f$ の計算を賢くやっていたつもりの部分を愚直にやったら通った。ずらしてbitwise ORするときに $16\rightarrow 8\rightarrow 4\rightarrow 2\rightarrow 1$ と幅を狭めることで効率的に全部埋められると思っていたところを、 $1\dots 31$ を全部行う方針に。何がダメだったのかわからない。

残り20分もないため、ほかの問題は無視してこのまま満点を考える。まず $f(A\oplus B)$ を作り、適切にずらしてbitwise ORを繰り返すことでこれのMSBだけ下ろした数を得る。その数を $X$ とし、また $Y=A\cdot(A\oplus B)$ とする。 $Y\oplus(Y\cdot X)=Y\setminus X$ を計算した結果が非ゼロになるのと、 $A\oplus B$ と $Y$ のMSBが等しいことが同値になる。あとは先ほどと同様にすれば、 $A\gt B$ なら $A\oplus B$ になって $A\le B$ なら $0$ になるような数が得られる。こちらのアルゴリズムはレジスタ四つで実装できる。

残り時間が少ない。サッと書いてチェッカーに投げると合わず、焦りながら何度も読み返したものの結局合わないまま終わった。直後に、先ほどは $A\lt B$ なら $A\oplus B$ になっていたところが今は $A\gt B$ なら $A\oplus B$ になるということに気づいた。非常に悔しい。

公開された順位表を見に行くと現時点で9位。自分より上の人は全員S3で満点を取っているので、実は解けなければならない問題だったらしい。今考えてみても全然わからない。S4の満点は二人しかいないので、余計に悔しくなってきた。総じて良い結果ではない。コンテストが難しかったこともあってしばらく放心状態だった。

終えてから日記のコンテスト部分を書き、戻ってS3のupsolveをした。あまりに無理すぎて途中椅子で寝入ってしまったが、何とかひらめきを得ることができた。

最初に $X\leftarrow X\bmod{\sum_i a_i}$ としておく。まず、バスもバス停も同じ色のものが固まって同じ順番で並んでいるのが最適とエスパーする。固まっているほうが明らかに嬉しくて、バスとバス停が列として一致する瞬間があるとさらに嬉しそうだから。あとは時刻 $0$ の時点でいくつずれているかの問題になって、部分点はずらす幅を全探索してバスごとに寄与をカウントしても通る。ここまではコンテスト中に考えていたこと。ただし実装はしなかった。

最大の非自明ポイントとして、このずらす幅はおよそ $X/2$ と決め打ってよいらしい。考え方としては、全くずれていない状態のとき答えに対する寄与が最も大きくなり、そこから左右に行くごとにどんどん減っていくはずだから、時刻 $0$ から $X-1$ の間に達成するずれ幅の区間を $[-\lfloor X/2\rfloor,\lceil X/2\rceil)$ などとして $\pm 0$ を含みつつその左右がだいたい同じ長さになるようにしたくなる、というものだった。部分点のコードを書き換えて提出してみると当然のように通ってひっくり返った。

あとは答えを求める部分の高速化。気合いが必要。ある色について、その色のバスが時刻 $0$ から $X-1$ の間にどの位置をどれだけ通るかの分布は台形になるため、傾き $+1,\pm 0,-1$ の部分に分割して、それぞれその色のバス停と重なる部分を求めて答えに足す。もう見るからに面倒そうなことを言っているが、実装してみると案外すらすら書けた。一発でAC。確かにこれは解けるべきだったかもしれない。しかしこれを通していたらS4は部分点も間に合わなかっただろう。

upsolve後はYouTubeに気を取られつつ昼間までおすすめのなろうまとめを書いていた。朝あたりに指導教員の先生からメールが来て、今週木曜日のセミナーがキャンセルになった。よって思いっきり生活リズムを乱すことができる。正午就寝。

そういえば今日は夏至だったらしい。コンテストへの参加が終わったあたりでTLを見て気づいたが、日記のその部分に割り込ませるのが不自然だったのでここに書いておく。

今日夏至！？
— こたつがめ (@kotatsugame_t) 2022年6月21日

06/22(水)

午後9時起床。ICPCの誓約書を提出した。また昨日参加したコンテストが終了していた。16位まで落ちて、最初のレーティングは2320。

YouTubeのチャンネルにコミュニティ投稿ができるようになったと通知が来た。登録者数500人で開放される機能らしい。思いがけない特典があって嬉しい。最近、YouTubeの動画の共有ボタンを押すと「投稿で共有」という謎の表示が出るようになっていたが、これもコミュニティ投稿が可能になったことによるもののようだ。

おすすめのなろうまとめを書く。昨日と同じくらい進められれば今日終わりそうということで頑張っていた。午前9時になってついに完成し、投稿した。

kotatsugame.hatenablog.com

前の記事から継続して紹介しているのが21作品、ここ1年で読んだものから26作品選んだ。ジャンル分けについては、二次創作が多いし、どうしても全部主人公最強モノという観点で見てしまっているので、今回はすっぱり諦めることにした。

こうして改めておすすめできるものをまとめてみると、一般にも評価が高い作品ばかり集めてしまったなという感想になる。ではこの記事の意義はどこにあるのかという話だが、ジャンルを問わず一人の人間が好きなものを集めたという点にあると考えている。特定のジャンルの作品を読みたいなら自分で検索して評価順に並べればよい。そこから離れ、別のジャンルなりあまり知らない作品の二次創作なりにこの記事を読んで手を出す人がいれば嬉しい。

学食で食事し、帰宅してからはしばらくラノベを読んでいた。午後2時就寝。

06/23(木)

午後10時起床。しばらくYouTubeを見ていた。

www.youtube.com

周央サンゴさん、かなり面白い。普通にやっていても面白いうえ、上手なのに題材が意味不明な声劇が最高。また朗読の際の声を人間が発音していることに驚くし、イラストとまったく合っていないように思えて笑ってしまう。

ラノベを2冊読んだ。まず1冊目、「灰原くんの強くて青春ニューゲーム」2巻。1巻に引き続き非常に良かった。当時日記に「微妙な緊張感がある」という感想を書いて、たぶんこれは態度を取り繕っている主人公がボロを出さないかドキドキする状態を指していたと思うが、1巻ラストの展開を受けて2巻ではかなり緩和されていた。依然としてまだあまり関わりのない人からは完璧超人という扱いを受けているものの、主人公はこれを不思議がりつつ軽くスルーするため、素直に主人公を引き立てるシーンとしてニヤニヤできた。この巻からは仲間内の恋愛模様について焦点を当てている。特に、心に決めた人が1巻から変わっていない主人公に対して積極的にアプローチを掛けるヒロインの話。まあこの人に対してはラストで一段落ついたため、不安定な状態は脱したように見える。しかしその過程で周囲の様々な関係が表出してきて、次の巻はどれだけ思惑が入り組むのか楽しみである。

2冊目、「才女のお世話」3巻。面白かった。幼馴染であるヒロインがようやくメインを張る。その幼馴染が抱える問題を解決しようと奮闘しているうちに、主人公も入学以来いつの間にか生じていた自身の問題点に気づく。後者については、別に叙述トリックというわけではないもののラノベ読者から見ると結構盲点な気がして、そういう展開になるのかと驚いた。ラストシーンは多少テンプレ展開に見えるが劇的でよい。しかし剣道の試合の最中に大声で声援を送るという描写は受け入れ難かった。それなしでは確かに味気ないので展開上の要請はありそう、とはいえもう少し気を使ってほしいところ。

日記に本の感想を書き、学食で食事して、それからなろうを読み始めた。午後3時半寝落ち。

06/24(金)

午後11時起床。実は明日土曜日は昼からICPC模擬国内予選らしい。完全に生活リズムが合っていない。大学から出る予定なので、とりあえず何も考えず注文した生協の冷凍弁当の配達を月曜日に振り替えてもらえるようメールを出した。

今日は横たわったまま過ごすことでできるだけ早く寝ようとし、布団でなろうを読み始めた。午前3時くらいになって1作読了。「隣に住んでる聖女様は俺がキャラデザを担当した大人気VTuberでした」。

https://ncode.syosetu.com/n5518hm/

非常に面白かった。そもそもとして、「Vtuber」と「半同棲」という僕が好きな題材を合体させているのだから気に入らないはずがない。特にVtuberパートが好み。タイトルにもある通り主人公はイラストレーターで、担当したVtuberに誘われて親娘コラボを繰り返し人気となっていた。二人が思いがけずリアルで対面することから話が始まるのだが、それ以前の設定だけで自分のストライクど真ん中。ファンに認められているくらい仲の良いVtuberの男女コンビは最高。

設定の話ばかりして内容に触れていなかった。Vtuberモノとしての配信パートと半同棲モノとしての恋愛パートをそれぞれだけ見ても十分面白い。前者については主人公がLive2Dの肉体を手に入れるくだりが好み。後者については学校、つまり他者の目があるところでも二人が距離を近づけていく様子が良い。いずれ二つのパートが大きく交わる展開もありそうで期待している。すでに描かれた部分としては、オフコラボのシーンがそれの一例になるだろうか。今のところおおむね独立して進んでいるように思う。

DMOJでまたRatedのコンテストが開催されていることに気づいた。金曜日から月曜日までの日程だが、土日はコンテストで埋め尽くされているし、月曜日はインターンだったり課題だったりでこれまた予定を入れたくないので、今日参加しておく必要があったらしい。明日の予定を鑑みて今からでもギリギリ大丈夫だと判断し、午前3時半から3時間で参加した。内容や感想については、今日の日記を公開する時点でコンテストが終了していないので来週の週記に書こうと思う。

DMOPC '21 June Contest - DMOJ: Modern Online Judge

公開するのは来週だが、文章は今日作成する。書き終えるともう午前8時を回っていた。布団に入り、そこから何を思ったかなろうを2時間以上読んで、午前10時半就寝。

06/25(土)

午後1時起床。死にそう。ノロノロ準備して出発し、学食で食事しつつ山に登った。信じられないくらい暑かった。

ホスフィンが大学の演習室を確保してくれたので、そこからICPC模擬国内予選に参加する。午後2時から3時間のコンテスト。これについては参加記を書く予定なので、日記ではあまり触れない。投稿したら以下にリンクを貼っておこう。全体3位だったことだけ、かなり嬉しいのでここにも書いておきたい。

07/01追記：投稿した。

kotatsugame.hatenablog.com

午後6時前に帰宅。即座に布団に横たわってABCまで仮眠を取ろうとした。しかしうまく眠れず、結局2時間横たわっただけになってしまった。ずっと目が冴えていたので、肝心の頭が休まった気が全然しない。シャワーを浴びて眠気を少しでも取り、午後9時からABC257。

NS Solutions Corporation Programming Contest 2022（AtCoder Beginner Contest 257） - AtCoder

Aはパッと見よくわからなかったので実際に文字列を作って解こうとし、C++で書き始めたところで $\lfloor(X-1)/N\rfloor+1$ 番目のアルファベットを出力すればよいことに気づいた。そのままC++で書き上げ、ACを確認した後、dcでも提出しておいた。Bは愚直に。Cは $S_i$ と $W_i$ を組にして $W_i$ でソートし、区切りをずらしつつ差分更新する。同じ体重の人を区別できないことに注意。このあたりの問題にしてはちょっと難しいなと感じた。

Dも難しい。 $i\rightarrow j$ と $j\rightarrow i$ でジャンプするための $S$ の下限が異なり得ることを見落とし、最小全域木を求めようとした。無向辺ではなく有向辺だと思わなければならないと知り、考察をやり直す。始点を1点決めると、そこから各点に到達するための $S$ の下限がdijkstraで計算できる。辺の数が $O(N^2)$ なので $O(N^2\log N)$ のdijkstraを $N$ 回行った。実装途中で答えが最大 $4\times 10^9$ とint型の最大値を超えることに気づき、コストの変数をlong longに修正したのだが、し切れていなかったようで1WA。

Eは最初に $9$ を連打することを考えて、それより桁数を増やすほうが得だと気づいた。桁数の最大値は $\lfloor N/\min C\rfloor$ になるので、これを達成できる限りで最上位桁から数字を大きくしていくのがよい。実装も簡単で、D問題のACから2分ちょっとで通った。見た目からdpっぽさも感じていたので拍子抜け。Fは、結ぶ街の片方が未定のテレポーターを超頂点 $0$ に繋がる辺だと見なしてグラフを作ればよい。頂点 $0$ と $i$ を同一視したときの $1$ から $N$ までの最短距離を求めることになって、 $1\rightarrow N$ と $1\rightarrow 0\rightarrow i\rightarrow N$ と $1\rightarrow i\rightarrow 0\rightarrow N$ の距離の最小値となる。 $1$ 、 $N$ から各頂点への距離をそれぞれ前計算すればよい。GはZ-Algorithmとrange chminで実家dpができる。range chminのほうは優先度付きキューで、今見ている要素への作用素を持つことで実装した。

Exは難しい。kyopro_friendsさんの解説と全く同じ式変形によって、 $\left(\sum x\right)^2+\sum y$ を最大化する問題に帰着した。よくわからないので適当な貪欲を試してみる。 $(x,y)$ の降順にソートして値を順に追加し、 $K$ 個を超えたら取り除いたときの値の減少量が最も小さいものを取り除く貪欲を書いてみると、70ケースくらいまで通った。もしかしてACかと思いかなり興奮したものの、蓋を開けてみると6ケースWA。次に $(y,x)$ の降順にソートして同じことをすると、5ケースWAに減った。最後に、 $(x,-y)$ の降順にソートして連続する $K$ 個を選ぶコードを追加してAC。

Editorial - NS Solutions Corporation Programming Contest 2022（AtCoder Beginner Contest 257）

最後の場合分けは、 $\sum x$ をいろいろ試しつつ $\sum y$ を最大化しようとしている。これまで値を1個だけ交換してきたが、2個交換するときどうなるか計算してみると、 $x$ が交換したペアの両方で増えているか減っていれば1個だけ交換するのよりよさそうだったので、積極的に $\sum x$ が減る方向に動きたかったのだ。

80分弱で全完、Dの1WAとExの4WAで5ペナ、4位。Dの想定解は二分探索だったらしい。考えもしなかった。Exの解説は大変そうなことが書いてあって、僕のコードに正当性がないことしかわからない。

コードゴルフ。A問題はAC直後に提出したdc 9Bが最短でよく、ちゃんと速度でも勝てていた。BはPerl。CはRubyで書いたがPerlに大敗。EはRubyで負け。他は手付かず。

眠気をこらえ、午後11時半からCGR21に出た。

Dashboard - Codeforces Global Round 21 - Codeforces

Aは $\max_i (a_i\mid z)$ が答え。Bは2手で必ず可能なので、0手と1手の判定ができればよい。0手は自明で、1手は両端から続く $0$ を削除したとき $0$ が残らないことを確認する。Cは逆の操作が可能なので、 $a$ と $b$ に操作を施して何らかの正規形にし、一致するか判定すればよい。具体的には1番目の操作で分解できるだけする。一応ランレングス圧縮して保持したが、普通に持っても間に合うくらいの長さにしかならないようだ。Dは右にしか進まなくてよいと思い込んで貰うdpをした。左向きの累積max・minを持って、それが更新される点だけdpの値をセグ木に乗せておく。あとは区間MINで今見ている点までの距離が求まる。

Eは各マスに対してそこに置かれた人形を消すのに何手必要かを手計算してみると、寄与の流れが見えてきた。 $i+1$ 行目の手数の列から $i$ 行目の手数の列を求めるとき、長さが $a_i$ になるよう $0$ 埋めし、全体に $+1$ したあと右から累積和を取るという操作をしていることがわかる。この $+1$ がマス $(0,0)$ にたどり着くときいくつになるか考えればよくて、これはマス $(x,y)$ から左と上への移動を繰り返してマス $(0,0)$ に到達する方法だから $\binom{x+y}{y}$ となる。よって求める値は $\sum_{x=0}^n\sum_{y=0}^{a_x-1}\binom{x+y}{y}$ となり、内側の総和がよく見る形。Wolfram|Alphaに投げたらちゃんと閉じた式になった。

Fはまず各頂点 $k$ について頂点たちを $k$ からの距離が同じものでグループ分けしておく。次に根を1点固定し、その子、つまり根から距離 $1$ にある頂点の集合を考える。どれかわからないので全探索する。実は、ここまで決めると木としては高々1通りになる。なぜなら、親 $p$ と子 $u$ の組が与えられたとき、 $u$ の子は $u$ からの距離が $p$ と同じになるからである。先ほど分けたグループから $p$ を含むものを見つけ、 $p$ 以外を $u$ の子とすることでBFSのようにして木を下っていける。途中ですでに見た頂点が出現したらダメだったということ。最後まで決めきれたら、改めて条件をチェックして出力する。グループ分けするときUFを使っていて、 $d(u,k)=d(v,k)$ かつ $d(v,k)=d(w,k)$ なのに $d(u,k)\ne d(w,k)$ であるようなケースに引っかかってしまい1WA。

残り1時間ちょっとはGを考えていて、端から決めるときの計算を関数だと思ってセグメント木に乗せられそうだったのだが合成が書けず終了した。

システスは全部通って速めの6完で21位。レートは2875→2964(+89)。あと1回上振れすればLGMだが相変わらず遠く感じている。

Dの右にしか進まなくてよいというのはあまり正しくない。解説では「常に右の最も遠い点に進むのが最適」という事実が紹介されていて、これを含んでいるからたまたま正しくなっていたようだ。右にしか進まなくてよいことを証明するためには、途中で左に進むような経路を取ってきて右にだけ進む経路で再現するのが一般的だが、かなり難しそう。少し取り組んでみたところ左に何回進むかなどで場合分けが大量発生し、早々に放り投げた。

Eは各マスに何個人形が置かれるかカウントするのでも答えが求まる。マス $(x,y)$ に置かれる人形の数を求めるときは、上に書いたのと全く逆の $(0,0)$ から右と下だけに進んで $(x,y)$ にたどり着く方法だと見れて、値は同様に $\binom{x+y}{y}$ になる。Fは根と子を一つ、つまり1辺決めてもよかったらしい。そもそもグループ分けが正しくないことに気づかず使っていたのが問題。計算量的には余裕があるので、子を探索するときに入力を直接見る方法で $O(n)$ かけてもよかった。

かなり眠い。布団に入って少しなろうを読み、午前4時半就寝。

06/26(日)

午前9時半に起きてしまった。かなり眠気が残っていたのにうっかりスマホを取り、TLを見て、二度と眠れなくなった。布団に横たわったままずっとなろうを読んでいたが、一向に眠れる気配がないので、午後2時半に布団から出て、しばらくICPC模擬国内予選の参加記を書いていた。

午後4時からOpenCup。今週も代理コンテストで、ARCと被せないため開始をこの時間にするということで合意が取れていた。今日のコンテストタイトルはPTZ 2021 Summer Day 2, NAC 2021。ちなみに代理コンテストは五つしかなく、これが最後である。

Petrozavodsk Summer 2021. Day 2. The American Contest - Dashboard - Contest - QOJ.ac

チームとしてMFLDJCEAGを解いた。僕は最初2時間をAに費やし、解けず、次の2時間半でGを解いた。ずっと椅子を温め続けていたので非常に苦しいコンテストだった。Gが通ったのもよくわかっていないので消化不良気味。Aは考察の初手が違っていて、後半は僕が考えていたことと同じことをやるようなので少し悔しい。チームメイトが通してくれたので感謝。

Gについて。クエリを $a$ の昇順に並べ、先頭から数列を展開していく。展開後の長さは前計算できるので、クエリに関係ないならスキップする。このとき、展開後の列に含まれる $k$ の個数というのをすべての $k$ に対して求めたくなる。値 $n$ を $s$ 回展開するとすれば、 $k\le n$ に対して展開後の個数が $k$ の $s-1$ 次式になる。 $s$ は非常に小さいので、多項式をBITに乗せれば区間和を取得することで個数が求められるようになる。

ただし $a\le 10^9$ なので、途中をスキップしたとしても何項見ることになるのかがよくわからなかった。残りの展開回数が $0$ 回になってからようやくクエリの計算をしていたらTLEだったので、残り $1$ 回の時点で求めるようにしたら通った。このとき固定された順列に対して区間内の $k$ 以下の要素数が知りたくなったので、 $\log$ が2個つく重めのライブラリを持ち出したが、さすがに全部展開するよりは速かったのだろう。

直後、午後9時からARC143に出た。

AtCoder Regular Contest 143 - AtCoder

Aは、 $A\le B\le C$ としてまず $B=C$ となるように操作したい。つまり $A$ と $C$ から $1$ 引くのを $C-B$ 回繰り返すため、 $A\ge C-B$ である必要がある。一度 $B=C$ になりさえすれば、後は $B$ 回の操作で全部 $0$ にするのが最適。

Bは少し難しい。まず1番目の条件を満たさない数は各列の最大値である。列 $i$ の最大値を $M_i$ とおいて、 $M$ の最小値が $i=i_m$ で達成されるとしよう。すると $i\ne i_m$ について、 $M_i$ と同じ行の $i_m$ 列目の数は $M_{i_m}$ 以下になる。今 $M_i\gt M_{i_m}$ なので、 $M_i$ と同じ行により小さい数があることが分かった。したがって2番目の条件も満たさないようなマスはあるとすれば $M_{i_m}$ だけである。あとは $M_{i_m}$ を全探索して適当に組み合わせ計算。

Cも難しい。最初、選ぶ山がちょうど一つだと勘違いしていた。少しの勘違いもあり解けたと思って実装し、サンプルが合わず、誤読が判明して絶望。ただし、相手の操作を真似することを考えて $A\leftarrow A\bmod{(X+Y)}$ としてよいという考察が変わらず適用できたので軽傷だった。そのような操作をした後 $A_i\ge X$ なる $i$ がなければ先手負け。まずこれでサンプルが通って提出し、WAだった。もうちょっと考えて、 $X\gt A_i\ge Y$ なる $i$ があると自分に手番が返ってくる可能性があることに気づいた。この条件を追加すると通った。

Dは案外あっさり解けた。 $(A_i,B_i)$ を辺と見たときに出現するループは、 $A_i\leftrightarrow B_i+N\leftrightarrow B_i$ と展開することで問題のほうのグラフでもループにできる。これを $A_i\rightarrow B_i$ という有向辺だと思うと、二重辺連結成分だったものが強連結成分となるよう向き付けられれば最適で、実際dfs木を使えば達成可能。これは日記を書きつつ整理したうえでの表現で、コンテスト当時どのような閃きでdfs木にたどり着いたのかは記憶があいまいで再現できなかった。ともかく実装し、提出すると1ケースだけWAで絶望したが、頂点番号を0-indexedにしていなかっただけだった。すぐ出しなおしてAC。ちなみに実装テクとして、0と1のどちらが $A\rightarrow B$ かということには注意を払わなくてよい。全部逆にしても橋の本数は同じになるからだ。

Eは初手が完璧で一瞬で解けた。葉の石をどのタイミングで取り除くか考えると、親より前か後かという話になって、初期状態を見ることで決定する。またこれに応じて親の石の初期状態が変わったと見なせて、さらに以降その葉は無視してよくなる。このように葉を順に削除していき、最後に残る1点の状態を見ることで判定問題が解ける。また各辺についてどちらの端点の石を先に取り除くかという条件だけが操作列に要請されるので、辞書順最小の構築はトポロジカルソートを優先度付きキューで行うという典型問題になる。実装も特に手間取ることなく一発AC。

この時点で2位。Fに80分残すことができて、初の全完もあり得るかと思ったが、その後ずっと考えていても解けずに終了した。最後のほうは愚直と比較していて、 $N=7$ で $\{1,2,3,5,7\}$ と $\{1,2,3,6,7\}$ が数えられていないことに気づいたものの、最後に $7$ を入れるかどうかの判定が難しいことに気づいて絶望。いや、 $N=7$ ならまだ何とかなっていた。しかしもっと大きな数になるともっと盛大に破綻していることに気づいて、今度こそ諦めてしまった。

結局Fは誰にも解かれず最終順位も2位。ARCでは最高。かかった時間がそれぞれ3分、7分、12分、8分、7分と、DEが自分でも信じられないくらい速かった。2ペナ出してしまったのが惜しいなと思っていたが、1位とは12分差なので惜しくもなんともない。3位とは10秒ちょっとの僅差だったので危なかった。

Eの判定問題は、初期状態における表が白い石の個数の偶奇を見るだけで解けるらしい。なるほど、葉から削除していくとその偶奇が変わらないことから確かめられる。コンテスト中は考えもしなかった。こういう顕著な性質が必要なく、むしろ想定解から外れていく罠になってしまう問題というのも面白い。

コードゴルフ。Aは $2\times\max(A,B,C)\gt A+B+C$ なら $-1$ 、そうでなければ $\max(A,B,C)$ なので、dcで実装。Bは解説にある閉じた式をさらに整理し、 $(N^2)!-\frac{N!^2(N^2)!}{(2N-1)!}$ をRubyで計算する、コードをVimで書いている。さすがに $(500^2)!$ は厳しいため $\bmod$ を取った値を使うことになり、割り算が面倒だが、 $\frac{(N^2)!}{(2N-1)!}=\prod_{i=2N}^{N^2}i$ と求めることにするとかなり縮んだ。CはPerl。シンプルな条件に見えて結構面倒で、うまい表現が思いつかず微妙に長そうなコードを書いている。以降は手付かず。

もうあり得ないくらい眠い。しかし今週末出たコンテストはどれも非常に良い成績を残しているため、午前1時からのSRM832にも出ることにした。

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

Easyは面倒。まずcommandsを1回実行したとき各点を何度訪れるかカウントする。最初はcommandsの要素がめちゃくちゃ大きいことに気づかず愚直を書いていた。後から気付いて修正。周期が $N$ なので、 $1\le i\le N$ に対して $i$ 個先を通るのが何回かそれぞれ数えるのが楽だった。次に、commandsを1回実行するたびに進む数が求まるので、これを $R$ 回繰り返したときどの地点から何回commandsを開始することになるか数えた。こちらは元に戻る周期が $N$ より小さくなる可能性があるが、 $N$ だと思って計算しても問題ない。最後に $O(N^2)$ かけて畳み込むと答えになる。始点に $+1$ することを忘れずに。

Medも面倒。 $A=0$ の場合に解ければ差を取ることで答えになる。まず、 $S$ の長さが $B$ になるとき何桁の数を追加しているのか調べる。 $n$ 桁のgoodな数は、 $1\dots n-2$ 桁のgoodな数に対して $n$ 桁目のbitを立てたものになるから、その個数や含まれる $1$ の個数が順番に求まる。桁数 $n$ を確定したら、「その桁が立っている状態で」下の桁が $1\dots n-2$ 桁のどれに該当するか調べていく。再帰的に繰り返すことで上位桁からどこが立っているか順に求まっていって、最後に中途半端な部分を調べる。非常に怖いので小さい値で愚直と比較したり、途中で桁数が大きくなりすぎたりしないか調べたり（58桁の数まで追加されるようだ）してから提出した。

Hardは簡単。 $i=1\dots N$ の順でループし、 $A$ を $i$ 番目から左に見ていったときに初めて出現する値の位置を差分更新で列挙する。 $H=i$ なるクエリ $[L,H)$ について、列挙した数であって区間 $[L,H)$ に含まれるものの和を求めることで、必要なtmaxの和が求まる。これは1点更新区間和のセグ木で実現できる。 $i=N\dots 1$ として同様のことを行えばtminも得られる。解法はすぐ出たものの実装に手間取って900点中600点くらいになった。

チャレンジの時間はARCのコードゴルフをしていた。全部通って全完8位、レーティングは2815→2848(+33)。highestである。

いよいよもって眠すぎる。日記をめちゃくちゃ溜めているが、かまわず寝てしまうことにした。さすがに今日睡眠失敗したのは痛い。午前3時半就寝。

2022-06-23

増えたやつ

影の勇者の再冒険　～～Re-Tale of the Brave～～

学校ごと異世界転移。その世界で勇者だったことを隠している主人公だが、それでも素の実力が十二分にあるため表向きの立場がガンガン上がっている。正体を隠しているという設定と、めちゃくちゃ強くて活躍しているという設定が両立されており、非常に好み。またほんの少しずつ周囲の人に正体を明かしていて、そのシーンごとに解放感があって気持ちいい。ただ非常に長いので内容は希釈されているように感じる。

https://ncode.syosetu.com/n5534co/

剣姫転生　〜エルフの娘は世界最強の剣士を目指す〜

無職転生の二次創作。重い話は全部原作主人公に押し付けてオリ主は自由に行動しているので、かなりストレスフリーに読めた。原作では本当にレアだった帝級や神級が大盤振る舞いされていて爽快感がある。

剣姫転生〜エルフの娘は世界最強の剣士を目指す〜 - ハーメルン

SAOを真面目に攻略しない人々

短編集。「キリト君にゲーム作らせたら解決なんじゃないかな」が一番好き。決して本題ではないが、ゲームの難易度調整を重ねるうちに現実における体の動かし方に影響が出てきた描写が特に好みだった。

SAOを真面目に攻略しない人々 - ハーメルン

ウマ娘　ワールドダービー　凱旋門レギュ『4:25:00』　ミホノブルボンチャート

プレイヤーキャラクターの造形が好み。行動がRTA走者によって制御されるから基本合理的ではあるが、その中でもRTA部分で描かれなかった話から見える性格があって、サイドストーリーではRTA関係なく面白い小説が読める。その性格が如実に表れた「サイドストーリー:怒髪衝天」が印象的で大好き。

ウマ娘ワールドダービー凱旋門レギュ『4:25:00』ミホノブルボンチャート - ハーメルン

ソードアート・オンライン　ラフコフ完全勝利チャートRTA　2年8ヶ月10日11時間45分14秒(WR)

上のRTA小説とは違い、プレイヤーキャラクターはとことん合理的。こちらにもサイドストーリーと同等のものが用意されているが、そこでも効率的にゲームのクリア目標だけを達成しようとする主人公が描かれる。その完璧に取り繕われた外面で人を操っているのが好き。

ソードアート・オンラインラフコフ完全勝利チャートRTA 2年8ヶ月10日11時間45分14秒(WR) - ハーメルン

もこたん→青ニート←その他大勢

ダークソウル由来の装備品や能力で無双しつつ東方Projectの世界で過ごしている主人公の話。古代スタートの要素もあり。不死となって枯れ切った主人公が原作キャラに向ける超然とした態度が好き。

もこたん→青ニート←その他大勢 - ハーメルン

正体不明の妖怪(になった男)、情緒不安定な百獣の腹心になる

ワンピースの二次創作。東方Projectクロスオーバー要素は主人公以外なし。主人公もワンピ世界で普通にあくどい海賊として成長していく。そのバロメータとして懸賞金がどんどん上がっていく描写がわかりやすく、興奮した。主人公の全力バトルは少なく暗躍多め。

正体不明の妖怪(になった男)、情緒不安定な百獣の腹心になる - ハーメルン

ヒエヒエの実を食べた少女の話

主人公勢力は善良な海賊（善良な海賊？）で、やがて成長していくと海運を牛耳ったりする。そうやって強大な組織を真っ当に運営している描写が好み。周囲の畏怖も良い。

ヒエヒエの実を食べた少女の話 - ハーメルン

じゃしんに愛され過ぎて夜しか眠れない

遊戯王の二次創作。圧倒的ドロー力でデッキをぶん回して勝ちまくるのが爽快。説明も細かいので、カードを知らなくても楽しめた。

じゃしんに愛され過ぎて夜しか眠れない - ハーメルン

黄金の経験値

MMORPGでラスボスのロールプレイをする主人公の話。周囲からNPCだと思い込まれつつ暗躍し続け、自勢力を強化したりほかのプレイヤーを手玉に取ったりする策略の描写がどれも読んでいてワクワクする。途中から積極的に表舞台に立つようになるものの、結局最後まで自分の正体を明かすような場面はほぼなかった。今のはそういう要素を求める人向けのネタバレ。

https://ncode.syosetu.com/n0806fu/

万魔殿の主〜胡散臭いトレーナーとウマ娘たちは日本を驚かせたい

トレーナーの主人公がチームを作って勝ちまくる。これもミホノブルボンチャートと同じく主人公の設定が好み。丁寧な物腰で、底知れなくて、天才。

万魔殿の主〜胡散臭いトレーナーとウマ娘たちは日本を驚かせたい@休止中、活動報告にて詳細 - ハーメルン

Vtuberってめんどくせえ！

主人公は女性Vしかいない箱から唯一デビューした男性V。些細なことでの炎上を繰り返しつつ、人柄や考えが知れ渡って人気が出ていく。ヒロインである同じ箱の女性Vとの関係性がめちゃくちゃ好き。配信上でも知らず知らずイチャイチャするくらいで、またそのような行動がファンから認められるような仲。

Vtuberってめんどくせえ！（烏丸英） - カクヨム

自作3Dモデルの素材を宣伝するためにVtuberになったら予想外に人気出てしまった

主人公がVtuberではあるが、配信や動画のシーンは少なめでリアルの人間関係が多く描かれる。キャラたちの間に複雑な関係があって色んなニアミスが描かれ、もどかしい思いをした。主人公がひたすら鈍感で何事にも動じない様子なのが好き。

自作3Dモデルの素材を宣伝するためにVtuberになったら予想外に人気出てしまった（下垣） - カクヨム

プレイしていたゲームの能力で転生するやつ

タイトル通りにオリ主がネギま世界に転生する。そうやって得たチート能力をうまく使って、原作キャラを立てつつ自分も盛んに活躍するバランスが心地よかった。

【完結】プレイしていたゲームの能力で転生するやつ - ハーメルン

秋宮ゆららは青を喰む

Vtuber小説。軽い気持ちで配信しているのにあまりに多才すぎて人気が出まくるのが、視聴者の反応も含めニヤニヤできる。同期との関係も好き。

秋宮ゆららは青を喰む - ハーメルン

Vの者！～挨拶はこんばん山月！～

Vtuber小説。主人公とその同期を始めとした同じ事務所の仲間たちが、各章ごとに襲い来る困難を乗り越えていく。誰も彼も才能に溢れていて勢いがあり、日常パートは面白おかしく、シリアスなパートは胸を熱くしながら読めた。三章ラストの吹っ切れ具合とライブシーンが特に好き。

Vの者！～挨拶はこんばん山月！～ - ハーメルン

アラサーがVtuberになった話。

主人公がデビュー時点で自分とは関係ないことで大炎上し、その後も人気がずっと低迷している。しかし鋼のメンタルで何事もなかったかのように淡々と活動を続ける様子が安心して見ていられるし、面白い。64、65話は特別感動的な話で好きなのだが、そこでも心無いコメント等が描写されるあたり徹底している。

アラサーがVtuberになった話。 - ハーメルン

蓬莱山輝夜お嬢様がコナンの世界入りした話

非常に面白い。たった20話足らずでまとまっており、読了後の余韻が心地よかった。事件と解決のパートが大胆にカットされているのもスピード感があり、濃密さに拍車がかかっている。途中いくつも自分好みのシーンがあったのも嬉しい。具体的には、輝夜が超有名人になったのに平気で出歩いて目立ちまくるところ。

蓬莱山輝夜お嬢様がコナンの世界入りした話 - ハーメルン

阿礼狂いに生まれた少年のお話

東方の二次創作。幻想郷の黎明期を生きた主人公の一生を描く。タイトルにも「狂い」と入っているように主人公の精神性の根っこはずっと変わらないのだが、表層は生きていくうち徐々に変化していって、中盤からはそうして形成された気質に惹かれて周囲に集まる人妖との交流が感傷的に描かれることが多かった。終盤になると、ああ主人公の死期が近づいてきたんだなというのが文章から明らかに感じられるようになって、大変名残惜しい思いをしながら読み進めていた。泣ける。

阿礼狂いに生まれた少年のお話 - ハーメルン

天地神明の真祖龍

モンハン二次創作。古龍の祖という最強中の最強の主人公が人間を観察したり、対話したりする描写が好み。

天地神明の真祖龍 - ハーメルン

帝征のヒーローアカデミア

古龍に変化する能力を持った主人公。シンプルに強いし、見た目もかっこいいので体育祭のクライマックスがとても好き。普段ののんびりした態度とのギャップも良かった。

帝征のヒーローアカデミア - ハーメルン

クラップスタナーは２度鳴る。

暗殺教室の二次創作。原作主人公がTS逆行転生する。原作前の部分がかなり好き。本校舎の設定や雰囲気がかなりそれらしく作りこまれていて感心した。その生活の中で逆行したことによる知識・能力の利点を活用していくのは爽快。

クラップスタナーは２度鳴る。 - ハーメルン

銃と私、あるいは触手と暗殺

主人公は元傭兵。原作でいくつかあった潜入や戦闘のシーンでは存分に無双しており、読んでいて楽しかった。そういう場面ばかりではなく、クラスメイトや殺せんせーとの交流を通じて自己の認識が傭兵から中学生に変わっていく過程も描かれて、暗殺者という観点からは弱体化とも言えるものの、納得感があった。

【完結】銃と私、あるいは触手と暗殺 - ハーメルン

俺は竈の女神様

ダンまち二次創作だがエタる直前まで原作前の話なのでほぼオリジナル。特に後半はいくつか別の原作世界に入り込むので、クロスオーバーっぽくもなっている。様々な権能を持つ神様である主人公が、上位存在らしく基本好き勝手している話。強さに裏付けされた自由人っぷりが好み。

俺は竈の女神様 - ハーメルン

デート・ア・ライブ　士道リバーション

原作からヒロインの攻略順序が変わり、さらに時期が大幅に早まっている。そのため一人ひとりとの関係がより深まっていて、特に七罪とのイチャイチャが微笑ましかった。またシーンとしては「狂三スチューデンツ」の高校に入学する部分がピンポイントで自分の好みだった。

デート・ア・ライブ士道リバーション - ハーメルン

俺の家が幻想郷

タイトル通り、自分の家でミニチュアサイズの東方キャラが生活するという話で、この設定が天才的で好き。主人公の描写がかなり厨二臭いのは読む人を選ぶかもしれない。

俺の家が幻想郷 - ハーメルン

続投

アイドルの世界に転生したようです。

アイマス二次創作。トップアイドルである主人公がその影響力などを駆使して数多のアイドルたちが抱える問題に介入していく話。外伝『Days of Glory!!』はそこから離れて完全オリジナルストーリーが展開され、主人公たちのライブが開催される。本編を忘れた、ただただ楽しい盛り上がりが本当に好き。

アイドルの世界に転生したようです。 - ハーメルン

この〇〇のない世界で

アイマス二次創作。逆行転生した主人公が未来知識とチート能力でアイドルどころかサブカルチャー全体の始祖のようになる話。思い付きで行動したり手当たり次第に事業を立ち上げたりするもどれも大当たりして、現在につながる文化の流れが作られていくのが読んでいて楽しい。

この〇〇のない世界で - ハーメルン

青空よりアイドルへ

アイマスの二次創作。主人公は見た目が貧相なのに歌や踊りのスペックはまさにチート的。そのことが掲示板で話題になっているという描写が好き。

青空よりアイドルへ - ハーメルン

最強カップルのイチャイチャＶＲＭＭＯライフ

どの章もラストに向けてだんだん話が盛り上がっていって、そのクライマックスに配置されているレイドボス戦が最高に熱い。そういうのを章ごとに何度も楽しめたのが非常に良かった。また、主人公たちは特に配信者ではないのだが、トッププレイヤーらしく活躍する様子が周囲の人間の配信に映ってコメントが盛り上がるという描写が好き。

https://ncode.syosetu.com/n2143dt/

打撃系鬼っ娘が征く配信道！

リアルの身体能力が人間の常識を遥かに超えている主人公がVRMMOの配信をする話。リアルチートで活躍しまくるのが好き。

https://ncode.syosetu.com/n9517fc/

逆行転生したおじさん、性別も逆転したけどバーチャルYouTuberの親分をめざす！

本編は転生してからVtuberの親分と呼ばれるくらいまでの話で、下積み時代の描写が苦しかった分報われたときは嬉しかった。その後から配信アーカイブとして1話完結の話が大量に投稿されていて、どれもシンプルに笑えるという意味の面白さがあってとても好き。

https://ncode.syosetu.com/n3530fy/

輝きたくて

Vtuber小説。逆行転生した主人公がVtuber運営会社を立ち上げて軌道に乗せる。そういう行動力、またやることなすことが型破りで、単に未来知識頼りの人間ではなく十分な才能があったということが周囲の反応から明らかになっていって好きになった。

輝きたくて - ハーメルン

俺は星間国家の悪徳領主！

悪徳領主を目指してそれっぽいことをいろいろするものの、どれも良いように捉えられてしまうという勘違いもの。行動の意図を周囲に勘違いされるときのギミックが手が込んでいて好き。

https://ncode.syosetu.com/n1976ey/

プニキとはじめるリーグ運営　～野球ゲーム？作って運営します～

高度な技術で、コンピュータ上でできる限りリアルに近づけた野球を再現し、AIの対戦を観戦する「だけ」のゲームを会社を作って運営するという話。スケールの大きな構想を一歩一歩実現していく過程が丁寧に描かれ、とても面白い。よりリアルに近づけるため、野球に関係するありとあらゆることにパラメータを設けたり機械学習による判断を入れているという工夫を解説しているシーンが、読んでいてワクワクする。

https://ncode.syosetu.com/n4212eh/

始まりの魔法使い

竜に転生した主人公が原始人を導いて魔法を体系立てる話。襲い来る困難がどれも重く否応なしに変化を強いられる中で、長命な主人公が昔を懐かしんだりする描写の、人から一歩引いた感じが上位者っぽくて良かった。人口が増えて集落の人間を全員覚えられなくなったという話をしていたのが、人が竜に庇護されるという状態を決定的に離れた感じがして印象深い。また第四章第19話も好き。

始まりの魔法使い（石之宮カント） - カクヨム

滅竜山くんの一生　～46億歳、全ての生命と魔の祖～

主人公は意識を持つ山で、オリジナル生物を作ったりしつつ生態系の変遷を見守り続ける。そういう「長命な主人公が歴史を作る」という自分のストライクゾーンど真ん中のストーリーが、たった16話で簡潔にまとまっているのは驚き。

https://ncode.syosetu.com/n3617fx/

東方遺骸王

前半は主人公の活躍が、後半は前半で張られていた伏線がことごとく原作の設定に繋がっていく物語の構成的な緻密さが好き。主人公はあまり表舞台に姿を現さないので、大きく動いて自分の持つ力を振るう「遺骸王の激昴」の章がかなり印象に残っている。この展開は大好き。原作キャラが登場しない期間が長いので、ほぼオリジナルだと思って読むべき。

東方遺骸王 - ハーメルン

少女(仮)の生活

主人公が一般人に紛れたり人里離れたところに居を構えたりしながら歴史を眺め続ける話。ただし、強大な力を持っているのに身内の都合を優先するので、いろいろ引っ掻き回すことも多い。その自分本位さに圧倒的な超越者っぽさを感じて好き。

少女(仮)の生活 - ハーメルン

東方狐答録

原作開始の遥か昔からスタートする、いわゆる古代スタートと呼ばれるジャンルの話。東方の古代スタートは、原作キャラが幻想入りする前に元ネタの神妖として活動していた時代に交流したうえでの、幻想入りした後の再会シーンが醍醐味だと思っている。必然的に主人公は長命となり、また長生きするにつれて強大な力を持つようになるため、様々な意味で自分の好みに一致しておりジャンル自体が大好きである。この作品も例に漏れない。第七十二話から少し現代入りする部分が好き。

東方狐答録 - ハーメルン

天才最弱魔物使いは帰還したい　～最強の従者と引き離されて、見知らぬ地に飛ばされました～

最弱の肉体とそれに見合わない強靭な精神を持ち、魔物使いという職業で最強になった主人公が、使役する魔物と引き離されてしまうところから始まる話。そうして戦闘力は皆無になってしまったものの、新天地でも手練手管で基盤を作り、頭の回転だけで存在感を示している様が明らかに異質でかっこいい。ただの設定だけではない、確かにカリスマのある主人公だと感じている。第一章第四十五、四十六話、第二章第三十六話が好き。

https://ncode.syosetu.com/n4224gn/

陰の実力者になりたくて！

勘違いもの。身の回りで起きていることに何も気づいていないのに、実力だけは圧倒的な最強で、いつも見せ場はしっかり決めてしまう主人公が好き。

https://ncode.syosetu.com/n0611em/

最強魔法師の隠遁計画

魔法師の世界ランク1位である主人公が半引退のつもりで身分を隠しつつ学園に入学する話。結局引退できていない。世界最強なのは作中ずっと変わらないけれども、その力を誰にどのように披露するかがだんだん大胆になっていって、そこから得られる爽快感が好き。

https://ncode.syosetu.com/n5606cq/

サイレント・ウィッチ

天才魔術師が正体を隠して学園に潜入する話。魔術に関すること以外はポンコツでコミュニケーションが苦手なため、いろいろ問題に巻き込まれてしまい、解決する過程で学園の生徒たちと仲を深めていく。主人公がいつどのように正体を明かすのかばかり気にしながら読み始めたが、そういう特別な一瞬への期待感を抜きにしても普段のドタバタ騒ぎから面白い。軽めの文章や台詞で気持ち良く読める。

https://ncode.syosetu.com/n8356ga/

うちの脳内コンピューターが俺を勝たせようとしてくる

りゅうおうのおしごと！の二次創作。脳内に将棋AIを飼っていてめちゃくちゃ強いという設定で、その強さを存分に発揮するコンピュータとの対戦シーンがどれも好き。特に「一閃」とその近辺。将棋AIが強いだけで主人公はただの人なんだと思っていたが、実はそうでもないということがはっきりと明らかになるのが良かった。

うちの脳内コンピューターが俺を勝たせようとしてくる - ハーメルン

Game of Vampire

ハリポタの二次創作で、東方とのクロスオーバー＋オリジナル主人公。ハリー世代にただオリ主を放り込むのではなく、その親やさらに親の世代から主人公勢力が継続的に魔法界と関わり続けている。そうやって積み重ねる歴史のそれぞれにおいてハリポタ原作の重要キャラと主人公勢力の東方キャラとの間に特別な関係が生まれていて、後々描かれる「ホグワーツ同期のパチュリーと会話するダンブルドア校長」などこれぞ二次創作と言わんばかりのシーンが確かな実感を持つようになった。連綿と続いた流れがついに回収されていくハリー世代はもう最高。シーンとしては「魔法」、「開戦」、「さよなら」が大好き。

Game of Vampire - ハーメルン

比企谷八幡　「・・・もう一度会いたかった」

社会人から逆行した比企谷八幡が、社会人生活で手に入れた知識・技術を振るいつつ高校生活をやり直す話。行事の企画・運営に社会人目線でメスを入れたり、語学力で人脈を築いていくという描写が良い。後者に関しては21話のような展開が非常に好みである。

比企谷八幡「・・・もう一度会いたかった」 - ハーメルン

2022-06-20

週記（2022/06/13-2022/06/19）

06/13(月)

先週は週記を投稿してすぐ布団に入った。午後0時半就寝。

午後4時過ぎ起床。あまりの眠気に体が動かず、5分おきにセットしていた目覚ましに助けられ何とかインターン先定例会の前に布団から這い出た。先週もほとんど何もしていない。昨日の夕方から回していた学習は未だにlossが下がり続けていたので、ログ出力から途中経過を見てそれっぽいことを言ったりしてお茶を濁した。

勉強会はリファクタリングの話。こういうのは宗教的な要素を多分に含んでいて、自分の感覚と合わないものも多い。競プロをやっていて書き捨てのコードばかり触れているからと思っていたが、実は統合開発環境を使わずほぼ素のVimだけでコーディングしているのも問題な気がしてきた。例えば変数・関数の型を自分で覚えておく必要がないというのはかなり便利だろう。そういう機能を駆使することで、プログラムの泥臭い実装からある程度離れて全体的な構造を把握するのもやりやすくなりそう。まあそんな規模のコード群に触れたことがない身でいろいろ言っても仕方ないか。

今週も月曜日は課題に追われる日。一つ目はゲーム理論。今回の教科書の範囲には発展的と注記された内容がたくさん含まれていて、これは課題も大変そうだと身構えていたら、さすがに大変すぎたらしく教科書の演習問題ではなくスライドで定義されたゲームに関する証明が一つだけ課題になっていた。簡単。

二つ目はハードウエア基礎。小さな論理回路が与えられるので、FPGA上に設計せよという問題だった。ルックアップテーブルで $n$ 変数関数をシミュレートするのは便利だが、これまで基本的なゲートを組み合わせて頑張っていたのを振り返ると、何というか仰々しすぎる気もする。問題も論理回路を設計するというよりは論理回路の入出力の様子を見て同じ挙動をするように設定するだけで、何が面白いねんという感想に。

三つ目は離散数学。もういい加減分かってきたが、数学科の学生がこの講義を受講して得られるものは単位だけである。学部一年の専門科目でやったことを延々繰り返している。さすが文理問わず受講できる講義なだけはあるぜ……。ただ僕も単位しか求めていないので、実はWin-Winになっている。今日も無難に課題を解いて提出しておいた。来週は休講になるらしい。

四つ目はまたハードウエア基礎。教員3人が持ち回りで担当していて、今週の講義から教員が変わると同時に、課題の提出期限も次週月曜日の23時59分から10時30分に変えられていた。気づけて本当に良かった。念のため今出ている課題をもう終わらせておくことにする。今回は様々な要素から回路の抵抗や容量を求めて云々する問題。レポート提出という形式になったので、答えが正しいか即座にはわからない。変な値になったのが気になる。

終えて午前1時半。日記を書いて午前3時過ぎに布団に入った。

校正と校閲の言葉の違いを知った。これまで日記を読み返して文章を手直しするのを校正と言ってきたが、校閲のほうが正しそう。まあ本当は推敲のほうが良いのだろうが。検索すると「校正」という単語が出現した記事が五つしかなかったので、全部別の表現に直しておいた。

午前4時就寝。

06/14(火)

午前10時前に目を覚ました。まだ寝足りないので二度寝をしようと思いつつ、ついつい布団でスマホを触ってしまう。ABC249で8位を取った時の賞金10000円が届いていた。

先週日曜日（から日付が変わって月曜日）、寝る前に生協に出向いた際に一言カードを確認したら、回答で電話による相談窓口が紹介されていた。せっかく営業時間内に起きているので、ここに電話してみることにする。昼前なのでまだそこまで忙しくもないだろう。納豆の購入制限をなくしてほしいと何度も言ってきたが、自分の考えをもう一度整理すると、結局納豆を一度に2パック購入する方法さえあればよいということが分かったので、これについて聞いてみることにした。

開口一番「レジに2回並べば2パック買えるので正しいのか」と言ったところ、想定しない行動であるが可能との回答を頂いた。なんだ可能なのか。先週僕をレジで止めた担当者の方がルールを勘違いされていたという話も出てきたので、おそらく次からは止められないのだろう。また、ご飯の量が多いなどの理由があればその場で申し出ることで対応してもらえもするらしい。席に食事を置いて離れるのは正直抵抗があるので、こちらを採用したい。

ハーメルンを読んでいた。まず4話でエタっているものをサッと読了。内容の感想はない。そういえば、チャンネル登録者数が1000人なのに普段から同接が500人というのはさすがに無理があると思ったな。しかしどのあたりならリアリティがあるのだろう。知名度は低いけど一部にカルト的なファンを抱える、という状況なら案外近い値を叩き出すのかもしれない。

syosetu.org

比企谷八幡がVtuberになるハーメルンは他にもある。1年以上前に読んで、そのときすでにエタっていたのだが、以来何話か更新があったので改めて読み直していた。やはり面白いし、面白くなりそうという感じもする。

やはり俺がVtuberになるのはまちがっている。 - ハーメルン

昼過ぎからは「輝きたくて」を読み返していた。何度目かわからない。とにかく面白い。

輝きたくて - ハーメルン

午後3時くらいに二度寝に成功。次に起きると午後10時半だった。ICPC模擬国内予選の参加登録が始まっていたので、チームメイトのメールアドレスを聞いてフォームを送信しておいた。

ICPC OB/OG の会による模擬国内予選を 6/25 (土) に実施します。
参加を希望するチームは以下のページより申し込みをしてください。申し込みの締め切りは 6/19 (日) となっております。申込期間が非常に短くなっていますのでお気を付けください。https://t.co/hUSQ5gbwLn
— ICPC OB/OG の会 (@icpcjag) 2022年6月14日

午後11時半からCF #799 div.4。

Dashboard - Codeforces Round #799 (Div. 4) - Codeforces

Aは問題文を読むのに手間取った。 $a$ より大か小である個数を答えればよさそうだったので、あとはサンプルを見て合わせ提出。Bは消すべき個数を求めて切り上げ。必ず1個以上残せるので、切り上げたとき $n$ を超えることはない。Cは実際にビショップを配置して一致するかチェック。端にないという制約の意味が分からず首を傾げていたが、後からこの制約なら8近傍がXのように埋まっているかチェックするだけでよいのだと気づいた。Dは最初の状態に戻るまで $x$ 分経過させるのを繰り返し、それぞれ回文かチェックする。

Eは尺取り。Fは $\bmod 10$ で要素をカウントし、 $a_i\bmod 10$ と $a_j\bmod 10$ を固定して対応する $a_k$ が存在するかチェックする。Gは $a_i\ge 2a_{i+1}$ なる要素を含まない区間を数える。隣り合う各ペアに関する条件なので添え字の $\pm 1$ がちょっと難しかった。一度 $b_i=[a_i\ge 2a_{i+1}]$ と置いて、この数列の連続する $k$ 項を考えるほうがやりやすかったか。Hは $a$ を決め打って、それが出現するインデックスを先頭から $I_1,I_2,\dots$ としたときに $i\le j$ のもと $2(j-i+1)-(I_j-I_i+1)$ を最大化すればよい。 $(2j-I_j)-(2i-I_i)+1$ と変形すれば $2i-I_i$ の累積 $\min$ を管理する典型。

24分全完で10位。

今日もマイク音声付きで録画していた。相変わらずボソボソ喋ってしまった部分もあるが、問題文の読解フェーズはあまり黙らないように頑張った。全完まで24分しかないのでほぼ無編集で投稿してしまおう。コンテスト終了までに前後を少しカットしてエンコード・YouTubeへのアップまで済ませておき、コンテスト終了後に公開した。サムネはopen hacking phaseが終わってから。

www.youtube.com

今日の夜にしぐれういさんがゲリラ配信をされていたらしい。アーカイブを視聴した。

www.youtube.com

29分21秒時点。気になっていた期間限定商品の販売がすでに終了しているとコメントに嘘をつかれ、すごい顔をするシーン。Live2Dの表情が豊かで可愛らしいですね。

https://www.youtube.com/watch?v=piVNAMMi0_k&t=1761s

日付が変わって06/15からTCB48が始まっていたので参加した。例のごとく日曜日終了なのでここに感想を。

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

6問目はとりあえず根から最も遠い頂点が $2^N-1$ であることがわかるが、もう片方はすぐには決定できない。しかしLCAを全探索すれば十分で、そこからコストを求めるのも毎回 $O(N)$ かけてよい。7問目は二分探索して判定はUF。判定に $O(N^2\alpha(N))$ かけてちょっと怖かったが普通に通った。8問目は親の顔より見た拡張dijkstra。

9問目は難しい。トポロジカルソートを計算するときについでに何かすることで求まるのかと思って考えるもよくわからない。入次数が $0$ の頂点からの最長距離でグループ分けしたものを提出して思いっきりWAを出した。反例だらけ。30分ほど考えてどうにもならなかったので、各点についてそこに到達可能な点とそこから到達可能な点が合計で $N+1$ 個になることを確認する方針に。DAGの到達可能性判定は各頂点でそれぞれ愚直に計算する $O(N(N+M))$ をビット並列にするやつ。事前にトポロジカルソートすることで見るべき頂点を減らし、定数倍にさらに $1/2$ を付けて提出すると4.6secくらいで通った。C++最高！

10問目も難しい。その頂点にたどり着いた時の操作回数 $\bmod 2$ を考えて頂点を倍化すると、辺 $(a,b,c)$ が $(a,c)\rightarrow(b,1-c)$ と $(b,c)\rightarrow(a,1-c)$ になり、 $2N$ 頂点 $2M$ 辺の有向グラフが得られる。このグラフのすべての辺を通るような道を見つける……わけではない。辺も倍になっているので、そのうち片方ずつさえ通っていればよいというのが問題。まず強連結成分分解して、始点を含む強連結成分からどのように辺を辿っていけばよいか考える。今見ている強連結成分から出る未使用の辺が二本以上あったとき、どれを使うべきか。

実はどれでもよい。そのような辺が2本 $e_1,e_2$ とあったとして、それぞれペアになっている辺を $e_1',e_2'$ とおく。例えば $e_1$ を使ったとする。このとき二度と $e_2$ は使えないので、そこから先のどこかで代わりに $e_2'$ を使う必要がある。そうしたら、その間で使った辺をすべてペアのもう片方に置き換え、逆から辿ることができて、 $e_2$ からスタートして $e_1'$ で終わるような道もあることが言える。 $e_1$ の始点から $e_2'$ の終点への道が $e_2$ の始点から $e_1'$ の終点への道になってしまうが、問題ない。なぜなら、今 $e_1$ の始点と $e_2$ の始点は同じ強連結成分に属していて、その2点を含むループを先ほどのように反転することで $e_1'$ の終点と $e_2'$ の終点を含むループが得られる、つまり2点が同じ強連結成分に属するとわかるからである。

強連結成分間を渡るとき、すでにペアのもう片方を使った辺、つまり使用済みの辺を考えてしまい1WA。上の議論において $e_1\rightarrow e_2'$ の道と $e_2\rightarrow e_1'$ の道に共通する強連結成分があると、途中で混ざってしまい $e_1\rightarrow e_1'$ を辿ってしまうかもしれないので、ちゃんと一度使った辺を弾く必要がある。逆にこれ以外の場合では壊れない。ペアの片方の辺がどこかの強連結成分に含まれるなら、もう一方の辺も別の、あるいは同じ強連結成分に含まれるから。

9問目が34分1ペナで-27pt、10問目が79分1ペナで-68pt、合計-95pt。10問目はかなりやりごたえがあって面白かった。9問目が本当にわからないので、日曜日深夜のTLを注視したい。

6月中旬～7月中旬の新刊ラノベをチェックして注文した。15冊。06/17発売予定の富士見ファンタジア文庫の新刊が、どれも書籍注文サイトに表示されず、予約できなかった。1件ヒットと書いてあるのに一覧が空だったりして謎。そのうちリアル書店で買うか、機を見て再度注文したい。

午前6時くらいから日記を書き始め、YouTubeを見つつ午前10時に書き終えた。文章量がそれなりにあったので時間がかかったのもまあ納得できる。見ていた動画の一つはこれ↓。先週日曜日に見たカバンチェックと同じく大喜利企画だが、こちらはあまり面白く感じられなかった。8分17秒時点、「酒を呑ませて酔わせて倒す」と言われ即座に「なんで八岐大蛇と同じなんだ」と突っ込めるのはすごいと思う。見ていてびっくりした。

www.youtube.com

https://www.youtube.com/watch?v=WtSwAAOpZl0&t=497s

チャンネル登録者数500人を達成した。しばらく450人手前で停滞していて、そこから3本動画を出して一気に到達。Twitterアカウントの規模が大きめなので、そこから誘導することでインプレッション数が稼げている。

チャンネル登録者数500人！ありがと～ pic.twitter.com/3L9xCUmzVM
— こたつがめ (@kotatsugame_t) 2022年6月15日

競プロ実況と銘打っているが、決して解説ではなく、ただコンテスト上位に入る人間がどのような速度で解いているのか見せたいという考えで動画を作っている。だから「動画を見て憧れた・モチベが上がった」という感想を見たときは非常に嬉しくなったし、「理解する前に先に進んでいった」という感想に対してはすまないがそういう動画だとしか言えない。幸い僕がTwitterでエゴサする範囲では動画は好意的に受け止められているものの、YouTubeというプラットフォーム上で何かフィードバックがあったわけではない。動画とTwitterにおける個人が切り離されているように感じていて、自分の影響が及ばないものの評価を見守っている心境で少し怖い。

学食で食事。ちゃんとレジで宣言して納豆2パックを購入してきた。このメニューを選ぶのはもうこれで何度目かわからないくらいで、今日は合計606円になるはずがなっていないことに気づいて会計漏れを指摘した。

食事 pic.twitter.com/BwYQvWzg3N
— こたつがめ (@kotatsugame_t) 2022年6月15日

帰宅して布団に横たわり、またYouTubeなりにじさんじ非公式wikiなりで無為に過ごしてしまった。wikiはアンジュ・カトリーナさん。動画は以下の切り抜き。

www.youtube.com

午後1時前に就寝。

06/15(水)

午後4時直前に起床。即座に会議に接続してペアプログラミングを始めた。

序盤はだいぶ頭が回っていなくて反応が鈍かったと思うが、どちらかというと前回（06/03）のペアプログラミングの記憶がほとんど抜けてしまっていたのが問題だった。意識も記憶も回復したので何とか普通に進んでいって、最後、コードが正しく動くか確認しながらしばらく雑談さえ挟み2時間程度で終了。今書いたコードで学習を回し始め、しばらく見守って問題ないことを確かめてから二度寝した。

午前0時半起床。相変わらず学習はちゃんと動いているようでよかった。同じPCでちょっとYouTubeでも見ようかとしたらGPUのメモリがギリギリになったので、慌てて会議アプリだったりSlackだったりを落とした。こういうの、一度起動するとバックグラウンドで一生走り続けるのであまり好きではない。通知を送る以上仕方ないことではあるのだろうが、それは別のPCかスマホから見るので十分なので、毎回手動で落としている。

ハーメルンに気を取られつつ明日、日付が変わったので今日に控えたセミナーの準備をする。もう何回同じページ予習するんだという感じなので、あまり気が乗らなかった。また証明を再現して、今回は万が一にも炎上しないようメモとかではなく丸々書いた紙を用意しておいた。どうせ念入りにやっていたらあまり進まないということが分かっているので、量は控えめ。ハーメルンとセミナー準備を体感2対1くらいで行って、午前7時前には切り上げて布団に入った。そこからさらにハーメルンを読んで午前8時就寝。

06/16(木)

午後2時過ぎ起床。火曜日に投稿したCF #799の実況動画だが、順位が確定していたのでサムネイルを作って設定した。上に二つあった灰色・無色のアカウントが両方消えて8位に上がっていた。

ちょっと遅めの時間に出発し、生協でパンやおにぎりを買って教室へ。おにぎりだけ食べてすぐセミナー開始。今日は僕の発表だと思っていたが、実際はもう一人と時間を半々に分け合う予定だったらしく、さらにその人の発表が長引いて今日は聞いているだけになった。

岡目八目とはよく言ったもので、証明の簡単そうな別方針だったり黒板に書かれていることの反例だったりがいくつか思い浮かんで指摘したりした。そういうことをする立場は気楽だが、指摘される側はたまったものではないのだろうなとも思う。自分も昔黒板発表で炎上して頭が真っ白になった経験がある。先生からもいろいろ指摘を受けていて、今日はとにかく大変そうだった。これについては途中から先生が発表者の発言を遮りがちだったのも問題に思える。

ただ自分自身をネガティブに言い続けるのは、聞いていてこちらの気も滅入ってしまう……自分で自分を信じられなくなったら終わりですよ。

学食で一緒に食事し、別れて帰宅。ふぁぼん氏が氏の食生活についてブログを書かれていた。僕の「ペペロンチーノの作り方」のオマージュらしい。ところで、オマージュとリスペクトは大体同じ意味のようだが、自分で自分のブログ記事がリスペクトされていると言うのは語感からして尊大すぎるので、ここではオマージュという語彙を選択した。

yuyusuki.hatenablog.com

kotatsugame.hatenablog.com

親が大量にパスタソースを購入してくれるのでそれしか使わなくなったり、茹でる前のお湯でインスタント味噌汁を作ってそれを飲むため普通に2分以上待てるようになったり、いろいろ変化があります
— こたつがめ (@kotatsugame_t) 2022年6月16日

でもあなたが食事をしている間にライバルが競技プログラミングの問題を解いているのは変わりませんね
— こたつがめ (@kotatsugame_t) 2022年6月16日

そもそもライバルとして見定めている人はいないのだった。さらに競技プログラミングの問題もあまり解かなくなってしまった……。

シャワーを浴びて午後8時くらいには布団に入った。少しハーメルンを読んで午後9時くらいに仮眠に入り、午後11時過ぎに何とか起床した。午後11時半からCF #800 div.1。

Dashboard - Codeforces Round #800 (Div. 1) - Codeforces

Aは $i\rightarrow i+1$ の操作と $i+1\rightarrow i$ の操作が同じ回数だけ行われるので、それによる影響を前または後ろから順に見ることで操作回数を決定していける。僕は後ろから見た。操作回数が負になる場合と、途中で $0$ になる場合、つじつまが合わない場合がアウト。Bは葉から順に自分の子に流せる値の最大値を求め、それが $l$ 未満なら $r$ に、 $r$ より大でも $r$ にするということを繰り返すのが最適。 $l$ 未満から $r$ にするときに操作回数が $1$ 増える。

Cはよくわからない。単純にdpしようとすると、 $u$ に対して $u\rightarrow v$ なる辺を見て $dp_v+1$ を求め、各値に対してそれより大きな値に繋がっていた辺をすべて削除するときのコストを足したものの最小値が $dp_u$ になる。ただしループがあるのが問題。単に頂点 $1$ からDFSして、ループを検出した場合dpの値を $\infty$ にするようなコードを書いたら落ちた。そこで逆に頂点 $n$ からdijkstraのように求めることを考えた。 $dp_{v_0}$ が決定したとき、 $u\rightarrow v_0$ に対して $dp_u$ を、 $dp_{v_0}+1$ に「まだ使っていない $u\rightarrow v$ の本数」を足したもので更新できる。なぜなら、今dijkstraをしているので、まだ使っていない $u\rightarrow v$ について $dp_v\ge dp_{v_0}$ が成り立ち、足した値が先ほどの「それより大きな値に繋がっていた辺をすべて削除するときのコスト」に相当するからである。これで通った。未だに最初のコードの何が悪かったのかわかっていない。

ここまで26分。残り1時間半はDで詰まって椅子を温めていた。まったく良い性質が見つからない。実験などを経て先頭から増加列・減少列を適当な規則に従って貪欲に更新することで判定は行えるとわかったので、その二つの列を上手いこと更新して尺取りのようなことができないか考え、できずに終了した。3完速解きで77位、レートは2906→2875(-31)。

火曜日にラノベを予約した時表示されなかった商品が表示されるようになっていたので、改めて注文した。7冊。

またしばらくYouTubeを見ていた。以下の動画。以前剣持刀也さんの話術について日記に書いたことがあったが、やはり屁理屈が上手い人として認識されていたらしい。また7分24秒時点の「天変地異」は遊戯王のカード名の意味で取ると話が繋がりそう。お互いデッキを逆さにしてプレイするという大胆なカード。

www.youtube.com

https://youtu.be/ZN1MBVAWqPw?t=444

ラストでスタッフを煙に巻くシーンがあって、急に入社日マウントを取り始めるのが本当に好き。話題とは一切関係ないことをすぐに持ち出せる発想力がすごい。22分27秒時点。 https://www.youtube.com/watch?v=KwxIJYdRl3s&t=1347s
週記（2022/06/06-2022/06/12） - kotatsugameの日記

ハーメルンを1作読了。「この手のひらで踊れたのなら」。超然とした主人公が好み。しかしどうやら体を勝手に操られていたらしいということが明らかになってきて、かなり不穏な気配が漂っている。

syosetu.org

GCJ Tシャツに関するメールが届いていたので注文し、それから日記を書き始めた。かなり長い時間をハーメルンに吸い取られてしまい、この部分まで書き終わったのが午前10時。メールを見たら、ABC253の賞金が届いていた。この回は全体3位、日本人2位で、優秀賞と基礎科学研究奨励賞（数学専攻のため）で合計18万円。当然これまでもらった額では一番大きい。正直現実味がない。

1時間弱で全完したコンテストで18万円稼いだ。これまでの人生で最も時給が高かった瞬間らしいです
— こたつがめ (@kotatsugame_t) 2022年6月17日

三└(┐卍^o^)卍ドゥルルル pic.twitter.com/1bjtsdYDes
— こたつがめ (@kotatsugame_t) 2022年6月17日

競プロしててお金もらえるのマジで夢あるな。AtCoderとスポンサー各社に感謝
— こたつがめ (@kotatsugame_t) 2022年6月17日

いったん布団に入るもあまり眠れる気がしない。眠気はあるが目が冴えている。再度起きて少しおすすめのなろう小説まとめを書き進めた後、午後1時前後に一瞬出かけた。学食で食事し、購買でラノベや菓子パンを購入し、原付に給油してきた。帰宅して布団に入り、ハーメルンやYouTubeで時間を溶かして午後4時就寝。

www.youtube.com

見ていた動画はこれ↑。最初、花畑チャイカさんの演技のみの切り抜きを見て、とんでもなく面白かったので他の人のも全部見た。結局彼のものが一番面白く感じられたので、それについては字幕が付いた切り抜き動画のほうを下に貼っておこう。他の人のもそれぞれで良かった。社築さんの「俺がついてるだろ」は自分でも知っているくらいの、音ゲーマーの間では有名なネタ。つまり内輪ノリの一種に感じられて、それを知らないだろう他のVtuberの反応が聞いていて辛かった。変な笑いが出てきたので、そういう面白さもあったということか。そもそも面白さを競う企画ではないのだが……。

www.youtube.com

06/17(金)

午後11時過ぎ起床。ICPCのチームが組まれていて、登録した情報が足りないというエラーが出ていた。Companyの欄を、特に必要とも書かれていないのに埋めなければならないらしい。Noneと書いておいた。

ブックマークしている小説の作者さんが別作品を書かれたそうなので、読んだ。5話完結でさっくり。特に好きではなかった。ノクターンノベルズなのでリンク先R18。

https://novel18.syosetu.com/n6221hr/

そのあとは朝までずっとおすすめのなろう小説まとめを書き進めていた。ちょっと読み返してみたり、読了当時の日記を見たりして何とかコメントを捻り出していたので、数時間かけて10作品分しか書き進められなかった。かなりの難事業。今日は読み返しのつもりで熱中するようなことはなかったが、その代わりうっかり捜索掲示板を漁り始めたりランキングを見たりして、最終的には別のハーメルンを読み進めつつ書く状態になっていた。

午前9時半就寝。

06/18(土)

午後3時前に目を覚ました。ハーメルンを読みつつ冷凍弁当の配達を待つ。

まず1作読了。「貴方は中央トレセン学園から追放されることを希望しています。」。

syosetu.org

悪印象を与えようとして取った行動が好意的に受け止められてしまう勘違いもの。トレーナーが主人公のウマ娘二次創作としては、口調が乱暴だったのが印象的。たいていは丁寧であるか、そこまでいかずとも愛想がないだけのことが多かったはず。話の設定上自然とは言え、正直良い気分はしなかった。

話は、主人公視点で数話進んだ後、そこで発生した勘違いの経緯を周囲の人物視点で1話描くことによって説明する、というのを繰り返す構造になっている。自分の知る範囲では目新しくて良かった。個人的には周囲の人物からの評価をもっとネットリ記述するようなものが好みだが、こうやってテンポよく新しい勘違いが発生し続けるのも読みやすくてよかった。

午後4時半ごろに弁当を受け取り、さらにハーメルンを読み続けてもう1作読了。「追放系お嬢様」。この2作は最近並行して読み進めていて、ちょうど同時期に最新話まで追いついたということ。

syosetu.org

「輝きたくて」の作者の新作。勘違いもの。前作でも被虐願望のあるTS転生者を描いていたが、今回の性的嗜好はもっと悪化していた。正直ついていけない。勘違いの内容についても今のところ特に印象に残ったものはない。ただ、なぜ勘違いされてしまうのかの理由が明らかにされたときは、なるほどと思った。前作では途中から主人公に対する評価が自分の中で変わった記憶があるので、今作もそんな感じの展開があることを願う。

午後5時半ごろに二度寝。そこからなかなか起きられず、午後8時半に何とか布団から出た。食事してすぐABC256。

Tokio Marine & Nichido Fire Insurance Programming Contest 2022（AtCoder Beginner Contest 256) - AtCoder

Aはやるだけ。dcの4Bを9秒時点で提出してFAを逃し、直後にbcの2Bが存在することに気づいた。もうダメダメ。そこからはC++。Bは何を言っているのかよくわからなかったので、言われた通りに書いた。Cは左上 $2\times 2$ を全探索。Dは $L_i$ でソートして先頭からマージできるならしていく。Eは $i\rightarrow X_i$ と辿っていくとループに辿り着くので、それぞれのループ内で最も小さい $C$ だけ答えに足せばよい。同じループを2回以上数えないように注意。

Fは面倒。 $C$ を等差数列を区間加算できる遅延セグメント木で管理して、区間和で $D$ を求めた。Gは $N$ 角形の頂点を一周しつつ、頂点の色と各辺上にある白い石の個数を持つdpを考えて、後者は互いに関係がないことに気づき、前者だけで行列累乗した。ただしこの考察の流れから、 $2\times 2$ 行列の各要素を長さ $D+2$ のベクトルにして、ベクトル同士の加算乗算を要素ごとに行うような方針を取ってしまい、実装にちょっと苦労した。各辺上の白い石の個数を先に決め打ったほうが明らかに楽。

Exは同じ値になった区間をマージすればあまり種類数が増えなさそう（未証明）だったので、それをmapを使って実装する。ただし区間和の取得は難しいので、区間setと区間和取得が行える遅延セグメント木も用意して、適宜書き換えた。3125ms。

ノーペナ全完で16位。Eの解説を読んで、これまでfunctional graphという言葉を誤用していたことに気づいた。正しくはすべての頂点の出次数が $1$ の有向グラフであるようだが、自分は加えて入次数も $1$ であるようなものだけそう呼んでいた。日記におけるこれの出現を調べると、全部順列をグラフに直したときの表現だった。入次数が $1$ であることに着目しないとグラフ全体がいくつかのループに分割されることが言えないので、functional graphだからループに分けて云々みたいな説明が意味をなさなくなってしまう。では入次数も $1$ のグラフはどう呼べばよいのか？適切な表現を知らず直すのが面倒なので、放置。

午後11時半からCF #801 div.2に出た。レジったページを開きっぱなしにしていたら時計の誤差が積み重なり、ページ上のカウントダウンが残り10秒を切ったぐらいでリロードしたらもうコンテストが始まっていてびっくりした。

Dashboard - Codeforces Round #801 (Div. 2) and EPIC Institute of Technology Round - Codeforces

Aは最大値のマスを必ず含むような縦幅・横幅を考える。最大値が $A_{i_mj_m}$ だったとすると答えは $\max(i_m,n-i_m+1)\times\max(j_m,m-j_m+1)$ になる。Bは $n$ が奇数なら $a_1$ を $0$ にすることで先手勝ち、そうでない場合は二人とも取る山が同じなので、 $1$ 個ずつ取っていったとき初めてなくなる山、つまり $a$ の最小値と等しい最も先頭の山がどちらのプレイヤーに対応するか調べる。何を考えたか総和の大小を比較して1WA。Cはbitsetでdp。

D1は、一つ必ず聞く頂点を決め、そこを根とした根付き木を考える。子を二つ以上持つ頂点について、その子らはそれより下の頂点を聞かないと区別できない。よって各頂点に対し、部分木の頂点を全部区別するために必要な聞く頂点の個数を求める木dpが考えられる。dpの値がちょうど $0$ の子、つまりそれ以下の頂点を一切聞かなくてよいような子、が二つ以上あった場合にそのうち一つ以外を追加で聞く必要がある。そしてこのdpは、各頂点の値が隣接する頂点の値だけから計算できるので、全方位木dpに書き換えられる。

先にD2に提出し、通るのを確認してD1にも出した。D2の点数のほうが低いのでこうすべきだと考えたが、冷静になって考えてみると、間違っていた場合のリサブのペナが定数であるのに対し、時間による点数の減衰は元の点数に比例するので、ちゃんとD1から出したほうが良かったらしい。何なら全方位木dpに書き換えるのに手間取ったので、 $O(n^2)$ が書けた時点でD1を提出するべきだった。

Eはちょっと面白い。二人が置いたドミノをマスを結ぶ辺だと思うと、全体はいくつかの長さ4以上の偶閉路に分けられる。ここでドミノをマスではなく値を結ぶ辺だと思い、各辺を2回ずつ使っていくつかの長さ4以上の偶閉路に分割できれば、縦 $2$ マスのマス目に置くだけで盤面と二人のドミノの配置を決定できる。ただし片方の人だけが同じドミノを2回使ってはいけないことに注意。これで偶閉路にうまく分割する問題になった。

ひとまず、連結成分ごとにすべての辺を2回ずつ使って一つの偶閉路が構築できる。具体的には、適当な全域木を取って辺属性オイラーツアーのように並べ、余った辺はどちらかの端点にいる際に往復すればよい。このようにして作った偶閉路（を適当な位置で切り開いた列）について、それぞれ二本ずつ含まれる同じ辺の出現位置の偶奇は異なるため、そこから決めたドミノの配置で片方の人だけが同じドミノを2回使うことはない。長さに関する条件は、辺を一本しか含まないような連結成分でなければ満たされる。dfs木を取って実装した。多重辺や自己ループの扱いが難しい。

あとは復元。二人のドミノの配置を作るのがちょっと面倒だった。まあジャッジのためには仕方ないか。うっかり1ペナ付けつつ全完、システスも全部通って11位。

ABCのコードゴルフをする。Aは速度で負け。Bは全完後に考えると後ろからの累積和が $4$ 以上であるような要素の個数だと分かったので、dcで実装して17B解を作ったものの、まったく同じコードがコンテスト開始すぐに提出されていてひっくり返った。朝方になって-1Bできた。CはAWK。 $2\times 2$ マスの全探索の最中にうまくループの範囲を調節することで、確認すべき条件を減らしている。DもAWK。imos法。EはRuby。すでに通った頂点を検出するまでfunctional graphをたどり続け、今のループで通った頂点が見つかったらその部分が初めて見るループなので、答えを求めて足す。以降は手付かず。

日記を書き、しばらくYouTubeを見てから布団に入った。実は布団に入ってからもYouTubeを見ていた。午前9時半就寝。

06/19(日)

午後0時半くらいにうっかり目を覚ましてしまった。

今日のOpenCupが開催されるのかわからないとツイートしたところ、Telegramで情報が得られると教えてもらった。というかOpenCupに招待されたときにちゃんとそのリンクが貼られた文章が共有されていたようだ。全然見ていなかった。

今日のOpenCupはあるのかい！代理コンテストなのかい！どっちなんだい！

ん〜〜〜〜〜〜パワー
— こたつがめ (@kotatsugame_t) 2022年6月19日

そこを見て、この時間になっても特に更新がないことを確認。今日は代理コンテストになりそう。午後9時からのARCに被せないため午後4時から5hで参加しませんかとチームメイトに聞いてみると、了承・同意が得られたので、そうなった。というかこの時間に連絡つくのは感動。コンテスト直前まで起きられず寝起きで5hに突入するのって僕だけらしいです。

明らかに寝足りないので午後4時直前まで二度寝するぞと思って再度布団に横たわるも、なぜか眠れない。午後3時くらいまで布団で身悶えして、仕方なく起き上がった。今日は睡眠時間3時間で5h+2h+3hに挑む。

まず、午後4時からOpenCup代理コンテスト。コンテストタイトルはPTZ 2022 Winter Day 6 (ICPC Camp Day 1)であった。チームでGHICAの5完で、担当したのはAだけ。それも未証明で通したので、解法をあまり真面目に書く気がない。

06/21追記：https://www.acmicpc.net/category/detail/3056

頂点数 $N$ で辺数が $2NK$ 本以上の無向グラフから適当な頂点集合を重ならないように二つ取り出して、それぞれの集合のすべての頂点がもう一方の頂点集合に隣接する頂点を $K+1$ 個以上持つようにせよという問題。Diestel Graph TheoryのTheorem 1.4.3が「平均次数 $4K$ 以上のグラフは点連結度が $K+1$ 以上の部分グラフを持つ」という主張なので、この証明を追えば解けると思って結構長い間粘着した。結局点連結度は何の役にも立たなくて、次数が $2K$ 以下の頂点を削除していくことで次数 $2K+1$ 以上の頂点のみからなる $2K+2$ 頂点以上の部分グラフが得られることだけが分かった。

しかしこれは当然の話。次数が $2K$ 以下の頂点を削除しているのだから最小次数が $2K+1$ 以上になるのは当たり前、次数が $2K+1$ の頂点が存在すればそれ自身を含め頂点数が $2K+2$ 個以上になるのも当たり前。頂点 $1$ 個と辺を高々 $2K$ 個組にして削除しているので、常に平均次数が上がり続けるのだから、グラフは空にならない。今年のGCJ R3では平均次数が小さい状態が保たれていたが、それとは逆向きの評価を行っている。見覚えのある議論だと思っていたらProp 1.2.2に全く同じことが書かれていた。

以上がとりあえず正しいとわかっていること。あとは、残っているグラフの頂点を二つに分割して隣接する頂点の個数に関する条件を満たせばよい。頂点集合を $A$ と $B$ として、最初全部 $B$ に入れておいてどんどん $A$ に移すという操作を行った。操作後に $B$ の各頂点がそれぞれ $A$ に隣接する頂点を $K+1$ 個以上持つようにはできたので、 $A$ でも同様の条件を同時に満たすため $A$ と $B$ を入れ替えて同じことを何度も繰り返すというコードを書いたら通った。

残りの問題は何もわからない。Jの考察に参加して、チームメイトがそれっぽい解法の実装に入ってからは完全に集中力が切れていた。さすがに数時間椅子を温め続けると厳しい気持ちになる。

直後、午後9時からARC142。

AtCoder Regular Contest 142 - AtCoder

Aは $K$ を反転しても小さくならないことを確認し、 $N$ 以下の範囲内で $K$ またはそれを反転したものの末尾に $0$ を加え続け、カウントする。 $K$ が回文である場合に注意。Bは連番で埋めた後、奇数行→偶数行の順で並べるだけでよい。

Cは $3\le u\le N$ に対して $d_{1,u}+d_{2,u}$ を求め、これが $k$ であるような $u$ の個数がちょうど $k-1$ 個となる最小の $k$ がだいたい答え。ただし $d_{1,2}=1$ である場合が問題。このとき、全ての $u$ に対して $|d_{1,u}-d_{2,u}|=1$ なので、まずこれをチェックしておく。この判定に通るのに $d_{1,2}\gt 1$ となる場合は、 $N=4$ で1-3-4-2のような並びをしている場合しかないと思って、これを特別扱いしたら通った。出力形式ミスで1ペナ、コーナーケースの処理をミスして1ペナ。

Dは面倒。良い操作はそれを戻すこともできるので、操作の度に初期状態と1回操作後の状態を繰り返すかチェックすればよい。操作の際に移動した駒を元に辺を向き付けると、互いに重ならない長さ2以上の有向パスがいくつかできて、各有向パスではもともと終点以外のすべての頂点に駒があったことになる。逆に、木をこのような有向パスに分解して今述べたように駒を置くことで、良い操作が可能な駒の置き方を全部生成できる。

あとは操作を2回繰り返したときに元に戻る、つまり2回目の操作に対応する有向パスが必ず1回目を反転したものになるという条件について。まず、駒がない頂点が隣接してはならないので、パスは木の頂点すべてをカバーしている必要がある。さらにパス同士の位置関係について丁寧に考えると、パスの内部の点に別のパスの端点が隣接してはならないこと、パスの始点が隣接しないこと、パスの終点が隣接しないことを満たしていれば良さそうだと分かった。

木dpをする。部分木について、その内部を条件を満たすように有向パスに分解する方法を数え上げる。これを根の状態を解説通り五つに分けてそれぞれで持ち、気合いで遷移を書く。細かい説明は放棄する。子全部を見るループを7回書いたが定数倍的には余裕だった。精神的には全然余裕ではない。しばらくの間上に挙げた三条件のうち一番目を見落としており、サンプル3だけが全然合わずかなり絶望した。何とか合わせて提出し、WAで、端点の隣接関係を勘違いしていたところを書き直してAC。

残り20分くらいでEへ。フローだと決め打ってグラフをエスパーしようとし、失敗。諦めモードになりつつしばらく考察していた。魔法使い $i$ について、その強さ $a_i$ は $L_i=b_i$ 以上であるか、または $R_i=\max_{\exists(i,y)}b_y$ （ペア $(i,y)$ が存在するような $y$ を渡る最大値）以上である必要がある。とりあえずこのどちらかを満たすまで強さを増やしておく。さて、この状態でまだ良いペアになっていない二人の魔法使いについて、片方は $L\le a\lt R$ であり、もう片方は $L\gt a\ge R$ である。よってこのようなペアに辺を張ると、出来上がったグラフは二部グラフになる。

適当に塗り分けて連結成分ごとにどちらかの色だけ条件を満たすように増やすとよいのではないかと思い、実装してラスト1分で投げて当然のように落ちた。後からケースを確認すると、prefixが05_maximalのケースだけ全部落ちていて面白かった。まあそれが30ケースあるので惜しくもなんともない。

4完。やはりDから難しかったようで、26位になっていた。Cは実は嘘解法だった。 $N\gt 4$ の場合でも上で無理やり弾いたのと同様のケースが発生してしまう。

C、
5
1 5
5 3
3 2
5 4
で落ちる人居ないのかなぁ
— ひゅ〜Men (@men_cotton) 2022年6月19日

午後11時半からCodeChef。June Lunchtime 2022 div.1。

https://www.codechef.com/LTIME109A

1問目の問題IDはもともとLOSTARRAYだった。開いて、10分弱かけてコーディングまで済ませたのだが、提出ページが開けなかった。慌ててコンテストトップに戻りページをリロードしたところ問題が消え去っていた。キレそう。ただ他の問題のACがほとんど出ておらず、みんな同じ現象に遭遇していたことが伺えたので、そこだけは救いだった。とりあえずツイートでキレ散らかしておく。

インド、問題が消えとる。ふざけるのもいい加減にしろよ
— こたつがめ (@kotatsugame_t) 2022年6月19日

後になってLOSTARRAY_というIDの問題が追加され、コンテストが10分延長された。コンテスト中に問題が消えたり増えたりするdiv.1 rated（結局ratedだった！）って景気がよすぎるだろ。頭お花畑か？絶対語り継いでやるからな。どうやら、古い問題とIDが被ってしまって、意図せずそちらの問題が表示されてしまっていたようだ。

以下解いた順に。MAXCYCSHIFTは累積XORの（多重）集合の変化が「要素を一つ削除する」「削除した要素を全体にXORする」「新しく一つ値を追加する」の3手で書ける。よって集合全体にXORされた値を持てば削除と追加だけで再現できる。XORXORSUMは難しい。最上位桁から見るのは失敗。最下位桁から見るのがよい。最下位桁が同じ数同士で組にする必要があって、 $0$ である数は全部 $2$ で割って再帰的に解く。 $1$ である数はその次の桁が $0$ のものと $1$ のものでペアにする必要があって、2種類に分けた後全部 $4$ で割り、「二つの集合から一つずつ選んでペアにする場合の数」を求める関数を用意して解く。この関数もまた再帰関数として実装できる。

LOSTARRAY_はもともと1問目に置かれていただけあって簡単。 $N$ が奇数のときは $A$ 全体のXORが決定して、偶数の時はそもそもどれを全体のXORだと思っても適切な $A$ が復元できる。XORDETECTIVEは、まず $X=0$ を聞いて $A\oplus B$ を手に入れ、この値で立っている最上位ビットの割り当てを決定する。そこから上下に広がるように一桁ずつ決めればよい。下のほうは、 $A$ でも $B$ でも立っていないビットを $X$ で埋めることで、 $X$ による繰り上がりを $A\oplus B$ で立っているビットまで影響させることで区別できる。上のほうも考え方は同じ。問題文をよく読んでおらず、 $T$ と $Q$ をそれぞれ読み損ねて2WA。愚か。

あとは部分点。MINXORSEGはBinary Trieを必要なところだけ作るセグ木だと思って、更新する度に現在の集合に対して問題を解いた値を求めておいた。これでMo's Algorithmを実装し、小課題3までの50点。手元のランダムケースで20秒弱かかっていて満点は絶望的だが、なぜかしばらく粘着していた。16秒くらいにはなった。インデックスを持っていた部分をポインタにしたら、そのポインタが差す先が実はvectorの要素で、メモリ再確保が発生し値が壊れてしまったりした。最初に十分な量reserveしておくことで対処。

INC0XORはbitDP。小課題2までは自明、と言いつつ $2^7$ の桁まで繰り上げる必要があるケースで引っかかった。小課題3、4は逆に各桁についてどの要素を繰り上げるか全探索すると思ったのだが、答えが合わない。残り時間が少なく、何が間違っているかもわからないままコンテストが終了した。

480点で13位、レートは2761→2730(-31)。XORXORSUMは最下位桁から見ると条件を満たす相方の数がただ一つに決定するらしい。言われて考えてみれば確かにそう。最上位桁から見て列を分割していく方法を最初に考察し、最後までそれに引きずられていた。

消えてしまったLOSTARRAYのほうもコードは完成していたので通しておいた。区間に対しbitwise ANDを行う更新で条件を満たし、区間bitwise ORを求めることでちゃんと条件が達成されているかチェックできる。適当に遅延セグ木で書けそうだったが、念のためビットごとに累積和を取ったりする方法で実装した。

https://www.codechef.com/viewsolution/67201656

TCB48が終了していた。全完優勝。そもそも全完が二人しかいなかった。9完の人とあまり点差がなかったので危ないところだった。

ARCのコードゴルフ。Aは適当にPerlで書いておいた。Bはなんと $2,1,4,3,\dots$ と出力するだけで通る。ただし $N$ が奇数のとき $N^2$ と $N^2+1$ を交換しようとしてはならないことに注意。dcで21Bで書けてしまった。 $N\times N$ に整形する必要がないのはいつものことだが、それにしても行・列を完全に無視できるうえ、ここまで単純になるのはびっくり。各行について値の大きさがジグザグになっていればよさそうという考えから試した構築方法だった。残りは手付かず。

午前4時くらいから日記を書き始めたが、どうにも眠い。明日はインターン先定例会の前にもミーティングが入っていることだし、無理せず寝てしまうことにした。午前6時就寝。

2022-06-13

週記（2022/06/06-2022/06/12）

06/06(月)

先週の週記を投稿してから。午前9時過ぎに布団に入って、ちゃんと7時間くらい眠れるな～と思っていたのに、うっかりにじさんじ非公式wikiを読みふけってしまい結局就寝したのは午前11時半だった。ちなみにベルモンド・バンデラスさんと社築さんの記事を読んでいた。

午後4時起床。回していた学習の記録をグラフにプロットするなど準備をして、インターン先の定例会に臨んだ。先週はバリバリ進捗を産んだのでかなり気が軽い。ノリノリで発表した。

勉強会は先週日曜日に終了したAHC011の話。僕は結局初日に1Bの解を提出しただけ（しかも時間差で最短を取れていない）だったが、順を追って説明されることで何となくの全容を把握することはできた。印象的だったのは、「目標の全域木を作ってスライドパズルを解く」という方針を得る方法。初日のmaspyさんのスコアを1ケース当たりに直してみると、スコア関数の定義から全域木を作るのが前提の戦いだとわかるらしい。またこれはスライドパズルという問題の性質からも必要で、何故かというと目標の盤面とどれくらい離れているかでしか現在の盤面を評価できないから。なるほど確かに、解いている途中で得られた木の大きさになんて微塵の価値もない。

今日の夕方あたりにニコニコ動画の「おとわっか」が削除されてしまったらしい。ちょくちょく再生していたので寂しい気持ちになった。諸行無常。最初はヤマダ電機からのコネクトパートばっかり注目していたのだが、さすがにMADに失礼だと思って全編通して視聴するのを繰り返した結果、その前のダダダダ天使パートが好きになってきていた。

【合作】おとわっか - ニコニコ動画

ご愛顧ありがとうございました！申し訳ございませんでした！ pic.twitter.com/yvbkVb3Tua
— ラグマット (@rugsmatt) 2022年6月6日

眠気をこらえ、今日が期限の課題2つと明日期限の課題を1つ倒す。まず最初はゲーム理論。手書きだと読みづらいからWordかTeXで書けというコメントが出ていて、仕方なくWordで。思ったより戦略系ゲームの表を作るのが簡単だったのは良かった。ゲーム木を書けと言われるとまた困ってしまうが、それ以外だと圧倒的にWordのほうが良いな。そもそも図表を作成するのが面倒という先入観から手書きを好んでいたのだった。

次にハードウエア基礎論。ちょっとよくわからなくなってきた頃合いだな、と思いつつ講義スライドを眺めて、課題を開いたら特にスライドに言及のなかった計算問題ばかり並んでおり大変びっくりした。スライドではなく講義動画を視聴したらまた違うのだろうか。何とかそれっぽいことはできそうだったので、上手く空気を読んで手を動かし、何とか今回も全問正解で終えられた。Googleフォームを利用した課題なので点数が即座にわかる。

完全に集中が切れてしばらくYouTube。やはり人が喜びを爆発させているシーンは良い。音ゲーの話題ということもあって、この配信が当時のトレンドに乗っていたのを見聞きした気がする。記憶の捏造か？当時何やってたんだろうと思って日記を読み返したら、ラノベを3冊読んだ日らしかった。最近さっぱり読めてないな……。

www.youtube.com

本当はサークルの運営とかICPCに関する記録のまとめとかしなければならないことが確実にあったのだが、ラノベを3冊も読んだらたいていのことはどうでもよくなる。積読を減らしたので、今日何もしていないわけではないと自分で信じられるのが大きい。
週記（2020/11/09-2020/11/15） - kotatsugameの日記

日付が変わってから火曜日期限の課題、離散数学のものを提出した。同値関係であることの証明を3つの性質それぞれで書くのが少し面倒だった。

ありえないくらい眠い。すぐ布団に入って、少しハーメルンを読んで午前1時半に就寝。

06/07(火)

なかなかスッキリとした目覚めで、これは睡眠負債もかなり返済できたかな？と思いつつ時計を見たら午前6時半だった。明らかに睡眠時間が足りていないので一刻も早く二度寝しなければならない。なのにやたら寝起きが良く、全然眠れなかった。

しばらくYouTubeを見て、ハーメルンの更新をいくつか読んで、なろうを読んで、午後2時になってようやく二度寝。次に起きたのは午後8時だった。

またずっとなろうを読み続けて、午後11時半からCF #797 div.3。ところで最近、CFのURLをブログに埋め込むときにタイトルを表示する機能がうまく動かなくて悲しい。以前までだったら以下のリンク文字列は「Dashboard - Codeforces Round #797 (Div. 3) - Codeforces」のようになっていたはずだ。自分で書くこともできるが、面倒。

https://codeforces.com/contest/1690

Aは出力が $h_2,h_1,h_3$ の順番であることに気付くのが難しい。Bは $\max_i a_i-b_i$ 回だけ操作して達成できているかチェック。各 $i$ について、 $a_i-b_i$ 回ちょうど操作するべきか、またはそれ以上の回数なら何でもよいか決まるため、どちらにしろその $\max$ をチェックすれば事足りる。Cは直前の仕事が終わった時間を記録して前から見る。Dはさすがに自明。Eは微妙に難しくて、 $a_i\leftarrow a_i\bmod k$ とすると、ペアであって和が $k$ 以上となるものの個数を最大化する問題になる。ソートして $a_i$ が大きいほうから見て、必要最低限の値とペアにしていくのを繰り返すのが最適。

Fはいつもの置換の周期を求めるのを、ループの長さの代わりに文字列の周期を使って計算する問題。文字列の周期については長さの約数を全探索したので、最悪ケースでも $O(n\sqrt n)$ になっているはず。この問題、マルチテストケースのくせして $\sum n$ に制約がない。このことにコンテスト後になって気づき冷や汗をかいた。Gは累積 $\min$ が更新されるインデックスをsetで持って追加・削除を繰り返す。各クエリはまず $k$ がsetに入るかチェックして、入るならその後ろの要素をどこまで削除するべきか順に試していく。

全完時点で3位、その後ペナ差で抜かれて6位に落ち着いた。

PCのSSDが画面キャプチャのストックで圧迫されてきたので、悪い成績だった回やAtCoder以外のコンテストに参加した時のキャプチャを削除した。とりあえず70GBほど空けたので一安心。正直、ある程度昔のものは全部削除しても良さそうな気がしている。古いものよりは新しいものを編集するべきであるから。ああ、前にA問題のACシーンだけを集めた動画というのを考えたのを思い出した。これを作るとしたら、今日いくつか完全削除したのは失敗だったかもな。

先ほどのCFは、初めての試みとして音声も拾いつつキャプチャしていた。コンテスト開始まで少しのカットと、一部映ってはいけないものにぼかしを入れるだけの編集をサッと済ませてエンコードし、投稿。いわゆる生声実況のつもりだったが、特に問題文を翻訳して読み上げたわけでもなし、ただただ僕がボヤいているだけの動画になってしまった。これも実況であると強弁している。順位は確定後にサムネに入れておきたい。open hacking phaseで僕のコードがHackされたらどうしよう……。

www.youtube.com

本当は実況プレイと銘打つつもりだったんだけど、なんも実況してなくて「ありえね～」とか「この問題作ったの誰？」とか「助けて～」しか言っていないので残念
— こたつがめ (@kotatsugame_t) 2022年6月7日

YouTubeでにじさんじの公式番組に熱中。にじさんじ無人島シリーズを3本一気に見てしまった。演者を一切映していないのに普通に違和感なくバラエティできているのはすごい。ところどころでしか3Dモデルが使われていないから、おそらく動きだけスタジオで別撮りしたのだろう。それ以外の部分はなんと声だけで面白い動画が構成されている。サバイバルもガチ。ガチでやっているのに動画に映った部分は演者の影の映り込みもないのが本当にすごい。

www.youtube.com

しかしこうやってにじさんじの公式番組に熱中するのと、地上波のテレビ番組に熱中するのには全く違いがないように思える。僕がテレビをあまり見ない人間だったのは、つまるところ出演者に興味がなかっただけの話だったらしい。大学生になったとき、下宿先にテレビを置かないことで今後もテレビ番組から身を遠ざけようとしていたのに、今こうやってYouTubeで漁りまくるようになってしまい台無し。しかし一片の悔いなし。

朝方から日記を書き始めた。月・火のぶん。結構時間を使い、午前9時半就寝。

06/08(水)

午後4時半起床。しばらくPCを触ったりして、午後6時に家を出発した。今日はゲーセンに行く。空模様が怪しいので自転車は使えない。

家と地下鉄駅とゲーセンの位置関係を考えたとき、地下鉄に乗るのと歩き通して行くので時間的にあまり違いがないのでは？と考え、試しに歩いてみた。実際、地下鉄のタイミング次第とはいえ平均的には同じくらいの時間でゲーセンに到着できそう。今日は途中で寄り道して油そばを食べ、ATMでお金を下ろした。

午後7時から閉店までゲーセン。新曲を埋めた後、14+の新規AJを狙っていた。今日は3曲。

Grievous Lady AJ pic.twitter.com/oPBWQ1e3K6
— こたつがめ (@kotatsugame_t) 2022年6月8日

前半が苦手。特にフリック混じりのスライドとタップをそれぞれ別の手で処理するところが全然安定しなかった。焦ってリズムがうまく取れない。後半はおおむね上手で、一番最後、高速の交互から切り替わった4鍵の最後だけ結構失敗しがちという感じ。確か2敗。前半で失敗することが多くなり捨てゲーが連続して、今日は止め時かと思っていた頃合いでかみ合った。しかも最高精度。ラストのホールド・スライドの右の始点で2個出したのがちょっと残念か。まあそれがなくても9950には届いていないので、気にしてもしょうがないと割り切れている。99AJというだけで十分。

水晶世界〜Fracture〜 AJ
今日一発！ pic.twitter.com/kntnvsoVc4
— こたつがめ (@kotatsugame_t) 2022年6月8日

NEWになってすぐの頃にSSS+狙いで粘着していた運指を覚えていた。久しぶりにプレイしてみたところ、一発で何もかも上手くいった。かなり危ないところもあったなという感じなので、決め切れてよかった。今日は1-0や0-1を多く出していたし。しかし精度はあまりよくなかったと思っている。謎の赤が多かった印象。

Vallista AJ pic.twitter.com/5U0g4W44ch
— こたつがめ (@kotatsugame_t) 2022年6月8日

たった4回で決めることができた。出したのはラスクレの2トラック目。これで出なかったら最後は別の曲をプレイして終わろうと思っていたので、ギリギリ。5鍵と高速4鍵は擦って、第二発狂（と呼ばれていたはず）はノーツを増やしてトリルと読み換える。ここまでは昔組んだ運指で、他の鍵盤は見たまま押すことができた。BPMが遅めなのでかなり余裕があるが、それにしても本当に上手かった。精度も良いと感じる。赤の数的には水晶世界と変わらないとはいえ、こちらはそもそもAJが出るだけで万々歳だからか。

立ち食いそばを食べて帰宅。疲れ果ててパソコンデスクにへばりつき、いくつか動画を視聴した。

www.youtube.com

先週視聴して日記にも書いた犬山たまきさんの3D LIVEのうち、恋愛裁判カバー部分だけを抜き出した動画。好みのシーンだったが1時間超の動画の一部なのでループ再生には向かないなと思っていたところだったので、大変助かる。ただのLIVE切り抜きではなく歌動画となるように編集されており、茶番シーンがばっさりカットされていた。それもまたいいよ。

www.youtube.com

15分11秒時点。この頃渋谷駅前のスクランブル交差点にデカデカと掲示されていた、花譜さんの武道館ライブの広告が映り込んでいる。思いがけず嬉しい気持ちになった。しかしこのような、明らかに動画の主題ではないことに反応するのはちょっと申し訳ない気持ちになるな。日記には好き放題書くがツイートするかどうかはしばらく悩んだ。

www.youtube.com

懲りずにまたにじさんじの公式番組で夜を明かした。その中から1本。剣持刀也さんがロリコンロリコン言われているのはしぐれういさんの切り抜きばかり見ていた頃から知っていたが、こうやって実際に幼いアバターのVtuberに挟まれたときは普通の好青年になっていて、純粋にゲーム実況的な面白さがあった。この辺り弁えているからこその人気なんだろうなと感じた。ラストでスタッフを煙に巻くシーンがあって、急に入社日マウントを取り始めるのが本当に好き。話題とは一切関係ないことをすぐに持ち出せる発想力がすごい。22分27秒時点。

https://www.youtube.com/watch?v=KwxIJYdRl3s&t=1347s

昨日のCFのopen hacking phaseが終わっていた。全完6位のまま変わらないということで確定したので、アップした動画にサムネイルを入れた。

サムネイル作った！ pic.twitter.com/18fvQ9852R
— こたつがめ (@kotatsugame_t) 2022年6月8日

かなり眠い。日記は清書せず、今日やったことをサッとメモだけして午前5時半就寝。

06/09(木)

正午起床。昨日、にじさんじ運営会社のANYCOLORが上場したことを知った。さらなるご躍進を祈念している。

ANYCOLORが東証グロース上場、時価総額1652億円に。躍進続ける｢にじさんじ｣の魅力とは？【UPDATE】 | Business Insider Japan

準備して午後1時半に家を出る。まず学食で昼食。先週、納豆にはレジ1回につき1パックしか買えないという制限があることを知った。そこで今日は、最初に1パック買って席に置いた後、即座に戻ってもう1パック買った。納豆を見せると2回目かと確認されて、「2回目のレジだ」と答えたものの、プリペイドから引き落とされてしまった。これは納得いかないと「1回のレジで1パック」という制限であることを主張した結果、会計をやり直して、今度こそちゃんとミールカードで購入することができた。おそらく「1回のレジで1パック」という制限を「1食につき1パック」と勘違いされていたのだろう。

先週の一言カードには、日記に書いたような経緯と、納得いかないルールなのでなくしてほしいという要望を書いた。これに関する回答は次のようなものだった：「ミールカードのこのような制限は組合員の食生活を守るために設けている」「従業員間で再度ルールの確認を行う」。まず前者から、食生活を守るという目的なら何かを1食につき1個と制限するのはおかしな話ではない。しかし実際のルールの文言ではそのような制限のかけ方になっていないわけで、だのに存在しないルールを適用しようとされるのは後者ができていないことになる。1週間もあってルールの周知ができていないと見るか、まだ1週間しか経っていないと見るかは内情を知らないので何とも言えないが。

「食生活を守る」という目的を聞いて、「1回のレジ」を「1食」のことだと忖度することは可能だが、しかし僕がわざわざそのような解釈を行う必要はまったくない。もともと学食のレジ担当者はルールがガバガバなことが多く、それに甘えてきた経緯もあるので、正しくルールを適用されるなら諦めも付く。しかしより厳しいほうにルールを誤解されるのは我慢ならない。今日はそういう感じで一言カードにクレームを書いてきた。ちなみに、先ほど言っていたような忖度の話は敢えて触れていない。話が通じない人という空気を醸し出そうとしている。

一言カードを書いていたら遅くなった。午後3時開始のセミナーに少し遅れて到着。今日の前半はもう一人の発表で、教科書にあった天才的な構築について、全員で考えても結局よくわからないという結論になって終わった。もともと彼一人だけ発表する予定で、このままでは午後4時半と少し早い時間に終わりそうだったので、せっかくなら少し話したいと主張して僕も発表することに。意気揚々と黒板の前に立ったはいいが、1週間前に準備で読み返したきりの内容、しかも少し複雑な証明だったこともあり、再現するのに失敗して炎上。最終的に何とか補完できたものの、午後6時前までかかった。先週考えていたことは不正確で、十分に性質を拾い切れていなかったようだ。

午後6時に終了して帰宅。疲れ果ててなんと4時間以上YouTubeを見たりにじさんじ非公式wikiを読んだりしていた。

www.youtube.com

今日はぐんかんという、Vtuberテーマのネット小説で見たてぇてぇムーブを現実でやってしまっているにじさんじの男女コンビを発見して、一瞬で夢中になって脳を破壊されていた。実は僕「てぇてぇ」という言葉がまともな日本語と思えずあまり好きではなかったのだが、確かにこういうムーブを見せつけられると口角上がりまくってまともな語彙を失ってしまう。男女のライバーで身体的接触を行える、またそれを許容されるような関係性はさすがにフィクションにしか存在しないと思っていた。マジで最高すぎる。

セミナーの途中に先生にこういうものを作れないかと言われていたプログラムを書いてメールで送信した。行列計算や統計処理が含まれるもの。R言語で実装できないか聞かれたが、自分はそれを使えないのでOctaveで書いた。

またYouTubeに戻る。それと並行して、おすすめのなろうまとめの編集を再開した。しかしついうっかりなろうの読み返しを始めてしまい、そのまま朝まで戻ってこれなかった。馬鹿野郎。「最強魔法師の隠遁計画」は読んだのが高校生の頃で今の好みから外れたかと思っていたら全然そんなことはなく、昔好きだったシーンが今も好きであるということをずっと再確認していた。

https://ncode.syosetu.com/n5606cq/

これはまずいと一旦日記を書き始めた。日記を書きつつまたYouTubeを見てしまう。

以下の動画の51分57秒からは森中花咲さんと剣持刀也さんのデュエットでトンデモワンダーズを歌っている。これが抜群に良かった。特に剣持刀也さんの歌が上手すぎて初めて聞いたときマジでひっくり返るかと思った。配信のメインじゃないけど日記だから彼だけに言及しちゃうぞ。まず冒頭ですぐプロセカバージョンのMVと似た声をしているなと感じた。それなりに高めの声でクールに歌っているのが良い。早口の歌詞にも関わらず一音一音はっきり発音されていることからも原曲のボカロっぽさを感じられてどんどん好きになっていった。

www.youtube.com

午前11時就寝。

06/10(金)

午後10時起床。たくさん眠れて偉い。しばらくYouTubeを見てから起き上がった。

昨日先生に送信したOctaveコードについて、R言語に書き直したものが研究室の先輩から送られてきていた。読んでコメントをくれとのことだったので、一念発起しR言語の環境を整えることにした。といってもUbuntuだとapt-get install r-baseするだけだったので非常に簡単。それで実行して、確かに正しく動いているのを確認。一応一か所パフォーマンス的に嬉しくなさそうなところを指摘したものの、本質的ではないなあと自分でも思う。

午後1時半からCF #798 div.2。火曜日は失敗したURL貼り付け時のタイトル表示だが、この記事を書いているときはうまくいった。一度表示できてしまえばこちらのもの。当然火曜日の分も貼り付けなおせば表示されるが、いちいちそういう対応をするのは面倒なので、これからはその時々で貼り付けた状態をそのまま放置することにした。

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

Aから微妙に難しい気がする。 $a$ と $b$ で文字が共通しないので、貪欲に取るのが良い。Bは先頭から貪欲に埋めても最後の2つを入れ替えたりすればちゃんと条件を満たせる。Cは単純な木dp。Dは45度回転して各軸における座標の最大・最小を求め、その中央の近くを試せば十分。45度回転を戻したときにちゃんと範囲内になることは要チェックか。ちょっと怖いので各座標で試す範囲を $\pm 5$ とした。実はそもそも $n\times m$ マス全部試すのが想定解だったらしい。

Eは難しい。デクリメントがあることを完全に忘却して、まず最初の状態で連結成分を求めて、偶数をいくつか奇数にすれば全部繋げられるなと考えていた。これで1WA。デクリメントの存在を再発見し、思ったより難しいことに気づく。しばらく考えて、LSBで分類すると高々2手（ただし $0\rightarrow 1$ を除く）でよいことが分かった。LSB最大のものをデクリメントすることで、それ未満のLSBを持つ要素全部と連結にできて、残りLSBが同じものについては一つ選んでインクリメントすれば十分。よって0手か1手で達成できるか確認するという問題になって、0手は愚直に、1手はすべての $\pm 1$ を全探索して、連結性を $O((\log\max a)^2)$ で判定して解いた。判定は各bitを頂点とし、要素ごとに立っているbitたちを結ぶ辺があると見たときの連結性に言い換えられ、各bitのペアについてそれを両方含むような要素が何個存在するかカウントしておくと差分更新できる。

システスも全部通って15位。

午前3時から日記を書き始めた。昨日から日記を書いている間YouTubeでNJU歌謡祭2021をずっと流していたのだが、朝方ついに完走した。後半にあるニホンノミカタはインタビューまで含めて一つの流れだったらしく、元ネタを調べて完成度の高さに笑っていた。最初にこのアーカイブを再生した時は、知っているVtuberが歌っている部分だけ飛ばし飛ばし見ていたので、こうやって全編通して見る機会を作れたのは良かったなと思った。

www.youtube.com

後半の2時間24分19秒時点、インタビューでリゼ・ヘルエスタさんとアンジュ・カトリーナさんが決めポーズについて話している部分。この後のどこかでチャリで来たポーズを決めたいねと言っていて、もしやと思って最後のVirtual to LIVEをじっくり見てみたら見事に成功させていた。3時間14分29秒時点。これだけで目を灼かれるくらい良いな。

https://www.youtube.com/watch?v=zoynMroawZw&t=8659s

https://www.youtube.com/watch?v=zoynMroawZw&t=11669s

ハーメルンを1作読み始め、そのまま最新話までたどり着いてしまった。日記を書いていたんじゃないんですか？「幼馴染がVTuber始めたら友人Aちゃんと呼ばれるようになった件」。幼馴染がVtuberを始めて、配信で話題に挙げられるためファンに認知されてしまったという設定は似たものをカクヨムでも読んだ記憶がある。僕はそういう設定が好みなのだが、これは結構一般的な感覚なのだろう。この作品もかなり好みでエタっているのが残念。

syosetu.org

しかし結局こういう設定は「人気者と特別仲が良い自分」に対する優越感が根底にありそう。その人気者の位置に今ドキ風にVtuberをメインに据えるのも、ラノベでよく見るようにアイドルをメインに据えるのも本質的には変わりないなと考えてしまった。Vtuberとアイドルの違いは自分でもできそうと思えるかどうかだと思っていて、それを押し出した作品がより良いのか。しかし演者をメインに描こうとするとすぐ炎上だったり人間関係だったりドロドロした話になってしまいがちなので、考え物。

結局そのあとも別のハーメルンを読み始めたりしてほとんど書き進められなかった。午後0時半就寝。

06/11(土)

午後4時前に冷凍弁当を受け取った。またすぐ寝て、午後8時起床。食事してYouTubeを見て、午後9時からABC255に出た。

Aising Programming Contest 2022（AtCoder Beginner Contest 255） - AtCoder

今日はA問題の問題ページを事前に開いておいたが、すぐ短くなりそうな見た目ではなかった。以降Ex問題まで全部C++で実装。Aはよい。Bはちょっと題意を把握するのに手間取った。Cはかなり難しめ。まず $D=0$ のケースを処理し、 $D\lt 0$ を $D\gt 0$ に帰着しておく。あとは $A+Di\le X\lt A+D(i+1)$ のような不等式を解いて高々2か所チェックする。Dは自明。

Eはそれなりに難しいものの考察がスムーズに進んでかなり素早く解けた。とりあえず $A_1$ を固定して一つ良い数列を作っておけば、適当にずらすことですべての良い数列を考えたことになる。ずらすと $A_1\leftarrow A_1+x$ なら $A_2\leftarrow A_2-x$ のように交互に増減することを踏まえ、各位置についてラッキーナンバーにするときに欲しい $x$ を求めて、最も重複するものの個数を出力する。Fは $P_1$ が木の根になっていて、それの $I$ における出現位置の左右で列を分割すると左右の子の部分木に関する $I$ が得られる。この $I$ に含まれる要素は $P$ においてもまとまって出現している必要があり、その部分が $I$ に対応する $P$ になっているので、再帰的に解く。

Gは実装がつらい。考察を進めると、Grundy数は大体連番になっていて、石の数がどれかの $X$ に一致するところだけたまに変な値が出現して全体が後ろにずれるとわかる。よって全体のGrundy数は連番となっている区間に分割することで $O(M)$ 個の情報で保持できる。Grundy数のカウントを連番と変な値に分け、連番の分仮想的にカウントが $+1$ されていると見なせば、実際に $X$ に対応するGrundy数を求めるのはmapで行える。Exは座圧して区間ごとに含まれるインデックスの和を持っておくことで遅延セグ木に乗る。実が増えるのはインデックスの和の係数に対する区間加算になって、収穫は値のセット。 $N$ の制約が大きいことに気づかず、最初長さ $N$ の遅延セグ木を作ろうとしていた。

全完。Gのしょうもないミスで1WAし、順位は6位になった。

コードゴルフ。Aは冷静になるとdcで素直に書ける。コンテスト開始から1時間以上経ってようやく気付いたものの、ちゃんと開始すぐに同じコードを書かれた方がいて負け。BはRubyで、複素数のabs。Cは謎。とりあえず自分の解法をRakuで実装しておいた。Dみたいな大量に二分探索を行う問題はOctaveのlookupが強い。最近活躍する機会があまりなかったので、久しぶりに使えて気持ちいい。EはPerl。インデックスの偶奇を得るため特殊変数$|を用いているが、ゼロクリアしていないので $N$ が奇数のとき正しくない挙動をするはず。なのに通った。よくわからない。以降は手付かず。

今日のABC255もリアルタイムで実況しつつ参加していた。この録画の編集を日付が変わったあたりから始めた。発言がない部分を切り詰めるという編集スタイルを知ったので、今回はそれを試してみたい。

AviUtlに動画を読み込み少しカットしたところ、音ズレが発生してしまった。調べるとフレームレートが固定か可変かの違いによるものらしい。僕が使っているキャプチャソフトShadowPlayは可変フレームレートでしか録画できず、一方AviUtlは固定フレームレートにしか対応していないようだ。AviUtlの入力プラグインの設定を弄って再度読み込んでも変わらなかったので、動画自体を固定フレームレートにエンコードしなおすことにした。

HandBrakeというソフトをインストールして、実行。これにもしばらく時間がかかった。しかも出来上がったファイルをAviUtlに読み込ませると例外が発生してしまう。入力プラグインL-SMASH Worksを優先的に使うようにして何とか解決。しかし今度は一部の操作が異常に重くなった。先ほどのエンコードでは元のファイル2.2GBから出来上がったファイルが600MBほどで、つまり圧縮されてしまったのが問題らしい。調べると無圧縮に変換するとよいと書いてあったものの、やり方がよくわからなかったので、操作の重さに耐えつつ編集を進めることにした。

幸い動画の一部を削除するのが激重なだけで、動画の一部を別のところに移動させるのは大丈夫だったので、それを多用し削除を保留するような形で編集を進めた。先ほど述べたような編集スタイルでは大量のカットが発生するので、このことに気づかなければ待ち時間が長すぎて途中で心が折れていただろう。無言かつ画面に動きがない部分をチマチマカットし続けて何とか最後までたどり着いた。この時午前7時。本当は重要でないシーンもばっさりカットするべきだったのだろうけど、考察シーンもコーディングシーンも全部動画に残したかったので、元70分弱だった動画は結局50分強になった。このあたりゆっくり実況なら倍速をかけていたのだろうが、一応喋りながらコーディングしていたし……。

適当にBGMを設定して完成。この状態でチェックする気力がないのでとりあえず出力する。カットした部分の処理に時間がかかるようで、これには80分ほどかかった。その間はまたYouTubeを見ていた。途中でBGMをフェードアウトさせる設定を忘れたことに気づいて絶望。もう何もかも面倒になって修正しないことを決定。次に、出力された動画を再生しておかしなところがないかチェック。これは主に音だけ聞きたかったので、日記を書きながら流しておいた。

全部完了して午前10時に投稿。序盤のサクサク解いている部分だけなら結構見てもらえるのではないかと思う。全部通して見る物好きがいるかというと……毎週2万文字くらい投稿される週記を読んでくれている人がいるように、50分僕がボソボソ喋っている動画を見てくれる人も誰かいるだろう。そう、ちゃんとマイクに向かって発言することを意識しないとすぐボソボソ不明瞭な話し方になるのは改善すべきところだった。しかしそもそも生声実況の編集は音ズレなどの問題でかなり面倒であることに気づいてしまったので、今度動画を作るときはまたゆっくり実況に戻るかもしれない。

www.youtube.com

Vtuberにドハマりした結果動画で何かを表現するのに憧れを抱き、また競プロ実況に手を染めました
— こたつがめ (@kotatsugame_t) 2022年6月12日

合間に昨日から読んでいたハーメルンを1作読了。「24歳、男性。Vtuberを始めるも、女性ファンより男性ファンが多い件について。」。あまり設定が好きではないのにVtuberモノだからと何となく読み始めたら思ったより重い話が多くて、全体的に辛かった。

syosetu.org

さらにいくらか日記を書いて、午前11時半就寝。

06/12(日)

午後4時半起床。午後5時からOpenCupの代理コンテストがあるので、それまでに食事をしたい。冷凍弁当をレンチンしつつ合間の時間で機械学習のコードを書き換え実行しようしたら、案外時間がかかって弁当を食べる前にコンテストの開始時刻になってしまった。結局コンテスト中に食べた。

今日のコンテストタイトルはPKU Contest 2, PTZ Summer 2021 Day 5。今日はチームメイト一人が参加できないらしく、二人だった。思い返せばこれまで一年近く、みんな毎週参加していたのが偉すぎる気もする。結果はAEGCDの5完だった。コンテストリンクを貼っておいて、問題に対する言及は解法だけにしておこう。どういう問題だったかは以下のリンク先を参照してほしい。

https://www.acmicpc.net/category/detail/2800

Aはどんな操作でもコストが一意。Eは部分長方形の行を決め打ち、数列に関する問題に帰着する。そうすると最大値を削除して区間をマージするのを繰り返すことでソートを除き線形で解けるため、全体で $O(n^2m\log m)$ になる。うっかり数列に帰着する部分で $O(nm)$ かけてしまい1ペナ。さすがに頭が回ってなさすぎる。次にチームメイトによってGが通された。

Cは $n=1$ の場合を除いておけば、（円状に並べて）隣接する値が一致する確率を独立に求めて足し合わせることで答えになる。ここで、 $s$ の長さ $a$ について、 $f(s)=1\dots a$ のそれぞれの値を取る確率を考える。 $s$ の周期が重要になって、 $a$ の約数を昇順に $d_1,\dots,d_k$ とおくと、 $f(s)=1\dots d_1$ の確率はそれぞれ同じ、 $f(s)=d_1+1\dots d_2$ の確率はそれぞれ同じ、……となるようだ。よって、隣接する $a_i$ と $a_{i+1}$ の約数を列挙しマージすることで、各値を取る確率が同じになる区間に分けて計算すればよい。この制約のもと $k\le 128$ なので間に合う。

Dの $L$ を固定する方針だけ立てて、考察の後半と実装はチームメイトにやってもらった。定数倍に大変苦しまれている間BとFを考えて、どちらもそれっぽい解法を考えたものの正当性がわからない。残り30分でDが通ったのでBに特攻し、3ペナほど吐いて終了した。

コンテスト後にFを実装したら20分で書いたコードが一発で通った。こちらに進んでいれば完数を増やせていたらしい。 $a$ が零行列になるまで、一番上の非ゼロの行を消し、残っている中で一番左の非ゼロの列も消す。これで一つ $\vec b$ と $\vec c$ のペアが決定する。この操作を繰り返して、 $a$ が零行列になる前に $K$ が足りなくなったらダメ。逆に余った場合、二個ずつ組にして $b_1=1$ と $c_1=\pm 1$ を入れる。一つ残った場合は直前の組を少しずらして、それを打ち消すようなものを入れるのが良い。基本的にどの要素も $\pm 1$ のどちらかを選べばまた非ゼロ要素にできるので可能。基本的にと言ったので、そうでない場合をいくつか場合分けする。

まず、簡単なものとして「直前」がない場合、つまり $K=1$ かつ $a$ が最初から零行列だった場合。これは当然不可能。次に、 $p=2$ の場合はずらすと $\vec 0$ になる可能性がある。具体的には、 $\vec b$ または $\vec c$ のどの要素を選んで $\pm 1$ しても操作後に $\vec 0$ になってしまう場合。 $0\rightarrow 1$ ができることに注意すれば、このようなケースは $p=2$ に加え $n=m=1$ を満たすとわかる。この場合は最初に $a_{1,1}$ のパリティと $K$ のパリティを比較して処理しておくのが良い。

解説をいくつか読んだ。Bの $\bmod{p+q}$ で考えるという考察は見覚えがある。見るたびあまりの天才性にひっくり返っている。これこのコンテストで5番目に解かれている問題ってどういうことなんだ。Iの $N=6$ のケースはヒューリスティックに求めよと書いてあってげんなり。大きなケースのヒントではなかったらしい。そういう優しさのあるコンテストではなかったか。一方 $N=20$ のケースの構築方法はこれまた天才的だった。そもそもオートマトンである文字列が受理されないとは、遷移後に終了状態にないということであって、決して途中で遷移先がなくなったということではない。このことを勘違いしていた。

少しYouTubeを見た。実はカバンチェックがあるというのは事前に言われていたらしい。そういう企画はオモコロで見覚えがあるし、最後に謎の格言を大声で喋っているのもオモコロっぽい。面白いのでOK。確かにVtuberの演者のリアルに繋がることは徹底的に排除されるべきだから、予告なしのカバンチェックなどタブー中のタブー。

www.youtube.com

午後11時半からECR130。

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

Aはやるだけ。Bは大きいほうから $x-y+1\dots x$ 番目の和なので、ソートして累積和。Cは'a'と'c'の相対的な順序が固定されていて、間を'b'が動くと見なせる。しかし'b'だけ抜き出したりするような実装が面倒だったので、普通に先頭から合わせていった。まだ使っていない最も前にある文字を正しい位置に持ってこれるかチェックする。操作の順序は答えには影響しないはず。

Dは先頭から見て、まずその位置の文字がこれまでに出現したか判定する。出現していない場合はクエリ1で特定。出現している場合は、どの位置まで区間を広げれば今見ている位置の文字が出現するか二分探索する。普通にやると $\lceil\log_2 n\rceil$ 回かかるが、これまで出現した各文字の最も右に位置するインデックスを集めてソートしそれだけ見ることで $\lceil\log_2 26\rceil=5$ 回になる。最初の判定と合わせてクエリ2は高々 $6n$ 回で、ギリギリ制限を満たす。二分探索の条件で頭を壊してしまい1WA。

Eはかなり迷走した。同じ色で塗れる点の集合、特にサイズが2以上のものを考える。まず、同じ集合に属する点は互いに最も近い距離にある必要がある。さらに、逆に各点について最も近い距離にある点が全部その集合に入っていなければならない。以上のことから、それらの集合を全通り集めてきたとき、どの二つも共通部分を持たない。それぞれの集合について全部同じ色にするか全部バラバラの色にするかの二択になり、これを遷移として使った色数を持つdpが書ける。どの色とも同じ色で塗れない点は先に処理しておく。最後に、色数に応じてどの色を使うかの場合の数を掛けて答えになる。

Fは解けず、23位。open hacking phaseが終わっていないので暫定的な結果。Dの最初の判定も二分探索に含めることで、クエリ2を高々 $\lceil\log_2 27\rceil n=5n$ 回におさえられそう。Eのdpは謎の次元を増やしてしまい計算量が悪い。これは $n\le 100$ という制約に助けられた。さらにtypoでうまく $\bmod$ を取れていないが、こちらはギリギリ大丈夫そう。Fは2-SATらしい。

ネット小説の更新を漁っていたら午前4時になってしまった。溜めていた日記を書き始める。相変わらずYouTubeに気を取られつつ午前10時までかかってこの位置まで書き進めた。

Vtuberにハマってから明らかにPC作業の集中力が落ちている。もともと昔から作業用BGMのため常にバックグラウンドでYouTubeを開いていて、一年ほど前にモニターが5枚に増えてからは一画面をYouTubeに使うようになって常に動画が見える状態だった。これまでは曲のPVや一枚絵が表示されているだけだったそこに、今はVtuberが四六時中映っている。やるべきことに手を付けられないことを除けば、今の環境はまあ、幸せである。

一瞬外出。生協でパンやお菓子と注文していたラノベを購入して帰宅。

書いた日記を推敲していたが、問題の解法を説明する文章がどうにもうまく書けず苦しんだ。特に自然な言い方にはなっていないし、かといって曖昧さを排除できているわけでもない、中途半端な形である。ほどほどに諦めをつけ、正午を過ぎてようやく完成。

2022-06-06

週記（2022/05/30-2022/06/05）

05/30(月)

日曜日は週記を投稿してからすぐ布団に入り、少しYouTubeを見て午前9時前に寝た。

いい感じの時間に起きて少し進捗を産んでからインターン先定例会に出席しようと思って、午後2時から30分おきに目覚ましをかけていた。一応意識は取り戻すものの布団から身を起こすことができずまたすぐ寝入ってしまい、気づいた時には午後4時半になっていた。飛び起きてオンライン会議に接続。ギリギリセーフだった。

先週の進捗は、ない。集中講義だったということで許してもらえないだろうか。そもそも自分で自分を許すべきではない気もする。これまで書いたコードが今、デプロイされたことによって自分の手を離れたところで動いているはずだが、それに関するフィードバックも一切ないため本当に報告できる進捗がない。先週水曜日の日記に書いたようにキャッシュの問題でうまく使えないということもあり得るようなので、そもそも動いているのか心配である。これに関してはまたメッセージで確認の催促をしておく。

勉強会まで終えてからは、ずっと講義の課題に取り組んでいた。先週と同様に今日締め切りの課題が2つ、明日締め切りの課題が1つあって、気合を入れて全部終わらせてしまった。ゲーム理論と離散数学については特に感想もない。

ハードウエア基礎は面白かった。MOS トランジスタを用いていくつかの論理回路を作るという話で、まずNOT回路がトランジスタ2個で実現される。そして、次に作るのがNANDとNORだった。それぞれ並列・直列つなぎを用いるという自然な発想からトランジスタ4個ずつで実現されていたが、そのように素直に構成したものがANDやORではなくその反転であるという事実に衝撃を受けた。NANDのみですべての論理回路を構成できることは事実として知ってはいても、パズルの一種以上の意味はないと思っていた。案外そうでもないらしい。

さらに集中講義の課題に取り組みつつ、午後11時から1時間ほどしぐれういさんの配信を視聴していた。いわゆる赤スパが結構乱れ飛ぶ配信であったが、特に5万円のスパチャが流れたときにコメント欄が大盛り上がりだったのが印象的。1万2万出すのと5万出すのは結構違う受け取られ方をするようだ。額面が大きすぎて、自分では差に想像がついていない。

www.youtube.com

平面グラフの頂点数と辺数について、 $V\ge 3$ のとき $E\le 3V-6$ という関係が成り立つ。これを用いて、整数 $n$ であって「任意の $n$ 頂点グラフについて自身と補グラフのどちらかは非平面的」を満たすような $n$ の最小値を評価せよという問題があった。結論から言えば $n\ge 11$ が出る。では $n=10$ では自身も補グラフも平面的な例があるのかと思って、しばらく適当なグラフを作っていたのだが、すぐ $K_{3,3}$ をマイナーに持ってしまう。結局構成できずTwitterに質問を投げた。

リプライで、 $n\ge 9$ ならどちらも非平面的になることが示されていると教えてもらった。「EVERY PLANAR GRAPH WITH NINE POINTS HAS A NONPLANAR COMPLEMENT」というタイトルの論文。読むと、次数列でいろいろ場合分けして各個で示しているようだった。そちらに深入りはしないものの、 $n=8$ で両方平面的になるようなグラフがあるのならそれは構成しておきたい。適当に頂点を繋いでみると一発で見つかった。

n=8できた。目の錯覚じゃないよ pic.twitter.com/6wIuJgnwZA
— こたつがめ (@kotatsugame_t) 2022年5月30日

辺がぐにゃぐにゃしていて大変複雑なグラフに見えるが、並び替えてみると見事に綺麗な平面への埋め込みが得られた。ほかにも補グラフが孤立点を持つような構成があったりと、 $n=8$ なら適当にやってもすぐ見つかるらしい。それが $n=9$ になった瞬間全部ダメになるというのだから、驚きの事実である。

整理したらえらい綺麗になった pic.twitter.com/89yYmfoRbV
— こたつがめ (@kotatsugame_t) 2022年5月30日

午前3時くらいから集中が切れてハーメルンを読み返していた。「輝きたくて」。何度も読み返している作品だが、最近Vtuberを見るようになってまた新たな発見があった。というか、元ネタとなったVtuberをいくらか判別できるようになっていた。しかしこれ、何回読んでも面白いな……。

syosetu.org

そんなことをしていてはいけないぞということで気合を入れてページを閉じ、日記を書いてゴミを出して布団に入った。明日もミーティングがある……と思いながら少しなろうを読んで、午前8時半就寝。

05/31(火)

午後3時前に起床。準備して1時間ちょっとのミーティングへ。

ちょっと新しいことを始めることになりそう。今そちらは手が足りていないらしい。こちらとしてもデプロイを終え一段落ついた感じがするし、進捗をほぼ産めない状態が続いているから、この辺りで一つ誰かと連携して作業することでちゃんと毎週稼働するペースを作っていきたい。というか、僕自身の稼働より会社から貸与されたPCの稼働が問題で、せっかくごっついGPUを備えた物を送ってもらったのに、いつの間にか機械学習を使わないコードばかり書いてしまっていたのが気になっていた。

終えてからもちょっと考え込んでいたら、購買が閉まるギリギリの時間になっていた。原付を飛ばして駆け込み、カロリーメイトを買ってミールカードの残高を調整。そのまま夜の部が開店した学食で食事して帰宅した。購買の閉店時刻と学食夜の部の開店時刻が一致しているのは辛い。

かなり眠気があって布団に倒れこんだ。しかし眠らず、しばらくにじさんじ非公式wikiを眺めていた。今、現実のVtuber（？）を少し見るようになって、現在どのように活動しているかは何となく感じ取れる。しかし人に歴史ありということで、現在に至るまでの数年間の活動から生まれた膨大なエピソードに圧倒されていた。リンクされていた動画に飛ぶと非公開になっていたりするのも、Vtuberという存在が誕生してから経過した時間の長さを感じる要素。

人が泣いているのに弱いので、こういうシーンを説明されるとすぐ自分も涙ぐんでしまう。

youtu.be

午後9時前に起きあがって、昨日の続きで集中講義の課題に取り組み始めた。途中でICPCの参加登録が始まったので、とりあえず個人アカウントの設定を確認して、学士から修士に変更したりしておいた。

午後11時半からCF #795 div.2。

Dashboard - CodeCraft-22 and Codeforces Round 795 (Div. 2) - Codeforces

Aはよく見ると偶数か奇数のみの列になる。Bは靴のサイズの小さいほうから誰のところに行けるか考えると、サイズが同じ人たちで交換し合うしかないことがわかる。よって各サイズに2人以上いる必要があって、いる場合は適当にrotateしておけば十分。Cは各桁に対する $f(s)$ への寄与を考えると、末尾が $1$ 、先頭が $10$ 、残りは全部 $11$ であるとわかる。従って、できれば末尾に'1'を持ってきておきたい。最初にそれを試して、次に先頭に'1'を持ってこれるか試すことになる。'1'が一つしかない場合に注意。

Dは $\max$ を決め打つと使える区間がわかるので、区間の $a$ の和を最大化する。累積和を取っておけば、右からその最大値を取って左から最小値を取ると言い換えられるので、適当にデータ構造を使えば解ける。区間のマージと読み替えると線形でも解けそう。Eは区間の端点でイベントソート。区間が消えるタイミングでもっと右にある別の区間と「直接」繋がっていなければカウント、という大嘘をついて1WA。間接的につながっている場合もある。結局UFの辺を頑張って省略するのが間違いがない。ちょっと考えると、例えば赤の区間が消えるタイミングで青の区間に辺を張るとき、その時点で保持している青の区間すべてに対して辺を張っておけば、以降青の区間は最も遠くまでカバーするものだけ残しておけば十分とわかる。これで辺を張る回数が線形になって、通った。

Fはいかにも全方位木dpのような装いをしている。まず木dpを考えてみると、各頂点に対して $S$ のLCAが自分になる場合の数を求める方針が立つ。 $u$ の部分木の頂点数を $c_u$ とすると、とりあえず $\binom{c_u}{K}$ 通りあって、ここからもっと下の頂点がLCAになる場合を引く。一段下の子を考えた瞬間に完全に独立した事象となるので包除原理は必要なく、 $u$ の子 $v$ に対して $\binom{c_v}{K}$ を引くだけで求まる。こうして求めた場合の数に $c_u$ を掛けて答えに加えることになる。そして、このように一段階下の子しか見ないなら~~容易に~~（別に容易ではない）全方位木dpに書き換えられる。 $u$ から $v$ に移動するときは $u$ と $v$ の持つ値のみを注意深く修正すればよい。今いる頂点を根としたときの値を持ち続けることを意識するのがコツか。

システスは全部通って6位。Eで迷走したのが痛い。Fの全方位木dp部分はなんだかんだ更新12行・巻き戻し12行とすごい実装になってしまったが、一発で合ってくれて助かった。しかしtouristはCFのルールでtourist出しして1位を取っており、圧巻。

ハーメルンを1作読了。「ありきたりな正義」。集中を切らしすぎて課題レポートを書きながらチラチラ読み進めていた。設定は好みで、展開は今のところそこまででもない。原作前スタートだが大胆に時間を飛ばしてくれているのですぐ1巻時点まで辿り着きそう。

syosetu.org

午前9時頃までかかって、ひとまず課題となっていた設問にはすべて回答を作成できた。あとは講義の感想が求められている。先週の週記で毎日面白かったところをまとめていたので、それを引き写してくればよさそう。追加で昨日見つけた、頂点数 $8$ で自身も補グラフも平面的なものを載せておけば十分だろう。これでついに課題レポートが完成。ページ番号を振ってみたところ、実に19ページあった。スキャンの手間も無視できないサイズ。06/05期限だからと言ってギリギまで溜めていたら大変なことになっていただろう。

レポートを提出してしばらく日記を書いた後、生協に向かった。食事して、予約していたラノベを受け取り、床屋で散髪。今日は眠すぎて髪の毛に鋏を入れられている時ですら容赦なく首をグラグラさせてしまった。また、ついに200円ほど値上げしたようで、世知辛い。

帰宅して5月分の読書記録をツイートした。今月は何に時間を吸い取られていたのかわからない。なんだかラノベをうまく読み進められない時期があった気がする。文章をじっくり読んでしまってページが進まない、という感じ。適当に読むという能力も必要らしい。

5月の集計
買った：22冊
読んだ：8冊
積読：+14冊
積読（累積）：+47冊
— こたつがめ (@kotatsugame_t) 2022年6月1日

午後2時前にこれまでの日記が書きあがり、すぐ寝た。

06/01(水)

消えた。

06/02(木)

午前0時半起床。

DDCC2022の予選申し込みが始まっていたので、登録しておいた。今年は新卒枠に入れるので予選通過しやすそう。いや、去年も新卒枠だった気がしてきた。理系大学生は二度卒業するということで。

YouTubeを見ながら午後からのセミナーの準備を始めた。結構前に作ったカンペがあり、そこにメモしていない行間を再現して記憶を掘り返す、必要ならばメモを書き足す、という作業になる。それが最初に準備したときを含めてこれで3回目。さすがにここまで発表の機会が遠のくとは思っていなかった。ちゃんとメモをするべきだとわかってはいるが、しかしちょっと考えればわかると判断したからカンペに書かなかったのであって、直前に急いで準備している状態だとそんなのに紙幅を割くのは面倒だなあと考えてしまう。余裕を持って準備する必要がある。

以下、セミナー準備について話すことはないので、見ていた動画についていくつか書いておく。

www.youtube.com

昨夜、犬山たまきさんの3D LIVEが行われていたらしい。ゲストもかなり豪華。やはり動画になると、生配信より情報の密度が高くなってより面白く感じられる気がする。まあ用意するのは大変そう。いくつか特に好きなシーンがあるので、以下に列挙する。

38分26秒。「判決は……」のセリフとともにしぐれういさんの眉がキリッとするのが良すぎた。細かく表情が変わるのすごいなあ。どういうトラッキングを行っているんだろうか、あるいは手で表情を付けているのか。

https://youtu.be/Rzxdn5YT_BM?t=2306

40分50秒。「うい先生盆踊りしてる？」というコメントがあって、探して見つけた。このシーン、後ろで踊っているしぐれういさんの振り付けが確かに盆踊りのように見える。可愛すぎ。

https://youtu.be/Rzxdn5YT_BM?t=2450

またその少し後から舞元啓介さんが歌い始めるのも非常に良かった。それまでもしぐれういさんの切り抜き経由で何度も目にしていたが、火曜日に氏の非公式wikiを読んでからより直接的に興味が湧いている。

ただ↑の動画はループ再生には向かない。今日の作業用BGMはこれ↓。これまた火曜日にNJU歌謡祭2021のアーカイブをところどころ見ていて、特に気に入ったシーンのうえ探すとそこだけ切り抜いた動画が公式で上がっていたので採用。一番気に入ったのはラストのVirtual to LIVEだが、これはさすがに動画にはなっていなかった。ライブで歌っているということで、歌動画として考えれば完成度は高くはないのだろう。しかしなぜかループして聞いても全く飽きない。

www.youtube.com

朝になったので切り上げて布団に入った。午前9時就寝。

午後0時半、外から大きな音が鳴って起床。雷らしい。その後すぐ強く雨が降る音が聞こえてきて、セミナーのため山に登るのが億劫になった。午後1時半ごろに布団から出て、外を見ると案外晴れている。天気予報を確認すると、夜までは何とか天気が持ちそうな感じだったので、カッパだけ持って原付で山に登ることにした。

学食で食事。いつものように納豆を2パック購入したら、片方をプリペイドで会計された。どうやら1回のレジにつきミールカードで納豆は1パックしか買えないという制限があるらしい。確かにそういう制限の一覧を学部1年生のころに見た記憶はあるものの、それ以来4年以上通って、特に引っかかった記憶がない。こうやってルールに厳しい人と厳しくない人がいると計算が狂うので困る。しかもなぜか、ミールカードによる会計とプリペイドによる会計が分けて行われていた。それはもうレジに2回通したのと何も変わらないだろう（屁理屈も理屈である）。納得いかなかったので一言カードにクレームを書いてきた。もしこれによってルールが厳格化されるなら、ちょっと余計なことしたなという気持ちになるが、今日みたいに急にプリペイドから引き落とされるよりはマシだと僕自身は感じる。

山に登って午後3時からセミナー。今週ももう一人の人は集中講義に出席するそうなので、今日は僕と指導教員の一対一になった。用語や記号の定義はだいたいすっ飛ばしての発表にできるから、もしかしたら用意していた分で足りないかもな～と思っていたら、2時間半ほどでA4用紙に6ページ分書いたメモの1.5ページ分しか終わらなかった。これだけ進みが遅かったのは脇道に逸れまくっていたから。急に競プロの過去問の話を始めてみたり、先生に定理や証明を深堀りされたりした。僕がふ～んとしか思わなかった不等式評価のタイトさについて例を挙げて確認してみたり、やはり着眼点が違うと感じる。

川内の学食で食事し、午後6時半帰宅。50分もある↓の動画を最初から最後までしっかり見てしまった。信じられないくらい面白かった。この回のゲストは、これまでずっとナレーションを担当されていた方らしく、最終回にしてついにゲストになったようだ。そういう展開からしか摂れない栄養素は確実にあるだろう。最終回だけ見てる奴が何言ってるんだという感じだが。

www.youtube.com

49分55秒。手の形を見るに花束を持っているようだ。こういうところまで見て取れるトラッキング技術はやはり凄い。体の比率と3Dモデルの比率が微妙に合っていないのかモノを食べるときに手が口元からずれてしまっているが、それ以外は特に違和感なく体が動いている。各人が何をしているのか細かくわかるのも、ついつい動画に引き込まれてしまう理由の一つだと感じた。

https://youtu.be/CGksvc8lwm8?t=2995

午後8時半からインターン関連のコーディングを開始。明日何やらペアプログラミングをするようなので、それまでにひとまずのコードを書いて、機械学習の実験を回しておきたい。半年以上前に書いていたコードを見て記憶を蘇らせるのとググってサンプルコードを拾ってくるのを繰り返し、何とか動くコードが書けた。

適当に学習を回し始めた後、勢いづいたままこれまで書いていたコードの修正と追加実装を行った。ある2つの列を順序バラバラで最もらしくマッチングさせる必要がある。つまりは最大重み二部マッチングで、フローなら多項式時間で解けるのだが、さすがに実装が面倒だったのでとりあえずbitDPを書いておいた。列が長すぎる場合は即座に異常な値を返すようにしてあるので、とりあえず落ちることはない。実際にそのようなケースが発生してから書き直すことにしたい。結局自分の作った機能のテストなので、変な挙動をしても今のところ自分にしか影響がない。

午前4時までコーディングしていた。Excelの謎の挙動に悩まされて大変苦しかった。このように自分がただただ苦しんでいる時間も業務上必要だったと思っているので、作業の記録に含め、時給を発生させた。進捗ではなく自分の支払った労力をカウントしている。

またしばらくYouTube。レバガチャダイパンが面白かったので、アーカイブから少し見ていた。FFの友人が結構前から戌亥とこさんにハマっていたこともあり、↓の回を選択。これまで歌動画しか見たことがなくて、かっこいい声をしている方という認識だったが、普段の声の落ち着きと可愛らしさが同居している感じがかなり好みだと分かった。しぐれういさんの声はひたすらに可愛らしく、星街すいせいさんの声はハリのある強さを感じて、それぞれ普通ではない点で良さがあると思っているところ、戌亥とこさんの声はその普通さが良いとも言える。

www.youtube.com

午前7時から午前8時半まで日記を書いていた。布団に入って動画を見たりカクヨムを読んだりし、午前9時半就寝。

06/03(金)

今日のペアプログラミングは夕方からということしか決まっていなかったので、午後3時から1時間ごとに目覚ましをかけていた。すると、午後6時ちょっと過ぎの連絡に午後7時になってようやく気付くという事態に。申し訳なくなりながら起床し、食事して午後7時半から開始。

昨日回してから寝た機械学習の実験が終わっていたので、結果を報告。その後しばらく話していて、自分がoptimizerとschedulerを混同しており、片方しか設定しなかったせいでLearning Rateを一切変えないままずっと学習してしまったことに気づいた。一瞬で過学習したのも当たり前だったか。それの修正と今後の実験の方向性を確認しつつ、ライブラリの実装を読んだりしていた。通話は2時間ほどで終え、その後午後10時までコーディングを続けていた。学習を回し始めて完了。久しぶりにバリバリインターンの進捗を出せている感じがして気が軽い。

YouTubeの動画をいろいろ漁って時間を過ごし、午後11時半からCF #796 div.1に出た。

https://codeforces.com/contest/1687

Aから難しかった。最初、始点を自由に決められないと勘違いしていて、最初に右に行くか左に行くかなど考えていた。その後始点が自由であることに気づいてからも思考が固定されて、どこからどこまで往復するか全探索する方針の正当性を示そうとしていた。問題文に書いてあることをそのまま実装するとどうにも場合分けなど大変そうだったので、何か簡単な方法がないか考え、ようやく各座標を最後に通った位置だけが問題になると気づいた。直ちに $\min(n,k)$ 個の座標を一直線に移動する場合だけ考えればよいことがわかり、実装してAC。

Bは冷静になると簡単。まず $m$ 回のクエリで各辺の重みを求める。次に辺を重みでソートして、順に最小全域森に使うかどうか決める。それまでの最小全域森が分かっていれば、そこに辺を追加してみて、重みの増分が追加した辺の重みと一緒である場合だけ使用するという方法で次の最小全域森が求まる。「最大」の全域「森」というほとんど見ない概念に惑わされ、辺を並べ替えることをなかなか思いつけなかったのが反省。実装して提出したら400 Bad Request。すぐにm1のほうのサイトを開いて提出しなおしたところ、以前の提出もちゃんと処理されていたようでリサブ扱いになってしまった。最悪。

Cは難しい。 $a-b$ の累積和を $S$ とすると、区間 $[l,r]$ は $S_{l-1}=S_r$ である場合のみ使用可能となる。さて、計算量的に左端からdpっぽいことをしたい気持ちになるが、区間のオーバーラップだったり操作の順序が顕著に関係してくるのが非常に辛い。ひとまず最も左端で使う区間が $[l,r]$ だった場合を考えてみると、 $S_{l-1}=0$ は最初から成り立っていなければならず、あとはそれまでの操作によって $S_r=0$ になっている必要がある。そしてこのとき、 $l\le i\lt r$ に対して $S_i\leftarrow 0$ となるようだ。

ここで、 $S_{l-1}=S_r=0$ であるような区間しか使えないと勘違いした。この条件を満たすような区間を使うと、それに含まれる位置の $S$ が $0$ にセットされて使える区間が増え、最終的に $S$ の全要素を $0$ にできればYESと判定できる。結果的に正しかったが初期化ミスで1WAして本当に辛い。勘違いを修正する場合は、区間 $[l,r]$ を使うことが $l\le i\lt r$ に対して $S_i\leftarrow S_{l-1}=S_r$ とする操作であると捉えると、 $S$ に $0$ 以外の要素を増やす利点がないことから結局 $S_{l-1}=S_r=0$ であるような区間しか使わなくてよいことが言える。

Dも難しい。cuteな数は、実験するとある正整数 $y$ について $[y^2,(y+1)^2-y)$ の区間に入るとわかる。cuteな数の区間とそうでない数の区間は当然ながら交互に現れるが、その長さは先頭から順に $2,1,3,2,4,3,\dots$ とそれぞれで単調増加になっているようだ。ここから、 $a_1$ が属する区間を決めるとほかの数が属し得る区間が一意に定まる。つまり、 $a_1$ の条件から得られる $k$ の候補が、それ以降でcuteでない数の区間を跨げるほど幅広くないということ。

計算の際は、逆にcuteな数の区間それぞれに対しそこに属する数を集めてみる。区間 $[l,r)$ と現在の $k$ があったとき、 $a_i+k\ge r$ となるような $i$ の最小値は前計算しておけば $O(1)$ で見つけられる。 $r-(a_{i-1}+k)-1$ がその区間だけ見たとき追加で $k$ に足せる数となって、それのこれまでの最小値を求めておく。次の区間 $[l',r')$ について $a_i+k\lt l'$ となってしまうと困るので、先ほど計算した値の範囲内で $k$ を適切に増やすことで $a_i+k\ge l'$ とできるかチェックする。出現する区間の長さは $a_1$ が属すると決め打った区間以上であるため、その長さが $L$ のとき、探索する区間が $2\times 10^6/L$ 個くらいになるとわかる。よって特に工夫せず調和級数になる。

残り4分で提出。しかし通らない。焦りつついろいろ書き換え、3WAしたあたりでコンテスト終了。システス後にテストケースを見ると、 $a_1$ が属する区間の候補をちゃんと検出できていなかったことが分かった。区間 $[l,r)$ に対して $a_1\lt r$ ならば候補とすべきところ、 $a_1\le l$ という条件にしていた。最初の提出からこれだけを修正したら通ってしまい、非常に悔しい思いをした。

コンテストの結果は3完70位で2953→2906(-47)。Bのリサブ扱いとCが解けなかったのでコンテスト中かなり絶望していたが、何とか2900は残して重傷に留めた。

しばらくYouTubeを見た後、午前4時から日記を書き始めた。木曜日の途中から書き始めたのに、今ここを書いている時点で午前11時。なぜこんなに集中できなかったのか。途中かなりの時間を、YouTubeを見たりハーメルンを読んだりするのに使っていたらしい。やるべきこともやりたいことも他に無限にあるはずなのに……。

見ていた動画をまた一つ貼っておく。「トンデモワンダーズ」で検索したら以下の動画が出てきた。これも木曜日に聞いていたのと同じくライブの切り抜きらしい。しかしダンスも歌も圧倒的。ホロライブとにじさんじの何が違うのかよくわかっていなかったが、ホロライブのほうはアイドルらしくダンスレッスンなど受けているということをコメント欄で知った。

「しかし」という言葉を使ったものの、別にどちらが動画として優れているという話ではない。木曜日に聞いていたのもまだ延々ループ再生を続けていて、これは社築さんと笹木咲さんの二人が歌って踊っていることに「良さ」があるんだよな。なるほど、これが関係性のオタクというやつか……。

www.youtube.com

日記を書き上げるともう正午近く。布団に入ってからしばらくカクヨムを読んで、午後1時就寝。

06/04(土)

午後4時前に生協の冷凍弁当を受け取った。正直起きられたのは奇跡だったと思う。眠りの淵でドアチャイムの音を聞き、しばらく何の音か考えていた時間があったように思う。

その後即座に二度寝し、次、午後7時前に悪夢で飛び起きた。人を殺してしまったという夢。犯行の瞬間ではなく、その後数年単位で時間をおいてから、幸せな日常の中でふと自分が人を殺したことを思い返し、捕まったら今の暮らしが全部崩壊してしまうのだと実感して震え上がるという夢だった。夢で本当に良かった。また三度寝。

午後8時にようやく起床。食事して午後9時からABC254。

AtCoder Beginner Contest 254 - AtCoder

Aは問題名から容易に内容の想像がつく。Vimで後ろ2文字を削除する方法を考えながら開くと、入力が3桁固定だった。つまり先頭1文字を削除すればよい。削除に1B、Vimの終了に2Bの合計3Bで書ける。16秒時点で提出したものの、最速は9秒で大敗。やはり問題ページを先に開いておく必要がありそう。Bはcombinationのテーブルを作る問題だが、念のためRubyやRakuの関数を持ち出さずにC++で問題文の式を書いた。Cは $K$ 個おきに要素を取り出してソートし、全体をソートできているかチェック。

Dは数をsquare-freeになるまで割ったあと重複を数え、それぞれ2乗する。square-freeにする部分は $i=2\dots\sqrt N$ に対し $i^2$ の倍数をループで列挙する方針。見るからに速そう。もうちょっと正確に評価すると、バーゼル問題より倍数を列挙するところまでは線形になっていて、実際に割っている部分がどうなるのかは謎。Eは次数も $k$ も小さいので愚直に。Fは隣接項の差の区間 $\gcd$ を見るやつで、ただし $A_{h_1}+B_{w_1}$ とも $\gcd$ を取らなければならないのに気付かず1WA。差が全部 $0$ になる場合だけ $A_{h_1}+B_{w_1}$ を出力して満足していた。

Gは実装がヤバい。まずビルごとに区間が重なるエレベーターをマージしておく。ビルからビルへの移動がかなり自由であること、エレベーターが区間であることを考えると、わざわざ目的階から遠ざかるような移動をする必要はない。そして、前処理の時点で同じビルにいる間できるだけ $Y$ を $W$ に、 $W$ を $Y$ に近づけておくと、あとはどのビルからどのビルに移動したという情報を忘れてよくなる。すべてのエレベーターを使えると見なし、 $Y$ 階からスタートして $W$ 階より上（あるいは $Y\gt W$ なら下）まで移動できた瞬間の、使ったエレベーターの数に $1$ を足したものがビル間を移動した回数になる。

以下 $Y\lt W$ とする。最初、 $Y$ 階に対応するクエリを表す人がいるとして、下の階から順に見ていく。今 $i$ 階を見ているとしよう。まず、 $i$ 階がゴールであるようなクエリに対し、そのクエリを表す人が今どの階にいるかチェックする。ちゃんと $i$ 階より上にいれば、その人が使ったエレベーターの数を記録する。次に、 $i$ 階にいる人をエレベーターに乗せて上に運ぶ。この時選ぶエレベーターは、 $i$ 階から乗れるものであって最も上まで繋がっているものと決め打ってよい。そして、移動先にいる人と $i$ 階にいる人の集合をマージする。このとき、 $i$ 階にいる人たちの使ったエレベーターの数にそれぞれ $1$ 加えておく。

集合のマージ部分をマージテクで行いたい。集合に属するすべての値について同時にカウントを増やすのは、代わりに全体に足されている値を持っておけば可能。残る問題は、クエリ番号からそれを表す人がどの階にいるのか取得すること。どの階にいるかではなくどの集合に属しているかを持っておけばマージはできる。ただしこの際、集合を単純に階の番号をインデックスにした配列で持ちながらうっかりswapしたりすると、クエリと集合の紐づけが外れてしまう。よって、集合を持つ配列は別に用意しておき、クエリ番号からも階の番号からもその配列を参照するという実装になった。ポインタでも良かったが慣れないので配列の添え字で押し通した。階の番号は集合に紐づけておけばよい。

実装が嫌すぎる。いったん順位表を見るとExのほうが解かれていてひっくり返った。まだ時間は結構あるのでじっくり実装し、何とか完成したものを提出。しかしWA。もう完全に嫌になってExを見に行ったがよくわからなかったので戻ってきて、デバッグを始めた。単純なケースで考察ミス、例えばエレベーターをマージする前に前計算してしまった値があったり、ビル間の移動回数を数え間違いしたりしたのが見つかって、さらにクエリと集合の紐づけを修正した4回目の提出が通ってくれた。地獄のような考察も、幸い大きな破綻なく実装しきることができていたらしく、軽微な修正で通ってくれて良かった。

もう一度Exを見る。大きな数から決めたい気持ちになる。実際、最大の数が一致しているならそれらをペアにすることで全く損しないことが言える。一致していない場合、大きな方を減らすことになる。それが $A$ 由来だったなら単に $2$ で割って切り捨てればよい。 $B$ 由来だった場合、これを $2$ で割ることは $A$ の要素を $2$ 倍することに対応しているので、奇数なら即座に $-1$ を出力する。……もう解けているのではないか？優先度付きキューで適当に実装して投げたら通った。Gを通してからたった3分後であった。

全完7位。Gはダブリングらしい。完全に頭から抜け落ちていた。

直後、午後11時からGCJ2022 R3に出た。

https://codingcompetitions.withgoogle.com/codejam/round/00000000008779b4

Aはfunctional graphのループごとに塗り分けるとしてよさそうで、直感的にはループ上で隣接するものをさらに2個ずつ分けるのが嬉しいと思った。実装してローカルでテストすると、2ケース目から通らない。ここから解法ガチャを始め、いくつか全然ダメな解法を生み出した後3個ずつ分けるという方針を試したら全ケースに通った。そのまま提出してAC。正当性は謎。

Bは簡単。選ぶ区間の始点を固定して終点を数えたい。色ごとに選べる終点が高々2つの区間として表せ、全部の区間が重なっている位置の個数を数えられれば良い。後から始点をずらすことを考えれば、遅延セグメント木の区間加算で選べる終点に $1$ 加え、最終的に値が $C$ になった位置を数える方針が立つ。区間加算を行いつつ値が $C$ になった位置を数えるのは難しいが、これを「区間内の最大値の個数」と捉えると遅延セグメント木に乗る。典型。ちゃんと最大値が $C$ であることをチェックしつつ答えに加え、始点をずらす際はその位置に塗られた色の条件だけ修正すればよい。 $A_i=0$ のケースでREを吐くも2回目の提出で通った。

Cはつい先週グラフ彩色の集中講義を受けた経験がダイレクトに表れた。まず、条件は高々 $(2+4)N$ 個の「部屋 $u$ と部屋 $v$ は異なる文字でなければならない」という関係で表せる。このグラフを13彩色せよという問題になる。さて、今辺は $6N$ 本（以下）あるので、頂点の次数の和は $12N$ になる。これを $N$ 個の頂点で分け合っているので、グラフ全体の平均次数は $12$ 。平均次数は当然最小次数以上なので、つまりグラフには次数 $12$ 以下の頂点が必ず存在する。そのような頂点一つとそれに接続する辺を削除したとき、残ったグラフについて、辺は高々 $6(N-1)$ 本になっている。よって $N\leftarrow N-1$ として最初の状態に戻ったとみなせる。このように頂点を減らしていき、グラフが空に（あるいは頂点数が $13$ 個以下に）なってから逆順に戻すと、戻す頂点は常に次数が $12$ 以下なので、他の頂点の色に依らずに必ず $13$ 色のうちどれかを塗ることができる。

この平均次数を用いる議論は、閉曲面に埋め込まれたグラフの彩色数を求める問題で嫌というほど触れた。オイラーの公式を使うことで、例えば平面的グラフなら $E\le 3V-6$ が言えるので、上の議論と同様にして次数 $6$ 未満、つまり $5$ 以下の頂点が必ず存在するとわかる。したがって即座に平面的グラフが6彩色可能であることが言える。平面的グラフはさらに4彩色可能であることが知られているが、もっと種数の大きな曲面では、このような平均次数に関する評価だけで最良の彩色数を導けているということが示されたらしい。

ただし実装が下手くそ。いたるところにsetを使いまくるような実装でとりあえず提出したが、その後ランダムケースを試すと手元で50secかかっていることに気づいた。慌てて全体をvectorや優先度付きキューで書き直すと同じケースで6sec強になり、リサブした。

Dは何を考えればよいかすら全く分からず、残り1時間弱はABCのコードゴルフをしてしまった。結果はABCで30位。思ったよりdを通した人が多かった。Cで最初から高速なコードを提出できていれば、ペナ差でfinalに進めるくらいの位置だったようだ。恐る恐るリサブ前のコードを再度提出してみるとちゃんとTLEしてくれたので、決して無駄なリサブではなかった、というのは救い。僕は残りのグラフから次数最小の頂点を削除することに固執してしまったが、次数 $12$ 以下であればよいので、普通にBFSっぽく書けるらしい。

ABCのコードゴルフ。AはFAの方もちゃんと3Bで提出しており、案の定負け。Bは配列をずらして和を取るようなコードをRakuで書いた。Cは元の列とソート済みの列でインデックス $\bmod K$ ごとの値の（多重）集合が等しいか見たい。入る集合に応じて適当に係数を掛け、和を取って一致するか確かめる方針が短そう。単純にインデックス $\bmod K$ を掛けたら通った。飛んでExはheapq、Python3がTLEしたのでPyPy3。

Dは $1\le i,j\le\sqrt N$ かつ $\gcd(i,j)=1$ なものに対し $N/\max(i,j)^2$ の和を取るという方針が提出されており、美しく短かった。Octaveで書き直して最短に。しかしこれはどういう仕組みで数え上げているのだろう。見た瞬間納得した記憶があったものの、どうにも考え違いしていただけのようで、それほど簡単な話ではない。ちょっと詳しく見てみよう。

おそらく、組 $(i,j)$ をsquare-freeな数 $k$ と $x,y$ によって $(kx^2,ky^2)$ と表した時の $x,y$ について全探索しているのだろう。ただし、上の解法では $k$ がsquare-freeであると限定されておらず、一方こちらは $\gcd(x,y)=1$ である必要がない。ここがうまく対応づいていることを示そう。つまり、square-freeな $k$ による $(kx^2,ky^2)$ と、 $\gcd(x,y)=1$ なる $x,y$ による $(kx^2,ky^2)$ の間に一対一対応が存在することを見る。実は具体的に構成できて、前者の $(k,x,y)$ があったとき、 $g=\gcd(x,y)$ として $(kg^2,x/g,y/g)$ が後者の対応物になっている。逆に後者における $k$ をsquare-freeにした分を $x,y$ に押し付けると前者の組が得られて、これらは互いに逆写像の関係になっているので、よい。

別の問題のコードゴルフ。数の区間が与えられるので、それぞれ素因数分解して含まれる素数の（重複を含めた）個数が素数になっているものを数える問題。factorで素因数分解してawkで出力を整えるのを2回繰り返していたので、evalとブレース展開を使いまとめた。このテクニックは何度か挑戦した記憶があるものの実際の最短コードにはなかなかならなかったので、こうして上手くいったのがうれしい。

atcoder.jp

レバガチャダイパンのこの回が面白いとおすすめされたので視聴した。序盤のバルーンファイトですでに面白かったので満足していたら、リズム天国が始まってからが本番だった。26分14秒のところで社築さんが椅子から崩れ落ちて座面を叩きながら笑っていたのが非常に面白かった。しかしリズム天国は難しそう。夜見れなさんのプレイの何が悪いのか、動画を見ているだけではよくわからなかった。自分の耳だけでリズムを取らなければならない点はノーツがある音ゲーと明確に異なる。音ゲーゴリラの社築さんもあまりスコアが出ていなかった。

www.youtube.com

https://youtu.be/rJNcd0c0JMk?t=1574

朝までカクヨムを読んでから日記を書き始めた。土日はコンテストが盛りだくさんなので、土曜日と日曜日の間にしっかり書き進めておかないとまた月曜日の昼までかかって日記を書く羽目になる。午前10時に書き終えて布団に入り、少しYouTubeを見て午前10時半就寝。

06/05(日)

午後3時半に親からの仕送りが届いて起床。なかなかスッキリした寝起きだったのでそのまま起きていることにした。しばらくTLを眺めて時間を潰し、午後5時からOpenCup。

今日はGrand Prix of Urals。チームとしてはEDMJALBGFCKをこの順に解いて11完12位。今回のセットは簡単な問題が多かったらしく、チーム共有ドキュメントに何も書かれず即座に倒された問題もいくつかあった。僕はAとFを解いた。

Aはマス目を連結になるように塗って、面積を周長で割った値が $p/q$ と一致するようなものを構築せよという問題。実験して解いた。まずブロックが $p$ 個以上必要で、このとき周長は最大で $2p+2$ になる。面積を増やしても $p/(2p+2)$ より比率を小さくすることはできないので、これより $p/q$ が小さければ構築不可能。それ以外のケースは全部 $h\times w$ のように配置するだけで作れるのではないかと思い、PCが空いた隙を見計らって試してみた。すると比率が小さいところでかなり抜けがある。そこで $1\times w'$ のように伸ばすブロックを接続してみると、なんと全通り作れるようになった。

F。これから $n$ 日に渡って毎日一人ずつ人を働かせる。候補は $m$ 人いて、人 $i$ を $j$ 日目に働かせるときのコストが $c_{i,j}$ となっている。また、人 $i$ は連続して $a_i$ 日しか働けない。この制約のもと、かかるコストの最小値とそれを達成するような雇い方を求めよという問題。dpで解く。 $dp_{i,j}$ を「 $i$ 日目まで終え、次の日人 $j$ を働かせられない状態」の最小コストと定義する。 $i+1$ 日目に働かせる人を人 $k$ と決め打った時、それから人 $k$ を連続で働かせる日数を $1\le d\le a_k$ として $dp_{i+d,k}\leftarrow\min_{j\ne k}dp_{i,j}+\sum_{l=i+1}^{i+d}c_{k,l}$ と遷移する。

まず、値の取得は行の左右から累積 $\min$ を求めておけばよい。値の更新について、コストは累積和の形で書けるので、列ごとにみるとスライド最小値が使える。結局どちらも線形で行えるし、逆に制約が $n,m\le 1500$ なので線形で行わないと間に合わないという問題だった。復元は気合い。

他にも読んだ問題がいくつかある。Bは貪欲で通ったらしい。こういう問題は貪欲が落ちがちという意識が先行して、それで通るという嗅覚が一切働かなかった。すごい。Cは特定の数だけ取り出してそれの遷移を見ると状態数がめちゃくちゃ少ない。これは気づいてもよかった。Gは全頂点の次数が $3$ のグラフに関する問題で、何らかのグラフ理論的な背景があるのかと考えていたが、純粋に競プロ的テクニックだけで解けたようだ。Lはある関数の最大値を求める問題ではなく、値が適当な閾値を超えられるか判定せよと言われているので、その閾値を使って式変形していた。

前半で僕の貢献は終わりで、後半はIが実は愚直で通らないかなど無謀な実験をしていただけだった。

とりあえずここまでの日記を書いて、午後11時半からCodeChef。June Cook-Off 2022 div.1。

https://www.codechef.com/COOK142A

SIMPLE_XORは典型。 $(2n,2n+1)$ のXORが $1$ なので、2つ束ねて $0$ にする。

SPLITANDSUMは下のbitから見て、そこが立っている要素を数える。一つ以下ならその桁はより上に一切影響しないので無視してよい。二つ以上あった場合、和においてそのbitが立っているような連続部分列に分割できる。具体的には、偶数個だったら $1$ 個とそれ以外、奇数個だったら特に $3$ 個以上なので、 $1$ 個と $1$ 個とそれ以外。しかしWA。何度考え直してもどこが間違っているのか全然わからず、ランダムケースでもちっとも落ちないので、とりあえず出力する区間が条件を満たすかチェックするassertを入れ、また配列サイズを念のため倍にして提出した。するとAC。

これは制約違反か？と思って運営にclarを出そうとして、ページをいろいろ探しているうちに、自分の最初の提出がいつの間にかACに変わっていたことに気づいた。特に通知もなくリジャッジが行われていたらしい。20分くらい時間を無駄にしてしまい、本当にキレていた。実はトップページにアナウンスが書き足されていたようで、そこを読むとチェッカーが間違っていたのが原因と分かる。いやこんなところ見ないって。

THROWTAKEはよくわからない。そもそも前の問題に信じられないくらい時間を使ったのを引きずっており、焦ってまともに考察できていなかった。偶奇を保ったまま $C$ を $3$ 以下にしても答えは変わらないと信じ、メモ化再帰したら通った。後から試したら $1$ 以下にしてもよかったようだ。

PRFSUFDSTNCTは頑張って必要条件を探す。まず $P$ も $S$ も隣接項の差に制限がある。また $P_N=S_1$ である必要がある。以上が満たされていれば、 $A$ に出現する $P_N$ 種類の数について、それらが出現する最も左の位置の集合と最も右の位置の集合が手に入る。これらをうまくマッチングさせる問題になりそう。とりあえず、集合の共通部分はそこに唯一出現する要素が入ることで確定する。残りはソートして先頭からマッチングさせていくのが最適で、区間の左右の大小関係が正しいことを確かめておく。

実はまだ足りない。 $P=\{1,1,1,2,2\}$ 、 $S=\{2,2,1,1,1\}$ の場合を考えると、マッチングまではうまくいくものの、真ん中に入れられる要素が存在しないことがわかる。つまり、上のマッチングで得られた区間に含まれないような位置があってはいけない。そういう位置は、左右でそれぞれマッチングが完結してしまっているので、今からペアを入れ替えたところでどうにもならない。よってチェックだけ行えばよく、いもす法で実装した。

一時50位台に落ちて絶望していたものの、ここまで解いた時点で10位台に戻ってきたのでまあ助かったかなという気持ちになって少し落ち着いた。

PERMSEGMENTSは難しい。挿入dpっぽいことをしたくなるが、隣り合うという関係が重要なので、（連続）部分列を作ってマージしていくという方針にした。小さい値から順に挿入していき、今持っている部分列はその直後に必ず一個以上、より大きな数を入れると定めておく。こうすることで値の挿入時に持っている部分列の個数がそのままその位置を含むような区間の個数となるため、条件のチェックができる。ただし、末尾に来る要素の取り扱いに注意。これのせいで区間の重なりのチェックが壊れるとまずい。よって、そのような部分列が存在するということを示すフラグをdpの次元に追加する実装になった。

値を挿入する際の方法は、前後に今ある部分列を入れるか入れないかで $2\times 2$ 通りあるので、それぞれ遷移を書き下した。この辺りは気合いでガチャガチャするしかない。前に部分列を入れて後ろに部分列を入れない遷移の際は、今挿入した値だけそこを含む区間が一つ増えてしまうことに注意。例えば $2$ の前に $[1]$ を繋げて、次に直後に $3$ を入れると、 $2$ を含む区間が二個になっている。末尾に持ってくる部分列のチェックは、重なった区間の個数が条件を満たさなくなった瞬間に持っている部分列のどれか一つを末尾に固定して何とか回避するような実装をしたが、今整理して考えてみれば値を挿入するごとに末尾にするかどうか決めるほうがわかりやすい。コンテスト中の実装で重複が省けているのは結構非自明に見える。

MAXMINUSMINは実験。適当に回してみるとそのうち同じ値が2連続で出てきそうだったので、 $A=B\gg C$ の場合にどういう遷移をするか手計算して、8ステップで似た形に戻ってきたのでそこをスキップする実装を行った。これでランダムケースに十分高速に答えられていたので、提出。しかしTLE。ここで、 $0\dots 10^{18}$ から一様に取って $A,B,C$ としていたランダムケースを、それぞれ $10^6$ 以下、 $10^{12}$ 以下、 $10^{18}$ 以下と決めるようにしたら、ちゃんとめちゃくちゃ遅いケースが見つかった。 $A,B\gg C$ になったあたりで時間がかかっていたので、 $A\ge B\ge A-C\gg C$ の場合を同様に手計算。するとこちらも8ステップで戻ってきて、先ほどのケースを含んでいることに気づいた。これを実装すると新しく作ったケースも高速になったので提出。自信はほとんどなかったが、通った。

6完6位で2708→2761(+53)。highestには1足りない。過去の自分が強すぎる。しかしリジャッジがあったが、このくらいのミスなら平気な顔してratedにするというのはすごいな。

社築さんが初のオリジナル楽曲を投稿されたので、今日はこれを作業用BGMにしていた。かなり良い。サイバー感のある歌声に編集されているのが好き。

www.youtube.com

午前5時前に日記を書き上げてからは、おすすめのなろう小説まとめを作成していた。↓の記事に追記する形でもよかったが、やはり時間の経過とともに過去の作品に対する印象が薄れてきて、今はそれほど心惹かれない作品も多く載っている。よって新しく記事を立てることにした。ただしここ1年で読んだ作品だけでなく、古い記事からもいくつか特におすすめしたいものを抜き出して載せる。わかりにくくなるとしてもオールタイム・ベストという体裁は保っておきたい。新しく増えたものだけ知りたい場合は各自で集合の引き算を行ってほしい。

進捗は、載せる作品の選定を終えて、各作品にコメントをつけている途中。それぞれ一言、自分が好きなところを書き留めている。参考にと読み始めて止まらなくなったりして、思うように進まなかった。

kotatsugame.hatenablog.com

午前9時を回ったので寝ることにする。

06/27(月)

06/28(火)

06/29(水)

06/30(木)

07/01(金)

07/02(土)

07/03(日)

C問題

D問題

E問題

F問題

G問題

コンテスト終了

06/20(月)

06/21(火)

06/22(水)

06/23(木)

06/24(金)

06/25(土)

06/26(日)

増えたやつ

影の勇者の再冒険 ～～Re-Tale of the Brave～～

剣姫転生 〜エルフの娘は世界最強の剣士を目指す〜

SAOを真面目に攻略しない人々

ウマ娘 ワールドダービー 凱旋門レギュ『4:25:00』 ミホノブルボンチャート

ソードアート・オンライン ラフコフ完全勝利チャートRTA 2年8ヶ月10日11時間45分14秒(WR)

もこたん→青ニート←その他大勢

正体不明の妖怪(になった男)、情緒不安定な百獣の腹心になる

ヒエヒエの実を食べた少女の話

じゃしんに愛され過ぎて夜しか眠れない

黄金の経験値

万魔殿の主〜胡散臭いトレーナーとウマ娘たちは日本を驚かせたい

Vtuberってめんどくせえ！

自作3Dモデルの素材を宣伝するためにVtuberになったら予想外に人気出てしまった

プレイしていたゲームの能力で転生するやつ

秋宮ゆららは青を喰む

Vの者！～挨拶はこんばん山月！～

アラサーがVtuberになった話。

蓬莱山輝夜お嬢様がコナンの世界入りした話

阿礼狂いに生まれた少年のお話

天地神明の真祖龍

帝征のヒーローアカデミア

クラップスタナーは２度鳴る。

銃と私、あるいは触手と暗殺

俺は竈の女神様

デート・ア・ライブ 士道リバーション

俺の家が幻想郷

続投

アイドルの世界に転生したようです。

この〇〇のない世界で

青空よりアイドルへ

最強カップルのイチャイチャＶＲＭＭＯライフ

打撃系鬼っ娘が征く配信道！

逆行転生したおじさん、性別も逆転したけどバーチャルYouTuberの親分をめざす！

輝きたくて

俺は星間国家の悪徳領主！

プニキとはじめるリーグ運営 ～野球ゲーム？作って運営します～

始まりの魔法使い

滅竜山くんの一生 ～46億歳、全ての生命と魔の祖～

東方遺骸王

少女(仮)の生活

東方狐答録

天才最弱魔物使いは帰還したい ～最強の従者と引き離されて、見知らぬ地に飛ばされました～

陰の実力者になりたくて！

最強魔法師の隠遁計画

サイレント・ウィッチ

うちの脳内コンピューターが俺を勝たせようとしてくる

Game of Vampire

比企谷八幡 「・・・もう一度会いたかった」

06/13(月)

06/14(火)

06/15(水)

06/16(木)

06/17(金)

06/18(土)

06/19(日)

06/06(月)

06/07(火)

06/08(水)

06/09(木)

影の勇者の再冒険　～～Re-Tale of the Brave～～

剣姫転生　〜エルフの娘は世界最強の剣士を目指す〜

ウマ娘　ワールドダービー　凱旋門レギュ『4:25:00』　ミホノブルボンチャート

ソードアート・オンライン　ラフコフ完全勝利チャートRTA　2年8ヶ月10日11時間45分14秒(WR)

デート・ア・ライブ　士道リバーション

プニキとはじめるリーグ運営　～野球ゲーム？作って運営します～

滅竜山くんの一生　～46億歳、全ての生命と魔の祖～

天才最弱魔物使いは帰還したい　～最強の従者と引き離されて、見知らぬ地に飛ばされました～

比企谷八幡　「・・・もう一度会いたかった」