11/07(月)

午後4時半の少し前に起床。すぐインターン先の定例会に参加した。

先週の進捗は何といってもバグが取れたことに尽きる。今までは新しい仕様に対応するための下地作りといった感じで、それが終了し今週からいよいよ機能を追加して実際に対応させるフェーズに入る。順調順調と思っていたが、僕にこの作業を振ってくださった方が今日言っておられたスケジュールと照らし合わせるに、この先も余裕があるわけではなさそう。あいまいな感じだったので努力目標とは思うものの、早く終わるに越したことはないのでこれからも頑張っていきたい。

勉強会は……わからない。一体何の話だったんだ。定期的に行われる数学回で、今日は線形代数の中編と題されていたが、中身は超関数とかフーリエ変換とか。冒頭でフーリエ展開をしたところまでは、基底だから線形代数なんだなあという気持ちが持てる。しかしそこから先は何がどうしてどういう話題が出てきたのかすら掴めなかった。

圧倒されたまま午後6時半終了。それからはずっと週記を書いていて、午後11時過ぎに校閲まで終わらせた状態で公開できた。過去の週記には仕上げが終わっていないものがいくつか残ってしまっているが、現在のものを完成させるのを優先させている。なぜこんなにも毎週ギリギリなのかということについては、土・日・月にしこたま書いた反動でそれ以外の日はだらけ切ってしまっているから、と自覚している。

TTPCの解説スライドを読んでいた。H問題のメモリ制限の意味と自分が引っ掛からなかった理由を知ったため、先週の週記に追記しておいた。

TTPC2022 解説 - Google スライド

11/07追記：最大流のライブラリを使うと逆辺を持つところで制限に引っかかる。自分は蟻本にある2部グラフの最大マッチングを求める専用のライブラリを使っていたため難を逃れたようだ。
週記（2022/10/31-2022/11/06） - kotatsugameの日記

また、K問題をupsolveした。しばらく何も見ずに考えて、一人が出す手を固定してよいとか、012を割り振ると「あいこ」と「和が3の倍数」が同値になるとか考えていた。しかしまったく先に進めず、早々に諦めてスライドをちょっと見たら、9元連立方程式と書いてあってひっくり返った。パターンが9個しかないことには気づいていたが、本当にそれが正解の方針だとは……。

手計算で頑張って解くと2変数だけが残り、 $l_a\le a$ 、 $l_b\le b$ 、 $a+b\le m_{a+b}$ という範囲を動く整数 $a,b$ について $f(a)g(b)h(a+b)$ の和を計算する問題になった。この式が $\sum_{a,b}f(a)g(b)x^{a+b}$ を畳み込みで求めた後 $a+b$ を全探索すれば求まることに気付くのも少し時間がかかった。

Submission #36311842 - 東京工業大学プログラミングコンテスト2022

愚直に手で解きました pic.twitter.com/AkvNMVNM9M
— こたつがめ (@kotatsugame_t) 2022年11月7日

ラノベを1冊読了。「前世は剣帝。今生クズ王子」4巻。主人公の無双シーンは面白いものの、自分語りだか回想だかが多すぎてかつ読みづらいという評価をしていたシリーズ。3巻を読んでからしばらく時間が空いたが、記憶よりも読みやすくてびっくりした。1巻の時点では伏字にされていたキーワードが話が進むにつれて明らかにされた結果、文章の体をなしたということだろうか。1巻はもう実家に送ってしまったため実際どうだったかは定かでない。バトルシーンは相変わらず良い。主人公が「剣帝」と呼ばれた理由が明らかにされ、これもなかなか捻ってあって面白かった。

午前4時前に、10月中旬に行われたJOI一次予選（第2回）の問題が公開されていたのに気づいた。

JOI 2022/2023 一次予選 (第2回) 過去問 - AtCoder

JOI 2022/2023 一次予選 (第2回) の過去問 AtCoder ページを公開しました！https://t.co/quy5Vi0lii
— kichi2004 (@kichi2004_) 2022年11月7日

