05/30(月)

日曜日は週記を投稿してからすぐ布団に入り、少しYouTubeを見て午前9時前に寝た。

いい感じの時間に起きて少し進捗を産んでからインターン先定例会に出席しようと思って、午後2時から30分おきに目覚ましをかけていた。一応意識は取り戻すものの布団から身を起こすことができずまたすぐ寝入ってしまい、気づいた時には午後4時半になっていた。飛び起きてオンライン会議に接続。ギリギリセーフだった。

先週の進捗は、ない。集中講義だったということで許してもらえないだろうか。そもそも自分で自分を許すべきではない気もする。これまで書いたコードが今、デプロイされたことによって自分の手を離れたところで動いているはずだが、それに関するフィードバックも一切ないため本当に報告できる進捗がない。先週水曜日の日記に書いたようにキャッシュの問題でうまく使えないということもあり得るようなので、そもそも動いているのか心配である。これに関してはまたメッセージで確認の催促をしておく。

勉強会まで終えてからは、ずっと講義の課題に取り組んでいた。先週と同様に今日締め切りの課題が2つ、明日締め切りの課題が1つあって、気合を入れて全部終わらせてしまった。ゲーム理論と離散数学については特に感想もない。

ハードウエア基礎は面白かった。MOS トランジスタを用いていくつかの論理回路を作るという話で、まずNOT回路がトランジスタ2個で実現される。そして、次に作るのがNANDとNORだった。それぞれ並列・直列つなぎを用いるという自然な発想からトランジスタ4個ずつで実現されていたが、そのように素直に構成したものがANDやORではなくその反転であるという事実に衝撃を受けた。NANDのみですべての論理回路を構成できることは事実として知ってはいても、パズルの一種以上の意味はないと思っていた。案外そうでもないらしい。

さらに集中講義の課題に取り組みつつ、午後11時から1時間ほどしぐれういさんの配信を視聴していた。いわゆる赤スパが結構乱れ飛ぶ配信であったが、特に5万円のスパチャが流れたときにコメント欄が大盛り上がりだったのが印象的。1万2万出すのと5万出すのは結構違う受け取られ方をするようだ。額面が大きすぎて、自分では差に想像がついていない。

www.youtube.com

平面グラフの頂点数と辺数について、 $V\ge 3$ のとき $E\le 3V-6$ という関係が成り立つ。これを用いて、整数 $n$ であって「任意の $n$ 頂点グラフについて自身と補グラフのどちらかは非平面的」を満たすような $n$ の最小値を評価せよという問題があった。結論から言えば $n\ge 11$ が出る。では $n=10$ では自身も補グラフも平面的な例があるのかと思って、しばらく適当なグラフを作っていたのだが、すぐ $K_{3,3}$ をマイナーに持ってしまう。結局構成できずTwitterに質問を投げた。

リプライで、 $n\ge 9$ ならどちらも非平面的になることが示されていると教えてもらった。「EVERY PLANAR GRAPH WITH NINE POINTS HAS A NONPLANAR COMPLEMENT」というタイトルの論文。読むと、次数列でいろいろ場合分けして各個で示しているようだった。そちらに深入りはしないものの、 $n=8$ で両方平面的になるようなグラフがあるのならそれは構成しておきたい。適当に頂点を繋いでみると一発で見つかった。

n=8できた。目の錯覚じゃないよ pic.twitter.com/6wIuJgnwZA
— こたつがめ (@kotatsugame_t) 2022年5月30日

辺がぐにゃぐにゃしていて大変複雑なグラフに見えるが、並び替えてみると見事に綺麗な平面への埋め込みが得られた。ほかにも補グラフが孤立点を持つような構成があったりと、 $n=8$ なら適当にやってもすぐ見つかるらしい。それが $n=9$ になった瞬間全部ダメになるというのだから、驚きの事実である。

整理したらえらい綺麗になった pic.twitter.com/89yYmfoRbV
— こたつがめ (@kotatsugame_t) 2022年5月30日

午前3時くらいから集中が切れてハーメルンを読み返していた。「輝きたくて」。何度も読み返している作品だが、最近Vtuberを見るようになってまた新たな発見があった。というか、元ネタとなったVtuberをいくらか判別できるようになっていた。しかしこれ、何回読んでも面白いな……。

syosetu.org

そんなことをしていてはいけないぞということで気合を入れてページを閉じ、日記を書いてゴミを出して布団に入った。明日もミーティングがある……と思いながら少しなろうを読んで、午前8時半就寝。

05/31(火)

午後3時前に起床。準備して1時間ちょっとのミーティングへ。

ちょっと新しいことを始めることになりそう。今そちらは手が足りていないらしい。こちらとしてもデプロイを終え一段落ついた感じがするし、進捗をほぼ産めない状態が続いているから、この辺りで一つ誰かと連携して作業することでちゃんと毎週稼働するペースを作っていきたい。というか、僕自身の稼働より会社から貸与されたPCの稼働が問題で、せっかくごっついGPUを備えた物を送ってもらったのに、いつの間にか機械学習を使わないコードばかり書いてしまっていたのが気になっていた。

終えてからもちょっと考え込んでいたら、購買が閉まるギリギリの時間になっていた。原付を飛ばして駆け込み、カロリーメイトを買ってミールカードの残高を調整。そのまま夜の部が開店した学食で食事して帰宅した。購買の閉店時刻と学食夜の部の開店時刻が一致しているのは辛い。

かなり眠気があって布団に倒れこんだ。しかし眠らず、しばらくにじさんじ非公式wikiを眺めていた。今、現実のVtuber（？）を少し見るようになって、現在どのように活動しているかは何となく感じ取れる。しかし人に歴史ありということで、現在に至るまでの数年間の活動から生まれた膨大なエピソードに圧倒されていた。リンクされていた動画に飛ぶと非公開になっていたりするのも、Vtuberという存在が誕生してから経過した時間の長さを感じる要素。

