05/09(月)

午後2時前に起床。1時間ほど布団でゴロゴロした後、シャワーを浴びて購買に向かった。この時間帯、すでに購買のパンやおにぎりは売り切れている。仕方なくお菓子とカロリーメイトを買って、帰り道でコンビニに寄り昼食を確保した。

先週金曜日の配信アーカイブを改めて確認していると、チャットリプレイができないことに気づいた。設定を弄った記憶はなかったが、調べてみるとカット編集を行ったアーカイブはそれができないようになってしまうらしい。配信画面にコメントを表示するのはこれの対策という意味もあったのだと知った。昔は設定していたものの、いろいろソフトの連携が必要で面倒になり、最近は止めてしまっていた。

午後4時半からインターン先の定例会。GWを挟んで2週間分の進捗を報告する。といっても先週は帰省先でのんびりしていたので、なんとさらに一週前の火曜日にコーディングしたのが最後の進捗であった。ここまで間が開いてしまうと、考えておいた改善点や実装案も全部頭からすっぽ抜けてしまってかなり効率が悪い。たまにドカッとやるよりは、毎日少しずつでも進めたほうが良さそうだとだんだんわかってきた。最近は1on1の頻度も低い。1on1駆動開発を再開するべきなのかもしれない。

勉強会はgitの操作について。Online Judge Verification Helperを導入していると、ファイル編集を行った後はいつも自動でverifyが行われるのだが、このときタイムスタンプが記録されるようになっている。そのせいで、ローカルの変更を続けざまにpushした場合、間でタイムスタンプが更新されているとローカルが最新でないと言われて怒られてしまう。そのあと何とかして直してもcommit履歴によくわからないものが入ってしまって気に入らないなあと思っていた。同様に怒られる事例が紹介されていたので、謎のcommitを出さない方法を質問したところ、pull時のマージ戦略を適切に設定すればよいと言われた。細かくは理解できていないが、そういう方法があると知れてよかった。調べるとよくある話らしい。

Merge branch 'master' of github.com:kotatsugame/library · kotatsugame/library@f2689ee · GitHub

Merge branch....みたいなコミットログをなくす - by shigemk2

終了後、先週の日記を書き上げた。YouTubeに目を奪われつつ読み返して校閲し、午後10時を回って何とか投稿した。

ABC250Exを通した。ブルーフカ法という話を聞いていたので、考える方針だけは与えられた状態だった。各家から多始点dijkstraをして、別の家にたどり着いたらその間の距離をMSTの辺にする、ということをしたい。しかし実際に実装してみると、ある家から別の家に向かうパス上では当然逆方向からも近づいてくるので、真ん中でぶつかってしまっていた。そこで、ぶつかった瞬間にパスの距離を計算することにした。各頂点について、そこに最も近い家 $u$ とその距離 $d_u$ を記録し、別の家 $v$ からスタートしたパスが距離 $d_v\ge d_u$ でそこにたどり着いたとき、距離 $d_u+d_v$ の $uv$ パスをMSTの候補にする。これはうまくいった。別の家 $w$ と $d_w$ があって $vw$ パスを考えたいとき、 $d_v+d_w\ge d_u+d_v,d_u+d_w$ であるから、いったん $u$ を経由しても損しない。公式解説の別解と近いかと思ったが、それよりユーザ解説にリンクがある記事と全く同じだった。

Submission #31574240 - AtCoder Beginner Contest 250

tokoharuland.hateblo.jp

午前2時までかけて課題を2つ倒した。その後ラノベを読み、午前5時に寝た。

05/10(火)

午後2時起床。しばらくYouTubeやハーメルンで時間を溶かし、午後4時くらいになってようやく布団から出た。

さくらインターネットからメールが来ていた。atgolferのサーバが攻撃の踏み台にされているらしい。

Trafficに覚えがなさ過ぎて顔面蒼白 pic.twitter.com/vj7X7IHGh5
— こたつがめ (@kotatsugame_t) 2022年5月10日

さくらインターネットからメールが来てログ添付されてて、読んだ限りログイン失敗してるから……ええかｗｗｗとか思ってたんだけど、それは僕のサーバーを踏み台にした攻撃を受けたところのログで、僕のサーバーはもうNTRされてたってワケ
— こたつがめ (@kotatsugame_t) 2022年5月10日

特に重要なデータを置いているわけではないので、サーバの中身はもう何も触らずOSを再インストールした。そこから改めてPythonの環境を整え、atgolferを実行できるように。何もかも初期化された後の最初の実行は、現存するすべての最短コードが新たに打ち立てられた扱いとなるため、ツイートしない設定で行う必要がある。--verboseオプションをつけて進捗をしばらく見守っていたのだが、かなり時間がかかるようだった。一度キャッシュが保存されればいくらか高速になるのだろう。

chokudaiさんにリプライを送ってみたところ、今日あーだこーだーが行われること、そこにゲストとして呼んでいただけることが確定した。いよいよである。

