02/21(月)

先週は週記を投稿してから比較的すぐ布団に入り、しばらくハーメルンを読んで午前10時過ぎに就寝した。

午後3時半ごろ目覚ましで起床。ベッドから出てインターンの進捗報告スライドを作成した。先週の進捗はなんと金曜日にミーティングをしたのみ。日記に書いたようにかなり満足感のあるミーティングだったので偉いという気持ちになっていたが、稼働時間は相変わらずゴミカスである。ただ進捗報告スライドに書くことはいろいろ考えられるため、作成には苦労しなかった。インターン先定例会自体はつつがなく終了。

そこからずっとコードゴルフをしていた。今日は古めの問題をいくつか。言語アップデートが2020年の6月にあって、それから数か月のうちに提出されたコードはまだテクが成熟しきっていない感じがした。改めて粘着すれば微妙に縮む問題も散見された。特に物珍しいコードはなかったように思う。

午後11時半からFebruary Cook-Off 2022 div.1に出た。

https://www.codechef.com/COOK138A

PERFPERMは、 $1,\dots,K,K+2,\dots,N,K+1$ という列を作ることを思いついた。後ろ $N-K$ 項をrotateするとそれぞれgoodでなくなる。ただし $N=K-1$ の場合はこれでは対応できない。さすがに $-1$ かと思ったが、 $N,2,\dots,N-1,1$ とすればよいことに気づいた。また実装上 $N=K$ の場合も特別扱いする必要があって、これらの場合分けをしてAC。PERMEXはまず $A_0=A_1=A_N=1$ である必要がある。それ以外はどんな場合でも対応できて、 $A_i=0$ であれば $0,\dots,i-1$ が出現する位置の合間に $i$ を入れ、 $A_i=1$ であれば逆にその間に $i$ を入れないようにすればよい。実装は $0$ と $1$ の間に入れるか端に追加するかで分けた。MANGOMKTはギャグで、価格の変動を「全体に $-1$ 」と「隣接する頂点に $+2$ 」に分割すると、 $+2$ 以外の寄与をひとまず $\sum_u A_u-N(N-1)/2$ と表せる。残りについて、辺ごとに考えてみると、辺でつながった頂点のうちどちらか一方だけがその辺によって $+2$ されると見なせることがわかる。つまりどのような順番で操作しても寄与は全体の辺数を $E$ として $+2E$ 。

UNCANNYXORは、 $x\mapsto x\oplus {\rm reverse}(x)$ という操作を何回行ったら $0$ になるかが $f(x)$ の値であるという風に読み替えられる。プログラムを書いて実験してみると必ず3回以内で収まっているように見える。手で試すと法則が分かった。今2進表現で $n\ge 2$ 桁の数を扱っているとする。最上位bitは当然1である。まず最下位bitが0の場合、操作後も $n$ 桁の数になるが、これは必ず回文となる。よって2回目で $0$ になる。次に最下位bitが1の場合、全体が回文であれば1回目で $0$ になる。回文でないならば操作後の数の最下位bitは0で、またその数自体は非ゼロ、つまり最上位bitは1となる。この場合は一番最初の場合分けのケースに帰着できて、1+2回の操作で $0$ になる。以上の考察から、 $n$ を固定すると、最下位bitが1で全体が回文であるような数が $2^{\lceil(n-2)/2\rceil}$ 種類存在するというように考えて $\sum_{i=2^{n-1}}^{2^n-1}f(i)$ の値が閉じた式で表せる。 $n$ の偶奇で分けると、等比級数の和で $2\le n\le N$ の和がまた閉じた式で表せるので、最後に $n=1$ の場合を足して終わり。実装はかなり短くなった。

SLINGは、 $A$ の値で降順ソートして順にdpしていくことが考えられる。遷移については $(x,y)\mapsto(x+y,x-y)$ を考えると、盤面からある正方形を除いた領域から値を貰ってこれる。二次元セグ木……を持ち出さずともよくて、行ごとのmaxを管理するセグ木と列ごとのmaxを管理するセグ木をそれぞれ持てば、正方形の上下左右で高々4回クエリを投げることで求める値が取得できる。更新もそれぞれ1点ずつsetすればよい。

ここまでかなり順調で、5完時点ではtouristに次ぐ2位だった。しかし残り2問に手も足も出なかった。TANGLINGTREEは1次関数と傾きが変わる点を持ってマージテクする方針でしばらく考えるも、そもそも関数の加算ができないことに気づいて終了。GRANDPAPAは $A$ にしかない要素・ $B$ にしかない要素・ $A$ と $B$ の両方にある要素の個数を管理してdpし、最後に順序付けるようなことを考えていたが、5乗から落ちずおしまい。最終的にGRANDPAPAが4人に解かれ、5完最速で5位だった。

