11/06(月)

午後3時起床。半からインターン先定例会に参加した。今週から時間が1時間早められ、午後3時半からになっている。

先週は少しコードを書いたので進捗報告で話すことがある。実は結果を見ていて気付いたことがあったのだがまだ調査していない。今週はもとから実装する予定だった機能を完成させ、それを使って調査するところまで進めたい。

勉強会は自動運転に関する未来予想。部屋がそのまま走るなど、まだSFとしか思えないもののロマンのある話だった。自分も自動運転技術には期待している。そもそも普通免許なんていう誰でも取れるような資格で車を走らせられること自体何かの間違いであり、300年ほど続いている車の歴史は徒歩・馬から別の安全な乗り物へ移行する過渡期に過ぎない、はず。

人間が運転することを一斉に止めれば、AIにそこまで依存しないルールベースでの自動運転も可能ではないか。道路・標識・信号機なども自動運転システム向けに調整してしまえばよい。一度現実社会にデプロイされてしまった物事なので、そうもいかないのが現実だが……。

質疑応答が盛り上がり長時間に渡ったが、そもそも定例会が早く始まったため、解散後に閉店前の購買に滑り込むことができた。ラノベ等を購入して学食で夕食を摂り帰宅。

あとは夜中までずっと先週の週記を書いていた。日付が変わる直前に投稿。今回はUniversal Cupまですべて埋めることができた。一体何週間ぶりだろうか。

非常に眠く、すぐ布団に入った。午前0時半就寝。

11/07(火)

午前6時くらいに目を覚まし、ラノベを読んでいた。

「許嫁が出来たと思ったら、その許嫁が学校で有名な『悪役令嬢』だったんだけど、どうすればいい？」3巻を読了。序盤の展開が重い……！あそこから人を集めてバスケの大会に出ようという気持ちにはならないと思うのだが、それはそれとして練習シーンは面白かった。スポーツとラブコメが高度に両立されていてどちらの点でも満足。肝心の大会シーンは次巻らしく楽しみである。

午後2時半から午後10時まではまた寝ていた。

先週出たDMOJのコンテスト期間が終了した。

Singularity Cup - DMOJ: Modern Online Judge

P1は $N!$ をvalueで割った値を最小化する。この値は整数であり、また順列全部を選ぶことで $N$ になるためオーバーフローするほど大きな値を考えなくてよくなる。またここから使わない要素が $O(\log N)$ 個であることも言えるので全探索可能。

P2は、文字列の先頭と末尾が等しいとき、末尾を削除した後任意の回数rotateして全体をreverseすることで操作が表現できる。もし隣接する2文字が同じ位置があるなら、rotateを調整してそれを文字列の先頭と末尾に持ってくることでまた操作できる。よって隣接する2文字が異なる位置の数（と1との最大値）が答え。最初の操作ができないケースに注意。

P3は二分探索してトポロジカルソート……と思ったらTLEが取れない。どうやら二分探索の $\log$ を付けてはいけないようだ。よく考えたら、 $C=0$ としてトポロジカルソートを始め、途中で行けるところがなくなったら $C$ をじわじわ増やせばよい。そのときこれまでの経路を捨てる必要はないから線形時間で答えが求まる。実際は最初に $D$ をソートしているが、その $\log$ はOKらしい。

P4は大変だった。まず $(r,c)\rightarrow(r-c,c)$ と変換した平面上で矩形領域の和を取る。このとき右端まで含めるようにすると階段領域と平行四辺形の和になるので、今度は $(r,c)\rightarrow(r,c-r)$ の変換で平行四辺形を矩形領域にしてキャンセルすればよい。2D BITを使うと空間計算量が $N(N+M)+M(N+M)$ になってMLEしない。

P5は最小流量制限付き最大流が思い浮かぶが制約が大きすぎる。飛ばした。P6は爆弾の上を覆う辺から右手法っぽく辿ってぐるっと一周したら消すみたいなことを頑張っていたが全然通らなかった。

4完24位でレートは2916→2880(-36)。

シャワーを浴びて午後11時半からCF #908 div.1に出た。

Dashboard - Codeforces Round 908 (Div. 1) - Codeforces

Aは、操作後の数列は $x$ の選び方によって複数考えられるが、操作すると $x$ が数列の末尾に来るので操作前の数列は高々一意。よって $b$ から操作前の数列に遷移するのを $k$ 回行えればよい。数列は常に $b$ のrotateになっているので、 $n$ 回遷移できたら必ずループに入っており、それ以上試さなくてよい。

