06/24(月)

午後3時過ぎ起床。昨夜開催されたUniversal Cup Semifinalsの順位表凍結が解除されており、我々のチームは全体10位・Finals未進出チーム内6位だった。8位までは確実にFinalsへ行けるはずだから、これはもう確定と言っていいだろう。やった！！！ちなみに決勝がいつどこで行われるかについては、まだ一切のアナウンスがない。

The 2nd Universal Cup Semifinals - Standings - Contest - Universal Cup Judging System

午後3時半からインターン先定例会に出席。進捗がないので、やろうとしていることを具体的に書いてお茶を濁した。勉強会は時系列データの圧縮アルゴリズムについて。時系列データは例えば一定時間ごとに取得されたりしており、差分を取るとほぼ定数、かつ値もあまり大きくならない。それを活用すると高い圧縮率が実現できるようだ。bitに詰め込んだり、差分のさらに差分を取ったりしていた。

解散後は大学生協でラノベを受け取り、夕食。帰宅してからはずっと先週の週記を書いていた。普段はUCまで手が回っていないが、今回は時間に少し余裕があったし、Semifinalsという特別な大会なのでちゃんと書くことにした。日付が変わる直前に投稿。その後しばらく追記してUCについては完成させ、灘の有志コンだけ穴あきで残っている状態となった。

ラノベ「冒険者酒場の料理人」を読了。面白かった。迷宮産の素材を試行錯誤して調理していく過程は丁寧さとテンポの良さが両立していて小気味よい。また合間合間に描かれる街や酒場の様子は人情味があって、味わい深かった。異世界での日常を描くという点で「バスタード・ソードマン」を思い浮かべたが、こちらは主人公が貧弱なため少しヒヤヒヤする場面がある。しばらくすると戦闘力がヒロインに外注されて一安心。

午前9時就寝。明日は午後1時からホスフィンと二人で集まり、進捗を産む会を開催する。

06/25(火)

午後1時起床。遅刻である。曇り空が怪しかったので地下鉄で登校し、さらに学食で食事していたら最終的には1時間遅れでの到着になってしまった。

夜までずっと集中講義の課題に取り組んでいた。5月末に受講したものだが案外記憶が残っていて助かった。課題は10問ある演習問題をできるだけ解いてレポートにせよというもの。講義に最後の最後までついていけたこともあってか、問題はこれまで受講した集中講義に比べると非常に簡単に感じた。ただ時間はかなりかかって、これだけで一日が終わってしまった。

ホスフィンに無職転生第2期の22話を見せてもらった。なろうで読んだ時の記憶がはっきり残っているわけではないが、再会できそうでギリギリできなかったこのタイミングの悪さが非常に辛かったことを思い出した。そのまま23話の冒頭もチラ見。昨日TLに流れてきたイラストが記憶に焼き付いていたので、そのセリフを確認した。

長編大作の無職転生の中でもNo1に響いた、完全に沼ったといっても過言ではない台詞。アニメで聞けて良かった。 pic.twitter.com/mYaSkt5vwA
— ーSHU (@misasagi99) 2024年6月23日

明日は午後5時から集まることにして午後11時過ぎ帰宅。半からCF #955 div.2に出た。

Dashboard - Codeforces Round 955 (Div. 2, with prizes from NEAR!) - Codeforces

Aは逆転が起こらなければよい。Bは $y$ で割れるまでインクリメントするのをまとめて行うと、 $\log_y x$ 回くらいで $x=1$ になり、そこからはループする。Cは $l$ をギリギリ超えるだけ取るか1枚だけ取るのを考えればよい。後ろからdpしたが前から貪欲でよかったらしい。

Dは冠雪している・していないで高さに $\pm 1$ を掛け、足し合わせて $0$ にしたい。操作範囲の符号を集計すると総和をどれだけずらせるかわかるから、可能な操作に対して求めたそれらの $\gcd$ が最初の総和を割り切ればよい。

Eは区間内でpopcountが最も大きな数を考える。 $l\lt r$ なら $l$ において $l\oplus r$ のMSBより下のbitをすべて立てた数、もしくは $r$ のみが候補。このときMSBより上にはあまり興味がないから、その部分の情報はpopcountだけ持つことで桁dpで数え上げられるようになる。

