10/02(月)

午前4時半に目を覚ました。当然眠気は取れていないが、すぐ二度寝する気にもならない。スマホを弄って無為に過ごすよりはと思って本を読んだ。

「探偵は友人ではない」を読了。久しぶりに読んだまったりした日常の謎で良かった。ただ数学で上手いことを言おうとして失敗していたのは残念。「 $a\div 0$ 」という式は $a=x\times 0$ を解いているわけではないので、 $a=0$ なら答えが無限にあるとかそういうことはない、はず。オチにこれが来て冷めてしまった。

午前9時から午後1時まで二度寝した。閉店する前までに購買に行きたいなと思っていたが、冷静になるともう夏休み期間が終了したので閉店時間は午後3時より遅くなっている。調べたらなんと午後6時半まで開いているらしかったので、思う存分布団でゴロゴロしていた。

午後4時前に布団から出て、購買まで往復しラノベやパンを買ってきた。食事して半からインターン先定例会に出た。

先週は木曜日に1on1をした後断続的に実験を回していた。ちょっとコードを弄って数時間放置するのを繰り返すだけなので日記には書きにくいが、ちゃんと進捗が存在する。それを報告した。今週も同じ感じになるだろう。

勉強会は最小二乗法について。外れ値を除外するのにロバスト推定、特にM推定と呼ばれる手法が紹介された。用意したモデルでうまく説明できないデータに対しほぼ0の重みを割り当てて無視する、という手法に見えてかなり乱暴な方法だと感じてしまった。

その後はずっと先週の週記を書いていた。日付が変わる直前に投稿したが肝心のオンサイト部分が穴あきだらけ。強い眠気にやられて書き足す間もなく布団に倒れこみ、寝た。午前0時半ごろだった。

10/03(火)

今日もまた午前4時半に目を覚ました。ラノベ「灰の世界は神の眼で彩づく」2巻を読了。この巻は主人公のステータスが順調に上がっていくだけであまり面白くなかった。インフレ具合からもうそろそろ人類最強になりそうな感じがするし、いいところで話が終わっているので、次巻は少し楽しみである。

午前8時から午後2時半くらいまでは寝ていたはず。起きてからノクターンノベルズを二つ読んだ。正確には他にもいくつか拾い読みした作品があったはず。

https://novel18.syosetu.com/n8676ik/

https://novel18.syosetu.com/n7469ik/

午後8時前に寝た。この日は一日中布団の上にいた。

10/04(水)

午前3時起床。ラノベ「「キスなんてできないでしょ？」と挑発する生意気な幼馴染をわからせてやったら、予想以上にデレた」2巻を読んだ。1巻よりスキンシップが激しかった気がする。もう今にも一線を超えそうな危うさがあるが、悪いことではない。ヒロインが「他の女の子にはマフラーごと貸すのに私には半分しか貸してくれない」と言いつつ主人公とマフラーをシェアしていたのが面白かった。

その後もしばらくラノベを読んで午前9時から3時間ほど寝た。起きて登校し、ホスフィンと会って昼食を摂った後、図書室で教科書を返却し新しいものを借りた。

帰ってきてから後期の履修を考えた。もともと基礎論の集中講義を一つ取るつもりだったが、念のため入れておいた前期の講義で無事単位が出て卒業要件は満たされ、その上で考えると今そこまで興味があるわけでもないことに気づいたので、止めにした。今期はセミナー以外何もなし。

今年の履修計画を見直した。集中講義を二つ取って卒業要件をピッタリ満たすというのは流石に危ういと感じ、講義を一つ追加した。
週記（2023/04/17-2023/04/23） - kotatsugameの日記

これまで続けていた時間割ツイートの前期の分をしていなかったので、このタイミングで単位の集計だけしておいた。カウントしていないものの、実は通年の必修単位であるセミナー（と課題研究）の評価もすでに出ている。なぜ半年分だけで評価を付けられているのか意味不明だが面倒なので特に何も言っていない。

