09/15(月)

午後4時過ぎ起床。今日は祝日でインターン先の定例会もなく、夜中までずっと先週の週記を書いていた。

ギリギリで投稿して、午後11時半からECR182に参加した。

Aで何も考えず全探索するコードを書いたら、サンプル出力が $(0,0)$ と $(1,2)$ のみになった。ここで $\sum a$ が3の倍数なら分割は何でもよいことに気付いたが、コードはもう出来上がっているのでそのまま提出した。

Bは $p_i\ne i$ をすべて覆うコスト。未定の要素が0個または2個以上ならすぐわかるが、1個のときなぜか $p_i=i$ となるよう埋めるしかないものと勘違いしてしまった。1WA。

Cは直前をswapしたか持つdp。制約がやたら小さくて謎。Dは $x$ を決めると $O(n/x)$ で解けるので全探索可能。

Eは $\max(a)$ を境に左右で分離できるので、それぞれdpで解いてマージ。E2の存在を忘れたまま $O(n^2)$ で解いて、 $O(n\log n)$ にもなりそうだけど面倒だなと思っていたら、ちゃんとそれも問われていてびっくりした。ループの順序を入れ替えて遅延セグ木を使ったら確かに計算量が落ちた。

Fは((()))と()()()が強く、 $s$ に()があって自明に不可能なケースを除き $m=2$ が達成可能。そこで $m=1$ を確かめることになるが、これはABC419Fで見たばかり。制約が小さいので、Aho-Corasick法やほかの文字列アルゴをすべてサボっても間に合う。ある $s$ が別の $s$ に含まれている場合にちゃんと判定できていなくて1WAした。

https://atcoder.jp/contests/abc419/tasks/abc419_f

70分で全完して3位。BとFどちらかのペナがなければ優勝していたので残念。

www.youtube.com

先週の週記にちょっと書き足して、正午就寝。

JAG夏合宿の話

先週土曜日から今日までJAG夏合宿が行われていた。三つの5hはそれぞれ内部コンテストとして取り組んだので、所感を述べておきたい。ソロ、コピペ・検索なしで走った。

2025/Practice/夏合宿 - ICPC OB/OG の会

day1

I以外の11完。Iはupsolveすらしていない。

Aはよい。Bは簡単と言われているから簡単に見えているだけではないだろうか。

Cは蟻本に最大独立集合を一つ求める方法が書いてあって、二部グラフの部集合を入れ替えることで二通りできてサンプル出力が得られる。さらに作り方から、最大マッチングを適当な交互閉路で取り換えても求まるものは変わらない。これで全部カバーできていることを信じて投げたら通った。

Dは末尾 $N$ 文字だけ変な挙動をするので、 $S+S$ のSuffix Arrayを作るとよい。 $S$ が周期的になっているとちょっと面倒で、サンプルにもないため自分で気づく必要がある。Suffix Arrayの構築には $O(N(\log N)^2)$ のアルゴリズムを持ち出した。

Eは三次元幾何に見えるが、位置関係を木で取り出したあとはグラフの話になる。 $\vec a$ で定義された平面の奥に $\vec b$ があるか判定すればよく、これは $\vec a$ と $\vec b$ のなす角 $\theta$ が $\vec a$ と円上の点のなす角 $\varphi$ より小さいことと同値。 $\frac{\vec a\cdot\vec b}{|\vec a||\vec b|}=\cos\theta\lt\cos\varphi=\frac{|\vec a|}{R}$ を整理して辺々二乗すると高々10³⁶の数の比較になって、128bit整数で誤差なく行える。

Fは深さごとに移動するタイミングのパリティを変えられないので、行きたい方向に降りられる最も早いタイミングを前計算しておく。ただし $N$ が奇数のときに注意。

Gは $i+j$ 一定のマスを通る回数がすべて同じなので、十分多い回数通れば高々1マスの損で抑えられる。この損はパリティを見る必要があって算数が面倒。また区間更新なので遅延セグ木も必要になってさらに面倒。