Fは大変。ソートしなくてよいprefix/suffixを求める。列をreverseすることによりprefixだけ考えれば十分。列の要素がdistinctならば、あるべき位置に存在しない最小値を求め、それ未満の数がいくつあるか数えることによって達成される。ここで求める最小値は、列において直前の要素より小さい値の最小値として特徴付けられるから、これを管理した。distinctでない場合もインデックスとペアにして考えればよい。

$\log$ 一つだが定数倍が重く、pretextで2200msと少し不安だった。2300msに伸びつつも何とかシステスを通過してくれて、全完9位。

www.youtube.com

日記を書いて午前7時就寝。

06/26(水)

午後5時起床。また集合予定時刻に起きてしまった。天気が良かったので昨日とは違って原付を使えたが、代わりにガソリンスタンドに寄ったため相変わらず1時間遅れでの到着となった。数日前に夏至を迎えてこの時間でも非常に明るく、まるで昼下がりのよう。

今日は先週書いて動かした実験コードが正しいか検証していた。本当は手計算と比較するつもりだったが、それが可能なサイズではあまり情報が得られない。とりあえず文献に載っていた例をいくつか試し、正しい結果が出ていることは確認した。また午後10時くらいからはセミナーで読んでいる論文の行間を、ホスフィンにも考えてもらって埋めた。

夜中のCFもないし終電も気にしなくていいしで日付が変わってからもしばらく話続け、午前1時半くらいに解散。コンビニに寄りつつ帰宅した。メールでABC355の賞品アマギフ15000円分が届いていた。

実験コードの話。デスクトップPCで動かしているとあっという間にメモリ使用量が増えていき、64GBあっても数時間で食い尽くされるため、進捗をファイルに書き出すようにして、起きては再開し帰宅しては再開しを繰り返す羽目になっていた。PythonあるいはJupyterの書き方が悪くて不要な変数が生きているものと思っていたが、今日ノートPCで実行してみると全く問題なく動いてびっくりした。環境の違いらしい。

手始めにバージョンを調べると、デスクトップPCのPythonが古いことが判明した。aptでは更新できず首を傾げたが、そもそもまだUbuntu 20.04にいるのが悪いようだ。ということでUbuntu 22.04へのアップグレードを開始。機械学習用に入れたNVIDIAドライバーの更新をしてからdo-release-upgradeを実行し、1時間ほど待っていたら何事もなく完了した。実はOSのバージョンアップをするのは初めてなので感動した。

同時にパッケージもバージョンアップされた結果、メモリをバカ食いするのは解消された。しかし、安心して実験を回していたら、今度はログ出力が100MB近く溜まってChromeが耐え切れなくなってしまった。これまでちょくちょく再起動していたので顕在化しなかったらしい。どうせ正しく動いているのでバッサリ全部取り除いて実行しなおした。

そんなことをしながらラノベを読み進め、午前8時就寝。

06/27(木)

午後0時半起床。原付で登校し、パンを買って食べて午後1時から後輩のセミナー。

今日は結構詰まって大変そうだった。教科書で「簡単な」とか「明らかに」と言われている事実は、確かに感覚として明らかに見えるものも多い。しかし、では示してくださいと言われると途端によくわからなくなることは、まあなくはない。万全を期すなら準備段階で少し考えておきたいところではあった。あとは、そのような言葉はセミナー資料に書かないとか……。

午後3時からは後輩の院生室仲間を招き、自分の修論や最近の研究について説明した。知識が非常に広い人で、知らない分野との関連性を指摘された自分はタジタジになりつつ曖昧な顔をして頷いていた。興味はあるらしく、進展があったらまた聞かせてほしいと言ってくれたのは非常にありがたいこと。普段のセミナーに人を巻き込むのは難しいからいい機会だった。

セミナーは午後5時に終了。その後後輩と今日のセミナーで詰まった箇所について議論し、学食で夕食を摂った後はいつものように立ち話をして別れた。午後8時過ぎ帰宅。

