2021-04-09

ABC174 F - Range Set Query

ABC DP高速化典型競技プログラミング解説

Mo's algorithmを用いた方法を説明します．

問題はこちら

問題概要
解説
提出プログラム
感想

問題概要

長さ ${N}$ の数列に関して「 ${l_i}$ 番目から ${r_i}$ 番目までに含まれる数の種類を求めよ」という ${Q}$ 個のクエリに答えよ．

${1\leq N,Q \leq 5×10^5}$

解説

Range Set Queryという名前とか数列の区間に対するクエリとかからSegmentTreeを使いそうだが，区間のマージ操作に時間がかかってしまい無理．

以下の条件を満たすときMo's algorithmというものが使える．

更新クエリがない
${[l,r)}$ の答え(状態)から ${[l±1,r),[l,r±1)}$ の答え(状態)が高速に計算できる．
オフラインで処理できる．

※「オフラインで処理できる」とは ${[l,r)}$ の答えを求めるクエリに答える順番は関係ない、という感じです．答えを求めるクエリの間に更新クエリがあるとこれができなくなります．(2022/01/08 追記)

今回の問題はこれを満たしているのでMo's algorithmが使える．

Mo's algorithmの考え方について説明する．
${[l,r)}$ のクエリがある場合に ${(l,r)}$ に点をプロットしたような二次元平面上を考える．

入力例 ${2}$ での例

このように考えることにより， ${[l,r)}$ から ${[l±1,r),[l,r±1)}$ への変化が二次元平面上で上下左右に ${1}$ 移動することとみなせる．

この移動を繰り返し，全点をできるだけ少ない移動で訪れる巡回セールスマン問題のようなものになる．

ここで， ${L}$ (横軸)を ${K}$ 分割し(二次元平面を縦に切る)，分割されたグループごとに順に訪れることにすると， ${R}$ (縦軸)方向の移動回数は ${1}$ つのグループにつき ${O(N)}$ ，グループ内で ${L}$ 方向の移動回数は点ごとに ${O(N/K)}$ (1つのグループの ${L}$ 方向の長さが ${O(N/K)}$ )であるから，上下左右に ${1}$ 移動する操作が ${O(T)}$ でできるとすると全体の計算量は ${O(TN(Q/K+K))}$ となる．これを最小にするような ${K}$ は ${\sqrt{Q}}$ なので ${\sqrt{Q}}$ 分割することにより ${O(TN\sqrt{Q})}$ で解くことができる．

今回の問題は ${O(T)=O(1)}$ なので ${O(N\sqrt{Q})}$ で解くことができる．これでもC++などの高速な言語なら間に合う．移動の仕方として，すべてのグループで ${R}$ の昇順に訪れるのではなくて，昇順に訪れるグループと降順に訪れるグループを交互に(蛇行するように)すると速くなる．

入力例 ${2}$ での例(緑がグループの境界，初期状態は ${[1,1)}$ )

また，ヒルベルト曲線を用いると定数倍速くなるらしい(なんで？)
https://codeforces.com/blog/entry/61203

マンハッタンTSPの2近似アルゴリズムもやってみたが，所詮2近似なので遅かった．

他のMo's Algorithmを使う問題は以下にまとめてます。
kanpurin.hatenablog.com

提出プログラム

https://atcoder.jp/contests/abc174/submissions/21564578
https://atcoder.jp/contests/abc174/submissions/22161351 ヒルベルト曲線
https://atcoder.jp/contests/abc174/submissions/26267842 三角形バージョン

巡る順番を決めるフェーズはそんなに重くないので上の三つ全部調べて一番更新回数が少ないものに決めるのもいいかも

感想

巡回セールスマン問題の近似解法とかをうまく使ったらもっと速くなりそう．計算量のオーダーじゃなくて答えのオーダーを評価する必要がある．

2021-03-28

ABC197 F - Construct a Palindrome

ABC グラフ典型文字列競技プログラミング解説

問題はこちら

問題概要
解説
提出プログラム
感想

問題概要

${N}$ 頂点 ${M}$ 辺の連結無向グラフの各辺に英小文字が ${1}$ つ書かれている．頂点 ${1}$ から頂点 ${N}$ までのウォークのうち，通った辺に書かれた文字を順に並べると回文となるようなものの回文の長さの最小値を求めよ．