人が泣いているのに弱いので、こういうシーンを説明されるとすぐ自分も涙ぐんでしまう。

youtu.be

午後9時前に起きあがって、昨日の続きで集中講義の課題に取り組み始めた。途中でICPCの参加登録が始まったので、とりあえず個人アカウントの設定を確認して、学士から修士に変更したりしておいた。

午後11時半からCF #795 div.2。

Dashboard - CodeCraft-22 and Codeforces Round 795 (Div. 2) - Codeforces

Aはよく見ると偶数か奇数のみの列になる。Bは靴のサイズの小さいほうから誰のところに行けるか考えると、サイズが同じ人たちで交換し合うしかないことがわかる。よって各サイズに2人以上いる必要があって、いる場合は適当にrotateしておけば十分。Cは各桁に対する $f(s)$ への寄与を考えると、末尾が $1$ 、先頭が $10$ 、残りは全部 $11$ であるとわかる。従って、できれば末尾に'1'を持ってきておきたい。最初にそれを試して、次に先頭に'1'を持ってこれるか試すことになる。'1'が一つしかない場合に注意。

Dは $\max$ を決め打つと使える区間がわかるので、区間の $a$ の和を最大化する。累積和を取っておけば、右からその最大値を取って左から最小値を取ると言い換えられるので、適当にデータ構造を使えば解ける。区間のマージと読み替えると線形でも解けそう。Eは区間の端点でイベントソート。区間が消えるタイミングでもっと右にある別の区間と「直接」繋がっていなければカウント、という大嘘をついて1WA。間接的につながっている場合もある。結局UFの辺を頑張って省略するのが間違いがない。ちょっと考えると、例えば赤の区間が消えるタイミングで青の区間に辺を張るとき、その時点で保持している青の区間すべてに対して辺を張っておけば、以降青の区間は最も遠くまでカバーするものだけ残しておけば十分とわかる。これで辺を張る回数が線形になって、通った。

Fはいかにも全方位木dpのような装いをしている。まず木dpを考えてみると、各頂点に対して $S$ のLCAが自分になる場合の数を求める方針が立つ。 $u$ の部分木の頂点数を $c_u$ とすると、とりあえず $\binom{c_u}{K}$ 通りあって、ここからもっと下の頂点がLCAになる場合を引く。一段下の子を考えた瞬間に完全に独立した事象となるので包除原理は必要なく、 $u$ の子 $v$ に対して $\binom{c_v}{K}$ を引くだけで求まる。こうして求めた場合の数に $c_u$ を掛けて答えに加えることになる。そして、このように一段階下の子しか見ないなら~~容易に~~（別に容易ではない）全方位木dpに書き換えられる。 $u$ から $v$ に移動するときは $u$ と $v$ の持つ値のみを注意深く修正すればよい。今いる頂点を根としたときの値を持ち続けることを意識するのがコツか。

システスは全部通って6位。Eで迷走したのが痛い。Fの全方位木dp部分はなんだかんだ更新12行・巻き戻し12行とすごい実装になってしまったが、一発で合ってくれて助かった。しかしtouristはCFのルールでtourist出しして1位を取っており、圧巻。

ハーメルンを1作読了。「ありきたりな正義」。集中を切らしすぎて課題レポートを書きながらチラチラ読み進めていた。設定は好みで、展開は今のところそこまででもない。原作前スタートだが大胆に時間を飛ばしてくれているのですぐ1巻時点まで辿り着きそう。

syosetu.org

午前9時頃までかかって、ひとまず課題となっていた設問にはすべて回答を作成できた。あとは講義の感想が求められている。先週の週記で毎日面白かったところをまとめていたので、それを引き写してくればよさそう。追加で昨日見つけた、頂点数 $8$ で自身も補グラフも平面的なものを載せておけば十分だろう。これでついに課題レポートが完成。ページ番号を振ってみたところ、実に19ページあった。スキャンの手間も無視できないサイズ。06/05期限だからと言ってギリギまで溜めていたら大変なことになっていただろう。

レポートを提出してしばらく日記を書いた後、生協に向かった。食事して、予約していたラノベを受け取り、床屋で散髪。今日は眠すぎて髪の毛に鋏を入れられている時ですら容赦なく首をグラグラさせてしまった。また、ついに200円ほど値上げしたようで、世知辛い。

帰宅して5月分の読書記録をツイートした。今月は何に時間を吸い取られていたのかわからない。なんだかラノベをうまく読み進められない時期があった気がする。文章をじっくり読んでしまってページが進まない、という感じ。適当に読むという能力も必要らしい。

5月の集計
買った：22冊
読んだ：8冊
積読：+14冊
積読（累積）：+47冊
— こたつがめ (@kotatsugame_t) 2022年6月1日

午後2時前にこれまでの日記が書きあがり、すぐ寝た。

06/01(水)

消えた。

06/02(木)

午前0時半起床。

DDCC2022の予選申し込みが始まっていたので、登録しておいた。今年は新卒枠に入れるので予選通過しやすそう。いや、去年も新卒枠だった気がしてきた。理系大学生は二度卒業するということで。

YouTubeを見ながら午後からのセミナーの準備を始めた。結構前に作ったカンペがあり、そこにメモしていない行間を再現して記憶を掘り返す、必要ならばメモを書き足す、という作業になる。それが最初に準備したときを含めてこれで3回目。さすがにここまで発表の機会が遠のくとは思っていなかった。ちゃんとメモをするべきだとわかってはいるが、しかしちょっと考えればわかると判断したからカンペに書かなかったのであって、直前に急いで準備している状態だとそんなのに紙幅を割くのは面倒だなあと考えてしまう。余裕を持って準備する必要がある。

以下、セミナー準備について話すことはないので、見ていた動画についていくつか書いておく。

www.youtube.com

昨夜、犬山たまきさんの3D LIVEが行われていたらしい。ゲストもかなり豪華。やはり動画になると、生配信より情報の密度が高くなってより面白く感じられる気がする。まあ用意するのは大変そう。いくつか特に好きなシーンがあるので、以下に列挙する。