M2春学期
単位取得状況 4/4
単位取得率 100%
最低限の記録だけ……
— こたつがめ (@kotatsugame_t) 2023年10月4日

ラノベ「凶乱令嬢ニア・リストン」3巻を読了。2巻にイラストページがなく不穏に思っていたが、この3巻でイラストレーターが交代していた。体調不良だったらしい。内容としては主人公の目立つ活躍がなかったのがちょっと残念。4巻の発売が決定していて、巻末の広告では主人公が大暴れするらしきことが書いてあるものの、本編で自身の幼さをかなり自覚しているようだから、不自然なほどの力を見せつけ目立つといったことはもうそうそうないのだろうなと思った。

布団に入り、しばらくスマホを弄って寝落ち。午後8時くらいだった。

10/05(木)

午前3時半起床。しばらく日記を書いた後、昼過ぎまでかけてセミナー準備をした。先週示した等式について話す。後々あると便利だろうと思って、今回は手書きではなくLaTeXで原稿を用意した。

今日はチュウニズムの日替わりボーナスがデュエルクリティカル確定なので、来週までのデュエルを終わらせにゲーセンに行きたい。ひと眠りしてから行くか迷ったが、うっかり夜遅くまで寝てしまうとまずいと思って今から行くことにした。シャワーを浴びて午後2時くらいに出発。久しぶりに自転車に乗ろうとしたらギアからガタガタ異音がし、危険に感じて地下鉄で向かうことにした。

まず久しぶりの大戸屋で昼食。今日はいつも追加しているほうれん草の胡麻和えではなく麦みそ汁を頼んでみた。かなり美味しかったし野菜の量としても申し分ない。

食事 pic.twitter.com/71divDNPp9
— こたつがめ (@kotatsugame_t) 2023年10月5日

午後3時から4時間くらいゲーセンで遊んだ。チュウニズムデュエルは無事終わらせることができた。また今日はAJ埋めもしていた。

Jack-the-Ripper◆
Guilty ULT
Therapeutic Hoedown
Tango Rouge pic.twitter.com/y1CxoLkvMp
— こたつがめ (@kotatsugame_t) 2023年10月5日

Nijirate Fanatics

これで14全AJ！！！！！ pic.twitter.com/4EGwWZRayr
— こたつがめ (@kotatsugame_t) 2023年10月5日

14で未AJのまま残っていた5譜面を一気に終わらせることができた。「Jack-the-Ripper◆」「Therapeutic Hoedown」「Nijirate Fanatics」は数回連奏したらすぐ終わった。「Tango Rouge」はお祈りしながらひたすら連奏。37小節のタップスライドは直前の手の位置が悪いため意識しないと絶対にアタックが出る。今日は終盤の勝率が高くて助かった。

「Guilty」のULTはやはり最後が鬼門だった。直前まで交互で取って左左右右左左とするのは、2連打への心構えができず全く通らない。直前を左手で擦って右右左左右右と入れ替えてみたら余裕ができて安定した。91小節はかなり速めに擦るとよい。

「Dreadnought」も出た。一発。ちょっと赤が多かったのは残念だが、さて次にAJが出るのはいつになるだろうか……。

Dreadnought AJ pic.twitter.com/hHUQlbaTZt
— こたつがめ (@kotatsugame_t) 2023年10月5日

昼食が遅かったので、夕食の前に本屋に入った。2冊購入。最近YouTube shortsで紹介動画を見て気になっていた「ぎんなみ商店街の事件簿」は残念ながら在庫がなかった。

つけ麺を食べて帰宅。シャワーを浴びて午後10時くらいに寝た。

10/06(金)

午前5時に目を覚まし、昼前まで布団の上でラノベや一昨日借りてきた教科書を読んでいた。昼前に原付で登校。思ったより寒くてTシャツを長袖にしただけでは足りず、パーカーも着て行った。