BはLISを変化させないような構築が可能。自分は $a$ の累積MINを更新する点の直前に詰め込んだ。

Cは $\sum l\le\#X\le\sum r$ で、この幅が十分広ければ $a$ として存在しない値をサイズに選べてanti-beautyを0にできる。そうでない場合はサイズの全探索が可能。anti-beautyは $a=\#X$ となる要素を含む集合だけ見て算数をすれば求まるため、全体で $O(\sum n)$ になる。

Dは謎。結論から言えばいろんな貪欲が通る。自分は棚を順に見て、残っている個数が最も多い色のキューブを1個置く操作を繰り返した。棚 $(s,d)$ があったとき、基本的には1色につき $\lfloor s/d\rfloor$ 個置けて、そのうち $s\bmod d$ 色はもう1個置ける。この制限を違反しそうになったらスキップした。棚は $d$ の降順に見たが、ここは何でもいいらしい。

至るところで手間取り、4完遅めで75位。レートは3014→2958(-56)となった。Dは棚 $(s,d)$ を $\lfloor s/d\rfloor$ 個の $(d,d)$ と $(s\bmod d,s\bmod d)$ に分解することで、すべて $s=d$ であるようなケースに帰着できるようだ。これが多い色から置いていく貪欲で解けるのはわかりやすい。分解後の棚を見る順番は関係ないらしい。

www.youtube.com

DMOJのP5をupsolveした。最小流量制限付き最大流で通るらしい。ダメもとで試してみればよかった。 $O(N+M)$ 頂点 $O(NM)$ 辺だが、まともな計算量解析はあるのだろうか。

少し日記を書いた後はラノベを読んでいた。「依存したがる彼女は僕の部屋に入り浸る」を読了。連載初期から追っているハーメルンの書籍化である。非常に面白かった。

Web版ではこの依存というのはもっぱら酒・タバコ・ギャンブルなどへの話で、主人公とヒロインたちの間の感情はあまり表立って描かれていなかったという印象があり、変更されたタイトルや帯・あらすじにはそぐわないような気がしていた。しかし大量の加筆によってそういう話に仕立て上げられており違和感はなかった。Web版より話が分かりやすくて自分はむしろ好み。

syosetu.org

午前11時を回ったくらいに学食に行って昼食を摂った。帰宅して「三傑のサッカーは世界を揺らす！」を読了。面白かった。プロ入りどころか中学生の野良サッカーしかまだ描かれなかったが、ちょくちょく未来の話が挟まるのでわくわくしながら読めた。サッカーでは無名の公立高校に入学したところで1巻が終わったため、全国で活躍する機会はまだまだ遠そう。

早くサッカー選手として成り上がっていく話が読みたいと思いWeb版を探したら、高校生編の途中でエタりかけているようだった。これなら続刊を待ったほうが良いはず。仮に続刊しないことになってしまったなら……おそらくWeb版もエタるだろう。

1時間半ほどインターン関連のコーディングをして、また学習を回し始めた。2時間ほど回してから最大化すべき評価値を最小化しようとしていたことに気づきやり直しに。

スポーツ、特にサッカー系のネット小説を読みたい気分だったので、ハーメルンの捜索掲示板からなろうを1作見つけてきた。それを読みふけり、午後8時半就寝。

11/08(水)

消えた。

11/09(木)

午前2時起床。なろうを読み続けていた。

Yandex Cup Algorithm部門の決勝に招待された。マジか……。せっかくなのでできれば参加したいが、カザフスタンに行くという点、直前に修論題目の提出締め切り日がある点など懸念すべき要素もいくつかある。気力があるときに悩むことにして、今は放置。

Congratulations!
You have qualified for the Yandex Cup 2023 finals in the Algorithm category.

The finals will be held on December 2-3 in Almaty, Kazakhstan.
— こたつがめ (@kotatsugame_t) 2023年11月8日

午前7時半から4時間ほど二度寝していたらしい。OpenCupのSlackに通知が来ていることに気づき覗いたらYandex Cup決勝向けのチャンネルが作成されていた。そこで知ったが、決勝参加のフォーム回答期限がメール下部に白文字で書かれていたようだ。背景の黒塗りが途中で途切れており、その部分は背景色と同化して見えなかった。ヤバすぎる。

一昔前の個人サイトじゃないんだからさあ…… pic.twitter.com/IewWhVx93H
— こたつがめ (@kotatsugame_t) 2023年11月9日