公開されたのは午前2時頃らしい。慌てて解いたものの、目ぼしい問題は縮め切られていた。AとCはほぼ自明で、Bは別方針でも最短タイにしかならなかった。一方Dは何とか縮めることができた。

9月に行われた第1回は、直後にTLで検索すると問題内容に関する言及やコード長が確認できたので、それを元に事前に問題内容を予測してC以外の最短コードを書いておくことができた。コンテストページが公開されたらそれらを自動で提出するようなスクリプトを回して放置しており、その後無事最短コードが取れたのだが、今回はほとんど言及がなくてダメだった。一応ページは開いておいて定期的にリロードしていたものの、タイミングも悪かった。

しばらくなろうやラノベを読んで、午前6時半ごろ就寝。

11/08(火)

午後1時半起床。

眠くて布団から脱出するのに30分以上かかった。そこからしばらくコードを書いて、午後3時から1on1。はっきり言って1時間弱では全然進められていないが、少なくともタスクの一部が思ったより難しいことは分かった。そういう困難も含めて行ったことを共有し、次に何をするかの判断を仰ぐ。

月曜日の日記でも書いた通り、これまでは下地作りで、ここから新たな仕様への対応が本格化するものと認識していた。しかしこれは異なっており、実のところすでにある程度形になっているようだ。扱うデータの設計が上手くて、それに沿ってコードを書き直した時点で対応もほぼ完了している、というか。残りやるべきことをリストアップしていただいたが思ったより少なかったのに驚いた。今日やり残したことも含まれている。今後はそれを一つ一つ潰していきたい。

午後5時終了。食事した後、夜からのSRMに備えてAppletを起動してみたが、証明書の確認に失敗した。はいはいいつものね、と思ってJavaの構成から設定を変更しに行ってみたら、以前同様のことがあって変えたものがそのままになっていた。

これまでの対処法が使えずどうしたらいいか途方に暮れて、とりあえずAppletをもう一度ダウンロードしてみたところ、なぜか動いた。ファイル名がこれまで使っていたものと異なっている。いつの間にかアップデートでもされていたのだろうか。

Competitive Programming at Topcoder | Topcoder

無事レジったので布団に入り、仮眠。午後6時半から午後8時45分まで寝ていた。気合いで身を起こし、午後9時からSRM841。直前になってC#とVBが使えないとアナウンスがされたらしい。それでもratedなのか……。

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

Easyは簡単。各bitが立つ確率がサイコロごとに求まるので、適切に掛け合わせてXORが立つ確率も求められる。簡単すぎて逆に怪しくなり、誤差がたくさん出るのかとも考えたものの、結局そのまま提出した。

Medは大変だった。leadした回数を考えなければならないのに、leadした時間の和、leadした時間の最大値と2回も誤読してしまった。さらに悪いことには、最初の誤読に対する解法は真の問題に対する解法とほぼ変わらなかったのに、2回目の誤読に対する解法だけちょっと変わったdpができてしまい、都合2回もコード全体を書き換える羽目になってしまった。このせいで時間を食って点数が大変なことに。

解法は $25^6$ 状態のdpで、1次元だけサイズ2にして配列を使いまわすことで空間計算量を削減した。やっとの思いでサンプルを合わせた後、念のために最大ケースを試したらTLEして絶望。しかしdpの値が0だった場合にスキップしたら十分高速になった。到達できない状態が思ったより多かったらしい。

残り20分でHardに進むも何もわからず。チャレンジフェーズではMedで上のような高速化をしていない提出がないか漁ったものの見つからなかった。EMはちゃんと通って2完19位、2829→2774(-55)。Hardはyukicoderでほぼ既出で、何やら名前の付いたアルゴリズムを使うらしい。

No.1069 電柱 / Pole (Hard) - yukicoder

