10/03(月)

午後4時半起床。インターン先定例会が始まっている。飛び起きてオンライン会議に接続した。

先週の進捗は金曜日に産んだ分だけ。小さなタスクをちぎっては投げ、ちぎっては投げと、かなり楽しい期間である。ただし投げてから次にちぎるまでの間で毎回1週間休んでいる。

勉強会はHTTP通信について。原理などの説明があって、最後にコードを書いて実行していた。しかしほとんどのサイトではHTTPで通信するとHTTPSにリダイレクトされてしまうようだ。それはさておき、このリダイレクトというのは実はHTTPステータスコードで表現されており、サイト側ではなく我々通信を試みる側が対処する必要がある状態である、というのにびっくりした。ブラウザを使っているばかりでは、このことは全く意識できない。

午後6時半終了。思ったより早く終わったので学食に行って夕食を摂った。帰宅して先週の週記に取り掛かり、午後10時半ごろ一通り文章が出来上がる。読み返しはまだしていないが、そこまで含めると日付が変わる前には終わらないだろうと考え、先に投稿しておくことにした。

9000ACを突破していた。今年初めは8000弱だったらしい。10か月で1000問、1日3問強のペースと考えられるが、実際は「アルゴリズムと数学　演習問題集」で100問嵩増ししていたりする。

Solved By kotatsugame
Topcoder: 148
Codeforces: 2022
AtCoder: 4017
AOJ: 1322
yukicoder: 1469
library-checker: 25
Sum: 9003
https://t.co/0nO54qH8aU

9000超えてる～
— こたつがめ (@kotatsugame_t) 2022年10月3日

AIでコードを生成する新たなサービスがリリースされ、話題になっている。以下のツイートが面白かった。魔法のようなサービスに見えるのに、実際は入力に特定のコマンドをくっつけて汎用AIに渡しているだけらしい？真偽のほどはわからないが、だとするとアイディア一発でこういうサービスに仕立て上げられるのは夢がある。一方で、こういう自然言語の自由度を利用したインジェクションへの対処は非常に難しそう。画像AIがやっているように、コマンドではなく出力物をチェックするしかないのだろうか。

AI Programmer

pic.twitter.com/gEoRuzbkeD
— Masaki Hara (@qnighy) 2022年10月3日

30分ほど床で寝てしまったりしつつ、日付が変わってから週記の校閲を始めて午前2時半ごろに完了した。それから朝までかけてラノベを3冊読んだ。

「王様のプロポーズ」3巻。前半のギャグシーンは面白いが今の気分からは微妙に外れているな……と思ってなおざりに読んでしまったものの、ラストはちゃんとバトルしていて良かった。主人公が活躍してくれてうれしい。本のそでにあったコメントで、鬼と炎モチーフの妹が「デート・ア・ライブ」と被っていることに気づいた。色の印象が青と赤で全く違うため、似ているという感覚はない。

「ランジェリーガールをお気に召すまま」1巻、2巻。面白かった。ランジェリーという全く新しい題材を扱いながらちゃんとラブコメしていて良い。主人公が鈍感気味なのも好み。ストーリーの都合上全編お色気シーンみたいになっていて、脈絡なくそういう描写が挟まるより受け入れやすいなと思った。ただ表紙イラストから思い切り下着なので、ちょっと買いにくさは感じてしまう。恥を忍んでこれからも大学生協で買うだろうが。

ちょうど読み終わったくらいでTLにyukicoderのテスター依頼が流れてきたので、引き受けてしばらく取り組んでいた。一通り終わらせ、ゴミを出して布団に入ったのが午前9時。ハーメルンの捜索掲示板を漁って新しいなろうに手を出した。2時間くらい読んで就寝。

10/04(火)

午後7時ごろ起床。先週金曜日に参加したDMOJのコンテストの期間が終了していた。ここに感想を書いておく。

DMOPC '22 September Contest - DMOJ: Modern Online Judge

P1は $A_1\lt A_2\gt A_3\dots$ と $A_1\gt A_2\lt A_3\dots$ を両方試す。忘れた要素は極端に小さな・大きな値で埋めておけば問題ないので、忘れていない要素が隣り合っている位置のみチェックすればよい。

P2は二人に被せる帽子の色を全探索する。あらかじめ二人からそれぞれBFSすることで、各人についてその人の帽子を交換で持ってくるための手数を求めておける。色ごとに集計し、交換回数が少ないものから二つ保存しておけば、それを用いて答えが求まる。