回答期限は今日の午後11時までなので、今のうちに決める必要がある。日本人の決勝進出者は他に4人くらいいて、Slackを見た感じ結構カザフスタン行きに乗り気なようだ。行き帰りは揃って行動しようという話にもなっていたので、そのあたりの不安は払拭された。

指導教員の先生にも連絡を取った。この時にはもう行くことを決心していたので「是非とも参加したいがこの期間に何か予定はあるか」という文面のメールを送ったら、呆れた感じで止めても無駄だろうと返信が来た。心証が大変なことになっている気がするものの、構わず行く。決勝参加のフォームに回答した。

学食に行って昼食を摂ってから、明日のセミナーの準備を始めた。実は来週金曜日に別のセミナーで自分の研究成果を発表することになっていて、明日はその練習をする予定。しかし何一つ用意ができていない！まったくやる気が出ず、なろうにもかなりの時間を費やしてしまったが、午前10時くらいまでかけて何とか仮の発表スライドをでっち上げた。

テレビで「トランジスタ技術の圧縮」が映像化されることをTLで知った。これは宮内悠介さんの短編集「超動く家にて」の中の一編。よくわからない短編が多かった印象の本だが、その中でもこの短編だけはストレートな面白さがあったと記憶している。

✨情報公開③✨
第3弾は溝端淳平さん主演「トランジスタ技術の圧縮」。誰もが愛読する国民的雑誌「トランジスタ技術」を圧縮する話。普通ならそれっぽいあらすじをここに書くところだが、もはやこの字数では表せないので割愛することにした。いわゆる問題作なのである。#世にも奇妙な物語 #溝端淳平 pic.twitter.com/4dg2LQcmgN
— 「世にも奇妙な物語」公式アカウント✨😎 (@yonimo1990) 2023年10月25日

toragi.cqpub.co.jp

発表スライドを先生にメールで送ろうとしたら、午前7時過ぎに今週のセミナーをキャンセルするとのメールが入っていた。単に先生に急用が入ったからかもしれないが、前日までに準備が完了していない自分に愛想を尽かした可能性も否定できない。カザフスタン行きを強行したこともその疑念を強める。

なろう「やり直してもサッカー小僧」を読了。面白かった。主人公には最初明確な弱点があってハラハラしていたが、それがはっきり改善されていくと安心できた。主人公を擁する日本代表は攻撃的なチームというだけあって攻め筋をたくさん持っている。そのためリーグ戦もトーナメント戦もほぼ全部描いているのに1試合1試合違った展開になっていて、途中でだれることがなかった。

https://ncode.syosetu.com/n9987bi/

午前10時半就寝。

11/10(金)

午後2時半に気合いで起床。念のため登校してみたがやっぱりセミナーは休みだった。

院生室にいた同級生としばらく話し、整数論の人々は発表経験が豊富だと教えてもらった。そこで来週の発表についてアドバイスを貰おうと思い、その分野の院生室に行ってみたが、残念ながら人がいなかったのでそのまま帰宅した。

しばらく日記を書いていたが眠すぎる。早々に布団に倒れこんで午後7時過ぎに寝た。今日のyukicoderは出なくていい回。

11/11(土)

午前2時起床。

ラノベ「君の先生でもヒロインになれますか？」を読んだ。年齢差のある半同棲ラブコメは初めて。年齢差のほうが主題になっているようで、主人公も大人っぽく描かれていたように思う。グイグイ行く性格はちょっと性に合わないかもしれない。同級生のヒロインとの2枚体制かと思っていたら、1巻ラストですでに先生とゴールインしかねない勢いで仲を確かめ合っていて驚いた。

午前7時半から正午くらいまで二度寝していた。食事とシャワーを済ませて午後2時からUniversal Cup 9回目、Qinhuangdaoセット。

The 2nd Universal Cup. Stage 9: Qinhuangdao - Dashboard - Contest - QOJ.ac

チームでAGJFBIDMCEを解き、10完14位。自分はGICを解いた。

AGJは簡単枠。Gは列の途中を飛ばしても得しない。気づかずにセグ木を使ってdpしてしまった。その後Fもすぐ通り、そこからNyaanさんのBとrisujirohさんのDがどちらも詰まって大変なことになった。それ以外に解かれている問題がなかったので自分はとりあえず読まれていない問題を読み、Iに取り組むことにした。