ラノベを2冊読んだ。1冊目、「前世は剣帝。今生クズ王子」5巻。シリーズ最終巻。追い求めていたラスボスとのバトルがあったが、情報もスルスル集まって実際に戦うまでそれほど苦労したようには見えない。思ったよりあっさり終わったなという印象。結局回想シーンに登場した人々は一部を除いて誰が誰かよくわからなかった。人数が多すぎたし、あとがきにも本筋と関係ないのであまり掘り下げなかったとある。ただ作者の中では設定がいろいろあったようなので、減らしてほしいというのは酷か。

2冊目、「ブラックな騎士団の奴隷がホワイトな冒険者ギルドに引き抜かれてSランクになりました」6巻。名前がカタカナ3文字のキャラクターが多く、5巻を読んでから間が開いたこともあってなかなか読みづらかった。6巻になってから言及することでもないか。内容はヒロインの一人が体を乗っ取られて悪事を繰り返してしまうというもの。しかし主人公が強すぎて、乗っ取っていた敵が戦わずして降参するというアクロバティックな解決方法だった。拍子抜けだが、そのシーンに至るまではそれなりに面白かった。

セミナー準備のため教科書を読み始めた。木曜日に発表する分。前回は一度通して読んでからどういう風に話すか考えるという手順を取れたが、今回はそれほど時間的な余裕がない。それでも2回読んでおくと準備が楽になったので、今回は流れの確認と思って証明以外の部分だけ読むことにした。

途中で寝そうになったものの、朝までかけて発表するであろう分を読み終えた。眠気も消えたためそれから日記を書いていたら、結局購買が開く時間まで起きていることになったので、学食に行って食事し、注文していた本や菓子パンを購入して帰宅。

少しYouTubeを見て正午就寝。

11/09(水)

午後9時頃起床。まだ寝たい気持ちはあるが生活リズム的にもセミナー準備の進捗的にももう起きなければまずい。頑張って布団から這い出た。

しばしばYouTubeに気を取られつつ、午前4時半までかけて準備終了。体感としてちょっと少ない気もするが、メモ書きのページ数だけ見れば普段通りに見える。あとはどの程度図を描いて論述を省略するかということになるだろう。

余裕ができたと思ってコードゴルフしていたら午前6時を回ってしまった。急いで就寝。

11/10(木)

午前9時過ぎ起床。ちょうど3時間くらい寝た計算になる。

昨日寝る前に縮めた問題を確認したらさらに縮められていたので、しばらくそれとにらめっこしていた。昨日考えた方針の一つを再検討した結果運よく最短コードを取り返せたはいいものの、家を出るのがかなり遅くなってしまった。午前10時に少し遅れてセミナーの教室に到着。

午前中は同級生のセミナー。僕が教室に入った時にはすでに先生と何やら議論をしていたので、少し前提知識の説明をしてもらった後自分も参加した。特に発表という形でまとまっていたわけではなく、教科書の記述をより精密にできないかという予想を話していたらしい。見ていた限りでは肯定的に解決されて、自分でも直感的な理解が得られたので納得している。反例を作れたと思ったこともあったがただの勘違いだった。

午前中はそれで終了。正午から1時間は昼休みで、食事した後ノートPCでコードゴルフしていた。朝に縮めたコードがさらに縮められていたので、それに取り組んでいた。今度は大幅に縮め返すことに成功。ABC276-Cである。

atcoder.jp

後ろから見て初めて $P_i\lt P_{i+1}$ が成り立たなくなる $i$ を探し、 $P_{i+1\dots N}$ をreverseした後適切な $j$ について $P_j$ と $P_i$ を入れ替える。自分が昨日縮める前の時点では、いったん $P_i$ たちを配列に保存して、それを見ながら後ろを再構成していた。ところが保存しなくても直接$iを見て後ろにくっつけていけばよい。使った値に空文字列を入れておくことで不要な部分が出力に影響しないようにできる。その分数列の間に空白が入ってしまうがジャッジ的には問題ない。

