うまぴょい伝説 楽譜書いてみた

楽譜書きました．Aメロの音程無しの部分にも無理やり音を付けたのが，あんまりよくなかったかも．

楽譜のダウンロードはこちらです．
pdf:https://drive.google.com/file/d/15-dlXxAkLhkKpnqWk9Yp1lcmWoprqJjI/view?usp=sharing
music xml:https://drive.google.com/file/d/164EHHLJbmZv-kBDcjK9n7nVqHHbTaZ87/view?usp=sharing

 

 

すっごい久しぶりにはてなブログ見た...

ABC165参戦

ABC165に出れました。起きてたので出れました。
解説放送見ればよくね?そうだね なんで書いてるの?知らん

A - We Love Golf

  • A問題の制約なら、A以上B以下の数全部試せばいいやろ 終わり

atcoder.jp

B - 1%

  • そもそも最初問題の意味あんまり分かってなかった 日本語力の問題
  • 愚直には、×1.01とfloorを取るのを繰り返せばいい
  • 制約が1018なのが気になるけど...電卓で計算したら\displaystyle{\mathrm{log} _ {1.01}(10^ {16}) \lt 2000}だから愚直で大丈夫

atcoder.jp

C - Many Requirements

  • え、わからん(絶望)
  • DPも思いつかないし、グラフ等に直せる気配もない
  • 全部試すにしても、20C10って\displaystyle{\underline{10^ {10}}}くらいでしょ?(これ間違い)
  • D行こ

D - Floor Function

  • 1～Nまで試すのは当然ダメ
  • 凸関数になってるとか、何かそういう都合のいい性質があるのかな?例2の設定でx=1～100まで出力してみる
  • 結果どうも周期がありそうに見える、しかも周期がB -> 余りで変わるのか?
  • \displaystyle{x = Bp+q(0\leq q \lt B)}とおくと、([]はfloor)
\displaystyle{ \begin{align*} \left[\frac{Ax}{B}\right]-A\left[\frac{x}{B}\right] &= \left[\frac{ABp+Aq}{B}\right]-A\left[\frac{Bp+q}{B}\right] \\ &= Ap+\left[\frac{Aq}{B}\right]-Ap-A\left[\frac{q}{B}\right]\\ &= \left[\frac{Aq}{B}\right]-A\left[\frac{q}{B}\right] \end{align*} }
  • じゃあqを0からB-1まで動かせばいいな(Nにより多少変わる)
  • TLE&WAしました(Bの制約考えればそれはそう)
  • さっきの式をもう一回眺めると\displaystyle{[q/ B] = 0} つまり\displaystyle{[Aq/B]}だけ見ればいい そしてこれは単調増加

atcoder.jp

E - Rotation Matching

  • とりあえずおんなじ人が番号コロコロ変えると面倒
  • 番号変えるっていうルールをなくすと、
    • a vs b
    • a-1 vs b-1
    • a-2 vs b-2
    • ...
    • a-M+1 vs b-M+1 みたいな当たり方をすることになる(<=0,>Nはよしなに考える)
  • つまり何回目の試合だとしても「2人の対戦者の番号の差」は会場ごとに一定 なのでM個の会場で差がダブらないようにすればいい?

  • 例えば例2なら

    • 会場1:差1 (または6)
    • 会場2:差2 (または5)
    • 会場3:差3 (または4)

  • にしようとしたら、

    • 会場1:1 7
    • 会場2:2 6
    • 会場3:3 5

とかでもよさそう

  • 奇数の時はこんな感じでうまくいくけど、偶数の時が面倒

  • 例えばN = 10のとき、

    • 1 10
    • 2 9
    • 3 8
    • 4 7

とすると、差が3のペアが2つできる(2 9と4 7)

  • この場合は
    • 1 10
    • 2 9
    • 3 7
    • 4 6

みたいにちょっと値をずらさないといけない

  • この値の切り替え点とかパターン構築とかがめちゃくちゃ時間かかった

atcoder.jp

F - LIS on Tree

  • とりあえずわかりやすいように頂点0を根にしておく

  • "一直線の"数列のLISの求め方は

    • \displaystyle{A _ i}昇順で調べる
    • 各\displaystyle{A _ i}に対し、max{自分より前の位置でLISをすでに求めた項のLIS}+1を自分のLISとする

