週記（2024/04/01-2024/04/07）

04/01(月)

午後3時起床。半から定例会に参加した。

先週はミーティングをした。今週もミーティングをする予定。新年度なので、自分がどういうタスクに携わっているかも改めて軽く説明した。

勉強会はGrundy数の話。Sprague–Grundyの定理とその証明を改めて聞いて、自分がステートメントを勘違いしていたことに気づいた。通常のNimと同様に進め、相手がGrundy数を大きくしてきたら小さくする、という戦略を考えれば必敗盤面とXOR＝0が対応することはすぐ納得できるが、定理の主張である「XORが全体のGrundy数になる」ことはより強い命題であった。

解散後は先週の週記を書いていたが、午後9時20分からのyukicoderエイプリルフールコンにうっかり参加してしまった。

yukicoder April Fool Contest 2024 - yukicoder

まずAを開いた。問題文が見えないが、お誕生日コン典型ということでページのソースに行ったら怪しげな文字列を発見。冒頭のdata:audio/mpeg;base64をググって、base64エンコードされた音声ファイルをでコードするWebページに辿り着き、無事問題文を「聴く」ことができた。なるほど問題名のListeningに納得。

Base64 to Audio | Base64 Decode | Base64 Converter | Base64

ところが、グラフの最大マッチングを求めよと言われてしまった。今の制約では無理そう。Library Checkerから高速な提出を窃盗してきたものの無事TLEしたため、いったん諦めてB問題に移った。

Bは最初のほうの問題なら解ける。A=3,B=23,C=180,D=-360,E=0,F=360,G=1,H=19,I=4。また「Wkh Fdhvdu flskhu」くらいまででググってみたらシーザー暗号がヒットしたため、復元してK=6も分かった。現在、式は次のようになっている。

\displaystyle f(n)=\frac{1}{\sqrt 5}\left(\left(\frac{6+\sqrt{\left\lfloor\frac{3\times(6J)^J}{J+19}\right\rfloor}}{L}\right)^{\frac{Jn}{4}}-\left(\frac{-\log_6(4\times(JL+1))}{1+\left(\frac{6^J}{180}\right)^{\sin\left(\frac{L+7}{6}\pi\right)}}\right)^n\right)

残り2問は解けなかったためエスパーで。まず、\sin( (L+7)\pi/6)の値がまともに扱える値になるのはL=2のときの-1、L=4のときの-1/2のみである。次に\left\lfloor 3\times(4J)^J/(J+19)\right\rfloorはJ=1,2,3,4でそれぞれ0,2^2\times 5,3\times 5\times 53,3\times 5^2\times 577。最後に\log_6(4\times(JL+1))を見ると、整数になるならJL+1=9より(J,L)=(2,4),(4,2)だろうと思える。

まあ6は\bmod 998244353における原始根なので、6^{\log_6 x}\equiv xという意味での\logは常に定義できないこともない。ただそれを用いたところで整合性のある計算結果になるかは知らないし、何よりその解釈を用いるとしても絶対に解決しなければならない問題が残っていることに気づいた。すでに決定した部分に現れる\sqrt 5は、\bmod 998244353において定義されない。

ということで、これをキャンセルするような形で同じく\sqrt 5がそこかしこに現れるだろうと考えた結果、(J,L)=(2,4)がちょうど良さそうに見えた。この時式は次のようになる。少し前の時点でさすがにフィボナッチ数列の一般項だろうなとは想像がついていたが、実際ここから有理化などを行うとピッタリ一致する。これでようやくACが取れた。

\displaystyle f(n)=\frac{1}{\sqrt 5}\left(\left(\frac{3+\sqrt 5}{2}\right)^{\frac{n}{2}}-\left(\frac{-2}{1+\sqrt 5}\right)^n\right)

次にsolved数を見てEへ。これは検索サイトがあることを知っていたので、ググって出てきたところで探した。

Aに戻って悩んでいたら急に閃いた。最大マッチングつまりmaximum matchingを求めろと聴こえたが、あれは実はmaximal matchingだったのではないか。この発想が降ってきた瞬間、あまりの「それらしさ」に正解を確信。貪欲を提出したら無事通った。かなり好きだったのでFavしておいた。

最後にC。3N回を超えて質問した場合のジャッジ結果が不定だから実は許してくれるんじゃないかと思ったが、普通にQLEが出てきてしまった。絶対にギャグだろうと思っていたので今度は初手で(1\dots N,1\dots N)を答えてみたところ、正解だった。

ABCEの4完で4位。Cは当てずっぽうでACを取ってしまったが、題意はインタラクティブの問題文に関する良い指摘だったと思う。まあアダプティブにおける「これまでの質問から回答が一意に定まらない場合WAとする」という注意書きは、それが判定できるという意味で解法のヒントになる可能性もあるから、なかなか難しい出題方式。

