03/07(月)

先週の週記を投稿したあとは比較的素早く布団に入ったはずが、寝っ転がったままなろうを読んでいたら寝るタイミングを逃してしまった。さらに今日の午後から来客が予定されていることに気づき、仕方なく起き上がってパソコンの前に座っていた。思いがけず届いた仕送りも受け取れてラッキー。中にとらやの羊羹が入っていてうれしい気持ちになった。

pic.twitter.com/MO5Z9Sgtdy
— こたつがめ (@kotatsugame_t) 2022年3月7日

どんどん眠くなっていって、かろうじて意識を保ちながらYouTubeをボーっと眺めているような状態が続いた。午後4時半からインターン先の定例会なので、何とか進捗報告スライドを生成。先週の進捗は、もしかしたらメッセージをいくつかやり取りしただけかもしれない。これは本格的にまずい。コードを書く以外のことはしばらくする必要がなさそうなので、どこかで気合を入れてガーッと書く必要がある。

定例会とそれに続く勉強会自体は何事もなく終了。今日の勉強会はかなり興味深い話題だったので、あまり眠気も気にならなかった。

シャワーを浴びてしばらくなろうを読み、午後9時半就寝。

03/08(火)

午前7時半起床。

ずっとなろうを読み続けて、午前10時に1作読了。「黄金の経験値」。02/25から実に12日間を吸い取られたようだ。

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

非常に面白かった。序盤はMMOで自分だけのキャラクタービルドを追求していく感じの話かなと思っていたが、そういう感じで真っ当なトッププレイヤームーブをしていたのは50話くらいまでで、あとは人類に敵対するボスとなるべく一直線だった。その他のプレイヤーとは格が違う、突出した強さが読んでいて気持ちいい。プレイヤーキャラクターなのにNPCのふりをするというのもかなり面白かった。主人公はちょっと迂闊なところがある設定だったので、何かボロを出すのではないかとハラハラしていた。そういう部分で頭の回転が速い人が味方に付いてからは多少安心できた。最強ボスとして君臨する主人公に挑む一般プレイヤーたちが真剣にゲームを進めている一方で、主人公陣営では気の抜けるようなやり取りが繰り返されたりして、その緩急もよかった。

ちょっとネタバレになる。600話もあるし、主人公がプレイヤーキャラクターであるという事実はいずれ大々的に明かされるのかなと思って読み進めていたが、本当に隠しきったまま完結してびっくりした。またリアルの話が全くと言っていいほど描かれない点も含めて、徹頭徹尾ブレなかった作品だと感じた。

読了後も布団に寝転がって、しばらくYouTubeを見ていた。先週の週記でも書いたflat-工房というYouTubeチャンネルの動画で、またテンポの良いものを見つけて何回もループしている。

www.youtube.com

ちょっとデュエマの話をする。預言者クルトという1コストパワー500能力なしのクリーチャーがあって、僕はこれをネタカードだと思っていた。普通能力なしなら2コストパワー2000なり3コストパワー3000なり、コストの1000倍がパワーになるべきところ、なんでこいつだけ500引かれているのかと。ただこれは逆で、こいつだけ500足されていたのが正解だったようだ。つまり、1コストのクリーチャーの適正パワーは1000ではなく0で想定されており、本来はそこからデメリット能力を付けて何とか正のパワーを得てカードとなるところを、クルトだけは「光文明→ちょっとパワーが高い」という世界観設定を利用して能力なしで正のパワーを達成したということ。

1コストだけ特別扱いされているのは納得もできる。そうポンポンクリーチャーを並べられても困るということだろう。 $N$ コスト支払える状態でどれだけ場に並ぶかを計算すると、単純に $\frac N 1$ が $\frac N 2$ より倍大きいという話。実際、1コストパワー1000能力なしのクリーチャーはいまだ存在しないらしい。またそれに関連して、凶戦士ブレイズ・クローという1コストパワー1000、能力で毎ターン攻撃しなければならないクリーチャーという、僕ですら見知った太古のカードが現役である（つまり完全上位互換が存在しない）ことはなかなか感慨深い。

