otagai_tasukeaiが助け合わなかったこと(ICPC 2022 Asia Yokohama Regional参加記)

  • コーチと選手2人は電車、1人逆張りバスで来た結果遅刻しかけた
  • リハーサルの時までライブラリの使い方を知らない
  • 1人だけvim使った上に、set expandtabの設定を忘れていてタブ文字がすごい
  • 英字配列の練習をしていたかったので唯一使える人がライブラリ全部写す係に
  • チーム紹介担当を2人が嫌がったので1人が助け出そうとしたら「そういう真面目なのはやめとこう」となって(tasukeaiとは)、虚言癖のある人に一任した
  • 1日目のホテル着後、1人はベッドに溶け、1人はいつの間にかイルミネーションを一人で見にいった結果、夜ご飯は別々に(メロンパン、炒飯、食べ放題、全員一人で食べた)
  • 朝ご飯前に部屋前で起床チェックが入る予定だったのに、先に食べ始めていた
  • 「追加のライブラリ印刷代は俺が奢るから」→ もらっていません
  • 「チームの2人の仲が悪くなっても、もう1人と不可侵条約を結んでるから大丈夫」という虚言
  • 3人がそれぞれD, E, Gを担当することになって、全員プログラムをバグり散らかしてパソコンの所有権をぐるぐる、デバッグはお互いが関与せずにAC
  • JOI17/18の話は、やめよう(歳をとった たすけてくれ)

  • (追記)

  • チーム紹介スライド 僕が出した渾身の一作がrejectされた
  • コンテスト本番に嘘の問題概要を伝えて「サンプルと違くないか?」「すまん虚言だった」をやりました

  • 追記2

  • 考察を聞いたものの理解できず、自分には分からない解法だと思ってなあなあにしていたが誤読が後から判明
  • ライブラリの印刷をしておくと言いながら直前までせず、前々日の昼にPDFを要求されるも17:00まで寝ていたため印刷が前日に
  • 2人が当日失敗したらチーム解散どころか絶縁の危機だった(結局2人とも失敗したので回避)
  • otagai_nonoshiriaiというエイリアスが誕生した

「お互い助け合い」だよな?

ICPC2020 国内予選参加記

niu_mogu_moguでugisとplayrollerで組んで参加しました. うにもぐもぐ.

コンテスト前

library-checker-porblemsをクローンしてきた. 16:30まで授業だったので, 授業を途中でブッチしました. 教員から「結果残してね♡」と言われる.

コンテスト

なんかアクセスできなくて焦る, 電話するけど繋がらなかったのでそういうことかと安心する. ぬるっとスタート.

ugisにA, playrollerにBを任せて, 僕はC, D, E, Fあたりを一通り見る.

Cは解けそうなのでヒントだけ二人に託した, Dが構文解析がメインではないこと, EがbitDPできそう, Fはできるけどバグらせそうと思ったあたりで, ABが通っている. 焦るなあ

Eは絶対bitDPだと思っていたけどどうするか悩む. 4*4に分割するのかともおもった. 連結成分が4つに分かれるしグラフが15*30に圧縮できそう → 書く.

書いてバグらせている間にCが通されている. 実行に1分くらいかかったらしいけど通ったのでよし!

Eのバグは圧縮したグラフを勘違いしていたことだった. これをちゃんと書き直してAC. playrollerにお茶を奢ってもらう.

Fは絶対に通せると思っていたのでDを託す. おもむろにOnlineDynamicConnectivityを貼る. 実装は20分くらいで終わったしData No.1は通ったけど, Data No.2が通らない. なんやこれ...

Dわからんとちょくちょく連絡が来る, 僕もわからない. まあF通せればいいやと思っていた.

Fのバグに気がついたのが終了30分前. けどこのバグで治らなくて非常に焦る, なぜNo.1が通ったのか全くわからない.

う〜と唸って残り2分. 辺を切った連結成分を見るときに, 切っていない連結成分も含めていることに気がつく. if文を追加して, サンプルテストせずにNo.2No.3を通す. ここで残り20秒. 危なかった.......

最終成績25位 ABCEF5完

しめ

教員もかなりびっくりしていた. かなり胸を張れる結果が出せたかなあと思う.

一番良かったのは, 高専での長い付き合いだった同級生と一緒にICPCで良い結果が出せて本当に良かった. 二人に感謝...

