自分が作問し 2023 年に公開された問題を振り返り、 upsolve を勧誘する記事です。 ICPC 2023 国内予選 D 「効率的な問題セット」（原案のみ） オンラインジャッジ： https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1667&lang=ja 大昔から作問…

AtCoder Library (ACL) の atcoder::lazy_segtree をもとにした Segment tree beats の抽象化の方法と，そのいくつかの具体的な使用例を紹介します．Segment tree beats は列に対する複雑な更新・取得処理を高速かつオンラインに実現する強力な手法ですが，…

問題 \(O(N^3) \) 解（執筆時点で Fastest AC）です． 解法 連結グラフの場合だけを考えます（それ以外の場合は連結成分毎に行列木定理を適用することでもともと \( O(N^3) \) で解けるので）．このとき，問題は「 \(N \) 頂点の単純連結無向グラフが与えら…

問題 思考の過程が想定解と違ったので．（追記）答えは合うのですがかなり怪しいところがあるので，正当性の証明（または反例）を募集しています． 解法 長さ \(2^N\) の配列同士の (bitwise) OR convolution: $$ (f \ast g)[i] = \sum_{(j | j') = i} f[j] …

atcoder.jp まず，問題を言い換えて状況を整理する．のランプに加え，最初から個のランプも点灯しているとみなし，うまい操作によって全てのランプを消灯させられるようなを求めればよい． ここで，「点灯しているランプのうち最大のy座標」が小さくなるよう…