2025-01-03

ABC082 D - FT Robot Next-DP 解法

Next-DP よくわかってないのでもしかしたら違うかも．
問題リンク D - FT Robot

解法

まず，前処理として $S$ を $\lbrace x軸とy軸どちらと平行に動くか,移動する回数 \rbrace$ というペアの列にランレングス圧縮します．次に，配列 $\mathrm{dp}$ の値 $\mathrm{dp}_{x,y}$ を，座標 $(x,y)$ に到達できるかの bool 値と定めます．すると， $i$ 回目の移動で到達しうる座標は前に同じ向きで移動したときに到達しうる座標にのみ依存します．よって，RLE 配列を順に見ていき，Next-DP 配列に移動後に到達しうる座標を記録し $\mathrm{dp}$ の対応する次元の値を上書き，という操作を繰り返すことで最終的に到達しうる座標を求めることができます．RLE 配列のサイズは $O(|S|)$ 時間，移動による配列の更新も $O(|S|)$ 時間で行えるので全体として $O(|S|^2)$ 時間で答えを求めることができます．
提出コード (76ms) Submission #61342243 - AtCoder Beginner Contest 082

2024-12-11

JOI '11 本選 B - 古本屋 bitDP解法

解説することはあんまりないです．
問題リンク？ B - 古本屋 (Books)

解法

各ジャンルについて， $i$ 個売るときの買取価格の最大値は貪欲法で求まります．したがって， $dp_{i j}$ を(既に0冊以上売却したジャンルの集合が $i$ ，売却した総冊数が $j$ のときの買取価格の最大値)とすれば，bitDP によって答えを求めることができます．時間計算量はジャンルの種類数を $\sigma$ とすると $\mathrm{O}(N \log{N} + \sigma 2^{\sigma} N)$ となり， $\sigma=10$ なので定数倍に気を付けると AC できます．ちなみに，std::vectorを使うと TLE になります．

Submission #60653147 - 第１０回日本情報オリンピック本選（過去問）

2024-09-04

dequeで作る挿入削除 O(√N), 添字アクセスO(1)のset

急に思いついたので実装してみたらなんか速かった。

アイデア

集合の要素数の最大値が高々 $N$ であるとして, $\sqrt{N}$ 個の集合 $S_0, \dots, S_{\sqrt{N}-1}$ を次のようなルールにしたがって管理することを考えます。

各 $S_i$ の要素数は高々 $\sqrt{N}$ である。
$0 \le i \lt j \lt \sqrt{N}$ かつ $S_j \neq \emptyset$ なら $|S_i| = \sqrt{N}$ である。
$0 \le i \lt j \lt \sqrt{N}$ かつ $S_j \neq \emptyset$ なら $\max S_i \lt \min S_j$ である。

このとき、各 $S_i$ の最大値 $\max_i$ を持つことで挿入削除が $O(\sqrt{N})$ time、インデックスアクセスが $O(1)$ time で行えます。

insert

ルールより、 $\max_i$ は単調増加です。したがって、(挿入する要素の値) $\lt \max_i$ となるような最小の $i$ を二分探索し、これを $pos$ とします。
次に、 $S_{pos}$ に要素を挿入し、 $|S_{pos}| = \sqrt{N}$ となるまで以下の操作を行います。

$S_{pos}$ の最大値(dequeの末尾)をコピーし削除する。
$\max_{pos}$ を更新。
$S_{pos+1}$ の最小値としてコピーを挿入(dequeの先頭)。
$pos$ を1増やす。

挿入に $O(\sqrt{N})$ time、上記のループは1回あたり定数時間で高々 $\sqrt{N}$ 回行われるので $O(\sqrt{N})$ time です。

erase

insertと同様に二分探索して $pos$ を発見します。
次に、 $S_{pos}$ で削除を行い、 $|S_{pos + 1}| \lt \sqrt{N}$ となるまで以下の操作を行います。

$S_{pos+1}$ の最小値(dequeの先頭)をコピーし削除する。
$S_{pos}$ の最大値としてコピーを挿入(dequeの末尾)。
$\max_{pos}$ と $\max_{pos+1}$ を更新。
$pos$ を 1増やす。

insertと同様に $O(\sqrt{N})$ time です。

k番目の要素へのインデックスアクセス

ルールより要素は左詰めです。なので、 $S_{\left\lfloor{\frac{k}{\sqrt{N}}}\right\rfloor}$ の $(k \mod \sqrt{N})$ 番目の要素を返せばよいです。 $O(1)$ time です。