二度寝ができなそうだったので布団から身を起こし、大学院の入学手続きをすることにした。まず期限が迫っている学生証用の写真を送信。次に書類を作成する。リストを確認しつつ必要な書類に記入を行っていると、2点、お金の振り込みが必要なものを見つけた。入学料と保険料。前者だけだと思っていたので、見落として郵便局まで往復することにならなくてよかった。外出し、いったん学食で食事し床屋に寄った後、郵便局で振り込んで、ついでに郵送用の封筒を購入してきた。

帰宅して書類を完成させ、再度郵便局に行って速達で出した。この時書留である必要があるかわからず大変に心配したが、後から確認したところ指定されていたのは速達だけだったので一安心。郵便局から直接バイク屋に行って原付を点検のために預け、そこから徒歩でゲーセンに行った。

今日は夕食を挟み午後5時半から午後10時まで。眠気が強く閉店までいてもしょうがなさそうだった。目立った成果もない。14の99AJがいくつか増えたのと、先週木曜日に詰め切れなかった14+を1譜面AJしただけ。ツイートの文面はふざけているが実際はTECHNOPOLIS 2085という曲である。先週、見るのとやるのとでは大違いと言ったものの、何回かやったら出た。

Battlefield 2042 AJ pic.twitter.com/2KnIjPhRZS
— こたつがめ (@kotatsugame_t) 2022年3月8日

帰宅してしばらくTwitterを眺めた後、午前0時就寝。

03/09(水)

いつから起きていたのか定かではない。Chromeの閲覧履歴は午前11時半から始まっているが、その前にどのくらいYouTubeを眺めていたのかがわからない。

正午ちょっと前に布団から出て、ICPCチーム紹介ドキュメントのメイキング記事を書き始めた。手元に届いたらすぐ公開するくらいの気持ちでいたのに、実際には一切書き始められていないまま今日届いてしまった。ただ自分は早いほうだったようなので、まだ少し時間をおいてもタイミングは逃さないだろう。

午後6時までICPC横浜大会のチーム紹介ドキュメントを作成していた。これについては別にメイキング記事を書いて公開する予定だ。
週記（2022/02/28-2022/03/06） - kotatsugameの日記

午後3時くらいまで書いていた。なかなか進まず詰まってしまったので、別のやるべきことを行うことにした。まず、昨日預けた原付の点検が終わっているので取りにいかなければならない。次に、そろそろ期限が切れるパスポートを更新しなければならない。今日はこの2つをこなす。まず県庁でパスポート更新の申請を行い、帰りにバイク屋に寄るのがよいだろう。

県庁のパスポートセンターに行って居所申請をしようとしたら、特別な理由がない限り受け付けていないと言われてしまった。「案内サイトのどこにそのような記述がありますか？」みたいにしばらくゴネてみたものの、普通に「必ず申請できるものではありません」と書いてあって絶望。すごすご引き下がって、今度は富山県のパスポートセンターに電話して代理申請について聞いてみた。こちらは僕が6か月以内に受け取りに行くことも含めて問題なく行えそうだったので、必要な書類を聞いておいて、再度パスポートセンターに行って申請書＋委任状をもらい、またその近くの写真屋でパスポート用写真を撮ってきた。これらとパスポートを合わせて、近々仙台に来る親に渡せば間に合いそう。

県庁を出て、食事する店を探す。仙台レジャーランド一番町店に通っていたころ足を延ばしていた本屋（が入っている三越）は県庁にかなり近いらしい。ということで、そのすぐ近くにあるミスドに入ってドーナツを5個ばかり食べた。フレンチクルーラーは形が特徴的なだけだと思っていたが、中にクリームが入っていてかなりおいしかった。

そこから本屋に寄って、さらにバイク屋まで歩くことにした。本屋からレジャランもレジャランから青葉通一番町駅も何回も歩いた道だし、そこから地下鉄一駅くらい歩いても大して変わらないだろうと思ったのだ。しかし続けざまに歩き通すとなるとなかなかつらかった。歩いている途中にいろいろな食事処を見て、下のツイートのようなことを考えた。30分ほどかけてバイク屋にたどり着き、原付を受け取ってそれに乗って帰宅。帰宅ラッシュかと思っていたけど今日は道が空いていて助かった。