午後8時を過ぎたあたりでchokudaiさんがあーだこーだーの予定を忘れていたことが発覚し、今日は配信しないことになった。来週はGW中で自分が帰省しているので、また再来週以降となる。
週記（2022/04/25-2022/05/01） - kotatsugameの日記

学食で夕食を摂り、しばらくラノベを読んで、午後8時から配信の視聴を開始。30分前には入っていてと渡されたZoomリンクを待ちきれず踏むと、僕の準備ができていることをchokudaiさんも認識したらしく、今日のお知らせが少なかったこともあって少し早めに登場することになった。

www.youtube.com

そこからはずっとマシュマロやチャットに寄せられた質問に答えていた。答えたい質問を拾ってと言われても全部答えたくなってしまう。自分に興味を持ってもらえるのは嬉しくて、さらに自分のことについて話すのが好きなこともあって、実に80分も喋っていたらしい。いくらchokudaiさんに許しを得られたとはいえ、普通一時間のあーだこーだーを40分も延長してしまったのは少し反省。ただ喋っている間は本当に楽しかった。同時接続数も安定して200人を超えていて、ありがたい限り。

配信を終え、chokudaiさんに出演料としてアマギフを頂いて、解散。エゴサーチをしながらしばらく余韻に浸っていた。

声が好きだというツイートをいくつも目にしてかなり嬉しかった。以前から配信する度たまにそういう感想を見つけていたのだが、より多くの人の耳に入り、より多くの人に言及されたという事実を確認して、自尊心が非常に高まった。さらに、発言の間を埋める意味のない言葉が少なくて良いというツイートもあった。配信に乗るからには常に意味のある言葉を喋るよう努力すべきであると考えていて、ある程度達成できていたからこういうことを言っていただけたのかなと思う。これも大変嬉しい。一方で、よく整理できていないうちに話し始めてしまうことも多かったと感じているので、うまいことバランスを取れるようになりたい。

さらにいくつかの出来事を述べる。まず父からLINEが来て、受け答えがしっかりしていると褒めてもらえた。次に、配信で言及したこの「kotatsugameの日記」が、新しく記事を出したわけでもないのに一日のアクセス数400を記録した。最後に、マシュマロの画面を配信に直接映しながら新しい質問を確認したのはちょっと不用心であるとの指摘があった。いやはやその通り。度を過ぎればマシュマロ側で弾かれるとは言え、問題のない質問ばかり来ていたのは単に運がよかっただけに思える。

赤になったときにGoogleフォームで質問を受け付けたのだが、これをもう一度やってほしいと要望があったので、用意した。もう一つ、最近おすすめのなろうを教えてほしいという質問を保留しているので、これも含め近くこのブログでちゃんと回答する。しばらくお待ちいただきたい。

午後11時半からCF #790 div.4があったので参加した。2回こどふぉって45分スタートになっていた。

Dashboard - Codeforces Round #790 (Div. 4) - Codeforces

Cまではよい。Dは交点を決めた後、毎回斜めに和を取っても十分間に合う。Eもよい。Fは誤読して大変だった。 $[l,r]$ が数列の区間を表すと思い込んで実装。幅の最大値ではなくそれを達成する $(l,r)$ を出力しなければならないことに気づいて書き換えるなどした後サンプルを実行すると、値が全然違っていてちょっと固まった。読み直して間違いに気づき、ソートしてランレングス圧縮して解いた。この問題は8分もかけてしまった。Gは頂点番号の大きいほうからループを回せばdfsの必要がない。Hは普通。

コンテスト直後の結果は12位。ただ上のほうに怪しいアカウントがいくつかあって、後から確認したら10位に上がっていた。SSRSさんが言語の壁を物ともせずに優勝しているのはすごすぎる。Fの誤読がなかったとしても全然敵わない。

ラノベを1冊読了。「最凶の魔王に鍛えられた勇者、異世界帰還者たちの学園で無双する」2巻。ヒロインが能天気なのはイライラするが、面白い。主人公と現学園最強がバトルするようだったので楽しみにしていた。主人公の油断具合がちょうど良かった。見くびっているのではなく、情報を集めるために手加減していたという描写。主人公は未だに実力を隠したままなので、人目につかないところで戦っていた。まあ2巻から大々的に公開するわけはないか。巻末の次巻予告を見ると、今よりもっと人前に出るような立ち位置になるらしいので、どんな感じに実力が明かされていくのか非常に楽しみである。そのカタルシスを辛抱強く待ちたい。

しばらくYouTubeを見て、日記を書き、午前4時半就寝。

www.youtube.com

05/11(水)

いつ起きたのか不明。正午あたりにChromeの履歴が残っていて、おそらくそれからYouTubeを見ていたのではないかと思う。二度寝できていなかったはず。

午後2時半くらいに布団から出た。1時間後に健康診断があるので、それに向けて準備する。シャワーを浴びるのすらグダグダしていたので、かなりギリギリの時間に出発することになった。