38分26秒。「判決は……」のセリフとともにしぐれういさんの眉がキリッとするのが良すぎた。細かく表情が変わるのすごいなあ。どういうトラッキングを行っているんだろうか、あるいは手で表情を付けているのか。

https://youtu.be/Rzxdn5YT_BM?t=2306

40分50秒。「うい先生盆踊りしてる？」というコメントがあって、探して見つけた。このシーン、後ろで踊っているしぐれういさんの振り付けが確かに盆踊りのように見える。可愛すぎ。

https://youtu.be/Rzxdn5YT_BM?t=2450

またその少し後から舞元啓介さんが歌い始めるのも非常に良かった。それまでもしぐれういさんの切り抜き経由で何度も目にしていたが、火曜日に氏の非公式wikiを読んでからより直接的に興味が湧いている。

ただ↑の動画はループ再生には向かない。今日の作業用BGMはこれ↓。これまた火曜日にNJU歌謡祭2021のアーカイブをところどころ見ていて、特に気に入ったシーンのうえ探すとそこだけ切り抜いた動画が公式で上がっていたので採用。一番気に入ったのはラストのVirtual to LIVEだが、これはさすがに動画にはなっていなかった。ライブで歌っているということで、歌動画として考えれば完成度は高くはないのだろう。しかしなぜかループして聞いても全く飽きない。

www.youtube.com

朝になったので切り上げて布団に入った。午前9時就寝。

午後0時半、外から大きな音が鳴って起床。雷らしい。その後すぐ強く雨が降る音が聞こえてきて、セミナーのため山に登るのが億劫になった。午後1時半ごろに布団から出て、外を見ると案外晴れている。天気予報を確認すると、夜までは何とか天気が持ちそうな感じだったので、カッパだけ持って原付で山に登ることにした。

学食で食事。いつものように納豆を2パック購入したら、片方をプリペイドで会計された。どうやら1回のレジにつきミールカードで納豆は1パックしか買えないという制限があるらしい。確かにそういう制限の一覧を学部1年生のころに見た記憶はあるものの、それ以来4年以上通って、特に引っかかった記憶がない。こうやってルールに厳しい人と厳しくない人がいると計算が狂うので困る。しかもなぜか、ミールカードによる会計とプリペイドによる会計が分けて行われていた。それはもうレジに2回通したのと何も変わらないだろう（屁理屈も理屈である）。納得いかなかったので一言カードにクレームを書いてきた。もしこれによってルールが厳格化されるなら、ちょっと余計なことしたなという気持ちになるが、今日みたいに急にプリペイドから引き落とされるよりはマシだと僕自身は感じる。

山に登って午後3時からセミナー。今週ももう一人の人は集中講義に出席するそうなので、今日は僕と指導教員の一対一になった。用語や記号の定義はだいたいすっ飛ばしての発表にできるから、もしかしたら用意していた分で足りないかもな～と思っていたら、2時間半ほどでA4用紙に6ページ分書いたメモの1.5ページ分しか終わらなかった。これだけ進みが遅かったのは脇道に逸れまくっていたから。急に競プロの過去問の話を始めてみたり、先生に定理や証明を深堀りされたりした。僕がふ～んとしか思わなかった不等式評価のタイトさについて例を挙げて確認してみたり、やはり着眼点が違うと感じる。

川内の学食で食事し、午後6時半帰宅。50分もある↓の動画を最初から最後までしっかり見てしまった。信じられないくらい面白かった。この回のゲストは、これまでずっとナレーションを担当されていた方らしく、最終回にしてついにゲストになったようだ。そういう展開からしか摂れない栄養素は確実にあるだろう。最終回だけ見てる奴が何言ってるんだという感じだが。

www.youtube.com

49分55秒。手の形を見るに花束を持っているようだ。こういうところまで見て取れるトラッキング技術はやはり凄い。体の比率と3Dモデルの比率が微妙に合っていないのかモノを食べるときに手が口元からずれてしまっているが、それ以外は特に違和感なく体が動いている。各人が何をしているのか細かくわかるのも、ついつい動画に引き込まれてしまう理由の一つだと感じた。

https://youtu.be/CGksvc8lwm8?t=2995

午後8時半からインターン関連のコーディングを開始。明日何やらペアプログラミングをするようなので、それまでにひとまずのコードを書いて、機械学習の実験を回しておきたい。半年以上前に書いていたコードを見て記憶を蘇らせるのとググってサンプルコードを拾ってくるのを繰り返し、何とか動くコードが書けた。

適当に学習を回し始めた後、勢いづいたままこれまで書いていたコードの修正と追加実装を行った。ある2つの列を順序バラバラで最もらしくマッチングさせる必要がある。つまりは最大重み二部マッチングで、フローなら多項式時間で解けるのだが、さすがに実装が面倒だったのでとりあえずbitDPを書いておいた。列が長すぎる場合は即座に異常な値を返すようにしてあるので、とりあえず落ちることはない。実際にそのようなケースが発生してから書き直すことにしたい。結局自分の作った機能のテストなので、変な挙動をしても今のところ自分にしか影響がない。

午前4時までコーディングしていた。Excelの謎の挙動に悩まされて大変苦しかった。このように自分がただただ苦しんでいる時間も業務上必要だったと思っているので、作業の記録に含め、時給を発生させた。進捗ではなく自分の支払った労力をカウントしている。

またしばらくYouTube。レバガチャダイパンが面白かったので、アーカイブから少し見ていた。FFの友人が結構前から戌亥とこさんにハマっていたこともあり、↓の回を選択。これまで歌動画しか見たことがなくて、かっこいい声をしている方という認識だったが、普段の声の落ち着きと可愛らしさが同居している感じがかなり好みだと分かった。しぐれういさんの声はひたすらに可愛らしく、星街すいせいさんの声はハリのある強さを感じて、それぞれ普通ではない点で良さがあると思っているところ、戌亥とこさんの声はその普通さが良いとも言える。