ラノベ「最強守護者と叡智の魔導姫」を読了。表紙イラストを見て清楚なヒロインだと思っていたら冒頭から真逆の行動ばかりでびっくりした。明け透けに迫ってくるヒロインは苦手かもしれない。一方能力の強力さは好み。敵を倒す直前に遠隔で割り込まれ取り逃がしかけたところで、ヒロインが能力を使って隠れていた敵の名前を暴き、動揺させたのが特に良かった。安全圏にいる相手に一矢報いる展開は、直前までのフラストレーションが解消されて好きである。

午後11時半からはECR167に出た。

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

Aは $y\ge -1$ 。Bは $b$ の連続部分文字列であって $a$ の部分列として取れる最も長いものを求めればよい。インクリメント忘れでマッチしたインデックスを使いまわしてしまう、部分列計算時の典型的なバグで1WA。

Cは $(a,b)=(+1,+1),(-1,-1)$ をどう割り振るかが問題。個数を式で置いて計算したら、二分探索するまでもなく直接答えが出た。言われてみれば当たり前の上界たちのMIN。Dは作れる武器のうち $a-b$ が最小のものを貪欲に作り続けるのがよい。 $\max a$ 以上については作る武器が決まるので算数で求め、 $\max a$ 以下はdpしておいた。

Eは $a$ をランレングス圧縮した列を考えてみると、同じ値の連続区間はほとんど $b$ から復元できる。唯一不可能なのが $b=[\dots,1,1,\dots]$ で、長さ1の区間が二つあるのか長さ2の区間が一つあるのかわからない。よってこれは前者に固定することとした。最初と最後の区間も合わせ、 $f=x+x^3+x^4+\dots$ として求める値は $[x^n](f+x^2)^2(f^{k-2}+f^{k-1}+\dots)$ 。つい最近のTCBからFPS関連を拾ってきて通した。

Fは制約を、行と列のどちらを後から塗るかという制約に書き換え、そこから作った有向グラフの強連結成分ごとに操作していくことになる。つまりオフラインで辺の追加と強連結成分のサイズの取得ができればよい。ググって記事を見つけたはいいが読解に失敗し、実装できなかった。

My own algorithm — offline incremental strongly connected components in O(m*log(m)) - Codeforces

5完15位。Fはupsolveしておいた。分割していく時系列と考慮すべき辺が別物であるということに気づいておらず、持っている辺の前半だけ使ってSCCを計算してみるなど寝ぼけたことをしていた。SCCを計算するためには最初のほうからほとんどすべての辺を管理しておく必要がありそうだが、頂点の適切な圧縮によってdisjointに分けられ再帰していく様は見事。

www.youtube.com

動画をアップロードしたのち、公開作業をする前に布団に倒れこんで寝落ちした。午前3時半くらい。

06/28(金)

午後1時に目を覚ました。今日は床屋とゲーセンに行きたいが、とりあえず寝そべったままラノベを開いた。

「魔法警察ファンシー☆マリリン」を読了。ヒロインが魔法でフーダニットだけ行い、主人公が推理でハウダニットを補足するミステリ。それをかなりラノベに近づけたようなものだと思った。一つ一つの事件が非常にスピーディに解決していく。容疑者や証拠はほとんど最初から提示されており、推理シーンが始まれば犯人はすぐ取り乱して馬脚を露す。さらにホワイダニットについてはほぼ自供頼りだった。とまあミステリ部分についていろいろ言ったが、とにかくテンポが良かったので、ラノベとして面白かったと思う。

一瞬布団から出て昨日のECRの動画を公開した後、再度布団に戻って別のラノベを読み続けていた。午後5時くらいになってようやく行動する気になり、シャワーを浴びて大学生協へ。床屋の前に購買でラノベを買ったところ、顔なじみの店員さんに学年を聞かれた。そういえばここで本を大量に買うようになったのは2020年だから、もう4年経ったのか。

床屋では散髪後に「ワックスは付けないんですか？」「ワックス付けるといいですよ！」と猛プッシュされて困惑した。実は前回もほとんど同じことを言われている。「急に結婚式に呼ばれたらどうするんですか！」みたいな話をされたが、そのようなイベントが自分の身に起こるとは考えたこともなく、愛想笑いしかできなかった。

