熨斗袋 (@noshi91) | teapawt

Tweets
All Posts
Sort by
Most recent Popular
Tweets & Replies
Reposts
Media
Search

Pinned Tweet

熨斗袋@noshi9125 Mar 2021

このアカウントの運用について他アカウントをフォロー解除するときに、ブロック→ブロック解除をしています。これに深い意味はなく、普通にフォロー解除すると相手方が気付かずに面倒が起こるかもしれない (空リプに気付けない等) と考えてのことです。また、ミュートは使っていません。

1

35

熨斗袋@noshi9115m

AIが1000点↑の問題も自力で解けるようになったから、どうやったら解けたんですかというのを問い詰めてみている。結局後知恵になっちゃうけど....

1

3

211

熨斗袋@noshi9114m

「どうやったらうまく実装できたんですか」は結構ちゃんとした積み重ねになるかもしれない

1

142

熨斗袋@noshi9133m

B でもうこの方針通らなかったら無理という嘘を提出し 1WA になり、終わり

1

2

321

熨斗袋@noshi9119m

maxを更新する要素の個数についての条件を考えると、L=0については各区間について個数が決まっているという形になる。そこからL=1に移動すると、差分条件になるので、この調子で差分条件のまま更新していけると祈る。ありったけの必要条件を乗せて更新していくと、1ケース以外通ったが、普通に嘘で

2

127

熨斗袋@noshi91Nov 6

未来、AIの研究成果を研究者が理解しても本人の利益にしかならなくて、その解釈を書いた論文を読むくらいならAIに直接聞けば良いやとなってしまう(完全自律研究できるAIならすぐにあらゆる人間より優れた説明を生み出すようになるだろう)ために、研究者という概念がなくなる可能性はあるかもしれない。

1

47

5,529

熨斗袋@noshi91Nov 6

研究者本人からすると宇宙人が理解しているのと自分が理解しているのとは大違いだが、一般市民や出資者からすれば違いはないということになってしまう可能性があり、そのとき職業としての成立が危うい

21

1,327

熨斗袋@noshi91Oct 27

galacticな計算量を許すならNPも何とかなるのではないかということを根拠にP=NPと予想するのはEXPTIME完全な問題の存在で破綻してないか？

14

1,405

熨斗袋@noshi91Oct 27

C++で永続平衡二分木を書くと、new と比べて delete が遅すぎるため解放しないことが大真面目な高速化になる

33

3,061

熨斗袋@noshi91Oct 27

[0, 1] の一様分布で x=2 は「起きない」か？「確率が0なだけ」か？起きないと考える場合、[0, 1] の一様分布で x=0.5 だけ「起きない」ようにできるか？

1

25

8,353

熨斗袋@noshi91Oct 27

ETH 死んで四天王の最後の一人落ちたな感があるあとは OV ？

29

2,692

熨斗袋@noshi91Oct 21

subset sum は加法的整数論みたいなの出てきたあたりでもう分からんとなっていたが、ついに計算量限界まで来てしまったか modular の方はなんか実用的な感じになってるらしいしあとは knapsack？

9

1,094

熨斗袋 retweeted

Data Structures and Algorithms Papers@AlgorithmPapersOct 16

Subset Sum in Almost-Linear Time Ce Jin, Xiao Mao arxiv.org/abs/2610.20742 [𝚌𝚜.𝙳𝚂]

We give a deterministic algorithm for finding a subset of the input integers 1≤ a₁,…,aₙ ≤ Δ that sums to the target t in O(n+Δ¹⁺ᵒ⁽¹⁾) time. This improves upon the previous Õ(n + Δ¹.⁵)-time algorithm by Chen, Lian, Mao, and Zhang (SODA 2024), and achieves almost tight dependence on Δ assuming SETH. We use an inverse theorem for subset sums due to Conlon, Fox, and Pham (2023), and develop a quotient variant of economic cap covering from the polytope approximation literature.

ALT We give a deterministic algorithm for finding a subset of the input integers 1≤ a₁,…,aₙ ≤ Δ that sums to the target t in O(n+Δ¹⁺ᵒ⁽¹⁾) time. This improves upon the previous Õ(n + Δ¹.⁵)-time algorithm by Chen, Lian, Mao, and Zhang (SODA 2024), and achieves almost tight dependence on Δ assuming SETH. We use an inverse theorem for subset sums due to Conlon, Fox, and Pham (2023), and develop a quotient variant of economic cap covering from the polytope approximation literature.

1

36

2,110

熨斗袋@noshi91Oct 17

昔気まぐれにルール読んだ直後にCPUの囲碁と対戦したら、囲ったのに取れなくて？？？になりそのまま放置してたんだけど、最近のTLで謎が解決した。最初に陣地の話をするから、囲ったら取れるを「囲うと自分の陣地になり、中にいる相手は死ぬ」という意味だと類推してしまい、

1

116

40,941

熨斗袋@noshi91Oct 17

隙間なく囲わないといけないということに気付かなかった。ルール書いてる側は無意識に隙間ないのが当たり前と思ってるので記述が抜けやすそうだ。自分もオセロの説明するとしたら隙間あったらダメですって言い忘れそうだな。

1

35

9,121

熨斗袋@noshi91Oct 17

自分の石で囲ったのに中に敵が石を打ってくるのも結構びっくり挙動ではあるな。ボードゲームって勝敗条件から説明するのが鉄板だとと思うけど、その時に「打っても損するだけと双方が思ってノータッチになった場所」という結構複雑な概念がいきなり必要になってハードだ

31

8,644

熨斗袋@noshi91Oct 15

僕のライブラリはCC0にしておいたような気がするが実はバグってて大損しましたという報告が年一くらいで届いており…

30

1,659

熨斗袋@noshi91Oct 14

爆速ライブラリでインチキACができそうな時にLCのfastestを眺めて、CC0やMITで公開されていないのでコピペを諦めるということは結構ある。

16

1,120

熨斗袋@noshi91Oct 7

競プロ大喜びであるところの代数や数え上げ系のアルゴリズムは見た感じなさそうではある (見落としてたらごめん)

1

31

3,244

熨斗袋@noshi91Oct 7

F_p 多項式の因数分解をdeterministicにしましたというのがギリ該当か

1

4

1,025

熨斗袋@noshi91Oct 7

OpenAIの発表の理論計算機科学のところ眺めてるけどあまりにヤバすぎる結果がドカドカ出てて唖然

138

8,898