またコードゴルフの続きをする。atgolferに流れてきた更新を見て知ったが、Octaveのdisp関数は、括弧なしでも呼び出せるらしい。もしかして全部縮むかと思って慌てて仕様を調べたところ、引数……というか直右に書いた文字列がそのまま出力されるので、ほとんどの場合には使えないということが分かって一安心。ただかろうじて文字列の出力には使えるので、それで1問縮められたようだ。この問題の最短コード自体は言語をRakuに変えて取り返すことができた。

atcoder.jp

日記を書いて、さらに5時間ほどJOIの古い問題のコードゴルフ（？）をしていた。昔のJOI予選の問題は、手元で実行して出力ファイルを提出するというコンテスト形式から、テストケース数が高々5個しかない。これを利用して答えを埋め込むことができる。数年前から知られている手法だが、あまりの不毛さにか提出数はそれほど多くない。ただまあ、それが可能であるならばいつか必ず誰かが行うはずなので、取られる前に取っておこうということでずっと作業していた。

以前はsedで入力中の特定の文字を見つけ、答えを出力する手法が取られていた。ところがそれから言語アップデートがあって、追加されたdcがこの用途でも猛威を振るう。入力の先頭1、2行ほどを読み込んで値のmodを取ったり平方根を求めたりし、そうして作りだした小さな数でスタックをrotateし、あらかじめ仕込んでおいた答えを出力する。5通りの入力があるなら5通りの出力を用意しなければならず、また入力から計算する数もうまくバラけさせなければならない。計算式については適当に形を決め打ってからプログラムで全探索するとよい。出力の埋め込みは基本的にそのまま書くだけだが、間にいちいちスペースが必要になるので、そこをうまく詰められるなら前の数と差分を取ったりスタックサイズを持ってきたり、いろいろ試すことになる。こちらは用意する出力の順番にも依るので完全に手作業となる。

昼間になってしまってさすがにまずい。明日は夕方からとは言え1on1が予定されている。布団に入って少しハーメルンを読み、正午就寝。

02/22(火)

午後4時、目覚ましで起床。1on1まで1時間。普段ならもうひと眠りしたところ、今日はあまりの眠さからさすがに今寝たらヤバいと思って気合いで起きた。

しばらくコードを書いて、出来上がる直前に1on1が始まる時間になった。書いたコードの意図などを説明していたら、さっき焦って書き進めていた部分が全然見当違いのことをしていたと気づいて焦る。少しの議論の結果、簡単に効果が見込める実装方針はなさそうということになったので、とりあえず全体をコメントアウトして放置した。それから、そもそも今日の本題であった、作ったコードのデプロイ作業について手順の確認をした。そう、デプロイである。先週金曜日のミーティングを受けて、ひとまず今できている部分を使ってみようという話になっていたのだ。

このあたりどこまで書いてよいものかわからない。日記ではかなりぼかしているというか、極端にマクロな話か極端にミクロな話しか書かないようにしているつもりなので、一応秘密にできているのではないかと思うものの、客観的に見るとバレバレなのかもしれないという不安感がある。インターンを続けてそれなりに経過し、だんだん気の緩みが出てきているかもしれない。とりあえずここでは、僕が何のために何のコードを書いているかは書かないことにしよう。とにかく何か書いていて、それがデプロイされることになったのだ。

確認を終え、今日の1on1は30分程度で終了。その後、デプロイのためコードをmasterにマージする前にもうちょっとちゃんとテストしておくかということで少しやってみた結果、実はボロボロであることが明らかになって、修正のためしばらく格闘していた。つまらないコーディングミスを修正したら思ったよりクリティカルに効いて、金曜日のミーティングで説明した動作は保てていそうという感じ。また依存しているライブラリのバグを踏んでしまったらしく、NullPointerExceptionが送出されるケースにも遭遇した。さすがに回避しようがないので、良くないコードだと知りつつtry-catchでログを吐いてから握りつぶすことにした。

依存しているライブラリのバグか何かでぬるぽが吐かれるので、それをキャッチしようとして調べていたら、ぬるぽをキャッチしてはならない（戒め）ということを言われて人生終了
— こたつがめ (@kotatsugame_t) 2022年2月22日

昨日のCook-Offのレート更新が来ていた。5位で2662→2762(+100)、highestである。国内3位、世界35位。

東方遺骸王の更新が来ていた。相変わらず良い。最近はスカーレット姉妹が登場した。以下ネタバレ注意。かなり昔からいたキャラの娘という設定になっていて、そう繋がるのかと感服していたら、さらにフランの狂気・能力についても1年以上前に張ってあった伏線が回収されてひっくり返った。これまで長い間、出てもせいぜい旧作キャラで、ほぼオリジナルとも見える展開が続いていた本作だが、やはり根っこは東方の二次創作だったのだと実感している。

