熨斗袋 (@noshi91) | teapawt

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

Pinned Tweet

熨斗袋@noshi9125 Mar 2021

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

1

36

熨斗袋@noshi918h

重みなしの区間LISは順列の累積和になるという綺麗な構造があったんだけど、重み付きになると順列から一般の非負行列になってしまい表現として使えなくなってしまう Mongeではある

4

554

熨斗袋@noshi9112h

セグ木に永続BBST載せる系のアルゴリズム結構あるんだけど、それらと比較すると、分岐点だけ持つことで圧縮表現にするテクニックが適用不能かも

2

532

熨斗袋@noshi9114h

重み付き区間LISクエリが解決されていた、ただし重みなしの場合の美しい構造は特に役に立たなかったっぽくて悲しい

1

28

3,435

熨斗袋@noshi9114h

普通は演算に Θ(n) 掛かってダメなんだけど、なんと LIS の性質からこのマージにおいて single crossing 性が成り立つので、2つの配列で大小関係が切り替わるポイントを見つけてくっつけるだけでいいということになり、列を永続セグ木で持つことで Θ(log n) でマージできてしまう (完)

1

8

757

熨斗袋@noshi9114h

かなり競プロだったなあ

5

653

熨斗袋@noshi91Nov 11

僕のAIはrandom thinningとかいう謎の手法で曲芸みたいな解析を始めたんだけど助けて

7

1,020

熨斗袋 retweeted

@tatyam_primeNov 11

AI は部分木の {min, max} を持たせて枝刈りしろと言っています

3

1,091

熨斗袋@noshi91Nov 11

悲しい

1

619

熨斗袋 retweeted

toomer@toomerhsNov 11

3乗の下界があって、min/max で早期終了する split なら2乗になるらしい

3

677

熨斗袋@noshi91Nov 11

Treap の union: 根のうち priority の高い方を選び (これが完成する木の根となる)、他方をその key で split する。左右を再帰的に union する。問: このアルゴリズムは split 後の merge で Θ(log(n)²) 掛かってしまうが、自然なアルゴリズムでこれを回避できるだろうか？

6

1,242

熨斗袋@noshi91Nov 11

Treapのunion (split 含む操作列) の償却計算量解析、何年も前から気になっていたのでAIに投げたところ、log^3 N までしか抑えられずモヤモヤ続行ということになった。少なくとも shift が無ければ 1 乗、どんなに譲っても 2 乗にはなると思うんだけどなあ速すぎるから

1

15

2,807

熨斗袋@noshi91Nov 11

交互ブロックを切り出していく方が速いとか、アルゴリズムの綺麗さに差がありすぎて許せないだろ。あと最終的に出来上がる木の構造からして素朴な union が理論値すぎるように見える

1

1

820

熨斗袋@noshi91Nov 11

左右に切り離してmergeを繰り返すだけで2乗になるの忘れてたわ。これ上手く処理できるシンプルなunionあるのかな

1

570

熨斗袋@noshi91Nov 8

ある程度自由度がある順列の数え上げで準線形要求な時点で有向木にならないわけないだろという反省をした

12

1,238

熨斗袋@noshi91Nov 8

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

1

13

2,845

熨斗袋@noshi91Nov 8

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

1

836