www.youtube.com

午前7時から午前8時半まで日記を書いていた。布団に入って動画を見たりカクヨムを読んだりし、午前9時半就寝。

06/03(金)

今日のペアプログラミングは夕方からということしか決まっていなかったので、午後3時から1時間ごとに目覚ましをかけていた。すると、午後6時ちょっと過ぎの連絡に午後7時になってようやく気付くという事態に。申し訳なくなりながら起床し、食事して午後7時半から開始。

昨日回してから寝た機械学習の実験が終わっていたので、結果を報告。その後しばらく話していて、自分がoptimizerとschedulerを混同しており、片方しか設定しなかったせいでLearning Rateを一切変えないままずっと学習してしまったことに気づいた。一瞬で過学習したのも当たり前だったか。それの修正と今後の実験の方向性を確認しつつ、ライブラリの実装を読んだりしていた。通話は2時間ほどで終え、その後午後10時までコーディングを続けていた。学習を回し始めて完了。久しぶりにバリバリインターンの進捗を出せている感じがして気が軽い。

YouTubeの動画をいろいろ漁って時間を過ごし、午後11時半からCF #796 div.1に出た。

https://codeforces.com/contest/1687

Aから難しかった。最初、始点を自由に決められないと勘違いしていて、最初に右に行くか左に行くかなど考えていた。その後始点が自由であることに気づいてからも思考が固定されて、どこからどこまで往復するか全探索する方針の正当性を示そうとしていた。問題文に書いてあることをそのまま実装するとどうにも場合分けなど大変そうだったので、何か簡単な方法がないか考え、ようやく各座標を最後に通った位置だけが問題になると気づいた。直ちに $\min(n,k)$ 個の座標を一直線に移動する場合だけ考えればよいことがわかり、実装してAC。

Bは冷静になると簡単。まず $m$ 回のクエリで各辺の重みを求める。次に辺を重みでソートして、順に最小全域森に使うかどうか決める。それまでの最小全域森が分かっていれば、そこに辺を追加してみて、重みの増分が追加した辺の重みと一緒である場合だけ使用するという方法で次の最小全域森が求まる。「最大」の全域「森」というほとんど見ない概念に惑わされ、辺を並べ替えることをなかなか思いつけなかったのが反省。実装して提出したら400 Bad Request。すぐにm1のほうのサイトを開いて提出しなおしたところ、以前の提出もちゃんと処理されていたようでリサブ扱いになってしまった。最悪。

Cは難しい。 $a-b$ の累積和を $S$ とすると、区間 $[l,r]$ は $S_{l-1}=S_r$ である場合のみ使用可能となる。さて、計算量的に左端からdpっぽいことをしたい気持ちになるが、区間のオーバーラップだったり操作の順序が顕著に関係してくるのが非常に辛い。ひとまず最も左端で使う区間が $[l,r]$ だった場合を考えてみると、 $S_{l-1}=0$ は最初から成り立っていなければならず、あとはそれまでの操作によって $S_r=0$ になっている必要がある。そしてこのとき、 $l\le i\lt r$ に対して $S_i\leftarrow 0$ となるようだ。

ここで、 $S_{l-1}=S_r=0$ であるような区間しか使えないと勘違いした。この条件を満たすような区間を使うと、それに含まれる位置の $S$ が $0$ にセットされて使える区間が増え、最終的に $S$ の全要素を $0$ にできればYESと判定できる。結果的に正しかったが初期化ミスで1WAして本当に辛い。勘違いを修正する場合は、区間 $[l,r]$ を使うことが $l\le i\lt r$ に対して $S_i\leftarrow S_{l-1}=S_r$ とする操作であると捉えると、 $S$ に $0$ 以外の要素を増やす利点がないことから結局 $S_{l-1}=S_r=0$ であるような区間しか使わなくてよいことが言える。

Dも難しい。cuteな数は、実験するとある正整数 $y$ について $[y^2,(y+1)^2-y)$ の区間に入るとわかる。cuteな数の区間とそうでない数の区間は当然ながら交互に現れるが、その長さは先頭から順に $2,1,3,2,4,3,\dots$ とそれぞれで単調増加になっているようだ。ここから、 $a_1$ が属する区間を決めるとほかの数が属し得る区間が一意に定まる。つまり、 $a_1$ の条件から得られる $k$ の候補が、それ以降でcuteでない数の区間を跨げるほど幅広くないということ。

計算の際は、逆にcuteな数の区間それぞれに対しそこに属する数を集めてみる。区間 $[l,r)$ と現在の $k$ があったとき、 $a_i+k\ge r$ となるような $i$ の最小値は前計算しておけば $O(1)$ で見つけられる。 $r-(a_{i-1}+k)-1$ がその区間だけ見たとき追加で $k$ に足せる数となって、それのこれまでの最小値を求めておく。次の区間 $[l',r')$ について $a_i+k\lt l'$ となってしまうと困るので、先ほど計算した値の範囲内で $k$ を適切に増やすことで $a_i+k\ge l'$ とできるかチェックする。出現する区間の長さは $a_1$ が属すると決め打った区間以上であるため、その長さが $L$ のとき、探索する区間が $2\times 10^6/L$ 個くらいになるとわかる。よって特に工夫せず調和級数になる。

残り4分で提出。しかし通らない。焦りつついろいろ書き換え、3WAしたあたりでコンテスト終了。システス後にテストケースを見ると、 $a_1$ が属する区間の候補をちゃんと検出できていなかったことが分かった。区間 $[l,r)$ に対して $a_1\lt r$ ならば候補とすべきところ、 $a_1\le l$ という条件にしていた。最初の提出からこれだけを修正したら通ってしまい、非常に悔しい思いをした。

コンテストの結果は3完70位で2953→2906(-47)。Bのリサブ扱いとCが解けなかったのでコンテスト中かなり絶望していたが、何とか2900は残して重傷に留めた。