${2\leq N \leq 1000\\ 1\leq M\leq 1000}$

解説

回文の性質(というか定義)と，始点・終点が固定という条件からいろいろ考えてみると， ${1\rightarrow N}$ が回文になっているなら ${1\rightarrow v}$ と ${N\rightarrow v}$ が等しいような頂点 ${v}$ が存在するか， ${1\rightarrow u}$ と ${N\rightarrow v}$ が等しいような隣接する頂点 ${u,v}$ が存在する，ということがわかる(逆も言える)．

頂点 ${1}$ と頂点 ${N}$ から同じ文字が書かれた辺を，上の条件を満たすまで辿ればとりあえず回文になる．

同時に辿って行くのは難しいので，二つの頂点を( ${(1,N)}$ のように)一つの頂点にまとめるようなグラフを作ることで，同じ文字が書かれた辺の対ごとに新たなグラフに辺を張ればいい．

例：元のグラフで ${a,b}$ 間の辺と ${c,d}$ 間の辺に書かれた文字が同じ場合，新たなグラフでは ${(a,c),(b,d)}$ 間， ${(a,d),(b,c)}$ 間に辺を張る．

元のグラフで ${a}$ から ${b}$ に， ${c}$ から ${d}$ に行くことは新たなグラフで ${(a,c)}$ から ${(b,d)}$ に行くことに対応する．
同様に，元のグラフで ${a}$ から ${b}$ に， ${d}$ から ${c}$ に行くことは新たなグラフで ${(a,d)}$ から ${(b,c)}$ に行くことに対応する．

このようなグラフでの ${(1,N)}$ から ${(v,v)}$ や ${(u,v)}$ ( ${u,v}$ は隣接する) までの最短距離を求める問題になる．同じ文字が書かれた辺の対に張られた辺(例の ${(a,c),(b,d)}$ 間など)のコストを ${2}$ ，新たに頂点 ${G}$ を作り， ${(v,v)}$ から ${G}$ にコスト ${0}$ の辺を張り， ${(v,u)}$ から ${G}$ にコスト ${1}$ の辺を張ることで， ${(1,N)}$ から ${G}$ への最短コストが答えとなる．

提出プログラム

感想

連結って条件いる？アルファベットサイズも関係なさそう．

2021-03-26

ABC196 C - Doubled

ABC 解説競技プログラミング

${O(\sqrt{N})}$ 解法， ${O(\log{N})}$ 解法， ${O(1)}$ ？解法について解説します．

問題はこちら

問題概要
解説
提出プログラム
感想

問題概要

${1}$ 以上 ${N}$ 以下の整数 ${x}$ のうち，先頭に余分な0をつけない十進表記で偶数桁であり，前半と後半が文字列として一致するようなものは何個あるか．

${1\leq N < 10^{12}}$

解説

O(√N)解法

${x}$ を ${1}$ から ${N}$ まで全探索するのは間に合わない．この全探索では，各 ${x}$ について「前半と後半が文字列として一致する」という条件を満たすか調べる必要がある．そこで，そもそもこの条件を満たしている ${x}$ について探索を行うことができれば探索範囲を削減できる．前半と後半が等しいので，前半を決めることで条件を満たす ${x}$ のみについて全探索を行うことができる．

O(logN)解法

${O(\sqrt{N})}$ 解法の ${x}$ の探索において「 ${x\leq N}$ であるか？」の真偽が単調であることを利用して二分探索を用いることで最大の ${x}$ を求めることができる．

O(1)？解法

${O(\log{N})}$ 解法において最大の ${x}$ は，

${N}$ の長さが ${1}$ の場合， ${0}$ (例：3 -> 0)
${N}$ の長さが ${1}$ でない奇数の場合， ${99\cdots 9}$ (例：3141592 -> 999)
${N}$ の長さが偶数かつ「前半の数 ${\leq}$ 後半の数」の場合，前半の数字 (例：31415926 ->3141)
${N}$ の長さが偶数かつ「前半の数 > 後半の数」の場合，前半の数字-1 (例：314159 ->313)

提出プログラム

https://atcoder.jp/contests/abc196/submissions/21262672 ${O(\sqrt{N})}$ 解法
https://atcoder.jp/contests/abc196/submissions/21262749 ${O(\log{N})}$ 解法
https://atcoder.jp/contests/abc196/submissions/21262571 ${O(1)}$ ？解法

感想