ではどのタイミングで後ろにくっつける・空文字列を入れる作業をするかということで、今朝の時点では $i$ を見つけた後に行っていた。「適切な $j$ 」を見つけるループとまとめてあり、そのまとめ方で細かな改善がいくつかあって取ったり取られたりしていた。

そこで $i$ を探しながら行うことにすると、大変短くなった。 $i$ を探すループには式を入れられる隙間がいくつもあって、問題なくreverse用の作業ができる。さらに、2回目のループでは $j$ を見つけることだけに集中できるので式が短くなるようだ。あとは入力の読み方などに細かい改善がいくつも入って上のコードが完成した。

午後1時からは自分の発表。特に時間管理などしていなかったのでたまたまだが、ちょうど2時間で昨日用意した分を発表し終えることができてうれしい。今日の証明はちょっと長めで、最初に全体を概観してから説明に入ろうとしたところ先生から待ったがかかって例を要求された。用意していないしその場で作れるとも思えず窮してしまうも、先生がサッと描いたグラフがそのまま使えて感動した。

教科書に載っている魔法のような手順の証明に、感心はしても何か疑問を抱いたことはない。例がなくても論理が正しければ大体は納得してしまう。実はこれらは、研究者として良くない性質ではないか。今日のセミナーなどまさに対称的で、同級生は教科書を読んで抱いた疑問を突き詰めていた。セミナー発表自体は行われず、それについて先生から苦言を呈されていたが、しかしそうやって教科書を疑うような姿勢はこの道を進むならいつか必ず必要になるのだろう。

セミナー終了後しばらく打ち合わせをして解散。5限のTAのため山を下りた。

生協でラノベを買って教室に向かう。まだ4限の時間帯だったので、何食わぬ顔で教室に入って話を聞いていた。内容は生物で、目が悪く最後列からは黒板もスライドも見えないし、先生の声が小さくて聞き取りやすさも微妙。結局1ミリも理解はできなかったが、教室の広さを体感できたという意味では非常に有意義だった。何か説明するときはもっと大きな声・大きな文字である必要がある。

TA。今週も発表資料が共有されていないので、その場で話を聞くだけの楽な仕事になった。今日の発表者は二人。一人目は以前の発表、前回はまた別の話だったので2回前のときにやり残していた部分。説明に自分で納得いかなかったらしく、同じ内容を何度か方針を変えて喋っていたものの、自分が見ている限りではどれでも特に問題なかったしちゃんと理解できた。

二人目はGeoGebraによる図をたくさん用意しており、その場で点を打ったりしながらスマホのメモ書きを見て喋るという発表の方法だった。それ自体はよいが、細部の説明に入るたび方針を考えて少し詰まっていたのが気になる。自分にも覚えがあることで、準備段階では自明な考察に見えてもいざ教壇に立つと内容が飛んでしまうというのはあるある。

また、計算すれば資料に乗っている式や値が出るのは当然だが、だからと言って全部飛ばしてしまうのは講義の趣旨にあまり沿わないと思う。自分は資料のその部分をまだ丁寧に読んでおらず、興味もあったため、余った時間でいろいろ計算してもらった。以上2点に関して、メモ書きであっても事前に発表内容を共有してほしかったという気持ち。

講義後30分ほど質問対応をして終了、学食で食事して帰宅。疲れて結構な時間をボーっとYouTubeを見るのに費やした。

午後10時過ぎからは日記を書いていたが、同時に社築さんのサーモンランの配信も見ていた。「総理大臣によるサーモンラン」という動画シリーズにハマった結果、サーモンラン自体にも興味を持っている。非常に面白くて、午前1時くらいに終了するまでずっと気を取られていた。

www.youtube.com

制限時間ギリギリかつノルマ未達の状態で社築さんが死んでしまいこれはダメかと思ったら急に納品数が伸びてクリアしたり、3人死んでいるのに最後の一人がボスを倒してクリアしたりと、劇的なシーンが何度もあってかなり配信映えしている。特に後者は時間的に最後のバトルだったこともあって本当に興奮した。

