PCT

一応使い道はあって、前計算で O(N log N) かかるが、<O(sqrt N),O(1)> で monoid 1 点更新区間積が出来る（Mo とかでギリギリ使い道がありそう） sqrt N 個に列を分割して、それぞれの列と、列での monoid の計算結果について DST を作るとよい

この前ふと考えていたが、DST って更新は O(N) で出来ることに気がついた 何に使えるんだよ、と言われたら困ってしまいます

自分でも知らない内容もちょいちょいあって凄い

【AtCoder Algorithm Lectures 公開のお知らせ】 「AtCoder Algorithm Lectures」を公開しました。 競技プログラミングの理論やテクニックを解説する講座です。 今後も講座を拡充し、質の高い学習コンテンツの提供を目指します。 info.atcoder.jp/entry/algorith…

これ、チームメンバーの変更があるところだと練習等が少し面倒そうだなあと思っている（別にどうしようもないのだが）

ICPC、実は次の大会が 2025 年度の WF ではなく 2026 年度の国内予選なのか（JOI/IOI はここが反転していないので少し慣れない感覚）

N 頂点の木が与えられる。各頂点には整数が割り当てられている。単純パスのうち、パス上の頂点に書かれた整数が全て異なるものの個数を求めよ。 o(N^2) でまともに解けません　助けてください

@SSRS_cp なんか平方分割すれば n sqrt n log^2 n とかで解けるかもしれないな、とは思っていますが少し考えて無理でした(この方針はあまり真面目には詰めていません、出来てもカスの計算量にしかなる気がしなかったので)

@PCTprobability まともにというのは、まともではない解法はわかっているということを意味している？

PCTprobabilityさんのAtCoder Regular Contest 217での成績：4位 #AtCoder #ARC217 atcoder.jp/users/PCTproba…

A：mod 4 でやったら下界が達成可能 B：i が i,i+1,...,N のうち何番目にあるかを考えると見やすい C：人の所持金集合を先に固定すると買うものの集合が順番に寄らず定まり、dp D：[l,r] 円持っていた人たちが [0,r-l] 円持っているという l,r を管理 E：主客転倒すると画像の式になり、展開して気合

全完

ARC

UC かなり調子よく 14 完 6 位(はるるんが少し遅れて H を通していて惜しい) 日本セットとの相性の良さをかなり実感していた

@vwxyz68357032 これで x = 18 などにすると制約内で top 15 間でしか見てないと嘘なケースができます

@PCTprobability 1/3乗オーダー本見ないといけないのってどんなケースですか？

OUPC-J、1 辺固定してフローを流す段階で多重辺が多い top k だけ流すという嘘で本番通したが、k = 1 はすぐ hack できるものの辺数の 1/3 乗のオーダー本見ないといけないケースまでしか作れていない 解説の上位 30 本見て通されてしまったというのは正当かもしれない(そこまでは示せていない)

@kyougikyougi ほかの提出は ACL 使ってないのに言われるんですね、情報ありがとうございます

CF でこの前の F の提出が似ています、と言われていたが ACL を貼ってるからかと思いきや python の提出とかもあって唖然している なにかこの現象について知ってる人がいれば教えてください

自分の解法の嬉しいところとして、残ったグラフが DAG になるかを考える必要がない(DAG であることと出次数 0 の頂点がないことを同値にするために予め取り除いているため) 悲しいところとして、dp の遷移が凄いことになる

AGC-D、自分は操作列のグラフを出次数 0(つまり逆操作で戻せる)ものを戻しきってから、出次数 0 なものがないという条件で包除したが始めから入次数 0 なものについて包除をすればよかったのか