コンテストは午後11時くらいに離脱し、週記を書く作業に戻った。日付が変わる直前に投稿。読書記録ツイートもしておいた。3月頭まで没頭していたなろうは現在手が止まっているが、代わりにその期間チェックしていなかったハーメルンやカクヨムの作品を読み漁ってしまっており、ネット小説を優先してしまっている現状は変わっていない。

椅子でしばらく寝落ちしてしまったので布団に移動し就寝。午前2時だった。

04/02(火)

午前4時半くらいに目を覚まし7時間ほどハーメルンを読んでいたらしい。二度寝して、午後3時に目覚ましで起床。明日の入学式のためクリーニング屋に預けたワイシャツを回収してくる必要がある。午後5時閉店なのでこの時間に目覚ましをかけていた。

シャワーを浴びて外出し、無事受け取りに成功。そのまま何もせず帰ってきた。帰り道に花見会場があったので出店で食事でもしようかと思ったが、先週母親が作ってきてくれた総菜がまだ残っているため止めておいた。桜はまだつぼみだった。

帰宅してから午前1時までずっとハーメルンを読んでいたが、重い腰を上げて修論の英訳を始めた。しかし午前4時にはもう眠くなってしまったため就寝。

04/03(水)

午前9時起床。シャワーを浴び、スーツを着て入学式に向かった。

着席完了時刻を過ぎてから到着したら保護者席に通された。式は特に何事もなく終了。退場後、その場で自撮りしてツイートした。

偶然会った同期の友人と近くにあったIKEAを練り歩いた。売り場で山積みになったサメの抱き枕を発見し、買うかどうかかなり迷った。昼食は中のレストラン。見ていたのが会員価格だったらしく、思ったより高くついてびっくりした。

ABC345優勝賞品のアマギフ10万円が届き、ついに残高100万円を突破した。一度超えてみたかった壁だったので達成感がある。有効期限は短いものでもあと8年以上あるので、消費について考えるのはまだ後回しにできるなと思っている。

寝るまでずっと修論の英訳作業をしていた。午前2時就寝。

04/04(木)

午前7時半起床。修論の英訳を続け、正午くらいに一段落させて先生に送り付けた。ページ数稼ぎの内容を全部削除したらかなり短くなった。

シャワーを浴びて原付で登校。微妙に暑かったので、普段Tシャツの上からパーカー、さらにウィンドブレーカーを着ていたところ、パーカーを外してみたのだが、教室での体温調節ができなくて大変だった。パーカーは着ないとしても持っておいたほうがよさそう。行き帰りについてはこれで特に問題なかった。

学食で昼食を摂って午後1時からセミナー。昨年度オンラインで参加してくれた学生がついに進学・引っ越ししてきたので、彼も交えて今後しばらくの予定を決めた。その後1時間半ほど自分が発表。3週間前に準備してきたものを話したが、内容を忘れかけておりかなりたどたどしい感じになってしまった。最後に修論の英訳についてダメ出しがあった。

午後4時からは数学専攻のガイダンス。ほとんどが就職の話だった。

終了後は同期数人と割り振られた博士の院生室を探検した。全体的に埃っぽいし散らかっている。大量の漫画とコスプレAVを見つけたので、前者は修士の院生室に持っていき誰でも読める状態にしておいた。以前からの居住者もいるが、漫画の年代的にその人たちの持ち物ではないだろう。

学食で夕食を摂り、午後7時帰宅。TLを見たりしてダラダラ過ごしつつ何とかシャワーを浴び、午後10時半に寝た。

04/05(金)

午前5時半起床。

ハーメルンで「カードゲームで世界が滅ぶ世界に転生してカードショップを開店したら、周囲から前作主人公だと思われている」を読了した。ランキング上位に駆け上がってきた作品だけあって非常に面白かった。前作主人公という単語を筆頭にメタ的な発言が多いが、そういう世界観が主人公の超然としたあり方を後押ししている。周りのキャラから見た主人公パートもしっかり用意されていて嬉しかった。

syosetu.org

その後、ハーメルンを読んだり正午から3時間ほど二度寝したりしているうち、午後5時になったので1時間ほどミーティングに参加した。

先週生えたタスクは、現状のものを大幅に改革しないとあまり意味がなさそうだったので、別部署に任せることになった。人間同士のやり取りで使われるExcelファイルをプログラムで読むのは難しい。特に吹き出しなどのオブジェクトは、視覚的には分かりやすいのかもしれないがそもそも対応していないライブラリも多く、手も足も出ない。別のタスクを生やしてもらい、しばらくそちらに向けて調整することになった。