午前3時くらいに切り上げて本を開いた。1時間くらいで閉じてハーメルンに移行し、午前4時半に寝落ち。

↓このツイートのイラスト3枚目は自分がイメージらしい。本を持っているのがそれらしい特徴だろうか。片目が前髪で隠れているのもふわふわのくせっ毛も可愛らしく、非常に嬉しい。競プロをやっていただけで美少女化イラストを描いていただけるとは、人生何があるかわからない。

とある赤コーダーさんたちを美少女化らくがき！ひさぶりにオタク活動してたのしかった
ご本人の目に触れませんように…と投稿してしまうの、一種の性癖であり深夜のお赦し　るるる pic.twitter.com/ZKv4twa3u3
— burioden (@burioden) 2022年11月9日

11/11(金)

午前11時半起床。

昨日寝る直前に読んでいたハーメルンをそのまましばらく読んでいたが、1時間ほどで放棄した。各話のタイトルを見た限りではこの先最新話まで主人公の出番がなさそうで、息切れ。

覇王、自由気ままに旅をする。 - ハーメルン

別のハーメルンを開いてそのまま読了。「俺は基本ソロの剣士なんだが、自称凄腕の盗賊とバディを組まされている。～お兄さんってぇ、陰キャのぼっちですよねぇ～」。主人公の淡々としたキャラと正統派の強さが読んでいて心地よかった。ちょっとシリアスな内容の話が数話ずつで展開されていく形式も読みやすい。

syosetu.org

午後3時過ぎに寝落ちして、目覚ましで午後7時に起きた。サークルをサボってしまった。うっかり午前中に起きてしまって、それから二度寝しなかったのが完全に失敗。自分の意志でハーメルンを読むのをやめられない。

目覚ましをこの時間にセットしてあったのはちょうどAHC016が始まる時間だから。まだレジってすらいなかったので急いで情報を入力し、問題文を開いて読んだ。読んだだけ。

HACK TO THE FUTURE 2023 qual（AtCoder Heuristic Contest 016） - AtCoder

ハーメルンに戻る。今日はどうやらyukicoderがないらしいので特に起きたままでいるつもりもなく、午後8時半ごろまた寝落ち。日付が変わる前に起床した。

ハーメルンを1作読了。「科学技術全盛時代に精霊の居場所は」。遊戯王の二次創作で完結済み。主人公はカードの精霊を見ることができる。見えるだけでデュエルが強いなどの設定はなかったものの、ちゃんと精霊と交流して絆を深めているのが良かった。主人公の回想に出てきた精霊がクライマックスで表れて印象的。その話のあとがきに怪しい空行があったため反転表示すると、精霊の内心が書かれていて、読んでニヤニヤできた。

syosetu.org

それから昼間までで本を4冊読んだ。

1冊目、「令和の化学者・鷹司耀子の帝都転生」。なろうで読んでいた作品の書籍化。結構な数の注釈がつけられており、より理解が深まったように感じる。なろうだとわからない専門用語もスルーしがち。ちょっと範囲選択して検索するだけで説明が読めるのに、その手間を惜しんでしまう。一方注釈を真面目に読んでいたら読了にかなり時間がかかってしまった。構造式まで出して説明されていた薬品や物質については、相変わらず眺めるだけになっている。

2冊目、「陰キャだった俺の青春リベンジ」2巻。前半のイベントは、主人公が努力して期末テストで学年一位を取るというものだった。「常に一位」とか「勉強して上位に」はよく見るが、トップにまで上り詰めるのはなかなか見ない気がする。この順位で勝負していた敵キャラを見返していて爽快。後半はヒロインの実家にお呼ばれし、親バカの父と問答。逆行転生モノらしく、一周目の人生で鍛えられた精神面で認めさせる気持ちの良い展開だった。

ラノベを読むことがヒロインと主人公の共通の趣味だが、逆行転生しただけあって挙げられるタイトルが古めで、自分では全部はわからなかった。そのままの形ではなく少し変えられているのでなおさら。