Iは操作Cをまとめ、 $t$ 回引き算した後の $x$ 番目を求める問題を解く。 $k$ で割った商とあまりで2回二分探索するのが基本方針。まず初めに、 $t$ 回以下の操作で $\max a\lt Qk+k$ となる最小の $Q$ を求めた。 $a\ge Qk$ なる $a$ に対し個数と $\lfloor a/k\rfloor$ の総和が分かれば二分探索の判定ができる。

$\max a\lt Qk+k$ となった瞬間の残りの操作回数を $t'$ とおく。この時点で $a\ge Qk$ なる $a$ はすべて $Qk+(a\bmod k)$ になっている。それを降順に $R_1,\dots,R_r$ とすると $r\gt t'$ 。もし $r\ge t'+x$ なら $R_{t'+x}$ が答え。

そうでない場合、 $Qk-k\le a\lt Qk$ なる $a$ を $L_1,\dots,L_l$ として、 $x\gt l+r$ ならもともとの $a$ で $x$ 番目に大きな要素が答え。どちらでもない場合、 $L_1,\dots,L_l,R_1-k,\dots,R_{t'}-k$ のうち $x-(r-t')$ 番目に大きな要素が答えとなる。

クエリを $Q$ の降順に見ると $R\bmod k$ をBITで管理できるから、最初のパターンはBIT上の二分探索で答えられる。2番目のパターンは簡単。3番目のパターンについては答えを二分探索する。BITで個数を取得する際に $t'$ とのMINを取ることで、 $R_{t'+1}$ 以降の要素の寄与を取り除ける。 $L$ は $a$ をソートしたものの連続部分列になっている。以上で $\log$ 二つで解けた。

最初 $t+x-1$ 回引き算してから最大値を取ればよいと思っていたら、実装してからサンプル1すら合わないことに気づいてひっくり返った。ちゃんと修正できて良かった。TLEが怖かったので $Q$ を求めるのに並列二分探索を使いセグ木の $\log$ をソートの $\log$ にしたが、結局2回目の二分探索が重いので無意味。

次はC問題。まずコストを求めることを考えると、文字列の両端からprefixがsuffixの反転と一致する限り取ってよいことが分かる。これはSA+LCPで解ける。そうやって残った区間において、左端または右端に接した最長の回文をさらに取り出し、残ったものが削除すべき区間となる。こちらはmanacherの結果を見つつ全クエリまとめて平面走査っぽい感じで頑張れば解ける。

あとはそのコストを達成するような区間の選び方を数える。上の方法で区間の例を一つ見つけたら、それをprefixあるいはsuffixに食い込むようにずらしていっても残った回文の中心が変わらないとrisujirohさんに指摘された。よってその半径が分かればOK。偶数長の回文や添え字・算数のoff-by-oneを考えるのはかなり辛かったが、書き上がったら一発でサンプルが合った。 $m$ の桁を間違えていて1REしつつAC。

あとはEの応援をしつつLの話を聞いていた。結局5分遅れで通って残念。

感想戦。Aは順位表を見てギャグだと知ったとのこと。Jは集合を一つずつ決めていく3¹³で解いたらしいが、一つずつ追加しても解けるので13×2¹³になると指摘した。Fは1、そのまま、偶数に変える、奇数に変えるの4状態でdp。適切な素数が常に存在することは3人で考えても示せなかった。後からTLで双子素数を含むから実験するしかないと聞き納得。

Bは話を聞く限りこのタイミングで通るとは思えない問題だった。Stern-Brocot treeにおいて $(a,b)$ と $(c,d)$ の間に $(a+c,b+d)$ があるとき、 $(A,B)=(a+c,b+c)$ によって生成される文字列が $(A,B)=(a,b),(c,d)$ で生成される文字列を連結したものに一致するらしい。これを使って文字列を小さいパターンの繰り返しに分解し、部分列dpを行列で書くと解ける。

DはUniversal Cup 3回目のL問題に帰着してしまってWAが出ていたようだ。まあMAXとMINが違うからそれはそうかな……という気持ちになった。最終的に謎の貪欲で通したらしい。

MとEはNyaanさん。Mは木dpできると思ったらできたらしい。Eは実装を頑張る問題で、頑張っていただいた。ブラシの位置 $2^n$ 通りで状態が表せて、遷移するときにブラシの位置を固定してから遷移先を探すのではなく遷移先を探しながら固定していくと高速になったそうだ。

Lはrisujirohさん。順列の長さ $k$ を固定したとき、そのような連続部分列を新たに作れる操作は定数個しかなく、壊してしまう操作はおおむね $\min(p_i,p_j)\le k\lt\max(p_i,p_j)$ で判定できる。あとはそれらを線形RMQやバケットソートを使い線形時間で実装する問題だった。