Hは答えを二分探索。色の多重集合は64bitの乱数の和で表現した。辺属性のオイラーツアーを行い、パスクエリをLCAからのクエリ二つに分けることで、ハッシュ計算は区間和取得になる。座圧付き二次元BITを書いてヘトヘトになっていたが、内側は単なる累積和でよかった。あるいは並列二分探索を行えば普通のBITでOK。累積和にした場合も座圧は必要になるし、いずれにしても $\log$ は二つついていた。

Jは謎。スターグラフを作って二辺で適当な範囲の数をすべて表そうと思った。探索の結果 $\{1,2,4,6,7,12,14,17,21,30,39,48,57\}$ の13個で64まで、 $\{1,2,4,6,7,12,14,17,21,30,39,48\}$ の12個で56まで作れることが分かったので、前者を四つ、後者を一つの計64辺で $65^4\times 57\gt 10^9$ 未満をすべて作れた。こういうのは一人でPCを占有できるソロのほうが取り組みやすそう。

Kは区間dp。stackが途中で空になり得るかをちゃんと区別しておく必要がある。途中で空になる場合の計算を各区間で独立に行うと全体で $O(N^7)$ になるが、左端降順・右端昇順で区間を見ながら同時に求めていくと $N$ が一つ落ちる。

Lはある $W$ について $N/i\ge W$ なら $j$ を商列挙、 $N/i\lt W$ なら $i$ を商列挙しつつ $j$ に関する和に前計算の結果を用いた。前計算は $O(W\log W)$ 。 $W=N^{2/3}$ としても全然間に合わず首をかしげていたが、そもそも前計算は一度だけでよいので目一杯大きくしておくと得。 $W=2^{22}$ を用いた。

day2

CHI以外の9完。後からCとHだけupsolveした。

Aはよい。白状するとcondimentもacridityもsournessも知らなくて大変読みづらかったが、何かパラメータが二つあるとだけわかればよい。Bは頭を使いたくなかったのでdpした。

Cはまず平面グラフに関するオイラーの定理から凸包上の頂点を減らせばよいことがわかる。凸包の辺上にピッタリ乗った点も数えることに注意。二点追加すれば必ず三角形にできるので、問題は $k=1$ 。元の $N$ 点の凸包において、角度の差が180度未満であるような二つの辺に挟まれた頂点を隠すことができるので、尺取りでぐるっと一周した。同じ角度の辺があるのでかなり怖い。

Dは長方形の辺に時計回りに向きをつけて、全部まとめたあと打ち消しあうものを除いて連結成分に分けた。図D-3のような配置がない制約が非常にありがたく、これで隙間をすべて列挙できている。最後に符号付き面積を求めると一つだけ負になっており、これが外周。

Eはやることはわかるがひたすら面倒。最初はなもりグラフの二通りを頑張ってチェックすればよいと思い書き始めたものの、途中で木の場合に全方位木dpが必要になることに気づいてひっくり返った。逆になもりグラフのケースは一辺切ると木の場合に帰着される。

Fでは信じられないくらい詰まった。実験すると $f(T)=|T|-1,|T|,|T|+1$ で、 $|T|+1$ のケースはわかりやすい。よって残り二つの判別をする必要がある。ずっと隣接文字のXORなどを考えていたが、最終的には文字列の数がおよそ1対2になることから $\bmod 3$ で何かすることを思いついた。

Gは適当に全探索。Hはコンテスト中ほとんど時間を割かなかったが、ちゃんと取り組んだとしてこの判定が思いつくかは不明。

Jは2-SAT。交差判定がかなり面倒だった。2-SATになると分かっているなら「色 $i$ を上/下向きに繋ぐなら色 $j$ を上/下向きに繋ぐ必要がある」という関係で有向辺を張ればグラフが完成する。命題変数の否定だったりを考える必要がないので若干簡単になると思っている。2-SATにならない場合は当然使えない。以下の記事を参照のこと。

noshi91.hatenablog.com

Kは各数列のprefixとしてどのくらいの長さが必要になるか考え、どんどん以前の数列へと帰着していった。戻りながら構築する際には余計なコピーが発生しないように注意しなければならない。dequeを使うとかなり簡単に書けた。

Lは二部グラフのマッチングと捉えて増加道を見つければよい。

day3

CEIL以外の8完。C以外はupsolveした。

Aはよい。Bは二分探索。