P3は面白かった。4人を選んだとき、その間にどのような「非」友人関係があれば条件を満たすか全列挙してみると、長さ3のループまたは長さ3のパスがあればよいことが分かった。なのでその個数を数えたい。ループを数えるのは難しいが、これも構わず長さ3のパスだとみなすことで可能になる。個数は0かどうか以外問題ではないので、長さ3のループを3回数えていても全く問題ないのだ。

つまり、次数が2以上の頂点を結ぶ辺を数え上げればよい。真面目に計算する必要があるのは次数が1と2の間で変化する場合だけなので十分高速。隣接リストをsetで管理した。

P4は少し手間取った。単純なdfs全探索で二つ目の部分点まで通ったが、満点解法は全く別の方針。各カードについて、引いたとき右から何番目に挿入されたかがわかる。一番右に挿入されたカードであって最後に引いたものは、十中八九 $K$ のカードだろう。十中八九というのはただの四字熟語であって、本当は $1-\left(\frac{K-1}K\right)^N$ の確率でそうなる。

さらに右から2番目に挿入されたカードで最後に引いたものもほぼほぼ $K$ 。これを用いて $K$ らしきカードを確定させていける。求める場所に挿入されたカードがなくなるか、あってもこれまで確定させたカードより先に引いていれば終わりにする。すると、残ったカードだけ用いることで $K\leftarrow K-1$ としても全く同じことができる。これを繰り返せばよい。 $K$ のカードを引き切ってから $K-1$ のカードが初出現したりすると壊れるが、 $N=100$ でそんなことはそうそうないだろう。

P5は解けず、しばらく粘ってからP6に進んだ。まず、 $a\le b$ のクエリは常に達成可能だから、最後にやることにして無視。その後 $s$ の値の降順に見ていく。 $s=N$ なるクエリを $b$ の昇順にソートしてみると、最小の $b_i$ が $A_N$ 以上で、またそれに対応する $a_i$ は次に小さい $b_j$ 以下で……というような条件が得られる。

このもとで $s=N-1$ のクエリについて考えたい。先ほど $A_N\le b_i\lt a_i\le b_j\lt\dots$ という列を得たが、このうち $[A_N,b_i)$ や $[a_i,b_j)$ の部分にはまだ受け入れる余裕がある。つまり、 $A_{N-1}$ とのswapで $v$ になったとき、 $a_i\lt v\lt b_j$ ならば適切なタイミングで操作を実行することでこれまでの状態を壊さずに $A_N=a_i$ をゲットできる。

ここからはエスパー気味。受け入れ余裕のある区間をsetで持って頑張ってみたがWAだったので、その余裕も数値として保存しておくことにした。実装を簡略化すると、最初に $[A_i,\infty)$ という区間を区間ADDで追加し、またクエリの度に $[b_i,a_i)$ をデクリメントして負にならないかチェックしたら通った。正直よくわかっていない。

何はともあれ5完。今日確定した結果は全体5位で、レートは2666→2825(+159)と大きく伸びてくれた。当然highest。

布団に横になったまま10時間ほどなろうを読んで、午前5時過ぎに寝落ちしたらしい。

10/05(水)

午前8時前に目を覚ました。かなり眠いがなろうを読むのが止められない。この日は午前8時～午後3時半、午後5時～午後8時、日付が変わって午前1時～午前6時とずっとなろうを読んでいたらしい。微妙に空いた間は寝落ちしていた時間である。

10/06(木)

午前9時半に目を覚ました。布団で二度寝する代わりに1時間ほどなろうを読んでから外出。今日は大学でセミナーとTAの予定。

今週やろうと思っていたことが全くできていないので、どうしても外出しなければならなかった今日でいろいろ終わらせておきたい。まずバイク屋まで歩いて、木曜日から点検で預けたままになっていた原付を受け取ってきた。それに乗って大学に行き、ラノベを購入し、床屋で散髪。

ここでいったん帰宅し、シャワーを浴びて着替えた。切った髪の毛に首筋をチクチクされたままで過ごすのは耐え難い。再度大学に向かい、購買で買ったパンを昼食として午後1時からセミナー。

今日は3時間を半々に分けて二人発表する予定だったが、博士課程の方の発表のみになった。前回に引き続き定理の証明。必要な事実のうちいくつかは紹介されるにとどまったが、簡単な部分は我々も手を動かしてみよと先生に言われた。忘れ去った線形代数にしてやられ続け、大変なことになってしまった。