横浜に旅行に行きたいです. よろしくおねがいします.

hatena blogからGithub Pages + Hugo に移しました

はてなグループが消えてしまって, 競技プログラミングの記事が消えていくのをみて
僕も何か対策をしないとなあと思ってこうなりました

toptreeとか消えるのいやだからね...

How

github.com

これを使いました

  • 画像が何故かダウンロードされなかったのでそれを直した
  • chart.apisをtex記法($$で囲む)ようにした

これでコマンド実行だけで移植できました

移植先はここです. このブログは残しておこうと思います.

niuez.github.io

これからもにうをよろしく!

約数畳み込みを使って最大公約数と集合をうまく扱うメモ

書いて置かないと頭に置いておけない気がしたのでメモを残す. 間違ってたらごめん

これについて気になったので

概要

ネタバレあるので気をつけてください

約数畳み込み

関数 f(n)に対する約数畳み込みとは,

 \begin{eqnarray} g(n) = \sum_{ d | n } f(d) \end{eqnarray}

あとで解説しますが, 方針としてはこの畳み込んだ後の g(n)を問題を解けるように定義してやることでGCDを綺麗に扱うことができます.

メビウス関数

実際に g(n)を定義してみます. 一番有名なのは g(n) = \delta(n, 1)です.  \delta(n, 1)クロネッカーのデルタです. このとき,

 \begin{eqnarray} g(n) = \delta(n, 1) = \sum_{ d | n } f(d) \end{eqnarray}

を満たす f(n)メビウス関数と呼ばれ,  \mu(n)と書きます.(メビウス関数 - Wikipedia)

メビウスの反転公式(約数畳み込みの逆操作)

上の式のままだと,  f(n)を導くのは困難です. ここで登場するのがメビウスの反転公式です. これは, 約数畳み込みの逆操作に当たります.

$$ \begin{eqnarray} g(n) &=& \sum_{ d | n } f(d) \\ f(n) &=& \sum_{ d | n } g(d) \mu(\frac{n}{d}) \end{eqnarray} $$

これで g(n)を定義してから反転公式を適用することで f(n)を導くことができます.

約数畳み込みと逆約数畳み込みのアルゴリズム

約数畳み込みとその逆はnoshi91さんが計算量 O(A \log{\log A})で計算するアルゴリズムの記事を紹介しています.

noshi91.hatenablog.com

逆約数畳み込みの実装例

template <class T>
void inverse_divisor_transform(vector<T> &a) {
    int n = a.size();
    vector<bool> sieve(n, true);
    for (int p = 2; p < n; ++p) {
        if (sieve[p]) {
            for (int k = (n - 1) / p; k > 0; --k) {
                sieve[k * p] = false;
                a[k * p] -= a[k];
            }
        }
    }
}

最大公約数の扱い

自然数 n, mに対して,

 \begin{eqnarray} \sum_{d | n, d | m} f(d) \end{eqnarray}

を考えると,

$$ \begin{eqnarray} \sum_{d | n, d | m} f(d) &=& \sum_{d | \gcd(n, m)} f(d) \\ &=& g(\gcd(n, m)) \end{eqnarray} $$

となり,  \gcd(n, m)に対する操作ができます. 例えば,  f(n) = \mu(n), g(n) = \delta(n, 1)とすると,  g(\gcd(n, m))は,「 n, mが互いに素であれば 1, そうでなければ 0」となり, 互いに素かどうかの判定ができます.

集合の扱い

例えば,  c_m(d) = [d | m]という関数( d mを割り切るなら 1, そうでなければ 0)を考えると,

$$ \sum_{d | n, d | m} f(d) = \sum_{ d | n } f(d) c_m(d) $$

と変形できます.

これを応用します. 自然数の集合 S を考え,  c(d) = \sum_{m \in S} c_m(d)とすると,

$$ \begin{eqnarray} \sum_{d | n} f(d) c(d) &=& \sum_{m \in S}\sum_{d | n} f(d) c_m(d) \\ &=& \sum_{m \in S} g(\gcd(n, m)) \end{eqnarray} $$

となります.

 f(n) = \mu(n), g(n) = \delta(n, 1)を考えてみると, 「集合 Sの中に nと互いに素な要素の数」を計算しています.

AGC038C LCMsを解く

atcoder.jp