Dは操作を巻き戻していくと、盤面の左または上がどんどん削れていく感じになる。最後に白マスだけが残れば終了。

Eはコンテスト後にフローの問題だと聞いてなんとか解けた。全然思いつかなかった。

Fは最終的な向きが左になるprefixと右になるsuffixに分かれる。その向きを固定すると最初の向きや衝突回数は端から順に求められるので、中央でマージする。

Gは一次関数のMAXを求める問題。しかし直線の追加と削除があるし、傾きは単調ではない。とりあえず列を左右両方から処理することで直線の削除は回避することができた。追加はどうしようもないので、CHTのdequeをmapに置き換え、insertと周囲のeraseで無理やり処理することにした。

誤差が怖かったので直線を整数で管理しようとしたものの、面倒すぎたし絶対値が大きくなって128bit整数にも収まらなくなったので、途中からは諦めてdoubleを使った。隣接ビルを結ぶ直線だけでよいという考察は通らなかったが、通っていたらもうちょっと楽だっただろうか。

Hは大きな数を残すとよさそう、くらいで詳しい証明はしなかった。Iはかなり粘ったが、三角形を作れれば常に可能であることに気づけず門前払い。Jは入次数と出次数の差を見る。すべて0の場合にも一機必要なことに注意。

Kは真似っこ戦略によって両端から均等に取り除かれていくはず。限界まで消したとき、そこに黒石が $M-1$ 個含まれていたら、あとは両端から連続する白石の個数の偶奇で決まる。 $M-2$ 個含まれている場合、残った部分の両端は黒石になっているはずだが、そのどちらを消すかは先手が選べる。その先に続いている白石の個数の偶奇を見て、勝てるほうがあるかチェック。

Lはbitset高速化で解いた。戻すdp方針を有名modで行う解法が狙い撃ちされていた件についてTLでは賛否両論あったようだが、まあ伝統芸能だろうと思う。テストケース作成者が優しいことを期待するべきではない。

09/16(火)

午後8時くらいに起床。Puzzle Square JPで「美術館」を解いていた。

盤面が三次元に拡張された変種に取り組んでいたが、解けない。美術館に限らないペンシルパズル汎用のプレイヤーなのでおそらく想定解との完全一致しかチェックしておらず、間違いがあっても指摘してくれたりはしないため、そもそも大変やりづらい。しかしこの「解けない」というのはそういう意味ではなく、正誤判定が動作しないという意味である。

そもそも盤面に置ける記号がたくさんあるので、想定解に使われた正しいものを選択しなければならない。通常はそのまま「Akari」と名前が付いた電球を置くか、あるいはMサイズの円が使われるのだが、どちらを試してもうんともすんとも言わなかった。

仕方がないのでプログラムを書いて、自分の解が正しいことを確認した。さらにもうちょっと頑張って照明の配置を全探索するコードを書いたら、ちゃんと唯一解になっていた。どうしようもないので、プレイヤーでの正解判定が出ないまま解答済みと記録した。

ちなみに同じ作者の作品に四次元の美術館もあるが、そちらはなんと有志によって専用のプレイヤーが開発されていた。

puzsq.logicpuzzle.app

今年のYandex Cupに関するメールが来た。Semifinalがなくなって11/02の深夜に4hの予選が1回だけ行われ、トップ20人がトルコ・イスタンブールでの決勝に招待されるらしい。決勝の日程は12/05-07で、ICPCアジア地区横浜大会と完全に被っている。

また不正防止の競技ルールがかなり念入りに設定されていた。画面録画はもちろんのこと、参加者自身や周囲の様子まで動画に収める必要があるらしい。さらに「proctoring system」とやらを使用しなければならないようだ。心当たりがないが、別にアナウンスがあったりするのだろうか。例えば昨年のYandex Cup決勝では、ブラウザ経由で運営に画面共有をした状態でコンテストに参加した記憶がある。

Rules — Yandex Cup

ラノベ「商人令嬢はお金の力で無双する」5巻を読了。後半ではいよいよ商会の商品が社交界にお披露目され、主人公が商会長として活躍する様子は大変好みだった。特に、諜報好きの妖精を使役することで初対面の相手に対しても情報戦で優位に立つところが爽快。またタイトル通りお金の力での無双もあった。