今日あんまり通ったことない道練り歩いて帰ってきたんだけど、知らない呑み屋に突撃したと思しきサラリーマン見て、家で死んでるかゲーセンで板しばいてるかの2択じゃなくてそういうところで飲み食いする幸せもあるんだろうなと思った
— こたつがめ (@kotatsugame_t) 2022年3月9日

「黄金の経験値　番外短編集」を読んだ。

https://ncode.syosetu.com/n9587gk/

ハーメルンを漁ったりYouTubeを眺めたりしているうちにかなり時間が経ってしまった。今日はSRMがあるらしいが、眠いので不参加を決め込む。午後10時半くらいに布団に入り、寝転がったままノーパソを開いて朝の続きでメイキング記事を書いていた。さすがに無理があったので筆は全然進まず、午前0時就寝。

03/10(木)

午前6時半起床。しばらくハーメルンを読んでから、どうせ二度寝はできないと見切りをつけて起き上がった。

チーム紹介ドキュメントのメイキング記事を書いた。午前中いっぱい使って仕上げた。夜に投稿すれば人目に付きやすいかなど考えていたが、今日の午前中にICPCから荷物が届いた人が結構多いように見受けられたので、もう投稿してしまうことにした。

kotatsugame.hatenablog.com

サムネイルの設定が大変だった。何も設定しないと、記事中で最初に使われた画像が設定される。一度その状態で投稿してしまって、慌てて下書きに戻して（別に戻す必要はなかったらしい）再度投稿した。すると記事一覧においてはちゃんと設定されているものの、ツイートに表示されるカードでは先ほどの間違ったサムネイルのままになってしまっている。調べたところ対処法が見つかった。以下の「Card validator」を使うと、ちゃんと現在のサムネイルが見えるようになる。キャッシュされていた、みたいな話だろうか？

https://cards-dev.twitter.com/validator

午後からはずっと日記を書いていた。集中があまり続かず、頻繁にYouTubeを見てしまっていた。月曜日から溜めてしまっていたので、今日までの分を書き終えたころには夕方になっていた。

すでに眠気が強い。布団に入って眠い目をこすりつつラノベを読んでいたが、1冊読了とまではいかず午後9時半に就寝。

03/11(金)

午前7時半に起床。食事して昨日の続きのラノベを読み始めた。残り少なかったこともあり、1時間ちょっとで読了。

「神々の権能を操りし者」2巻。主人公が特殊対策部隊というチームに入ったところから始まる。1巻は確か学校内での出来事だけだったので、序盤のちょっとしたざまあ描写を除けば全く新しい場所のスタートとなり、前巻の内容をほぼ覚えていなくても何とかなった。1巻を読んだ時の日記を読み返すと下のような疑問が残されていたが、確か主人公が持っている全部の能力を見せてしまったように思えたのが引っ掛かっていたはず。2巻において、主人公の能力は全然そんなものじゃなくてもっとぶっ飛んでいることが分かったので一安心。文章的には、主人公視点である地の文のノリがあまり好きになれない。

1巻から実力を周囲に知らしめていて、手っ取り早い満足感があった。しかし2巻以降はどういう展開になるのだろうか。
週記（2021/09/20-2021/09/26） - kotatsugameの日記

別のラノベを開いてしばらく読み進めた後、訪れた眠気に逆らわず再度就寝。午前11時から午後4時まで寝ていた。

少しパソコンを触った後外出。ゲーセンに行く。油そば屋に寄って食事しつつ、午後6時から午後11時前まで遊んだ。今日の成果は理論値が3譜面と14+のSSS+が2譜面。

Bad Apple!! feat.nomico (REDALiCE Remix) 理論値 pic.twitter.com/4gylCZxP0i
— こたつがめ (@kotatsugame_t) 2022年3月11日

序盤の跳ねリズムの勝率が低く、結構な回数の捨てゲーをしてしまった。そのうち道中でもポロポロ赤を出すようになってきて明らかに止め時ではあったのだが、エアーだったりラストのスライドの終点だったりで一落ちを出していたのでどうしても諦められず、何とか捻り出した。