院生室に顔を出して久しぶりに同級生と少し話した後、指導教員の先生と留学生と待ち合わせて昼食を摂った。そのまま教室に移動して午後1時からセミナー開始。

まず2時間は留学生による論文の発表だった。存在は知っていてもちゃんと読んだことがなかったので助かる。今日は途中の全単射の説明があいまいだったのを突っ込むうちに終わった。英語が聞き取れなかっただけだろうか？しかし全単射の証明は全射性と単射性をそれぞれ言うか、慣れているなら逆写像を定義するか、いずれにせよテンプレがあると思っていて、それに従っていない時点で信頼度は低くなる。

30分ほど進学予定の学生によるオンラインでの発表があり、次に次回のセミナーまでに留学生が何をするか話し合った。

最後に自分の発表だが、予定していた時間より短くなったので、証明を用意してきた等式のシチュエーションだけ話して終わりにした。これは留学生が出席していなかった先々週のセミナーの内容である。自分の英語がボロボロで大変だった。残念ながらあまり伝わっているとは思えない。

午後5時くらいに4限を終えた1年生がやってきて、セミナーの日程などをすり合わせた後全員で夕食のため学食に行った。いろんな学食を知っていると良いだろうと思いけやきダイニングを提案したが、いつの間にか夜営業がなくなっていて、仕方なくいつもの理薬食堂になった。

午後6時半くらいに解散。強風に煽られつつ帰宅した。帰り道ではATMに寄り、まとめて振り込まれたICPCの旅費を分割してチームメンバーに送金した。

結構眠くてTLを見ながらずっとダラダラしていた。コンテスト前に仮眠を取るほどの時間的余裕もなくなってしまった。何とかシャワーだけ浴びて午後9時20分からyukicoder 407。

yukicoder contest 407 - yukicoder

A、Bはよい。Cは問題文をよく読まずに書き始めたら求めるものが違っていてちょっと手間取った。次にDを読んで、しばらく考えても解けなかったのでEに移った。

$N\ge 3$ のケースだけ考える。まず $A_1=\min_j \mathrm{lcm}(A_1,B_j)$ を求めつついくつかの $B_j$ を特定し、そのうちの十分大きな素数 $P$ を使って $A$ を決める。 $P$ としては $3P\gt N$ なるものが必ず取れるようなので、 $1$ と $P$ 、 $2$ と $2P$ 以外は確実に決まる。 $1$ と $P$ の区別は $B_j\ne P,2P$ とのLCMを計算すれば良いので高々2手で求まる。こうして得られた $1$ を使って残った $B$ を全部求め、最後に1手で $2$ と $2P$ を区別すればよい。

クエリ回数を見積もると $N+N-1+2+N-1+1=3N+1$ となるが、実は $2P\gt N$ なる $P$ が取れないケースは $(N,A_1)=(4,3),(6,5),(10,7)$ のみらしく、この場合どれも最初の $N$ 手でほとんどの $B$ が特定できるため、最後に $B$ を求める部分には $N-1$ 手もかからない。 $2P\gt N$ なる $P$ が取れればそれを使うことで最後の1手が削れる。よってどちらもOK。

コンテスト中はここまで考えておらず、いろんなところを乱択して1手ごまかしたつもりになっていた。ところがそもそも $B_j$ の特定部分を $\mathrm{lcm}(A_1,B_j)/A_1$ としていて大嘘だった。

Fは簡単。素因数ごとに分解するとその素数をできるだけ含まないようにパスを取ればよく、dijkstraになる。

Dに戻ってきたら選んだ $A$ のMINと $B$ のMINを決め打つ発想が出て解けた。要素の選び方としてはある値以上のものを全部使うという形しかないため、これで $S_A$ と $S_B$ を全通り試したことになる。すると残る $C$ の要素ごとの寄与がわかるので、どの値まで使うか算数で求め、前計算したテーブルを引けばよい。