9月ももう半ばだが、電撃文庫の新刊が生協に届かない。不思議に思って通販サイトを確認したら、なんと予約していなかった。慌てて3冊注文。ついでに10月分の新刊チェックを行い、17冊予約した。

「かくりよの宿飯」13巻が出ることを知った。12巻で予告されていた天神屋の社員旅行の話が、三年半の時を経てついに世に出る。非常に楽しみ。また、この10月からアニメ二期が始まるそうだ。

lbunko.kadokawa.co.jp

天神屋の社員旅行はまた別の外伝という形でそのうち出版されるらしいので、そちらも楽しみに待ちたい。
週記（2022/03/21-2022/03/27） - kotatsugameの日記

正午になって用事のため大学に行こうとしたら雨が降っていた。家に引き返してしばらく待っていたら天気予報通り止んだので、改めて登校。学食で食事し、書類を提出した。

久しぶりに院生室に顔を出したら後輩がいたので、ボドゲ「コリドール」で遊んだ。なんとなくコツが分かってきた気がする。相手にゴールまでの道を塞がれるのを防ぐためには、先に自分の後ろを囲っておくとよい。ゴールと非連結にする操作は許されないので、前の道は塞がれなくなる。さらに将来的には相手の邪魔にもなる。

圧倒的ではないか pic.twitter.com/0zMd5EgTaK
— こたつがめ (@kotatsugame_t) 2025年9月17日

そうこうしているうちに再度雨が降り出したので、止むのを待ちつつ椅子を並べて1時間ほど寝ていた。起きたところに環境構築の相談を受けて、夕食を挟みつつ夜まで格闘した。

ITensorというC++ライブラリを使いたいらしい。普段Visual Studioでプログラミングしている人なので、そこに導入できないかちょっと粘ってみたが、まずmakeコマンドが用意できない。早々に諦めてWSLを導入してもらった。

そうやってライブラリがビルドできたら、次は使えるようにする作業が待っている。サンプルのmakeコマンドはg++にライブラリのパスを渡しているだけだと判明した。しかしVisual StudioからWSLのg++を叩く方法がわからない。これも諦めてVSCodeをインストールしてもらい、そのタスクとしてまとめた。

ITensor

午後11時帰宅。ほぼ徹夜状態となってしまい若干怖いが、CF #1051 div.2に出た。

Dashboard - Codeforces Round 1051 (Div. 2) - Codeforces

Aはすべての $k$ について $n-k,\dots,n$ が $p$ における区間をなしていればよい。Bは $b$ の昇順に貪欲に使っていくのがよい。Cはすべて $\max(x,y)$ を達成可能。スカスカのDAGをトポソする話になるが、単に子を適切な順序で訪れるdfsだけでも解ける。

DはLDSの長さが2以下であることが必要十分条件。初項の最大値、2項目の最大値を持てば状態数 $O(n^3)$ でD1が解ける。定数倍が良いのでD2も手元では間に合っていたのだが、提出するとTLE。よく見ると区間和取得・1点更新になっていたので、二次元のdpテーブルを縦横に切ったようなBITを $2n$ 本持って $O(n^2\log n)$ にした。