立ち食い蕎麦屋で食事して帰宅、午後11時半からCF #777 div.2。記念すべき第777回ということで、これに間に合うよう閉店前にゲーセンを離脱してきたのだ。

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

Aは $n\bmod 3$ で場合分けして1212...か2121...を出力する。Bは、「2x2マス内に1がちょうど3個存在する」ような箇所が存在することと答えがNOであることが同値であることに気づいてすぐ解けた。まず $(\Rightarrow)$ については、2x2マスの中で0を含まないように2種類長方形を作ったとき、それを適当に拡大して得られるniceな長方形が包含関係になく、また交差することからわかる。 $(\Leftarrow)$ については対偶を考える。0と1が隣接しているところを探し、そこから上のような2x2マスが存在しないように広げていくと、1の連結成分が必ず長方形になることからわかる。Cはギャグで、1x2か2x1を使って右下から塗っていけばよい。一番左上のマスは明らかにどうやっても黒くできないが、それ以外は今言った方法で対応できる。

Dは問題文がカス。先に本題以外の場合分けを説明する。 $x/d$ が $d$ で割り切れなければNOである。以降 $x=d^a\times y$ と分解する。ひとまず $\{d,\dots,d,dy\}$ という分解があるので、適当に組み替えてもう一種類を見つけられればYES、存在しなければNO。 $y$ が合成数ならそれをさらに分解すればよい。 $y=1$ なら $d$ を分解するしかなく、 $d$ が合成数であることに加えて $a\ge 3$ が必要である。

$y$ が素数の場合、こちらも $d$ が合成数であることと $a\ge 3$ が必要となる。ただ十分ではない。今度は逆に $d=y^b\times e$ と分解してみる。 $e\gt 1$ のとき、 $b\ge 1$ なら $\{d,d,dy\}\rightarrow\{de,dy^{b+1}\}$ と組み替えられ、 $b=0$ なら合成数 $e=d$ を適当に分割できるため、それぞれYESとなる。 $e=1$ のとき、 $d=y^b$ 、 $x=d^a\times y=y^{ab+1}$ とどちらも素数 $y$ のべき乗で表せる。 $b\ge 3$ ならば $\{y^b,y^b,y^{b+1}\}\rightarrow\{y^{b+\lfloor(b+1)/2\rfloor},y^{b+\lceil(b+1)/2\rceil}\}$ と組み替えることができる。 $d=y^b\ge 2$ と $d\ne y$ より $b\ne 0,1$ もわかるので、最後に $b=2$ の場合が残る。 $d=y^2$ 、 $x=y^{2a+1}$ である。

さて、ここで2つの分割が異なることを定義している文章「Two ways are different if the sets of numbers used are different.」が問題となる。「sets of numbers」とあるので、分割した後の数たちが「集合として」（＝重複を省いたとき）一致していれば同じ方法だとするんだな、と思った。このとき、すでに $\{y^2,\dots,y^2,y^3\}$ という分割があり $\{y^2,\dots,y^2\}$ という分割は不可能なので、 $\{y^3,\dots,y^3\}$ が可能かどうか、つまり $2a+1$ が $3$ で割り切れるかどうかで場合分けすることになる。しかしWA。40分くらい苦しんだ後、ふと「多重集合として」一致するかを見るようなコードを提出することを思いついた。この解釈の場合 $a\ge 4$ ならば $\{y^2,y^2,y^2\}\rightarrow\{y^3,y^3\}$ が許されてYESになる。これで出したら通った。

the sets of numbers used are differentって集合として一致しないことを言ってるんじゃないんか張り倒すぞ pic.twitter.com/2EtCq74U0P
— こたつがめ (@kotatsugame_t) 2022年3月11日

Dを通した後に上のツイートのようなclarを投げていたので、残り30分しかない。Eに進んだ。数列 $\{p_i\}$ が順列ではなくてびっくり。最初はループとそこに向かういくつかのパスに分解して、ループの中の数字はもともとループの中にあるとしてよいと思っていたが、最後のほうまで書いてから、パスから侵入してきた数字がループの中の数字を蹴り出す場合も普通にあることに気づいた。するとループの検出など面倒な操作を一切行わない解法が浮かび上がる。与えられた状態まで何ステップかかるかが一意に定まるので、それをもとにダブリングで各マスがどこに行くかを求めると、それぞれ入れてよい数の最小値が求まる。この条件に加えて、その最小値が同じマスたちのうちどれかには実際にその値が入っている、という状態であれば良いことがわかるので、先に後者の条件を満たした後前者の条件を満たすようsetなどで値を埋めていけばよい。これらはすべて先頭から貪欲に決められる。