ネタバレ回避用






































































 lcm(x, y) = x (\frac{y}{\gcd(x, y)})と変形します. 約数畳み込みを使う方針でやると, この (\frac{y}{\gcd(x, y)})が最後に来てほしい気持ちになります.  g(n) = \frac{1}{n}と置くと,

$$ \begin{eqnarray} \frac{y}{\gcd(x, y)} &=& y \cdot g(\gcd(x, y)) \\ &=& \sum_{d | gcd(x, y)} f(d) y \\ &=& \sum_{d | x, d | y} f(d) y \\ &=& \sum_{d | x} f(d) s_y(d) \end{eqnarray} $$

ここで s_y(d)を「 d yを割り切るなら y, そうでなければ 0」としました.
応用して, 自然数の集合 S を考え,  s(d) = \sum_{m \in S} s_m(d)とすると,

$$ \begin{eqnarray} \sum_{d | x} f(d) s(d) &=& \sum_{y \in S}\sum_{d | x} f(d) s_y(d) \\ &=& \sum_{y \in S} y \cdot g(\gcd(x, y)) \end{eqnarray} $$

と計算できて, これに xを掛けると「集合 Sの中の各要素と xの最大公約数の和」を計算できました.
計算量は,  O(A \log{\log A} + N \sqrt A)です.

atcoder.jp

ソースコード

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define rep(i,s,e) for(i64 (i) = (s);(i) < (e);(i)++)

/* modint */
/* IO(niu::fin, niu::fout) */

const i64 MOD = 998244353;
using fp = modint<MOD>;


#include <bits/stdc++.h>
using namespace std;
using i64 = long long;

template <class T>
void inverse_divisor_transform(vector<T> &a) {
    int n = a.size();
    vector<bool> sieve(n, true);
    for (int p = 2; p < n; ++p) {
        if (sieve[p]) {
            for (int k = (n - 1) / p; k > 0; --k) {
                sieve[k * p] = false;
                a[k * p] -= a[k];
            }
        }
    }
}

constexpr i64 A = 1e6 + 1;

int main() {
  std::vector<fp> f(A);
  rep(d,1,A) {
    f[d] = fp(d).pow(MOD - 2);
  }
  inverse_divisor_transform(f);

  i64 N;
  niu::fin >> N;
  vector<fp> sum(A);
  fp ans = 0;
  rep(i,0,N) {
    int x;
    niu::fin >> x;
    fp res = 0;
    for(int d = 1; d * d <= x; d++) {
      if(x % d == 0) {
        res += f[d] * sum[d];
        sum[d] += fp(x);
        if(x / d != d) {
          res += f[x / d] * sum[x / d];
          sum[x / d] += fp(x);
        }
      }
    }
    ans += res * fp(x);
  }
  niu::fout << ans.value() << "\n";
}

Suffix Array と LCP と 文字列検索の実装をした

この土日のメモです. SAとLCPのお気持ちをまとめたくなっただけ. 間違ってたらごめん

これをやめたいので, 手始めにSuffix Arrayを使った文字列検索をやってみようかなというのが今回の主題

概要

  • SA-ISでSuffix Arrayを構築 O(|S|)
  • LCP配列の構築 O(|S|)
  • LCPによるSuffix同士のLCPをSparse Tableで構築 O(|S| \log{|S|}), クエリ O(1)
  • Suffix Arrayの二分探索で文字列検索を O(|T| log{|S|})
  • Suffix ArrayとLCPの二分探索で文字列検索を構築 O(|S|), クエリ O(|T| + \log{|S|})

の実装をやってみました. このときのメモを残しておきたいと思います.

各用語の説明はここではしません... 他の記事や, 蟻本 - Amazonを参考に.

SA-IS

Suffix Arrayの実装は蟻本にも載っていますが, そこまで早くありません... SA-ISというアルゴリズムが早いらしいのでこれを実装します.

SA-ISの理解には, この記事がとても参考になりました. とてもわかりやすい記事です.

mametter.hatenablog.com

SA-ISの実装はyosupoさんのコードを見ました.

僕が書いたSA-ISのコードはこれです.

judge.yosupo.jp

  • メモリを使い回す(resizeの回数を減らしてメモリを使いまわしても, assignが割と早くてこれが非自明)
  • push_backをなくす
  • 入出力の早いライブラリを使うともっと早くなります

実はSA-ISの論文に実装が載っていてそれがとても速いです. ぜひ参考にしてみてください.