正則な行列 $A$ と $B$ について、 ${\rm rank}(A-B)={\rm rank}(A^{-1}-B^{-1})$ となる。これがわからず苦労していたが、なんと $A^{-1}-B^{-1}$ に左右から $A$ と $B$ を掛けるだけで示せてしまうらしい。 $A(A^{-1}-B^{-1})B=B-A$ で、正則行列を掛けても ${\rm rank}$ が変わらないこと、符号の違いは無視してよいことから従う。

その後教室を移動して5限のTA。このため、今日のセミナーは山の上ではなく川内キャンパスで行っていた。

今日は最初に自己紹介した後は普通に授業を受けていただけだった。そもそもTAとは最前列に座っているものなのか？人数が少なく、また今年から始まった講義なので、どういう立ち位置にいればいいのかがよくわからない。自分なりのアシストのつもりで、これからの講義に関する取り決めにあたって粗を潰す質問をしたりしてみたが、これも先生と馴れ合っているだけに見えるのかもしれないと考えてしまう。

授業後、先生の所に質問に来られた方が自身のPCにPOV-Rayをインストールするのを見守っていた。午後6時半くらいに完了して学食へ。夕食を摂った後、そのままゲーセンに行くことにした。

アプデで消える要素の回収のため、それまでに2回くらいはゲーセンに行っておきたい。
週記（2022/09/26-2022/10/02） - kotatsugameの日記

アプデで消える要素のうち楽曲削除に伴って取得できなくなる称号を回収。アップデートの度に有志が作るリストとにらめっこしながら2時間くらいかけて完了した。金の曲名称号とマッチングを要求するものは残っているが、そこまで集める気はない。

消える称号集めた pic.twitter.com/ivHC7KZcKC
— こたつがめ (@kotatsugame_t) 2022年10月6日

残り時間は手元を撮りながらX7124のSSSを狙っていた。しかし実際のところ、終盤が下手くそすぎて噛み合い待ちのレベルですらない。運指をちゃんと組まなければならない。

X7124 11-2 手元 pic.twitter.com/QLCz1585lW
— こたつがめ (@kotatsugame_t) 2022年10月6日

あとは理論値を2譜面出した。閉店まで遊んだ後、立ち食いそばを食べて帰宅。手元動画をツイートしたりメールをチェックしたりTUPCのテスター作業っぽいことをしたりして、午前2時半に布団に入った。そこから3時間なろうを読んで寝落ち。

10/07(金)

午前9時半起床。TLで面白い切り抜きが流れてきた。1回聞いてもわからないが2回聞くとわかる。ちゃんと動画で2回流されているのがありがたい。あまりにもマッチしていて最高だった。

「笑い声がトルコ行進曲」の女#月ノ美兎 #にじさんじ https://t.co/DHNDKUnVAN pic.twitter.com/EeVdnKOhPb
— 月ノ美兎切り抜きch (@mitopi_love) 2022年10月6日

ABC270の賞金、10万円分のアマギフが届いた。

全完3位、日本人2位で賞金10万円。
週記（2022/09/19-2022/09/25） - kotatsugameの日記

5時間ほどなろうを読んでいた。布団から脱出し、30分ほどインターン関連のコーディングをして、午後3時から1on1。

30分の間に思ったより進捗を産めなかったため、今日は特に話すこともないなあと思っていたら、その辛うじて産んだはずの進捗すら正しくない始末。ただし原因を探るとライブラリの噛み合わせの悪さに行き当たって、これは自分一人では解決できなかっただろうなという気持ちになった。そういう意味では、ろくにコーディングが進まないまま1on1に突入したのは実は幸運だったのだろうか。

終わってから外出。まず生協に行ってラノベ購入。実は09/27に出荷メールが届いた本の入荷メールが届いていない。発売日は09/30なのでその問題ではなく、同時に出荷メールが届いた他の本はすでに購入してあるので、輸送の問題でもない。そのうち届くだろうと楽観視していたが、発売から1週間経ち、さすがにこちらから何かアクションを起こすべきではないかと考え、店員に確認してみた。

なんと店の棚に並べられていた。その本だけ自分が予約したという印が外れていたらしい。見つかってよかったとニコニコしながら会計してきたが、やはり不特定多数の人の手に触れたということでちょっと気になってしまう。この件から得るべき教訓は、入荷メールを信用するべきではないということ。実は入荷メールは生協側が手動でチェックして送信しているらしいのだ。やはり人は間違える生き物。

競プロサークルが活動する教室へ向かう。上のようなゴタゴタがあって少し遅刻しながらバチャに参加した。後ろから解いたら最初の問題でかなり詰まってしまった。

https://kenkoooo.com/atcoder/#/contest/show/0290894f-f978-40e7-a718-69075354c6e3