ちょっと迷走し、Fに辿り着いた時点で残り5分。問題文を読んだぐらいで諦めた。システスは全部通って5完76位。D問題の問題文にはさすがに腹が立ったので、初めてコメントを書いた。しかし見返してみると、ただしょんぼりしているだけの人に見えるな。もうちょっとはっきりゴネておけばよかった。

https://codeforces.com/blog/entry/100739#comment-894976

布団に入ってラノベを1冊読了。「創成魔法の再現者」。初っ端から上下巻になっていて、1巻で話が一段落していない。基本的に主人公の能力で無双してはいるのだが、その下準備となる敵キャラに陥れられる描写がかなりえげつなくて辛かった。貴族階級の人間は生まれつき魔法を持っていて、爵位よりその強さだけで発言力などが決まってしまうという設定らしい。いろいろ考えさせられる話。今のところ敵の首魁となっている王子はこの魔法が強すぎてかなり無茶苦茶やっており、主人公たちが力で対抗する舞台を整えるだけでもかなり大変な目に遭っていた。

魔物の脅威があって、それを撃退する役目を負う代わりに様々に優遇されるのが貴族階級の人間であるということだから、魔法が強い人が偉いというのは理にかなっている。そのような常識を変えようとする主人公陣営にどのような正当性があるのか、というような話も出ていた。また魔法が強ければ偉いなら主人公も偉いはずだが、主人公は一度才能なしとして追放されていたもので、そこから戻ってきた前例がないため周囲の人間も強さを認めるに認められない状態になっていて、さらに苦しい。どうあがいても普通に手に入れた強さではないことが明らかなのだ。

さらに別のラノベを開いて読み進めた後、午前6時半就寝。

03/12(土)

午前10時半ごろ目を覚まし、うっかりスマホを触り始めてもう眠れないかと思ったのだが、何とか二度寝に成功した。次に午後0時半起床。食事してTUPC2021の観戦を始めた。

https://onlinejudge.u-aizu.ac.jp/beta/room.html#TUPC2021

TUPC2021を開催しました | puzzleknot 公式サイト

まず最初に言っておくと、僕は全体テスターとして参加しただけで1問も作っていない。全問にそれなりのACが出て、かつ全完が1チームもないという完璧なコンテスト設定だった。サークルのメンバーが強くなりすぎていて怖い。以下、コンテスト前に予想した難易度順に、各問題に対する感想を書いておこう。ACGIJKDEFBHである。実際のsolved数は、タイブレークを都合よく決めればACGIDJFKEBHの順だったので、編集距離的に考えれば外したのはDとFだけとかなりうまく評価できていたのではないか。

A - Unique Nickname。84AC。最初この問題は存在せず、C問題が一番簡単な問題として置かれていた。さすがにもうちょっと簡単な問題を置いてほしいと要望を付けたところ出てきた問題。急いで作ってもらった問題とは思えないほどTUPCらしいものになっていて感動した。

C - Extreme Balance。64AC。実はジェンガの進行を表現しているということで、そういう論文を探すと定数時間での判定法が見つかったそうだ。ただ、あまりに単純すぎて実験エスパーでも容易に同じものが得られる一方、その証明は論文になるほど難しいようで、仕方なくこの制約でこの位置に置かれたという経緯があるらしい。

G - Tree Happiness。57AC。特に言うことなし。ここまでが簡単枠だと見ていた。

I - Range Totient Query。52AC。想定解はなかなか頭のいいことをしているが、ABC238-Gのユーザ解説のようなMoでも解ける。つい最近見たのでこの位置と予想。

https://atcoder.jp/contests/abc238/editorial/3377

J - WISWIS。33AC。少し面倒な行列累乗。