syosetu.org

午後11時半からECR123に出た。5完31位。

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

Aは問題文を読みながら、通路の横に扉があることを想像して「経路を工夫して最短の移動ですべての扉を開けよ」みたいな問題かな、と思っていたら先頭から見るだけだった。Bは謎。 $2,\dots,N,1$ 、 $3,\dots,N,2,1$ 、……というように $1$ を末尾に置いた状態でrotateするのを $N-1$ 通り出力し、最後に $2,1,3,\dots,N$ を出力した。Cは2乗なら簡単そうだけどそこから高速化できないなと思って制約を見ると $n\le 5000$ で拍子抜け。しかし2乗も別にそこまで自明ではない。まず区間の長さごとに初期値の和の最大値を求め、長いほうから順に累積maxを取る。すると $k$ 回操作したいときに必要になる「長さ $k$ 以上の列の最大」が求まるので、それぞれ $kx$ を足した後再度累積maxを、今度は先頭から取る。ここで初期状態は区間の長さが $0$ のところに値 $0$ を、それ以外のところに $-\infty$ を入れておく必要がある。最初、全部 $0$ を入れており修正に少し手間取った。

Dは後ろから見るだけで簡単だと思っていたら2WAしてしまった。1回目は、行が全部埋まって列を更新しても無意味な場合（またはこれの行と列が逆のパターン）の考慮し忘れ、2回目はそれの修正ミス。また1回目の提出後に気づいたが、 $n$ や $m$ の和に制約がないので毎回使ったフラグを全部消しているとTLEする。いちいち更新した箇所をピンポイントで消す必要があってひたすら面倒。Eは、とりあえず簡単のため先頭文字が'R'になるようにしておく。最初1直線に進む部分を特別扱いした後、次に連続する'D'の個数を $c$ とし、それより先にある'R'の個数を $r$ 個とすると、上から $c$ 行のうち右から $r$ 列には立ち入れないことになる。残りの部分は常に長方形領域なので縦横が入れ替わった状態で同じ形の問題になり、再帰的に解くことができる。全部同じ文字の場合だけ別に処理する。

Fは解けなかった。まず $G$ の存在から、数の具体的な値に興味がないことがわかる。 $F$ を考えると、数列をランレングス圧縮した状態で個数を順に $a_1,a_2,\dots,a_m,a_{m+1}$ としたとき $\gcd(a_1,\dots,a_m)=1$ である必要があることもわかる。本当は全部同じ数列というものが存在しうるが、これは適当な列を $F$ にかけることで得られるので、 $n,k\ge 2$ の場合は無視してよい。 $n=1$ または $k=1$ の場合は最初に1を出力しておく。

さて、ランレングス圧縮後の $a_1,\dots,a_m$ を $\sum a\lt n$ の範囲で数え上げる。 $a_{m+1}\gt 0$ から出る制約である。 $\gcd=1$ である場合を数え上げるので、包除原理っぽいことを考えると $\gcd=p$ である場合を数えて係数に $\mu(p)$ を掛けて足し合わせればよい。まず $p$ に対して $1\le m\le \lfloor(n-1)/p\rfloor$ であり、 $m$ を決め打ったときどこに区切りがあるかを考えれば区間長の場合の数が $\binom{\lfloor(n-1)/p\rfloor}{m}$ であることもわかる。あとは $m+1$ 個の区間のどこにどの値を入れるかという話になる。先ほども述べたように $G$ の影響で数の具体的な値には興味がないため、例えば $m=1$ ならば $\{1,2\}$ しかないし、 $m=2$ ならば $\{1,2,1\}$ と $\{1,2,3\}$ しかない。小さいケースを手で試してOEISに投げると一応見つかった。ただ高速に計算するのは難しそう。

愚直に求めるコードを書いて試してみると、サンプルが合わない。よく考えると、例えば $k=2$ かつ $m=2$ の場合に $\{1,2,3\}$ は使えない。 $3$ が登場せざるを得ないためだ。だから、そうやって仮置きした数字の最大値も考慮して場合の数を求めないといけない。現在の要素数と仮置きした数字の最大値をキーに持つdpを考えて埋め、その表自体をOEISに投げると、今度も見つかった。どうやら（第二種）スターリング数になるらしい。スターリング数の部分和を求める方法をググるも見つからず、係数を求める代わりにdpの初期値を弄って値がそのまま答えになるようにした後遷移を高速化しようとしているうちにコンテストが終了した。