Eは((や))を好きな位置に移動させることができるので、いったん削除して考えてよい。できる限り取り除くと残りは()()...または)()(...になっているので、その左右に均等に戻した。そもそも取り除いた回数が奇数回だと均等に戻せないが、これはどうしようもない。

Fは自分以前の要素のXORで作れる値をすべて自由に設定できる。よって $\mathbb{F}_2$ 線形代数の話になって、作れる値の空間が等しい $O(\log a)$ 個の区間に分解して考えてよいことがわかる。この区間は各suffixに対して順に求めていくことができる。

列を前から貪欲に構成しようとすると、 $\mathbb{F}_2^{20}$ の部分空間において整数としてのupper_boundや $k$ -th maxが行えればよい。各基底の最上位bitが他の基底に影響されないようにすれば、適当な算数により $O(\log a)$ で実現可能。ちなみにこのような基底はReduced Row Echelon Form、簡約階段形と呼ばれるらしい。

単に簡約階段形を求めると $O((\log a)^2)$ かかり、計算したい空間が $O(n\log a)$ 個あるので少々まずい。しかし実のところ基底を一つずつ増やしていくような空間の列になっているため、各suffixに対して合計 $O((\log a)^2)$ ですべての簡約階段形を求めることができる。

80分で全完して5位。

www.youtube.com

午前3時半就寝。

09/17(水)

火曜日に吸収された。大学に行ったりCFに出たりしていたのは、日付的には水曜日の昼から深夜にかけての話である。

09/18(木)

若干の中途覚醒を挟んで午後6時過ぎまで寝ていた。

ニコニコ動画で「重音テト一人合作」を観た。非常に面白く、また一人で作っているとは思えない手数の多さ・引き出しの豊富さに度肝を抜かれた。投稿者は「ライアーダンサー」などで知られるマサラダさんの別アカウントらしい。

www.nicovideo.jp

ラノベ「サイレント・ウィッチ」9巻extraを読了。これまでの特典ショートストーリーなどをまとめた短編集で、9巻に渡って描かれた学園での一年間を振り返ることができた。主人公の社会性の回復・成長が感じられて非常に微笑ましく、面白かった。

$N$ クイーン問題が登場したので、配置の数え上げについてちょっと調べた。OEISには似た数列が二つある。新しいほうはNQueens@Homeというプロジェクトの計算結果で、既知の値とずれていたため新規に登録されたようだ。数か月後にオーバーフローによるミスだったと判明したが、誤った数列もそのまま残されている。

A140393 - OEIS

続けて「サイレント・ウィッチ」10巻も読了。新章開幕ということで導入程度かなと思っていたら、主人公の超絶技巧が大盤振る舞いされていて大変嬉しかった。自分の正体・実力を隠すことの優先度が下がったので、これからはより自由で大胆な活躍が楽しめることと思う。

正午就寝。

09/19(金)

午後3時半起床。

大学生協に行って、来週大阪に行くための新幹線切符を買った。すでに窓際の席が埋まっている列車もあったりとかなり混雑している様子。

9月末に大阪大学で行われる「組合せ論的ホッジ理論勉強会（第1回）」に参加することを決めた。
週記（2025/08/18-2025/08/24） - kotatsugameの日記

ラノベを買って、散髪して、食事して、帰宅。1時間以上かけてメールを一本書いたあと、今度はゲーセンに向かった。

閉店まで19クレプレイし、新曲をあらかた埋めて理論値が四つ出た。粘着中に5クレ分くらい捨てゲーしてしまったが、Lv.14の理論値も出てくれてかなりいい感じだった。

今日は19クレ pic.twitter.com/kd7MX9DZMU
— こたつがめ (@kotatsugame_t) 2025年9月19日

帰りに一閃閣の向かいにある「油そば専門店だるま」に入ってみた。入口が紫色の照明で照らされていて目立っており、以前から気になっていた。複数人向けの座敷席しかないあたり、飲み会のシメで来る客が想定されているのだろう。価格は若干高め。

ドンキに寄って帰宅し、昼前まで日記を書きつつペンシルパズル。Puzzle Square JPの「美術館」で解いた問題が2014問中2000問になった。

午前10時就寝。

09/20(土)

午後8時起床。午後9時からABC424に出た。27卒が対象のオンサイトの予選になっている。博士2年の自分も27卒扱いにしてくれるらしい。

https://atcoder.jp/contests/abc424

Aはよい。Bは $B$ を無視してもよい。Cは有向グラフにして探索。Dは1行の状態を持つdpで、制約が小さいため1行ずつ一気に遷移することが許される。 $H-1$ 行目まで遷移すれば十分だと勘違いして1WA。

Eで大変なことになった。解法は答え $\ell$ についての二分探索で、長さ $2\ell$ 以上の棒なら長さの大小に依らず操作してよいとしたとき、 $K$ 回の後に長さ $\ell$ 以上の棒が $X$ 本以上あるか判定する。 $K$ 回操作しきれない場合にばかり目が向いて、 $K$ 回より多く操作できてしまうコードになっていたのに気づかなかった。

あとは単なる実装ミスも一つあってWA。しかしそれからずっと精度の問題を疑っており、最終的にはすべての数を $A_i/2^k$ の形で表現する絶対に誤差の発生しないコードを書いて、それでもなお落ちたことでようやく気付いた。40分と4ペナを消費してなんとかAC。

Eを通す直前には500位くらいまで落ちていて浮足立っていたが、Fは一瞬で解けた。区間の交差判定にすれば $A$ と $B$ の間から外に出るものがあるかのチェックとなり、1点更新区間MIN・MAX取得のセグ木でよい。

Gは4分ほど間に合わなかった。少しフローを考えたが、冷静になってある曲の集合が演奏可能かの判定問題を考えると、そこそこ単純な式で書けたような気がしてくる。しかしその式を思い出したりその場で導出したりするのに失敗。焦りが先立ってあまり整理しないまま雰囲気でdpのキーを弄っていたら、コンテスト終了後に正解を引き当てた。

ちゃんというと、任意の k について、a の上位 k 個の和が min(b[j], k) の和以下か？
— risujiroh (@risujiroh) 2023年12月18日

6完262位。久しぶりにこんな順位を取ってしまった。まあオンサイトには行けるかな。

www.youtube.com

午後11時半からはCGR29に出た。CGRは年間通してのランキングが存在するはずだが、なんと9月も下旬に入って今年初めての開催である。

Dashboard - Codeforces Global Round 29 (Div. 1 + Div. 2) - Codeforces

Aは $x\lt y$ なら2歩、 $1\lt y\lt x-1$ なら3歩、他は不可能。ちゃんと証明せずに提出した。Bは $n-1,n-2,\dots,2,1,n,1,2,\dots,n$ とすれば距離 $x$ または $2x$ になっている。この構築には何となく見覚えがあって、すぐ思いつけた。

Cは11で切って考える。0のブロックが偶数個あるか、サイズ2以上のブロックがあるか、元の文字列において端にあればOK。三つ目は $s$ の先頭と末尾の文字を一つずつコピーしておくと無視できる。

Dは完全に雰囲気で解いた。偶数ならお互い均等に取れるだろうから、奇数の扱いにだけ注目する。奇数の出現回数をそれぞれ調べて多いほうから先手後手交互に割り振ったら通った。

Eも細部は証明していない。各popcountを達成するために必要な最小の操作回数を計算する。実は目標とすべき総ORがもともとの総ORを下のbitから順に埋めた値として一意に定まるため、これを高々 $31$ 回解けばよい。

上のbitから見て、現在の総ORで立っていなかったら、最小の操作回数でそのbitを立てられる数を選んで操作するという貪欲が正当。この操作で下のbitが消えてしまう場合も、以降の処理で解消される。この貪欲以外の操作もbitごとに分解してみると実は一致する、という感じで考えたが詳細は詰めなかった。

Fは結構面白かった。点 $(p_i,s_i)$ をプロットすると、左上にも右下にも点がないようなブロックに分けることで数え上げができるようになる。ブロックの切れ目 $k$ は、 $p$ と $s$ が順列であることを思い出せば「 $p_i\le k$ かつ $s_i\le k$ となる点が $k$ 個」が条件。具体的な答えは $k$ の二乗和と $k$ の隣接する2数の積たちから求まる。

ここで遅延セグ木を用意し、 $v_k:=k-\#\{i\mid p_i\le k\land s_i\le k\}$ を乗せる。条件 $v_k=0$ を $v_k=\min(v)$ に緩めると区間ADDに対応できるようになるのは典型テクで、両端の $k$ を持っておけば答えも一緒に計算できる。クエリは点の追加・削除だと思ってもよく、 $[\max(p_i,s_i),n]$ に区間ADDするだけなので逆順列で頭を壊すこともない。

GはAIで解けるらしく順位表が破壊されていた。 $m$ と互いに素な数 $a$ を固定する。 $a^{a^{b_n}}\equiv 1\pmod m$ は $\operatorname{ord}_m(a)\mid a^{b_n}$ と同値で、 $b_n$ はすぐ大きくなるから結局 $v:=\operatorname{rad}(\operatorname{ord}_m(a))$ として $v\mid a$ が条件になる。ここで $\operatorname{rad}$ は公式解説でも使われていた、素因数の重複を除いた積。

$v$ は $a$ を $a\bmod m$ に取り換えても変わらないので、 $0\le a\lt m$ として $km+a$ の形をした数について考える。 $km+a\equiv 0\pmod v$ となる $k$ を考える際には $\gcd(m,v)$ が気になるが、今 $v\mid a$ かつ $\gcd(m,a)=1$ なので $\gcd(m,v)=1$ としてよい。このとき $k\bmod v$ が一意に定まり、密度は $1/v$ となる。

もう $a$ のことは忘れてよい。 $v$ 、ひいては $\bmod m$ における位数を直接扱うのは難しいので、中国剰余定理を使う。 $m$ を素因数分解して現れる $p^e$ に対し、 $\left(\mathbb{Z}/p^e\mathbb{Z}\right)^\times$ における位数を考える。以下のページを見ると巡回群になっているので、かなり簡単に求まる。

巷で話題のカーマイケル数・カーマイケルの定理について - tsujimotterのノートブック

特に $\gcd(m,v)=1$ で $p\mid m$ なので、位数が $p$ の倍数にならないようにしなければならない。 $p=2$ ならそのような元は $1$ しかないので、無視できる。 $p\ge 3$ なら $\mathbb{Z}/(p^{e-1}(p-1))\mathbb{Z}$ において $\ell\times p^{e-1}$ という形をしていて、このとき位数は $(p-1)/\gcd(p-1,\ell)$ として求まる。

$p-1$ をさらに素因数分解して $q^f$ が現れたなら、 $q^f\not\mid\ell$ と $q\mid v$ は同値で、これを満たさない $\ell$ は $(p-1)/q^f$ 個しかない。同様にすることで各 $v$ に対し $\ell$ を数え上げることができる。最後に $\left(\mathbb{Z}/m\mathbb{Z}\right)^\times$ に戻すには、 $p^e$ それぞれで計算した $v$ を集めてきてLCMを取るとよい。

愚直にやろうとすると計算量が不明。つまり、各 $p\mid m$ について $p-1$ の素因子をすべて集めたとき、サイズがどのくらいになるかわからないのだ。その上でbitDPみたいなことをする必要がある。提出したらTLE。改めて式をぐっと睨むと $q$ ごとに独立した式の積になっていることに気づき、二項定理を使ってまとめたところ爆速で通った。

7完14位でレートは2942→3048(+106)。LGMに返り咲いた。

www.youtube.com

明日は午前11時からまたコンテストがある。午前6時くらいに布団に入ったが、そこからうっかり3時間ほどハーメルンを読んでしまった。

09/21(日)

午前10時半起床。

「BNPC-HS 2025 Qualification Round Mirror」とやらに出た。このサイトでのコンテストはおよそ一年ぶり。ファイル提出しかできなかったはずが、いつの間にかコピペ欄が生えていた。

https://tlx.toki.id/contests/bnpchs-2025-penyisihan-mirror

Cまでは自明。Dも自明だろうと思ったら自明ではなかった。各道について目的関数が上に凸なので、差分を全部集めて上から $K$ 個取ればよい。

Eは $x\ne y$ のとき $\gcd(x,y)\le|x-y|\le x\oplus y$ なので全部等号になるところを数えて引く。 $\gcd(x,y)=|x-y|$ となる数の列挙が調和級数でできる。

Fは一次関数に対する区間ADDと $x=v_h$ でのMAX取得がしたい。まともな方法ではできないので平方分割とCHTを使った。取得側に $\log$ がつくのでバケットサイズは大きめがよいかと思ったが、手元のランダムケースでは200が最適になった。

バケットサイズガチャに勝利し50分でノーペナ全完、3位。レートは3030→3044(+14)でなんとかランキング一位を維持できた。それにしてもこのセットでRatedなのか……。

金曜日のyukicoder 483を解いた。AとBはよい。Cは立っているbitを下から二つ消す。Dは答えとなる数の桁和を $N+1$ 以上から全探索で求めたらすぐ見つかった。Eは分数の形で持って最後に一回だけ除算を行う。定数の用意ができないが、今分数を持っているのか整数を持っているのか把握しておけば何とかなる。

yukicoder contest 483（オムニバス） - yukicoder

午後4時半から4時間ちょっと仮眠してARC206 div.2へ。

AtCoder Regular Contest 206 (Div. 2) - AtCoder

Aは同じ列を作る最も短い区間で考えると、 $A_L\ne A_{L+1}$ かつ $A_L\ne A_R$ なる $(L,R)$ の数に1足したものが答え。 $O(N)$ になる。Bはスライムを色ごとに分けて考えてよい。色を変えないスライムの数を最大化する問題になって、これは $P$ のLISをとればよい。

Cは $r=l+1$ での条件が $B_l=r$ もしくは $B_r=l$ であり、端から考えるとどこか一か所を境にして左は $B_i=i+1$ 、右は $B_i=i-1$ となっていることが必要。逆にこのとき、確かに良い数列になっている。数え上げは $B_i\ne i+1$ となる最小の $i$ を固定すると簡単。

Dは $K\ge 2$ なら手ですぐ構築できた。全探索を書くと $K=1$ なら $N=1$ と $N\ge 5$ 、 $K=0$ なら $N\ge 8$ で達成可能らしい。得られた列を適当に拡張すれば構築も容易だった。念のためチェッカーを書いてから提出し、問題なくAC。

Eは上下左右から二点ずつ選べば大体可能で、逆に四隅を塗るためにはそれが必要でもある。下手な選び方をすると真ん中が開いてしまうが、そのようなパターンは限られていて回避可能。各列のprefix・suffixのMINを求めておいて、全体で線形時間の解法が得られた。

しかしWA。四回の操作で塗る方法はすべて尽くされたはずで、さらに $U$ と $L$ による操作などを増やすのも無駄だと確認できている。しかし $U$ と $D$ 、 $L$ と $R$ については十分に検討していないことに気づいた。改めて考えると、そのような操作を追加で一回行えば必ずすべて覆えることが確認できた。このパターンを追加してAC。

82分1ペナで全完。順位表を見るとなんと優勝していた。ペナルティが少ないのが偉かったらしい。

www.youtube.com

午後11時半からはCF #1052 div.2に出た。

Dashboard - Codeforces Round 1052 (Div. 2) - Codeforces

Aは出現回数を全探索。Bは $n-1$ 個以上選ぶ方法をチェックすればよい。Cは $x$ より小、 $x$ 、 $x$ より大がこの順で並んでいればstableである。特に $s_i$ が1なら $p_i=i$ が確定。その間は適当にバラバラにすればよいが、間が一個しか空いていない場合はバラバラにできないので不可能。

Dはbitごとに独立にペアを作れる場合の上界が達成可能。2べきっぽい数を取ってそこを中心にペアを作れば損はしておらず、残りもまた高々一つの区間になっているので再帰的に実行。これでD2まで一気に解けた。

EはMEXを決めるのが難しいので、 $m\notin b$ を適当に固定して $b_i\gt m$ を数える。末尾が $i$ で $m$ を含まない最長の区間に対するこの値を管理するには、 $i$ をインクリメントする度 $m=a_i$ のゼロクリアと $m\lt a_i$ のインクリメントが行えればよく、遅延セグ木で全体MINが取れる。

Fはsort関数の戻り値が $\max_i\#\{j\lt i\mid a_j\gt a_i\}$ になっている。そこで順列 $p$ に対し $c_i:=\#\{j\lt i\mid p_j\gt p_i\}$ と定めると、条件 $(k,l,r)$ について $l\le x$ は $c_1,\dots,c_l\le k$ と同値。 $x\le r$ は難しいので包除原理を適用すると、すべて $c$ の上限という形で書けるようになる。このときの数え上げは挿入dpの要領で行える。

条件を $k$ の昇順に見ていくと、 $c$ のあるprefixの上限が決まったものとして状態を表現することができる。これは高々 $2m$ 通りしかないので、dpによって $O(m^2)$ で計算可能。符号を入れ替えながら遷移することで包除原理もできている。遷移時の係数は $\min(i,k+1)$ の区間積になるため、階乗などの前計算のもと $O(\log n)$ で求められる。