以下, 文字列SSuffix ArraySAとします. Sの辞書順でi番目に小さいsuffixをSuf[i] := S[SA[i]...]とします.

LCP(Longest Common Prefix)

LCP配列は, Suffix Arrayで隣り合ったSuffix(つまり, Suf[i]とSuf[i + 1])の最長共通接頭辞を求めた配列です. Kasai's Algorithmを用いて O(|S|)で構築できます.

LCPの理解は以下の記事がわかりやすいです. 蟻本にもあるはず.

lumakernel.github.io

例は, 接尾辞配列(Suffix-Array) | Luzhiled’s memo がわかりやすいです.

僕の実装は先頭に無(空配列)があるので, 以下のようになります.

i :lcp
0 : 0 
1 : 0 a
2 : 1 abra
3 : 4 abracadabra
4 : 1 acadabra
5 : 1 adabra
6 : 0 bra
7 : 3 bracadabra
8 : 0 cadabra
9 : 0 dabra
10: 0 ra
11: 2 racadabra

任意のsuffix同士のLCP

上の例で, i = 2, abraと, j = 5, adabraのLCPを求めるとすると, 3, 4, 5lcpの最小値である1がその答えになります.

Suffix Arrayで, indexが  i のsuffixと  j のsuffixのLCPは,  [i + 1, j + 1) 間のlcpの最小値になります.

なので, lcpをSparse Tableに載せると構築  O(|S| \log{|S|}), クエリ O(1)で処理できます.

Suffix Arrayで文字列検索

文字列SSuffix Array SAを使って, Sの中に文字列Tがあるかどうかを二分探索で処理できます. これは, Suffix Arrayによって各suffixがソートされているのを利用しています.

計算量は O(|T| \log{|S|})です. AOJの提出コード

cin >> t;
int L = 0;
int R = sa.size();
while(R - L > 1) {
  int M = (L + R) >> 1;
  if(s.substr(sa[M], t.size()) <= t) {
    L = M;
  }
  else {
    R = M;
  }
}
cout << (s.substr(sa[L], t.size()) == t) << endl;

これがかなりはやい なんでだろう

SAとLCPで文字列検索

この二分探索はさらに高速化できます. suffixとTの比較を最小限にすることで,  O(|T| + \log{|S|})を達成します.

具体的には, suf[L]とTのLCPを常に持ちながら二分探索をします. このLCPをLlcpとします. M = (L + R) / 2として, suf[L]suf[M]のLCPを求めて, nlcpとします. nlcpは先に書いたとおり, Sparse Tableで求めることができます. 次にLlcpnlcpを比較します.

  • Llcp < nlcpのとき

以下の例で考えてみます. (Suffix Arrayではありませんが, 複数の文字列を辞書順にソートしたという意味で同じです)

T = ad

L : aaa
    aaab
    aaac
M : aac
    aacc
    ba
R : 

Llcp = LCP(aaa, ad) = 1  // "a"aa, "a"dなので
nlcp = LCP(aaa, aac) = 2 // "aa"a, "aa"cなので

Tは辞書順でsuf[T]以上ということがわかっているので, Llcp < nlcpより, Tとsuf[M]のLCPはLlcpであり, Tは辞書順でsuf[M]以上です. なので, Llcpはそのままで, L = Mとします.

  • Llcp > nlcpのとき
T = aaac

L : aaa
    aaab
    aaac
M : aac
    aacc
    ba
R : 

Llcp = LCP(aaa, aaac) = 3  // "aaa", "aaa"cなので
nlcp = LCP(aaa, aac) = 2 // "aa"a, "aa"cなので