solved数を見てHに進んだ。各 $S_j$ をマスごとにバラしてスコアを考えると、各列から1マス選んだときの値の積に、そのマス配置が出現するような場合の数を掛けたものの総和が答えだとわかる。全部積なので行ごとに分解することができて、 $j$ マス選ぶとしたときの寄与を使う遷移のdpがしたくなる。畳み込みだから遷移さえ求まれば $O(HW\log W)$ になる。

マスの選び方は多項係数で処理できるから、問題は和が $A$ 以上 $B$ 以下の非負整数列すべてに対する先頭 $j$ 項の積の和を求めることに帰着された。 $A=0$ の時に解ければよい。まず非負整数列の数は重複組み合わせ、ボールとしきりの解釈で $\binom{B+W}{W}$ になっている。

先頭 $j$ 項の積は積の和典型で、先頭の項に対応するボールから1個ずつ選ぶ場合の数だと思うと、二つ合わせて $\binom{B+W}{W+j}$ だとわかる。 $B$ は非常に大きいが、 $j=0$ での値を $O(W)$ で求めてからずらしていくと $j=0\dots W$ に対する値を $O(W)$ で列挙できる。これで解けた。

残り8分半でGが解けるわけもなく、7完5位。ロスタイム17分で通した。

解法自体は結構簡単。 $A$ が全部 $0$ の場合と全部 $2^{30}-1$ の場合に操作をシミュレートしておけば任意の値に対する結果が分かる。これを見ながら桁dpすると $A=0\dots M_i$ に対する操作後のpopcountの分布が求まる。popcountは高々30なので、これまでのMAXを持ちながらdpすればよい。

シミュレート部分で遅延セグ木を60本持ったらTLE。bitごと・初期値0と1で分けていたので初期値2通りをpairで持つようにしたら2550msで通った。

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

10/07(土)

午前9時起床。

ラノベ「富豪令嬢」を読了した。財力を振りかざすシーンではほとんど嫌味を言っているのと変わらないようなセリフが散見されたが、主人公の設定もかなりきらきらしいので、そこまで嫌悪感なく受け入れられるくらいの説得力がある。そこさえ乗り越えれば、札束とパトロンとして培ったコネで何でもかんでも殴っていく展開はかなり爽快だった。

R-18のハーメルン「遊戯王　奴隷ヒロイン争奪ゲーム」を読了。グロの方向で過激な描写があったり、設定がいまいちよくわからなかったりするが、なんだかんだ読み進めてしまった。

https://syosetu.org/novel/325325/

正午からまた寝ていたらしい。目覚ましで起きたらちょうど午後2時だった。慌てて飛び起きてUniversal Cupに参加。今日は4回目、Taipeiセットだった。

書く

感想戦後、食事して午後9時からABC323。

UNIQUE VISION Programming Contest 2023 Autumn(AtCoder Beginner Contest 323) - AtCoder

A、Bはよい。Cは自分以外の最大値を求めたり残っている問題を列挙したりと微妙に面倒。この問題を解いている最中に手元を撮影しているWebカメラの接続が切れて、復帰させるため数分格闘していた。Dは小さなスライムから貪欲にマージしていく。mapで何匹いるか管理。Eはdp。

Fは荷物を一旦迂回して押せる位置に行かなければならないケースに気づき、他にも無限にコーナーケースがありそうだなと思って紛れの少ない解法を選択した。つまり、各地点の周囲数行・数列だけ取り出し座圧したグリッドの上でdijkstraをする。そのグリッドの上で荷物と高橋君が隣り合っていたとしても元のグリッドでは10¹⁷マスくらい離れているかもしれないが、周囲を広めに取り出しておけば気にせず実装してよい。