実装

実際には2べきの定数で分割しています。（何個か試したら 2¹¹ が一番速かった）
pairなどの std::numeric_limits<T>::max() が使えないような型を要素に使うときは inf の値を指定してください。

Submission #57429636 - AtCoder Regular Contest 033

とっぴんぱらりのぷう

2024-07-15

動的な Merge Sort Tree を作っちゃうぞ

Merge Sort Tree というデータ構造があります。 $n$ 要素の 静的な列 $a=(a_0, a_1, \dots, a_{n-1})$ に対し、次のようなクエリを処理できます。

$l, r, x$ が与えられるので、 $a_l, a_{l+1}, \dots, a_{r-1}$ に含まれる $x$ 以下の値の総和を求めよ。

atcoder.jp

$x$ 以下の総和なので、ソートされていれば累積和+二分探索で $O(\log n)$ 時間で求められますが、一般の場合はどうでしょうか。

これは、マージソートの過程（と累積和）をセグ木の形で持つことにより処理できます。

通常のセグ木と同様に、区間をすべて包含するノードまで降りる→クエリ処理（累積和+二分探索）の流れで解くことができます。
目的のノードに降りる操作、クエリ処理はどちらも $O(\log n)$ 時間かかります。よって構築 $O(n \log n)$ 時間、クエリ $O((\log n) ^2)$ 時間で問題を解くことができます。

提出コード
Submission #55233396 - Japan Registry Services (JPRS) Programming Contest 2024 (AtCoder Beginner Contest 339)

次に、こちらの問題を考えてみましょう。

$l, r, x$ が与えられるので、 $a_l, a_{l+1}, \dots, a_{r-1}$ に含まれる $x$ 以下の値の総和を求めよ。
$i, x$ が与えられるので、 $a_i$ の値を $x$ に変更せよ。

先ほどのように Merge Sort Tree で処理しようとすると、更新クエリごとに配列をリセットする必要があり計算量が大きくなってしまいます。
そこで、各ノードでどのように値が管理されていてほしいかを考えると、次のような要件が浮かんできます。

閾値以下の総和が高速に求められる（≒常にソートされた状態が保たれる）
値の重複を許す

実装が大変ですが、multisetを自作すればよいですね。

変更クエリはないですが、ちゃんと動きそうです

Submission #55641511 - Japan Registry Services (JPRS) Programming Contest 2024 (AtCoder Beginner Contest 339)

2024-05-24

【精進】ABC153 F - Silver Fox vs Monster

毎日自分のレート+400以上のdiffの問題を解きます。
問題リンク F - Silver Fox vs Monster

解法

座標順にソートした後、単純に前から順に「 $X_i$ が負ならcontinue, 正なら座標が $X_i$ から $X_i+2D$ の間にあるモンスターの体力に $H_i$ 以上の最小の $A$ の倍数を引く」という操作を行う。
座標が範囲内にある最大の添字は二分探索、体力の更新は遅延セグメント木を使えば $O(\log N)$ で処理できるので、全体で $O(N\log N)$ となる。

Submission #53801688 - AtCoder Beginner Contest 153

2024-05-23

【精進】ABC046 C - AtCoDeer and Election Report

毎日自分のレート+400以上のdiffの問題を解きます。
問題リンク C - AtCoDeer and Election Report

解法

投票数が満たすべき条件は「広義単調増加」かつ「比が $T_i:A_i$ 」
したがってi回目での投票数は
「 $(i-1)$ 回目の投票数以上の最小の $T_i$ の倍数 $÷T_i$ 」
「 $(i-1)$ 回目の投票数以上の最小の $A_i$ の倍数 $÷A_i$ 」
のうち大きい方を $(i-1)$ 回目の投票数にかければ良い。計算量は $O(N)$
Submission #53756132 - AtCoder Beginner Contest 046

2024-05-21

【精進】ABC073 D - joisino's travel

毎日自分のレート+400以上のdiffの問題を解きます。問題リンク D - joisino's travel

解法

$N\leq200$ という制約からワーシャルフロイド法 $O(N ^ 3)$ が見えてくる。町を訪れる順番は順列全探索で $O(R!)$ 、順番が決まれば移動距離の総和は $O(R)$ で求められるので、合計で $O(N^{3}+R R!)$ となりAC。
Submission #53721947 - AtCoder Beginner Contest 073