午後9時の15分前に解散。すぐABC328に出た。

Toyota Programming Contest 2023#7（AtCoder Beginner Contest 328） - AtCoder

Aはよい。Bは一瞬 $i$ 月 $i$ 日を数えそうになった。冷静になり、文字列に変換してチェック。Cは完全に既出だったはず。off-by-oneに気を付けなければならないが、適当に書いたら一発で合ってビビった。Dはstackで貪欲にやってよい。Eはdfsで全域木を全探索した。計算量を見積もっていなかったのでサンプル3に最大ケースがあって助かった。Fは重み付きUF。

GはTL 2.8sec・ML 512MBでどちらも標準と異なる。特にMLが調整されているのはAtCoderでは非常に珍しい。問題自体は簡単。 $A$ を順列 $P$ に従って並べ替えると $\sum_i|A_{P_i}-B_i|+C\times\#\{i\mid P_{i}+1\ne P_{i+1}\}$ がコストになるので、bitDPで解ける。 $P$ の最新の要素が必要なため状態数 $O(N2^N)$ 、遷移 $O(N)$ 。実装してからこれを落とすためのMLだということに気づいた。

各状態に対しコストの最小値を達成する $P$ の最新の要素だけ管理するといいのではないかと思ったが落ちた。ハックケースはすぐにはわからないものの、ダメだと言われればそれはそうかという気持ちになる。 $P$ のうち連番になっている部分を一度に遷移すると状態数 $O(2^N)$ 、遷移 $O(N^2)$ になることに気づいて提出し、実装ミスによるWAをもう一つ挟んで何とかACした。

29位。575点でこんなに苦労していてはお話にならない。Gは長い連番で遷移できる状態数が少ないため、実は計算量 $O(N2^N)$ になっているとのこと。

www.youtube.com

コードゴルフはA、B、D。AはNibblesで、 $S\le X$ を $\lfloor X/S\rfloor$ で実装するテク。BもNibbles。10進展開なんてしなくてもpでshowすればよい。DはPerl。毎回s/ABC//するのは当然TLEだが、s/ABC$//とすると間に合った。パターンに$が指定されたとき用の高速化でも実装されているのだろうか。

生活リズムが前にずれている。布団に入ってカクヨムを読み、午前2時前には寝落ちしていた。

11/12(日)

午前6時起床。今日は珍しく出る予定のコンテストが一つもない。夜中まで起きている必要もないため、この時間から起き出して夜までずっと日記を書いていた。その間にポツポツ別のこともやっていたため、日記にはそちらを書いておく。

DMOJで微妙に手こずったので2次元BITを整備した。このくらいならその場で書けなくもないが、整備するとしたら今がいい機会。ついでに元からあるBITが1-indexedだったのを0-indexedに揃えておいた。

0-indexedにすると言っても、結局添え字は1-indexedで扱うことになる。このとき配列長を $N+1$ にするかアクセス時に1引く必要があるが、後者のほうがメモリ使用量はもちろんのこと速度的にも良いらしい。DMOJのP4に提出して確かめたら100msくらい差がついていた。実際ACLも1引く方法で実装している。

library/datastructure/BIT_2D.cpp at ca16f62e4ac97705abd820861b4af810dc243301 · kotatsugame/library · GitHub

MHC Tシャツがもう注文できるらしい。まだメールは届いていないが、MHCのプロフィールページからショップに飛べたので自分も注文しておいた。期限は12/15のようだ。

午後1時半から午後4時くらいまでインターン関連のコーディングを行っていた。学習結果のビジュアライザを整備して試しにいくつか表示させてみたら、lossなどの数値だけ見て考えていたより全然うまくいっていなくて愕然とした。精度評価の指標を何か考える必要がありそう。

昨日のUC-Dを自分の解法で通した。選んだ $k$ 日のうち最小の日付だけがクーポンによる割引に影響する。このことから、 $a$ が小さいほうから $k$ 日選ぶか、 $k-1$ 日だけ選んで最後により早い日付の日を選ぶのが最適。前者は簡単。後者は最後に選んだ日にしかクーポンを使わないとしてよいので、使えるクーポンを全部使った場合の $a$ を見ればわかる。

少しラノベを読んで、午後7時くらいに寝落ちした。

kotatsugameの日記

週記（2023/11/06-2023/11/12）