健康診断は事前の予約制で、10分刻みで定員がしっかり決められていたため、全く待ちもなくスムーズに終了した。身長が記憶より縮んでいて悲しい。実は僕の世代は麻しんワクチンを一回しか接種しておらず、紙に「二回接種していない人は別の医療機関で健康診断してください」と書いてあったのが気になっていたが、ダメもとで聞いてみたら問題なく受けさせてもらえた。助かる。

生協で運よく売れ残っていたおにぎりやパンを買った後、しばらく講義棟を徘徊して、競プロサークルのチラシを探した。

うおおおあった pic.twitter.com/tZ2PGsnu4n
— こたつがめ (@kotatsugame_t) 2022年5月11日

帰ってきて、明日のセミナー発表に向け教科書を読み始めた。DiestelのGraph Theoryという本。結構頻繁に集中を切らしていたので、その時何にかまけていたかを順に記録する。

イラストレーターのrurudoさんもVtuberとして活動されていることを知った。この方の声も良い。

るるどらいおん - YouTube

www.youtube.com

すとらさんのチュウニズム配信を見ていた。15の理論値を狙い始めて、午後9時過ぎ、ついに「Trrricksters!!」の理論値が出た。見ているこちらまで心臓が痛くなってくるので、作業中に流し見できるようなものではなかった。そのしばらく後に「Killing Rhythm」の最後のタップスライドで散った回があったのだが、こちらは結局出ずに終わった。片方出るだけでも時代が変わったのを感じる。

www.youtube.com

ラノベを1冊読了。「英雄と賢者の転生婚」。主人公最強＋学園モノで面白かった。クラスメイトのかませ犬みたいな立ち位置のキャラもそこまで嫌らしくなく、実は立派な人間であったという風に描かれていて気持ちが良い。主人公がなぜ強いのかはまだ全く明らかにされていない。後書きを読む限り考えなしなわけではなく、ただ秘密にされているだけのようだが、特に意味なくハチャメチャに強いとしてもそれはそれで面白いかもしれないなと思った。

教科書を読む作業は思うように進まなかった。YouTubeを見てしまったので当たり前か。GW前、先生に「2章までは終わらせてきたいですね」と大言壮語してしまったが、結局1章も終わっていない。午前6時になって、寝坊のリスクを避けるためいったん寝て明日起きてからまたやることにし、就寝。

05/12(木)

午後0時半起床。

1時間ほど頑張って、とりあえず1章の最後まで目を通すことに成功した。証明も自分の中では納得した気になっている。それが正しいかどうかを確かめていないが、もう時間もないので、破綻していないことを祈るしかない。あとはセミナーの準備として今日話す内容を整理する必要がある。しかし持ち時間1時間で何をどう話せばよいのだろう。適当に先頭から命題を書き出してみるも、どう考えても終わらない量になっている。後半まで突入したら教科書をチラチラ見ながらやらせてもらうか、と諦めて、途中で切り上げてYouTubeを見ていた。なぜYouTubeを見ているのか。

www.youtube.com

家を出て時間通り教室に到着。午後3時からセミナー開始。結論から言うと、今日はもう一人の発表内容が難しくて皆でいろいろ考えていた結果、僕の発表が来週に持ち越しになった。

先々週の予告通り、今週はコンビネータ論理の話。面白そうと言っていたが手を動かすのが楽しいだけであって、命題の証明は大変そうだった。

もう一方の発表は面白かった。面白かったというか次回が面白そうというか。ラムダ計算自体にはあまり触れたことがないが、SKIコンビネータはUnlambdaの経験があるのでそれなりに手を動かしたことがあり、そのパズルみたいな作業が面白かった記憶がある。
週記（2022/04/25-2022/05/01） - kotatsugameの日記

不動点コンビネータの話になった。Unlambdaで再帰関数を実装するのに使った覚えはあるが、今は自力では書けないだろう。まあその仕組みは今日の本題ではない。不動点コンビネータは教科書に載っているもののほかにも大量に（無数に）あり、Wikipediaでも数種類紹介されている。そのうち見た目が面白いものについて、先生にどうなっているか確かめてみよと言われた。

不動点コンビネータ - Wikipedia

L=\abcdefghijklmnopqstuvwxyzr.(r (t h i s i s a f i x e d p o i n t c o m b i n a t o r))とおいて、Y=(L L L L L L L L L L L L L L L L L L L L L L L L L L)とするもの。昔見たときはややこしそうだと思っただけで放置してしまっていた。今日改めて考えてみると、非常に簡単というか、なんだそんなことかとなるような仕組みであることに気づいた。YはLが26個続いた形であり、Lは26個の引数を取る関数であるから、そのうち25個までがLで埋められてY=\r.(r (L L L L L L L L L L L L L L L L L L L L L L L L L L r))=\r.(r (Y r))となる。「this is a fixed point combinator」は文字rが末尾にしか登場しない27文字のものであるということだけが重要だったようだ。当然、変数を束縛する順番を入れ替えればもっと自由にできる。

かなり延びて午後6時半に終了。川内で食事して帰宅。ABC250BがRakuで縮められていた。やっていることはPerlと同じに見える。自分でも書いてみたらさらにいくらか縮んだので、それで取り返した。