以上の考察は正解から微妙に離れて行っている。まず、スターリング数の部分和は実はベル数と名前がついているらしい。それを知らなくてもスターリング数の具体的な式がわかっていたら自力で行えるべき式変形ではあるが、ベル数を1つ求めるのは現在の制約だとだいたい $O(k\log n)$ かかる。まだ間に合わない。そこで、先ほど区間の区切りを決めてから仮置きする数列を決めるというように2段階に分けたところを、1段階にまとめてみることにする。つまり、直前の区間の値と違う値を入れるという制約を外してみる。これでも必要十分な数え上げができて、 $\lfloor(n-1)/p\rfloor+1=\lceil n/p\rceil$ 個の区間に値を割り振る場合の数となる。これまた現在の要素数と仮置きした数の最大値をキーに持つdpを考えてみると、なんと少しずれただけで先ほどのdpとまったく同じ値が出現する。つまり、スターリング数であった。

今度はベル数 $B\left(\lceil n/p\rceil,k\right)$ を $1\le p\le n-1$ で求めればよい。今 $\lceil n/p\rceil$ は $O(\sqrt n)$ 種類しか存在しないので、求めるべきベル数もまた $O(\sqrt n)$ 種類である。毎回 $O(k\log n)$ かけても間に合う制約なので、これでようやくAC……とはいかず、まだ微妙に異なる値が出る。これは数列が全部同じ値になるケースのせいで、そのようなものは数え上げの対象になっておらず、また現状だと $\sum\mu(p)$ 回足されてしまっているので消えてもいない。よって毎回ベル数から $1$ 引いて足し合わせることで、今度こそ正しい値が出る。

3800msで通った。 $n\le k$ のとき $B(n,k)=B(n,n)$ という事実を利用してベル数の計算にかかる時間を削減すると、なんと50msで通った。爆速。スターリング数やベル数など写像12相っぽい感じになってびっくりしていたが、考えてみると何となくわかった。 $k$ 個の区別されない箱を用意して $1\dots\lceil n/p\rceil$ を入れ、各値についてそれが入っている箱の番号（初めて出現する箱の場合は連番を振っておく）を並べると、いま求めたい列としてvalidなものになるということ。ただしコンテスト中に考察していたような「常に直前の区間と値が異なる」列もまた少しずれたスターリング数になるのはよくわからない。

ハーメルンを1作読了。「ヤミヤミの実で宵闇の妖怪」。設定は好物だが、ほぼダイジェストと原作をあまり知らない人間にとって最も読みにくい形式だったためつらかった。

syosetu.org

日記を書いて、昼間まではずっとハーメルンを読んでいた。またワンピースの二次創作。午前10時半ごろに今年のICPCの模擬地区予選に関する情報が公開されたので、参加登録をしておいた。学食で食事でもしようと思っていたら、02/23は現在の天皇誕生日で祝日のようだったため失敗。

Twitterで以下のような問題が流れてきた。引用したもののうち1番目のツイートである。これには強烈な見覚えがあって、記憶から掘り出してきた「東大王」だとか「ポッキーの日」だとかいうワードが大当たりし、検索すると一発で見つけることができた。2番目のツイートである。当時は今よりもうちょっと数学パズルに対する興味が強くて、これに関しても解答まで見てははあと感服した覚えがある。当時のその解答とは、1番目のツイートのリプライにぶら下がっている黒板の写真のうち、左半分のものと全く同一であった。

〔おためし企画 #ツイッター数学探究部〕
自由に考えてリプライ・引用リツイートしてください。 #数学授業の教材 pic.twitter.com/DUXxo492zm
— すど (@ysmemoirs) 2022年2月22日

📝この難問、解けるかな📝
東京大学医学部の学生でありながらクイズ界で名高い水上颯さん @sou_mizukami より超難問が届きました✉📭簡単なようで…難しい💦
正解の発表は今夜8時❗制限時間は11時間です。解答リプライをお待ちしています☺#ポッキー頭の体操 #降参したらRT pic.twitter.com/osBKZ2PNDf
— Pocky Japan (@PockyJPN) 2016年11月11日

これらをRTすると、FFの方から「 $N$ 角形に対して一般化できないか？」というツイートがなされた。ちょっと気になるところではある。多角形の成立条件については、自分の直感によれば三角形の成立条件の素直な拡張、すなわち「任意の一辺が他の辺長の和未満である」というだけでよいように思える。必要性は明らかで、十分性については、例えば線分たちを3グループに分け、それぞれ直線につなげたもので三角形を作れることを示すとよさそう。最も長いものを $a$ とすると、まず $a$ だけで1グループ作り、残りをできるだけ均等に割り振って2グループ作るので十分。その2グループでは長さの和の差は $a$ 以下にしかならない、ということから三角形の成立条件を確認できる。

