⋆꙳.*･

AtCoder三段

[⋆꙳.*･ @Segtree]

プリム法（最小全域木）

[⋆꙳.*･ @Segtree]

https://t.co/QorG2ggtEe

[⋆꙳.*･ @Segtree]

何かしらの日常生活の課題をmonotone minimaで解決する夢を見たが、そんな「日常生活の課題」は実際には無かったのだろうという確信がギリギリ持てる

[⋆꙳.*･ @Segtree]

考察用紙に書いた予想
- ans=#{(c,d) | cn+dm<=N && gcd(c,d) == 1}（雰囲気だけ近いが嘘）
- (a,c), (b,d)それぞれで互除法をやっている（嘘）
- (b,d)固定で(a,c)がちょうど一つ（嘘）

一番上の予想が立った時点で(c,d)->#{(a,b)} を実験すべきだったらしい

[⋆꙳.*･ @Segtree]

ARC233 o---
A ans == 2の判定：1~⌊N/2⌋を聞いて、結果の少ない方の相手を聞く　集合全体が求まり、ans == 3の判定：convolution　ans == -1
B (an + bm, cn +dm)の形で見る　A_qを線形変換(a,b,c,d)->(c,d,a+qc,b+qd)とする　(1,0,0,1)からA_qの列で到達可能な集合を見る　gcd(a,c) = gcd(b,d) = 1

[おおさか @todo314]

井上裕太・河原林健一・宮下敦行・Bojan Mohar・Carsten Thomassen・Mikkel Thorupの論文“The Four Color Theorem with Linearly Many Reducible Configurations and Near-Linear Time Coloring”https://t.co/rjpYzEzumPが理論計算機科学のトップ会議FOCS2026のBest Paper Award受賞‼️おめでとう🎉🎉🎉

[⋆꙳.*･ @Segtree]

最近ワーキングメモリが2bitくらいだし、タスク管理は一本のスタックでやっているので、俺はプッシュダウンオートマトン

[⋆꙳.*･ @Segtree]

3SUMとAPSPの反証を見ての根拠のない予想

L = NL = NC ⊊ P = NP = BPP = BQP = MA = QCMA ⊊ QMA = PP = PSPACE

[⋆꙳.*･ @Segtree]

現代のコンテストが問題の前提にある文脈/知識が重くて嫌になったので2012年のCF Div.1走ったところ、range chmax range minを書くだけで5位でtouristとかPetrに勝ててしまい、結局現代人の文脈/知識パワーを発揮するだけの人間になってしまった

[⋆꙳.*･ @Segtree]

A
ユークリッド距離を
- f((x,y), (x',y'))
- 三角不等式
- 3つ固定して下凸
くらいの性質を持った関数として抽象化していて、その2乗だからその亜種みたいなものだろうと思って考察していたのでクエリ平方分割になってしまったが、実際は
- g(x,x') + h(y,y')
が使えるので簡単だったということか

[⋆꙳.*･ @Segtree]

ARC231 xo---
A クエリ平方分割　d[x][y]と {x,y,c} を管理　flushがCHTでO(X(B + Y))、求値がO(B)　O(N(X + Y))
B X = [0,A) + {1024}, Y = [0,B) + [1024,1024+C)
E 転倒数が偶数のものと奇数のものでペアを作る　Bの値のmultiset固定で、複数の値があり得る最小の i に注目（無ければ転倒数偶数）

[⋆꙳.*･ @Segtree]

サブスクを解除しようとして "revoke termination" のボタンを押してしまい、ドイツの電車にあと一ヶ月乗り放題になってしまった

[⋆꙳.*･ @Segtree]

Bはペアの順序を逆にすれば良かったらしい
あと一つ追加できるかの判定のために次の値への制約を優先度第一に扱う必要があると思っていたが、末尾の値をfirstに置いていればこれをsecondに置いていても回収できるらしい
直観はまだ得られていない

[⋆꙳.*･ @Segtree]

AGC078 -x-
A 判定はおかしな転倒ペアが無いかどうか　回数最小化は、各Bごとにその周りでできるCBA,CAB,BCAの回数の和の上界を定めるとそれが達成できると予想
B Y < X LISと同様に、長さ->(次の値への制約, 次の次の値への制約) のmin　を管理 ->WA　X,Yがiに依存しない定数であることを使うと予想

[⋆꙳.*･ @Segtree]

C 円環なら簡単　端の値を変えるような操作を行うと不利に　これをどれだけ行う必要があるかは端だけでは決まらない

[⋆꙳.*･ @Segtree]

美容師さんに「美容師もAIに置き換わるんですかね〜」と言われ、「ロボットはまだ時間がかかると思いますよ」と答えてしまった

[⋆꙳.*･ @Segtree]

起床　健康

[⋆꙳.*･ @Segtree]

C で b[i] + b[j] = max(b[i],...,b[n]) を見たとき「i -> j の部分写像ですね～」とだけ言ってsuffix max要素を完全にスルーして考えていたの、ものの見方が雑というか楽観的すぎてひどいな

[⋆꙳.*･ @Segtree]

CF1120(Div.1) (oo)o----
A {0,1}^Nに対して、O(NlogN)個の区間についての「1が存在」「1が存在しない」という制約を満たすものを数える問題
B クエリ降順　forfeitを起こすiの集合Sを管理　一度Sから抜けたものは戻らない
C suffix maxはmaxとsecond maxのちょうど2種類　b ◦ pは存在するなら一意

[⋆꙳.*･ @Segtree]

unordered_mapをfor(auto &&e : dp) で読んでいる間にdpに新しいキーを追加したらイテレーションが壊れた
パソコン難しい

[⋆꙳.*･ @Segtree]

ABC475 oooooo(o)
A n回のうち初回だけ除いてn - 1回のループ
B counter
C (l,r) -> 最小距離, 個数
D 再帰の各段階で一番強い条件で枝刈り
E 辞書順上M個　(正誤列,cnt)の集合pass,failを管理　ins,del関数を定義
F 極小性（四辺に' , ' があること）を要求すると一対一　fix h1, h2でO(w)

[⋆꙳.*･ @Segtree]

G 小さい素因数から見て作っていく　(p, 約数の個数, 値, Dの倍数の可能性が残っているか)　の状態があり、値は他固定で最小のものだけ見ればok　見る素数は2,3,...53まででok　約数の個数の種類数は少ないと予想しunordered_mapで管理