火曜日に設置したGoogleフォームにそこそこの数の質問が来ていたので、ちゃんと記事を1本作って回答することにした。午後8時に書き始めて、午前7時まで書いていた。もちろんその間には何度も集中を切らしていたわけであるが。

作業用BGMとして、ずっと花譜というバーチャルシンガーの動画を流していた。もともとVtuberが出したフォニイの歌ってみたをいくつかループ再生していて、オリジナルが実はボカロではない合成音声だということを聞いたので気になって調べ、「可不」のオリジナルである「花譜」にたどり着いたという経路。特徴的な歌い方・掠れたような声にハマった。

www.youtube.com

朝になって眠くなってきたのでいったん切り上げることにした。午前7時半就寝。

05/13(金)

午後1時くらいに目を覚ました。二度寝するつもりで布団に横たわったままYouTubeを見たりハーメルンを読んだりして、午後5時まで起きていた。その後もう少し眠って午後7時にまた起床。さらにハーメルンを読み続けて、午後8時に1作読了した。「転生したら始祖で第一位とかどういうことですか」。勘違いものの宿命か、主人公が内心でナヨナヨしているのがあまり気に入らなかった。

syosetu.org

起き上がって食事。腹が減っていたのでパスタを200g茹でた。こういうことをするといつも多すぎて後悔する羽目になっていたが、今日はスルッと食べられた。

pic.twitter.com/pLncbyWFLn
— こたつがめ (@kotatsugame_t) 2022年5月13日

パスタって200gあんねん
— こたつがめ (@kotatsugame_t) 2022年5月13日

少しコードゴルフしたあと、また質問に回答する記事を書いていた。yukicoderは、僕がテスターした問題が2問出題されているが、今週もサボり。先週金曜日に配信画面に映してしまった問題の一部なので、出題の直前にそういうことをしてしまったということでことさら申し訳なくなった。

yukicoderで1問テスターを行った。詳細は当然書けないが、面白い問題だと思った、くらいは言っていいだろう。
週記（2021/10/25-2021/10/31） - kotatsugameの日記

午後11時半から2時間、ECR128に出た。

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

Aは最大値と最小値を同じにできるかで場合分け。Bは一番上の行にある一番左のロボットを左上に寄せたとき、その下の行で左にはみ出るロボットが存在するか判定。

Cは難しい。さらにコストが2数のMAXではなく和だと誤読して、一度実装までしてしまった。 $c_i$ で $[0,i)$ に存在する'1'の個数を表すとすると、 $i\le j$ に対して $\max(c_{|s|},j-i)-(c_j-c_i)$ がコストとなる。コンテスト中はここから $i$ としては $j-c_{|s|}$ か $0$ だけ考えることにしてもよいとして実装したが、その理由は全くもって正しくなかった。 $j-i\ge c_{|s|}$ のときコストは $(j-c_j)-(i-c_i)$ なのだから、 $-c_i$ ではなく $i-c_i$ のMAXを管理しなければならない。

しかし通った。日記を書いているときに調べてみると、 $j-i=c_{|s|}$ の場合だけチェックすれば正しい答えが得られることが分かった。これはなぜかというと、 $(i,j)$ がそのような条件を満たすとき、 $[i,j)$ の'0'とその外側の'1'の個数が等しくなるからである。そこから $i$ を左右にずらすとどちらかは大きくなるので、コストも大きくなってしまうというわけ。運がよかった。

Dも難しい。まず $a_i=0$ の場所を埋めるときは、高々1つ中途半端になる値を除いてすべて $\pm k$ であるとしても良さそう。最初にその個数を求めておくと、今見ているインデックス、 $+k$ を何個使ったか、中途半端な値を使ったかの3つから現在の位置を計算できる。これでdpすればよいかと思って、左端のMINを達成する方法と右端のMAXを達成する方法をそれぞれ持って実装してみたら、最後のサンプルで落ちてしまった。

考え直して、とりあえず中途半端になる値の位置を決め打ってみることにする。すると残りは $\pm k$ で埋めることになるが、ここで $i$ 番目の移動で最小値を達成する場合を考えると、 $i$ 番目までにできるだけ $-k$ を使って、それ以降は $+k$ を優先的に使うのが最適だと分かった。最初に $+k,\dots,+k,-k,\dots,-k$ と埋めておき、1個ずつずらしていく差分更新を遅延セグメント木で行うことで、 $O(n\log n)$ で全ての場合が計算可能。これで解けた、と思ったがWAが取れず、いったんEに移った。

Eは簡単。2行それぞれ駒が存在するかの4通りを次元に持つdpを左右両方向から行って、合流する地点を全探索すればよい。問題なく通ってDに戻ったところ、 $i$ 番目の移動で最小値ではなく最大値を達成する場合についても考えなければならないことに気づいた。つまり最初の状態が $-k,\dots,-k,+k,\dots,+k$ の場合。書き足してDもAC。残り時間はFを考えて、すべての奇閉路に含まれる辺があればよさそうと思ったが、実装してみても全然検出できずに終わった。遅めの5完で順位は崩壊してしまった。