本当にO(1)か怪しい

2021-03-07

ABC194 E - Mex Min

ABC データ構造解説競技プログラミング

問題はこちら

問題概要
解説
提出プログラム
感想

問題概要

長さ ${N}$ の整数列 ${A}$ が与えられる． ${A}$ の連続する長さ ${M}$ の区間すべてについてのmexのうち最小値を求めよ．

${1\leq M\leq N\leq 1.5×10^6}$

解説

最初の区間についてmexを求めた後，区間をずらしながらすべての区間についてのmexを求める．区間をずらすとき，変化するのは区間の端の数のみ．したがって区間中の整数の数は区間ごとに ${O(1)}$ でカウントできる．

mexは整数の集合により値が決まるのでsetうまく管理することで求めることができそう．

${\downarrow}$

現在の区間の整数の集合を ${S}$ とする． ${S}$ の連続する整数の端をsetで持つ．

例として ${S=\{1,2,3,4,6,8,9\}}$ とするとsetの中身は ${1,4,6,8,9}$ となる．

f:id:kanpurin:20210307023027p:plain

${S}$ に整数を追加する場合

以下の図のように区間を隣り合った区間を接続する．隣に区間が無いなら追加した整数が区間の端になる．

f:id:kanpurin:20210307023955p:plain

${S}$ から整数を削除する場合

以下の図のように区間を分割する．削除する整数が区間の端である場合も同様に行う．

f:id:kanpurin:20210307024346p:plain

${S}$ のmexを求める

${0}$ がない場合は ${0}$ が答え．

${0}$ がある場合は ${0}$ を含む区間の右端の整数 ${+1}$ が答え．

ほかにも

上の解法のほかにもっと簡単なものとしてsetに ${0}$ から ${N}$ までをつっこんで ${S}$ の整数をsetから削除する．このときset内の最小の整数が答えとなる．全部つっこむ分，上の解法より遅いが間に合う．

どちらも計算量は ${O(N\log{N})}$

公式解説ではmexとminの性質を用いて直接答えを求めていた．本解説の手法だと計算量は悪くなるがmexの列挙ができる．

提出プログラム

https://atcoder.jp/contests/abc194/submissions/20738573
https://atcoder.jp/contests/abc194/submissions/20740038

感想

問題文から素直な考え方で導かれる解法の解説を行った．実装は重くなるがいろいろ応用できそうな解法だと思う．

2021-02-27

ABC193 F - Zebraness

ABC 典型競技プログラミング解説グラフ

問題はこちら

問題概要
解説
提出プログラム
感想

問題概要

${N×N}$ のマス目が白か黒に塗られており，塗られていないマスもある．塗られていないマスを白か黒で塗るとき，隣り合ったマスが異なる色で塗られているようなマスの組の数の最大値を求めよ．

${1\leq N\leq 100}$

解説

隣り合ったマスに異なる色を塗った場合1点得るというように考える．

${\downarrow}$

以下の条件で利得の最大化を行うことになる.

まだ塗られていないマス ${(i,j)}$ を白で塗る．
まだ塗られていないマス ${(i,j)}$ を黒で塗る．
隣り合ったマスに異なる色を塗ると ${1}$ 点得る．

${\downarrow}$

白/黒で塗るという選択と, 複数の選択の間に対する制約(罰則条件)があるのでProjectSelectionProblem(俗にいう燃やす埋める問題)を解くアルゴリズムを使えそう.
ProjectSelectionProblemについてはこちら

上の条件は利得になっているのでProjectSelectionProblemに対応させるため損失に書き直す.

白が塗られているマス ${(i,j)}$ を白で塗ると, ${0}$ 点を失う．
白が塗られているマス ${(i,j)}$ を黒で塗ると, ${\infty}$ 点を失う．
黒が塗られているマス ${(i,j)}$ を白で塗ると, ${\infty}$ 点を失う．
黒が塗られているマス ${(i,j)}$ を黒で塗ると, ${0}$ 点を失う．
まだ塗られていないマス ${(i,j)}$ を白/黒で塗ると, ${0}$ 点を失う．
隣り合ったマスに異なる色を塗ると ${1}$ 点失う．

隣り合ったマスの組の数からこれの解を引けば答えになる．また， ${i+j}$ が偶数のときと奇数のときで白/黒の選択を表す辺の並びを変える必要がある．

