コンテスト中AC:A〜D
コンテスト後にFを自力ACしました。
D - Neighbors
問題文の条件は簡単ですが、判定法に抜けなどがあり、WAをたくさん出しました。
問題文の条件を満たすかどうかの判定は以下のようになります。
整数を頂点とし、と
に無向辺が存在するグラフとみなした時(連結とは限らないことにも注意)、
・次数が3以上の頂点があればNo
・閉路があればNo（最初これが抜けてWA量産しました）
・以上2つを満たさなければYes
次数3以上かは各頂点の辺の数を調べれば分かります。
閉路判定は各連結成分に対して、DFSを行い、訪問済みの頂点にぶつかるか調べれば良いです。
(別の問題で、DFSして頂点数Vと辺数Eを調べ、V-1=Eが成立するか調べる方法もありました)
特殊な形をした森であるか判定する問題と言い換えても良いかもしれません。
F - Jealous Two
高橋くんがi番目、青木くんがj番目のプレゼントをもらった場合、満たすべき条件は、
かつ
です。
を基準として昇順ソートしておくと、
なら
が成立します。
この時、にのみ着目でき、既に出現したものの中で
であるjをカウントする問題となり、これは一見Binary Indexed Tree(BIT)で反転数を求める手法で求められそうです(
を配列としてもつために前処理として座標圧縮は必要なので、以下座標圧縮されているとします。)。
(反転数を求める方法を使うABCの過去問題の記事。ネタバレ注意)
しかし、実はと
が等しい場合、iを高橋くんに、jを青木くんにプレゼントするという順序を入れかえることができてしまい、単純に出現順で計算しても誤った答えになってしまいます。
そこで、自分の解法と公式解説の3パターンを載せておきます。
自分の解法
を第一キー、
を第二キーとして昇順ソートします。
を満たすjについては、BITで反転数を求める方法で求めます。
の時は、iとjの大小関係は無いものとして、
・であるjの区間[l,r)を二分探索によって求める
・[l,r)内で、以上となる
の個数を二分探索によって求める
ことで、計算しました。
実装上、気をつける点として、反転数を求める場合はの出現数を+1する処理がありますが、これは
が同一である区間が終わってからまとめて行います。
公式解法
を第一キーとして昇順に、
を第二キーとして降順にソートします。
こうすると、であっても、
なら、通常の反転数を求めように計算できます。
の時の対処は、事前にランレングス圧縮しておけばよいです。
ランレングス圧縮すると、なら
が成立し、通常の反転数を求める方法が適用できます。
反転数を求める操作で得られたjの個数に対して、組の要素の個数を掛ければよいです。
ユーザ解説(Wavelet Matrix)
このユーザ解説によれば、ウェーブレット行列によっても計算できるようです。
過去に実装したもので解いてみました。
を二次元座標上の点
とみなします。
するとこの問題は、各iについて、
かつ
を満たす長方形領域の座標上の点をカウントする問題となります。(但し、は
のうち最小のもの)
これはウェーブレット行列によって、実現できます。
をキーに組
を昇順ソートしておくと、
・二分探索によって、を満たすjの範囲[l,r)を求められる。
・[l,r)の範囲で、を満たすjの個数をウェーブレット行列のrangefreq関数により、求める。
ことができます。(には
など、Bのどの要素よりも大きい値を設定する)