終了後は感想戦、それに加えてTUPCの作問の話も飛び出て結構な長丁場になった。終わったのが午後7時半で、ギリギリ学食が閉店してしまっているので、そのまま帰宅。

午後8時から3時間ほど仮眠を取り、シャワーを浴びてCF combinedに出た。

Dashboard - Dytechlab Cup 2022 - Codeforces

Aはちょっと面倒。文字をカウントし、それを削りながら先頭からできるだけMEXを大きくしていく。このとき、最大のMEXを達成するために必要な文字以外の文字、つまり $n/k$ 文字のうち残りの文字のことを考えないのが楽。最後に余っているものを割り振ればよいし、そもそもそこを真面目に構築する必要はない。

Bは $r$ 以下の個数から $l-1$ 以下の個数を引いて求める。 $r$ についてだけ述べよう。 $\lfloor\sqrt x\rfloor=n$ となるような数 $n^2\le x\lt(n+1)^2$ のうち $n$ の倍数であるものは、 $n^2$ 、 $n(n+1)$ 、 $n(n+2)$ の三つ。これは $n$ によらないため、 $r$ 以下の個数を求めるに当たって $1\le n\lt\lfloor\sqrt r\rfloor$ に対する個数は簡単に求まる。それ以外は愚直に三つそれぞれ $r$ 以下か判定。

Cは大変。手で実験すると、初期状態のL字を保ちながら2マスずつ移動することができるらしい。ただコーナーケースとして、L字が盤面の角にあるとどうしようもない。この場合はそのL字から縦横に盤面の端を沿うマスにだけ辿り着ける。実装の際は、盤面を90度回転させ続けて特定の向きのL字にしか反応しないようしたため、その後が少しだけやりやすくなったと感じる。

Dは辺の端点を辺に沿って動かせると解釈する。答えとなるパスに辺が2本以上含まれるなら、そのうち連続する2本に対し1手かけて1本にしても損しないため、最終的には $1$ と $n$ を直接辺で繋いで通るだけになる。このとき使う辺を全探索。入力に自己ループがないので操作の途中でも自己ループを作ってはならないと思い込んでしまい、しばらく考え込んでいた。

実際はそんな制約はないので、単に使う辺の端点をそれぞれ $1$ と $n$ に持っていくまでかかる手数 $+1$ を辺のコストに掛けたものが答え。二つの端点をそれぞれ独立に持っていくか、どこか1点に片方だけ持っていき、1手かけて自己ループを作ってから持っていくかという方法がある。あらかじめワーシャルフロイドで頂点間の移動にかかる手数を求めておき、辺ごとに $O(n)$ かけて最小の手数を求めた。

Eは結構すぐに正解の方針にたどり着いたのに、合わせるのに時間がかかった。蟻の向きを $R\dots RL$ という形の連続部分列たちに分解すると、まずこれが合体して一つの蟻となり、さらに左から順にマージされていくことになる。この元で、それぞれの蟻に対し、その蟻がそれより左の蟻を全部吸収できる場合の数を求める。まず自分自身が右端の蟻であるか $L$ である必要があり、また自分を含む $R\dots RL$ の長さがそれより左にある蟻の数以上でなければならない。自由度を数えて2べきで求まる。

あとは右から順に、自分より右の蟻に吸収される場合を引いていく。自分も $L$ なので、先ほど述べた十分な長さの $R\dots RL$ に自分が引っかからないほど遠くにある蟻になら吸収されうる。ただしこの時、自分を含む $R\dots RL$ に必要な長さのせいで自由度が減っているので、その分の係数を掛けながら引く必要がある。ここで1WA。そもそも $n$ が大きいときに $i=1$ に対する答えが $0$ にならないので、提出する前に気づけてもよかった。

ここまでそれなりに時間がかかっていて順位はあまりよくない。FもGもsolved数がかなり少なく、両方読んで考えてみたが手も足も出なかった。システスは全部通って5完55位、レートは2969→2949(-20)。

そこから12時間ほどなろうを読み、午後2時前に就寝。

10/08(土)

午後4時半ごろ冷凍弁当を受け取った。また眠る前に、ちゃんとアラームをかけたかなと時計アプリを開いたら、アラーム音が小さすぎるとポップアップで怒られてしまった。ウィンドウのそれっぽい箇所をタップしたら自動で音量調整がされたらしいが、元がどんなだったか覚えていない。ちゃんと起きられるだろうかと一抹の不安を抱えながら二度寝した。