学食で食事して帰宅し、再度シャワーを浴びた。食事中に自分の院試体験記を読んだ外部受験生から連絡が来ていたので、自分が当時作成した過去問の解答を整理して送った。院試ゼミのメンバーで分担して解いたため、自分の解答だけではカバー率が非常に低い。本当に参考になるのか不安である。

kotatsugame.hatenablog.com

今日買ってきたラノベをチェックしたら、予約したものと違うことに気づいた。生協への入荷メールまでは正しいため、おそらく他の人が注文した本と入れ替わってしまったのだろう。会計の際、電子マネーにチャージすることに気を取られて、商品の確認をおざなりにしてしまった。幸い明日も購買は開いているので、行って確認してみたいと思う。

もう夜も遅く、残念ながらゲーセンに行くような時間ではなくなってしまった。yukicoderに参加することとする。サイトを開いたら先週のコンテストのE問題がチャレンジで落ちていた。指数部の $A_1+2A_2+\dots+NA_N$ がオーバーフローし得るらしい。修正し、午後9時20分からyukicoder 435。

yukicoder contest 435 - yukicoder

Aは埋め込み。お誕生日コンテストと聞いていたので、この問題を見て「そういう」ことだと思ったのだが、以降は普通の問題が続いてびっくりした。Bは操作Bでできるようになることがちょうど二つのマトリョーシカを組み合わせることだけなので、最初に操作Aをできるだけやっておきたい。 $R$ が大きいほうからmultisetで適当に貪欲すればよい。

Cはサンプル出力でお絵描きをし、 $A\lt B$ として $(B,0)$ と $(0,0)$ を $(+B,+A)$ ずつずらしていくパターンを見出した。 $A\times A$ の周囲を見ると四畳半みたいに詰め込まれそうだからかなりそれっぽい。ペナがないのでとりあえず投げてみると、大半のケースで通ってびっくりした。 $A$ と $B$ が互いに素でないとき壊れるようだ。改めてお絵描きすると、全体を $(+B-A,+B+A)$ だけずらして繰り返せばよいことがわかり、もう一度出したら通った。

DはNyaanさんのライブラリから拝借した高速素因数分解を貼った後、 $L$ を決め打って素因数ごとに数えた。数えるのにはdpを使ったが、結局分割数を計算していたらしい。またこのことを使うと $p^2\mid N$ なる $p$ しか考える必要がなくなり、真面目に素因数分解するよりオーダーが落ちてライブラリなしでも解けるらしい。

高速素因数分解(Miller Rabin/Pollard’s Rho) | Nyaan’s Library

Eは勘。ケーキを切る側は弱そうというところから考察を開始した。このことから、お互いまず $S\le K$ なるケーキを交互に食べていくはず。残る $S\gt K$ のケーキについては、 $S$ が偶数なら半分に分割した後真似っこ戦略をとることで切る側が $S/2$ だけ食べられる。 $S$ が奇数の場合は最初に1だけ切り離すなどで $(S-1)/2$ だけ食べられる。「切る側が弱い」んだからこれが最善だろう。一つのケーキを食べつくすたびに切る側が交代することを考えて貪欲に取ったら通った。

Fは案外簡単。部分木のGrundy数をすべて求めたい。ある頂点 $u$ について $u$ 以下の部分木だけ考えているとき、1手操作したときのGrundy数は、操作したパスから1歩外に出た頂点たちのGrundy数のXORだから、パスを $u$ の親へと一つ伸ばしたときの変化は、パスのもう一方の端点によらない値のXORとなっている。つまり数値の集合に対して全体XORとMEXの取得、さらにマージテクが行えれば木dpで計算できる。そしてこれらは実際binary trieで実現可能。

Gには手も足も出ず。ただしABCEでFA、さらにFが2ACしか出なかったこともあって完数も点数も断トツの優勝となった。

「双子探偵ムツキの先廻り」を読了。これもミステリラノベ。双子の兄が常時異様なまでの警戒心で監視カメラを設置したり録音を行ったりしており、この「先廻り」によって得られた証拠で事件を立ちどころに解決するという話。ホワイダニットだけは担当できないので、双子の妹が代わりに暴く。証拠を出す前に丁寧に推理を行うものの、最終的にはポンポン出てくる証拠で押しつぶすような解決。ミステリとしては身も蓋もないが、爽快だった。

