非想定解あるある、制約のせいで逆に迷った。 問題概要 atcoder.jp 考えたこと 今回は 1-indexed で考えた方が圧倒的にわかりやすいのでそのように統一する。 箱の色容量 色 $ i $ のボールを $ j $ 番目の箱に $ j $ 個入れる操作を「 $ 1 $ 色入れる」と定…

困ったときの平方分割。 問題概要 atcoder.jp 考えたこと 要素の総和が $ k $ の"素晴らしい整数列"の個数を $ f (k) $ とする。 また、このうち最後の要素が $ x $ であるものの個数を $ f _ x (k) $ とすると、 $$ f _ x (k + x) = f(k) - f _ x (k) $$ が…

問題概要 atcoder.jp 考えたこと なんとなく、親ノードに遡りながら状態をまとめていけばよさそう。 当初、特殊辺を二つの木に対して同時に親ノード側に伸張することを考えたが、二つの特殊辺が片方の木でのみ接続するパターンに対する数え上げパートが原因…

kyokkounoite.hatenablog.jp 前回の続き。テンプレート化したアルゴリズムたちを毎回コピペするのは面倒なので自動化した。 target C++er Visual Studio Code environment example MSYS2 atcoder-tools 筆者は Visual Studio Code の Workspace Folder 以下…

自分好みの環境構築で全部まとまってる記事は自分で作るしかない。 target (OS: Windows) MSYS2 MinGW64 GCC Git Visual Studio Code atcoder-tools install MSYS2 (参考) MSYS2の導入 - 東京大学工学部 精密工学科 プログラミング応用 I・II Windows10の開…

問題概要 （筆者は問題を要約することに疲れたようです） atcoder.jp 考えたこと $ X_i $ の範囲を絞る $ L_i \leqq X _ {A_i} + X _ {B_i} \leqq R_i $ に着目する。 $ X_i $ のとり得る範囲を $ L ^ X _ i \leqq X_i \leqq R ^ X _ i $ とする。 仮に $ X …

結論から言うと、クエリ平方分割で O(N√Q log(max {A}) + Q(√Q + logQ)) で解けます。 問題概要 atcoder.jp 考えたこと クエリ 1 が曲者で、通常の遅延セグメント木には乗せられないため、仕方なく「困ったときの平方分割」をしてみる。 √Q 回のクエリを 1 …

着想は公式解説とほぼ同じなのでかなり簡潔に記します。 問題概要 atcoder.jp 考えたこと 掃き出し法っぽい操作ができればよい。 A_i を区間 [i, i] であると考えて A(i, i) とする。 (k-1)-bit 目まで全て 0 であるような A(l, r) について、r の小さい順に…

筆者は（一応）文系なので、数学的な記法、特に集合に関する記法については誤りを含んでいる可能性があります。 ニュアンスで汲み取ってください。 致命的な誤用がある場合はコメントやツイッターで教えてほしいです。 問題概要 $ 2N $ 個のピースからなる円…

問題概要 まとめるのが面倒なので割愛。 atcoder.jp 考えたこと 直前の行に対して、各ピースが下に凸であるかを状態にもつ DP でできそう。 ただし、遷移させるときに四辺が凹のピース（以下、Concave）と四辺が凸のピース（以下、Convex）をそれぞれいくつ…

C++ で競プロ用で良い感じの実装をしてる人が見つからなかったのでここに置いておきます ( が、使用頻度はかなり少ないと思います ) 。 アルゴリズム概要 ja.wikipedia.org トライ木の一種。 通常のトライ木は単一の文字によってラベリングされているが、パ…

問題概要 $ 1 \leqq N \leqq M $ となる整数 $ N $ について、$ K $ で割った余りと、$ 10 $ 進法表記での各桁の和を $ K $ で割った余りが一致するような $ N $ の個数を求めよ。 制約 : $ 1 \leqq K \leqq M \leqq 10^{10} $ 考えたこと $ i $ を $ 1 $ ず…