午後8時起床。とんでもない音量で飛び起きることになった。いつも耳元にスマホを置いて寝ているので直撃を食らい、しばらく心臓がドキドキしていた。音量はまた小さくしておいた。

30分ほどなろうを読んでから布団を脱出。食事して午後9時からABC272に出た。

AtCoder Beginner Contest 272 - AtCoder

Aで $N$ 個の入力を求められてびっくりした。そういうものは出ないと聞いていた気がするが、時代は進むということだろう。びっくりしただけで問題自体は普段と比べても簡単。Ruby 16B、Raku 17Bを提出しておいた。ちなみにABC-Aで可変個の入力を要求するのは実は初めてではなく、ABC022-Aという前例がある。こちらはちょっと面倒な問題。

A - Best Body

Bは愚直に判定。これを提出した後、ふとA問題に戻ってdcで書いてみたら15Bができてしまいびっくりした。Cは偶奇で分けて上位2個を取る。Dは平方根を前計算した後BFS。遷移は行を決め打つ $O(N)$ で行った。

Eはちょっと詰まった。よく見ると $[0,N)$ に収まる値以外はMEXと関係しないため、これだけ注目すればよい。 $i$ 番目の要素がその範囲に収まるのは $O(N/i)$ 回だから、全部列挙することができる。Fは $S+S+T+T$ のSuffix Arrayを計算。LCPが $N$ 以上の区間に分けて計算することで $f(S,i)=f(T,j)$ なる場合に対応した。

Gは大変。 $A_i\equiv A_j\pmod M$ なら $M\mid(A_i-A_j)$ なので、 $(i,j)$ を全探索して約数を見ることで候補は絞れる。しかし間に合うわけもなし。 $M$ として素数だけ考えることにしてもダメそう。しばらく考えて、 $A$ の全ての要素が相異なることから別の方針を考えた。 $M=p$ だったとすると、差が $p$ の倍数であるような数が $\lceil N/2\rceil$ 個存在することになる。つまり $\max A-\min A\ge(\lceil N/2\rceil-1)p$ 。一方 $\max A-\min A\le 10^9-1$ なので、 $p$ として考える必要のある値はある程度小さいのではないか。

チェックを線形時間で行うことにすると、 $N\ge 50$ もあれば十分間に合いそう。 $N\lt 50$ の場合は、最初に言っていた $(i,j)$ を全探索して $A_i-A_j$ の素因数を列挙する方針が使える。この二つを組み合わせた。しかしWA。 $p$ として見る範囲が少し小さかったので直したが、変わらず。ここで $M=4$ の場合に対応できていないことに気づいた。これを付け加える。

素数を列挙したvectorに $4$ を追加。このvectorが昇順に並んでいることを仮定した実装だったのでそれに合わせるためにsortしたら、ギリギリTLEしてひっくり返ってしまった。ちゃんと列挙のタイミングで挿入するようにしてAC。ちなみに線形時間でのチェックは、出現頻度を配列でカウントするもの。 $M$ が小さいからこそこういうことができるのであって、 $N\lt 50$ の場合はここに $\log$ をつける実装になっている。

40分残したもののExはさっぱりわからず、途中からコードゴルフに逃亡してしまった。7完36位。Gは乱択らしい。

今回のA問題について、「ABC-Aでループを使う想定解はダメなのでは」と話題になっていた。以下のツイートをうっすらと覚えていたのもあってコンテスト中にびっくりしていたのだ。まあもう5年も前の話だし、上でも書いたように時代は進むんだなあというのが一つ。またそもそも入力ですら本質的にはループを回して文字を読んでいるからして、sum関数で一発の今回も、関数内に隠蔽されているので制約を違反しているとは言えないというのが一つ。まあ、普通に考えれば前者を理由とした出題だろう。

ABCのA問題、そのレベルだと思うのだけど（というか100点問題にはループを使ってはいけないって制約が存在する）、それじゃダメなんだろうか（多分見せ方が悪い）
— chokudai(高橋直大)🐙🔥@AtCoder社長 (@chokudai) 2018年1月28日

コードゴルフ。Aはdc 15Bが提出時間で負けているうえ、後から14Bに縮みすらした。Bは面倒そうな見た目をしていたが、コンテスト中にすでにゴルフされており、特に縮みそうな隙もない。CはRuby。要素を昇順に見て、直前に出現した偶奇が同じ値との和を求め、その最大値を出力。Gは想定解通りの乱択をRubyで。約数列挙は商列挙のテクを使うと短い、が、その周りで改善があって負け。他は手付かず。