K - Autumn Triangle。13AC。式変形すればやることはすぐわかる。凸包だけ見ればよくて尺取りできる、という事実は少し考える必要があるのでこの位置に。もともと $N\le 3000$ だったので $\log$ をつけて大丈夫か少し怪しかったが、制約を調整したのでいい感じになったのではないだろうか。ただ単純な全探索が爆速過ぎて $O(N^3)$ と $O(N^2\log N)$ を区別できずPythonお断りになった上、普通にC++の $O(N^3)$ が通ってしまった。ここまでがテスター作業時にすぐ解法が分かった問題である。

D - ABS Pairs。45AC。これはエスパー含めた難易度予想で、証明をつけるのはそこそこ難しい。僕もテスター作業時未証明で通してしまった。操作順も答えさせるという話が出ていたようだったが、スペシャルジャッジの設定がわからず見送られてしまったという悲しい裏話がある。結果的には、エスパー含めた難易度で予想したはずなのに大きく外してしまった。

E - LEQ and XOR。13AC。解説のように $A_{N+1}$ を定義するのが頭良すぎ。僕は思いつけなかったのでかなり苦労したが、数日頭の中で寝かせた結果何とかゴリ押せた。普通のdpを書くと、同じ値が結構連続するとわかる。それらを圧縮すると $O(\log M)$ 個くらいになるので、その状態で行列累乗できるかと思ったものの、どの位置の値が一致するのかがバラバラだったので失敗。そもそもなぜそんなに同じ値が連続するか考えると光明が見えた。

例えば $M=5$ のとき、 $[0,M+1)=[0,6)=[0,4)\cup[4,6)$ と分割する。 $[0,4)$ は下2bitが自由に定められる数、 $[4,6)$ は下1bitが自由に定められる数とみなせ、 $[0,4)$ から1つ、 $[4,6)$ から1つ選んでそのXORを計算すると $[4,7)$ が2つずつ得られる。これは下2bitが自由に定められる数が $2^1$ 個ずつという意味である。一般化すると、下 $n$ bitが自由に定められる数と下 $m$ bitが自由に定められる数のXORは下 $\max(n,m)$ bitが自由に定められる数 $2^{\min(n,m)}$ 個ずつである、と書ける。これを利用して頑張ると、最終的には解説のような式の再帰をループにしたようなものが得られる。

F - Gift Exchange。28AC。初見では二乗のところが一乗だったら無理だろと思って、二乗であることを用いる解法を探して迷走を始めてしまったが、NTTで解けることに気づいて戻ってこれた。それを元に二乗の式を展開すると、何もかもNTTで解ける形になって感動。ちょっと前まで $N\le 10^5$ でPythonお断りだったので、さすがにもうちょっと小さくしてもいいだろと思って制約を調整してもらった。多少筋力があれば通せる問題とはいえ思ったより解かれたなという印象。これも難易度予想を大きく外した問題。

B - Minimum Upper Sum。4AC。多分6時間くらいかかった。愚直dpを整理するといかにもCHTっぽい形になるが、そこからどう実装するのかが難しい。追加クエリも取得クエリも単調なので蟻本にあるdequeのCHTで通せるだろうとかなり試行錯誤して、なんとか通した。これについてはテスター解説を書いてある。LiChao Treeを書いたことがなくて、Undoが簡単にできるのを知らなかった。

B - Minimum Upper Sum.pdf のコピー - Google ドライブ

開始21分で解かれてひっくり返っていたら、既出だったらしい。まあシンプルな見た目だし仕方のないところはあるだろうか……。

https://codeforces.com/contest/1175/problem/G

H - Magical Shuffle。4AC。ボス問。5時間考えて想定解の方向に一歩も進めず、自力で解けなかった。そのくせコードは単純になるのでAGCっぽい最高の問題だと思っている。これも既出でないかだけが心配だった。

ラノベを1冊読了。「迷子になっていた幼女を助けたら、お隣に住む美少女留学生が家に遊びに来るようになった件について」。タイトルからわかる通りの半同棲ラブコメ。主人公もヒロインも怪しげな過去を抱えていそうではあるが、1巻の今は特に明かされず2人の馴れ初めを描くに留まっている。つまりそのうち否応なしに重い話が入るということで、ちょっとひるんでいる。またタイトルにもある「幼女」の行動が好きになれなかった。この子の強引な行動がなければ2人の関係が進展することもないとはいえ、強く咎められることもなくずっとわがまま放題なのにイライラしていた。もともと子供が好きではないというのもあるかもしれない。