しばらくYouTubeを見た後、午前4時から日記を書き始めた。木曜日の途中から書き始めたのに、今ここを書いている時点で午前11時。なぜこんなに集中できなかったのか。途中かなりの時間を、YouTubeを見たりハーメルンを読んだりするのに使っていたらしい。やるべきこともやりたいことも他に無限にあるはずなのに……。

見ていた動画をまた一つ貼っておく。「トンデモワンダーズ」で検索したら以下の動画が出てきた。これも木曜日に聞いていたのと同じくライブの切り抜きらしい。しかしダンスも歌も圧倒的。ホロライブとにじさんじの何が違うのかよくわかっていなかったが、ホロライブのほうはアイドルらしくダンスレッスンなど受けているということをコメント欄で知った。

「しかし」という言葉を使ったものの、別にどちらが動画として優れているという話ではない。木曜日に聞いていたのもまだ延々ループ再生を続けていて、これは社築さんと笹木咲さんの二人が歌って踊っていることに「良さ」があるんだよな。なるほど、これが関係性のオタクというやつか……。

www.youtube.com

日記を書き上げるともう正午近く。布団に入ってからしばらくカクヨムを読んで、午後1時就寝。

06/04(土)

午後4時前に生協の冷凍弁当を受け取った。正直起きられたのは奇跡だったと思う。眠りの淵でドアチャイムの音を聞き、しばらく何の音か考えていた時間があったように思う。

その後即座に二度寝し、次、午後7時前に悪夢で飛び起きた。人を殺してしまったという夢。犯行の瞬間ではなく、その後数年単位で時間をおいてから、幸せな日常の中でふと自分が人を殺したことを思い返し、捕まったら今の暮らしが全部崩壊してしまうのだと実感して震え上がるという夢だった。夢で本当に良かった。また三度寝。

午後8時にようやく起床。食事して午後9時からABC254。

AtCoder Beginner Contest 254 - AtCoder

Aは問題名から容易に内容の想像がつく。Vimで後ろ2文字を削除する方法を考えながら開くと、入力が3桁固定だった。つまり先頭1文字を削除すればよい。削除に1B、Vimの終了に2Bの合計3Bで書ける。16秒時点で提出したものの、最速は9秒で大敗。やはり問題ページを先に開いておく必要がありそう。Bはcombinationのテーブルを作る問題だが、念のためRubyやRakuの関数を持ち出さずにC++で問題文の式を書いた。Cは $K$ 個おきに要素を取り出してソートし、全体をソートできているかチェック。

Dは数をsquare-freeになるまで割ったあと重複を数え、それぞれ2乗する。square-freeにする部分は $i=2\dots\sqrt N$ に対し $i^2$ の倍数をループで列挙する方針。見るからに速そう。もうちょっと正確に評価すると、バーゼル問題より倍数を列挙するところまでは線形になっていて、実際に割っている部分がどうなるのかは謎。Eは次数も $k$ も小さいので愚直に。Fは隣接項の差の区間 $\gcd$ を見るやつで、ただし $A_{h_1}+B_{w_1}$ とも $\gcd$ を取らなければならないのに気付かず1WA。差が全部 $0$ になる場合だけ $A_{h_1}+B_{w_1}$ を出力して満足していた。

Gは実装がヤバい。まずビルごとに区間が重なるエレベーターをマージしておく。ビルからビルへの移動がかなり自由であること、エレベーターが区間であることを考えると、わざわざ目的階から遠ざかるような移動をする必要はない。そして、前処理の時点で同じビルにいる間できるだけ $Y$ を $W$ に、 $W$ を $Y$ に近づけておくと、あとはどのビルからどのビルに移動したという情報を忘れてよくなる。すべてのエレベーターを使えると見なし、 $Y$ 階からスタートして $W$ 階より上（あるいは $Y\gt W$ なら下）まで移動できた瞬間の、使ったエレベーターの数に $1$ を足したものがビル間を移動した回数になる。

以下 $Y\lt W$ とする。最初、 $Y$ 階に対応するクエリを表す人がいるとして、下の階から順に見ていく。今 $i$ 階を見ているとしよう。まず、 $i$ 階がゴールであるようなクエリに対し、そのクエリを表す人が今どの階にいるかチェックする。ちゃんと $i$ 階より上にいれば、その人が使ったエレベーターの数を記録する。次に、 $i$ 階にいる人をエレベーターに乗せて上に運ぶ。この時選ぶエレベーターは、 $i$ 階から乗れるものであって最も上まで繋がっているものと決め打ってよい。そして、移動先にいる人と $i$ 階にいる人の集合をマージする。このとき、 $i$ 階にいる人たちの使ったエレベーターの数にそれぞれ $1$ 加えておく。

集合のマージ部分をマージテクで行いたい。集合に属するすべての値について同時にカウントを増やすのは、代わりに全体に足されている値を持っておけば可能。残る問題は、クエリ番号からそれを表す人がどの階にいるのか取得すること。どの階にいるかではなくどの集合に属しているかを持っておけばマージはできる。ただしこの際、集合を単純に階の番号をインデックスにした配列で持ちながらうっかりswapしたりすると、クエリと集合の紐づけが外れてしまう。よって、集合を持つ配列は別に用意しておき、クエリ番号からも階の番号からもその配列を参照するという実装になった。ポインタでも良かったが慣れないので配列の添え字で押し通した。階の番号は集合に紐づけておけばよい。

実装が嫌すぎる。いったん順位表を見るとExのほうが解かれていてひっくり返った。まだ時間は結構あるのでじっくり実装し、何とか完成したものを提出。しかしWA。もう完全に嫌になってExを見に行ったがよくわからなかったので戻ってきて、デバッグを始めた。単純なケースで考察ミス、例えばエレベーターをマージする前に前計算してしまった値があったり、ビル間の移動回数を数え間違いしたりしたのが見つかって、さらにクエリと集合の紐づけを修正した4回目の提出が通ってくれた。地獄のような考察も、幸い大きな破綻なく実装しきることができていたらしく、軽微な修正で通ってくれて良かった。