コンテスト後も記事を書き続け、午前3時半にようやく投稿できた。質問に答えるのは楽しいことではあるが、やはりエネルギーを使う。自分の考えをうまく言語化するのは難しいし、質問を読んで考えたことを全部書くのが良いわけでもない。質問の意図から外れていそうなことは言うか言わないか決める必要があって、もし言うと決めたならせめても論理の流れが自然になるように気を使いたい。とにかく、普段日記を書くよりよほど力を入れて文章を書いたのだった。

kotatsugame.hatenablog.com

そのあとは日記を書いていた。午前7時くらいに切り上げて布団に移動し、ハーメルンの捜索掲示板をいろいろ眺めた後、読み止しにしていた作品を少し読み進め、午前10時前に就寝。

05/14(土)

午後3時起床。しばらく布団でYouTubeを見ていたら、午後4時過ぎに生協の冷凍弁当が配達された。今日は午後6時半からCFがあるので、そのまま起きていることにした。

コンビネータ論理について少し考えていた。Haskellのコードゴルフテクニックにポイントフリースタイルというものがある。abstraction eliminationが、これを機械的に行う方法に見えてきた。しかしさすがにSを多用するわけにはいかない。僕の経験によれば、ポイントフリースタイルは基本的に関数合成演算子.を使って進めていくものだったはずだ。Wikipediaを見ていると、さらにC=\f x y.(f y x)とB=\f g x.(f (g x))を定義する場合もあると見つけた。Cは明らかにflipである。では、Bは(.)ではないだろうか？

まずBの型を考えてみる。 $f:a\rightarrow b$ とすると $g(x):a$ であるから、 $g:c\rightarrow a$ と $x:c$ がわかる。つまりBは $(a\rightarrow b)\rightarrow(c\rightarrow a)\rightarrow c$ である。Hoogleで調べてみると、見事に(.)がヒットした。感動。意味を考えれば当たり前であるが、純粋に形式的に導けたのが嬉しかった。

(a->b)->(c->a)->c->b - Hoogle

しばらく日記を書いて、午後6時半からCF #791 div.2。

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

Aは、まず $n$ が $4$ 以上の偶数である必要がある。後は $n/2$ を $\bmod 2$ と $\bmod 3$ で場合分けすればよい。Bは要素ごとの書き換えタイミングと全体の書き換えタイミングを記録して頑張る。Cは行ごと・列ごとにいくつルークがあるかセグメント木で持っておいて、区間MINでチェックした。setを使う方法をTLで知って、そちらのほうが楽そうだなと思った。Dは二分探索。各頂点についてそこから何回操作できるかをdfsで求める。ループ検出も良しなに。

Eはちょっと大変。回文の中心を決め打ち、長さを伸ばしていくことで、各部分文字列が回文になる場合について「自由に決められる'?'はいくつか」「どの文字が使えなければならないか」を全体 $O(n^2)$ で計算できる。自由に決められる'?'の個数を持っていても扱いづらいので、使える文字の種類数を決め打って場合の数の形に直しておく必要がある。'?'の個数が $O(n)$ 通り、使える文字集合が $2^{17}$ 通りでヤバそうに見えたが、部分文字列を見ているとき同時に計算すると実は $O(n^2)$ 通りであるとわかった。あとは使える文字集合についてゼータ変換。

Fは面白かった。操作は巻き戻すことができるので、何らかの正規形を考えて数え上げる方針を取りたい。操作で作れる数のうち辞書順最小のものを選ぶとよいのではないかと思った。 $n$ 桁から $9$ の位置を決めて、 $8$ の位置を決めて……とすると組み合わせで立式できた気がするが、各数字を使った個数を覚えておく必要があり不可能。桁dpのほうで実現できないか考えてみる。前にある大きな数字とそれより小さい数字を入れ替えられなければよいので、最後に使った数字を持てばよさそう。これを実装するとサンプルは合った。しかし5ケース目でWA。

ランダムケースで試してみると、結構小さいケースでも間違っていることが分かった。 $(u,v)=(0,1),(1,2)$ のケースでWAになることを発見したので、10進法ではなく3進法に制限していろいろ出力してみたところ、 $201$ からより小さい $120$ に変換できるのに別のものとして扱っていることに気づいた。 $0$ と $1$ を入れ替えても小さくならないが、それより先と入れ替える場合も考慮しておく必要があるケース。そこで、最後に使った数字ではなく「今何が来ればより小さいものに変換できるか」の文字集合を持ってdpすることにした。その集合が $U$ の状態で、新たに数字 $d\not\in U$ を追加したとき、 $d$ と交換できる文字集合を $V$ とすると $U\leftarrow\{v\in V\mid v\lt d\}\cup(U\cap V)$ とすればよい。追加した数字と交換した時点で小さくなるか、あるいはそこを乗り越えていけるケース。これで通った。

全完7位。かなり良かった。僕の上に4人も日本人がいてかなり面白かった。