Gは解けなかった。行列木定理のラプラシアン行列に多項式を持たせると良いのではと思い、とりあえず $\bmod{x^N}$ として掃き出し法を愚直に行ってみたところ、答えは合うらしい。そこから各要素が1次式であることを使って高速化できないか考えていたがダメだった。掃き出し法をするうちにすぐ高次の項が現れてしまう。

また「行列式 FPS」で検索したらNyaanさんのライブラリが出てきて、それを参考に多項式補間を書いたが、 $O(N^4)$ なので当然間に合わなかった。手元で28秒くらいかかっていた。

多項式行列の行列式 | Nyaan’s Library

6完32位。Fは実は気づいたもの意外にコーナーケースなど存在しなかったらしい。速い人はみんな場合分けで解いていてびっくりした。

Dはmapを舐めている途中に要素を追加したくなる。迂闊なことをするとイテレータが無効化されると思い、事前に入っていなかった値はスキップするという実装をしたが、リファレンスを見るとinsertは既存のイテレータを無効化しないらしいので気にしなくてよかった。ただしmapのサイズに $\log$ がついてオーダーが悪化する。

map::insert - cpprefjp C++日本語リファレンス

コードゴルフはAとBで、両方Nibbles。Aはstepに負の数を渡すことで後ろから取れるらしい。これで偶数indexの文字だけ取り出した後は、MAXを取って文字コードの偶奇で出力を制御した。Bは入力の各行をソートすると辞書順が勝ち数の大小と一致してくれる。そこから自分はindexとzipしてソートしたが、group byを使う方法で4Bも縮められた。上手い。

Webカメラを復帰させている最中に映ってはいけない情報が映り込んだので、一瞬だけぼかし処理を入れることにした。エンコードを待って動画を投稿。動画内でMHCの話を散々していたのに、公開はその直前となってしまった。

www.youtube.com

午前2時からMHC Round 1に参加した。

Meta Hacker Cup - 2023 - Round 1

Aは両端のグループのサイズを2か3として探索すればよい。問題文が読みづらかった。この問題への提出は無事行えたが、その後B問題のvalidationをしようとしたらエラーが出るように。そのうち全問題でサンプルが表示されない、validationもできないという状態に陥ってしまった。これは1時間ほど続いた。

問題だけは見られたので、提出できない間に解いていった。Bは前計算。B1だけ通るようなコードを書く理由はない。Cは先頭から見るとどのボタンを押すか一意に定まる。これでC1は解けて、C2はこの「一意に定まる」という性質から新たに押されたボタンをキャンセルするように操作をflipするべきとわかるのでOK。Dは遅延セグ木。

Eは解けなかった。他の問題への提出作業を終えた後もしばらく考えていたがわからず、午前4時くらいに布団に倒れこんで寝落ちした。本当は30分ほどの仮眠の予定だったのに起きられなかった。

実は提出ができない間にR-18のハーメルンを1作読んでいた。「異世界(現代)パコTuber」。AI生成の挿絵があって特徴的。まあ別にいらないかなとは思う。知らない原作のキャラが扱われている間は良かったものの、知っている原作が出てくると辛い。

https://syosetu.org/novel/319409/

10/08(日)

午前8時起床。MHC R1はちゃんと提出したものが全部通っており、68点でピッタリ100位だった。システムトラブルがあったので1問でも通ればR2進出ということになっていたらしい。

昼過ぎまで日記を書き、少し本を読んで午後3時から午後5時半まで寝ていた。起きて食事し、午後6時からCF #902 div.1。

Dashboard - Codeforces Round 902 (Div. 1, based on COMPFEST 15 - Final Round) - Codeforces

Aは当然コストが軽いものから使いたい気持ちになり、コスト $p$ を1回以上支払う方法がすべてvalidであることは簡単に確かめられる。Bは適当にタイブレークをつけて最大値が $a_i$ となる選び方を数え上げる。前計算でどのindexを選ぶと最大値がいくつ以上になるか求めておくと、それがちょうど $a_i$ であるものの個数と $a_i$ 未満であるものの個数から計算できる。