Gの改善について。Rubyではa./b+1とメソッド呼び出しの形で演算子を書くことで、この例だとb+1を引数と解釈させて括弧を省略するテクがある。つまりこう書くとa/(b+1)になるのだ。ところが、これを使う周りでいくつかの文をまとめるために()を使っている場合、そこに(b+1)を押し込むことで縮む。他にもいくつか適用できる問題があったらしく、しばらく取られたり別の改善で取り返したりしていた。

しばらくなろうを読んで午前2時からMHC R3。

Meta Hacker Cup - 2022 - Round 3

Aから難しい。最大値を持っているプレイヤーを探し、それに対して他のプレイヤーがどのような行動をするか考えることで解こうとしたのが最初の方針。例えば、最大値を持っているプレイヤーが $A1$ だった場合、他のプレイヤーは自分の持つ一番小さいカードを出すだろう。 $B1$ だった場合、 $A1$ の最大値に被せるように出すべきで、残りのプレイヤーは先ほどと同様。ただし $A2$ と $B2$ が持っていた場合の行動がよくわからない。それっぽいものをいろいろ試してみるも、validationでずっと落ち続けていた。

方針を変える。一人ずつ順番に、全部のカードを $N/4$ ゲームでどのように使うか決めることにした。まず、このままだと相手チームが得点してしまうゲームをできるだけ多く自分チームの得点に変える。次に、余ったカードで、自分チームが得点するゲームであってカードの最大値が小さいものを優先的に大きくする。いかにもそれっぽさはあるが正当性はわからない。とにかくvalidationには通ったのでそのまま提出した。コンテスト開始から1時間だった。

Aで詰まっている間に順位表をチラチラ見て察した通り、Bは簡単だった。すべてのtrie木で作れるすべての文字列に対し、それを答えに含むような三つのtrie木の選び方を数えて足し合わせる。ある文字列を表すノードが存在するtrie木は一つとは限らないので、全部vectorに持って、そのvectorを状態としてBFSする。いかにも重そうだが、BFSの過程で出現するすべてのvectorについて、その要素数の総和がノードの個数の総和で抑えられる。速度的には全く問題なく、無事提出。

また順位表を見て、D1に進んだ。とりあえずマージテクで色の変化は追えそう、では判定は……と考えて、「隣り合う二つの杭の色が同じになったタイミング」を全部求められることに気づいた。自分がどの集合にいるかを、色とは独立して代表元という形で記録しておき、マージテクで値を移動させつつ隣り合う杭と同じ集合に入ったか判定するのだ。実はこれを要求する問題をCFで見た覚えがある。探したが見つからなかった。

あとは適切な位置を飛ばして値の $\max$ を取ればよい。D2もほとんど同様に解ける。飛ばす場所が $(N-1)/K$ 箇所しかないため、 $K=1\dots N$ で和を取っても $O(N\log N)$ 。よってセグ木に乗せてチマチマ値を削除したり戻したりしつつ全体の $\max$ を計算するのが $O(N(\log N)^2)$ となって十分高速。

1時間ちょっと時間を余らせてCに進んだ。 $V$ と $W$ のペアを全探索して異なる位置をSuffix Arrayで計算する $O(NQ\log( (N+Q)L))$ の解法と、 $W$ と文字が異なる位置2か所を固定してハッシュで一致判定する $O(QL^2\log N)$ の解法が思い浮かんだので、ケースごとに軽い方を使えば解けそうだと信じて実装。しかし時間ギリギリで書きあがったのにサンプルが合わずお手上げ、そのままコンテスト終了。

出したものは全部通ってABdD、76位。Cを通せていてもペナ差でFinalには遠かった。上位200位には入ったので、Tシャツが少し特別になるのは楽しみ。Cは両方から1文字ずつ変えると考えればよいらしい。なぜ思いつかなかったのだろうか。

2時間なろうに意識を吸い取られた後、日記を書き始めた。今週は本当にずっと布団でなろうを読んでいたので何も書いていない。

1時間半ほど取り組んだところで集中力が切れ、うっかりまたなろうを開いてしまったのが運の尽き。ちょうど読んでいた章のクライマックスに入って、ただでさえ興奮しているのに急に「生配信」という自分のストライクゾーンど真ん中の設定が放り込まれて、夢中になって読み進めてしまった。「シャングリラ・フロンティア」の「謳えスカイスクレイパー：下」。この作品に今週の自由時間すべてが捧げられようとしている。

https://ncode.syosetu.com/n6169dz/

そのまま日記執筆に帰ってくることなく午後1時半就寝。

10/09(日)