(蟻本に載ってる実家DPよりこっちの方が個人的に好き)

これを根～任意頂点\displaystyle{v}間の最短パス上の数列LISにしようとしたら、

  • \displaystyle{A _ i}昇順で調べる

  • 各\displaystyle{A _ i}に対し、max{自分から根のパス上の、自分より根に近い頂点の最大LIS}+1を自分のLISとする

  • この前書いたHLDで終わりやんけ!(当然皆さん私のHLDの記事は読みましたね?(傲慢))

  • 狭義単調増加なので、同じ\displaystyle{A _ i}を持つ頂点については、根から遠いものから見る(各頂点の深さは別にbfsで求めた)

  • 「う～んこれは勝ちでしょ!やっぱりHLDは偉大だn」
    AtCoderさん「WAです^^」

atcoder.jp

  • 全く原因がわからないし残り20分だったのでCに戻る

C - Many Requirements(再)

  • やっぱりうまい方法が見つからないけど、全探索....?あっ冷静に電卓したら1010もありませんね
  • 全パターン作って(105通りぐらいだった)、各数列についてMパターン確かめれば終わり

  • 全パターン作るには、

    • 長さNの配列V = {1,1,...,1}を用意
    • 以下をwhile(true):
      • 今のVの状態でd _ iの和を計算
      • Vの、Mでない一番後ろの要素の位置をnとする
      • \displaystyle{V _ {n}}を1増やし、\displaystyle{V _ {n+1},\cdots,V _ {N-1}}を\displaystyle{V _ {n}}でそろえる
      • (10進数の増え方を考えればまあ たまにやる処理のちょっと変形版みたいな)

atcoder.jp

ここで終了

F - LIS on Tree(再)

  • 上の手順で求められるのは、厳密には各頂点LISではなく「各頂点の\displaystyle{A _ i}が末尾に来る数列のLIS(☆)」
    本当に答えとなるLISを求めるには各頂点について、根までのパス上の頂点の(☆)を順に見ていって最大値を取らないといけない

atcoder.jp

〆

ひどいミスり方してしまって笑えん 道具が優秀でも使い手が下手ならうまく活かせない典型
明日取り帰すぞ～～

もう今日だった

はてなブログLaTeXで遊ぼう

数学

これは何

はてなブログのLaTeX(あるいはMathJax)で何ができるかの実験の記録です。何か見つけるたびに増えていきます。

LaTeXをMarkdownモードで書く(2020/04/25)

これが出来なきゃ始まらない。

別記事にまとめてます:

ano3.hatenablog.com

Markdownモードで独自マクロを使いたい(2020/04/25)

MathJaxのドキュメントのこのページとかこのページに従って、

MathJax = {
  tex: {
     macros: {
       RR: '{\\bf R}',
       bold: ['{\\bf #1}',1]
    }
  }
};

みたいなのをはてなブログの設定->ヘッダに置いとけばいいかな～と思ったのですが、ダメでした。macrosはおろか、他の設定も効かないように見えます。なんで?

ただし、各記事に対し個別にマクロを定義することはできそうです。あまりよろしくないですけど。

まずマクロ定義用の枠を、最初にマクロを使う場所の前に作ります。

<div align="center" style = "display:none;">[tex:
<!-- ここにマクロを置いていく -->
]</div>

この中で以下のようにマクロを定義します:

  • 引数無し:\def\名前{{ 内容 }}
  • 引数n個:\def\名前#1#2...#n{{ 内容(i個目の引数は#iとして書く) }}

「内容」の書き方は、\newcommandでのそれと一緒です。

例えば記事のどっかに次のように書くと、

\def\myrot{{\mathrm{rot}\,}} \def\myiint{{\int\!\!\!\!\int}} \def\mypd#1#2{{\frac{\partial #1}{\partial #2}}} 
<div align="center" style = "display:none;">[tex:
\def\myrot{{ \mathrm{rot}\, }}
\def\myiint{{ \int\!\!\!\!\int }}
\def\mypd#1#2{{ \frac{\partial #1}{\partial #2} }}
]</div>

それ以降の[tex:~]でこれらのマクロを使うことができます。こんなふうに

\displaystyle{ \myrot \\ \mypd{x}{t} }

\displaystyle{ \myiint }