さて、問題の答えを求める。適当に言っていたら大外れで、これまた別のFFの方からそれらしい答えが出された。辺長の和を $2a$ とすると、 $N-1$ 次元空間における $0\le x_i$ かつ $x_1+\dots+x_{N-1}\le 2a$ となるような領域から、 $0\le x_i$ かつ $x_1+\dots+x_{N-1}\le a$ となるような領域を $N$ 個ぶん引いたものが $N$ 角形が成立する部分になりそう。そのような超多面体の体積を求める際には、超立方体の体積に何らかの係数（おそらく $1/N!$ ）を掛けることになる。その係数を $k$ とすると全体の体積が $k(2a)^{N-1}$ で、引くもの体積の合計が $Nka^{N-1}$ になるから、割合を計算する際には $ka^{N-1}$ の影響が消えて、求める確率は $(2^{N-1}-N)/2^{N-1}=1-N/2^{N-1}$ となる。

この値は、 $N\rightarrow\infty$ としたとき $1$ に近づくことや、 $N=1,2$ というギリギリのケースでも確率 $0$ となって成り立っていることから、それっぽさが非常に高いと考えられる。

シャワーを浴びて布団に入り、しばらくハーメルンを読んで午後0時半に就寝。

02/23(水)

午後8時半起床。ハーメルンを読み続け、日付が変わったあたりで小腹が空いたのでリンゴを切って食べた記録がある。午前1時半に寝落ちした。

02/24(木)

午前6時起床。また昼過ぎまでハーメルンを読んでいた。起きて学食に行く。今日は国公立大学入試の2次試験前期日程前日ということもあり、キャンパスには下見に来たらしい人々が散見された。もはや何もかも懐かしい。食事して注文していたラノベを受け取り、帰宅した。

またハーメルンの続きを読もうとした。しかし文章的な読みにくさに耐えきれなくなり、昨日今日と100話ほど読んできたものを途中で諦めることにした。設定はかなり好みっぽかったので、ちょっとくらい変な文章でも読み進めていけたはずだが、主人公のセリフが意図的に崩壊させられていたのには我慢できなかった。言語不自由系ってなんだよ。ある程度注意して読まないと内容が取れないので目を皿のようにしていたら、周辺の文章の微妙な間違いまで気になってしまった。

２度目の人生はワンピースで - ハーメルン

別のハーメルンを開いて、短かったので午後6時半読了。「絶対正義は鴉のマークと共に」。主人公がひたすら強くて残酷でよかった。

syosetu.org

また別のハーメルンを開いて少し読んだ後、ラノベを1冊読了。「一生働きたくない俺が、クラスメイトの大人気アイドルに懐かれたら」。良かった。主人公が変におどおどしたり遠慮したりしていないのが好ましかった。1巻ではヒロインと主人公が互いにほんの少し惹かれあうだけで、それよりも他のキャラたちをよく見ることができて嬉しかった。アイドル寄りのシーンが多く、学校での様子も描かれてはいたものの学内の関係性に影響があるようなイベントはまだ本格化していないため、次巻が楽しみ。

半同棲ラブコメは最近さらによく見るようになった。例えば昨年12月に買ったラノベを確認してみると、29冊中9冊で主人公とヒロインがプライベート空間を共有する描写があった。いやこれだと僕がただただ好んで買っているだけか、まあその9冊が全部12月の新刊というだけで多さはわかるだろう。というわけで、正直食傷気味なところはある。テーマ自体が好みであることは以前から変わっていないとはいえ、その中にも当然僕にとっての当たりはずれはあるのだ。その点、このラノベを購入した決め手というのは実はみわべさくらさんのイラストにあって、もちろんそれも良かったのだが、中身もいい感じだったので買ってよかったなという気持ちになった。

設定的には隣人・同級生の美少女・半同棲ということで「お隣の天使様にいつの間にか駄目人間にされていた件」との共通点がかなりあるが、それをどう料理するかというのは筆者によってさまざまなので、どれだけ読んでも面白い。どれだけ読んでも、と言ったのには理由があって、この設定の作品は書籍化に限ってもかなり多いのだ。隣人まで入れると結構絞られるが、それ以外の設定が共通しているシリーズなら実際僕も4つ5つくらい読んだ記憶がある。
週記（2020/10/19-2020/10/25） - kotatsugameの日記

1月のCook-Offで10位以内に入ったため、また100USDがもらえるらしい。メールが来ていた。新しく個人情報を送らなくとも、以前送ったものを参照してくれるらしい。