もう一度Exを見る。大きな数から決めたい気持ちになる。実際、最大の数が一致しているならそれらをペアにすることで全く損しないことが言える。一致していない場合、大きな方を減らすことになる。それが $A$ 由来だったなら単に $2$ で割って切り捨てればよい。 $B$ 由来だった場合、これを $2$ で割ることは $A$ の要素を $2$ 倍することに対応しているので、奇数なら即座に $-1$ を出力する。……もう解けているのではないか？優先度付きキューで適当に実装して投げたら通った。Gを通してからたった3分後であった。

全完7位。Gはダブリングらしい。完全に頭から抜け落ちていた。

直後、午後11時からGCJ2022 R3に出た。

https://codingcompetitions.withgoogle.com/codejam/round/00000000008779b4

Aはfunctional graphのループごとに塗り分けるとしてよさそうで、直感的にはループ上で隣接するものをさらに2個ずつ分けるのが嬉しいと思った。実装してローカルでテストすると、2ケース目から通らない。ここから解法ガチャを始め、いくつか全然ダメな解法を生み出した後3個ずつ分けるという方針を試したら全ケースに通った。そのまま提出してAC。正当性は謎。

Bは簡単。選ぶ区間の始点を固定して終点を数えたい。色ごとに選べる終点が高々2つの区間として表せ、全部の区間が重なっている位置の個数を数えられれば良い。後から始点をずらすことを考えれば、遅延セグメント木の区間加算で選べる終点に $1$ 加え、最終的に値が $C$ になった位置を数える方針が立つ。区間加算を行いつつ値が $C$ になった位置を数えるのは難しいが、これを「区間内の最大値の個数」と捉えると遅延セグメント木に乗る。典型。ちゃんと最大値が $C$ であることをチェックしつつ答えに加え、始点をずらす際はその位置に塗られた色の条件だけ修正すればよい。 $A_i=0$ のケースでREを吐くも2回目の提出で通った。

Cはつい先週グラフ彩色の集中講義を受けた経験がダイレクトに表れた。まず、条件は高々 $(2+4)N$ 個の「部屋 $u$ と部屋 $v$ は異なる文字でなければならない」という関係で表せる。このグラフを13彩色せよという問題になる。さて、今辺は $6N$ 本（以下）あるので、頂点の次数の和は $12N$ になる。これを $N$ 個の頂点で分け合っているので、グラフ全体の平均次数は $12$ 。平均次数は当然最小次数以上なので、つまりグラフには次数 $12$ 以下の頂点が必ず存在する。そのような頂点一つとそれに接続する辺を削除したとき、残ったグラフについて、辺は高々 $6(N-1)$ 本になっている。よって $N\leftarrow N-1$ として最初の状態に戻ったとみなせる。このように頂点を減らしていき、グラフが空に（あるいは頂点数が $13$ 個以下に）なってから逆順に戻すと、戻す頂点は常に次数が $12$ 以下なので、他の頂点の色に依らずに必ず $13$ 色のうちどれかを塗ることができる。

この平均次数を用いる議論は、閉曲面に埋め込まれたグラフの彩色数を求める問題で嫌というほど触れた。オイラーの公式を使うことで、例えば平面的グラフなら $E\le 3V-6$ が言えるので、上の議論と同様にして次数 $6$ 未満、つまり $5$ 以下の頂点が必ず存在するとわかる。したがって即座に平面的グラフが6彩色可能であることが言える。平面的グラフはさらに4彩色可能であることが知られているが、もっと種数の大きな曲面では、このような平均次数に関する評価だけで最良の彩色数を導けているということが示されたらしい。

ただし実装が下手くそ。いたるところにsetを使いまくるような実装でとりあえず提出したが、その後ランダムケースを試すと手元で50secかかっていることに気づいた。慌てて全体をvectorや優先度付きキューで書き直すと同じケースで6sec強になり、リサブした。

Dは何を考えればよいかすら全く分からず、残り1時間弱はABCのコードゴルフをしてしまった。結果はABCで30位。思ったよりdを通した人が多かった。Cで最初から高速なコードを提出できていれば、ペナ差でfinalに進めるくらいの位置だったようだ。恐る恐るリサブ前のコードを再度提出してみるとちゃんとTLEしてくれたので、決して無駄なリサブではなかった、というのは救い。僕は残りのグラフから次数最小の頂点を削除することに固執してしまったが、次数 $12$ 以下であればよいので、普通にBFSっぽく書けるらしい。

ABCのコードゴルフ。AはFAの方もちゃんと3Bで提出しており、案の定負け。Bは配列をずらして和を取るようなコードをRakuで書いた。Cは元の列とソート済みの列でインデックス $\bmod K$ ごとの値の（多重）集合が等しいか見たい。入る集合に応じて適当に係数を掛け、和を取って一致するか確かめる方針が短そう。単純にインデックス $\bmod K$ を掛けたら通った。飛んでExはheapq、Python3がTLEしたのでPyPy3。

Dは $1\le i,j\le\sqrt N$ かつ $\gcd(i,j)=1$ なものに対し $N/\max(i,j)^2$ の和を取るという方針が提出されており、美しく短かった。Octaveで書き直して最短に。しかしこれはどういう仕組みで数え上げているのだろう。見た瞬間納得した記憶があったものの、どうにも考え違いしていただけのようで、それほど簡単な話ではない。ちょっと詳しく見てみよう。