いくらか調べ物をした後、ゲーセンに行くため外出。大学近くの交差点を通りかかったらちょうど部活終わりの集団がいたのか自転車がたくさん走っており、春の訪れを感じた。

まず大戸屋で夕食を摂った。ちょっと多すぎた。大戸屋のセットメニューは単品の量を変えずに組み合わせてくるから注意が必要。

ゲーセンでは閉店まで16クレプレイした。一生終わらない新曲埋め。大型アップデートからこちらポゼッションを復活させられない。成果としては「Longinus」のAJが出た。調べて気づいたが14.9の初AJらしい。精度も非常に良くて嬉しい。延々続く分割トリルは必死にジタバタしたら通っただけで、あんまり押せた気はしない。

日付が変わったくらいで帰宅。結構な時間YouTubeを眺めながらボーっとしてしまったが、気合いを入れてシャワーを浴び、午前4時に寝た。

04/06(土)

午前9時半起床。ずっとハーメルンを読みふけっていた。午後2時を前に布団から這い出し、Universal Cup 27回目、Indiaセットに出た。

https://qoj.ac/contest/1586

書く：UC

Twitterのアカウント登録から11年が経ったらしい。当時は意識するはずもなかったが、登録したのはたまたま13歳という規約ギリギリの年齢だったようだ。設定された誕生日と照らし合わせたとき違反しているアカウントには容赦なくロックがかかると結構前に話題になった。そのときに自分も確認して胸をなでおろしたことを覚えている。

午後9時からABC348。

Toyota Programming Contest 2024#4（AtCoder Beginner Contest 348） - AtCoder

Aはなぜペナルティキックが題材なのかよくわからないがやるだけ。Bもよい。Cは最大と最小で混乱しそうになったので問題文をガン見しながら実装。Dは適当にDijkstra……と思ったら同じマスから何度も遷移する可能性があることに気づいた。正解は薬同士の距離をO(NHW)かけて求めてN頂点のBFS。コードをかなり書き直すことになって大幅にタイムロスした。

Eは全方位木dpで計算できる。根をずらしたときの差分と考えたほうが簡単だったらしい。パスグラフで答えが2.5e18くらいになることに気づかず、答えの初期値を1e18にしており1WA。Fはしばらく考えても分からなかったもののO(N^2M)を書いてpragmaで最適化をかけたら爆速になった。730msとまあまあ余裕をもってAC。

Gは解けなかった。\max Bを固定したときの答えがkに対して上に凸となるから、その折れ線複数の最大値を取るとして、傾きの集合の変化を追えばよいのではないかと考えたりしていた。このG問題がなんと100人に通されており、6完119位。久しぶりにABCで3桁順位を取ってしまった。

書く：G

Gのupsolveをしていたら振り返りが間に合わなかった。録画を続行し、午後11時半からCGR25。久しぶりのGlobal Roundである。

Dashboard - Codeforces Global Round 25 - Codeforces

書く：CF

2コンテストぶっ続け、7時間弱という長さの動画を投稿した。

www.youtube.com

ノクターンノベルズを読んだり日記を書いたりして午前11時就寝。

04/07(日)

午後5時に目覚ましで起床。いざAHC……と思ったら2時間早かった。寝なおすつもりがうっかりハーメルンに没頭。午後7時から、改めてAHC032に参加した。

AtCoder Heuristic Contest 032 - AtCoder

書く：AHC

「リィンカーネーションダービー ‐新人トレーナーがんばる‐」を読了。ウマ娘の二次創作において総合評価トップの作品である。昔から存在は認識していたが、あんまり勝てなくて辛そうな雰囲気のあらすじだったため敬遠していた。しかし読んでみると、確かに最序盤は負けっぱなしで苦しいところがあるものの、すぐにとんでもない実績を積み上げていくようになった。ただしそこまで読んだころにはもうストーリーやレース描写に引き込まれ、勝敗に関わらず面白いと思うようになっていた。レースやその前後のシーンが毎度毎度感動的で涙をこらえられない。

出走馬をかなり史実に寄せたらしく、ネームドウマ娘であっても容赦なく故障で休養に入っていくのがなかなか寂しいところ。そのためか競い合う相手が固定されていて、レースごとの展開の差異は少なかった印象がある。そのうえ主人公チームのウマ娘でも容赦なく負けさせるから、最後まで結果がどうなるかわからず毎回ドキドキしていた。

スマートファルコンの様子がおかしいという描写が中盤くらいから存在して、そのことには気づけたものの、どういう感情に由来するものなのか他人の感想を読むまで理解できなかったのが残念。これは原作を知らないせいだろう。教えてもらえてラッキーくらいに思っておきたい。ハーメルンの感想欄はBadが多いものが非表示になるので安心して読むことができる。

syosetu.org

日付が変わったくらいで寝落ち。