Cは $i\rightarrow a_i$ という辺を張って考えると「印をつける頂点は印をつけない頂点からの辺を持つ」「印をつけない頂点は印をつける頂点への辺を持つ」という条件になる。この事実を使うとfunctional graphのループ以外の部分は一意に定められて、あとはループだけ考える問題になる。ただしいくつかの頂点は印をつけない頂点からの辺を持っていて、すでに印をつけることが確定している。

あるループにそのように確定した頂点が含まれる場合、未確定の頂点に印をつける・つけないを交互に割り当てると条件を満たす。含まれない場合、長さが偶数なら交互に割り当ててよく、奇数の場合はどうやっても不可能。以上で印をつける頂点の集合が決定。具体的な解は印を付けなかった頂点に対する $a$ を前から順番に選ぶことで構成できる。

Dは面白かった。まずimbalancedの条件は「同じ値を持つ要素の色が交互になっている」と書き換えられる。よって値ごとに二通りの塗り方が存在するが、これが完全に逆になっている塗り分けは色が完全に反転しているから、もし色ごとに分けた列が異なるならどちらか片方のみが辞書順の条件を満たす。

よって二つの列が完全に一致する塗り方を数え上げる問題になった。一致する場合対応する要素のペアが決定し、それぞれで前・後ろどちらの要素を青く塗るか決めることになる。この対応を区間と見たとき、まず包含関係があると求める塗り方は存在しない。

そうでないとき、区間が交差していると塗り方を揃えなければならず、また当然値が同じペアもそうである。この二つの関係だけが制約になっており、最終的な自由度は連結成分数に他ならない。よってUFで計算できる。

Eはまずすべての辺の向きが決まった状態で解いた。同じ色になるべき辺をUFで繋ぐことにする。例えばすぐわかるものでは、同じ頂点に入ってくる辺はすべて同じ色でなければならない。これを拡張すると、向かい合う向きの辺でその間のパスが正しい括弧列みたいになっているものが同じ色になるとわかる。これはパスしか考えていないが十分条件。辺を往復するとstackの状況が復元されるので、walkもパスのケースに帰着できる。

パスをLCAで折って考えると、ある頂点から根に向かって進みつつ順方向の辺を開き括弧として括弧列を作り、ある頂点で合流したとき余った括弧の数が等しい2点（から親に向かう辺）をUFで繋ぐとよいことがわかる。あとは括弧列が完結した場合も処理する。余った括弧の数に対し辺をmapで持つとマージテクが適用できるので、これで解けた。

この解法を見ると、根に向かう辺が多ければ多いほどUFに追加する辺も多くなりそうな感じがする。よってそのような辺の数を最小化するように根を選び、無向辺には根から遠ざかる向きを割り当てれば良いだろうとエスパーしてみた。根を選ぶのは木上のimosなりなんなりでできて、あとは先ほど述べたアルゴリズムを実装。提出したらなんと通ってびっくりした。

Fには歯が立たなかった。「どの魚を最後に選んだ」「これまで何匹選んだ」「最後に選んだのはオス・メス」という情報から次に選ぶ魚のサイズが決まると分かったので、試しに $O(nk)$ 状態のdpをmapで書いて提出したが、当然のようにTLE。実は状態数が少ないとかそういうことはないらしい。

結果はARC後に確認した。システスも全部通ってなんと3位。レートは2887→3095(+208)でhighestとなった。

午後9時からARC166に出た。

AtCoder Regular Contest 166 - AtCoder

Aはまず $Y$ にある文字Cで区切って考える。すると $Y$ をAB文字列とすることができて、 $X$ のCを何文字ずつAとBに振り分けるか決まる。操作3は文字Aを一つ右にずらす操作だから、Aに置き換えるCは左から貪欲に選ぶのが最適。これで実際に変換した後、操作3で一致させられるか判定すればよい。