<div align="center">[tex:\displaystyle{
\myrot \\
\mypd{x}{t}
}]</div>
[tex:\displaystyle{
\myiint
}]

〆

こんな記事書いといて何ですが、ガチの数学を書きたいなら、正直ローカルのLaTeXでPDFでも作ってここに貼るのが一番いい気がします。

ABC163バチャ参戦

競プロ

「ABC163は日曜日夜にちゃんと出るぞ!」と思っていたら寝過ごしました。アホですね。

「は～～こんなんどうやって手ぇ付けろっちゅうんねん」っていう問題たまにあるじゃないですか。そういう問題の解答を思いつくまでの脳内実況あってほしいなって僕いつも思ってるんです。そういうわけでこの記事を書いてます。誰かに役に立つといいね。

A - Circle Pond

  • 円周=2×半径×円周率 ちょっと誤差が怖いけど、πを長めに直書きして、setprecision(12)して小数点以下12桁ぐらい出力しておけばまあ大丈夫でしょう

(一回提出時の言語選択をミスって1CE食らいました。みんなは気をつけような。)

atcoder.jp

B - Homework

  • 結局宿題全部やるのには\displaystyle{A _ {1}+\cdots+A _ {M}}日かかるので、これがNより大きければ無理ね
  • 空いた日はNから引けばいいか

atcoder.jp

C - management

  • 木じゃん で「社員番号1以外には上司がいる」ってことは社員1が根ね
  • 直属の上司が木で言う親で、直属の部下は木で言う子だね いつもみたいに自作の木のクラス持ってきて構築すれば...
  • や、求めるだけでいいのね なら自分が出てきた回数が子の数ってことでvectorでカウンタ持っとけばおｋ

atcoder.jp

D - Sum of Large Numbers

  • すげえでかい数字来たな
  • とりあえずk個だけ取った時の和の個数はどうなるかな?
    一番小さい和が\displaystyle{\sum _ {i=0}^ {k-1}(10^ {100}+i)=k\times 10^ {100}+\frac{1}{2}k(k-1)}で、
    一番大きい和が\displaystyle{\sum _ {i=N-k+1}^ {N}(10^ {100}+i)=k\times 10^ {100}+\frac{1}{2}k(2N-k+1)}か
    でもってこの間の数は全部とれる(昔似たパターン見たからパッて出た)から、\frac{1}{2}k(2N-k+1)-\frac{1}{2}k(k-1) (☆)通りね。
  • これは10^ {100}が大きすぎて、kでの和の範囲とk+1での和の範囲がかぶることは絶対ないね(kは高々10^ 5程度なので二乗しても10^ 10)
    ということは(☆)を素直にk=K～N+1で足していけばよさそう

atcoder.jp

E - Active Infants

  • え、これ一回読んだけど、手でやる方法すらわからん、どうすりゃいいんだこれ 大きい数字を遠くにやった方がいいことしかわからん

  • 先にF読んじゃお～～(Fへ)

