ICPC模擬地区予選 2021 参加記

2022/03/06に開催された模擬地区予選にチームAobayama_dropoutで参加しました。メンバーはゆきのんさん・ha15さん・僕です。

使用するユーザ名とパスワードが各チーム3組ずつ配布されましたが、これの割り当てについてはメールが届いた時点で決めていました。

うっかりコンテスト開始時間に起きてしまい、また考察共有用のHackMDを作るのにも手間取って10分くらい遅れて問題を読み始めました。

https://yokohama2021.jag-icpc.org/public

C問題

2人がA問題とB問題を読んでいるようだったので、C問題を読みました。置換してハミング距離の最小化ということで、i\rightarrow jという置換が選ばれたとき得点\#\{k\mid 1\le k\le N,\;A_k=i,\;B_k=j\}が得られると言い換えると、最大重み完全マッチングになります。これは負辺ありの最小費用流で解けます。負辺ありで負閉路なしということで、最初のポテンシャル計算を手動で行えばあとは普通の最小費用流で解け、計算量はO(M^3\log M)になります。先頭要素から順番に固定していくとこの計算をO(M^2)回行うことになりますが、定数倍としてちょっと減ることもあり通ると思えました。実装してAC、29分でした。

H問題

僕がC問題を通すちょっと前に立て続けにA問題とB問題が通っていて、その後2人はそれぞれG問題とI問題に移ったようでした。自分も順位表を見てH問題に行きました。Short codeという単語が見えて興奮しましたが問題自体はほぼ自明で、入次数が0の頂点を全部選べば十分に見えます。ただ書いているうちにループが存在しうることに気づいたので、いったんSCCを計算して、その上で入次数を見るコードを書きました。36分時点で通りました。

J問題

グラフの同型性判定まで読んだところで検索すると、WikipediaにPであるかわかっていない問題と書いてあって絶望しました。しかし問題文をよく読むとグラフがN頂点N辺の連結グラフ、いわゆるなもりグラフだったので、とりあえずループが確定することがわかりました。ループの各頂点からは木が生えていて、ループを適当に回したり反転したりして、これらの木を全部一致させられれば答えがYesになります。

まず（根つき）木の同型性判定ですが、これは括弧列にしたりハッシュ値を計算したりする方法があります。括弧列は下手な実装をすると文字列長の総和がO(N^2)になりそうなので敬遠して、ハッシュ値を求めることにしました。念のため法を2つ用意してハッシュを計算するクラスを作りました。

snuke.hatenablog.com

さて、あとはこのハッシュ値の列を一致させる問題です。ループを反転しなければならないケースは実際に反転して考えればよいので、ループを回して一致させられるかのみチェックすればよいことになります。ハッシュ値が同じインデックスをmapで集めて云々というコードを書いていましたが、しばらくして正気に戻って、片方を2倍してZ-algorithmを適用するコードを書きました。これも1発で通って、時間は72分でした。

D問題（とI問題）

Iが詰まっていたので問題を読み、Hの昇順に見るとSN状態のdpで解けることを指摘しました。順位表を見て、より多く解かれていたD問題に進みました。

クイズが人aに回答され、pポイント付与されたタイミングでのコインの枚数の変動を観察します。回答前、人iがポイントP_iを持っていたとすると、p\ge 0のときP_a\le P_i\lt P_a+pを満たす人i（i\ne a）の持つコインが1枚増えます。p\lt 0の場合もほぼ同じです。それらと人aを除けば、ほかにコインの枚数が変動する人はいないようですから、人を持っているポイントでソートできればコインの枚数の変動は区間加算（・1点更新）で管理できます。

これは可能です。具体的には、(P_i,i)という組を各クイズのタイミングで考えると、全体でも高々N+Q種類しかありえませんから、全部列挙してセグメント木のインデックスとして使うことができます。先ほども述べたように、区間加算と1点更新、1点取得が行えるセグメント木を用意して、ポイントの変動によって人の位置を動かしつつ処理します。クイズの回答者については、ポイントごとの人数を管理するBITがあればコインの枚数の変動が求まります。

実装は微妙に大変で、118分時点でACしました。

K問題

順位表ではK問題が解かれていて、考察もすでにG問題とI問題を通した他の2人がしてくれていました。人のペアを全部試すことができて、選んだ2人が距離D以内にいる時間というのは高々1つの区間で表せるようです。この区間の計算には2次方程式の解を求める必要があって、よく桁落ち誤差を問う問題で出題される七面倒な場合分けになります。HackMD上でその場合分けを詰めた後、実装すると一方的に宣言して書き始めました。区間さえわかってしまえば感染拡大の様子のシミュレートはdijkstraで行えます。144分時点でACしました。

F問題（解けず）

残りはE問題とF問題です。E問題が全完阻止幾何に見えてしまったので、F問題を考えることにしました。

