週記（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を取ってみた。以下のツイートに添付された画像において、左が初稿である。細々とした違いのほとんどが表現を少し改めた場所で、誤字はほとんどなかったはず。大きく異なっているのは文章を書き足したところで、特に日曜日の部分は急いで書いたため、改めて読んでいるうちに書き足したいことがたくさん出てきた。

ゴミを出して布団に入り、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通りの状態しかあり得ない。あとは愚直に書く。あまりにも愚直に書きすぎて106個の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

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

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

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

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

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

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

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

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

117～118、125～126小節

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

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

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

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

www.youtube.com

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

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になってしまった。昔にもそういうことがあった。以下のケース以外にも山ほど正しく計算できないケースがある、どころか正しく計算できるほうが珍しいくらい。

結局この場では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時就寝。