3冊目、同じく「陰キャだった俺の青春リベンジ」3巻、球技大会とお泊まり。運動が苦手な主人公なりに球技大会も練習から頑張っていたが、その前振りで描かれた一周目の人生における失敗のほうが記憶に残ってしまった。スポーツに関しては努力して成功することに現実感を持てない。主人公の家にヒロインが泊まるシーンは、主人公の家庭が2巻で描かれたヒロイン側の家庭と全く違う印象なので、2巻の焼き直しではない全く新しい感覚のやり取りが楽しめた。

4冊目、「ブラックな騎士団の奴隷がホワイトな冒険者ギルドに引き抜かれてSランクになりました」7巻。6巻でほとんどなかった分7巻では主人公のバトルが見られるかとワクワクしていたし、口絵も新技で圧倒する場面だったのでより楽しみにしていたが、思っていたのと違ったためあまり楽しめなかった。技を使うと幼児っぽい人格に切り替わるとは……。主人公の出生について少し明らかにされたので、それ関連の設定として意味のある描写だとは思う。

合間の時間に、また年末調整にチャレンジした。期限は11/14つまり来週の月曜日である。少し書類作成が進んだところで、インターンの給料の扱いに関して疑問が生じた。担当の方に質問を送ったが返信は月曜日になるだろう。それからまた書類作成を再開するためギリギリ。

TAも年末調整をしなければならないらしく、大学からメールが来ていた。読んでみるもほとんど意味が分からない。
週記（2022/10/31-2022/11/06） - kotatsugameの日記

午後3時前に就寝。すぐ生協の冷凍弁当配達で起こされ、受け取った。

11/12(土)

午後8時過ぎ起床。食事して午後9時からABC277に出た。

Daiwa Securities Co. Ltd. Programming Contest 2022 Autumn (AtCoder Beginner Contest 277) - AtCoder

Aはよい。ゴルフ的にもすぐには短くならないと思って次に進んだ。Bは正規表現を使えばよかったと後悔しながら頑張って文字を比較した。

Cははしごを $\min(A,B)$ でソートしてどこまで行けるか管理するというのを考えたが、よく見たら途中の階では上り下りできなかったのでグラフの問題になる。頂点番号が大きいので座圧して、UFで解いた。

Dは $A$ がソートしてあるものとすると、 $A_i$ または $(A_i+1)\bmod M$ が $A_{i+1}$ と等しいような区間の和の最大値を求める問題になる。列は円状に並んでいるものと見なすので、最初に条件を満たさないような位置を探して先頭に来るようrotateし、区間を貪欲に伸ばせばよい。実装しながら列を2倍にすれば楽だったなと思ったものの、そのまま書き上げたら無事通った。

Eはスイッチを押した回数の偶奇を持って01BFS。Fは0を無視してよく、行の入れ替えは明らか。列の入れ替えは列ごとの大小関係のうち必要なものだけ抜き出し、それを辺だと思ってループがないかトポロジカルソートして調べた。ただし同じ値が多いケースで大量の辺を張ってしまう可能性があるので、適切に超頂点を作ってまとめた。

Gは $i$ 回目の移動で頂点 $u$ にレベル $X$ で来る確率が $p$ だとすると、知りたいのはすべての $i$ と $C_u=1$ なる $u$ について $pX^2$ の和。 $(i,u)$ を状態として $\sum pX^2$ を管理しようとすると、レベルアップの処理が $\sum pX^2\rightarrow\sum p(X+1)^2=\sum pX^2+2\sum pX+\sum p$ となる。よって $\sum p$ 、 $\sum pX$ 、 $\sum pX^2$ を管理しておけば更新も含めて計算できる。

ここまで40分もかかっていないのにすでに全完が出ていてびっくりした。しかも、Exはそれくらい簡単なんだと思ったのに全然解けない。

