
mis.w54/traP24M 浅野-早大機航-科学(東工)大数理計算-社会 データ構造を志す AtCoder,codeforces : hotman78 (黄橙反復勢...) アイコン:@yuchemisw
- Tweets25.7K
- Following2.8K
- Followers2.2K
- Likes103K

ALT We give a deterministic algorithm for exact modular subset sum that, for every modulus m, computes all reachable residues and one requested witness in O(m) time and O(m) auxiliary words. The input is a compact list of distinct residues with multiplicities, and the word-RAM supports constant-time modular arithmetic. The algorithm represents reachable residues as intervals along cycles of repeated addition, charging work on partial cycles to newly reached residues. Processing prime factors in increasing order keeps the cost of rebuilding and changing cycles linear. A classical theorem on subset sums of distinct invertible residues bounds the number of boundary lists by O(m⁽3/4)); together they contain O(m) interval endpoints. Comparison sorting the short lists and radix sorting the long ones then takes O(m) total time. The algorithm is fast in practice, using arrays and interval lists rather than heavy data structures.

ALT We study fair division of indivisible goods when agents' valuations are accessed only through ordinal comparisons between bundles, with arbitrary tie-breaking. In this model, even deciding whether a given allocation is envy-free up to one good (EF1) can be impossible. This suggests explicit fairness certificates as a natural algorithmic object. Our main contribution is a certificate-preserving scaling framework, which recursively contracts goods, solves a smaller instance, and expands the solution while repairing an explicit envy-eliminating witness certificate. For arbitrary identical monotone valuations, this yields a certified EF1 allocation for n agents and m goods using O(n log n log(m/n)) comparison queries, within an O(log n) factor of the Ω(n log (m/n)) communication lower bound. For identical additive valuations, we additionally obtain a 1/2-MMS guarantee within the same query complexity. For non-identical additive valuations, exploiting our EF1+1/2-MMS algorithm, we accelerat






