おそらく、組 $(i,j)$ をsquare-freeな数 $k$ と $x,y$ によって $(kx^2,ky^2)$ と表した時の $x,y$ について全探索しているのだろう。ただし、上の解法では $k$ がsquare-freeであると限定されておらず、一方こちらは $\gcd(x,y)=1$ である必要がない。ここがうまく対応づいていることを示そう。つまり、square-freeな $k$ による $(kx^2,ky^2)$ と、 $\gcd(x,y)=1$ なる $x,y$ による $(kx^2,ky^2)$ の間に一対一対応が存在することを見る。実は具体的に構成できて、前者の $(k,x,y)$ があったとき、 $g=\gcd(x,y)$ として $(kg^2,x/g,y/g)$ が後者の対応物になっている。逆に後者における $k$ をsquare-freeにした分を $x,y$ に押し付けると前者の組が得られて、これらは互いに逆写像の関係になっているので、よい。

別の問題のコードゴルフ。数の区間が与えられるので、それぞれ素因数分解して含まれる素数の（重複を含めた）個数が素数になっているものを数える問題。factorで素因数分解してawkで出力を整えるのを2回繰り返していたので、evalとブレース展開を使いまとめた。このテクニックは何度か挑戦した記憶があるものの実際の最短コードにはなかなかならなかったので、こうして上手くいったのがうれしい。

atcoder.jp

レバガチャダイパンのこの回が面白いとおすすめされたので視聴した。序盤のバルーンファイトですでに面白かったので満足していたら、リズム天国が始まってからが本番だった。26分14秒のところで社築さんが椅子から崩れ落ちて座面を叩きながら笑っていたのが非常に面白かった。しかしリズム天国は難しそう。夜見れなさんのプレイの何が悪いのか、動画を見ているだけではよくわからなかった。自分の耳だけでリズムを取らなければならない点はノーツがある音ゲーと明確に異なる。音ゲーゴリラの社築さんもあまりスコアが出ていなかった。

www.youtube.com

https://youtu.be/rJNcd0c0JMk?t=1574

朝までカクヨムを読んでから日記を書き始めた。土日はコンテストが盛りだくさんなので、土曜日と日曜日の間にしっかり書き進めておかないとまた月曜日の昼までかかって日記を書く羽目になる。午前10時に書き終えて布団に入り、少しYouTubeを見て午前10時半就寝。

06/05(日)

午後3時半に親からの仕送りが届いて起床。なかなかスッキリした寝起きだったのでそのまま起きていることにした。しばらくTLを眺めて時間を潰し、午後5時からOpenCup。

今日はGrand Prix of Urals。チームとしてはEDMJALBGFCKをこの順に解いて11完12位。今回のセットは簡単な問題が多かったらしく、チーム共有ドキュメントに何も書かれず即座に倒された問題もいくつかあった。僕はAとFを解いた。

Aはマス目を連結になるように塗って、面積を周長で割った値が $p/q$ と一致するようなものを構築せよという問題。実験して解いた。まずブロックが $p$ 個以上必要で、このとき周長は最大で $2p+2$ になる。面積を増やしても $p/(2p+2)$ より比率を小さくすることはできないので、これより $p/q$ が小さければ構築不可能。それ以外のケースは全部 $h\times w$ のように配置するだけで作れるのではないかと思い、PCが空いた隙を見計らって試してみた。すると比率が小さいところでかなり抜けがある。そこで $1\times w'$ のように伸ばすブロックを接続してみると、なんと全通り作れるようになった。

F。これから $n$ 日に渡って毎日一人ずつ人を働かせる。候補は $m$ 人いて、人 $i$ を $j$ 日目に働かせるときのコストが $c_{i,j}$ となっている。また、人 $i$ は連続して $a_i$ 日しか働けない。この制約のもと、かかるコストの最小値とそれを達成するような雇い方を求めよという問題。dpで解く。 $dp_{i,j}$ を「 $i$ 日目まで終え、次の日人 $j$ を働かせられない状態」の最小コストと定義する。 $i+1$ 日目に働かせる人を人 $k$ と決め打った時、それから人 $k$ を連続で働かせる日数を $1\le d\le a_k$ として $dp_{i+d,k}\leftarrow\min_{j\ne k}dp_{i,j}+\sum_{l=i+1}^{i+d}c_{k,l}$ と遷移する。

まず、値の取得は行の左右から累積 $\min$ を求めておけばよい。値の更新について、コストは累積和の形で書けるので、列ごとにみるとスライド最小値が使える。結局どちらも線形で行えるし、逆に制約が $n,m\le 1500$ なので線形で行わないと間に合わないという問題だった。復元は気合い。

他にも読んだ問題がいくつかある。Bは貪欲で通ったらしい。こういう問題は貪欲が落ちがちという意識が先行して、それで通るという嗅覚が一切働かなかった。すごい。Cは特定の数だけ取り出してそれの遷移を見ると状態数がめちゃくちゃ少ない。これは気づいてもよかった。Gは全頂点の次数が $3$ のグラフに関する問題で、何らかのグラフ理論的な背景があるのかと考えていたが、純粋に競プロ的テクニックだけで解けたようだ。Lはある関数の最大値を求める問題ではなく、値が適当な閾値を超えられるか判定せよと言われているので、その閾値を使って式変形していた。

前半で僕の貢献は終わりで、後半はIが実は愚直で通らないかなど無謀な実験をしていただけだった。

とりあえずここまでの日記を書いて、午後11時半からCodeChef。June Cook-Off 2022 div.1。

https://www.codechef.com/COOK142A

SIMPLE_XORは典型。 $(2n,2n+1)$ のXORが $1$ なので、2つ束ねて $0$ にする。

SPLITANDSUMは下のbitから見て、そこが立っている要素を数える。一つ以下ならその桁はより上に一切影響しないので無視してよい。二つ以上あった場合、和においてそのbitが立っているような連続部分列に分割できる。具体的には、偶数個だったら $1$ 個とそれ以外、奇数個だったら特に $3$ 個以上なので、 $1$ 個と $1$ 個とそれ以外。しかしWA。何度考え直してもどこが間違っているのか全然わからず、ランダムケースでもちっとも落ちないので、とりあえず出力する区間が条件を満たすかチェックするassertを入れ、また配列サイズを念のため倍にして提出した。するとAC。