値の上限と下限を考えて、更新が起こらなくなるまで条件を使って伝播していくコードを書いた。 $(A,B)$ を辺だと思ったとき二部グラフになるなら値を交互に上限と下限に揃えることで満たせる。そうでない場合にどうするかは全く分からず、残り時間が少なくなってから再帰で全探索っぽく決めるコードを投げたら2ケースWAだった。そのままコンテスト終了。

7完最速で11位。Gの公式解説が $X^2$ を分解する方法でびっくり。それで解けることを考えもしなかったし、自分の解法のほうがストレートだとも思う。

Exの解説を開いたら2-SATと書いてあってひっくり返った。こんなの見えないし見えたとしても1位が速すぎるだろと思っていたら、ECR130-Fで既出だったそうだ。出て、考察して、解けなくて、コンテスト後に2-SATだと知り、そこで終わっていた。upsolveしていれば何か違っただろうか。

https://codeforces.com/contest/1697/problem/F

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

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

Aは実験。 $n$ が奇数のとき $(n+1)/2\times(n+1)/2$ をちょうど作れるらしく、それに $1\times(n+1)$ を追加してもサイズは増やせないので答えは $\lceil n/2\rceil$ 。

Bは数える部分文字列の末尾と文字の種類数を固定するごとに、種類数の条件と、各文字が種類数以下の個数しか出現しないという条件を同時に満たせるような先頭としてありうる区間が定まる。各文字の出現位置を順に管理しておけばよい。区間の幅を足し合わせる。

Cは0の位置の直前で切って考えることができる。切ってできた各ブロックについて、先頭の0を適切な値に合わせることで、累積和を取ったものに一律で値を足せる。この操作でブロック内で最も多く出現する値を0に変えればよい。先頭ブロックだけは先頭に0があるとは限らないので注意。

Dは、まず $d$ が偶数の間 $a$ 、 $b$ 、 $d$ を2で割った。途中で $a$ または $b$ が奇数だと不可能。そうでなければできそう。 $a\;{\rm OR}\;b$ を壊さないように $2^{30}$ の倍数を足すことで $d$ の倍数を作ることを目指す。適当に下の桁から決めてもうまくいかないようだが、 $d$ が奇数であることより $\left(2^{30}\right)^{-1}\pmod d$ が存在するため、これを求めて $2^{30}$ の係数を計算すればうまくいく。

Eは後ろから見て累積maxの位置を管理しながらdp。インデックスと値を状態として持ち、一つ右を先頭としたときの累積maxのうち、値が自分以下だったものから遷移してくる。遷移元に割り振る値は今見ているところに割り振る値以下である必要があるが、さらに累積maxは狭義単調増加なので、それらの間で同じ値を割り振ることがないよう注意する必要がある。サンプルを合わせるのに手間取った。計算量は $O(nm)$ で、制約で $nm$ が上から抑えられているため十分高速。ここはちょっとあからさま。

Fは解けず。手数は多くなるものの、一応任意の位置の値を別の位置の値にXORすることが可能だったので、例えばこれでswapを実装した場合回数を無視すれば解けている。しばらく手で試してみて、両端からどんどん作っていく方針がよさそうに見えたが、回数制限が厳しくどうにもならなかった。5完26位。

ABCのコードゴルフ。CF前にやったものも含む。

Aはコンテスト終了直後にVimで書いたらすぐ短くなってびっくりした。同じ長さのコードが開始直後に提出されており当然負け。Bは正規表現をテストケースハックで縮めていたらそれ以外の部分がダメダメだったらしく大幅に更新され、負け。Cは後述。

Dは列を2倍にして尺取り。列全体を一つの区間だと思ってしまい、その和が $\sum_i A_i$ を超えるケースの処理では、答えと0との $\max$ を取るのではなく、区間を伸ばす前に和を $\sum_i A_i$ で割ったあまりに置き換えることで短くなった。以降は手付かず。