例として隣り合った「黒に塗られたマス」と「塗られていないマス」の状況をグラフで表すと以下のようになる. 頂点 ${A}$ が既に黒に塗られたマスを表し, 頂点 ${B}$ がまだ塗られていないマスを表す.

このグラフのSからTへの最大流が答え．容量0の辺はどうせ流れないので張らなくてもいい．

燃やす埋める問題に関する基礎知識は以下の記事を参考にしてください．
kanpurin.hatenablog.com

ProjectSelectionProblemの他の問題は以下にまとめています．
kanpurin.hatenablog.com

提出プログラム

https://atcoder.jp/contests/abc193/submissions/20555264

感想

AtCoderでProjectSelectionProblemは解いたことなかった(忘れてるだけor精進足らず)のでおもしろかった．

追記
普通にありました．(ネタバレ回避のため載せませんが)

2021-02-26

ABC172 D - Sum of Divisors

ABC 典型式変形競技プログラミング解説数論

問題はこちら

問題概要
思考の流れ
提出プログラム
感想

問題概要

整数 ${X}$ に対し，正の約数の個数を ${f(X)}$ とする． ${\displaystyle\sum_{K=1}^{N}K×f(K)}$ を求めよ．

${1\leq N\leq 10^7}$

思考の流れ

正の約数の個数は，素因数分解や約数を列挙することによって ${O(\sqrt{N})}$ で求まる． ${1}$ から ${N}$ に対してこれを行うと ${O(N\sqrt{N})}$ かかる．

${\downarrow}$
実際に約数の分布をみてみる．横の数字が ${K}$ で約数に〇をかいた．

f:id:kanpurin:20210226104023p:plain

この図を横ではなく縦に見ると，上に書かれた数ごとに〇がかかれている．
つまり，上に書かれた数の倍数の和 ${\displaystyle\sum_{A=1}^{N}\sum_{B=1}^{\left\lfloor\frac{N}{A}\right\rfloor}A×B}$ が答え．

これは2重ループでそのまま書いても ${O(N\log N)}$ ，等差数列の和の公式を用いると ${O(N)}$ となる．

また， ${\displaystyle\sum_{K=1}^{N}f\left(\left\lfloor\frac{N}{K}\right\rfloor\right)}$ を ${O(\sqrt{N})}$ で求める手法を使えば高速に解ける．

計算方法は以下の記事に書いてる．

kanpurin.hatenablog.com

他にも， ${f(K)=\sum_{m|K}1}$ であるから約数におけるゼータ変換を用いることで ${O(N\log{\log{N}})}$ でも解ける．

参考：https://qiita.com/convexineq/items/afc84dfb9ee4ec4a67d5

提出プログラム

https://atcoder.jp/contests/abc172/submissions/20489255 ${O(N)}$
https://atcoder.jp/contests/abc172/submissions/20489357 ${O(\sqrt{N})}$

感想

${N\leq 10^{12}}$ でも解ける．

2021-02-21

yukicoder No.1400 すごろくで世界旅行

yukicoder 解説競技プログラミンググラフ DP高速化データ構造

問題はこちら

問題概要
思考の流れ
提出プログラム
感想

問題概要

${V}$ 頂点の重み無し有向グラフの隣接行列が与えられる．任意の頂点 ${i}$ から任意の頂点 ${j}$ までちょうど ${D}$ 本の辺を辿って行くことのができるか判定せよ．

${1\leq V\leq 2000\\ 1\leq D\leq 10^{18}}$

思考の流れ

yukicoder No.1340 おーじ君をさがせとほぼ同じ問題だから行列累乗で終わりと思いきや制約がきつい．

${\downarrow}$

きつくてもゴリ押す．bitsetを用いると，64倍くらい高速になるらしい．また， ${2V}$ 回の移動でたどり着けないようなところは ${D}$ 回の移動を行ってもたどり着けない．だから ${D\leftarrow\min(2V,D)}$ として計算する．計算量は公式解説の計算量に ${\log}$ がつくくらい．かなりギリギリ(現在(2021/02/21)のAC者のなかで)最遅．C/C++以外なら通らないかも

提出プログラム

https://yukicoder.me/submissions/620993

感想

テストケース追加されたら落とされそう．まだ大した高速化してないから追加されても高速化すればいいかも．

ほぼ下位互換のNo.1340より星が少ないってマジ？