午後9時からABC251に出た。

Panasonic Programming Contest 2022(AtCoder Beginner Contest 251) - AtCoder

AはVim。typoで1WA、 $|S|=1$ のケースで足りておらずもう1WA。最悪。BはRubyで書こうとして、先ほどAでWAを吐きまくったのだから慎重にと思い直してC++で実装したのに、うっかりRubyで提出してしまい1ペナ。言語選択ミス、相当久しぶりにやらかした。Cはset。Dは6桁の数を2桁ごとに分割する方法を初手で思いつけた。コンテスト後のTLを見た感じかなり冴えていたらしい。Eは一周回るdpを一か所固定して切り開くやつ。

Fの $T_1$ は水曜日にグラフ理論の教科書で見たばっかり。こういう性質を持つ全域木にはNormal treeという名前がついているらしいが、図を見て一目でDFS木だとわかった。例えばLowLinkはこの性質を利用している。 $T_2$ については $T_1$ と対にして聞かれていることからメタ読みし、DFS木から連想してBFS木を考えてみるとピッタリ当てはまった。

Gで大炎上。多角形による点の包含判定は、右に半直線を伸ばして辺と交差した回数を数える形でライブラリ化されていた。凸でない多角形に対応するためこのような実装になっていることに気づかず、しばらくこの方針で考えていた。他に、逆にクエリの点をずらした多角形が $P$ に内包されるかチェックするようなことも考えるも、いずれも現実的なオーダーにならない。多角形の共通部分を計算するしかないのかと思っていろいろ検索すると、平面走査して特定の $X$ 座標における多角形の辺の $Y$ 座標を管理する方法を見つけた。これを使えば共通部分を計算しなくても判定できるかもしれない。つまり、 $M$ 個の多角形が直線 $x=a_i$ とそれぞれ2点で交わり、その間に $b_i$ が位置しているかをチェックする。多角形の上側だけ考えて実装すれば、下側は符号反転で対応できる。その上側について、辺を線分とみなせばCHTで解ける。さらに今凸多角形を考えているので、辺ではなく直線を考えてもよいということに気づいた。これを最初に気づけていれば……。

うしさんのライブラリを窃盗し、 $O(NM)$ 個の直線をCHTに追加してみると、まずコンパイルが通らなかった。どうやらテンプレート引数に浮動小数点数が渡せないらしい。ライブラリ自体を文字列置換で書き換えた。ACLのセグメント木の単位元を無引数関数で受け取る実装は、こういうケースを想定していたのかもしれないと思った。さらに、ライブラリで一様に型 $T$ となっている値のうち一部は整数型でないとまずいことにも気づいた。幸い、今回値を取得する点 $x$ は常に整数なので、これも何とかなる。そのほかいろいろ間違いがあったのを修正して残り80秒で投げると、1ケースだけ落ちてしまった。浮動小数点数の比較にEPSを使うようにして残り14秒で投げなおし、念のため別のEPSも試そうとしたらコンテスト終了。祈りながら結果を確認すると……AC！かなり嬉しかった。

7完81位。ギリギリまで粘って通せたため気分はよいが、全体として見れば愚か者の一言に尽きる。

間20分ですぐGCJ R2。コードゴルフは後回しになった。

https://codingcompetitions.withgoogle.com/codejam/round/00000000008778ec

Aは移動できるマスの差分を観察する。 $N=5$ の図を見ると、一周目から二周目へは $(+15,+13,+11,+9)$ 、二周目から三周目へは $(+7,+5,+3,+1)$ となっていることがわかる。また、例えば $+11$ を使った次は $+7,+5$ は使えないこともわかる。通常の移動では常に $+1$ なのだから、そこからの差分はすべて偶数。つまり、まず $N^2-1-K$ は偶数である必要がある。これがチェックできたら、あとは全部 $2$ で割って、 $(N^2-1-K)/2$ を $(+7,+6,+5,+4)$ 、 $(+3,+2,+1,+0)$ でうまく構築できないか考える。

実は貪欲でよい。貪欲に取ると最大で $+7+3$ が作れて、これはそれぞれの四つ組から一つずつしか取れないことを考えれば確かに最大。それ以下の数が全部作れると仮定して、四つ組の個数で帰納法を回すことで証明できる。実装の際は、差分を達成できるマスを求めておく必要がある。一周目から二周目のマスだけ手で埋め込んだら残りは規則的に決めていける。このとき埋め込むマスを間違えて1WAしつつ、なんとか通した。

Bは難しい。まずround関数とsqrt関数の組み合わせでどのような値になるのか観察する。roundを表す数学記号が思いつかないのでこうやって文字で書くことになってしまった。ある整数 $X\gt 0$ をsqrtしてroundすると、値が $Y\gt 0$ になったとしよう。このとき $Y-1/2\lt\sqrt X\le Y+1/2$ である。辺々2乗して $Y^2-Y+1/4\lt X\le Y^2+Y+1/4$ 。 $X$ として整数だけ考えているので、 $Y(Y-1)\lt X\le Y(Y+1)$ と書き直せた。このような $Y$ は確かにただ一つ定まる。