これは制約違反か？と思って運営にclarを出そうとして、ページをいろいろ探しているうちに、自分の最初の提出がいつの間にかACに変わっていたことに気づいた。特に通知もなくリジャッジが行われていたらしい。20分くらい時間を無駄にしてしまい、本当にキレていた。実はトップページにアナウンスが書き足されていたようで、そこを読むとチェッカーが間違っていたのが原因と分かる。いやこんなところ見ないって。

THROWTAKEはよくわからない。そもそも前の問題に信じられないくらい時間を使ったのを引きずっており、焦ってまともに考察できていなかった。偶奇を保ったまま $C$ を $3$ 以下にしても答えは変わらないと信じ、メモ化再帰したら通った。後から試したら $1$ 以下にしてもよかったようだ。

PRFSUFDSTNCTは頑張って必要条件を探す。まず $P$ も $S$ も隣接項の差に制限がある。また $P_N=S_1$ である必要がある。以上が満たされていれば、 $A$ に出現する $P_N$ 種類の数について、それらが出現する最も左の位置の集合と最も右の位置の集合が手に入る。これらをうまくマッチングさせる問題になりそう。とりあえず、集合の共通部分はそこに唯一出現する要素が入ることで確定する。残りはソートして先頭からマッチングさせていくのが最適で、区間の左右の大小関係が正しいことを確かめておく。

実はまだ足りない。 $P=\{1,1,1,2,2\}$ 、 $S=\{2,2,1,1,1\}$ の場合を考えると、マッチングまではうまくいくものの、真ん中に入れられる要素が存在しないことがわかる。つまり、上のマッチングで得られた区間に含まれないような位置があってはいけない。そういう位置は、左右でそれぞれマッチングが完結してしまっているので、今からペアを入れ替えたところでどうにもならない。よってチェックだけ行えばよく、いもす法で実装した。

一時50位台に落ちて絶望していたものの、ここまで解いた時点で10位台に戻ってきたのでまあ助かったかなという気持ちになって少し落ち着いた。

PERMSEGMENTSは難しい。挿入dpっぽいことをしたくなるが、隣り合うという関係が重要なので、（連続）部分列を作ってマージしていくという方針にした。小さい値から順に挿入していき、今持っている部分列はその直後に必ず一個以上、より大きな数を入れると定めておく。こうすることで値の挿入時に持っている部分列の個数がそのままその位置を含むような区間の個数となるため、条件のチェックができる。ただし、末尾に来る要素の取り扱いに注意。これのせいで区間の重なりのチェックが壊れるとまずい。よって、そのような部分列が存在するということを示すフラグをdpの次元に追加する実装になった。

値を挿入する際の方法は、前後に今ある部分列を入れるか入れないかで $2\times 2$ 通りあるので、それぞれ遷移を書き下した。この辺りは気合いでガチャガチャするしかない。前に部分列を入れて後ろに部分列を入れない遷移の際は、今挿入した値だけそこを含む区間が一つ増えてしまうことに注意。例えば $2$ の前に $[1]$ を繋げて、次に直後に $3$ を入れると、 $2$ を含む区間が二個になっている。末尾に持ってくる部分列のチェックは、重なった区間の個数が条件を満たさなくなった瞬間に持っている部分列のどれか一つを末尾に固定して何とか回避するような実装をしたが、今整理して考えてみれば値を挿入するごとに末尾にするかどうか決めるほうがわかりやすい。コンテスト中の実装で重複が省けているのは結構非自明に見える。

MAXMINUSMINは実験。適当に回してみるとそのうち同じ値が2連続で出てきそうだったので、 $A=B\gg C$ の場合にどういう遷移をするか手計算して、8ステップで似た形に戻ってきたのでそこをスキップする実装を行った。これでランダムケースに十分高速に答えられていたので、提出。しかしTLE。ここで、 $0\dots 10^{18}$ から一様に取って $A,B,C$ としていたランダムケースを、それぞれ $10^6$ 以下、 $10^{12}$ 以下、 $10^{18}$ 以下と決めるようにしたら、ちゃんとめちゃくちゃ遅いケースが見つかった。 $A,B\gg C$ になったあたりで時間がかかっていたので、 $A\ge B\ge A-C\gg C$ の場合を同様に手計算。するとこちらも8ステップで戻ってきて、先ほどのケースを含んでいることに気づいた。これを実装すると新しく作ったケースも高速になったので提出。自信はほとんどなかったが、通った。

6完6位で2708→2761(+53)。highestには1足りない。過去の自分が強すぎる。しかしリジャッジがあったが、このくらいのミスなら平気な顔してratedにするというのはすごいな。

社築さんが初のオリジナル楽曲を投稿されたので、今日はこれを作業用BGMにしていた。かなり良い。サイバー感のある歌声に編集されているのが好き。

www.youtube.com

午前5時前に日記を書き上げてからは、おすすめのなろう小説まとめを作成していた。↓の記事に追記する形でもよかったが、やはり時間の経過とともに過去の作品に対する印象が薄れてきて、今はそれほど心惹かれない作品も多く載っている。よって新しく記事を立てることにした。ただしここ1年で読んだ作品だけでなく、古い記事からもいくつか特におすすめしたいものを抜き出して載せる。わかりにくくなるとしてもオールタイム・ベストという体裁は保っておきたい。新しく増えたものだけ知りたい場合は各自で集合の引き算を行ってほしい。

進捗は、載せる作品の選定を終えて、各作品にコメントをつけている途中。それぞれ一言、自分が好きなところを書き留めている。参考にと読み始めて止まらなくなったりして、思うように進まなかった。

kotatsugame.hatenablog.com

午前9時を回ったので寝ることにする。

kotatsugameの日記

週記（2022/05/30-2022/06/05）

05/30(月)

05/31(火)

06/01(水)

06/02(木)

06/03(金)

06/04(土)

06/05(日)