ハーメルンの捜索掲示板で、最近読んだワンピースの二次創作のタイトルで検索していろいろ漁ろうとした。総合評価でソートして上からいろいろ見ていたので当然ではあるが、有名なものはあらかた目にしたらしい。もちろんあらすじで読まないことにしたものも含む。ワンピースに絞るのはやめて、さらに適当に捜索内容を眺め、1作見つけ出して読み始めた。ただ、午前8時半寝落ち。

02/25(金)

午後3時半から午後4時、午後8時から午後10時半の2回は起きていた形跡がある。しかし本格的に目を覚ましていたのは、日付が変わって午前1時半からのことであった。金曜日はゲーセンに行こうと思っていたのに、起きたら土曜日になっていた。インターン先からSlackでメンションが飛んできていたのも返信が遅れてしまい、週をまたぐことになって動きが遅くなるのは申し訳ない。

少しずつ起きていた間もハーメルンを読んでいて、午前5時半に1作読了。「じゃしんに愛され過ぎて夜しか眠れない」。

syosetu.org

かなり良かった。遊戯王のカードで遊んだのはおそらく中学生の頃が最後だったはずで、もうルールをほとんど忘れていた。しかし登場するカードそれぞれのテキストだったりコンボの解説がかなり丁寧に行われていたので、非常に読みやすかった。内容的にもかなり好みに近い。圧倒的なデュエルの実力を保持した状態で学園生活を満喫する展開が最高だった。

そういえば、僕は構築済みデッキをいくつか買ってルールブックを読んだので、バトルフェイズの後にメインフェイズ2が存在することを知っていたが、それを実行したことはなかった気がする。また融合召喚で手札から直接融合素材にできるというのも、どこかで聞いたとは言え微妙に信じ切れていなかった。少なくとも僕の周囲ではそういうプレイが行われていなかった。まあ、当時はインターネットでルールをチェックするような文化もないことだし、小学生が正確にプレイするのは難しかったということだ。最近は遊戯王のカードで遊べるスマホアプリが話題なので、よくこういうことを思い返している。

さて、なかなか良い作品に出合えたので、次も似たようなものが読みたい。先ほど「圧倒的実力」「学園生活」というワードが出てきたので、それっぽいもので一つ検索でもかけてみようかと考えたのだが、おそらくこれだと、転生して前世の力を残したまま云々というような話が大量にヒットしそうな気がする。しかし自分の中で何が違うのだろう？もう一捻り欲しいのだろうか。とりあえず、先ほどのハーメルンが紹介されていた捜索ページからもう1作品見繕ったので、それを読むことにした。小説家になろうの、「黄金の経験値」というもの。読み始めたのが午前8時で、それから午後5時半に就寝するまでずっと読み続けていた。非常に面白い。

頂点で待ち受けるキャラクター - ハーメルン

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

寝る直前にFFの方がちょうど東北大の受験を終えられたことを知り、もしかしたら川内キャンパスの周辺で会えるかとも思ったが、すでに仙台駅の方まで出られたようだったので断念した。さすがにそこまで行くのは、もうかなり眠いことだし夜からのABCを考えると避けざるを得なかった。

02/26(土)

午後8時前に起床。あまりに眠すぎる。必死で布団から這い上がった。いつの間にかAHC008が終了していて、最終提出がコードゴルフ用のWAのものだったのでちょっと残念。結局初日から全く手を付けなかった。食事して午後9時からABC241に出た。

AtCoder Beginner Contest 241（Sponsored by Panasonic） - AtCoder

AはAWKで書くと短そうというのはすぐわかったものの、入力が0-indexedなのを忘れて1WA。Bは多重集合の包含を判定すればよいので、Rakuで⊃演算子を使えばよい、と思ったらWA。信じられなくてほぼ同じコードをもう一度投げてしまった。とりあえずC++でACを確認した後、何が違うのかを探った。実は⊇演算子を使う必要があり、前者だと精密に書けば $\supsetneq$ の意味になるようだ。自分が普段使う意味と異なるため、言語リファレンスを眺めて⊇演算子の存在に気づき、ようやくACできた。Cは愚直に見る。Dはmultisetのlower_bound・upper_boundを使う。Eはダブリング。Fはひたすら面倒。とりあえず注目する点を列挙した後、行・列ごとにまとめて辺を張った。間に他の障害物がないような障害物のペアを列挙し、その間にある「注目する点」から両端の障害物の一つ手前に向かって辺を張るという方法で実装した。