Tsuf[M]のLCPはnlcpであり,Tは辞書順でsuf[M]未満です. なので, Llcpはそのままで,R = M`とします.

  • Llcp = nlcpのとき
T = aacc

L : aaa
    aaab
    aaac
M : aac
    aacc
    ba
R : 

Llcp = LCP(aaa, aacc) = 2  // "aa"a, "aa"ccなので
nlcp = LCP(aaa, aac) = 2 // "aa"a, "aa"cなので

このときは, Tsuf[M]の辞書順の関係がわからないので比較をします. このとき, LCPの部分は一致していることがわかっているので比較をしなくてよいです. 比較をした後, Llcpを比較をした時の計算結果を利用して更新します.

Llcpは探索中, 単調増加します. なので, 文字列の比較が全体で O(|T|)しかされません. これにより, 計算量が改善されます.

実際にコードを示します.

std::pair<int, int> get_lcp(const std::vector<T>& t, int si, int offset) {
  int i = offset;
  si += offset;
  while(i < t.size() && si < N) {
    if(t[i] != str[si]) {
      return { i, t[i] - str[si] };
    }
    i++;
    si++;
  }
  return { i, 0 };
}

std::pair<int, int> search(const std::vector<T>& t) {
  int L = 0;
  int R = N + 1;
  int Llcp = 0;

  while(R - L > 1) {
    int M = (L + R) >> 1;
    int nlcp = st.query(L + 1, M + 1);
    if(Llcp < nlcp) {
      L = M;
    }
    else if(Llcp > nlcp) {
      R = M;
    }
    else {
      auto p = get_lcp(t, sa[M], Llcp);
      if(p.second >= 0) {
        L = M;
        Llcp = p.first;
      }
      else if(p.second < 0) {
        R = M;
      }
    }
  }

  return { Llcp, L };
}

これで早くなるはず...!

onlinejudge.u-aizu.ac.jp

5倍遅くなった...

Sparse Tableの構築が重すぎる

 O(|S| \log{|S|}) 流石に重い... 改善したい

Sparse Tableを使わない方法で改善

二分探索だけならSparse Tableである必要はありません. Segment Treeを使います.
二分探索で最小値を求めたい区間は必ず[L, (L + R) / 2)に対応できます. なので, 二分探索するときに, Segment Treeのノードを降りていくようにすると 構築 O(|S|)で二分探索ができるようになります.

コードはこんな感じ

...
...
  seg_n = 1;
  while(seg_n < N + 1) seg_n <<= 1;
  seg.resize(seg_n * 2, 1e9);
  for(int i = 0;i + 1 < N + 1;i++) {
    seg[i + seg_n - 1] = lcp[i + 1];
  }
  for(int i = seg_n - 1; i --> 0;) {
    seg[i] = std::min(seg[(i << 1) + 1], seg[(i << 1) + 2]);
  }
}

std::pair<int, int> get_lcp(const std::vector<T>& t, int sa_i, int offset) {
  if(sa_i > N) return { offset, -1 };
  int i = offset;
  int si = sa[sa_i] + offset;
  while(i < t.size() && si < N) {
    if(t[i] != str[si]) {
      return { i, t[i] - str[si] };
    }
    i++;
    si++;
  }
  return { i, 1 };
}

std::pair<int, int> search(const std::vector<T>& t) {
  int L = 0;
  int R = seg_n;
  int Llcp = 0;
  int j = 0;

  while(R - L > 1) {
    int M = (L + R) >> 1;
    int nlcp = seg[(j << 1) + 1];
    if(nlcp == 1e9) {
      j = (j << 1) + 1;
      R = M;
    }
    else if(Llcp < nlcp) {
      j = (j << 1) + 2;
      L = M;
    }
    else if(Llcp > nlcp) {
      j = (j << 1) + 1;
      R = M;
    }
    else {
      auto p = get_lcp(t, M, Llcp);
      if(p.second >= 0) {
        j = (j << 1) + 2;
        L = M;
        Llcp = p.first;
      }
      else if(p.second < 0) {
        j = (j << 1) + 1;
        R = M;
      }
    }
  }

  return { Llcp, L };
}

onlinejudge.u-aizu.ac.jp

これでも最初の二分探索に勝てませんでした... なんでだろう でもこれでもかなり速いです.

しめ

FM-indexとかやってみたくなりました

動的木上の最小シュタイナー木をtoptreeで解く

この記事は「データ構造とアルゴリズム Advent Calendar 2019」 14日目の記事です.
13日目は@ajalabさんのRun-Length FM-Index - koki,
15日目は@minaminaoさんのMerkle Patricia Tree まわりです.

toptreeとは

toptreeは今年競プロ界隈で話題になった動的木を扱うデータ構造の一つです.
link-cut treeも同じ動的木を扱うデータ構造ですが, 機能だけを見ればその完全上位互換です.

toptreeは, 木を動的に扱うデータ構造です. [cs/0310065] Maintaining Information in Fully-Dynamic Trees with Top Treesを読みました.

toptree自体については半年くらい前に自分が書いた記事があります.

niuez.hatenablog.com

上の記事をまとめると

  • 基本的には, 平衡二分探索木(Splay Tree)
  • 葉には辺を表すノード(Edge Node)
  • 1頂点を共有する2つの辺をマージして新しくできた辺を平衡二分探索木の節とする(Compress & Rake)

f:id:niuez:20190804184203p:plain

  • 二分木だけでは列しか管理できないので, 二分木ともう一つの子を管理する(Rake Node)

f:id:niuez:20190804184342p:plain

というあたりです. この形を保持しながらsplay treeの回転を行い各クエリの計算量を償却 O(\log N)を達成しています.

例えば,

  •  \mathtt{link}: ある2頂点間を辺で結ぶ
  •  \mathtt{cut}: ある2頂点間を結んでいる辺をなくす
  • パス: ある木の2頂点を結ぶパスについてのクエリを処理する
    • 辺の重みの総和
    • 辺の重みを +xする
    • など...
  • 木全体に対するクエリ
    • 木に含まれる辺の重みを +xする
    • 木の頂点の重みの総和
    • 木の直径
    • ある頂点からの最遠点距離
  • toptree上の二分探索
    • 木の中心
    • 木の重心
    • パス x, \cdots, y上で xから yに向かって dだけ進んだ場所にある頂点 *1

というクエリが処理できます. 最強っぽい.

これを実装したのがこれです. めっちゃ大変でした. niuez/toptree-rust

動的木上の最小シュタイナー木

10月に僕の作問した問題がyukicoderで木上クエリコンとして出題されました. このときに全問正解を(意図的に)阻止した問題がこれです.

yukicoder.me

辺に正の重みが与えられている木の形が動的に変わっていくなかで, 頂点 v_0, \cdots, v_{k-1}の最小シュタイナー木の重みを答えるクエリを処理しなければなりません.

サンプルを図にしてみます.

サンプルの2個目のクエリのとき, 木は以下のような形をしています. この木に関して, 頂点0, 4, 6を頂点の部分集合とする最小シュタイナー木の重みは20です.

f:id:niuez:20191211212237p:plain

サンプルの4個目のクエリのとき, 木は以下のような形をしています. この木に関して, 頂点0, 4, 6を頂点の部分集合とする最小シュタイナー木の重みは27です.

f:id:niuez:20191211212246p:plain

この問題は, toptreeに載せることで解くことができます. 今回はその解説をしたいと思います.

ここから先, 各クエリで最小シュタイナー木に含めなければならない頂点を赤い頂点と表現することにします.

アルゴリズム

toptreeでは上でも述べたように, 1頂点を共有する2つの辺をマージして新しくできた辺を平衡二分探索木の節とします.
今回の問題で考えられる, マージされる前の辺の状態は2通りのみです.

  • 赤い頂点を1個以上含んでマージされた辺

f:id:niuez:20191211215436p:plain

  • 赤い頂点を一度も含んでいない辺

f:id:niuez:20191211215446p:plain

以下のような場合を考えそうになりますが, これは \mathbb{inter}=0とすると, 1つ目のパターンと同じになります.

f:id:niuez:20191211215846p:plain

辺の端点の色は, マージするときに考えます. つまり, マージの方法は 左側の辺の状態(2通り) * 右側の辺の状態(2通り) * 共有している1頂点の色(2通り) = 8通りです

マージの計算方法(Compress)

以下の通りです.

f:id:niuez:20191211223455p:plain

f:id:niuez:20191211223522p:plain

f:id:niuez:20191211223533p:plain

f:id:niuez:20191211223543p:plain

f:id:niuez:20191211223554p:plain

このパターンは頂点が赤でも黒でも同じです

何か足りない

このパターンだけでは,  \mathbb{inter}は作られません. どういうことでしょう...?
上でも述べたとおり, toptreeでは2通りのマージ方法があります. そのもう一つのマージ方法(Rake)では以下のパターンで \mathbb{inter}を発生させます.

f:id:niuez:20191211224305p:plain

他のパターンは上と同じように計算することができます.

これをちゃんと実装すると以下のように解くことができます.

yukicoder.me

20行目からの関数が, 上で述べたCompressのマージの計算をしています. その下にRakeの計算もありますね.

しめ

今年はtoptreeに夢中な一年でした. 来年はどうなるでしょうか.

*1: jumpと呼ばれることが多い