午後8時起床。食事して、少し日記を書いて、午後9時からARC150に出た。

AtCoder Regular Contest 150 - AtCoder

Aは方針を間違えるとドツボにはまり込みそうな見た目をしている。連続する $K$ 文字を $N-K+1$ 通り全部試して、条件を満たす方法がただ1通りであるかチェックすることにした。連続する $K$ 文字に0を含まず、それ以外の文字に1を含まなければよいはず。0の個数と1の個数の累積輪を計算しておいて判定。提出したら通って安心した。

Bは難しかった。 $k(A+X)=B+Y$ とおけば $A+X+B+Y=(k+1)(A+X)$ となる。この値を最小化すればよい。 $Y\ge 0$ より、 $B\le k(A+X)$ を満たす整数 $k\ge 1$ と $X\ge 0$ であって $(k+1)(A+X)$ を最小にするものを探すことになる。例えば $X=0$ のとき、 $k=\lceil B/A\rceil$ とするのが最適。この値が十分小さければ、 $k$ をそれ以下の正整数として全探索することができる。では $B/A$ が大きなときは？

今度は $X$ を全探索できるようだ。 $X$ を固定して $k$ を調整し、 $B\le k(A+X)$ をギリギリで満たしたとき、 $B+A+X\le(k+1)(A+X)\lt B+2(A+X)$ となる。ここで $X=0$ を考えることで、求める値は $B+2A$ 未満だとわかる。 $X\ge A$ のとき $(k+1)(A+X)\ge B+A+X\ge B+2A$ よりそのような値はどうやっても取れないので、 $0\le X\lt A$ で全探索することになる。以上で $O(\min(A,B/A))=O(\sqrt B)$ で解け、十分高速。

Cは最初、パスが絶対に通らないといけない頂点ということで関節点のことを考えていたが、さすがに500点にこれが出るわけはないと信じて軌道修正。結局 $B$ のどの要素まで出現したかを距離とする01BFSになった。そもそも今の場合頂点に割り当てられた値に重複があり得るため、関節点に注目しても解けないはず。

Dは初手だけは良かったがその後で大失速。各頂点について、その頂点がよい頂点となるまでに選ばれる回数の期待値を求めて足し合わせることにする。これは深さだけが重要となって、深さ1の頂点は $1$ 、2の頂点は $3/2$ になるらしい。サンプル1から深さ3の頂点は $11/6$ になるべきで、この値がどのように求まるのか気づくまでに非常に時間がかかった。

自分と親の計3頂点しか考えなくてよい。その3頂点のうち自分以外の頂点が最初に選ばれる確率は $2/3$ で、そのとき残り選ばれていない2頂点を両方選ぶまでの話になるから、深さ2の頂点に対する結果 $3/2$ を流用できる。自分が選ばれた場合が問題。自分が黒であるという状態での期待値を文字で置いて遷移を考えたら解けた。

先ほどと同様、次に選ばれる頂点の深さで場合分けする。自分以外の頂点が最初に選ばれた場合、また残り2頂点を両方選ぶ話になって、ただし今回は「深さ2の頂点」かつ「自分が黒」である場合に対する結果を使うことになる。手計算すると $1$ であった。そうでない場合は同じ状態に戻ってくる。求める期待値を $E$ とおけば、 $E=2/3\times 1+1/3\times(1+E)$ より $E=3/2$ 。自分が白の場合に戻ると、結局深さ3の頂点に対する期待値は $2/3\times 3/2+1/3\times(1+E)=11/6$ と計算できて、確かにサンプル1と合致する。

深さと自分が白か黒かの状態をこのように浅いところから計算しておいて、あとは頂点の深さに対応する値を足し合わせればよい。実装は非常に短くなった。

Eはよい性質が全く見えず、4完48位。Aはやはり場合分けの方針を取ると地獄を見るらしい。Dは実は深さ $d$ の白い頂点と深さ $d+1$ の黒い頂点に対応する値が一致していて、それを用いて式を整理すれば深さ $d$ の白い頂点に対応する値が $\sum_{i=1}^d 1/i$ となった。なるほど $11/6=1+1/2+1/3$ は何回か見たはずなのだから、感づけるべきなのかもしれない。

コードゴルフはD問題のみ。Ruby。深さを計算する配列と期待値を計算する配列を分けず、常に $(d,1+1/2+\dots+1/d)$ を組にして持つとかなり短くなった。配列アクセスが長そうに見えて、結局親の値のみを参照して自分の値を決定できるため、その親の値を最初にアンパック代入すれば解決。