Gは謎。優勝者を固定したとき、それ以外の人物でまだ勝敗が決まっていない試合に対し「勝ってもよい試合数」「必ず負けなければならない試合数」が求まる。それらに関する適当な不等式を立てると、当然のようにWAになった。さらにしばらく考えて最大流で解けそうだと感づいた。辺の張り方にはかなり苦労してさらに3WAを重ねた。まず頂点を2倍にして勝ちと負けを表す。その間に辺を張り、そのうちフローが流れたものについて、勝ちの頂点が負けの頂点に対して勝つと定義する。すると、先ほど求めた2種類の試合数は「始点から勝ちの頂点への流量」「負けの頂点から終点への流量」で表せる。まだ勝敗が決まっていないペアは、交差するように流量1の辺を2本張ることで表現した。フローを流して、最大流量が全員の「必ず負けなければならない試合数」の和に等しければよい。フローが流れなかった辺はどのように勝敗を決めても構わないことになる。

ACした後に気づいたことだが、各ペアについて2本辺を張っているのだから、両方にフローを流してしまう可能性があるのではないだろうか。これについて、例えば人1と人2の両方がもう一方に1回ずつ勝つとしてしまった場合に、適切に勝敗を振りなおすことで矛盾を解消できることを説明する。まず、人1と人2はどちらも「勝ってもよい試合数」「必ず負けなければならない試合数」がそれぞれ1回以上存在するため、初期状態で勝敗が決まっていない相手がお互いを含め2人以上存在する。その状態で2試合が重なり合ったような形になっているので、人1に対して人2が2試合したと見なせ、矛盾しない範囲で勝敗を確定させると、人1に対して代わりに誰か（ここでは人3とする）の勝敗が未確定のままになる。ここで、フローを流して判定に成功している以上、人3はすでに「必ず負けなければならない試合数」を消化していると言って良い。つまり新たに勝った試合が増えても問題なく、人1が人2に負ける代わりに人3に負けると振りなおしてよい。

Exは解けなかった。べき級数で表現すると、 $[x^M]\prod_i \frac{1-(A_ix)^{B_i+1}}{1-A_ix}$ が求まればよい。分子は次数こそバカデカいものの、非ゼロである項が非常に少ない（高々 $2^N$ 個）ので、全部列挙してうまくやれば解けるのではないかと考えた。分母は $N$ 次なので、Bostan-Moriなるアルゴリズムを使えば毎回それなりに高速に求まるだろう。Nyaanさんのライブラリを窃盗し、 $O(2^N N\log N\log M)$ のような計算量になった、はず。しかし残念ながら数ケースTLEしてしまった。実行時間を見る限り、別に惜しくもない。7完65位。

コードゴルフ。AはAWK、BはRakuでよかった。Cを飛ばし、DはC++。答えが-1になるケースの判定が面倒だったので、multisetの初期化時に番兵を置いておいたのだが、この場合ループを書いてイテレータのインクリメント・デクリメントをするよりstd::prevとかstd::nextとかを使うのが短くなるようだ。しかも、関数の引数にstd名前空間内で宣言されたイテレータを入れているので、prevやnextとのみ書いても勝手にstd名前空間内を探しに行ってくれるらしい。EはPerlが短いようだ。残りも手付かず。

実引数依存の名前探索 - Wikipedia

夜中から朝にかけてもずっとなろうを読んでいた。朝方溜めていた日記を書いて、またなろうに戻り、正午就寝。

02/27(日)

午後4時半に目覚ましで起床。今日は久しぶりのOpenCup……と思ったら、いつの間にか5月に延期されていた。正直睡眠時間が足りていないので助かった。眠いのにうっかり1時間ほどなろうを読んで、二度寝。

次に午後8時過ぎに起きた。今週の水曜日（日記では火曜日の欄）、模擬地区予選に参加登録をしてあったが、これが無事受理されて、チーム一覧の一番上に掲出されていた。参加登録開始のツイートを見つけたのもかなり速かったし、それをSlackに投下してからチームメイトの2人が反応するのも速かったのだ。

2021/Practice/模擬地区予選/申し込みチーム一覧 - ICPC OB/OG の会

食事して午後9時からARC136。

AtCoder Regular Contest 136 - AtCoder

Aは先頭から考えると、BB→AかBA→BBB→ABしかしなくてよい。Bはこのような操作が順列において転倒数の偶奇を変えないことを知っていたので、どうせそれ以外は何でもできるだろうと考えた。インデックスの移動を調べて、それの転倒数が偶数であることを確認すればよい。要素に重複がある場合は適当に選んでswapすることで偶奇を自在に弄れるため、常にYesとなる。やけに見覚えがあると思ったら、CF #653 div.3-Fで既出らしい。

https://codeforces.com/contest/1374/problem/F