とりあえず更新がない場合を考えます。よく見ると文字列の先頭に)を追加したり末尾に(を追加したり、とにかくこの2種類の操作は直感的に嬉しくないので、どうせ必要最低限しか行わないだろうと思いました。実際この2つの操作を余計に行ったとき)...(という文字列になりますが、両端の文字を移動させて...)...(...の状態にするくらいならしないほうがマシですし、...(...)...まで持っていくとしたらその間の)(をすべてswapするほうが安上がりです。

あとは、)(を()にswapするのが何回必要かを数えればよいです。いくつか方法を考えましたが、どれも括弧を\pm 1に変換したときの累積和の値があるボーダーラインより下になっている位置しか計算に含めないという場合分けを行う必要があり、セグメント木の区間更新には対応できませんでした。ところが、平方分割なら対応できることに気づきました。累積和の値に応じて集めておいたデータのマージが難しい一方で、結局計算に必要なのは集めてきたデータのうちただ一点であるからです。

より具体的な方法を述べます。(と)の数が一致している文字列を考えます。(という括弧は+1に変換されますが、この直前の累積和の値をsとしたとき、答えに\max(-s,0)だけ足すという計算で正しい値が求まるらしいことが実験からわかりました。実際には(と)の数には差があるため、それを均すために追加する括弧の分や、また平方分割している以上それまでのブロックのぶんも考慮する必要があるので、累積和の値は全体的に増減します。ここでtだけ減るとした場合、\max(t-s,0)の和を求めることになりますが、前計算でs\le tなる位置におけるsの和S_tとその個数c_tを求めておけば、c_tt-S_tとして計算することができます。全体をflipした場合の値も同様に前計算しておけば十分です。

これを実装しました。まずmapを用いて、出現した各sに対してS_sとc_sを求め、取得には二分探索を用いましたが、TLEしました。手元で作ったランダムケースでは5秒弱かかっていました。次に、mapの代わりにソートしたvectorを使って、取得は同様に二分探索で行うようにしました。さらに入出力高速化などを行い、平方分割のバケットサイズBについてもいろいろ弄ってみて、B=100にするのが最も高速になったのでそれを採用しました。これらの高速化によって、同じランダムケースで1秒となかなか高速に計算できるようになりましたが、同じくTLEしてしまいました。都合5回提出したもののすべてTLEとなり、そのままコンテストが終了しました。

コンテスト後

9完8位でした。9完内では2位ですが、それは上位陣が10完以上していったからで、9完までのペナルティ的にもかなり負けてしまいました。少なくとも自分が担当した問題では詰まった感触がなく、なぜこうも速度で負けているのか一瞬不思議に思いましたが、どう考えても最初10分くらいのんびりしていたからで、この時点でのタイムロスが全体に響くことを強く実感しました。

F問題の平方分割は方針として合っていたようです。足りなかった考察はsの取りうる値についてで、sはブロック内における累積和の値なので、必ず-B\le s\le Bを満たします。つまり、mapやvectorを用いずとも長さ2B+1の配列で値を保持することができ、この場合取得に二分探索が必要なくなります。更新時も含めて計算量から\logが消え、実装してみたところランダムケースの計算が0.5秒で終了しました。まだ提出できていないので、そもそもコードの正当性も確かめられていませんが、なかなか惜しかったと感じています。こういう崖の先の一問を解けるようにならない限り、世界大会はないでしょう。

週記（2022/02/21-2022/02/27）

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でログを吐いてから握りつぶすことにした。

昨日の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番目のツイートのリプライにぶら下がっている黒板の写真のうち、左半分のものと全く同一であった。

これらを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シャツは袖が微妙に短いので、それさえなければ常用してもよいくらいに思われる。

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

週記（2022/02/14-2022/02/20）

02/14(月)

先週は週記を投稿してから比較的すぐ寝た。午前4時だった。ここ最近かなり良い生活リズムが続いている。

午前9時半起床。二度寝に失敗した。目を覚ますといつも口内に違和感がある（寝ている間の細菌の繁殖か）ため、何をするにしてもとりあえずうがいをしておきたい。しかしうがいのために冷たい水を口に含むとてきめんに眠気が失せてしまうようで、いつも二度寝に失敗しているのにはそういう理由があるのではないかと考えた。

布団から出てしばらく他の人のブログを読み、昼前に学食に向かった。今日は非常に良い天気で、道路も空いていてかなり気持ち良く原付を運転できた。食事して予約していた本を受け取り、帰宅。これで1月の初めに注文した分は全部受け取れたはず。

それからずっと勉強会のための発表スライドを作成していた。昨日の時点でpreprintを一通り読んで、どのような説明の順序にするかも考えておいたので、それに沿って情報を置いていく。とはいえ、当然のことながら元のpreprintの時点でよく考えられた構成になっているので、基本はそれに合わせるような形になった。いくらか点在する情報があったのでそれをまとめようとはしてみたものの、効果のほどはどうか……。一度読んだから情報の位置を動かしてもついていけるだけで、人に説明することを考えるとこれまた元のpreprintの状態が良いのかもしれない。

夕方までかかって何とか完成を見た。急いで進捗報告スライドを生成して、インターン先定例会に臨む。先週金曜日にちょっと進めたことを発表して終了。その後勉強会が始まった。やたら早口になっていたり、同じことを何度も繰り返したりしていた気がするものの、発表後の質問が結構多かったあたりに手ごたえを感じる。やはりみんな興味はあるのだろうが、腰を据えてpreprintを読むまではいかなかったのだろう。自分もこのような機会がなければ全く見もしなかったはずだ。

使用した発表スライドを公開することにした。先週著作権についてあれこれ心配していたものの、悪意があるわけでもなし問題にはならないだろうと楽観的に考えることにした。

勉強会0214.pdf - Google ドライブ

勉強会の終了は午後7時だった。AtCoderのコンテストリストを見に行くと、つい昨日行われたJOI本選が過去問として解けるようになっていた。いつ公開されるかとコンテストリストを定期的に見守っていたのだ。

JOI 2021/2022 本選 過去問 - AtCoder

Aは簡単で、クエリがソートされているので完全に線形時間で解ける。Xでループを回して、その位置のピースを含むAまで分割し、そうやって直近に分割したAを変数に持っておいて出力する。最初に書いたこの方針がかなり良かったようで、Rubyに書き換えて76B、Perlに書き換えて71Bと予想よりはるかに縮んでくれた。BはTLが1secだしN\le 3\times 10^5だしでlogを落としに来ているのかと考えたが、全然そんなことはなく普通に二分探索が通る。

Cは非常に難しく、小課題7が解けずに解説をチラ見してしまった。本当は解説の途中で止めて考えるつもりだったのに、小課題6まで解説と全く同じことをやっていたのでずるずる最後まで読み進めてしまったというわけ。解説はdpテーブルの必要な位置が少ないことを利用して解いているが、自分としてはGoal人集めた瞬間に残りを前計算から求める方法が書きやすかった。DはTLでダブリングというキーワードを見てしまったので一瞬。E問題は解いていない。

Cの特に小課題7に2時間以上かかってしまった。急いでシャワーを浴び、午後11時半からCF #771 div.2に出た。服を着て部屋に駆け込むとコンテストが始まっていて絶望したが、実際は1分程度の遅刻だった。

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

Aはp_i\ne iとなっている最小のiとp_j=iなるjを見つけて[i,j]を反転するのが良い。Bは転倒数を考えると大小関係が逆転しているすべての要素が交換できる必要がある。先頭要素から順に挿入ソートしていくことを考えて、ソート済みの列の後ろから偶奇が一致する部分とその一つ先を管理することで何とか解いた。TLで偶奇それぞれが昇順ならよいということを知り、愕然。確かに……。Cは似たような問題を最近見た覚えがあったので、それを思い出しつつ解いた。2次元平面に(i,p_i)をプロットしたとき、連結成分それぞれをピッタリ含むような長方形が左下から右上に連なるような形になる。左からの累積maxが右からの累積min未満であるような境界を数えればよい。

ERASEは先頭から累積minの更新点を列挙して、隣接するどの2つの更新点にも、その2つとそれぞれペアを組めるほかの1点が存在すればよい。と面倒なことを言っているが、つまり2次元平面にプロットしたときに左上と右下に完全に分割できなければよいというだけの話。

週記（2022/01/17-2022/01/23） - kotatsugameの日記

Dは操作を逆順に見るやつ。106個の入出力は気が狂っている。Eは区間をsetで、色ごとに足された値を配列で管理する。色を塗り変えるときは、これまでその色自体に足されていた値を個別に足して、新しく塗られた色にもともと足されていた値を引くことになるが、この操作は区間に対して一律で行えばよいので遅延セグメント木で書ける。106にlogがついてTL 4secと意味不明な制約。Fは解けず。Eまでシステスが通って16位。

コードゴルフの興味深い更新があった。\bmod{10^9+7}した後の数を3で割る必要があって、巧妙な式変形で最短を取られたコードが、さらに縮んでいた。\bmod{3\times(10^9+7)}で余りを取った後直接3で割ってもよいらしい。3の倍数であることはわかっているのだから、確かにこれでうまくいくようだ。感服した。

atcoder.jp

午前4時就寝。

02/15(火)

午後4時起床。今日はうがいしたにも関わらず二度寝に成功した。よくわからないが睡眠負債がたまっていたのだろう。午後5時から1on1で、念のためそれに合わせて目覚ましをセットしておいて助かった。

しばらく布団でゴロゴロした後起き上がり、食事して1on1へ。先週金曜日からの進捗はほぼないので、いくらかの取り決めをしても30分程度で終了した。実装のアイディアはいくつも出てくるものの、どれも一長一短に感じられる。実際はやってみないとわからないのに、やる前から微妙に悲観的になって手が動かない状態にある。困った。

久しぶりにラノベを1冊読んだ。「『ずっと友達でいてね』と言っていた女友達が友達じゃなくなるまで」2巻。かなり良かった。1巻のラストがついに高校生活が始まるところだったので、どんな風になるのか期待していた。新キャラ2人以外には全く焦点が当たっていなかったが、その新キャラのうち男のほうがかなり好みの設定だった。淡々としていて何事にも動じない感じが好ましい。まあそれは本題ではない。主人公とヒロインの進展については終始外堀を埋めている感じで、次の巻でついにゴールインしそうな予感がする。あとがきでも3巻が節目の巻になると予告されているので、ぜひ続刊してほしい。

別のラノベを開いて少し読み進めた後、食事。今日は久しぶりにパスタを茹でた。調べたところ、昨年5月末以来だったらしい。パスタソースは軒並み賞味期限が切れてしまっていたものの、関係なくおいしい。食べ終えて午後10時からTROC #26に出た。

https://tlx.toki.id/contests/troc-26/

Aはよい。相変わらず提出が面倒で微妙に時間を食う。Bは一昨日のARC135-Dを解いていれば瞬殺で、市松模様に正負を割り当てて和を0にできればよい。Bにしては難しく感じる。Cは数の小さいほうから\left\lfloor\frac{\sum A_i}2\right\rfloor個を偶数番目に置くことを考えて、丁寧に条件を確認する。細かいところを詰めるのが嫌すぎてしばらく固まっていた。書き始めると意外と単純。Dは花と最短の蜂の距離を列挙して、適当に日付を更新しつつ取れるはちみつの必要なエネルギーを優先度付きキューで管理する。

Eは謎。各ノードで1\le k\le 自分の子の数の場合の値を計算する。kをインクリメントしてから子でループを回し、その子がさらにk個以上の子を持っているなら計算結果を取得し、そうでないならAの値を取得して、その値と直前の値を入れ替え、最後に上位k個の和を求める。まず入れ替えてから上位k個の和を求める部分は、上位と下位をsetで管理すると可能になる。setの要素を下位から上位へ適宜ずらしていく感じだ。次に子のループを回す部分だが、一度k個以上の子を持たないと分かった瞬間次のループからその子を見ないようにする。これも子をsetで管理してeraseしていくことで行う。計算量解析は貰う側ではなく渡す側で考えればよくて、各ノードは自分の子の数+1回しか計算結果を取得されないので、kのインクリメントに伴う子のループが全体でO(N)となる。setを弄る部分も大体そのくらいの挿入・削除回数になる。Fはちょっと面白い。各品物に対してA_{i,*}をソートし、差分を取ることで「maskに含まれる店が使えない場合はコストがさらに〇増加する」という情報がM個得られる。差分を取ったことにより、各maskに対し部分集合全体の和を取ることでコストがわかる。これはゼータ変換である。

GはしばらくKグループまでではなく1グループK人までという問題に誤読していた。そちらはどこまでグループ分けしたかのdpになって、遷移がdp_i=\min_{i-K\le j\lt i}\left(dp_j+(N-j)\max_{j\le k\lt i}T_k\right)と書ける。このうち\maxの部分をxと置いて直線だとみなせば、傾きN-jは単調減少だし値を取得する\maxは単調増加するのでdequeを使うCHTが使える。このdequeはセグ木に乗せることができる。取得クエリのたびに適当に先頭からpopしていき、更新は変更が一切行われずただ列を右に伸ばす感じなので、対応するノードのdequeにpushすればよい。dp_iの計算に戻ると、\maxの部分が同じになるjの範囲を管理し、その範囲が[i-K,i)に完全に含まれるものは前計算したものを区間minで取得、中途半端に重なるもの高々1つ（これは二分探索で求める）についてはセグ木で計算することになる。今まで書いたことは全部誤読した問題の解法であって、正しい問題が分かってからは手も足も出ず。

6完最速で5位、レートは2680→2732(+52)で最高値を更新。ランキングで7位に来た。

今月分のTCB44が始まっていたので、参加した。ちょうど日曜日に終了するので、ここに詳細を書ける。今月のテーマはデータ処理らしく、答えをQ回求めたりN回求めたりする問題ばかりだった。

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

2問目は微妙に面倒。5問目は数列A\%Mをソートしておき、最小値とM-X\%M以上の最小値、高々2種類を調べればよい。6問目はBITを2本作って、片方はまだ移動していない文字列を、もう片方は各文字列が移動した最後のクエリを管理する。8問目は小さいほうからx個目の値とそこまでの和が取得できればよく、実はこれはbinary trieで実装できる。二分木の各ノードにそれ以下のノードの和を持たせておく感じだ。このことに思い至るまで結構時間を使ったのと、考察ミスで小さいほうからx個目の値ではなく最小値を使ってしまったため、1ペナと30分強を費やすことになった。-26pt。そういえば以前binary trieを必要なところだけ作るセグ木と言ったことがあるが、より正確にはクエリの範囲が左端か右端を含んでいれば対応できるセグ木となるようだ。

9問目は、まず変数の正負を見るため2部グラフの判定をインクリメンタルに行う必要がある。これはUFを使う、頂点を倍加する手法で行える。次に\log_2を取った値を管理することを考えて、こちらはかなり久しぶりに重み付きUFを引っ張り出してきた。基本的に自由度は連結成分数になるが、正負のチェックやループにおける\log_2の値の不一致などで壊れてしまった連結成分は全部0を代入することになるので、そのような連結成分にマークをつけておいて丁寧に処理する必要があった。手間取って微妙に時間オーバーし、-2pt。10問目は最終形態の文字列にmanacherを使い、どの位置の文字を追加した瞬間に回文が増えるかを求めればよい。文字それぞれに対し、それを中心とする回文が増えるタイミングで追加される文字は最終形態の文字列における区間になるので、imos法で足せる。

日記を書いてシャワーを浴びた。すぐ寝ようとしたものの頭髪が乾いていないのでしばらく待つことにしてスマホを触っていると、Mojangからメールが来ていたのに気づいた。Minecraftを作った会社である。Minecraftのためのアカウントを、Mojang独自のものからMicrosoftアカウントに移行しろということらしい。もう数年触っていないので今更どうなろうとあまり気にしないとはいえ、気づいたからにはやっておかないと何となくすわりが悪い。ということで少し作業をして、そのあと流れでコードゴルフを始めてしまった。1時間以上経ってようやく一段落ついたので切り上げ、就寝。午前8時前だった。

02/16(水)

午後2時前に起床。どうにも眠れなさそうだったので素直に起きた。

購買に行く前に昨日のコードゴルフの続きで布団で思いついた改善を適用しようと思い、パソコンの前に座った……ところ思わず熱中し、購買の閉店に間に合わない時間になってしまった。仕方がないのでそのまま続け、仕上げに実行時間のブレを利用して微妙な解法を通したところで終了。

街に出る。ところどころ雪が残っているのが見えるが、まあ問題はないだろうということで自転車に乗って、仙台駅の反対側まで向かった。

まず駅前のヨドバシカメラでUSBケーブルを買う。先日賞品として受け取ったHHKBについて、Bluetooth接続でしばらく使ってみたものの、1台目のHHKBとまったく同じ理由でストレスを感じる。特にサブのマシンに接続しているということもあり、しばらく操作しないとキーボードの電源が切れるのは致命的だった。ケーブル長は机から下のPCまで伸ばすことを考えて1.5mを選択。巻き尺がないので必要な長さが正確に測れず、以前買った0.5mのケーブルをもとに目測で決めた値。大変悩んで、しばらく売り場で両手を広げて長さを感じてみたりと不審な行動をしていた。

使っていなかったBluetoothドングルを差して接続してみた。

週記（2022/02/07-2022/02/13） - kotatsugameの日記

USBケーブルを購入してHHKBを有線でつなぐことにした。bluetoothだとかなり不安定でよく変な挙動をするし、数分操作しないだけで電源が落ち、復帰のために数秒電源ボタンを押さなければならないのもつらい。

週記（2021/09/13-2021/09/19） - kotatsugameの日記

ついでに、以前から音声入力の際にノイズが混じるのが気になっていたので、新しいマイクを購入した。部屋では換気扇の音が結構するのでそれが原因だと思ったが、店員さんに聞いてみるとPC内の電気信号がノイズになっている可能性もあると聞いて驚いた。環境音については指向性のマイクを、電気信号についてはUSB接続のマイクをそれぞれ使うことで対処できるらしく、両方兼ね備えたものをおススメされたのでそれを購入。2000円ちょっとだった。これまで使っていたマイクの4倍の値段がするので、まあ悪くなることはないだろう。

食事してゲーセン。ヨドバシカメラの近くのゲーセンはチュウニズムの筐体にスマホアームが用意されていた、たまに手元を撮影しに来ていた。今日もそのつもりで向かったのだが、新筐体になったのをきっかけにだろうか、アームがなくなってしまっていた。残念。こうなるとただ遠くて台数も少ないゲーセンに来る価値はなくなる。移動して、いつものセガ仙台でプレイした。

今日は午後5時半から閉店までみっちり6時間弱プレイして腰をバキバキにした。進捗としては理論値が+10譜面と、1日に出した数では過去最高に。かなり調子が良かった。数回プレイしてダメだったらさっさと別の譜面に移ったのも良かったか。13+初の理論値も決めることができたとはいえ、譜面のレベルは理論値難易度を元に設定されているわけではないので、かなり簡単で拍子抜けだった。いや拍子が抜けていないから理論値なのだが。

あとは大鳥居が伸びた。14+の未鳥3譜面は本当にどうしようもなくて、たぶんこれが一番可能性があるはず。正当に難しいので、正当に頑張れば出ると思う。残りはSINister EvolutionとLove & Justiceで、どちらも鍵盤が押せない。

立ち食い蕎麦を食べて帰宅。疲れからしばらくぐったりして、シャワーを浴びてから買ってきたマイクの動作確認をした。なかなかよさそうだったので調子に乗ってYouTubeで生配信を行った。

www.youtube.com

「アルゴリズムと数学　演習問題集」の残りの問題が4問あったので、それを通した。特に言うことはなし。以前解こうとして謎に詰まってしまった部分もただの勘違いだった。ちょっとコードゴルフをして、まだ終わりたくないと感じたので、CF #760 div.3を解いた。

Dashboard - Codeforces Round #760 (Div. 3) - Codeforces

Aは先頭3要素が答え……と思ったら、3番目を飛ばすケースもある。かなり優しいサンプルで4つ目を見て気づいた。Bはある文字列の2文字目と次の文字列の1文字目が異なっていれば間が削除されているとわかる。制約から複雑なチェックは必要なく、間を埋めるだけでよい。一度も埋める操作が行われなかった場合は、末尾に適当に文字をつけ足しておく。Cは赤で塗られるインデックスたちの集合が2通りしかないので、両方試す。赤で塗った数の最大公約数をdとするのが最適で、青色についてチェックすればよい。Dは大きいほうから2k個を消すとしてよい。消す要素を入れ替えることではスコアは1しか減らない一方、残す要素を増やすと1以上増えてしまうからだ。最後に消す要素をどうペアにするかを決める。小に大を組み合わせるという考え方ではなく、値の異なる2要素をペアにすると考えれば簡単。消す要素のうち過半数を占める要素があれば、その個数からkを引いた分だけスコアが増えることになる。

Eは思いつくまでが難しかった。S=\sum a_iとすると、b_i-b_{i-1}=S-n\times a_iとなるらしい。差分を取ることで他の位置からの影響を取り除けるということ。S=\frac{\sum b_i}{n(n+1)/2}でもあるので、これで全要素が求まる。あとはa_iが正整数になるかを調べればよい。Fは2^{62}未満の範囲で問題文に書いてある操作を繰り返したら通った。一応理屈もあって、0を追加する操作は最初の1回以外無意味なので、操作で作れる数はそんなに増えないのだ。数の上限はオーバーフローしないところを狙ったが、2回目以降の操作は桁数が増える一方ということを考えれば2^{60}\gt 10^{18}で切ってもよかった。Gはa_iとb_iをまとめて昇順に並べ、隣接する項との間隔がk以下のところを連結すると、同じ連結成分内は自由に交換していける。各連結成分でもともとa_iだった要素を数えておき、大きいほうからその個数分だけ和をとっておけば、全部合わせて最大の値が求まる。これはクエリをkの昇順に並べることでどんどん更新していける。

途中から眠気が強くて大変だった。また生配信しながら問題を解くのはプレッシャーがかかってかなり緊張すると分かった。今日は何とか全完できたので助かった。配信を終え、アーカイブをちょっと見直しただけでも、やはりマイクを変えた影響はかなり大きく感じられる。まず音量が大きいし、ノイズも全然ない。対して以前の配信の、あまりの聞きにくさに衝撃を受けた。第二回日本最強プログラマー学生選手権のエキシビションなど、かなり多くの人が視聴してくれたのにこの音質だったとは……。恥ずかしい限り。

午前6時就寝。

02/17(木)

午後2時過ぎ起床。ゲーセンから帰るときは腰がバキバキだったが、一夜明けて肩がバキバキになっていた。

非常に眠いところを何とか布団から這い出して、購買に向かった。食事を手に入れようとしたのだ。しかし閉店間際ということもありパン類・ごはん類がものの見事に売り切れており、仕方なくカップ麺を買うことになった。追加で注文していた本を受け取り、帰宅。

atgolferを動かしているサーバーはさくらのレンタルサーバーを利用している。毎月650円弱がちびちび口座から出て行っているが、いちいちメールが来たり通帳の1行を埋めたりするのが煩わしく感じられたので、1年分を一度に払う方法に変更した。契約当初は適当なところですぐ止められるようにという配慮で月ごとの支払いにしたはず。ただ、もう2年近くbotを動かしてきて、今更止めることなど考えられない状態にある。

無理やり起きたのでまだ眠気も残っているし、今日はゆっくりしつつ細かなタスクを終わらせようと思って、とりあえずテスター作業に取り組んだ。当然詳しくは書けないのだが、諸々すべて終わってみると日付が変わりそうな時間になっていた。その後失った時間を取り戻そうとするかのように、朝方まで起きてラノベを2冊読了した。

1冊目、「護衛のメソッド」2巻。面白かった。イラストも良い。2巻になって新キャラが出るも、相変わらず誰が黒幕なのかはっきりしなくてところどころ不穏な雰囲気がある。そんな中でも一切動じない主人公が格好いい。取り巻くヒロインの事情は前巻である程度明らかになったので、その部分はまあ安心して読めた。いちいち可愛らしくてこれも良かった。最後までたどり着いて、満足しつつあとがきを読んだら、この2巻でシリーズ完結と書いてあってびっくりした。まだ明らかにされていないことも多いし、ぶん投げた感じが否めない。作者さんは別作品が売れているので、そちらに注力したかったのだろうか。残念。

この作品の主人公もそうだが、俗世を知らない設定のキャラとか、あるいは冷静な知的キャラとかが結構好みの設定である。これは恐らく、主人公が何らかの外的要因に影響を与えられる展開が好みでないということに通じるのだろう。細かいところだと、主人公がからかわれて赤面するみたいなシーンもあまり好きではない。皮肉が通じずに相手がぐぬぬとなるか、あるいはドンと構えて余裕の言葉を返すみたいな行動に憧れを抱いている。

2冊目、「純白と黄金」。これも面白かった。最強のヤンキーがテーマということで、チームとかストリートとかの話が好きな自分としては興味を惹かれて購入した。とはいえこういうテーマにはリンチシーンがありがちで、それだけは苦手なんだよなあと思いつつ読んでみると、実際はほとんど超人バトルみたいな様相を呈していてびっくりした。主人公は自分の実力を隠したいといいつつ全然隠せていないので、周囲に強さを見せつけるシーンがちょくちょく挟まって快感だった。文中の形容詞の一部がヤンキーっぽく、口が悪くなっていて笑った。

午前8時半就寝。

02/18(金)

午後2時半、目覚ましで起床。

午後3時からインターン先の業務に関わるミーティングを、メンターさんに加えてもう一方を交えて行った。詳細は当然ぼかすが非常に有意義な時間だった。いろいろご意見を伺えたこともそうだし、何より自分の作ったものを今からでも使えそうだと評価して頂けたのが嬉しい。メンターさんと話している間はまだ改善点がたくさんありますねという感じだったので、急にゴールが目前に来たような錯覚を覚えた。もちろん改善点は改善点で当然これから実装していくことにはなる。それを終えて、続けざまに少しだけ1on1をした。進捗はないので先ほどのミーティングに関して少し確認して終わり。

サークルのバチャに出た。Python（もしくはPyPy3）で全問通した。どれも見覚えのある問題とは言え、順当に通せて一安心。6問目のguruguruは区間に一次関数を足せればよくて、遅延セグ木でぶん殴ろうとして冷静になり、差分を取ってimos法をした。7問目はすごいことをしたような記憶があって怯んでいたが、書いてみるとかなりシンプルになった。

https://kenkoooo.com/atcoder/#/contest/show/a13007e5-73d2-4500-91e9-c0405d293e89

しばらくテスター作業をしていた。TLにハーメルンの「アラサーがVtuberになった話。」の書籍化情報が流れてきてびっくり。最近Vtuberもののラノベが多い。

syosetu.org

夜はずっと日記を書いていた。その後またしばらくテスター作業をし、シャワーを浴びたりして午前4時過ぎに布団に入った。ラノベを読もうとしたが、思ったより眠気が強かったので、素直に寝ることにした。午前5時就寝。

02/19(土)

午後3時起床。1時間くらいゴロゴロした後また寝て、次に午後5時に起床。届いた生協の冷凍弁当を受け取ってまた眠ろうとしたがどうにも眠れず、ゴロゴロしているうちにこれ以上は生活リズムの崩壊が致命的になると考えて起き上がった。午後6時半だった。食事してからラノベを読んで、午後9時からAGBC239に出た。

Denso Create Programming Contest 2022(AtCoder Beginner Contest 239) - AtCoder

Aはdc。答えが小数になるのを見落として1WA。Bはdcでどう書いたものかかなり悩み、とりあえずRubyで通してから10Bの解を思いついた。CはC++で全探索。このあたりでAがさらに縮むことに気づいて愕然とした。Dも全探索で、これは素数判定を書くのが面倒なのでRubyを持ち出した。その後10分程度Rakuでコードゴルフしていた。残りはずっとC++。Eは上位20個だけ持つ。列のマージは毎回マージソートみたいな要領で行った。全部まとめてからソートしてもよかったらしい。Fは連結成分ごとに新たに辺を生やさなければならない頂点を管理して、その個数が最少の連結成分と最大の連結成分を繋ぐことを繰り返した。この貪欲っぽい操作の証明を考えているうちに、新たに辺を生やさなければならない頂点がただ1つしかない連結成分が常にないとダメだということに気づいた。コードには特に反映されていない。Gは問題文に最小カットと書いてある。ACLのmaxflowが最小カットも求められたことを覚えていたので、それを利用してコーディングした。辺を双方向に張っておらず1WA。

Exは、見た目的に\lfloor M/k\rfloorを列挙して頑張るんだろうなと思った。M状態のdpで遷移を愚直に行うコードを書いて実験してみると、確かにその商の値が一致していればdpの値も一致するらしい。これで、とりあえずdpの状態数がO(\sqrt M)になった。遷移は、dpの各状態に対してそこに遷移できるサイコロの出目の範囲を求めることでこれもO(\sqrt M)になる。まとめてO(M)の解法ができて、出力は合うもののループ内部で割り算などしているため最大ケースでは8sec強とかなり時間がかかってしまった。ここでふと、dpのある状態を見てサイコロの出目の範囲を求めた後、それより1大きな出目で遷移することになるdpの状態を二分探索で求めることにしたら、なんと1.3secくらいになった。恐る恐る提出してAC。

全完24位。Exのdpの値が一致する話は、解説のようにdpのキーをkではなく\lfloor M/k\rfloorとするとわかりやすかった。商の値が一致していればそこからさらに同じ数で割っても常に同じ値になるということ。また、遷移に必要な状態を1つずつ見るのではなく二分探索で飛ばし飛ばし見ると速くなったというのは、\lfloor M/k\rfloorが小さい場合に影響が大きくて、関係するO\left(\sqrt{\lfloor M/k\rfloor}\right)個の状態だけをうまく抜き出せたことによる。

コードゴルフ。Aはコンテスト中に気づいた改善が開始1分ちょっとで提出されており、大敗。Bはコンテスト中のdc 13Bが最短になっている。スタックに-9、0、1を積んだ状態で入力を読み、掛け算と足し算を行う。X\ge 0の場合はX\times 1+0が得られ、これを10で割ることで答えになる。X\lt 0の場合は|X|\times(-1)+(-9)が得られ、これも10で割ることで答えになる。Cは( (x_1-x_2)^2+(y_1-y_2)^2)/2が\{0,1,2,5,8,9,10\}の要素であればよい。テストケースハックをすると、集合を\{0,1,2,3,5,6,7,8,9,10\}=\{0,\dots,10\}\setminus\{4\}に広げてもACできることがわかるので、AWKと正規表現で書いた。DはRaku。初めにgrepなどで書いたところをanyやらallやらのJunctionで書き換えていくと結構短くなった。Junctionの入れ子が便利で、A\le \forall x\le B.(C\le \exists y\le D.P(x+y))みたいな式をそのまま表現できる。

EはRubyで縮めていたら取られた。maxメソッドに引数を与えると上位n個を抜き出してくれる仕様は、効くところではめちゃくちゃ効くという印象。ただ稀にしか目にしないので今日は忘れていた。GはPythonとnetworkx。minimum_cutというそのものそのままなメソッドがあって、コストと一緒にカットによって分割されたグラフをsetで返してくれる。頂点を倍加した状態で、source側のsetに頂点の入口が、sink側のsetに頂点の出口がそれぞれ入っていれば元の頂点を答えに含めることになる。各頂点について判定するのではなく、setの内容を弄った後に集合としての共通部分を取る方法にすると短くなった。FとExは手つかず。

午前2時からSRM824に出た。

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

Easyは成功にFを、失敗に-Sを割り当ててZero-Sum Rangesをする。Nの最大値が5e5で怖いなと思いつつmapで実装。結構後になって、値とインデックスのペアでソートした後計算する方法なら定数倍が軽くなったと気づいた。リサブはしなかった。Medは現在達成しているdifferenceをbitで表して、それと最後に出た目を持つdpを行う。bitを降順に見れば、それぞれのbitに対してdpの値D個がD元の連立方程式で表せるので、解く。一応すべてのNを試してみたが、どれもちゃんと解けるようだった。Hardは何もわからず。

EM2完速めで7位、レートは2525→2587(+62)。highestから1だけ小さい。Hardは不可能枠だと思っていた。まず、相異なる行き先が決まったら互いに干渉せずたどり着ける操作列が存在することが示せるらしい。コンテスト中からそうだろうなとは思っていたものの、構成的に証明できないと実装できなかった。次に、ナイトがあるマスから別のマスへ進むときの最短手数が定数時間で求められるらしい。これは知らなかった。最後に、そのような手数をコストとして初期位置と最終位置の間の最小重み最大マッチングを求めると、最適な行き先が決定できる。

ナイトの移動の最短手数について。無限に広い盤面においてナイトが(0,0)から(x,y)（ただしx,y\ge 0）まで進むときの最短手数は、(x,y)=(1,0),(0,1)の時は3手、(x,y)=(2,2)の時は4手、それ以外はc=\max(\lceil x/2\rceil,\lceil y/2\rceil,\lceil (x+y)/3\rceil)として、c+( (c-(x+y))\bmod 2)手となるらしい。足しているのはx+yの偶奇性に関する条件から出る値である。cの値は3種類の単純な下界を表していて、それがほぼ達成可能というのは驚き。証明を探したが見つからなかったので、自分で少し考えていた。

c\ge 2ならcを1手で必ず1減らせる。x\ge yなら(x-2,y-1)に、そうでないなら(x-1,y-2)に進めばよい。こうすると\lceil (x+y)/3\rceilは必ず1減るし、\lceil x/2\rceilと\lceil y/2\rceilのうち大きいほうも1減る。この操作でcの値が減らないとしたら、それはx=yかつx,yが偶数だった場合に限られるが、その場合\lceil x/2\rceil=\lceil y/2\rceil\lt\lceil (x+y)/3\rceilとなっているので問題ない。x-1が負の数になる場合は、代わりにx+1に進んでもよい。x=0ならばc\ge 2よりy\ge 3で、\lceil 1/2\rceil\le\lceil (y-1)/3\rceil\le\lceil(y-2)/2\rceilであることからわかる。y-1についても同様。

そのように進んだときコーナーケースとなるマスに突入する場合は、突入する1歩手前で別の移動先を選ぶことで回避できる。このことは小さい範囲を実際に計算してみることで確認できる。c\lt 2の場合も同様に確認できるため、これで下界が達成可能ということが分かった。

ラノベを1冊読了。「今日も生きててえらい！」。前半はヒロインが主人公を全力で甘やかす話で、そういうヒモ願望が自分にない以上、ヒロインの好意が信じきれない主人公のほうに共感して正直気味悪がりながら読んでいた。しかし後半になって事情は一転。ヒロインと主人公がデートしている盗撮画像が校内で出回った話から、いかに主人公がヒロインに見合う人物になるかという話が展開されて、こちらは好みの話題だったので非常に楽しんで読めた。もともとヒロインの取り巻きをしていた人が、主人公が外見を整える前後で対応をガラッと変えるとかではなく、無関心だったのが興味を持ち始めるという描かれ方で、嫌にリアルで恐ろしいなと思った。

日記を書いて布団に入り、しばらくラノベを読んで就寝。午前10時だった。

02/20(日)

午後5時起床。しばらく布団でゴロゴロしてから起き上がる。ずっとテスター作業をして、午後9時からABC240に出た。

https://atcoder.jp/contests/abc240

Aはdcで1WA。人はなぜ。BはRaku。CはRubyの多倍長整数をbitsetのように使う。ここからはC++で書いた。Dはstackでシミュレート。Eはまず部分木に含まれる葉の個数を数えた後、もう一度dfsして区間の始点を求めた。Fはランレングス圧縮されたそれぞれの区間内における値の変化が二次関数になるので、頂点を求めたりして範囲内の最大値を調べる。多く調べて悪くなることは何もないため、範囲の両端と頂点の左右を毎回全部調べる感じになった。

Gは、X,Y,Z\ge 0となるように符号を反転した後、t=\frac{N-X-Y-Z}2を求める。この値が非負整数でなければ答えは0。非負整数だったなら0\le i,j,kかつi+j+k=tとなるようなすべての組(i,j,k)に対して\frac{N!}{(X+i)!i!(Y+j)!j!(Z+k)!k!}の和を求めればよい。k=t-i-jは後からどうにでもなるのでiとjについて考える。値が2つの列の畳み込みの形になっているためそれができればよいのだが、列の長さがそれぞれt+1であるため、畳み込むと長さ2t+1になる。この値は最大で10^7+1になりうるところ、\bmod 998244353での畳み込みは長さ2^{23}\lt 10^7までしか対応できないため、そのままでは計算できない。そこで、列を前半と後半に分けることにした。後半をインデックス\lfloor t/2\rfloor+1以降とすると、その要素2つの積に対応する畳み込み後のインデックスの値はi+j\gt tとなるため、答えには関係なくなる。よって前半×前半、前半×後半、後半×前半の3回畳み込みを計算すれば必要十分である。実装してから最大ケースとして適当にいくつか試したところ、どれも答えが1になってしまってよくわからない。とりあえず提出したら1900msで通って、ああ想定解ではなかったんだなあと思った。

Exはsuffix arrayを求めてその順番でdpしてみたりするもよくわからず、諦めてしまった。7完16位。Gの2次元版の問題をO(1)で解く方法は以前知って感心した覚えがある。まあいくら感心してもコンテスト中に使えなければ無意味。ちなみに手元で試したら答えが1になったのは、本当はtime echo [INPUT] | ./a.exeとするべきところをecho time [INPUT] | ./a.exeとしていたかららしい。どうしようもない。

コードゴルフ。Aは(a-b)^2\bmod 10でRコマンドを実行する16Bの解を思いついていたところ、a-bを9で割った余りでRする15Bに負けて呆然。コンテスト中に出したWAは、この余りを取る除数を8にしていたものだった。これはa-b=-8で壊れてしまう。それにしても最近全然A問題の最短が取れない。Copilot対策だかでちょっとひねった問題が出るようになって以来、やけに苦手意識がある気がする。BはRakuで18B。wordsをSetにして要素数を見るだけ。問題を見て自明な最短コードだと思い、即座に飛びついた。取れてよかった。

CもRakuで、達成可能な数の集合を直接管理した。Setにすると要素への一律加算が簡単に書けなくなるので、uniqueで重複を省く。そうして作った集合にXが含まれるかを見るのではなく、逆にXから値を引いて行って0が含まれるか見るほうが、いろいろうまくいって縮んだ。DはAWKで頑張る。EはRubyで頑張っていたらPerlに大幅に負けた。コンテスト中に2回dfsをしたところは1回で良い。これまでに見た葉の個数をグローバル変数で持って、部分木に入る前の値と部分木から出てきたときの値がそれぞれL-1とRになる。

FもRuby。取られたものを取り返した。二次関数の頂点付近の値として見るべき位置は\left\lfloor \frac b{-x}\right\rfloorになる。0除算を回避するため、x\ge 0の時は-xの代わりに-x-1を使う。その方法も、|x|\le 4であることを利用して入力文字列中の空白文字の位置を参照することで実現されていて、唸らされた。この値を1とyでclampして、あとはx\ge 0の場合のために位置yも調べておけば十分らしい。基本的に頂点以外では位置0と位置yを調べたくて、位置0は直前の位置yと一致する。ただし最初だけ位置0が許されていないため位置1を調べることになるが、その場合b=0なのでclampした値が1になってくれるということ。Gは手つかず。

午後11時半からCR #772 div.2に出た。全完4位。

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

Aは全要素のbitwise ORを1要素にまとめるのが最適。Bは左端からlocal maximumを潰していく。潰すときは3つ組のうち一番右の要素を変更する。このとき、真ん中の値に合わせるのではなく、もう一つ右の要素に合わせることで別のlocal maximumも一緒に潰せてお得な場合がある。サンプルにあったので助かった。Cは、数列の末尾に行くにしたがって変更できる操作が少なくなるので、末尾から順に考える。まずa_{n-1}\gt a_nだとどうしようもないのでダメ。そうでないならiの降順にa_i\leftarrow a_{i+1}-a_nとしていくと、どんどん差が負の方向に広がっていきそうで良いと気付いたので、実装して提出した。しかしサンプルでWA。a_n\lt 0の場合、差が負の方向に広がらないらしい。そもそもa_n\lt 0の場合は全要素が負になるしかなくて、どんな操作をしてもa_x=a_y-a_z\gt a_yとなるため広義単調増加にはならない。よって最初からOKかそうでないかをチェックすればよい。この場合分けを実装してAC。

Dは、数をbit列とみなすと、yに対して2y+1が右端に1を追加する操作、4yが右端に00を追加する操作とみなせる。数列aの要素それぞれに対し操作を逆向きに行っていって、数列の別の要素と一致した場合、操作していた数を削除する。これで同じ数を生成する値が存在しないようにできるので、あとはそれぞれの要素が2^p未満の範囲で何回操作できるかを数えて足し合わせればよい。つまり2進表現において桁数を1または2増やす操作を好きな回数繰り返す方法が、p桁に至るまでに何通り存在するかわかればよくて、これは増やしてよい桁数に対する値を前計算できる。

Eは面倒。まず与えられた関係で辺を張って、連結成分ごとに考える。関係で結ばれた2つの車の向きは必ず異なるので、得られたグラフは二部グラフでないといけない。連結成分ごとに1つ車の向きを自由に決めてよいため、適当に塗り分けたものを車の向きとしてよく、これと関係から座標の大小関係を表す有向グラフが作れるので、それをトポロジカルソートする。閉路が存在したらこれもまたダメ。無事ソートできたら、座標としては適当に連番を振っておけば完成。一発で通ってハッピー。

Fは難しかった。いろいろ考察していたが、結局「i\lt k\lt jかつ『w_k\le w_iまたはw_k\le w_j』なるkが存在するようなペア(i,j)は答えにならない」というのが本質で、僕はそれをもうちょっと複雑な形で考えていた。解法は次のようになる：jを全探索して、ペアにする意味のある各iに対してweighted distanceを計算し、セグ木のi番目に保存しておく。クエリはj=rを処理した瞬間にセグ木に対して[l,r)の区間MINを求めることで答えられる。ペアにする意味のあるiは、まずi_0=j-1を試して、次にw_i\lt w_{i_0}かつiが最大であるようなi_1=iを試して……というように、w_{i_k}\lt w_jになるまで探索していくのが必要十分。これはstackでインデックスを管理することで高速に求められる。w_i\ge w_jである間iをpopした後jをpushするという実装から、このような計算が全体でO(N)回しか行われないことがわかる。かなり綺麗になって感動した。

TCB44が終了していた。5位。WAのペナルティが大きすぎる。

ラノベを2冊読了。1冊目は「初恋のお姉さんを今度養うことになりまして」。昨日読んだラノベとは逆で、主人公がヒロインを甘やかす話。この本の作者はラノベ書きとしてはベテランであるという認識で、実際ラノベらしい展開が続くというか、スッと読める感じがした。その分特に何か思うこともなく、総じて印象に残らなかった。

2冊目は「最強魔術師の弟子は冒険者ギルドの始祖となる」。面白かった。何か大きな組織を立ち上げるというのは、自分の好きな設定である「組織のトップに立つという要素」「歴史を作るという要素」を両方兼ね備えていて最強に見える。さすがにラノベ1巻では始動後数日間分までしか描かれなかったので特に大きな組織というわけではないが、立ち上げるにあたっての困難を主人公たちが何とか解決していく様が描かれてそれはそれで良かった。将来全国的に広がっていく様子を空想するのも楽しいものだ。

主人公は師匠の権力的にも実力的にもかなり強いので、最終的にはそれで解決した問題もある。何かを始めるに当たって、強力なメンバーが必要不可欠であるというのは頷かれる。一方、十分に成長した組織においては個人の実力に何かを依存するのはできるだけ避けなければならない、というのもよくある話で、こちらはラノベらしく主人公を活躍させるには何とも難しい制約に思える。そのあたり学術的な正しさとラノベ的な面白さのどちらを取るかの程度問題になるはずで、僕なんかは何かを著すならできるだけ正しくありたいと考えてしまうものだけれど、面白さを優先する状況だっていくらでも考えられるのだ。実際、僕も読むなら面白いものを読みたい。

1か月ほど前に自分で自分の提出をHackした後ずっと放置していた問題、ECR121-Eをついに解いた。整理してみると、結局各頂点が「黒である」「黒に隣接している」「黒にたどり着ける」のどれかであると分かればよくて、3つ目の判定としては「自分を根としたとき、黒の頂点を部分木に2つ以上持つ子が存在して、その子が3状態のどれかである」かを調べればよい。部分木における黒の頂点の個数を全頂点に対して求めるのは、かなり単純な部類の全方位木dpになる。

Submission #147117599 - Codeforces

朝まではずっと日記を書いていた。

週記（2022/02/07-2022/02/13）

02/07(月)

先週の週記を投稿してからの話。しばらくハーメルンを読み続けて、午後4時前に購買に行った。しかし先週金曜日から春休み期間だったようで、購買が午後3時で閉店してしまっていた。コンビニで菓子パンやおにぎりを大量に購入して帰宅。スライドを作ってインターン先定例会に臨んだ。日曜日は午後11時とかいうアホみたいな時間に起きたため、何とか徹夜に成功した。

先週の進捗は、火曜日に頑張ったもの一つのみ。僕の最近の稼働状況から見たらかなり進んでいると思ってしまいがちだが、社会人は最低限としてあの日と同じだけの時間毎日働いていると考えると震えが止まらなくなる。まあ話すことはあるし見せるものもあるので、ある程度自信を持って発表できた。

また、ふとしたことからAlphaCodeの話が盛り上がって、僕も先週の週記の最後に書いたように「slow positives」のことが気になっていたので議論の俎上に載せたりしていた。preprintをちょっと読んだ感じではまだかなりTLE解が出ているようで、しかし算出されたCFのレートへの影響はよくわからない。こうなると、数学的な問題が比較的得意というのも実際は愚直解が生成できているだけではないのか、と邪推してしまう。何度も言うように、そもそも問題文から動くコードが作られているというだけで驚くべきことである。

かなり話が長引いたので今週の勉強会はなくなった。終わってからまたしばらくハーメルンを読んで、午後9時半就寝。

02/08(火)

午前3時半ごろ起床。今日はこのまま午後9時半に寝落ちするまでずっと布団でハーメルンを読んでいたらしい。Chromeの閲覧履歴を見るに、午前9時から午前11時のあたりも眠っていたようだ。今読んでいるハーメルンは1話あたりが長く、注意深く履歴の間隔を確認しないと寝ているのか普通に読んでいるのかわかりにくい。

02/09(水)

午前5時起床。

今日締め切りのレポート、それもテストも課題もないレポート一発の講義のものが残っているのに、昨日まる一日をハーメルンに捧げてしまった。今日もずるずると午前10時まで読み続けて、1作読了。「正体不明の妖怪(になった男)、情緒不安定な百獣の腹心になる」。

syosetu.org

過去の話もワノ国の話も原作がどうなっていたのかわからないし、主人公も完全に悪役側だしキャラが謎だけれど、文句なしに面白かった。というのも主人公が最強だからだ。この一点だけでやはり安心感が違う。またワンピースはキャラクターの実力が懸賞金という明確な形で表現されるので、これがインフレしていく様子も見ていて興奮する。ネットでちょっと感想を見て知ったことには、主人公の介入によって原作と比べ百獣海賊団の隙がなくなっているらしい。そういうこともしっかりわかるとより楽しめたのだろうなと思う。文字を大きくする特殊タグを多用しているのが気になっていたが、読んでいくうちに理解した。原作の漫画っぽい表現に近づけようとしていたらしい。特に幹部級が勢ぞろいするときなど、キャラクターの発言の直後に肩書＋二つ名（＋懸賞金）を大書されているのはかなり印象深い形式だったのですぐ思い出せた。

昨日の昼前くらいにTシャツが届いていたのを放置していた。開けると予想通りCGRの商品だった。このうちCGR15のものは、胸のワンポイントが刺繍で施されており、裏地の薄くて白い布（接着芯）も含めなんとも洗濯しにくそうな感じがしている。本来ならネットに入れるべきだろうところ、生憎持っていないのでとりあえず単独で洗濯機を回してみた。案の定糸の塊が出てきて厳しい。着ないようにしたい。

レポートから逃げたいあまり別のハーメルンを読み始めた。午後1時半に閉店間際の学食に滑りこんだりしつつ、ずっと読み続けていた。夕方当たりにレポート提出をほぼ諦め、午後8時半に寝落ちした。

02/10(木)

午前1時半起床。意識を取り戻したらレポート提出期限が過ぎていて、罪深い解放感を覚えた。そのままハーメルンを読み続ける。午後1時からのゼミ前に一旦寝たいと思っていたので、午前6時半に寝た。

午前9時半起床。今日のゼミは最終回ということで、ちょっとだけ話したいことがある。そのために発表資料を作る必要があってこの時間に目覚ましをかけておいた、とはいえ眠気も強く、ダラダラハーメルンを読んでいたら午前11時くらいになってしまった。シャワーを浴びてパワポでスライドを作り、午後0時半くらいに完成。ちょっと空いた時間に学食に行こうと思っていたが、雪が降っていて原付が使えないため間に合わないと判断し、スライドを手直ししつつゼミの開始を待つことになった。

午後1時からゼミ。僕の話したい内容というのは、以前発表したときに出てきたルジャンドル記号の値を計算するアルゴリズム2種類の性能比較である。演算をどれも1ステップと考えれば、どちらも素数pに対して\left(\frac n p\right)をO(\log p)で計算できる。しかし一方は定数倍こそ軽いものの\bmod pで計算する必要があって、他方は\bmod 2でよい。この条件なら、pが小さいところでは前者が、大きいところでは後者が高速だと考えた。実際にプログラムを書いて、その様子を確認した。結果は以下にリンクを貼ったスライドに載っているが、概ね想定通りの挙動をしている。またpが大きくなるにしたがって演算の計算量が顕在化していく様子も見える。実験に使ったコードも掲出しておこう。

ルジャンドル記号の高速な計算方法.pdf - Google ドライブ

test.py - Google ドライブ

このような形で余談を発表する人も多く、最終回らしい名残を惜しむようなゼミになった。最後に先生に促されて全員がカメラをオンにしたりして、なるほど1年間の終わりなのだと実感を得た。

ゼミが終わってからもまたハーメルンを読み続けて、午後6時半に1作読了。「ヒエヒエの実を食べた少女の話」。

syosetu.org

これも非常に面白かった。相変わらず主人公最強で最高。こちらの主人公はどちらかというと善で、残酷な描写に苦しめられることもなかった。しかし直前に読んだ作品もこの作品も、主人公はロジャーが生きていた時代から海賊として活動している。その経歴があってこそ主人公が最強の状態で原作の時間軸に突入できるのだが、過去編も新世界の話もよく分からないのはやはり寂しい気持ちがある。また原作の流れに合わせるためにどうしても発生せざるを得ない事件も多く、止められたはずなのにと苦しくなったりしがち。

そういえば今日の朝方にHHKBが届いていた。ABC235の商品である。早速開封して、サブのUbuntu機に使っていなかったBluetoothドングルを差して接続してみた。

ただ設定にかなり手間取った。メイン機では左Ctrlを英数キーに、左FnをCtrlに置き換えて使用しているので、それに合わせたい。英数キーを押したとき、一般に半角/全角キーを押したように入力を切り替えられるようにしたいが、そのままでは半角英数に切り替わってしまった。Mozcのプロパティから半角/全角キーと一致するように英数キーの挙動を変える。どういう原理かはわからないものの、とりあえずIMEの有効化・無効化を割り当てればよいらしい。それをして完了かと思いきや、なぜか毎回CapsLockが発動してしまう。ここでCapsLockキーを無効にするとダメで、英数キーも無効化されてしまった。調べたところ以下のブログ記事が見つかった。英数キーになぜかCapsLockキーが同時に割り当てられているようで、設定ファイルを弄るとようやく意図したとおりの動作になった。

mac/linux/windowsに全対応した日本語入力切り替えキー - yhara.jp

日付が変わるくらいまで日記を書いて、それからハーメルンを読み始め、午前3時半就寝。

「論理華金」というツイートを見て、明日が祝日であることに気づいた。生協に予約していたラノベが届いているのに今日受け取り損ねたので、来週を待たねばならないようだ。残念。

02/11(金)

午後0時半起床。横たわったまましばらくハーメルンを読んでいた。

今週末は生協の弁当配達が休み。手軽に食べられるものが欲しいと思ったので、コンビニに行ってパン類を大量に買ってくることにした。普段は菓子パンをたくさん買うところ、今日は値段を気にして食パンも買うことにした。そのまま食べるのはさすがにうれしくないので、練乳も買った。これさえあれば今後食パンを買ってくるだけで甘い食べ物を生成できるということになる。

帰宅してインターンのコーディングを始める。今日は1on1が予定されているので、それに向けて何かしら進捗を産んでおきたい。今週はレポート締め切りがあったりゼミがあったりであまり動けないかもしれません、ということを言ってはいたが、結局ハーメルンに吸い込まれてレポートを消し飛ばしてしまったため、何の言い訳にもならなくなった。まあハーメルンを読んでいなかったらレポートをしていたはずなので、どちらにしても今週は動けなかったということにならないだろうか。論理的に考えればそうなるものの、ハーメルンのせいで稼働できなくなるという事実についてはかなり申し訳なさがある。

調べものばかりであまり進まないうちに1on1に突入。自分でもよく整理できていないことをいろいろ言って微妙な感じにしてしまった。作業中に1on1が始まっただけであって別にどこかで詰まっているわけではないのに、何とか見栄を張ろうとして「〇〇が難しいです」とか言ってしまう。少し調べたら解決することなのに。そうこうしているうちにかなりコミュニケーション不全という感じになって、そもそも自分が考えている設計を共有できていないようだったので、メンターさんが僕があれこれ言うのを書き留めた設計スライドを作ってくださった。

来週火曜日に次の1on1を設定して終了。今日の1on1はメンターさんが祝日でもOKですと言っておられたので入れてもらったのだった。社交辞令はわからないので、OKと言ったらOKだろうという精神。

その後ハーメルンを読むのを再開して、1作読了。「海賊らしからぬ海賊」。あまり好きではなかった。原作で最強格のキャラがホイホイ主人公の言うことを聞くのがあまり受け入れられなかった。ドンと構えていてほしいという気持ちがある。主人公はめちゃくちゃ強いし懸賞金も高いので、文句なしの主人公最強モノではある。ただそれだけで面白く感じられるというわけではないらしい。

syosetu.org

しばらくコードゴルフをしてから、TUPC2021のテスター作業を始めた。何時間か経って、しばらく考え込んでいたらうっかり椅子の上で意識を飛ばしてしまったので、急いでベッドに移動して就寝。午前2時だった。

02/12(土)

午前9時半起床。

2021年のCGRの結果が出ていた。自分は25位で、パーカーには惜しくも届かず。6回中4回ポイントがついているのはかなり良かった。ただそうやって定期的にそれなりの順位を取るよりは、1回でも高い順位を取ったほうが合計ポイントが高くなる。なかなか難しい。

Codeforces Global Rounds 2021: Final Results (GR13-GR18) - Codeforces

昨日の続きで夜までずっとテスター作業を行っていた。その合間の出来事が2つある。まず、正午にAHC008が始まった。

MC Digital Programming Contest 2022（AtCoder Heuristic Contest 008） - AtCoder

夕方、藤井聡太五冠が誕生したことを記念して「りゅうおうのおしごと！」が5巻まで半額になっていた。さすがに無料公開ではないらしい。5巻はシリーズの山場で最高に良い。

最近、藤井聡太竜王の四冠記念で4巻まで期間限定で無料公開されていました。もし五冠を達成したら5巻まで無料公開されるのでしょうか。そこまででもぜひ読んでほしいシリーズです。

今年読んだ本のまとめ - kotatsugameの日記

テスター作業が一段落してから、AlphaCodeのpreprintを読み始めた。これを要約して、来週月曜日のインターン先勉強会で発表する予定。しかしかなり難しい。機械学習のことをほとんど何も知らないので、モデルや評価の細かい話が全然分からない。とりあえず大本になっているtransformerというのは検索して調べておいた。

Competitive programming with AlphaCode | DeepMind

午後9時からABC239……のはずが、10分ほど前にAtCoderのサイトに繋がらなくなった。DBへの負荷が原因らしい。まず1時間延期されて、CGRと被るが大丈夫かと心配していたら中止になった。来週また行われるようだ。そうして空いた時間でpreprintを読み進めて、午後11時半からCGR19に出た。

Dashboard - Codeforces Global Round 19 - Codeforces

Aは、数列がソートされていなかったら、ソートした数列と異なる要素のうち先頭のものの直後で分割すればよい。よってソート済みかどうかをチェックする。Bは区間を伸ばすより1個ずつに区切ったほうが得なので、各部分列に対するvalueが部分列の長さと含まれる0の個数を足したものとなる。これをすべての部分列に対して求める。O(n^3)が通る制約なので愚直に求めたが、結局0が何回カウントされるかさえわかればよいのでO(n)でも解けるはず。Cは、奇数の山にはどこかから1持ってくる必要がある。持ってこれる条件を整理すると、真ん中が全部1かN=3かつ真ん中が奇数なら-1で、それ以外は\sum_{i=2}^{N-1}\lceil a_i/2\rceilとなることがわかる。オーバーフローで1WA。Dは式を整理すると答えが(n-2)\left(\sum a_i^2+\sum b_i^2\right)+\left(\sum a_i\right)^2+\left(\sum b_i\right)^2になって、右2項の最小値を求めるには部分和dpをすればよい。

Eはcntの種類数がO(\sqrt n)になるので、組み合わせを全探索してもO(n)になる。cnt_xとcnt_yを固定すると、後はx+yを最大化すればよい。xの降順に見てyの降順に調べる。badでないペア(x,y)が見つかったらxを次のものに進めることと、最大のyにペアができたらxの探索を終了することを行えば、全体の探索回数がO(m)で抑えられるので間に合う。badなペア(x,y)の管理はTLEが怖かったのでvectorで行った。cnt_xに対して(cnt_y,-x,-y)を昇順に持っておくと、昇順にcnt_yを固定するとすれば探索中の要素がこの順で出現するので、先頭から比較していくことでbadなペアを検出できる。Fは、まず塔を建てるのは葉だけでよいとわかる。\max h_iがefficiencyとなるような塔が2本あって、それ以外の頂点はその塔のうち1本と別の塔によってカバーされることになる。そのような塔のefficiencyは、{\rm argmax}\;h_iを根とし、部分木にある塔のefficiencyの最大を持つような木dpをすれば求まる。最後に\max h_iがefficiencyとなる塔を2本用意して終了。

Gは、実験すると2べきに揃えるのだろうと予想がつく。N\ge 3なら必ず可能。N以上で最小の2べきの数を2^bとしたとき、2^bがN-1個と0が1個作れる。0を使うと2手で値を2倍できるため、つじつまを合わせつつ再帰的に解く。まずN=2^bの場合はN\leftarrow N-1に対して解けばよい。そうでないとき、r=N-2^{b-1}とすると、2^{b-1}+1,\dots,Nと2^{b-1}-1,\dots,2^{b-1}-rを一対一対応させることで2^bと2,4\dots,2r=(1,2,\dots,r)\times 2が得られる。さらにs=2^b-N-1として1,2,\dots,sも余る。r\ge 3またはs\ge 3ならば0を作ってこれて、もし1や2が余ってもそれも2べきなので、0を使って値を倍々にしていけば求める2べきの値に揃えられる。そうでない場合はN\le 6なので、手で回答を作って埋め込む。少し前のCodeChefの問題を思い出すような方法だった。

NN以下で最大の2べきを2b2bとすると、2b…N2b…Nと2b−(N−2b+1)…2b−12b−(N−2b+1)…2b−1（の逆順）を対応させることでbitwise ANDが0であるようなペアばかりを作ることができ、その上残りもまた1…N′1…N′の形をしている。

週記（2022/01/24-2022/01/30） - kotatsugameの日記

7完21位、レートは2735→2849(+114)。前回の-156が大きすぎる。

布団に入って寝る前にハーメルンの更新をチェックしていたら、耐え切れず寝落ちした。午前5時だった。

02/13(日)

午後0時半起床。ハーメルンを読んだりYouTubeを見たりした後、布団から出た。

結構前に「今日ヤバイ奴に会った」というチャンネルの動画をいくつか見ていたことがある。インドの屋台飯を扱うYouTubeチャンネル。コロナウイルス感染症拡大の影響で撮影ができなくなったという説明動画を最後にしばらく見ておらず、今日久しぶりにおすすめ動画に登場した。今はもう結構普通に撮影していて驚き。ただチャンネルの投稿動画を見てみるとコロナ禍の中でもちょくちょく新しい屋台が出ているようなので、ただ自分の興味が離れていただけかもしれない。

www.youtube.com

昨日の続きでAlphaCodeのpreprintを読む。昨日は4章の途中で止まっていた。この4章前半が学習についての細かい話で、予備知識のなさに絶望したものだったが、それ以降は正答率の評価や改善が話のメインになってかなり読みやすくなった。集中を切らしつつもどんどん進んでいって、夕方、6章まで一通り読み終えた。7章から9章は読み物なので飛ばしてよさそうで、10章の付録は時間がなく読まないことにしたため、これでとりあえず発表スライドを作る準備が整ったと言えるのではないだろうか。

ラノベの新刊チェックと予約をした。とりあえず03/01発売までの19冊。3月に入ってからは大学生協の営業時間がどのようになるのかわからないし、自分の帰省がいつになるかも決まっていないので、確実に受け取れそうな発売日のラノベだけ予約したということ。参考までに昨年3月の営業時間を調べようと思ったら、生協の営業時間告知ページはファイルが上書きされているようで見られなかった。Googleに残っていたキャッシュによれば、普通に営業していそうではあるが。

午後7時から負荷チェックコンテストに出た。

負荷チェックコンテスト - AtCoder

とりあえずseq 20で最短を取る。あとは1要素ずつ三分探索でもすればいいかなと思って適当にポイポイ投げていた。3要素目くらいで、最小・最大の2数に対する結果が分かれば復元できることに気づいたので、残りはそれで埋めた。計算が面倒だったので、各要素が決まったらその状態での点数確認（これは本来前の結果から求まる）のため提出していた。そのため満点を取った時には56ペナついていた。26位。

ハーメルンを読んで時間を潰し、午後9時からARC135に出た。

AtCoder Regular Contest 135 - AtCoder

Aは実験すると2と3だけになるまで分割するのがよさそう。k回目の分割では\lfloor X/2^k\rfloorと\lceil X/2^k\rceilの形の数しか現れない、ということがAGC044Aで出ているので、同じ数をまとめれば十分高速に計算できる。まとめるというか本当はメモ化再帰するだけで良かったのに、何を考えたかmapで分割をシミュレートしたりしてちょっと実装に手間取った。BはS_{i+1}-S_i=A_{i+3}-A_iなので、A_{4\dots N+2}をA_{1\dots 3}からの差分で表せる。これで各A_iが正になるために必要なA_{1\dots 3}の最小値が求まるので、A_1+A_2+A_3=S_1を満たせるかどうかをチェックすればよい。Cは実験すると2回以上の操作が無意味だとわかる。その前に上の桁の多数決など考えていたので、1回しか操作しなくてよいことが分かってからもそのまましばらく考え込んでいたが、実は操作後の総和がbitの各桁を見るだけで求まるので、操作に使う数を全探索できる。

Dはよくわからなかった。なんとなく右と下に押し付けるとよさそうと思ったので手で実験してみると、どうやら各行各列の交代和が現れるらしい。最小性について、よく見ると操作で交代和が保存されるので、操作後にどのようなA_{i,j}'になっても\sum_{j=1}^W |A_{i,j}'|\ge\left|\sum_{j=1}^W (-1)^jA_{i,j}'\right|=\left|\sum_{j=1}^W (-1)^jA_{i,j}\right|、つまり実験で出てきた交代和がi行目だけ見た時の最小だとわかる（ただしこれは全体が最小値であることを必ずしも意味しない）。押し付ける行と列を全探索しようと思ってしばらく考えるも、最後の微調整が必要そうで難しい。ここで、行と列に押し付けようとすると、行だけ・列だけ見た時の最小性は満たされるが全体としての最小性は満たされないことに気づいた。代わりに不変量となる交代和に注目して、それを作るように数を配置すればよさそう。市松模様のように符号を反転して考えると、ARC133Cの証明っぽく貪欲に置いていくことで最小値が達成可能。交代和が保存されていれば構築可能であることは示さなかったが、どうせできるだろうと投げたら通った。解説でその証明を見て納得。

C - Row Column Sums

残り時間はEを考えていた。実験してみると途中から等差数列になるようで、それがスタートするインデックスがだいたいO(\sqrt X)で抑えられることも分かった。しかしこれでは、割り算を含むループなので6secでもさすがに間に合わない。高速化の手がかりが掴めないままコンテストが終了した。4完34位。

コードゴルフ。Aはメモ化再帰ということで素直にRubyで実装する。CもRuby。他は手付かず。

明日の勉強会で発表する予定の、AlphaCodeのpreprintの要約だが、それなりに頑張っているので発表スライドを公開しようと思っていた。著作権が気になっていろいろ調べてみたところ、どうにも要約は著作物の「翻案」に当たるようで結構注意を払う必要があるらしい。今読んでいるpreprintの著作権の扱いがDeepMindのページを見てもよくわからなかったため、微妙に怪しいかもしれない。図表をコピペしないということで何とかならないだろうか。

今週の週記は短めだった。週前半をハーメルンに吸い取られたのが効いている。文字数的には200万文字以上読んでいるので身動きが取れなかった一方、ネット小説を読んだ感想はどんなに長くても1作品ごとに書いているので日記の文字数に貢献しない。まああまり長くても読みづらいだろうし、編集画面が重くなったりするので、短いことは悪いことではない。

週記（2022/01/31-2022/02/06）

01/31(月)

先週の週記を投稿してからの話。まず本を1冊読んだ。

「犯罪社会学者・椥辻霖雨の憂鬱」2巻。1巻の内容をほとんど覚えていなかったが面白かった。相変わらず主人公のキャラが立っていてよい。過度に理論的で人情を解さない（と周囲から思われる）ようなスタイルを格好いいと感じる。この巻では事件の加害者に焦点が当てられていた。特にネット上での誹謗中傷の描写などは、最近Twitterでも問題になっているのを見る分リアリティがあって辛かった。取り扱う事件こそ1件であるものの、登場人物たちがそれに対して様々な関わり方をしており、そのうちの誰に肩入れしても上手くはいかないのだと思わされた。そのようなバランスも含めて、取り扱いの難しい題材である。そう後書きにも書いてあった。

自分の中でのバランスも難しいところで、事件の内容を聞いて義憤に駆られることもあれば、過度な反応を諫めるツイートに納得することもある。後者は特に、少し前に話題となったいわゆる「上級国民」の事件に関するツイートで「あまりにネット上で叩かれるとその分刑が軽くなる可能性がある」との言説が記憶に新しい。いや、これに納得すること自体も、すでに「できるだけ重い刑罰を求める」という心理が根底にあるのかもしれない。一応言っておけば、自分が納得しているのは「ネットで叩かれることが情状酌量の余地となる」ことであって、当の事件自体にはあまり関心がない。それもそれで問題か？

https://www.itmedia.co.jp/news/articles/2110/21/news070.htmlwww.itmedia.co.jp

「悋気は女の慎むところ、疝気は男の苦しむところ」という言い回しが出てきた。悋気はわかるので、前半の言っている意味はすんなり理解できる。しかしどうも後半が全然わからない。「疝気」という病気があるらしいが、そこから何か別のもの、例えば物の考え方についての意味が派生して、全体として男女の違いの格言になっていると考えていた。しかし調べても出てこなかったので、結局疝気は男性特有の病気という意味そのままで、後半部分はただ対句でリズムを取っているだけだという理解に落ち着いた。

学食に行って食事し、菓子パンを購入。今日は購買にたくさん菓子パンが並んでいたので、普段遠慮して2つしか買わない商品を3つ買ってきた。帰宅して、眠気が強いので一瞬寝ることにした。先週もほぼ同じ感じで徹夜に失敗して寝た。その時の経験から、ダメそうなら早めに寝てちゃんと睡眠時間を確保しておくほうが良いとわかっている。午後1時半から午後4時半（のちょっと前）まで寝ていた。つまり、インターン先定例会ギリギリまで起きられなかったということ。

先週の進捗もスカスカのカッスカス。ショボいことを書いて、あまつさえ今週はレポートの締め切りがあるので……など逃げを打つ始末。はっきりモチベが失われているのを感じる。これまでの人生では徹頭徹尾自分の好きなことしかやってこなかったので、興味の対象から少しでも離れると一巻の終わりらしい。労働に向いていない。先週水曜日のペアプログラミングの結果、もうそろそろしこたまコードが書けそうな気配なので、何とかもう少し踏ん張りたい。明日火曜日の1on1に期待。

コードゴルフを1問。ABC237-Cが縮んだ。最初に左側に'a'を大量に追加しておいて、そのようにして作った文字列に元の文字列を逆から読んだものが含まれるかをチェックすればよいらしい。こうすることで、左端から連続する'a'が右端から連続する'a'の文字数以下であることと、真ん中の部分が回文になっていることが同時に確かめられる。Perlのindex関数で実装した（下の提出では文字列を全部逆向きにしている）。すんなり通ったので最初は気づかなかったことだが、冷静になると106文字程度の文字列検索を行っている。残念ながらRubyやPythonではTLEしてしまった。しかしPerlで書いたほうがそのTLE解より短くなったので問題なし。

atcoder.jp

ラノベを2冊読了。1冊目は「神狩1〈下〉」。上巻を読んでひと月も経たないうちに内容を忘れてしまい、厳しい。展開に驚かされると聞いていたのでわくわくして読んでいた。実際オッと思うようなものがあったとは言え、その驚きは単発のものであって、ストーリー的にもすぐ元の状態に戻ってしまい残念。上巻では正直振るわなかった主人公が無双しているのはよかった。全体としてあまり肌に合わない。

2冊目は「カワイイけど慎重すぎるお嬢様の笑わせ方」。主人公とヒロインが似た者同士で意気投合するという馴れ初めだが、あまりに気が合うせいか会話がハイコンテキストすぎて非常に読みづらい。主人公はよくわからないところでジョークを交えるし、ヒロインもよくわからないところで芝居がかって主人公に甘えて見せたりする。ただ、その読みづらい文章からでもヒロインの可愛らしさは感じ取れた。読者すら入り込めない二人だけの空間をそっと見守っていると考えればいいのだろうか。

1月はつい最近まで頑張って1日1冊ペースを超えていたはずだったのに、一瞬ハーメルンに囚われた結果すべてが崩壊。しかし今日、物理的に薄い本（250ページ前後）ばかり3冊読んだことで、今月はピッタリ1日1冊で終えることができた。記録を調べたところ2020年12月以来らしい。

少しコードゴルフをして、午前2時就寝。

02/01(火)

午前9時起床。二度寝に失敗した。1月の読書の集計をツイートした。

微妙な眠気でボーっとしつつ、レポートのため講義動画などを流し見ていた。昼過ぎに学食に行って食事し、散髪して帰宅。帰ってきたら先月の電気料金のはがきが届いており、年末年始で丸々一週間いなかったはずなのに電気代が10000円に届こうとしていてビビった。しかしよく見ると昨年同月と使用量がほぼ変わっていなかったため、ただ電気料金が値上がりしただけだと判明して一安心。インフラの単価は気にしてもしょうがないと考えている。

午後3時くらいからインターン関連のコーディングを始め、1時間の1on1を挟みつつ午後10時過ぎまでずっと頑張っていた。今日はかなり手が動いたというか、興が乗ったというか。今はエクセルファイルをPOIで扱っている。ここで、2つのブックをマージする必要が発生した。方法としては、あるブックから別のブックにシートをコピーできればよい。簡単なことだと思っていたし、実際そういうことをしたい人はたくさんいるようだったが、特別な関数は用意されておらず、いくつかそれを行うためのコード片が見つかったのみだった。しかも結構難しいらしい。

ブックをまたぐシートのコピーの難しさについて。POIでは……というかエクセルファイルという形式自体が、ブック、シート、行、セルの相互の連携によって表現されていることが問題。つまり、シートをコピーするには（あるいはセルをコピーするだけでも！）ブックの関係する要素を引っ張ってくる必要があるのだ。当初はセル自体からブックまで遡って取得できる設計の意味が分かっていなかったが、セルの書式に関する仕様を知って納得した。セルの書式は、セルに紐づくものではなくブックに紐づくものらしい。だから、単純にブックをまたいでセルをコピーしようとすると、該当する書式がコピー先のブックにないと言ってエラーが出る。対処法としては、書式をブック間でコピーした後にセルにコピーした書式を設定するというものだが、これに関しても簡単にはいかない仕様上の問題がある。一つのブックが保持できる書式は高々4000個程度にとどまるのだ。つまり、セルごとに新しい書式を作っていては到底足りないのである。だから、書式をコピーする際は同じ書式を複数回コピーしないよう、適切にMapなど使ってコピー済みの書式を取得してくる必要がある。

ここまでしてようやく、セルのコピーが可能となる。あとは行の設定のコピーをし、シートの設定のコピーをする。設定のコピーは、おおよそセッター・ゲッターが存在するありとあらゆるフラグをコピーすることで実現されて、公式ドキュメントとにらめっこして地道にコーディングしていった。と、ここまでコーディングしてから、シートに設定されたオブジェクトやブックが持っている設定のコピーが難しいことに気づいた。オブジェクトは単純に仕様がよくわからないので難しい。ブックの設定のコピーは、コピー先のブックの設定とかち合った場合どうするかという問題がある。結局、どうしてもすべての設定を保存したいブック自体をコピーして、それに今までの方法で微妙にコピーしきれないシートを追加することでマージを行うという設計にした。これが現実的で、限界でもある。

CodeChefのどこかのコンテストでいい成績を残したので、100USDがもらえるらしい。メールから飛べるフォームに個人情報を入力する必要がある。顔面の写真など、ちょっと怯むものもあったが、問題はSNSのアカウントについて。Twitterやfacebookはよいとして、LinkedInやInstagramのアカウントを入力する欄があり、しかも回答必須項目になっている。バカじゃないの？ただ、面倒さよりお金の欲しさが上回ったので、いい機会とアカウントを作ることにした。

LinkedInは問題ない。しかし、Instagramのアカウントを作成した瞬間ロックされてしまった。謎。個人的には、認証コードのメールが届くのが少し遅かったので再度要求した後、初めに届いたメールのほうのコードで回答してしまったからだと思ったが、確認すると届いたメールは2つともコードが同じだった。ともかく、24時間くらい待つ必要があるらしい。

IDは取得できていると思うので、それを入力してフォームを送信した。パスポートのコピーも必要だったのでスキャンを行った。これは高3のときにIOLに行くため作ったパスポートであり、有効期限がかなり近づいていることに気づいた。その更新もしたいと考え、住民票が地元にあるまま仙台で手続きできるか少し調べていた。一応できることにはできるらしい。ただ住民票が限定された形でしか取得できないようで、これについては不安が残るため、親に取って送って貰いたい。

しばらく布団に転がったりコードゴルフをしたりして、午前5時半就寝。

02/02(水)

午後0時半起床。学食で食事し、予約していた本を受け取って帰宅した。帯が少し破れていてかなり微妙な気持ちになった。

ラノベを1冊読了。「宅録ぼっちのおれが、あの天才美少女のゴーストライターになるなんて。」。良かった。ヒロインの一人のことを狙っているイケメン男子生徒がおり、彼もバンドを組んでいた。いかにも主人公に嫉妬してギスギスしそうな設定で警戒していたが、実際はかなりいいやつで、ヒロインの気持ちが主人公に向いていることをちゃんと認めるし、主人公も最初は彼の技術だけを見て軽んじていたのに、最終的には彼なりの表現に気持ちを揺さぶられていた。主人公はボッチで作曲していたのでバンドの楽器を一通りできるという設定があり、主人公無双チャンス！と思ってしまった。この本にはそういう描写はない。

今読んだシリーズの2巻を今日受け取ってきた。それを読み始めたが、うっかり布団で力尽きた。午後4時半くらいに寝落ち。

02/03(木)

02/02 午後10時半に起床した。

そろそろInstagramのアカウントがロックされてから24時間が経過するころだった。まだかまだかと待っていたら、ちょうど24時間くらい経ったあたりでロックどころではなくアカウント停止になっていた。不服を申し立てようとすると、サポートから来たメールに特定の文字列を手書きした紙と一緒に写った自撮りを返信しなければならないらしい。海外の犯罪者の写真みたいで非常に気分が悪い。送ってもどうしようもない、という体験談がリプライされてきたりしたが、ダメもとで送ってみることにはした。

午前1時からSRM823に出た。

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

Easyは簡単。2回連続でジャンプするのと1回大きくジャンプするのが完全に等価なので、現在地に加えて今どの方向にジャンプ中か、あるいは一切ジャンプしていないかの5状態を持ってBFSすればよい。これでO(HW(H+W))になる。直前でジャンプした距離を持ってもO(HW(H+W)\max(H,W))になるだろうが、こちらは定数倍で落ちてしまうのだろうか？もしかしたら考察は一切問うていなくて、実装だけで点数がついているのかもしれない。

Medはかなり難しく、面白かった。面白かったのは自分が解けたからかもしれない。Dで昇順ソートして、各点を終点にするようなパスを1本ずつ管理し、伸ばしていくことを考える。すると、ある辺を処理する際はパスが2本選ばれ、互いに1辺ずつ伸びて終点が交換されることになる。このような操作を繰り返すと、N本のパスが合計で2M回伸びることになる。今\frac{2M}N\ge \frac{2\times 10N}N=20なので、どれか1本のパスは処理の結果長さ20を達成できる。実装の時はまだ正当性を信じ切れていなくて、パスの終点を交換するときにそれまで作ってきたパスと長さを比較して長いほうを取ったりしていたが、まあそれでも問題はない。

Hardは簡単。約数を列挙して、それらの間の約数・倍数関係でdpをすればよい。N\le 5\times 10^{12}なので、d(N)（約数の個数）は最大で10^4個くらいになる。dpにO(d(N)^2)かけるのはちょっとまずいかと思って、素因数を列挙して細かく求めたりしていたら時間がかかってかなり点数を落としてしまった。しかも実際にはO(d(N)^2)で通るらしい。残念。

そういえば、火曜日の部分に書いたCodeChefの賞金の件はうしさんのツイートを見て気づいたのだった。ところが今、うしさんの賞金が手違いだったというメールが来たらしい。自分も実は手違いで顔面の送信しただけ損だったか……と思いつつメールをチェックしたところ、そのようなメールは届いていなかったので一安心。どうやら賞金を貰ったコンテストが異なるらしい。それにしても、いつの間に賞金付きのコンテストに出ていたのだろうか。コンテストのトップページを調べてみても特に賞金に関する言及がないので、もしや詐欺メールかとも思いかけた。しかしリプライでCodeChefの毎月行われるdiv.1コンテスト2つ（Lunchtime、Cook-Off）には毎回賞金がついていると知り、驚き。上位10人に100USDらしい。

How do I win a CodeChef Goodie? - #2 by admin - faq - CodeChef Discuss

ラノベを1冊読了。「宅録ぼっちのおれが、あの天才美少女のゴーストライターになるなんて。」2巻。前の巻にも増して良かった。後書きで知ったことだが、もともと文庫本2冊くらいの分量があったものを1冊にまとめたらしい。確かに様々なイベントが続けざまに描かれる濃厚な1巻だったと感じた。前半は入り乱れた恋模様だったり過去の出来事が影を落としたりで、微妙に辛くなりながら読んでいた。しかしそれも濃縮された文章でスッキリ解決して押し流されていき、最後の文化祭のシーンは屈託なく楽しむことができた。ステージに登場するそれぞれのグループに感動的な描写があり、このあたりの畳みかけるようなエモさも濃厚さの一つか。

朝方、計算物理学のレポートを書き始めた。時間軸以外に2次元以上あるような偏微分方程式を自分で設定し、数値計算で解くもの。講義動画で見た波動方程式による波のシミュレーションが綺麗だったので、それを扱うことにした。しかし普通にやっても講義動画のコピーにしかなりえない。そこで最初は球面上の波をシミュレートしたいと考えていた、のだが……講義で学んだ方法では不可能だと気付いた。グリッドの縦横隣接するマスから値を集めて次の瞬間の値を計算するのだが、球面に等間隔のグリッドを設定することができない。ビジュアライズしたら綺麗だっただろうなと悔しい気持ち。波のシミュレーション自体はすでにコーディングしてしまったので、残り何とかそれっぽいことを書いてレポートを締めたとは言え、結局講義動画のコピーになってしまった。

ともかくレポートは終わった（ことにした）。ラノベをもう1冊読了。「陰キャだった俺の青春リベンジ」。かなり良かった。高校生活を後悔している人が逆行してもう一度やり直す話ということで、つい2月前に似たような設定のラノベを読んだ気もするが、まあ逆行モノはいくらあってもよい。ただいろいろ違う点もあって、最も大きなものとしては高校2年生からやり直すためすでに主人公の評価が定まっていたということが挙げられる。前半はその評価を覆していく描写から始まって、後半は文化祭におけるクラスの出し物を、社会人生活で培った能力で成功に導くというもの。これはもう好みど真ん中である。↓のハーメルンを思い出した。

syosetu.org

逆行して得られるチートは、未来知識を利用するものと未来で身に着けた能力を利用するものの2つがあると思う。前者のほうが強力ではある一方、自分が知っている時点までたどり着いてしまうという動かしがたい終わりが存在して何となく不安になる。一方後者はそういう不安がないという点で好みなのかもしれない。未来知識をもとに、破滅を回避するため努力して能力を身に着けるという展開もあるが、それはほとんど「転生したけど意識があるので小さいころから訓練できていました」という展開と一緒で、逆行だけのものではなくそこまで好みでもない。

インターン先から技術書を貸与してもらった。分厚くて怯んでしまう。

コードゴルフをした。以下\bmod 10^9+7で考える。フィボナッチ数列を行列累乗で求める問題は、行列累乗を短くするしかない。一方、それに似てa_{n+2}=2a_{n+1}+a_nなる漸化式を持つ数列に対しては、もっと違う方法があるらしい。まずこの三項間漸化式を解くと、a_n=\frac{(1+\sqrt 2)^{n-1}+(1-\sqrt 2)^{n-1}}2という式が得られる。ここまではフィボナッチ数列とほとんど変わらないが、フィボナッチ数列においては\sqrt 5が登場する一方でこちらは\sqrt 2が登場する。実は、10^9+7を法として5は平方非剰余だが2は平方剰余なのだ。つまり、いま求めた閉じた式を直接計算することができる。

2乗して2になる数は59713600と940286407が該当する。ここで、1+\sqrt 2\equiv 59713601と1-\sqrt 2\equiv 1-940286407\equiv 59713601を選べばもっと簡単な式になると考えたのだが、合わない。冷静になるとそれはそうで、\mathbb{Q}[\sqrt 2]\simeq\mathbb{F}_{10^9+7}という同型があるのだから同型ではなく準同型であった（2022/05/17追記）2つの数のうちどちらかが\sqrt 2になるともう片方は-\sqrt 2にならなければいけなかったのだ。

atcoder.jp

布団に入って少しハーメルンを読み、午後8時半就寝。

02/04(金)

午前7時起床。そこから二度寝に失敗し続け、午後3時半までずっとハーメルンを読んでいた。

途中で少しコードゴルフをした。今日は横に長いマス目を1x2のタイルで敷き詰める方法を数え上げる問題。想定解は1列の状態をbitで持つDPを行列累乗で高速化するものだろうが、マス目の行数を固定してOEISに投げるとそれぞれ漸化式が見つかる。閉じた式はなさそうだったのでどちらにせよ行列累乗で解くとは言え、2^K\times 2^Kの行列だったものが高々4\times 4に収まるのは嬉しいところ。遷移行列を埋め込んで縮めた。その遷移行列や初項の値も結構共通部分があって、頑張って式を作ると単純な3項演算子で分けるよりいくらか短くなった。

atcoder.jp

今日はもともとゲーセンに行くつもりだった。朝から起きていたので眠気があり、しかも夕方になってしまったのでかなり迷ったものの、結局行くことにした。途中イオン地下のフードコートでうどんを食べて、午後5時から午後9時半まで遊んだ。眠気が強くなったので閉店より前に帰宅を決めたという感じ。成果は新曲を埋めたのと、あとはケルン氏と会ってしばらくマッチングをした。14の未SSS+が残り2譜面になった。

これまでB判定-1.0くらいにずらしてもFASTが出まくっていたのがさすがに気になっていた。最近フィールドウォールを設定するとよいと聞いて試してみた。まだ自分に合う判定がどこか明確に分かってはいないものの、フィールドウォールを1にするだけでB判定-0.6くらいにはなるようだ。このくらいなら普通かな、という感じ。それにしても、画面上でほんの1センチ程度見えなくなるだけでこうも変わるものかと驚きである。速度もいくらかいじってみるといいかもしれない。

立ち食い蕎麦を食べて帰宅。羽生善治九段が順位戦A級から陥落したというニュースがTLに流れてきた。将棋ラノベなどから順位戦に関するルールを知って、こういうニュースの解像度が上がって印象に残るようになった。午後11時半就寝。

02/05(土)

午前6時半起床。今日も二度寝に失敗して、夕方までハーメルンを読み漁っていた。順に書く。

syosetu.org

「小学生に逆行した桐山くん」読了。ここ数日読んでいたもの。3月のライオンは原作を全く知らないうえに主人公が原作知識ありで逆行しているので、出てきたばかりのキャラをやたら警戒したりしてびっくりした。その辺りもちゃんと後々わかってくるような書かれ方をしているので、読みやすいほうではあるのかもしれない。話は一気読みしてしまっただけあってかなり面白かった。

最新話まで追いついている作品をチェックしていたら、「東方遺骸王」が更新されていた。602話にしてついにスカーレット姉妹が登場した。父となったキャラは結構昔から出ているオリキャラで、吸血鬼だとかそんな素振りは全くなかったのでびっくり。またこれで原作の500年前に到達したということで、かなり感慨深い。

syosetu.org

syosetu.org

「ソードアート・オンライン　ラフコフ完全勝利チャートRTA　2年8ヶ月10日11時間45分14秒(WR)」読了。主人公が悪人側なのでかなり胸糞悪い描写も多かったとは言え、面白かった。途中でエタっている。まだ致命的な崩壊には至っていないので、序盤の地盤固めなど後々裏切るためだろう行動を素直に楽しめた。その点ではここで止まっていてくれて助かったという感じ。

syosetu.org

「トレーナー、仕事辞めるってよ」読了。上の作者の別作品。面白いことは面白いが、これも救いのない話が多く大変だった。そういうのもたまにはいい。

生協の冷凍弁当を受け取って、午後5時前に再度寝た。午後8時半に目覚ましで起きて、食事してABC238に出た。

Monoxer Programming Contest 2022（AtCoder Beginner Contest 238） - AtCoder

Aは小さいところだけそのまま比較しようと思って少し計算したら、答えがNoになるのが2\le n\le 4のみであることに気づいた。sedで書いた。Bは適当に。CはN以下の正整数を桁数ごとに分けるとそれぞれfの和を計算できる。Dはx+y=(x\;{\rm OR}\;y)+(x\;{\rm AND}\;y)が成り立つので、x\;{\rm OR}\;yがx\;{\rm AND}\;yをbit的に完全に含んでいるかチェックすればよい。Eは最近見た気がする。区間の両端を結ぶ辺を張って到達可能性を判定。Fはうっかり正しい解法を捨ててDAGを考えてしまいかなり迷走した。しばらく考えて最初の考察に戻ると正しかったことが分かった。Pでソートして、これまで代表に選ばなかった人のうち最小のQを持つdpを行う。GはMo's algorithmで、うっかり素因数分解を\sqrt Aまでループ回す方法で書いてしまいTLE。ちゃんとエラトステネスの篩っぽく素因数を前計算して素因数分解を\log Aにするのと、3で割ったあまりを何度も取らないようにしたり、クエリのソート順を右端がジグザグになるようにしたりと細かい調整を加えて2度目の提出でACした。Exは区間dpをしばらく考えるも微妙に間に合わないオーダーになってしまって解けず。

コードゴルフ。Aはdcで3を引くことで、答えがNoになる場合だけ値の絶対値が1以下になるためRコマンドが使えるようだ。全然気づいておらず絶望。BはRaku。Cはkyopro_friendsさんの解説の方法で、Nの桁数さえ分かれば和を全部閉じた式で表せる。肝心の桁数はdcにおいてZコマンドで取れるので、かなり短くなった。Dは1行目を読み飛ばす方法に忘れていた改善があってclimpetさんに取られた。EはPerlで書くUnionFindで、これまたclimpetさんにかなわず。Fはdpの遷移をちゃんと整理するとほとんど列をずらすことに言い換えられて、和を取るのは限られた部分のみになる。Rubyで書いておいた。

syosetu.org

「もこたん→青ニート←その他大勢」読了。読んでみたら東方古代スタートだった。以前は主人公がダークソウル由来ということで微妙に避けていたが、よくわからないアイテムの説明もちゃんと入るしかなり面白かった。主人公本人的にはたまったものではないとは言え、やはり不死による圧倒的な長命は良い設定である。幻想入り後すぐエタっているのはかなり残念。

朝方、Pythonの講義の最終課題に取り組んだ。今回与えられたipynbファイルにはデータ読み込み部くらいしかなく、データの可視化・分析・予測のうち何を行うかすら自分で決める必要があるらしい。ひたすら面倒だったのでとりあえず可視化することにして、計算物理学のほうで学んだグラフのアニメーションを多用してみた。やはり自分がちょろっと書いたコードでアニメーションが作れるとはありがたいライブラリである。さらに日本地図を描くjapanmapを見つけてきて使ったりして、データをいろいろな方法で表示すること自体には成功した。ところで、今回扱うデータは新型コロナウイルス感染症に関係するもの。これを可視化しようとすると、最近の感染爆発に対するそれ以前の増減が小さすぎて全然目に見えないということになってしまい、大変だった。今思えばlogスケールにしてもよかったかもしれないが、終わったことなのでもうどうでもよい。

10万ツイートを達成した。

もう昼前になってしまった。今週ずっと溜めていた日記を少し書き、布団に入ってハーメルンを読み始めた。午後3時半就寝。

02/06(日)

午後11時起床。食事せずにCF #770 div.2に出た。AlphaCodeが参加する初めてのコンテストらしく、そういうフレーバーテキストが散りばめられていた。問題文に入っていなかったのは幸い。

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

Aは一回操作すると回文になってもうどちらの操作でも変化しないので、答えは1か2になる。Bは嫌らしいギャグ。まともにやっては絶対に解けない。必ずどちらか一方のみが達成可能という条件がミソで、これは必要条件を考えろということだった。実際、値の偶奇はどちらの操作でも同じ変化をし、初期状態で2人の偶奇が異なるため、少なくとも片方は達成できないことがわかる。Cは各行が公差が偶数の等差数列になっていればよい。これで条件を満たせることはすぐわかるが思いつくのが難しい。実は今述べたことは後から気づいたもので、自分は先頭から貪欲に作ると1,3,5,7,\dotsになるのを知り、さらに公差2なら何でもよいことに気づいて通した。

Dは難しい。最大の要素と最小の要素を更新しつつ列を舐めることを考える。つまり、4つの数から最大と最小を含む3つの数を選べればよい。これは当然クエリの答えが最大になるものを選ぶことになるのだが、よく考えると、4つの数に対するクエリ4種類のうち最大となるのは最大と最小を含んでさえいればいいのだから少なくとも2通り存在する。つまりクエリ3種類の答えを集めれば十分で、新しい要素を舐めるときは古いものの答えを持っていることを考えて追加で2回クエリを投げることで達成される。最初に1回聞く必要があるので、合計1+2(n-3)回のクエリで列全体の最大と最小を含む3つの要素が得られる。あとは3つそれぞれを外してクエリを投げてみて、答えが変わらなかったもの以外の2つ（あるいは1つ）を出力すればよい。合計で1+2(n-3)+3=2n-2回と回数制限にちょうど収まる。

Eは、同じ値でペアにして列の間に辺を張ると全頂点の次数が偶数になるので、適当に向き付けて閉路の集合にできる。始点と終点にそれぞれLとRを割り当てればよい。LとRが多重集合としてではなく集合として一致すればよいと勘違いし1WA。FはまずA'_i=A_i-B_iとし、次にC_i=A'_i-A'_{i-1}-A'_{i-2}と置くことで、クエリによる更新がCの高々3点の更新に言い換えられる。クエリごとにA'が全部ゼロになったか判定すればよくて、これはCが全部ゼロになることと同値なので、1点更新の際にゼロの個数も更新することで定数時間で判定できる。

全完8位。何かの手違いで、今日はAlphaCodeは参加しなかったらしい。そういえば、以下の記事で解けたと紹介されている問題はそこそこ難しめだったので話題になっていた。しかし105要素の列からpop(0)しているのが気になる。何らかの最適化はあるかもしれないが、まずTLEするはずだ。とはいえ、あの問題文からこのコードを生成すること自体信じられないくらいの成果であるのは間違いない。

www.deepmind.com

夜中から昼間にかけてはずっと溜めていた日記を書いていた。ちょくちょくハーメルンに時間を吸い取られもした。最近読んでいるのはこれ↓。ワンピースは80巻くらいから読めていないので、カイドウはビジュアルすら検索するまで知らなかった。先の展開もわからないまま普通に面白く読んでいたのに、ちょくちょくあとがきでネタバレを交えた原作の考察が始まってちょっと残念。

syosetu.org

週記（2022/01/24-2022/01/30）

01/24(月)

先週の週記を投稿してからの話。日曜日に行われたJOIG本選の問題を確認した。ぱっと見た限り3問目まではコードゴルフできそうで、4問目は面倒、5、6問目はそもそも解くにあたって少し考える必要がある。まだAtCoder上に移植されていないので、今は頭を使わずスルーした。

学食に行って昼食を摂り、予約していた本を受け取った。その際下のようなことが起こった。特別扱いされているようで悪い気はしない。

昼食が変なところに入っていったのか、異常な腹痛を抱えつつ帰宅。少しコードゴルフをした。文字列を2進数として解釈するto_i(2)は、hexあるいはoctで置き換えられる可能性がある。具体的には\mathbb{F}_2^nにおける基底を扱う場合がそうで、立っているbitの位置が各数で一様にずれるだけなので計算結果に違いはない。ABC236Fでは基底を持つのではなく生成可能なすべての元を持つことで縮んだことから、ほかの問題でもそういうことが起こらないか探していて気付いた。ちなみにそちらの短縮については、制約が小さくともn\le 300となっており、生成可能な元が超大量にあるためうまくいかなかった。

atcoder.jp

ハーメルンを読んでいたが、あまりにも眠い。本当はこのままインターン先定例会まで起きているつもりだったところ、さすがに耐えきれないと判断して午後2時くらいにベッドに倒れこんだ。

ちゃんと30分おきに目覚ましをかけていたのに、起きたら午後4時半、定例会が始まるちょうどの時間だった。先週と同じく焦りながらミーティングに接続。何とかギリギリ遅刻ではないような感じになった。先週金曜日の1on1から今日までに何らかの進捗を産もうとして、それで日曜日から今日にかけて徹夜っぽいことをしていたのに、実際はハーメルンを読んだりコードゴルフしたりで真に何もしていない。うっすい進捗報告スライドを生成して発表した。その後勉強会の発表を聞き、特に正しくもないコメントをしたりしていたら終了。

yukicoderのテスター作業をした。実に3週間も前に手を付けたセットの続きである。忘れてはいなかったが、セット後半の問題が残っていたので、その難しさから心理的ハードルがあってずっと放置してしまっていた。テスターを依頼されたときの話を聞く限り1月中に終わっていればよさそうな見通しだったので、何とか間に合わせたといったところ。

夜中から朝方にかけてyukicoderのテスター作業をした。年末に依頼されたものをずっと放置していた。結構数が多かったのでいくつかはまだ残っている。時間に余裕はあるらしいが、うっかりするとすぐ忘れてしまうので、注意したい。

週記（2022/01/03-2022/01/09） - kotatsugameの日記

テスター作業は午後11時半まで行っていた。一通り解いて問題文・解説のチェックを終え、達成感からボーっとしてTLを眺めていたら、JOIG本選の最短コードがatgolferに流れてきているのを見つけた。いつの間にかAtCoderに追加されていたらしい。どこかのタイミングで、JOI過去問をAtCoderに移植されている方が「JOIG本選をAtCoder上で解けるようになるまではしばらくかかる予定です」とツイートされているのを見たはずだが、ツイートが消えていてわからなかった。今日はないだろうと気を抜いていたところに不意打ちを食らい、急いでコンテストページを開いて解いた。

JOIG 2021/2022 本選 過去問 - AtCoder

AはRakuで32B、Vimで34B。Bは最初にAWKでfor文を圧縮したコードを書いた。後から試しにRakuのcombinationsを使ってみたら、普通にやるとTLEのところ、文字列のリストを数値のリストに直しておく高速化を入れると間に合ってしまった。Cは普通にC++で書いてみるとループ1回で済んだので、すぐに短くなりそうに見えた。しかしAWKに移植すると答えが合わず苦戦。C++に戻すとそちらでもWAが出て、いろいろいじった結果累積和配列への代入タイミングが変わったのが問題だと分かった。X_i=0のとき、S_{i-0}+Y_i\le S_iのような条件式になる。ここで右辺の評価時にS_iを更新すると、左辺の評価時と値が変わってしまうのだ。代入タイミングを修正してAC。

残りはC++で通しておくだけ。Dはmapでカウント。探索する場所が9N種類でそれぞれ9箇所の足し算が必要になるので、何も気にせず書くと900ms、mapに存在しない要素を構築しないようにしても670msになってしまった。EFはちょっと考える必要があると書いたが、実際はすんなり解けた。Eは絵の種類を添え字にする実家dp、Fは拡張dijkstraで、よく見ると辺のコストが決定できる。

その後公式解説を読んで、Eを上位2要素を持つ方法でRubyを使いコードゴルフしておいた。絵の種類に関する重複を省くのには、降順ソートしてからuniqを使うのが便利だった。午前3時就寝。

01/25(火)

午前9時前には起床していたはず。覚醒してからしばらくTLを眺めたり、YouTubeの動画を漁ったりすることが多いが、これをすると閲覧履歴の日時が復元できないため、自分がいつから起きていたのか定かでなくなる。午前9時というのはChromeでハーメルンを開いた時刻であった。そのまま学食にも行かずずっと読み続けて、午後2時くらいに少し起きだしてパンを食べたはず。しばらくしたらゲーセンに行こうかな、など考えていたのに、午後4時くらいに再度寝落ち。

次、午後10時半起床。またずっと読み続けて、午前4時に1作読了。「ウマ娘　ワールドダービー　凱旋門レギュ『4:25:00』　ミホノブルボンチャート」。

syosetu.org

非常に面白かった。先週の週記の最後にも書いたことだが、ウマ娘を知らないままで楽しめた。ただ一応、キャラの名前で検索してビジュアルを確認するくらいのステップは必要か。文中では毛・目の色と服のパーツという断片的な情報しか描かれないので、確認しないままだとイメージがあやふやになって読みづらかった。トレーナーのビジュアルも正直あまりよく想像できない。芦毛で顔がよいと書いてあるため、つまりは白髪イケメンキャラとなるはず。これを想像するのは難しい。競馬用語については雰囲気。筆者の語彙がやたら豊富で、知らない言葉が頻出してびっくりした。

以前RTA形式の二次創作について以下のようなことを書いた。今読んだ作品でもおおむね同じ面白さがある。しかし、主人公が操るキャラの扱いについては大きく異なっていた。以前読んだ作品は、主人公が操るキャラの行動がすべてRTA走者の視点から描かれた一方で、今読んだ作品では、おおむねRTA走者の選択に沿った行動をしつつ、細部はキャラが自身で補完しているような感じだった。その結果、RTA走者がボタン連打で読み飛ばしていた会話なりイベントが後々影響を持ってきてチャートが壊れることが何回かあって、それも面白かった。

もしかして、RTA走者の軽薄な描写と、それを原作キャラの視点から見るギャップを楽しむものだろうか？そういう第3者視点で主人公の凄さを語るシーンは僕の好みのものだ。

週記（2021/12/13-2021/12/19） - kotatsugameの日記

同作者の別作品、というか今の作品の過去IFを読み始めて、最終話近くまで行きつつ午前7時に就寝した。

01/26(水)

午後1時起床。

寝る前に読んでいたハーメルンを読み切った。「ウマ娘　ワールドダービー　称号獲得レギュ『1:11:11』　サイレンススズカチャート」。こちらは途中で止まっている。

syosetu.org

追加でいくつかウマ娘のハーメルンを漁ってから、学食に行った。昼食を摂り、予約していた本を受け取って帰宅。今日は僕のことを覚えている店員さんがいなかった。帰ってきて少しコードゴルフ。一昨日のJOIG-AがVimで縮められていた。ソートした後先頭と末尾を削除する方法しか考えなかったが、dcの加算コマンドの回数を制御していてなるほどという感じ。

atcoder.jp

ABC236-Eも縮められていて、こちらは取り返せた。入力の1行目を無視するため#を前置してコメントとして扱っていたところを、そのまま配列に入れて、代わりにmapの部分をmaxにするのが最短を取られたときの短縮。そこからアドホック気味に縮めた。初期値0の変数を用意していろいろ計算し、最後に0と比較している。ループ内部で計算してきた値の正負をチェックしており、よく見ると初期値と同じ値を用意できるならその値は0以外でも構わない。よって入力の1行目に書かれた値を初期値にして、これを比較時にまた使うため、maxの結果がその値になるようにブロックの返り値を固定（この場合は0に）した。

atcoder.jp

JOIG-DもAWKでコードゴルフされていた。各点の9近傍を探索しつつそこのカウントを1つずつ増やしていくと、結局そのカウントの最大値を求めることになるので、昨日説明したコードより定数倍がよく、AWKでも僕のC++コードより高速に動作している。いろいろ一般的なテクを組み合わせてさらに縮めた。

atcoder.jp

午後4時から1on1。本当は昼からその準備をするつもりだったのに、上のようなコードゴルフに時間を取られて30分くらいしか準備できなかった。正直に進捗が全然ないと言ったらペアプログラミングをすることになった。いろいろ確認を取りながら進められるのは楽しく、わちゃわちゃしているうちにかなり長引いて終わったのは午後6時を回ってからだった。書いたコードの量としてはあまりないが、やりたいことの準備みたいな部分なので、仕様の把握などに努めていたと考えればこんなものか。最後に進捗をGitHubにアップロードするとき、どのファイルを変更したのか覚えておらずgit add *をした結果、別のターミナルで開いたままだったVimによる一時ファイル.swpもaddされてしまい赤面。

結構遅い時間になったし微妙な眠気もあるのでしばらく迷っていたが、結局ゲーセンに行くことにした。自転車を漕いでいる最中に雨が降ってきて、帰りはヤバいかな～と思いつつ駐輪場に自転車を止める。イオンのフードコートで食事し、洗剤・柔軟剤・ほろよいの新味を購入していよいよゲーセン。

今日は新曲の精度が上手かった。しれっと1曲理論値が出ているほか、ラグトレインも理論値を出した。他にもいくつか狙ったはずがうまくいかず、微妙に伸びたくらい。今は判定Aが-0.2、判定Bが-1.0と結構いじっているつもりなのに、かなりFASTに振れる。特に14+などやると本当にひどいことになる。

閉店したので帰宅。駐輪場から自転車を出した時点では結構雨が降っていた。夜遅く、感染拡大の影響もあって店が閉まっているかと思ったのに、思ったよりいろいろ開いていた。雨は立ち食い蕎麦屋で食事している間に止んでくれた。

帰宅して買ってきたお酒を飲みつつ日記を書き始めた。まだ今日の分に追いついていないうちに1缶空き、眠気が尋常ではなくなったため就寝。午前4時だった。

01/27(木)

午前10時起床。

しばらくYouTubeを見ていた。チュウニズムに最近追加されたVTuberのオリジナル曲を昨日プレイしてきて、いくつか耳に残るものがあったので寝る前に検索して聞いたのだが、ほんの数個動画を再生しただけなのにもうおすすめ動画に配信の切り抜きがいくつも上がってきていて、その感染力とも言うべきものに驚かされた。

HHKBのコンテストで学生応援賞に当たったらしい。以下のように自分より上に学生が4人いると思っていたので、かなりびっくりした。

全完14位。学生5位に滑りこんだかと思って喜んでいたものの、トップページを確認すると4位以下は飛び賞しかなくがっくり。

週記（2022/01/10-2022/01/16） - kotatsugameの日記

1年くらい前のコンテストでもいい感じの位置に滑りこんで、その時貰ったキーボード（日本語配列・白）をずっとメインで使っている。今回2台目が貰えることになって、相変わらず無刻印への憧れはあるものの、実用性を考えて今度は日本語配列・墨を指定することにした。普段ずっと日本語配列を使っている以上、キーボード1つだけ英字配列にするなどというのは不便なだけである。

HHKB プログラミングコンテスト 2020の受賞メールが届いていた。学生3位ということで、HHKBのキーボードがもらえる。

週記（2020/10/19-2020/10/25） - kotatsugameの日記

学食に行って食事し、パンやおにぎりを購入して帰宅。午後1時からオンラインでゼミに参加した。実はもうラストまで教科書の内容を発表する機会はないようなので、今日はひたすら気を抜いていた。日記を書いたり少しコードゴルフをしたりしつつ、午後4時半くらいに終了。すぐ布団に倒れこんで、そのまま寝てしまいそうになったものの、来客があって何とか意識を取り戻した。

来客とは、隣人かつFFの方であった。一度日記でも言及している。この度引っ越すことになられたようで、わざわざその挨拶に来てくださったのだ。手土産に仙台市指定ごみ袋を頂いたので、何かお返ししようと思って昨日買ってきたお酒、ほろよい1缶をお渡しした。もう荷物も運びだされた後らしかったので、ちょっと邪魔だったかもしれないと後悔。一方こちらが頂いたごみ袋は、邪魔にもならないしあると確実に役に立つしと非常に嬉しいチョイスであった。

ちょうど隣人が帰宅したので、挨拶でも……と声をかけた。 ちょっとした立ち話になって、「もしかしてこたつがめって名前のアカウントでTwitterやってますか？」と聞かれた。大正解である。FFの方だった。

週記（2020/09/28-2020/10/04） - kotatsugameの日記

ラノベを1冊読了。「パシられ陰キャが実は最強だった件」。YouTubeの漫画動画が原作らしい。「クラスの大嫌いな女子と結婚することになった。」が売れたので味を占めたか。1巻では、ヒロインがヤンキーに絡まれてそれを主人公が助けるという流れが2回繰り返され、仲良くなっていった。助けが間に合わないということは当然なかったが、それでも絡まれている間の描写は結構読むのがつらかった。主人公がどうしようもないところで味方キャラに危害が加えられる・加えられそうになるという描写は苦手だ。しかしそういうところでヘイトを溜めた分、主人公が無双するシーンが格段にスカッとするという効果もあって、読んだ後は面白かったという感想を抱いた。

食事しようと弁当を解凍したのに、また布団に倒れこんでしまい、午後10時ちょっと前から午前0時まで寝てしまった。起きると弁当は冷え切っていたし、CF div.1も始まっていた。いいとこなし。仕方ないので弁当を温めなおして食べ、ラノベをもう1冊読んだ。

「辺境都市の育成者」5巻。面白かった。主人公に好意を抱いているキャラが大量に出てきてよくわからないまま読んでいたが、この巻はそのうちの2人が特別であるような書き方をされていたので、なんとなくストーリーの整理がついた。ラストシーンで主人公がメガネを外したイラストが描かれ、これまでの温和な印象を一気に塗り替えるような精悍さが見られてかなり好み。口調や一人称がガラッと変わるのも良い。エピローグで「勝手に呼んだ挙句使い捨てた世界」というようなセリフがあった。純粋なファンタジーに見えて実は異世界転移ものだったのかも知れず、びっくり。よく考えれば、名前のスタイルが作中世界の人物と微妙に異なる人物も出ていたので、それも伏線になっていたのかもしれない。後書きで盛んに6巻が出るか心配していたのが気になる。売れ行きは好調に見えるので、作者の作業量の問題だろうか。ぜひ続刊してほしい。作業量といえば、この作者はデビューから3年間で2シリーズ14冊を刊行していることになって、いくらネット小説の書籍化だからとは言えかなりの速筆である。加筆修正も大量に行っているようなので余計すごい。

コードゴルフを1問。Pythonのheapqを使う際、最初から列に要素があるなら、そのリストをheapifyする必要がある。これは何をしているかというと、うまく並び替えて大小関係の条件が成り立つ二分木を構築しているのだ。heapifyはリストを引数にとってそれを直接更新するので、実行はちょっと面倒である。ところが、実はheapifyでなくとも、リストをソートしさえすれば求める大小関係は自動で成立する。この際sortedを用いることで、リストを変換しつつ変数に代入することができるようになる。また関数名も1文字短くなっている。こういう更新がatgolferに流れてきたので、そのまわりを弄って最短を取っておいた。

heapq --- ヒープキューアルゴリズム — Python 3.10.0b2 ドキュメント

atcoder.jp

午前9時くらいに布団に入り、そこからハーメルンを読みふけって、正午就寝。

01/28(金)

午後8時半に目を覚まし、少しハーメルンを読み進めて午後9時半にまた寝たような記録がある。

次に午前1時に起床。またずっとハーメルンを読み続けて、午前6時に1作読了した。「ハリー・ポッターRTA　ヴォルデモート復活チャート」。

syosetu.org

エタり気味だが、面白かった。原作の設定をかなり深く掘り下げているようで、その努力が後書きから伺える。また、必要の部屋を最初から使えたり、一方で魔法は本で読むか実際に見ないと解禁されないという設定が、いい感じに原作知識を縛っていて面白い。キャラも好き勝手に動いていて、RTA走者が気にも留めなかった些細な描写が後々の小説パートでどういう意味だったか明かされ、ちょっとした障害になったりするギミックも手が込んでいる。またRTAとはあまり関係ない点で、原作や多くの二次創作で不遇だったキャラを立てるような背景が創作されているのもよかった。

また別のRTAハーメルンを読み始めた。今度はSAOの二次創作である。SAOの1層からの攻略を描く「ソードアート・オンライン プログレッシブ」というシリーズがあって、それをもとに書いているように見える。自分はそのシリーズを1巻から積んでいるため、どうしてもネタバレになってしまう。読み進めるかどうか迷い、結局ずるずると読み続けていた。午後1時半就寝。

01/29(土)

午後3時、弁当の配達で一瞬起きた。またすぐ寝て、次に午後8時過ぎ起床。シャワーを浴びて食事し、午後9時からARC134。

AtCoder Regular Contest 134 - AtCoder

Aはよい。Bは貪欲だろうという読みがついて、しばらく考えても正しそうなので実装。文字の昇順、インデックスの降順でソートしておいて、文字列の先頭から順番に「その位置とこれまで使った一番左の位置の間にあるインデックス」が見つかるまで、先ほどソートしたものの先頭から値をpopしていく。最後に、交換して辞書順で小さくなるかを確認する。

Cは言い換えが面白かった。1が書かれたボールと2\dots Nが書かれたボールを1つずつ組みにしておけば、それらを適当に箱詰めした後、残った1のボールを各箱に1つ以上入れる場合の数になる。これはすべて重複組み合わせで書けて、それぞれO(K)かける方法で求めれば間に合う。しかしa_1-\sum_{i=2}^N a_iをint型で扱ってしまい1WA。

Dもすんなりいった。まず、a_{1\dots N}の最小値を1つだけ使うか、それとも全部使った後さらに付け足すかに分かれる。付け足す場合は、a_{1\dots N}の最小値をとる最小のインデックスをi_0としたとき、a_i\lt a_{i_0+N}であるかあるいはa_i=a_{i_0+N}かつ後ろを1つずらしたときに辞書順で小さくなればよい。後者の判定は隣接項の大小関係のチェックになるので、最初から計算しつつやっていけば線形時間で求まる。しかしこのチェックで不等号の向きをミスし、しかもその修正を2回も失敗したため、3WA。値を入れ替えるべき場所が2か所あり、最初にそのうち下だけを入れ替え、次に「上だけ入れ替えた」と勘違いして下をもう一度入れ替え（つまり最初に戻し）、3回目でようやく気付いた。最高にアホ。

Eは頑張った。2要素・3要素で実験した感じ、負けるパターンは「1のみ」「2のみ」「4と8のみ」「12の倍数の組み合わせ」に分かれるようだ。手作業の実験をもとに正当性を考えることで、何か見えないだろうか。まず2以下の数しかない場合はよい。3以上の数がある場合、奇数が存在すればm=2で操作することで勝てる。また偶数しかない場合も、4で割って2余る数があればm=4で操作することで勝てる。残りを12k+0,12k+4,12k+8と書いて組み合わせを考えてみると、「4と8のみ」「12の倍数のみ」以外はm=3とm=12のどちらかで操作することで勝てるようだ。これでとりあえず正当性が分かった。

しばらく12で割った値とにらめっこしていたが、m=5やm=16で操作するケースがあって厳しい。と、残り30分を切って、ふと\lfloor 200/12\rfloor=16であることに気づいた。つまり12の倍数の集合をbitDPで数え上げることができて、残りのこまごまとしたケースを処理することで負ける場合の数を全部求められる。K=16としてO(NK2^K)のbitDPとO(K2^K)に定数倍200がついた判定フェーズになって、手元で微妙に時間がかかるもTL 6secを信じて提出、すんなり500ms弱で通った。

5完26位。4ペナが効きすぎるほど効いている。

コードゴルフ。これは以下に書くCodeChef後のものも含む。A問題は列がソート済なので、dcで書ける。適当にガチャガチャしていたら何もかもがうまく作用して、当初想定していたよりずいぶん短く書けた。Bは前のほうに持ってくる文字を順に試して、rindexを使って位置を検索するのが短くなった。Cは想定解がO(NK)とRubyでは通らなかったので、Crystalを持ち出した。相変わらずa_1-\sum_{i=2}^N a_iが大きくなりすぎてオーバーフローのREを起こし続けていたが、答えが0になる場合変数の初期値を0にするようにしたら、オーバーフローするようなケースでは掛け算した値が0になるので問題なくなった。以降は手付かず。

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

https://www.codechef.com/LTIME104A

PERMXORSUMは、bitごとに立っている数と立っていない数を数えて、立っているbitができる限り無駄にならない場合を考えたら通った。つまり、2^iのbitが立っている数が1\dots Nにc_i個あった場合、答えに\min(c_i,N-c_i)\times 2\times 2^iを足す。コンテスト中は証明しなかったが、後からTLに流れてきた方法というか、構築方法が天才的だった。N以下で最大の2べきを2^bとすると、2^b\dots Nと2^b-(N-2^b+1)\dots 2^b-1（の逆順）を対応させることでbitwise ANDが0であるようなペアばかりを作ることができ、その上残りもまた1\dots N'の形をしている。よってこの要領で組にしていけば「立っているbitができる限り無駄にならない」という条件を満たすことができる。最後に高々1個余るが、それはどうあがいても無駄になってしまうbitたちである。

CIRCPRMRCVRYはよくわからない。A_i=Kとなるようなiを集めてきたとき、Nの制約から2つの間隔（の円周上で短いほう）がK以下なので、値の大小関係がわかる。その大小関係において最大だと分かるものが高々1つあるはずで、そこをNと確定してよい。そのようなものがなければ答えは-1である。さて、今Nが確定したとして、そこから遡ってK個ぶんAの値をインクリメントし、今のチェックを繰り返す。これで構築できればそれが答えとなる、はず。サンプルを手で試しているうちに思いつき、いかにもよさそうなので出したら通った。実装は遅延セグ木だったりsetだったりを使って結構大変だった。

PERMDELは端から2要素しか削除できないため、真ん中を決め打って左右の操作列を数え上げた。数え上げは次のようになる：例えば左を考えると、(i,i+1)が左から2要素になっている場合の数をdpで管理して、そこからi+1,i+2,\dotsとどこまで削除できるかをチェックする。i+1,\dots,j-1をこの順で消す場合を、最後にiを消して(j,j+1)を残す操作列としてdpに足しつつ、真ん中がjになる場合として別に保存しておく。このjは区間になるので、遅延セグ木の区間加算で扱える。提出すると全然答えが合わなくてひっくり返ったが、N=5を試すとすぐわかった。左右をどの順で操作するかも考えなければならなかった。

残りは部分点のみ。DIVDISTは全方位木dpを書いて35pt。ANTHRXORTASKはK=1を貪欲。空きがある中で最も上位のbitを立て、以下のbitはXORする値たちを見ながら桁ごとに総和が減らないように決める。とりあえずK=1は通って15pt、これをK回繰り返したら通らないかと思ってもう一度出してみるも、K=2からWAになるケースがあるようだった。以上350ptで14位、2614→2662(+48)とhighestを更新した。

朝までずっと日記を書いていた。そこからラノベを読み始め、1冊読了。

「美少女エルフ（大嘘）が救う！弱小領地」。非常に面白かった。ストーリーや終盤の山場はシンプルに劇的で良い。とはいえ経済の話を置いておくわけにもいくまい。1巻での経済的な発展は、まず出自等による信用を使って証券を発行し、その対価に得た貨幣を元手に紙幣を流通させるまでだったと認識している。後者が特徴的で、貨幣（銀貨）と兌換できる紙幣を発行するのではなく、土地等と兌換できる紙幣を発行していた。それも宝くじの景品として、である。確かに紙幣の形にしなければならないほど銀貨が流通していないような描写だったので、こちらのほうが現状に即しているのかもしれない。宝くじによって流通させるというのも初めて見た。さて、すでに経済を扱うなろうやラノベをいくつか読んだことがあるが、やはり難しい。より現代に近づいた舞台だと、すでに成立している資本主義に乗ってお金儲けをすることになるので、読み手としてはある程度の金融商品に対する知識が前提となる。そこまでいけば正直よくわからなくても気にならない。一方このラノベのように一から経済を作り出していく話では、自分でも理解できそうなラインの話をされるため、何とか飲み込もうと必死になって頭を働かせることになる、ように思う。

もう1冊本を開いて少し読み進め、午後2時就寝。

01/30(日)

午後8時半起床。食事してABC237。

AtCoder Beginner Contest 237 - AtCoder

Aは微妙に書きにくい。どう書いたら短くなるのかがわからないため、安定を取ってRubyで書いておいた。次にBを開くも、解法がすぐには見えなくて戸惑う。少し考えて、逆順に見れば列の先頭と末尾に値を入れる操作に言い換えられるとわかり、実装して提出。しかしサンプルからWAが出ているうえにREも出ている。空白区切りのところを実装の簡略化のため改行区切りで出力していて、そこも見られているのかと思い修正するも、またWA。絶望しつつ再度問題ページに遷移すると、見覚えのない問題が載っていた。びっくりして問題一覧を見に行くと、D問題の問題名が問題ページに載っていたものに一致している。開いてみると先ほどまで解いていた問題だったので、今までB問題だと思っていたのはD問題だったようだ。後に知ったことだが、コンテスト開始から5分弱、B問題の問題文がD問題のものになっていたらしい。

Dに提出しなおして、再度B問題に取り組む。これはOctaveで転置すると簡単。出力に手間取るもすぐACし、そこから少しだけコードゴルフもしていた。次にC問題。先頭と末尾の'a'を削除してから回文判定するコードをPerlで書いて投げると、WAとTLEが出る。TLEは正規表現が遅いからだろうが、WAも出ているので困る。冷静になると、左端の'a'の文字数は右端の'a'の文字数より少ない必要がある。その条件も含めたコードをC++で書いて通した。

Dは先ほど通していた。Eは始点と終点の標高がわかるので、移動における楽しさの変動はその差に加えて「どれだけ余計に登ったか」がわかればよい。これで辺の重みが非負になるので、dijkstraで解ける。FはLISをdp配列の二分探索で求めることを考えて、その際のdp配列の内容をそのままdpの添え字にすればよい。GはX未満の数の位置を管理する列とXより大きい数の位置を管理する列を2つ用意して、ソートはそれぞれの列からX未満の数・Xより大きい数の個数を取得して左右に振りなおせばよい。区間SET区間SUMになる。Exは各位置から右に最も長い回文だけ考えてよさそうだということまで感づいていたが、最大200頂点のグラフの最大独立集合を求めることになって絶望。解けなかった。

Bに2回提出した分が削除され、7完1ペナで41位。

しばらくコードゴルフして、午後11時半からCF #769 div.2。

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

Aはn\ge 3なら必ずNOになる。BはペアにしてXORを計算するのかと思ってARC122-Dを思い出し、binary trieを貼ろうとしたところで誤読に気づいた。この問題では、n以下の最大の2べき2^bを取ると、どうやっても2^bのbitが立っている数と立っていない数のXORが出現するため、答えは必ず2^b以上になる。2^b-1,2^b-2,\dots,0,2^b,2^b+1,\dots,nと並べるとその下界が達成できる。

D - XOR Game

Cは非常に難しい。大体はORを取る3つ目の操作で一致させるんだろうなと予想がつく。実際、ORの操作で一致しなかった場合は必ずa\gt bとなって、この時a-bの値を小さくするためには2つ目の操作でbをインクリメントするしかないため、追加でa-b回操作することで一致させるのが最短だとわかる。この考察によって、ひとたびORを取った以降の手順が一意に定まる。aをx回、bをy回インクリメントした後ORを取る、と固定すると、一致させるのに必要なコストは全体でx+y+1+( (a+x\mid b+y)-(b+y))=x+1-b+(a+x\mid b+y)と書ける。

まずa+x\ge bの場合を考えよう。今yの値は非負ならば何でもコストに影響しないため、y=a+x-bとするのが良い。このときコストはx+1-b+(a+x)となって、これはx=b-aの時に最小値b-a+1を取る。しかし、最初からインクリメントだけで一致させるコストがより小さいb-aなので、a+x\ge bの場合は考えなくてよいということが分かった。そんなことを計算しなくても、x\ge b-a回もインクリメントすれば当然途中で一致する。よって0\le x\lt b-aとなり、これは\sum bの制約が存在することから全探索できる。xを決め打った時、y\ge 0の範囲で(a+x\mid b+y)の最小値を探す必要があるが、これについてはa+xとbのbitを上から見て行って、最初に(a+x,b)=(1,0)となる位置より上はbから、より下はa+xからbitをコピーしてくると得られる。

コンテスト後にTLでaとbのどちらかしかインクリメントしないということを知った。上で述べたことの延長で考えてみる。まず(a\mid b)=bとなる場合を除く。(a+x\mid b)=bの場合、aしかインクリメントしなくてよいためOK。残りのケースは(a\mid b)\gt bかつ(a+x\mid b)\gt bとなって、このときx\gt 0を考慮しなくてよいことを説明する。(a\mid b)-b（つまり(a,b)=(1,0)となるbitの集合）と(a+x\mid b)-bを考える。(a\mid b)-b\le (a+x\mid b)-bであれば当然x=0のほうがコストが小さい。(a\mid b)-b\gt (a+x\mid b)-bであれば、(a\mid b)-bで立っていた最上位のbitを桁上がりさせてbに吸収させたとわかって、このとき桁上がりしたbitより下は全部0にできるため、(a+x'\mid b)=bなる0\le x'\lt xが必ず存在する。以上より、(a+x\mid b)=bとなる場合かx=0のみ考えてもコストの最小値が求まると分かった。前者のxを頑張って求めると、全体でO(\log b)が達成される。

Dは、書き換える値を非常に大きな素数だと思うと、そうやって書き換えた値で列を区切ってそれぞれで条件を満たしていればよいことになる。この書き換えは区間スケジューリングを考えると貪欲に行うのがよい。あとは書き換えが必要かのチェックで、これはrを固定すると高々1つのlをチェックすることになるとわかる。なぜなら、lが左に行くにつれてr-l+1の値は単調に増加し、一方\gcd(b_l,b_{l+1},\dots,b_r)の値は単調に減少するからである。この増加と減少がちょうど交わる点を二分探索で求めればよい。DisjointSparseTableを貼ってO(N\log N\log \max a_i)。ACLのセグ木で二分探索しても同じオーダーになるだろう。

E1はしばらく迷走したが何とか解けた。f(x)の値に対してそれを達成できる最大のxを求める。追加の辺なしではたどり着けない頂点をリストアップし、それらの頂点だけを考えた時の直径dを求めると、xの最大値はf(x)-\lceil d/2\rceilとなる。dをf(x)の降順に求めることを考える。毎回double sweepするとE1が解ける。実は、直前の直径の端点がu,vで今頂点wを追加したとすると、直径は必ずu-v,u-w,v-wのうちどれかになることがわかる。今見ている頂点たちのうちでは、u,vのどちらかが必ず最遠の頂点になるからだ。木の2頂点間の距離はLCAを求めることで高速に計算できるので、これでE2の制約でも直径の更新ができる。

55分でノーペナ全完、システスも全部通って、なんと優勝した。CFのコンテストで優勝するのは初めてな気がする。

ABCのコードゴルフについて。A問題は難しい。dcで頑張って数値比較をするよりも、精度を設定するコマンドkがちょうど2^{31}未満の非負整数しか受け付けないという性質を利用するほうが短くなるようだ。同様の性質を持つコマンドはもう一つあって、Rである。試してみると、絶対値が2^{31}+1以下の整数しか受け付けないらしい。つまり、N\ge 0に対してはN+2を、N\lt 0に対しては1-Nを作って、それでRすることにより、条件に応じてスタックを弄ることができる。これで縮めた。ただもうちょっと縮まないかと思って、ある程度見当を付けたdcコードを生成して境界付近のNでチェックするという方法でしばらくプログラムを回してみたところ、なんと1B縮んだ。N\lt 0に対しては-N-1を作っているらしい。

いやそれは違うだろう。N=-2^{31}-1のとき|-N-1|=2^{31}となって、Yesを出力してしまうはずだ。そう思って手元で実行してみると、信じがたい現象が発生した。どうやら、ちょうど\pm 2^{31}である場合も受け付けないようだ。この問題では、境界ギリギリの値はちゃんとテストケースに含まれている一方、少し離れた値は全く含まれていないため、このようなコードでも通るらしい。N=-2^{31}-2やN=2^{31}-2で落ちる。

BはOctaveよりもRakuでzipするほうが短くなった。[Z]だと、引数になるリストのリストがいったん展開（Slip）されるらしく、Rakuで65536要素以上のリストをSlipするとREになってしまうため動かない。今回はzipと[Z]が同じ文字数で助かった。ちなみにこのSlip制限の仕様は相当大きなテストケースでないと顕在化しないため、意気揚々と出したコードが謎のREを吐いて絶望することも多い。CはとりあえずPerl。DもPerlで書いたが縮められた。出力をjoinする空白ごとリストに入れるのは頭がいい。EはnetworkxがTLEしてしまい、仕方なくPythonのheapqで実装したのに、ACLの最小費用流を使うほうが短くなった。最小費用流をdijkstraの代わりに使うのは新鮮。FはLISのdpテーブルを直接Hashのキーにした。Rubyだと微妙にTLEしたのでCrystalで書いた。

GはTL 8secということで、O(NQ)を通せる。最初は区間SUMのループと区間SETのループ2つ、合計3つで書いていて、pragmaをつけて何とか通り、場合分けしてSETする値を定数にしないとTLEになるなど大変だったが、区間SETにmemsetを用いることで爆速になった。現在はClangではおまじないなしでも通っている。Xとの大小関係を正負で表しているので、memsetでも必要十分な代入が可能なのだ。区間SET2回のうち、片方を区間SUMのループと同時に行わせることで、700msほど遅くなった代わりにコードが縮んだ。それも許容できるくらい時間に余裕がある。

atcoder.jp

週記（2022/01/17-2022/01/23）

01/17(月)

先週の週記を投稿してからの話。購買が開店したので、注文した本の受け取りをするつもりだった。しかし、午後4時半から予定されているインターン先の定例会まであまり時間がないという事実が重くのしかかってきて、睡眠時間を確保するために今日は諦めることにした。さらにすぐ眠ればいいものをついついラノベを読み進めてしまい、布団に入ったのは正午を回ってからだった。そのうえしばらくTLを眺め、午後1時就寝。

午後4時半、目覚ましで意識を取り戻す。ボーっとした頭でもう少し寝ようと考え意識を失う直前に、すでに定例会開始時刻であることに思い至った。全身から冷や汗を噴き出して跳ね起き、ミーティングに接続。幸いと言うのもなんだが、3分程度の遅刻で済んだので特に言及されることもなかった。自分の進捗報告までにはいくらか時間的余裕があるので、ほかの人の話を聞きつつサッとスライド作成。先週は業務を期限に間に合わせるため個人的には頑張ったつもりで、そこから得た所感など盛り込んだら1ページ埋まった。発表も問題なく終了。

今日の勉強会の内容は、先日最終結果が出たKaggleのサンタコンペの解法についてだった。正直あまりよく理解できていないものの、とにかく上手い構築があったうえに必死の短縮が行われていたらしくスゲーという気持ちになった。特に、順位表で1文字縮むとわからなかったら自分たちも縮められなかった、というような言葉が印象的。これはコードゴルフにも通じて、もちろん似たコードを弄っていたら同じ短縮が効くのはそうだが、まったく異なるコードを弄っていても1人でやるよりは誰かと競うほうが短くなりがち。誰かにコード長で後れを取ると、その悔しさからより粘着して考えることになるためだ。また特に関係ない話で、「下界」を数学用語として使う場合の読みが「かかい」であることを知った。「下限」との対応を取っているのではないかというツイートを見てなるほどなあと思った。

定例会を終えて学食に向かう。一歩外に出るとあまりにも寒くてびっくりした。家の周囲は雪が全く残っていないようだったので自転車を出したのに、大学近くの歩道は踏み固められたのか微妙に残っていて肝を冷やした。食事を取り、ミールカードの今日分の残高で飲み物を購入して即座に帰宅した。

ボルテが10周年らしい。流れてきたツイートのイラストが良すぎて目を惹かれた。もう数年ほどプレーしていない。チュウニズムでは譜面を見たり運指を覚えたりなど座学も頑張っていたのに、ボルテはそういうことを一切行わなかったため、あまり上達もしなかった。比較してチュウニズムのほうが楽しく感じられたのだろう。今はもう他機種をプレイする余裕があるほどゲーセンに通えてすらいない。

ラノベを2冊読了した。1冊目は「俺は星間国家の悪徳領主！」4巻。これが今出ているシリーズ最新作になる。やはり面白かった。先週書き忘れたことだが、主人公の行動を周囲が勘違いするのとは逆に、周囲の行動を主人公が勘違いするほうも丁寧に描かれていて、なるほどそういう解釈があるのかと驚きも2倍であった。またキャラクターたちの行動が複雑に組み合わさって主人公の王道を演出するギミックも、相変わらず巧妙に思える。

2冊目は「西野 ～学内カースト最下位にして異能世界最強の少年～」9巻。内容を読むのはつらいが設定はめちゃくちゃ面白い、ということを何度も言っている。単純な話、主人公が世界最強なので良いと感じているのだ。しかしこの辺りの巻はそういうバトルシーンがほとんどなく、どんどん読むのがつらくなってくる。主人公の外見と態度のミスマッチがこれでもかと強調されているのが、場違いさを際立たせる。どうやら自分はキャラクターが場違い・身の程知らずな行動をするのが苦手らしい。10巻はあらすじなどを見る限りそういうバトルシーンがありそうで期待が持てるものの、あまり読む気になれないので、次に手を付けるラノベとしては選ばないことにした。

「話の出しにする」の表記が「出汁」でないことを知った。いや、「出し」の意味として出汁が含まれるので、おそらくニュアンスとしては一致しているはず。片方は話題を、もう片方はうまみ成分を抽出しているわけで、しかし「出汁」と書くと完全に食品関係の話になるということだろう。

日記を書いて布団に入り、ラノベを開いて少し読み進めた。午前6時就寝。

01/18(火)

午後3時、腹を壊して飛び起きる。ベッドとトイレを2往復くらいして一段落ついたところで、二度寝するのを止めて生協に行くことにした。

購買が閉まって同時に学食の夜の部がスタートするのが、午後4時だと勘違いしていた。実際は午後5時。雪が降る中早歩きで来たのに閉まる気配がみじんもなくて拍子抜けした。腹痛も再度ぶり返してきたので、生協のトイレに寄りつつ、購買でパン類を購入し、注文していた本を受け取って帰宅した。惣菜パンを食べてまた外出。今度はゲーセンに行く。

夕食を挟みつつ、午後6時から閉店までいた。今日はありえないくらい上手な日で、大量の成果を出せた。諸々伸びたものは省略するとして、理論値が6譜面、14+のSSSが1譜面、15のSSが1譜面。適当に選曲したものが理論値、ということが3回起こって、はっきり実力が向上したのを感じた。緊張に負けない心臓も身についてきているかもしれない。

結構前から1落ちは出ていた譜面で、Lv.13では初めての理論値。直後にもう1譜面出ている。下の部分が問題で、微妙に速い階段とフリックが同時に来るため焦ってしまい、非常に勝率が低かった。端フリックで取ることで手の動きを減らすと多少はマシになったので、あとは通るまでひたすら連奏していた。幸いそれ以外の部分は特に難しくないため挑戦回数はそれなりに稼げて、25連奏で出た。

f:id:kotatsugame:20220119042523p:plain
61、65、69、73小節

曲が好きすぎて定期的に選曲している。今日2回目で出た。

www.youtube.com

家を出る前に攻略動画を見て少し座学していた。序盤のフリックは、逆の手でホールドを押すことを一切諦め全押しのようなことをしていたら軽傷で済んだ。そこを終えて8000点弱、速さがよくわからないトリルで削られて6000点。ホールドトリル地帯は全押しの力の入れ方を理解した。恥をかなぐり捨てて腰を落とし、エアーを取る方の腕は上げるとき力を抜く。そこを抜けて何とか3000点残っており、あとは全力で叩いたり擦ったりしたら耐えきれた。プレイ中の記憶があいまいなので1000点くらい誤差があるかもしれない。ともかくこれで解禁済み全曲SS、OPはすでに90%に迫るくらいあるので金ポゼッションを飛ばしてプラチナポゼッションである。実は15の未解禁譜面が祈を含めて他に4つあるので、寿命は短いかもしれない。いや、祈は許容が大きいから何とかならないだろうか。混沌はノーツ数が2800個と15の中では少なめなのでかなり難しかった。

今日最後のクレの最後のトラックで選曲したら出た。今日一発。14+の未鳥は解禁済みだと残り3譜面になる。序盤がうまく行って終盤もうまく行ったので乗った、としか言えない。特殊な運指は全く組んでおらず、いわゆるお前の弁当地帯もそれっぽく押している。今日はこことその直後のホールドトリルがありえないくらい上手かった。ホールド階段を抜けてまだ8000点残っているのを見てびっくり。しかしラストのタップスライドに入る直前にはすでに7500点台まで削れていて、最後祈りを込めて擦ったら無傷だった。あと赤3個出したらアウトだったと思うと、今更肝が冷えてくる。

新春TechFUL Coding Battle 2022の順位表が更新されていた。自分は11位。そ、そんな……。ボス問以外理論値なのに、1問崩れるともうどうしようもなくなる。

SRM822に出た。2完15位で2455→2487(+32)。前回の傷は深い。

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

Easyは最後のサンプルの説明文に「2/3」と見えたのに、立式してみると合わない。よく読むと「almost, but not exactly, equal to 2/3」など書いてある。試しに作った式で値を計算すると、サンプルの答えと一致した。許容誤差を考慮しても2/3は異なる値なのでなにが「almost equal」やねんという気持ちになった。それ以外は普通の問題なのにこういうところで評価を落としにくるのは何なのか。

Medは、まず\{1,1,1\}なら勝てる。1が1つ足りない場合は、代わりに「次に\{1,1,1\}になるもの」があればよい。つまり\{1,1,2,2,2\}である。同様に\{1,1,2,2,3,3,3\}もできそう。こう考えると、値の大きな方から3つ見て(x,x,x)だったらx-1にまとめる、というのを繰り返して最後に\{1,1,1\}が得られればよさそう。それぞれの要素にはもとになったインデックスをvectorで保持しておく。マージは愚直にやっても間に合うだろうが、念のためマージテクを使っておいた。下のツイートのような考え方もあるらしい。こちらはかなり美しい。

Hardに40分程度残したはずだが、考えているうちに寝入ったりしていた。Hardが提出2、AC1であったこと以外は普通の問題が並ぶコンテストだった。

火曜日のPythonの講義からキーワードを抜き出して提出するやつをやって、日記を書き、布団に入った。午前6時だった。生活リズムを安定させるには、昨日と同じ時間に布団に入れたのはかなりいいことだな……と思っていたのに、眠気が薄いからと言ってラノベを開いた結果、1冊読み切ってしまった。

「プリンセス・ギャンビット」。学園を舞台にゲームで勢力争いするのはそれなりに多い設定とはいえ、そういうものの本題は独自ゲームなり勢力争いのルールを設定して、その穴を突きまくることにある。この本でもいくつかゲームのルールが導入され、プレイヤー同士がひたすら搦め手を使って戦う様子が描かれた。読むと疲れるので、実は苦手な部類なのかもしれない。大体は相手を罠に嵌めてすんなり勝っていたが、1巻ラストのゲームはかなりまともに心理戦をしていてよかった。ところで「ギャンビット」とはチェスにおける定石、特に自分のポーンを犠牲に盤面での有利を取るもののことらしい。この話でヒロインが犠牲としたものは何だろうか。今のところは、すべてのゲームに勝ち抜いた後の地位だと考えられる。

読み終えると昼前になっていた。木曜日の午後1時からはゼミがあるので、その近辺に睡眠時間をぶつけるような生活リズムは避けたい。そのため本来なら今から寝るのは言語同断だが、すでに眠気もかなり強い。何とか生活リズムをずらそうとハーメルンを開いたりラノベを開いたりして、午後0時半まで耐えてから寝た。

01/19(水)

消えた。

01/20(木)

01/19 午後9時半起床。といっても、ここから活動を始めるとまた朝方まで起きていることになって今度こそゼミ出席に失敗するので、何とか二度寝の範囲内で再入眠したい。布団に横たわったままハーメルンを読み始めると、これが面白く、途中一瞬起きて食事を摂りつつ数時間ずっと読んでいた。午前3時くらいに訪れた眠気に身を任せ、就寝に成功。5時間以上覚醒していたとは言え、その間ほぼずっと布団に横たわっていたので、まあ二度寝と言えなくもない……か？ともかく、この時間に再入眠できたのは良かった。

次に午前7時半起床。微妙な眠気を振り払ってハーメルンを読み進め、午前10時頃読了。「剣姫転生　〜エルフの娘は世界最強の剣士を目指す〜」。無職転生の二次創作。非常に面白かった。オリ主は最初からヒトガミの関与を跳ね除けたため、あとはルーデウスの苦悩を伝聞形式で聞くくらいとストレスフリーな展開になっていたのが個人的にうれしいところ。原作の流れは結構忘れてしまっていたので、ルーデウスの行動が描写されないのも相まって後半はちょっとついていくのが大変だった。

syosetu.org

さらにお気に入りに入れていた読了済みのハーメルンの更新を漁り、午前11時半ごろ布団から出た。英語のDMが届いていて、「a window to」と見えたので知らないイディオムかと思って調べたものの見つからない。文面をよく見直すと「widow」だった。これは「未亡人」という意味らしく、そのような単語を含むDMは当然スパムである。

シャワーを浴びた後学食に行き、予約していた本を受け取る。今日はファンタジア文庫の発売日で、今月は5冊を予約していた。どれも楽しみにしていたものである。午後1時になる直前に帰宅して、ゼミ。

先週作成したスライド分がまだ終わっていなかったので、今日最初の30分ほどを使って終わらせた。ルジャンドル記号の読み方がわからないのでいちいちつっかえてしまう。また、本来黒板発表の準備のためだけに作ったスライドだったので、情報をギチギチに詰め込んでいるページがあって読みにくかった。「no less than」の訳として「下らない」を使ったところ、「取るに足りない」の意味に聞こえるという指摘を受けた。下に貼ったPDFでは「下回らない」に直してある。特に関係ない話だが、下回らないの意味だと「下る」＋「ない」であるところ、取るに足らないは「下らない」で一語の形容詞となるらしい。

Apostol_Chapter9_9.1-9.6.pdf - Google ドライブ

僕と同じくTeXで書いた資料を使っている人が、3点リーダーの位置について指摘を受けていた。どうやら常に「dotsb」を使っているらしく、カンマ区切りの列挙の省略ならldotsを使いましょうということを言われていた。また、dotsならどの3点リーダーとなるか自動で判定してくれるということも言及された。ところで「dotsb」は初めて聞くコマンドである。調べてみると、ldotsやcdotsという位置だけ決められたもののみではなく、2項演算子の省略のための「dotsb」、コンマの省略のための「dotsc」など思ったよりたくさんの種類があるらしい。dotsはそれらを使い分けてくれるという理解でいいのだろうか。思ったより高機能であった。

ゼミ中に、コインハイブ事件の上告審の結果が出ていた。控訴審で出された有罪から逆転し、ついに無罪を勝ち取ったらしい。何か支援をしていたわけではないが喜ばしいことである。以前「控訴審では最高裁に判断を委ねるためわざと第一審と逆の判決を出した」という言説を見た覚えがあって、コインハイブ事件が当然無罪だと考えていた自分にとっては受け入れやすい論理だったので覚えていたが、友人に確認したところそのようなことが起こるとは考えにくいようだ。控訴審で相変わらず無罪でも重要事案なら検察側が上告するから、ということらしい。

判決では、コインハイブの反意図性は認められている。反意図性とは「当該プログラムについて一般の使用者が認識すべき動作と実際の動作が異なる場合に肯定されるもの」であり、「一般の使用者が認識すべき動作」は「当該プログラムの動作の内容に加え、プログラムに付された名称、動作に関する説明の内容、想定される当該プログラムの利用方法等を考慮」して認定されるようだ。WebブラウザがWebページを表示するだけでも複雑怪奇なプログラムが実行されるとは言え、それらは概ねWebページを表示する・動作を軽量化する目的で動いていると考えられるし、その上Webページに見たくもない広告がくっついてくるのも最早想定される範囲と言える、しかし知らないうちにマイニングが行われるのはさすがに想定できない、ということらしい。それはもう、マイニングがまだ一般的な技術ではないだけじゃないだろうか？

一般的なウェブサイトにおいて，運営者が閲覧を通じて利益を得る仕組みとして広告表示プログラムが広く実行されている……（中略）……ウェブサイトの収益方法として閲覧者の電子計算機にマイニングを行わせるという仕組みは一般の使用者に認知されていなかったことといった事情がある。

裁判例結果詳細 | 裁判所 - Courts in Japan

ところで、この事件について担当の弁護士が出した以下の文章は自分にとってかなり衝撃的だった。論理的であろうとすると言葉尻を捕らえられて不利になるなど、聞くだけでも絶望的である。取り調べの過酷さも印象に残った。

ゼミが終わってからすぐ布団に入り、ラノベを開いたはず。しかし即座に寝落ちして、起きたのは午後10時半だった。

そのまま読み続けて1冊読了。「お隣の天使様にいつの間にか駄目人間にされていた件」5.5巻。時系列的には2人が付き合う前、つまり4巻までの間の出来事が描かれた短編集である。まだ溶け切っていないヒロインだったはずが、内心ではかなり最初のほうから主人公にぞっこんだったことが知れて良かった。一番最後の短編はお互いがお互いのささやき声に悶える話で、あまりにも甘すぎて致命傷を負った。これがまだ付き合っていない2人の関係か。

さらにラノベを2冊読んだ。まず「VTuberなんだが配信切り忘れたら伝説になってた」3巻。2巻後書きに以下のようなことが書かれていて、ずいぶん楽しみにしていた。おそらくライブシーンのことだったのだろう。ギャグとシリアスの落差が激しすぎて感情が追いつかず、特に何も感じることはなかった。読後感が良いという曖昧な理由でおすすめラノベに入れたからか、3巻に対する期待が大きすぎて実際に読むとこんなものかとなってしまい、正直あまり楽しめなかった。僕が昨年末漁りまくっていたVtuberもののハーメルンと異なり、この作品には今のところ炎上というわかりやすい苦難、あるいはさらに広く言ってストーリーがない。その分主人公のキャラクター性だけが前面に出てきて、そのぶっ飛びぶりに付いていけなくなっているのかもしれない。

次巻にはweb版で屈指の人気を誇ったシーンが収録される

週記（2021/09/27-2021/10/03） - kotatsugameの日記

次に「青のアウトライン」。非常に良かった。絵の才能をテーマにした小説はいくつか読んだことがあって、どれも当たりだったので購入を決めたが、やはり大当たりだった。凡人である主人公と天才である幼馴染という設定は実は別の作品と被っているものの、こういう設定の話はいくらあってもよい。この作品でも主人公の良質な苦悩が描かれて感情的になれた。それでいて周囲の人物などはラノベらしく設定されており、全体通して軽い雰囲気がある。先に述べた、他の絵の才能をテーマにした小説を読んだときは、絵を競プロに読み替えたりしていろいろ考えこんでいたらしい。以下の引用記事にツイートへのリンクがある。今日はそんなことは全然考えなかった。天才キャラの描かれ方が違ったのか、あるいは1年以上経って自分の心境に変化があったか。仮にも赤に到達したので、才能という観点からは自信がついたのかもしれない。

「君を描けば嘘になる」もとんでもなく面白かった。読み終わってから感情に整理をつけるまでしばらく身動きができなかった。

週記（2020/11/23-2020/11/29） - kotatsugameの日記

布団に入ったのに寝るのに失敗したりしつつ、「放課後インスタントセックス」の溜めていた更新分を読んだ。章が1つ終わっていて、いろいろ山場もありハラハラした。最終章に入って少ししたところで更新が途切れている。しばらく休んだ後一気に完結まで投稿するつもりらしい。まだ微妙に不穏な要素があるので、どう解決されるのか楽しみである。

https://novel18.syosetu.com/n7640gf/

午前11時就寝。

01/21(金)

午後3時過ぎ起床。

今日は午後4時から1on1が予定されている。今週も進捗が何もなくて焦る。貰ったコードを少し読んで何とか耐えしのごうとしていた。始まってみると、今日はそのコードを書いた人もわざわざ時間を取って参加してくださるらしくびっくり。このような機会があるのに自分で何もしてこなかったのは辛い。しかし、まず一通りの説明をしてもらえたので、その後それを聞いて気になったことを質問していただけでもかなり得るものがあった。

2月頭に勉強会で発表する予定だったが、その近辺に期末課題の期限が集中してしまったのでずらしてもらえないかとお願いしたら、さらに次の週にしてもらえた。そういう調整も済ませ、ちょっと伸びて午後5時半に1on1が終了。話していただけなのに何故か達成感を得てそのまま布団に舞い戻ったところ、午後6時くらいに寝落ちした。

午前0時半に目を覚まし、布団の中でひたすらハーメルンを読み続けていた。

syosetu.org

「SAOを真面目に攻略しない人々」。1つの作品ではあるが章ごとに登場人物が独立しており、それぞれ異なったアプローチでSAO事件を解決するというもの。かなり面白かった。個人的には第3章が好きで、匿名凄腕ゲームクリエイター、しかしその正体は年端も行かぬ少年2人組……という設定に撃ち抜かれた。多分正体を隠している要素がツボに入ったのだろう。ただこれも4章に進むと何もなかったようにリセットされて新しい話が始まり、登場人物の名前だけは微妙に共通しているのが喪失感を感じさせて辛かった。

https://syosetu.org/novel/207052/

「東北家のただれた日常」。ボイロ二次創作のR18。ハーメルンはR18だとリンクを埋め込んでもタイトルが表示されないようだ。竿役がクズすぎて読み物としては受け入れがたい。読み物としては。

syosetu.org

「魔法少女サクリファイス【完結】」。これを含めた以下3つはどれも同作者のもので、その他以前に「格ゲー全一Vtuber【完結】」を読んだことがあった。どれも短くまとまっていて良いという印象を得た。この作品に関しては、途中までは勘違いものだと考えていて、実際その要素もあるが、主人公の死亡までが超スピードで描かれて勘違いしている場合ではなくなった。

syosetu.org

「The Boss in Ikebukuro」。デュラララの二次創作。池袋ウエストゲートパークがめちゃくちゃ好きなのだからデュラララも読むべきなのかもしれない。中学生の頃友人から借りて4巻まで読んだ、その事実は覚えているが、内容はすっかり忘れ去っている。それでも、この二次創作は一発ネタということであまり原作の流れを必要としていないためか読みやすかった。

syosetu.org

「気に食わないお隣さん」。なかなか好みの設定。配信者だとか、気安く言い争える友人関係にある男女といった設定も好み。

atcoder.jp

TLにlong doubleでないと通らなかったというツイートと共に「eject」への提出が流れてきた。上に貼った提出はそれとは異なるが、問題のわかりやすさのためこちらを掲示しておく。long doubleなんて特殊な浮動小数点数を使わないと通らない問題はそうそうないだろうと思っているので、別のところに原因があるんじゃないかとコードを読み、理解した。pow関数の第2引数に1018にもなる大きな数を入れることになるが、第1引数をdoubleにしていると第2引数もそれに合わせられて、結果精度が落ち値が変わってしまったらしい。今回は-1をべき乗する場合があるため、指数の偶奇まで正確に見る必要がある。その点long doubleだと1018でもなんとか保持できるということのようだ。

ラノベを1冊読了。「純白令嬢の諜報員」。ファルまろさんのイラストとか、設定を網羅した創作世界に降り立って無双するという設定に惹かれて購入した。話は面白かった。1巻は虐げられていた少女が侯爵になるまでを駆け抜ける部分なので、辛い描写も多かったのだが、のちに全て覆されるとわかっていれば耐えられる。実際すべて上手く行って、今のところの困難はすべて解決したように思う。ただ1点、どうしても受け入れられない文章があった。76ページ。

「三分の三は一ですか？」

「0.9999999999……限りなく一に近い一ではないものですね」

数学的に間違っていることを主人公の能力を示すやり取りの一部として書かれ、醒めてしまった。

https://ncode.syosetu.com/n2558ez/

またネット小説、今度はなろうを読んだ。「一人っ子男児の俺が四つ子姉妹の一人になったわけ」。名家に生まれる四つ子の一人に転生、という設定はかなり良さそうだったが、展開はあまり好みではなかった。他の3人や周囲のキャラクターに振り回されがちなのがちょっと気に食わなかった。エタっている。

さらに少しハーメルンを読み進め、午後1時就寝。

01/22(土)

午後5時、弁当を受け取るために少し起きてまた寝た。午後8時半起床。シャワーを浴び、食事して、すぐARC133の時間になった。

AtCoder Regular Contest 133 - AtCoder

Aは丁寧に考えると広義単調増加が途切れる直前の要素を消せばよいとわかる。実装は微妙に注意が必要なのでC++で行った……ところ、言語選択をミスってRubyで出し1RE。直前までRubyで書こうと思っていたせいか。その後Bに進まず5分ほどRubyで縮めていた。Bは実家dpを考えると遷移がO(N\log N)個しかないので間に合う。Cは左上(H-1)\times(W-1)マスにK-1を埋め、残りで調整したところ、サンプル1から合わない。どうやら埋めたK-1を一番下の行と一番右の列に分離することで、右下マスの変化によっては総和が増えることもあるようだ。右下マスがどれだけ増えるかを\bmod Kで全探索し、それに合うように限界まで分離させる（一番下の行・一番右の列が受け入れられる値の和を求めて、\bmod Kが一致する最大値を取る）コードを書いたら通った。Dは累積XORが\bmod 4で分類できるので、左右それぞれ固定。すると\lfloor l/4\rfloorと\lfloor r/4\rfloorが取りうる範囲、またそのXORがどうなればよいかという条件が得られるので、毎回桁DPした。

残り70分でEに進むも、こちらは全く手が出ずコンテスト終了。速めの4完で15位だった。

コードゴルフをする。AはAWKが短くなった。特に要素の削除はgsubを使うのが効く。数値の途中を削除することがないよう、パターンの左右には「単語の境界」を示すアンカーを付けておきたい。Perlでは\bだが、AWKでは\yらしい。ということで、文字列連結として"\y"を隣接させてみたが、動かない。エスケープシーケンスが無視されたというメッセージが出力されている。しばらく考えて気づいた。どうやら、文字列としてのエスケープと正規表現としてのエスケープが2段階に渡って解釈されているらしい。文字列としては\yは無意味なので、\が無視されている。ここで"\\y"とすれば文字列解釈後にちょうど\yとなり、正規表現としてエスケープシーケンスが解釈されることになる。

BはLISになるらしい。確かに。Cは全体にK-1を埋めてから適切に引き算することを考えると最大値ではなく最小値を求める問題になるようだ。行ごとに見たときと列ごとに見たとき、引くべき値の和が大きいほうが答えとなる。それで構築可能なのはまあなんとなくわかることで、コンテスト中の自分も証明せず使っている。上で述べた「限界まで分離させる」というところがそれだ。

午後11時半からCF #767 div.1に出た。

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

Aは貪欲。達成可能なMEXは毎回愚直に検索してもインクリメントの回数がnで抑えられる。あとはそれを達成できる最短のprefixを取ればよく、どうとでもなる。Bが鬼門だった。いつかのICPCで見た、両端から構築してまだ回文になっていない部分を持つ最短経路問題が頭から離れず、4WAと70分を費やした。実は回文が作れるなら高々2つ文字列を使えば十分だとわかる。残り時間があまりない中順位表を確認し、目に入った現在順位に絶望しつつ、より解かれていたD1に移った。nとmをキーにしたdpを考え、遷移を整理すると、maxやminが登場しない形になる。D2は今のO(nm)をO(n)にせよという問題らしく、手でいくらか表を作ってOEISに投げると見つかった。都合よく1か所をO(n)で求める計算式もあるので、オフセットを丁寧に考えて実装、通した。

A193605 - OEIS

最後はCを考えていて、i+jの偶奇で別々に作るそれっぽい構築が見つかったものの時間切れ。ABdDで410位、2891→2736(-155)。これまでで最大の減少幅。ほとんどギャグみたいなBに振り回されて本当に腹が立った。writerのレートが低いため余計に嫌な気分になる。Cは似た問題設定が「天下一王国の歴史」という問題で既出で、その解法から上1段を適当に決めても必ず全マスを奇数回聞ける構築があるらしい。僕が最後に発見したパターンは、そこに至る道筋こそ異なるものの結果的には公式解説の2番目に相当するようだ。

C - 天下一王国の歴史

しばらく日記を書いた後布団に移動し、ラノベを1冊読了。「デート・ア・ライブ アナザールート」。公式アンソロジー。特に「六喰トゥルールート」が良かった。六喰が逆行転移する話で、そういうネット小説を漁っていた自分にどストライク。公式アンソロジーとはつまるところ、職業作家による公式二次創作なのだと体感した。精霊攻略の部分はすっ飛ばし気味であるとはいえ、100ページ程度で本編をまるっと追体験した後、逆行そのものに向き合って綺麗なオチがついているのはすごい。六喰はほぼ最後に登場した精霊ということもあって露出が少なかったが、他の精霊に負けない良さがあるのだと感じた。そういう感情を抱えたまま読み進めると、次の短編は橘公司さん本人によるもので、こちらは完全なギャグ時空で落差にびっくりした。ギャグとしての面白さはピカ一だったので、さすがは作者本人ということか。

さらに2時間ほどハーメルンを読んで午後2時就寝。

01/23(日)

午後8時半起床。今日もシャワーを浴びて食事し、すぐABC236の時間。全完9位。

AtCoder Beginner Contest 236 - AtCoder

Aは短い書き方がわからないのでC++。BはRubyで、tallyを使って集計した。Cは尺取りっぽく書いた。Bからの流れでRubyで書いたが、特に書きやすいわけではない。以降はC++。Dは丁寧に列挙するとO( (2N-1)!!)になる。AOJ-ICPCのどこかの問題で見た覚えのある考察。Eは二分探索を2回やるだけ。Fは難しい。しばらくbitDPを考え続けた後、貪欲でよいことに気づいた。基底として読み替えると、取らなかった要素があるならそれの代わりになる要素が存在し、そのうちのどれか1つと交換しても変わらず基底になることから言える。Gはしばらく並列二分探索を考えていた。bitset高速化も含めてO(N^4/w\log T\log L)になって、さすがに間に合わないように見える（実は間に合うらしい）。ふと、ダブリングで使用した辺が追加される時刻のうち最も遅いものを持てばよいことに気づいた。

Exはかなりすんなり解けた。どうせ包除原理だろうと思って、一致する値のインデックス集合で遷移するO(3^N)のbitDPを書いた。しかしサンプル2が合わない。手で列挙してよくよく眺めたところ、包除原理で引かれすぎているらしい。2要素が同一になる場合として3パターン引かれているが、これらは全て3要素が一致しているから、3要素が同一になる場合を使って重複を省く。どうやらこの係数を+1から変えるべきであるようで、例えば今回なら、3要素が同一になる場合は2要素が同一になる場合を3回含むから、そのうち1回を除いて係数は+2となる。同様に4要素が同一になる場合は3要素が同一になる場合を4回含むため、係数は-(2\times(4-1))=-6となる。ここまでくれば規則性が見えてきて、どうやらnに対しては(-1)^{n-1}(n-1)!が係数になるらしい。これで出すとTLEが出て、毎回LCMを計算しているのが明らかにヤバかったのでそこを前計算したら通った。

コードゴルフ。Aは苦労してVimで書いていたら魔法のように縮められた。最終行でGコマンドを空打ちし、<Ctrl-o>で戻ってこれるようにするのは何となく見覚えがある気がする。とはいえ自力では思いつけない。Bはなんと全部の数のXORが答えになるらしい。まったく気づかなかった。総和を2N(N+1)から引いても求まる、ということにも気づけていない。完敗。CはRaku。TLEすると思っていたが思ったより高速に動作した。EはRubyのbsearch。Fはnoshi基底を使わず、現在生成可能な値をすべて保持すると結構縮んだ。D、G、Exは手つかず。

午後11時半からCodeChef Jan Cook-Offに出た。

https://www.codechef.com/COOK137A

MERGEDLISはそれぞれのLISの長さを求め、足したものが答え。SEGDIVはよくわからない。先頭から順に条件を満たせる値を探索して置いていったら1000未満で構築できてしまい、半信半疑で埋め込んで出したら通った。PRIMEGRAPHは、pをN-1以下の最大の素数としたときNp/2が達成可能な最大値で、この値が整数ならば対称性からうまく配置できそうなので良い。そうでない場合は特にNが5以上の奇数になって、どうしても次数が2の頂点を作る必要が出てくるため、それを1つだけ用いる(N-1)p/2+1が答えになる。

ERASEは先頭から累積minの更新点を列挙して、隣接するどの2つの更新点にも、その2つとそれぞれペアを組めるほかの1点が存在すればよい。と面倒なことを言っているが、つまり2次元平面にプロットしたときに左上と右下に完全に分割できなければよいというだけの話。日記を書きながら証明を思いついた。操作可能なペアに辺を張ってグラフを作ると、これが連結であれば全域木を取って葉から操作することで達成可能。連結でないというのは、つまり左上と右下に完全に分割できる場合である。

BTは頑張った。訪れるアトラクションを選ぶと、それらによって分割されたK+1個の区間を通る回数は順に0,2,\dots,K-2,K-1,K-2,\dots,2,0となる。どの区間もこれより多い回数通ることはできない。左半分だけを考えると、各区間は本来K回通るはずだったのに、あるアトラクションを訪れるとそれより左を通る回数が2回ずつ減らされる、という風に読み替えられる。アトラクションの退屈さも含めて優先度付きキューで管理し、退屈さの減少が小さいほうからK/2個を選ぶことになる。特に、各iに対し、アトラクションiを必ず左からK/2個目に選ぶ場合の退屈さを求めておく。右半分も同様の前計算をする。あとは真ん中のK-1回通る区間を管理しつつ答えを求めることになって、累積maxだのを適切に管理すればセグ木も要らず線形時間で求まる。

BPERMは難しい。1\dots X-1は無視してよい。まずXを置き、その後N\dots X+1を順に配置していくO(NK)の挿入dpを考える。手でいくらかdpテーブルを埋めてOEISに投げるとヒットする。これまたオフセットは慎重に管理せねばならないが、ともかく第一種スターリング数（の絶対値）を計算できればよさそう。検索すると母関数がx(x+1)(x+2)\dots(x+n-1)になるようで、こういう短い多項式がたくさん集まった積は丁寧に畳み込みの順序を管理すれば丸ごと求められることを思い出す。丁寧にとは言っても、実際はセグメント木に乗せれば自動で上手くいく。最初にセグメント木を105まで構築するコードが十分高速に動作したので投げ、AC。

A125553 - OEIS

UNRUPDは面倒。更新は、最下位bitを落とすか、最下位bitから下のbitを全部埋めるかの2つ。後者は連続で行っても特に影響がない。よって、「最下位bitから順にx個落とす→下のbitを全部埋める」で組にしてxをvectorで管理し、これを作用素とした遅延セグメント木を考えることにした。xとしては狭義単調増加なものさえ考えればよく、またx\ge 30だとAが0になってしまうので、vectorのサイズは高々30となり、間に合いそうだ（実際には実装し忘れた）。マージは頑張る。作用は普通にやると時間がかかってしょうがなさそうだったので、かなり頑張ってAのbitの走査を全体で1回しか行わないようなコードを書いた。3.8secで通り、先ほど実装し忘れたと言ったxのサイズに関する場合分けを書き足すと3.5secになった。TLは4secなのでかなりギリギリ。

調子が良かったのかABCに続き全完、10位で2518→2614(+96)。highestである。

3時間ほどハーメルンを読んでいると朝になってしまったので、日記を書いた。昨日からウマ娘プリティーダービーの二次創作を読んでいる。ゲームもしないし逆張りでウマ娘自体に興味がないフリをしていたので、誰が誰かよくわからないが、それでも読ませる文章である。

syosetu.org