午前2時に寝落ち。

06/29(土)

午前4時に目を覚まし、ラノベを開いた。

「地味なおじさん、実は英雄でした。」を読了。ダンジョン配信モノ。面白かった。主人公がネットに疎く、また配信も姪が勝手にやっているだけなので、コメントやネットの反応の描写が薄め。この距離感が読みやすかった。そもそも主人公はダンジョン攻略自体に興味がないらしく、自身の強さや能力を把握していないようだ。他の冒険者より圧倒的に強いことだけはわかっているので、具体的な差がどれくらいで、今後どのように明らかになるのかが楽しみ。

しばらく日記を書き、午前9時から4時間ほど寝た。無事起床し購買に昨日間違って買ったラノベを持って行ったところ、書籍担当の店員がいないため来週月曜日に確認するということになったので、店に預けてきた。ちなみに自分が注文したラノベは棚に陳列されていた。およそ2年ぶりで2回目。まあ積んでいるシリーズの2巻なので、前回とは異なりほとんど気にならなかった。正しいほうも確認の必要があるため今日は買えなかった。

なんと店の棚に並べられていた。
週記（2022/10/03-2022/10/09） - kotatsugameの日記

思ったより時間が取られて学食で食事する暇がなくなった。慌てて帰宅し午後2時からUniversal Cup。今日は第3回目、Ukraineセット。

https://qoj.ac/contest/1714

書く

シャワーを浴びて食事し、午後9時からARC180に出た。これはオンサイトコンテストの予選でもある。

AtCoder Regular Contest 180 - AtCoder

Aは簡単。AAやBBはどうやっても消せないので、AとBが交互に現れる区間に区切ることができる。これらは長さを2ずつ減らせるだけなので答えが簡単に求まる。あとは掛け合わせれば元の問題も解けた。

Bで大変な目にあった。サンプル4の出力を手で試したところ、どうやら $P_l-P_r$ が小さいものを優先的に操作しているらしい。これを実装した。操作の候補を $P_l-P_r$ で順位づけて管理し、操作するたびに関係する箇所 $O(N)$ 個を更新する。操作が $O(N^2)$ 回であることに注意すると、pushが $O(N^3)$ 回、popが $O(N^2)$ 回行われる。

単に優先度付きキューを使う場合 $O(N^3\log N)$ で間に合わないが、popの際に $P_l-P_r=1,\dots,N-1$ を舐めることにすればpushは $O(1)$ になり、合計 $O(N^3)$ 。 $N\le 7$ くらいで愚直と比較し提出した。popでしくじって1TLEしつつ何とかAC。コンテスト開始から50分経過し、すでに200人通していてひっくり返った。

Cは順当に解けた。操作後の $A$ を固定したとき、それを達成するような最短・辞書順最小の列だけ数える。これは余計な操作をしないようにすれば作れる。累積和が $0$ になった箇所に注目すると、その直後の要素は操作によって変化しない。つまりそれが更新位置の末尾あるいは $A=0$ なら取り除いてよく、そうでない場合も選べる最も先頭に近いものを使うべき。

これで、現在選んだ要素の和を持つdpが可能になっている。コンテスト中はなぜか最初から $O(N\sum|A|)$ で書こうとして少し苦戦していたが、もう一つ $N$ をつけて次に選ぶ要素へ直接遷移すると簡単。

Dも見覚えのある考察。 $\max B$ が真ん中のブロックに入っていれば、それを限界まで伸ばすのが最適。そうでない場合左のブロックに入っている場合を考えると、今度は真ん中のブロックを幅1にすべきだから、 $\max B$ が左に入るような適切な $i$ に対する $A_i+\max\{A_{i+1},\dots,A_R\}$ の最小値を求める問題となる。オフラインなので $R$ を昇順に見ることができ、 $R$ から左方向に見た累積MAXとそれを使った区間ADD区間MINの遅延セグ木を管理することで取得できる。

何とか4完を確保し34位。無事決勝に進出できた。Bの想定解はわかってしまえばあっけなく、なぜ逆順列を考えなかったのか不思議でならない。600点だから観察から力押しで解けるだろうと考え、あんまり腰を据えて考察していなかった気がする。ランダムケースも非常に小さい範囲でしか試せていなかったので、もし勘を外していたら悪夢だったろう。