YouTubeを見ていた。内容はしょうもないSSなのに、それっぽいセリフをやたら上手い声真似で読み上げるので完成度だけは高くて面白すぎる。「この後のあんまり有名じゃないパート」に言及しているのも好感度が高い。スカイピースさん、というかミームの元ネタ一般に対するリスペクトが感じられる。

www.youtube.com

TUPCのテスター作業をした。木曜日の深夜の続きで、今日は実際にコードを書いた。午前2時からは日記に着手。溜めてしまった分を頑張って書きつつもしばしばなろうに気を取られていた。

午後6時、ついに読了。「シャングリラ・フロンティア〜クソゲーハンター、神ゲーに挑まんとす〜」。閲覧履歴から復元したところ、日記を書き始めてからの14時間のうち9時間くらいはなろうを読んでいたらしい。月曜日の深夜に読み始めたもので、他の日と合わせてだいたい66時間ほど費やした一気読みだった。

https://ncode.syosetu.com/n6169dz/

最高に面白かった。全体的な印象としてはやはり主人公のハイテンションさが心地よい。本編から外れて謎のゲームを始めたりしたときもだれることなく読み進められたのは、その主人公の溌剌とした様子がどこでも変わらずに見られたからだろう。以降は印象的なシーンを記録しておくので、少しネタバレ注意。

まず「見上げた空、広がる海、深淵の都市を駆けて」章のプロゲーマーと対決するところ。最高。VRMMOモノのリアル描写が好物なのに加え、真にプレイヤースキルだけの勝負で全一と渡り合う主人公の強さに感動。さらにバトルの展開も劇的だった。特に177部分は読んでいて身震いした。

次に「竜災未だ止まず、狼は吠える」章のクライマックス部分。初のPvP、しかも人前で戦うということで、これまで巨大なモンスターに挑んできたのとは全く異なるバトルが展開されて楽しい。周囲のガヤが少し描写されているのは僕の嗜好とマッチしている。このバトルに言及した掲示板回があったらもっと最高だった。

さらに「響けグレイトフルレガシー」章のプロゲーマーと対決するところ。また？と思われるかもしれないが、こちらは前に紹介したものとは趣向を変えたバトルをしつつも定期的にバトルの外側視点が入るということで、さらに最高になっていた。主人公がヤバい挙動しているのが、驚かれつつ解説されているのは良かった。非常に。

最後に「謳えスカイスクレイパー：下」章クライマックス。主人公が考察クランに対しバトル動画を共有するために生配信することになる。ただしプライベート配信ということでそれほど目立ちそうになく、ちょっとがっかり。しかし蓋を開けてみれば、配信の設定ミスでパブリックのままバトルが開始した！ベッタベタなミスだがもはや何でも良い。VRMMOと生配信が二つ揃ってまさに最強。その配信を見たいろいろな視点からの描写が続いて、これまでこの作品で摂取できていなかった栄養素を完璧に充填することができた。

それでいて、真にクライマックスのバトルに入ると外部の描写が一切取り除かれ、展開や演出の格好良さだけで魅せられた。描かれないだけでこれが配信されていることはずっと頭の中にあり、そのためこれまでとは違い主人公を画面の向こうに見ているような少し変わった没入感があって、これはこれで最高だった。ちゃんとラストに掲示板回があって、感謝の涙を流しながら舐めるように摂取した。

最後と言ったが、もう少し。本当に最後……というか最新話近くのネタバレになる。「誰そ彼の蛇」章ラストで主人公の愛用してきた装備のいくつかがプレイヤーキラーに取られてしまい、かなり気分が沈んでしまった。そのストレス展開を回収したのが833部分から835部分。命乞いを言わせておいて全く斟酌しない、それも「で？」とか「だから？」みたいな中学生のような態度ではなく、そもそも人の話を聞いていないというスタイルが最高にスカッとした。

「誰そ彼の蛇」章ラストは主人公の負けイベントだった。上に書いたような展開のほかにももう一つ悲しいことがあり、それは812部分と819部分で回収されている。こちらは手垢がついた方法での演出だったが、むしろそれくらいストレートなほうがより心にじんと響いて良い。

以上！序盤はほぼ毎日投稿の上作者のテンションによっては1日に2回3回と更新されていたのが、最近はメディアミックスでお忙しいのか更新が途絶え気味で悲しい。上のようなストレス展開がちゃんと回収されていたのは救い。そういうのを残したままエタられると数日落ち込んでしまう……。

その後も日記を書き続けていたが、眠気で頭が回らなくなってきたので、ところどころ未完成なまま午後7時就寝。