しばらく日記を書いて、午後9時からABC243に出た。

AtCoder Beginner Contest 243 - AtCoder

Aは $V\lt A$ と $V\lt A+B$ を判定すればよいと思って書き始めつつ、サンプル3を見てひっくり返った。確かにどこにも $V\lt A+B+C$ のような制約はない。最短コードが自明な問題ではないので、いったんAWKで書いてお茶を濁した。BはRaku。どう書いたものかしばらく手元で試していたので問題なく通った。ここからC++。CはY座標でグループ分けした後X座標の昇順に見れば十分。Dはstackで操作を圧縮、ただしstackを使うと残った操作を前から順に行うのが難しいので慌ててdequeに書き換えた。

Eは難しい。とりあえずワーシャルフロイドを書いて、最短経路の候補にならないような辺は削除できる。問題は候補には挙がるものの別の辺複数本で再現できるような辺の検出である。適当に最小全域木を取ってみてもどうにもならないようだったので、改めて考えなおすことにした。すると、辺複数本で再現できるとしたとき、その中継点を全探索すればワーシャルフロイドで求めた距離行列から実際に再現可能かチェックできることに気づいた。

F問題はずっと包除原理を考えていたが、どうしても各 $1\le n\le N$ に対し、 $\binom{N}{n}$ 種類の「賞品 $n$ 個の $W$ の和を $K$ 乗したもの」の和が必要になる。これを計算するために、 $K$ 乗を展開した形でどの $W$ が何回出現するかで遷移していくdpを考えたところ、それを利用すれば直接的に問題が解けることに気づいた。30分くらいかかってしまった。

Gは簡単。 $X\le\sqrt[4]{9\times 10^{18}}$ までは愚直にdpができる。 $X\le\sqrt{9\times 10^{18}}$ までは、いま求めたdp配列の先頭 $\sqrt X$ 項の和になるので、事前に累積和を取っておけば定数時間で求まる。本題の $X\le 9\times 10^{18}$ の場合、 $1\le i\le\sqrt[4]{X}$ に対して $i=\left\lfloor\sqrt X'\right\rfloor$ となるような $1\le X'\le\sqrt X$ の個数分だけ「dp配列の先頭 $i$ 項の和」が答えに足されることになるので、 $i$ を全探索すれば $O\left(X^{1/4}\right)$ で解ける。

EFで時間を使いすぎて残り30分もなかったのに、Ex問題を見つつ順位表を確認するとまだ1ACも出ていなくて腰を抜かした。実際に問題文を読んでみると最小カットの数え上げみたいなとんでもないことが書かれていたので、早々に諦めてコードゴルフしていた。7完34位。

コードゴルフ。Aはdc。 $(V\bmod(A+B+C))-A$ と $(V\bmod(A+B+C))-A-B$ をそれぞれvコマンドに通して、出力に応じてスタックの深さを分ける方法。ただし今回、出力すべき文字の文字コードが70、77、84ということで、3連続の7の倍数になっている。実は先ほどの操作後のスタックサイズ（0、1、2のどれか）に10を足して7を掛けるとちょうど対応した文字コードになるので、この出力部の改善でかなり短くできた。Bはコンテスト中のRaku。さすがにもうちょっと何とかなるんじゃないの、という見た目をしているが、今のところどうしようもない。

CはRuby。Y座標でgroup_byした後チェックするというのんきなことをやっていたら、まとめてソートする方法で大幅に縮められた。そうでなくてもX座標は数値の大小だけが重要なので、to_iではなくhexが使えるという更新にも気づけず。DもRuby。LとRをそれぞれ0と1に置換しつつ読み込んで、文字列をスタックとして扱う。後ろから1文字切り離すのがchop!でできるということは他の人のコードを読んでいて気づいた。EはOctave。Fは手つかずで、GはRubyのメモ化再帰。2項ずつ進んでいくようにすると十分高速らしい。ただ平方根を計算する部分で普通に0.5乗すると精度の問題でWAになったため、bsearchを持ち出した。

