https://teapaw.org/t.co/cjjnd793B5 お気軽に unfollow してください。 その他のアカウント: @noshi91s @noshi91_locked
Joined June 2018
- Tweets49.5K
- Following755
- Followers2.7K
- Likes162K
熨斗袋 retweeted
Subset Sum in Almost-Linear Time
Ce Jin, Xiao Mao
arxiv.org/abs/2610.20742 [𝚌𝚜.𝙳𝚂]
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 Õ(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.
熨斗袋 retweeted
A list of tasks for which LLMs (mostly GPT-6 Pro) have found solutions significantly better and non-trivially different from the authors’ solutions: qoj.ac/blog/qingyu/blog/4412
The list is still being updated, and I'll mark all solutions I find particularly interesting.
熨斗袋 retweeted
修論の時やってたPCP[3,4]というパズルゲーム、２問だけ残ってたんですが、GPT-6-Astra が上手な探索を書いた結果解けました。驚き。
これにて3170インスタンス全部解決され、Isabelleでの証明も付与された。
github.com/Mojashi/pcp-3-4-p…
最小解はまだ不明
熨斗袋 retweeted
arxiv.org/abs/2609.01365
新作出ました！
すべての入力文字列を部分文字列として含む最短の文字列を求める最短超文字列問題において、単純な貪欲法の解が最適解の2倍より長くなることはない、という約40年間未解決だった予想に対し、（AIの力を借り）初の反例を与えることで予想を解決しました。
熨斗袋 retweeted
AtCoder で組合せゲーム 24 題を開催します！！9/26 (土) の 13:00-18:00 を予定しています
atcoder.jp/contests/game-24
組合せゲームの基礎的・教育的な問題を多く扱っています、発展的な問題もいくつか入れています
ぜひご参加ください！
熨斗袋 retweeted
はてなブログに投稿しました
ARC227の秘密 - よすぽの日記 yosupo.hatenablog.com/entry/…
#はてなブログ
熨斗袋 retweeted
このブログの問題も面白かったです
問題概要
・N×M行列がある。
・クエリをQ回処理し、最終的な行列を出力せよ。
・転置する。(i,jにあった要素をj,iに写す)
・NM=KLなるK,Lが与えられるので、上から下、左から右に読んだ数列が変わらないようにK×L行列にする
熨斗袋 retweeted
1/5 Oh wow. GPT-5.6-Sol seems to be on a whole other level. In just three weeks, it seems to have made nontrivial progress on 10+ problems in social choice. Exciting! (But I'm still processing what the existence of such a model means for research.) A snapshot:
熨斗袋 retweeted
初投稿です
競技プログラミング日本1位のコンテスト実況【Codeforces Spectral::Cup 2026 Round 3】 youtu.be/nFccb7H8Ap8?si=p26u… @YouTubeより
熨斗袋 retweeted
【AtCoder Algorithm Lectures 公開のお知らせ】
「AtCoder Algorithm Lectures」を公開しました。
競技プログラミングの理論やテクニックを解説する講座です。
今後も講座を拡充し、質の高い学習コンテンツの提供を目指します。
info.atcoder.jp/entry/algori…
熨斗袋 retweeted
The Li-Chao Tree: Algorithm Specification and Analysis
Chao Li
arxiv.org/abs/2603.07948 [𝚌𝚜.𝙳𝚂 𝚌𝚜.𝙲𝙶]