Cは激ムズ。 $A_i$ の最大値を見つけて、そこで切り開いてみる。 $A_0$ が最大だったとしたら、 $A_0,A_1,\dots,A_{N-1},A_0$ のように並べる。両側からの操作がうまい具合に重なる位置がもう一か所存在するので、それを $1\le i\lt N$ で全探索すると、 $j\le i$ に対して $\max(A_j-A_{j-1},0)$ 、 $j\ge i$ に対して $\max(A_j-A_{j+1},0)$ の和だけ新たに操作回数が必要となりそう。ただし、重なる位置はいくらか左右に広がっている可能性がある。今のところ $i$ で合流するときに $\max(A_{i-1}+A_{i+1}-A_i,0)$ だけ無駄になっているので、その分左から右、あるいは右から左に融通したい。融通できる操作回数は $i$ 番目を通過できる $A_i$ 以下でなければならないため、今の2数の $\min$ を先ほどの和から引いたものが暫定的な答えとなる。これを各 $i$ に対して計算し、最小値を取って負なら0に直すなどした後、最後に $A_0$ を足したら通った。

Dは面白い。素直に考えると「それぞれの桁の数値が $999999-A_i$ の対応する桁以下となるような数の個数」が欲しくなるが、これは計算できる。以下のQiita記事を思い出すと一瞬で分かった。

ゼータ変換・メビウス変換を理解する - Qiita

Eは難しく、解けたときは興奮した。到達可能なペアが最大で何本辺をたどる必要があるのか気になって実験してみると、7->14->20->25という3辺のケースのあと、4辺使うケースが一向に見つからない。この3辺のケースをよく見ると、それぞれ一番近くの偶数を経由してたどり着いているようだ。整理すると、 $(o_1,p_1)$ （奇数 $o_1$ とその最小の素因数 $p_1$ の組）、 $(o_2,p_2)$ （ただし $o_1\lt o_2$ ）は $o_1\rightarrow o_1+p_1\rightarrow o_2-p_2\rightarrow o_2$ という風に結ばれることになる。実はこれは最適な移動になっているようだ。1手でたどり着ける場合は $g=\gcd(o_1,o_2)\gt 1$ だが、特に $p_1,p_2\le g$ かつ $o_2-o_1\ge 2g$ （ $o_1$ 、 $o_2$ がどちらも奇数であるため）から先ほどの移動も可能である。2手以上でたどり着ける場合は、 $o_1$ から1手進むと必ず $o_1+p_1$ 以上になり、 $o_2$ から1手戻ると必ず $o_2-p_2$ 以下になることからわかる。

ここで、選んだ頂点に高々1つ含まれる偶数を $e$ としてみる。一つも含まれない場合は後から考える。今奇数 $(o,p)$ を選ぶとすると、 $o\rightarrow o+p\rightarrow e$ または $e\rightarrow o-p\rightarrow o$ のような移動ができてはいけない。このことから $o-p\lt e\lt o+p$ という条件が出る。逆に、これが満たされていれば $p$ の最小性から $o$ と $e$ を同時に選ぶことができる。次に、 $e$ に対してそれぞれ先ほどの条件を満たす組 $(o_1,p_1)$ と $(o_2,p_2)$ （ただし $o_1\lt o_2$ 、 $p_1\ne p_2$ ）があったとき、 $o_1$ と $o_2$ を同時に選ぶことができるか考える。実はこれも可能で、 $o_2-p_2\lt e\lt o_1+p_1$ からわかる。

あとは奇数 $o$ ごとに対応する区間 $[o-p+1,o+p-1]$ を求め、どの $e$ と一緒に選べるかをチェックすればよい。コンテスト中は考察が中途半端で、ある $e$ に対して $o$ と $o+p$ が同時に条件を満たす場合のケアを行っていたが、冷静になるとその2数が両方奇数になることはない。つまり、選べる数は全部選んでよい。偶数を1つも選ばない場合にも、偶数とは限らない数 $e$ が存在して選んだすべての数が $e\in[o-p+1,o+p-1]$ を満たしていることが必要十分であるため、同様に計算できる。最後に $A_1$ を足して答えになる。

Fは解けず、ノーペナ5完10位だった。

コードゴルフ。AはBA→ABという変換を考えたのでどう書くかかなり悩んでいたが、A→BBとBB→Aをこの順に貪欲に行うのでもよいらしく、かなり短くなった。sed。BはRuby。Cは数列の最大値と隣接項の差分の和を計算すれば答えが求まるようで、あっけにとられつつRakuで書いた。以降は手付かず。

昨日寝る前にSnackDown 2021のTシャツが届いていたので、開封した。サイズはSでちょうどよさそう。布の手触りがコンテストTシャツにしては良いように感じる。海外の半袖Tシャツは袖が微妙に短いので、それさえなければ常用してもよいくらいに思われる。

インド、サイコー pic.twitter.com/7raAuiz1IF
— こたつがめ (@kotatsugame_t) 2022年2月27日

昼までずっとなろうを読んでいた。