この式を使って、draw_circle_perimeterで塗られるマスは必ずdraw_circle_filledでも塗られることが確かめられた。 $x=0$ または $y=0$ の点はどちらでも必ず塗られるので、第一象限だけで数えて4倍することにする。 $1\le x,y\le R$ かつ $x^2+y^2\le R^2+R$ なる $(x,y)$ それぞれについてdraw_circle_perimeterで塗られるかチェックしたい。これは $x^2+y(y-1)\lt r^2\le x^2+y(y+1)$ または $y^2+x(x-1)\lt r^2\le y^2+x(x+1)$ を満たす整数 $r$ が存在するか確かめることで行える。式が2本あるのがつらいが、よく見ると $x\le y$ の場合前者だけでチェックしてよいことがわかる。

さて、ここで $x$ を固定して、 $r^2$ の分布と $y(y+1)$ の分布を考えよう。 $y(y+1)$ のほうが密に存在し、それを $+x^2$ で $r^2$ が疎になるほうへずらすので、 $x^2+y(y-1)\lt r^2\le x^2+y(y+1)$ を満たす解 $r$ は常に高々一つになる。つまり、チェックしたい $y$ の個数と解になり得る $r$ の個数をそれぞれ求め、引くことで、解が存在しない $y$ の個数を一息に求めることができる。 $x=y$ の場合を丁寧にケアして実装し、実験コードとしばらく比較して小さいケースで一致していることを確かめ、提出した。

Cも難しい。それぞれの子供について、1番目のお菓子以下の距離にあるお菓子を列挙し、辺を張ってみる。最も近いお菓子しか取れないという条件をなくせば二部マッチングになる。そうやってマッチングしたペアが、実際に残っている中で最も近いものならそれでよい。どの子供もそうでない場合、適当にマッチングを組み替えられるのではないかと考えた。ここにユークリッド距離を使うという問題設定が効くのだと思ってしばらく考えてみたが、まったくうまくいかない。純粋にグラフ的なアプローチを取るしかなさそう。

今、うれしい点として、残っているすべての子供についてマッチング先のお菓子より近くに別のお菓子が存在している、つまり二部マッチングを計算したグラフで子供から出ている辺は常に2本以上存在するということがある。これなら適当にdfsすれば交互閉路が見つかりそう。それっぽく実装するとWAだったので、もうちょっと丁寧に考えてみる。まず、ある子供のマッチング先を最も近いお菓子に変えようとしてみる。当然そのお菓子にはマッチングしている相手がいるので、今度はその子供に注目して最初からやり直す。こうして子供を辿っていくと行き止まりにはならないため、いつか必ずループする。ループの始点は最初に見た子供ではないかもしれないが、とにかくそのループに入っている子供のマッチング先を一斉に最も近いお菓子に変えても破綻しないことになる。実装を頑張って何とか通った。

残り15分ちょっとしかない。Dのsmallを通せないか頑張ってみる。とりあえず正の位置にあるビーチボールだけで考えてよい。 $0$ と $1$ で分けてソートしてみると、わざわざ交差した感じでペアにする必要はない。つまり今どのボールまで回収したかを持つ $O(N^2)$ のdpができて、これはsmallなら通る制約になっている。ここまでの考察がトントン拍子に進んで、実装もシンプルだったためすぐ書いて提出。何とか通せた。

Hiddenのジャッジ結果が出て、ABCdで29位。かなり良い順位。途中800位台で少し焦っていたが、Hiddenまで通していた人が思っていたより少なかったようだ。自分に自信を持ってもっとどっしり構えていたい。

ABCのコードゴルフに戻る。Aは速度でも長さでも負けていてボロボロ。BはOctaveで書いてみたら縮んだ。CはシンプルなAWKが最短になっていて、Vimで粘ってみたが最短タイから縮まなかった。Dは $i=0\dots 299$ に対して $\lfloor i/3+1\rfloor\times 100^{(i\bmod 3)}$ を出力するのが天才的。EはRuby。以降は手付かず。

その後朝まで日記を書き、布団でしばらくハーメルンを読んで、午前9時くらいに寝落ちした。

05/15(日)

午後3時半起床。ハーメルンを読み続けて、午後5時半に1作読了。「Vの者！～挨拶はこんばん山月！～」。

syosetu.org

昨年末から読んでいた。かなり面白かった記憶だけ残っていて、どこがどう良かったのかはあいまい。普段の面白おかしい配信の様子とシリアスなシーンの寒暖差がかなり大きくて大変だった。ただどの章もハッピーエンドで終わってくれたので一安心。キャラクターの元ネタは、僕が分かったものは全部現実の芸能人・Vtuberだったので、そのあたり詳しければまた違った読み方ができたのだろうか。起こった出来事のいくつかに他のVtuber小説で見覚えがあったので、それも実は現実のVtuber界隈で起こったことなのかもしれない。

布団から出てずっと日記を書いていた。午後9時からARC。