コードゴルフとしてAをNibblesで解いておいた。一つ置きにAとBを反転しランレングス圧縮する方法。反転の代わりに列 $1,2,\dots$ と足し合わせ、偶奇を見た。

www.youtube.com

「カミガカリ不自然言語処理殺人事件」を読了。「AIのべりすと文学賞」の受賞作。神託された犯罪事件の真相をもとに、人が詳しい経緯を調べたり証拠を集めたりするミステリで、神様の役割はAIのべりすとが担う。試みとして興味深いしAIの活用方法も非常に好みだった。生成された文章を一言一句正しいものとする事件が組み立ててあり、一見不自然な箇所にも非常に合理的な背景が用意されている。文章の細部まで大切に扱われていて良かった。

小説としても面白かった。中盤くらいまではとにかく陰鬱で、登場するキャラがみんな不気味で好きになれず、主人公に味方がいないように思えて窮屈だったが、そのあたりの事情も最終的には回収される。また後半で扱われた事件は設定の根幹にも絡んできて、ストーリーの構築に唸らされた。単なるアイディアだけの話ではないということ。

相変わらずSageMathで実験を回している。要素が $\mathbb{Z}$ の元であるような行列のランクや基底をなす行を求めているが、もしかしたら割り算ができる $\mathbb{Q}$ で計算したほうが高速なのかもしれない。そう思って少し書き換えたところ、なんと3倍速になった。うーん失敗。

しばらくラノベを読んで午前9時前に寝た。

06/30(日)

午後6時起床。「英雄ブランの人生計画」1巻と2巻を読了した。これで6月は1日1冊ペースで本を読めたことになる。

最強の冒険者の一角だった主人公が引退し、正体を隠して別名義で再度冒険者をする話。正体の隠し方が徹底されていて、雑用依頼ばかり受けているから戦闘能力は一切知られておらず、他の冒険者に絡まれて返り討ちにするといったテンプレシーンすら存在しない。一方で、周囲に雑用依頼を布教している部分はスローライフ的で良いなと思った。

急いで食事して午後9時からABC360。

AtCoder Beginner Contest 360 - AtCoder

Aはsed。Bは言われたとおりに実装。Cは各箱に対し最も重い荷物を管理して計算する。Dは左向きの蟻それぞれについて幅 $2T$ の区間に入っている右向きの蟻を数える。 $X-2T$ がオーバーフローする制約で、あまりのいやらしさにびっくりしていたが、実はちゃんとサンプルで落ちるようだ。……と思ったら右向きの蟻を固定したとき出てくる $X+2T$ のほうは落ちなかった。やっぱりいやらしい。Eは左から $2,\dots,N$ 番目にいる確率が一致するので、左端にいるかいないかの2状態でdpできる。

Fは $l$ を固定すると各区間に対して $r$ がどの範囲にあれば交差できるか求まるから、 $l$ をずらしつつ区間ADD区間MAX・argmax取得の遅延セグ木で逐一 $r$ を求めていけば解ける。 $l,r$ の候補は $L-1,L,L+1,R-1,R,R+1$ くらいなので、これらだけ集めて座圧すれば実現可能となる。ところが、座圧対象に $0$ を入れる必要があることには気づいていたが、 $1$ まで必要だとは思いもしなかった。嘘解法。

Gは通常のLISに加え操作を行ったかどうかを持ってdpする。操作する際はLISにおける直後の要素とまとめて遷移することにし、dpの更新タイミングを少し遅らせることで一つ前のdp配列の値を計算に使えるようにした。最初はLISの長さに対して末尾の値の最小値を持つdpを書いたが、これはdp配列の値が単調増加になることを使うから、操作を行った後のdpでも成り立つかわからない。

そこでmapを使い、末尾の値に対してLISの長さを持つことにした。最適でない値は逐一探して消していくことにする。このあたりの実装に手こずりつつ何とか書き上げるも、最初の提出はWA。よく見たら操作しないケースだったり操作する値がLISの末尾に来るケースだったりを考えていなかったので修正し、通した。実はまだ嘘解法で、dpの初期値的に $y=0$ での操作ができなくなってしまっている。