F - path pass i

  • 「色kの頂点を一度以上通るような単純パスの数」、だったら逆に「一度も通らない単純パスの数」を求めたいね
  • 単純パスって結局、はじめと終わりで一通りになっちゃう ということは単純パスの数って結局、端点になりうる頂点の数から求められる まずはそれが求めたいね
  • まず線状の場合は?

  • (ぐじゃぐじゃ～ってしてるやつらは同じ色)ぐじゃぐじゃの間に4つ頂点があるから、4C3+4で10通り

  • この場合は?...ぐじゃぐじゃの間には色なし頂点が6つ...6C2+6で21通り、この「6」を楽に求めたいなあ
  • この6は「一番上のぐじゃぐじゃの部分木の要素数」から、「それ以外のぐじゃぐじゃの部分木の大きさ」の和+1を引けば出るな

  • いやいやそこまで話は単純じゃないぞ!...例えばこういうとき↓は外側の青の分だけ引かなきゃいけない

  • これはどう判別させればいいだろう...今のパターンは「一方のぐじゃぐじゃが、もう一方のぐじゃぐじゃの孫になってる」パターンか...
  • これはもしかして、「同じ色のやつらを木にして、直属の子の分だけ引く」でいいのではないだろうか
    つまり頂点vの(全体の木での)部分木のサイズ数をs _ vとすると、頂点vでの求める数 = s _ v -1-\sum (s _ {自分の色の木での子})っぽい

  • こうなったらBFSで色ごとの木を作ろう
  • まずは全体の根からのBFS 頂点vの「色ごと木」での親は?...自分と一緒の色で、一番最後に来た頂点
    ->色ごとにstackを作ればいいのでは?
  • こういうBFSにするか:
    • 木の配列vector coltree(N),vector colstack(N),部分木の大きさを保存するvector subtree(N)を用意
    • void bfs(v){
    • LL mycol = vの色
    • 色ごとの木coltree[mycol]に新しい頂点を追加
    • 親はcolstack[mycol].top()
    • (全体の木での)子にbfsを回し、加えてsubtree[v]を求める
    • LL d = subtree[v]-1-subtree[色ごとの木でのvの子]として、ans[mycol] += dC2+d

    これで終わりや!

  • ダメでした。こういうパターンでこの計算すると、一番上のぐちゃぐちゃを通ることを許してしまいます

ということは、各頂点vについて、

  • 全体木での各子頂点chについて、

    • LL d = subtree[ch]
    • chに含まれ、かつvの属する色ごとの木でのvの子頂点tchについて、d -= subtree[tch]
    • ans[mycol] += dC2+d

みたいなことをしないといけない

  • (ここで実装が死にました。最悪な実装をしています。同じことをしていてもっとまともなコードはじき上げます) atcoder.jp

E - Active Infants(再)

  • 例1を見てみる:A = {1,3,4,2}
  • 大きい活発度のやつから遠くに移していきたいよね...例えば4を0番目、3を3番目、1を2番目、2を1番目に送るとどうなる?最大になってくれた
  • 例2も見てみる:A = {5,5,6,1,1,1}
  • 大きい奴から順に、遠く遠くに移してみる:{1,1,1,5,5,6}
    でもこれだと合計57,残念1足りない
  • これ最大パターンはなんだろう...初めに6を一番左に移したらできた、{6,1,1,1,5,5}らしい
  • 大きいのから移していくとしたら、確かに左か右のどちらかに移していくのがベストだな
  • これでとりあえずN!通りから2N通りになった...?(当然まだ足りない)
  • 活発度たちを、元の場所を持たせたまま昇順に並べ替えます 後ろの方から動かします
    するとn番目を見るときは、端から埋めていくので左右合わせてn個が埋まっているはず この左右の埋め方はn通りぐらい
    ->n=0～N-1でDPしても、出てくる状態はN×N程度しかなさそう
  • 一度求めた状態はmapで持っとくことにしよう(どうせlog Nが付くぐらいなので)
  • すると次のようなdpができそう:
    LL dp(LL n,LL s,LL e){ 左が0～s,右がe～N-1埋まった状態で(活発度降順で)n番目を動かすときのmax
    ①n番目をs+1番目に動かす場合
    今までdp(n+1,s+1,e)をしていなかったら、やってmapに記憶しておく
    この結果+(n番目を動かした分の利益)
    ②n番目をe-1番目に動かす場合
    今までdp(n+1,s,e-1)をしていなかったら、やってmapに記憶しておく
    この結果+(n番目を動かした分の利益)=d2
    d1とd2のおっきい方返す
    }
  • 通りました うれしいね

atcoder.jp

〆

これやる意味あるんですかね まあ気が向く間やればいいさ

HL分解・オイラーツアー入門

競プロ

初めに

この記事は、Heavy-Light分解(重軽分解、HL分解)・オイラーツアー・その融合形についての記事です。先日ある方のエントリに感動したのでこの記事を書きます。 HL分解とオイラーツアーは、論点を木から配列にずらすことで木に関するクエリをうまく処理する手法です。この記事ではこれらに加え、HL分解と「部分木に関するクエリを処理するオイラーツアー」を融合させることで、パス・部分木に絡むクエリ両方を処理できるよう方法を紹介します。

＿人人人人人人人人人人人人人人人人人人人人＿
＞　多分これが一番わかりやすいと思います　＜
￣ＹＹＹＹＹＹＹＹＹＹＹＹＹＹＹＹＹＹＹＹ￣

※クッソ長いです。ごめんね

オイラーツアー

雑にネットで調べたのですが、主に2種類あるようです。

  • パスに関するクエリを処理する オイラーツアーと
  • 部分木に関するクエリを処理する オイラーツアー です。

どちらも「クエリを列処理に還元できるようにBFS(深さ優先探索)をして頂点を並べる」のは変わりません。以下オイラーツアー(Euler Tour)をETと略すことにします。宇宙人ではありません。

冒頭のHL分解+部分木ETの理解のためには、パスETの方の理解は必ずしも必要ではありません。面倒な方はこれからのパスETは飛ばしてお読みください。

パスに関するET

次のような木を考えます。


ペイント最高!


この木上でDFSを行います。根から始めて素直に左側の子から訪れると、下の図のように訪れることになります。頂点の左の青い数字は来た順番です(一度来た頂点も記録します)。


今このBFSで訪れた順に、頂点を並べてみます。n番目の頂点をvi[n]とします:

n01234567891011121314
vi[n]012425267621310

次に各頂点vについて、

  • 「vが始めて訪れた時の添え字」\displaystyle{vd[v]}
  • 「vが最後に訪れた時の添え字」\displaystyle{vu[v]}

を記録します:

v01234567
\displaystyle{vd[v]}012123578
\displaystyle{vu[v]}141310123598

この2つは以下のBFSで求められます

void bfs(vector<vector<int>>& childs,int v,int& ind){
    vd[v]=ind++;
        for(int ch:childs[v]){
            bfs(childs,ch,ind);
            ind++;
        }
    vu[v]=ind-1;
}

この時2頂点\displaystyle{u,v} (ただし\displaystyle{vd[u]\leq vd[v]})について、以下が成り立ちます:

  • 頂点\displaystyle{vi[vd[u]]=u\rightarrow vi[vd[u+1]]\rightarrow \cdots\rightarrow vi[vd[v]]=v}はu\rightarrow vのパスになる(ただし最短のパスではない)

例えば

  • u=1,v=6について、\displaystyle{vd[1]=1,vd[6]=7}
    \displaystyle{vi[1]～vi[7]},つまり\displaystyle{1\rightarrow 2\rightarrow 4\rightarrow 2\rightarrow 5\rightarrow 2\rightarrow 6}はuからvへのパスである

  • u=7,v=3について、\displaystyle{vd[7]=8,vd[3]=12}
    \displaystyle{vi[8]～vi[12]},つまり\displaystyle{7\rightarrow 6\rightarrow 2\rightarrow 1\rightarrow 3}はuからvへのパスである

この性質を用いて、以下の問題を解いてみます。

  • 頂点数Vの木が与えられる。各辺(v,p(v))には整数\displaystyle{a _ {v}}が定められている。初期値は0。
  • 2種類のクエリが飛んでくる
  • 更新クエリ(v,x):\displaystyle{a _ {v}}+= x
  • パス和クエリ(u,v):頂点\displaystyle{u}から\displaystyle{v} (ただし\displaystyle{LCA(u,v)=u})への、最短のパス上の辺のa _ {*}の総和を出力する

要素数2V-1の配列Aを用意します。各クエリを以下のように配列の処理に置き換えます。

  • 更新クエリ(v,x):\displaystyle{A[vd[v]-1]+=x,A[vu[v]]-=x}
  • パス和クエリ(u,v):\displaystyle{\sum _ {i=vd[u]}^ {vd[v]-1}A[i]}を求める

この処理はセグ木に任せることでO(log\ n)で実現可能です。


vi[*]012425267621310
A _ {*}a _ {1}a _ {2}a _ {4}-a _ {4}a _ {5}-a _ {5}a _ {6}a _ {7}-a _ {7}-a _ {6}-a _ {2}a _ {3}-a _ {3}-a _ {1}

具艇的なコードは書きません、めんどいので...。

(u,v)の一方がLCA(u,v)でなくとも、LCAを取ることでこのパターンに帰着できます。また辺の重みの足し算ではなくほかの演算でも可能です。この演算が可換でない場合も、二方向の演算結果を持っておくことで適用できます。ただし逆元や単位元を持つ必要があります。したがって行列積や最大最小には使えません。総じて、いわゆる群っちゅう奴なら乗せられるということです。

LCAも求められます。DFSの時各頂点の深さも配列Dに記録しておきます。頂点u,vのLCAは、\displaystyle{D[vd[u]]からD[vd[v]]}の中で値が最も小さくなるような頂点です。

部分木に関するET

この場合も同様の準備を行います。ただし今度のBFSでは一度訪れた頂点は飛ばして記録します。

l[v] 01234567
v 01245673

以下、頂点vを何番目に訪れたかをl[v]で表します。 頂点6の部分木は6,7です。これは先の表下段のl[6]=5,6番目です(0-index)。同様に、頂点2の部分木は2,4,5,6,7です。これは先の表下段のl[2]=2～6番目です。このように、各部分木が表下段の数列の部分列に対応しています。
よって、頂点vに関する情報を配列のl[v]番目においておけば、部分木に関するクエリは列に関するクエリに変換できます。具体的に以下のような問題で見てみます。

  • 頂点数Vの木が与えられる。各頂点vには整数\displaystyle{a _ {v}}が定められている。初期値は0。
  • 2種類のクエリが飛んでくる
  • 更新クエリ(v,x):\displaystyle{a _ {v}}+= x
  • 部分木和クエリ(v):頂点\displaystyle{v}の部分木に含まれるすべての頂点uのa _ {u}の和を出力する

まず次のようなBFSを行います。

void bfs(vector<vector<int>>& childs,int v,int& ind){
    l[v]=ind++;
        for(int ch:childs[v]){
            bfs(childs,ch,ind);
        }
    r[v]=ind-1;
}

BFS順に頂点を並べた時に、頂点vの部分木は\displaystyle{l[v]}番目～ \displaystyle{r[v]}番目の部分列に対応します。次に要素数Vの配列Aを用意します。\displaystyle{a _ {l}}は\displaystyle{A[l[v]]}に入れます。
更新クエリ(v,x)に対しては、\displaystyle{A[l[v]]+=x}をします。
部分木和クエリに対しては、\displaystyle{A[l[v]]～A[r[v]]}の和を求めればいいです。
したがってこの問題はセグ木で解くことができます。

以上のようにETは、枝をうまい具合に列に変換して部分木・パス関連のクエリをうまく捌こうという案だと思っています。

HL分解

一方HL分解そのものは、「列がノードである扱いやすい木に変換する」という手法です。扱いやすいというのは、深さが低い、という意味です。

まず辺を2種類の辺、Heavyな辺とLightな辺に分けます:

  • (高さ1以上の)各頂点から、部分木が最も大きい子頂点への辺をHeavyな辺、
  • それ以外の辺はLightな辺

水色の数字は各頂点の部分木の要素数、水色の辺がHeavyな辺です。例えば頂点2の子頂点は4,5,6ですが、それぞれの部分木の要素数は1,1,2です。よって頂点2から葉方向へのHeavyな辺は2\rightarrow 6です。

次に、Heavyな辺で結ばれた頂点たちを、元の木での上下関係をとどめ一つにまとめます。以下この1つにまとめたものを「Heavy集合」とでも呼ぶことにします。あるHeavy集合に含まれる集合と、別のHeavy集合に含まれる頂点がLightな辺で結ばれている場合2つのHeavy集合を結ぶと、元の木より低い木ができます。 各Heavy集合は持っている頂点列を管理します。

この図の場合、

  • 0番目のHeavy集合が持つ頂点は、根の方から順に0,1,2,6,7
  • 1番目のHeavy集合が持つ頂点は、根の方から順に4
  • 2番目のHeavy集合が持つ頂点は、根の方から順に5
  • 3番目のHeavy集合が持つ頂点は、根の方から順に3,8

深く書く気力もないので証明等は割愛しますが(は?)、この変換で木の深さをlog\ V程度に抑えることができます。

この方法の利点は、長い枝を配列で処理し木上を行き来する回数を抑えられることです。具体的にどういう処理を行うか、改めて「パスに関するET」での例題で考えることにします。うまい抽象論を述べる日本語力がないので。

  • 頂点数Vの木が与えられる。各頂点vには整数\displaystyle{a _ {v}}が定められている。初期値は0。
  • 2種類のクエリが飛んでくる
  • 更新クエリ(v,x):\displaystyle{a _ {v}}+= x
  • パス和クエリ(u,v):頂点\displaystyle{u}から\displaystyle{v} (ただし\displaystyle{LCA(u,v)=u})への、最短のパス上の頂点のa _ {*}の総和を出力する

やはり具体的な実装は疲れるのでやめときますが(気が向いたら書くかも)、図を使いつつまあざっくり説明します。

  • 前準備:HL分解をします
    • 各頂点の部分木のサイズを求める
    • 各頂点についてどのHeavy集合に属するか求める(私はHeavy集合を最も根に近い頂点で見分けてます)
    • 各Heavy集合の(Heavy集合のみの木での)深さを求める...LCAを求める際には必要です
    • 各Heavy集合にセグ木を用意させる
  • 更新クエリ(v,x)の場合、
    • 頂点vを含むHeavy集合を求め、セグ木のvに対応する場所を+=xする
  • パス和クエリ(u,v)の場合、
    • vの属するHeavy集合Hとuの属するHeavy集合が異なる間、(whileループ)
      • Hの持つ一番根に近い頂点tからvまでの和をHのセグ木で求める
      • uをtの親で置き換え
    • uからvまでの和を求める

Heavy集合の木を1個ずつ上がっているわけですが、深さは高々log\ Vですから計算量はO(log^ 2\ V)です。

Easiest HLD with subtree queries

正直ここからが本題です。長いね。すずろに書いてたらめちゃくちゃ長くなりました。ごめんね

ご紹介するのは、CodeForces上のadamant様のこのエントリです。まあざっくりとアイデアを日本語にすると、「0番目の子がHeavyな辺でつながってくれれば、オイラーツアーしただけでHeavy集合がならんでくれるよね」という話です。

codeforces.com

ソースコード部分の下、おじさん?お兄さん?の上の英文は大体つぎのような感じです:

このBFSすれば、

  • 頂点vの部分木が\displaystyle{[in _ v,out _ v)}に、
  • vからHeavy集合の一番上の頂点nxt _ v へのパスが\displaystyle{[in _ {nxt _ v},in _ v]}に

対応する配列がゲットできるよ これで同じセグ木でパスと部分木両方処理できるよ

具体的にソースコードを見てみます。

void dfs_sz(int v = 0) {
    sz[v] = 1;
    for(auto &u: g[v]) {
        dfs_sz(u);
        sz[v] += sz[u];
        if(sz[u] > sz[g[v][0]]) {
            swap(u, g[v][0]);
        }
    }
}

基本的には頂点vの部分木のサイズsz[v]を求める処理です。普通と違うのは、swapの部分です。
これはつまり、「部分木のサイズが一番大きい子を強制的に0番目にする」わけです。もっと言うと、Heavy辺の決め方から「0番目の子が親と同じHeavy集合に属する」わけです。

次に2個目のDFS関数を見てみます。

void dfs_hld(int v = 0) {
    in[v] = t++;
    for(auto u: g[v]) {
        nxt[u] = (u == g[v][0] ? nxt[v] : u);
        dfs_hld(u);
    }
    out[v] = t;
}

まず\displaystyle{in,out}は前に示した通り、部分木に関するETにおける頂点vの部分木の範囲です。一方、子uについて、

  • u == g[v][0]、つまりuとvが同じHeavy集合ならば\displaystyle{nxt[v]}はnxt[u]
  • u \neq g[v][0]、つまり辺(u,v)はLightな辺ならば\displaystyle{nxt[u] = u}

これでnxtは各頂点が属するHeavy集合の、最も根に近い頂点になります。

わざわざ2つの子をswapしたのにも意味があります。素直に0番目の子から訪ねるオイラーツアーをした結果がHeavy集合を並べた形になるからです。例えば先の図の木の場合、ETの結果は0,1,2,6,7,5,4,3,8になります。この列は確かにHeavy集合を並べた形になっています。

実装例

HLD本体

class HLD {
public:
    Tree& tree;
    LL V;
    VLL depth;   //各頂点が属するHeavy集合の深さ
    VLL top;   //各頂点が属するHeavy集合の一番上の頂点
    VLL in;   //各頂点がEuler-Tourでどこにいるか
    VLL out;   //各頂点の部分木の終わり
    HLD(Tree& t, LL root = 0):tree(t) {
        V = t.size();
        VLL subtrees(V, -1);
        //各部分木のサイズを求める
        {
            stack<LL> order;
            stack<LL> hold;
            hold.push(root);
            while (!hold.empty()) {
                LL cur = hold.top();
                hold.pop();
                order.push(cur);
                for (LL ch : tree[cur].childs) {
                    hold.push(ch);
                }
            }
            while (!order.empty()) {
                LL cur = order.top();
                order.pop();
                subtrees[cur] = 1;
                for (LL& ch : tree[cur].childs) {
                    subtrees[cur] += subtrees[ch];
                    if (subtrees[ch] > subtrees[tree[cur].childs[0]]) {
                        swap(ch, tree[cur].childs[0]);
                    }
                }
            }
        }
        //HL分解 with eulertour
        {
            in.resize(V);
            out.resize(V);
            depth.resize(V);
            top.resize(V);
            LL cur = root;
            LL nextid = 0;
            dfs(cur, nextid);
        }
    }
    void dfs(LL cur,LL& nextind) {
        in[cur] = nextind++;
        for (auto ch : tree[cur].childs) {
            //0番目の子は同じHeavy集合
            if (ch == tree[cur].childs[0]) {
                top[ch] = top[cur];
                depth[ch] = depth[cur];
            }
            //それ以外は新しいHeavy集合
            else {
                top[ch] = ch;
                depth[ch] = depth[cur] + 1;
            }
            dfs(ch, nextind);
        }
        out[cur] = nextind - 1;
    }
    LL LCA(LL u, LL v) {
        //uの属するnode.depth >= vの属するnode.depthにする
        if (depth[u] < depth[v]) {
            swap(u, v);
        }
        while (depth[u] > depth[v]) {
            u = tree[top[u]].parent;
        }
        while (top[u] != top[v]) {
            u = tree[top[u]].parent;
            v = tree[top[v]].parent;
        }
        if (in[u] > in[v])return v;
        else return u;
    }
};

LLはlong longです(たぶん定数倍的にはよくないんですよね)
bfs_szに対応する部分はコンストラクタ中にいて、bfs_hldはbfsという名前になっています。LCAに対応するために、bfsで各頂点の属するHeavy集合の深さdepthも求めています。
LCAも求められます。

  • uのHeavy集合とvのHeavy集合を一個ずつ上がり続ける(u,vも一緒に更新)
  • 両者が一緒になったら(つまりtop[u] == top[v])、オイラーツアーで先に来た方をLCAとする

<そのうち増やす>

〆

疲れました。思ったよりめちゃくちゃ長くなりました。最初からもうちょっとソーシャルディスタンスな感じで書けばよかったですね。

Latexをはてなブログmarkdown形式に変換

数学


モチベーション

先日はてなブログのmarkdown編集で数式を書いてたら妙なところに詰まってしまいました。調べたらどうもmarkdown編集でのLatexにはクセがあるよう。
例えばDP[i][j]は当然Latexで下のようになりますが、

DP[i][j]

マークダウン編集に[tex:DP[i][j]]と書くと下のように途端に崩れます

DP[i[j]]

同様の謎現象が起こることは多々あるよう。ということで"まともな"Latexをはてブmarkdown編集用に変更する作業をプログラムにさせることにしました。

使い方

Latexで書いた数式を用意します。ここではz = Ae^{\omega it}+Be^{-\omega it}を用います。
上のテキストボックスに元数式を書きます。

下のテキストボックスに出てきたモノを、markdown編集モードで入れたい場所に貼り付けるればOK。


markdown編集に貼り付けると


このとおり

 何をしているか

 参考にさせていただいたこのサイトで述べられていたことをやっただけです。

7shi.hateblo.jp

具体的には、

  • 数式をブロック環境として変換する場合、

    1. <div align="center">[tex:と]</div>で囲む

    2. ]を\]に置換

  • 数式をインライン数式として変換する場合、

    1. [tex:\displaystyle{と}]で囲む

    2. ^(指数)の後ろにスペースを挿入

    3. _(添え字)の前後にスペースを挿入

    4. \{,\},]を\\{,\\},\\]に置換



以下のサイトを参考にさせていただきました。ありがとうございました

 

7shi.hateblo.jp

はてなブログmarkdown編集でのLatexの書き方について

 

kotokunohate.hatenablog.com

はてなブログでのjQuery導入方法について

 

blog.rinotc.com

はてなブログ上でのformの載せ方について