布団に入ってしばらくハーメルンを読んでいたところ、僕とコードを共有した疑いでCodeChefからメールが来たという人をTLで観測した。慌てて自分の受信メールを調べると、プロモーションのところに入っていた。僕が関係するものでは5組くらいコード共有の疑いがかかっているらしい。一つ一つ確認してみると原因が分かった。 $O(1)$ 算数の問題でACLのmodintを貼ったのだが、このときコード全体のうちおよそ97%もの行がライブラリに由来するコードとなってしまい、結果同じくmodintを貼った人のコピペであると検出されてしまったようだ。異議を申し立てる……前に、メールに記載されているリンクから不正に関する取り決めだったりFAQだったりの文章を3つ読んだ。せっかく英語を読んだのでここに、特に今回のケースに関係する部分をまとめておこう。

CodeChef's Code of Conduct | CodeChef

よくある参加規約とほぼ同じに見える。今回関係するのは7番で、ライブラリの利用について。そもそもクレジット表記などがあることを期待されているらしいが、それがなかった場合にも一応救済は用意されていて、そのコードがコンテスト開始前に公開されていたことを自力で証明すればよいらしい。

Plagiarism FAQs - Google ドキュメント

一番上のものが関係する。MOSSというのがコピペコードを検出するシステムの名前で、それによって誤った検出がされてしまった場合の話が書いてある。対処法はCode of Conductにあるものと同じ。それより下のほうはそこそこ面白くて、今のケース以外でコードを共有していたらもう助かりませんよということが、複数の言い訳にそれぞれ対応して執拗に書いてある。

The Cheating Cases Saga | CodeChef

これはポエムなので読む必要なし。運営も大変だということだけが伝わってくる文章になっている。

ということで、結局僕のコードがACLに由来すること、またACLがコンテスト前に利用可能だったライブラリであることを証明すればよい。英作文してメールを送った。かなり疲れた。~~（仮にも世界ランク40位なんだから何か優遇措置はないだろうか……）~~

Hello CodeChef.
This is kotatsugame. I request you to do a manual check because of MOSS's false positive.Nearly 97% of my solution is come from ACL (AtCoder Library), which is a third party library with CC0 license. The link is here.https://t.co/ujGbwPspQy
— こたつがめ (@kotatsugame_t) 2022年3月12日

ハーメルンを読み続け、午前5時半就寝。

03/13(日)

午前11時起床。今日はコンテストがないので自由。

かなり眠かったはずなのにうっかりハーメルンを読み始め、二度寝しよう二度寝しようと思いながらもずるずる夜まで読み続けていた。午後8時半に1作読了。「強めのモブウマ娘になったのに、相手は全世代だった。」。

syosetu.org

面白かった。主人公はあくまでモブウマ娘ということで、まあ勝てない。勝てないといってもそこはお話の都合上かなりいい成績を残してはいるのだが、ほかのウマ娘ハーメルンの主人公に比べると、という話。ほかの強い主人公を据えた作品でも、レースに勝利することでほかのウマ娘の夢をへし折っているということはいくらか言及されてはいたものの、それを「へし折られる側」から読むと苦しいものがあった。普段主人公最強モノしか読まないので、余計に。幸い主人公は一回の敗北で落ち込んだりする様子がほぼなかったので、その点は安心して読めた。

作者の活動報告からあとがきを読んで、さらにこの人のお気に入り小説から1つ見繕って読み始めた。午後10時半に読了。「秒読みの契約　～あなたに三つの冠を～」。天才トレーナー主人公は良いもののちょっと不穏なところでエタっていて厳しい。

syosetu.org

結局二度寝できないまま夜になったので起き上がった。昨日のABC243-Eが縮められていたので縮め返した。辺の重みを $-\varepsilon$ しておくと判定が簡単になるというやつ。そのあとは未明まで日記を書いていた。未明と書いた部分は最初夜更けと表現しようとしていたが、調べたらもっと早い時間帯を指すことが分かって慌てて別の表現を探した。