Bは、 $a,b,c$ の倍数がこの順に並ぶとしたら、 $b$ の倍数の位置を固定し、 $a$ と $c$ については左右それぞれ累積MINを使うことで操作回数の最小値が求まる。これを $3!$ 通り、さらに $a$ の倍数と $b$ の倍数が同じ位置に現れるケースなども全部列挙して同様に解いた。

Cはグリッドの辺を互いに独立な折れ線に分割するのが瞬時に見えて良かった。場合の数は折れ線の長さを持つdpで求まるので、前計算しておく。これの適当な値の積を取れば答えになり、それは累積積と累乗で書ける。前者はこれまた前計算しておける。

Dは答えを二分探索した。左から順に見て、区間をできるだけ左に押し付けるように、またこれまで作った区間を伸ばして使いまわすようにしつつ構築する。区間を右に伸ばすのは無制限に行えるが縮めることはできない。過剰に覆われる点が発生したらその時点でアウトとした。答えが10⁹以上になる場合すべての区間が左端または右端を含むようになるので、最大値が存在しなくなる。

Eは大変。 $\left(\lfloor R/a\rfloor-\lfloor R/b\rfloor\right)-\left(\lfloor(L-1)/a\rfloor-\lfloor(L-1)/b\rfloor\right)=n$ と見る。 $\lfloor\ast/a\rfloor-\lfloor\ast/b\rfloor$ が1ずつ変化するため良い組は必ず存在すると言えるようだ。同じ値を取るなら $R$ はより大きく、 $L-1$ はより小さくなると嬉しい。値がインクリメントされるのは $a$ の倍数のときなので、 $L-1$ と $R+1$ が $a$ の倍数になることが言える。

そこで $L-1=la$ 、 $R+1=ra$ とおくことができ、 $t:=r-l$ を最大化する問題になる。条件は $f(t,l):=(r-1-\lfloor(ra-1)/b\rfloor)-(l-\lfloor la/b\rfloor)=t-1-\lfloor(la+ta-1)/b\rfloor+\lfloor la/b\rfloor$ として、 $f(t,l)=n$ となる $l$ が存在すること。ここで区間は $ab$ だけずらすことができるので、 $0\le l\lt b$ としてよい。

式の形から $f(t,\ast)$ は1ずれた2種類の値しか取らず、またそれらの値は $t$ に関して広義単調増加ということが言える。そこで条件を $\min_l f(t,l)\le n$ とすると、これは $t$ に関して単調性があるので二分探索でき、またギリギリの $t$ に対し $\min_l f(t,l)=n$ となっている。

従って固定された $t$ に対し $\min_l f(t,l)$ とそれを達成する最小の $l$ を求めればよい。少し整理するとほとんど、 $\lfloor(la+( (ta-1)\bmod b))/b\rfloor-\lfloor la/b\rfloor=1$ とできるか、できるならそれを達成する最小の $l$ はいくつかという問題になる。

これは「 $0\le l\lt L$ に求める $l$ が存在する」かを判定して $L$ を二分探索すればよい。判定関数は $\sum_{l=0}^{L-1}\left(\lfloor(la+( (ta-1)\bmod b))/b\rfloor-\lfloor la/b\rfloor\right)\ge 1$ で書けて、floor_sumが使える形になる。

いま述べたことをそのまま実装すると、 $t$ の二分探索中に $L$ を二分探索して、判定関数にfloor_sumを使うので $\log$ が三つつく。TL 10secを信じて出したところ2650ms程度だったのでこれでも余裕。ただ $t$ の最大値を求めるまでは $l$ の具体的な値が必要ないので、 $L$ の二分探索は1回しか行わなくてよく、すぐに $\log$ 二つにできた。

Fは問題名を見て $\tan$ の加法定理を弄ったり $\sin$ や $\cos$ っぽい関数が定義できないか考えていたが、どうにもならなかった。5完5位。