⋆꙳.*・ (@Segtree) header
⋆꙳.*・ (@Segtree) profile picture

AtCoder三段

Joined November 2016
Photo by ⋆꙳.*・ (@Segtree)Photo by ⋆꙳.*・ (@Segtree)Photo by ⋆꙳.*・ (@Segtree)Photo by ⋆꙳.*・ (@Segtree)Photo by ⋆꙳.*・ (@Segtree)Photo by ⋆꙳.*・ (@Segtree)Photo by ⋆꙳.*・ (@Segtree)Photo by ⋆꙳.*・ (@Segtree)Photo by ⋆꙳.*・ (@Segtree)Photo by ⋆꙳.*・ (@Segtree)
プリム法(最小全域木)
3
26
4
208
Replying to @hirakich1310354
スカウトが来てますよ
1
59
CPU実験のインターンがあったので参加してきました。
【ブログ】今夏PFNのMN-Coreチップチームでインターンに参加した米山瑛士さんの研究開発成果の紹介です。RISC-V CPUコアをスクラッチから設計・実装し、MN-Coreの動的制御の可能性を探りました。 preferred.jp/ja/blog/tech/mn…
6
86
4,063
AGC079 o--x A l(x) = min {a | lca[a, x) = a, a <= p(x) } という木を作ると答えが書ける 木を求める部分は、区間lcaを繰り返すとUFの経路圧縮のようなことになる D D={2,..,2}のとき ans ⇔ N>=9(三角柱状のN=9の反例グラフを拡張)D={1,...,1}のとき ans ⇔ N>=6 それ以外はYesと予想 -> WA
4
856
何かしらの日常生活の課題をmonotone minimaで解決する夢を見たが、そんな「日常生活の課題」は実際には無かったのだろうという確信がギリギリ持てる
4
774
考察用紙に書いた予想 - ans=#{(c,d) | cn+dm<=N && gcd(c,d) == 1}(雰囲気だけ近いが嘘) - (a,c), (b,d)それぞれで互除法をやっている(嘘) - (b,d)固定で(a,c)がちょうど一つ(嘘) 一番上の予想が立った時点で(c,d)->#{(a,b)} を実験すべきだったらしい
2
567
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
1
4
1,122
⋆꙳.*・ retweeted
井上裕太・河原林健一・宮下敦行・Bojan Mohar・Carsten Thomassen・Mikkel Thorupの論文“The Four Color Theorem with Linearly Many Reducible Configurations and Near-Linear Time Coloring”arxiv.org/abs/2603.24880が理論計算機科学のトップ会議FOCS2026のBest Paper Award受賞‼️おめでとう🎉🎉🎉
27
1
74
5,939
最近ワーキングメモリが2bitくらいだし、タスク管理は一本のスタックでやっているので、俺はプッシュダウンオートマトン
11
891
3SUMとAPSPの反証を見ての根拠のない予想 L = NL = NC ⊊ P = NP = BPP = BQP = MA = QCMA ⊊ QMA = PP = PSPACE
1
29
3,483
現代のコンテストが問題の前提にある文脈/知識が重くて嫌になったので2012年のCF Div.1走ったところ、range chmax range minを書くだけで5位でtouristとかPetrに勝ててしまい、結局現代人の文脈/知識パワーを発揮するだけの人間になってしまった
1
1
50
10,748
A ユークリッド距離を - f((x,y), (x',y')) - 三角不等式 - 3つ固定して下凸 くらいの性質を持った関数として抽象化していて、その2乗だからその亜種みたいなものだろうと思って考察していたのでクエリ平方分割になってしまったが、実際は - g(x,x') + h(y,y') が使えるので簡単だったということか
1
692
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 に注目(無ければ転倒数偶数)
1
10
1,884
サブスクを解除しようとして "revoke termination" のボタンを押してしまい、ドイツの電車にあと一ヶ月乗り放題になってしまった
21
1,128
Bはペアの順序を逆にすれば良かったらしい あと一つ追加できるかの判定のために次の値への制約を優先度第一に扱う必要があると思っていたが、末尾の値をfirstに置いていればこれをsecondに置いていても回収できるらしい 直観はまだ得られていない
2
528
C 円環なら簡単 端の値を変えるような操作を行うと不利に これをどれだけ行う必要があるかは端だけでは決まらない
1
571
AGC078 -x- A 判定はおかしな転倒ペアが無いかどうか 回数最小化は、各Bごとにその周りでできるCBA,CAB,BCAの回数の和の上界を定めるとそれが達成できると予想 B Y < X LISと同様に、長さ->(次の値への制約, 次の次の値への制約) のmin を管理 ->WA X,Yがiに依存しない定数であることを使うと予想
2
8
1,938
美容師さんに「美容師もAIに置き換わるんですかね〜」と言われ、「ロボットはまだ時間がかかると思いますよ」と答えてしまった
2
34
2,554
起床 健康
4
785
C で b[i] + b[j] = max(b[i],...,b[n]) を見たとき「i -> j の部分写像ですね~」とだけ言ってsuffix max要素を完全にスルーして考えていたの、ものの見方が雑というか楽観的すぎてひどいな
1
744