Cで嘘解法が通っているのに気付いた。これまで到達した最高階を $M$ として、 $\min(A,B)\le M$ なら $\max(A,B)$ まで行けるというもの。コンテスト中に一瞬誤読していたままの問題である。実のところ $A$ と $B$ の大小関係を見るのがそこそこ面倒なので思ったほどは縮まなかったが、それでもこの解法が現在の最短になっている。

CodeChefが一対一のゲームをリリースしたとTLで話題になっていたので、夜中に少し参加した。同時に問題を読み始め、提出欄でコードの穴埋めをして先にACしたほうが勝ちらしい。3戦戦ったが、人が少なく毎回同じ灰色の人と当たってしまい、申し訳なくなってやめた。それに問題の質、特に問題文があり得ないくらいひどくてエスパー必須だし、穴埋めするコードの変数名と問題文の変数名が合っていないし、今のところまともに遊べる状態ではないという判断。

Games by CodeChef: Compete against other players

朝までかけてラノベを1冊読了。「アラサーがVTuberになった話。」。ハーメルンで読んでいた作品の書籍化。やはり良かった。改めて読み返すのも楽しかったし、要所要所にイラストが追加されていて一見の価値あり。この巻の内容はハーメルンにあるものの2章までで、特に展開が変わったということはない。ちょっと本が分厚いが、クライマックスに相応しい展開をちゃんとラストに持ってくるのは上手いなあと思った。最初からこうやって分割されるのを意識していたのだろうか？

実はもう続刊が決定しているらしい。また2章分だとすれば、2巻のラストは自分の大好きなシーンになりそう。今から非常に楽しみである。

【お知らせ】
『アラサーがVTuberになった話。』
重版＆続刊決定しました。
これもひとえに皆様方のご支援の賜物と深く感謝申し上げます。
そして、2巻でも引き続きのご支援よろしくお願い致します。 pic.twitter.com/VdnED8zYLN
— とくめい@アラサーV重版＆続刊決定 (@hameln_tokumei) 2022年11月10日

しばらく日記を書いて午前9時前就寝。

11/13(日)

午後2時半起床。ダラダラしていたら食事する暇がなくなり、午後3時からOpenCupの代理コンテスト。

Petrozavodsk Summer 2022. Day 3. Qingyu, flower and their friends’ Contest - Dashboard - Contest - QOJ.ac

今回は難易度が高かったようで、チームで14問中MJGAICEの7完。これで2位、完数としては1位タイで、0ACの問題が5問あった。自分はEFを読んで解けんなあと言ったあと、特殊な言語でプログラムを実装するKに特攻してこれも解けず、コンテスト終盤にCの考察を受け取って実装だけした。一発で通ったのはよかった。

Cは隣接項の差の絶対値がちょうど1で総和が $n$ であるような正整数列に関する数え上げ。すると長さと最大値のどちらかが $O(\sqrt n)$ になるらしい。最大値が小さいものはdpで解けて、そうでないものは初項が大きいか、途中でしきい値を超えるかの $O(n)$ 通りしかなく、それぞれ長さを全探索できる。値が十分大きいと、以降数列の要素が正であることをチェックしなくてよいため、いくらか状態をまとめて計算したものから値を引っ張ってくることができる。ここも自分には少し難しかった。

自分が読んでしばらく詰まっていたEは、チームメイトがパッと見てすぐパスを交わらないようにたくさん取る問題だと解釈し、これでかなり見通しが良くなってびっくりした。この問題はそのままチームメイトが考察を完成させたのだが、ともかくそうやって考察の初手で正しい方向に進む能力から全然違うんだなあと実感している。他の問題も考察メモを見たら、自分にとっては非自明な考察が最初にポンと書かれていたりして感服するばかり。

コンテスト後に1時間ほど振り返りをして解散。それから朝まではダラダラ日記を書きながらYouTubeを見たりハーメルンを読んだりしていた。集中力が持続しないのにこうやって時間をかけるのはあまり良いことではなさそう。今週は前半頑張ってみたが木曜日の途中から溜めてしまっていた。

少し教科書を読んで午前9時前に就寝。