AtCoder Regular Contest 140 - AtCoder

Aは $|S|$ を周期的にすることを目指す。周期を全探索。BはA...ARC...Cという部分文字列に分割して、奇数回目の操作は長さを $2$ 減らすことになるので長いものから、偶数回目の操作は部分文字列を1つ削除することになるので短いものから優先的に使う。Cは $\{\dots,2,N-1,1,N\}$ か $\{\dots,N-1,2,N,1\}$ が嬉しさ $N-1$ と最大で、これを達成できない場合は $\{1,\dots,N\}\setminus\{X\}$ で同様の列を作って先頭に $X$ を置くと、嬉しさを $1$ だけ減らした状態にできる。ここまで20分弱。

残り100分はずっとDを考えていた。全然解けなかった。連結成分を作らない辺の本数を数えることと、各連結成分で最も小さい頂点番号の頂点を数え上げることを考えて、どちらもうまくいかず苦しんでいた。終盤になって、各連結成分がなもりグラフになること、さらに最初から連結になっている成分ごとに行き先が決まっていない頂点が高々1個であることに気づいて、その成分に分割した後ループの個数を数えるdpを書こうとしたが、値が全く合わずに終了。

3完171位。3完最速は昨日に引き続き愚か者。本当に助けてほしい。

午後11時半からCodeChefでMay Lunchtime 2022。

https://www.codechef.com/LTIME108A

ANDEQは残る値が必ず全体のbitwise ANDになる。この値になるように左からまとめていくと、達成した瞬間そこで切っても良いことがわかる。最後だけ達成できない可能性があるので、ちゃんと検出する。

B01Tは最初の部分点が大きなヒントになった。 $u$ の部分木について $1$ の個数から $0$ の個数を引いた値を $c_u$ とおくと、 $c_1/2=-\sum_v c_v$ が満たされればよいことになる。 $N$ が偶数なので、 $c_1/2$ は必ず整数になる。ここで最初の部分点は直線グラフだから $c_1/2=-c_v$ を満たす $v$ を見つける問題になるが、木をどんどん降りていくと $c_v$ は $\pm 1$ ずつ、つまり十分連続的に変化するので、どこかで必ず見つかるという寸法。そしてこれは、木の頂点をDFS順に並べることでも同じことが行える。

RERNGは最後のステップに時間がかかった。 $P_i\lt P_{i+1}$ を分割する必要があるのは、 $L\le j\le R$ であって $P_i\lt P_j\lt P_{i+1}$ なる $j$ が存在する場合であるとわかる。いったん $j$ の制限をなくして左右からそれぞれ最も近いインデックスを探し、 $l_i,r_i$ と名前をつけておくと、クエリに対する答えが $\#\{L\le i\lt R\mid L\le l_i\lor r_i\le R\}+1$ と書ける。条件を反転して $R-L-\#\{L\le i\lt R\mid l_i\lt L\land R\lt r_i\}+1$ を求める。

$R=1\dots N$ の順番に求める。 $i\lt R$ かつ $R\lt r_i$ であるようなインデックスの集合は管理できるので、それらから $l_i\lt L\le i$ なるものの個数を数えることになる。 $l_i\lt L$ だけ見ると、区間に対してある数未満の値をカウントするデータ構造が思い浮かぶが、僕が持っているものは静的である必要があったため使えない。しばらく考えて、遅延セグメント木の $(l_i,i]$ に $1$ 加算しておけば実現できることに気づいた。これで実装。加算する区間の右端が $i$ であることに気づかずに1WAしつつ、通った。

PWMULは3つ目の部分点まで。 $A$ の位数が小さければ愚直に計算できる。大きければすぐ見つかると信じて答えを全探索し、BSGS。このときBaby StepとGiant Stepのどちらかはテーブルを前計算できるので、そちらをunordered_setに持っておくこと、またもう片方のサイズを小さめにすることで高速化ができる。4つ目の部分点も通らないかと定数をいろいろ変えて投げていたが、全然ダメだった。BSGは1つ目の部分点まで。Aliceは最も左にある $0$ か最も右にある $1$ を、それと最も近いものとペアにするのが最適。Bobはその2つをペアにするのが最適。よって $0$ のインデックスと $1$ のインデックスをそれぞれ集め、列の左右からどこまで使ったかを持って $O(|S|^4)$ のメモ化再帰ができる。

375点で10位。2628→2708(+80)。

午前5時まで日記を書いていた。平日頑張って書き進めても、週末に5個もコンテストに出るともう追いつかなくなってしまう。一段落ついたところでインターン先勉強会の準備を始めた。なんと明日（狭義には今日）の勉強会は僕が担当なのであった。前々からわかっていたのにちっとも準備せずのんびりしていたツケを必死に支払うことに。一応何について話すかは考えてあったので、ガリガリスライドを作っていた。

午前10時になってひとまず完成。いったん寝て、起きて時間があればもうちょっと確認しておきたい、というくらいの出来。そこから1時間ほどかけてこの日記の校閲をした。