2026-06-23

おわりに

■まえがき

ここは kyopro_friends について語る記事です。

けものフレンズについて語る記事はこちらです。

kyopro-friends.hatenablog.com

■よくあったわけではない質問

Q. かばんちゃんは出ないの？
A. 彼女はアニメ版の登場人物であり、 kyopro_friends が準拠しているネクソン版の物語には登場しません。
多くのけものフレンズファンは、ネクソン版とアニメ版の間には大きな時間的隔たりがあると考えています。
したがって、 kyopro_friends に彼女が登場することはありません。

Q. 「すっごーい！」って言わないの？
A. その台詞はアニメにのみ登場し、 kyopro_friends が準拠しているネクソン版には登場しません。

Q. リプライ用の画像ってどうやって用意してるの？
A. 有志が作成しかつて公開していた、ネクソン版全ストーリー21138枚のスクリーンショットを元に、全てのテキストを人力で書き起こし、文字列検索しています。

Q. アライさんは「かばんさんが近くにいるのか？」のようにYesNo疑問文では「のか？」という表現を用います。疑問文においても全ての語尾を「のだ？」とするのは誤りであり、アライさん強度が低いです。
A. いいえ、それはアニメ版の話です。
kyopro_friends が準拠しているネクソン版のアライさんは「フェネックはこっちに来て良かったのだ？」などのように、全テキスト中に4つあるYesNo疑問文全てにおいて「のだ？」という表現を用います。
余談として、「３」のアライさんはYesNo疑問文に限っても「のだ？」と「のか？」が混在している一方、「ぱびりおん」のアライさんは第？世代・第2世代ともにWH疑問文とYesNo疑問文で「のだ？」と「のか？」を完全に正確に使い分けています。

Q. あの結末はなに？
A. 単に「ぼくのかんがえたさいきょうの結末」です。公式から提示されている物語とは矛盾があり、思想的にも異なるものであるため、公式の物語がこのような結末を迎えることはないでしょう。

Q. 実家太いの？
私が高校生のとき、家族4人の世帯収入は380万円でした。（住宅ローンあり）

2025-07-14

公益社団法人日本動物園水族館協会に寄付を行いました

これからも日本全国の動物園・水族館が「あの子たちと、友達フレンズになれる！」場所として発展することを願っています。

2026年6月追記

感謝状をいただきました

2026年6月追記

紺綬褒章を賜りました

2025-02-18

償却計算量について

サーバルだよ！
マシュマロでもらった償却計算量についての質問で、私が間違ったことを言っちゃったみたいだから、ちゃんと調べ直して記事にしたよ。

サーバル「償却計算量っていうのはある意味での"平均"を考えてえるってことだから、「最悪O(1)」の操作なら「償却O(1)」っていう必要はないよ。言っても別に間違いじゃないけどね」#マシュマロを投げ合おう https://t.co/hLsAGBx6eI pic.twitter.com/LclKpCP65f
— 競技プログラミングをするフレンズ (@kyopro_friends) 2025年2月14日

償却計算量の定義

ガイドさんにも調べてもらったけど、償却計算量のちゃんとした定義はよくわかんなかったよ……。もし、一般的な定義があったら教えてね。
この記事ではnoshiさんの定義を使うことにするよ。

noshi91.hatenablog.com

データ構造に対して、起こり得る操作全体を $M$ とする。操作の償却計算量が $(A_m)_{m∈M}$ であるとは、任意の操作列 $(m_i)_{i=1}^n$ に対して
$操作列 (m_i)_{i=1}^n を実行する実際の計算量 \leq \sum_{i=1}^{n}A_{m_i}$
が成り立つことと定義する。ここで、操作列 $(m_i)_{i=1}^m$ は「何もない」状態から始まるもののみを指す。つまり、最初の操作 $m_1$ は「空の heap を作る」や「与えられた列から、segment tree を構築する」などになる。 (この条件が無いと、重い操作 1 つからなる列の計算量が壊れてしまう)

この定義からわかる通り、償却計算量の取り方は一意じゃないね。つまり操作1,2の2種類の操作を持つデータ構造に対して

償却計算量で、操作1は $O(1)$ 時間、操作2は $O(N)$ 時間
償却計算量で、操作1は $O(N)$ 時間、操作2は $O(1)$ 時間

の2つの主張がどちらも償却計算量の定義にあうことがあり得るよ！

償却計算量を求めるテクニックはいろいろあるみたいだけど、ここでは、各操作の計算量を直接考えてその収支をみる Banker's method と、ポテンシャル関数を使う Physicist's method を紹介するよ。

Banker's method

Banker's method は、償却計算量の定義を直接確かめる手法だよ。
「各操作で償却計算量に相当する分だけお金が貰えるので、そのお金を使ってデータ構造に対する操作を行い、途中で破産しないことを示す」っていう気持ちのものだね。

例として、元の質問にあった lazy binomial heap で push と pop だけを持つデータ構造の償却計算量を Banker's method で考えてみるよ。
「pushするときに $2$ 円貰える。popするときには heap 内の要素数を N として $1+2\log N$ 円貰える。計算機を動かすには1ステップあたり $1$ 円かかる」とすると、操作の途中で破産することがないことが証明できるから、「償却計算量で、pushは $O(1)$ 、popは $O(\log N)$ 」といえるね。（証明はさっきのリンク先を見てね）

Physicist's method

Physicist's methodは、"ポテンシャル関数"っていう関数を導入して、その関数の値の変化を観察することで償却計算量を考える手法だよ。
ポテンシャル関数っていうのは、データ構造の状態から0以上の数への関数で、Banker's method の"貯金額"にあたるものを表す気持ちのものだよ。
ポテンシャル関数を使うと何が嬉しいかっていうと、Banker's method だと「操作列に対して、破産しないか」を考えていたところを、Physicist's method だと「操作によるデータ構造の状態変化に対して、ポテンシャル関数の変分が実計算量に見合うか」だけを考えれば良くなって、ポテンシャル関数さえうまく決められれば、あとの証明は簡単になるになるところだね！
Banker's method と同じように操作での収支を考えると
$(操作前のポテンシャル関数の値)+(操作の償却計算量)-(操作の実計算量)=(操作後のポテンシャル関数の値)$
になるから、変形するとこう！
$(操作の償却計算量)=(操作の実計算量)+( (操作後のポテンシャル関数の値)-(操作前のポテンシャル関数の値))$
lazy binomial heap の例だと、tree の個数をポテンシャル関数の値とすると「償却計算量で、pushは $O(1)$ 、popは $O(\log N)$ 」が言えるよ。

変な償却計算量

lazy binomial heap の push はリストの最後に要素を追加するだけだから最悪 $O(1)$ 時間だね。popは運が良ければ $\Theta(1)$ 時間で済むけど、最悪のときは heap 内の要素数を N として $\Theta(N)$ 時間かかるね（要素数 1 の木が N 個あるとき）。最良/最悪計算量は、操作の実際の計算時間だけで決まるもので、償却計算量とは全然別物だよ。
ところでさっき、①「償却計算量で、pushは $O(1)$ 、popは $O(\log N)$ 」になるっていったよね。実は、Banker's method で「push するときに $1+2\log(N+1)$ 円貰える。pop するときには $2$ 円貰える。計算機を動かすには1ステップあたり $1$ 円かかる」としても破産しないことが元と同じように示せるから②「償却計算量で、pushは $O(\log N)$ 、popは $O(1)$ 」も正しいといえるよ！

ただ、そもそも償却計算量って「データ構造の状態次第で計算量が変わる操作に対して"平均的な"処理速度を考えたい」って気持ちで考えてることが多いから、「データ構造の状態によらずに最悪 $O(f)$ 時間の操作」の償却計算量は $O(f)$ になるように、操作に対する償却計算時間の組を決めるのが自然だね。
①を使って「pushは最悪 $O(1)$ 、popは償却 $O(\log N)$ 」って言うのは誤解を招くことはほとんどないはずだけど、②が言えるからって「pushは最悪 $O(1)$ 、popは償却 $O(1)$ 」って言うのはかな～～りミスリードだと思うよ。

質問に対する答え

「全ての計算量が償却計算量になるか？」に対する答えは、「ポテンシャル関数の値に影響するものはそう。ただし、償却計算量と最悪計算量が一致してるなら、その2つの区別をつけなくても困ることはないはず」だよ！

謝辞

noshi91 さんにいろいろ教えてもらったよ。ありがと～

2024-03-18

拡張GCDについて

スナネコです。拡張GCDについての質問に答えます。

問題：
以下のように実装された extgcdがある。
整数 $a,b$ が $(a,b)\neq(0,0)$ を満たし、extgcd(a, b) の返り値を $(x,y)$ としたとき、 $\max(|x|,|y|)\leq \max(|a|,|b|)$ が成り立つことを示せ。

def extgcd(a, b):
  # ax+by=gcd(x,y) を満たす (x,y) を返す
  if b == 0: return (1, 0)
  X, Y = extgcd(b, a % b)
  x = Y
  y = X - a // b * Y
  return (x, y)

extgcd(a, b) が「 $|ax+by|=\gcd(a,b)$ を満たす整数 $x,y$ を返すこと」の証明は省略します。

最初に補題を示しておきます。
補題★：
0 でない整数 $a,b$ と整数 $x,y,g$ について、 $|ax+by|=g$ かつ $|g|< |b|$ かつ $|x|\leq|b|$ が成り立つならば、 $|y|\leq |a|$ である。
証明：
$ax+by=\pm g$ を変形すると、 $|by|=|\pm g-ax|\leq|g|+|ax|$ となり、この両辺を $|b|$ で割ると $|y|\leq|g/b|+|ax/b|$ となります。
ここで $|x|\leq |b|$ の仮定から $|x/b|\leq 1$ なので $|ax/b|\leq |a|$ であり $|y|\leq |g/b|+|ax/b|\leq |g/b|+|a|$ です。
仮定から $|a|,|y|$ は整数で $|g/b|<1$ なので、小数部分を無視してよく $|y|\leq |a|$ が成り立つことがわかりました。

もとの問題の証明をします。
証明：
$a=0$ または $b=0$ のとき、extgcd(a,b) の返り値は $(1,0)$ か $(0,1)$ になることが実際にアルゴリズムの挙動を追うことでわかるのでOKです。
$a\neq 0$ かつ $b\neq 0$ のときを考えます。
$|x|\leq |b|$ かつ $|y|\leq |a|$ が成り立つことを示します。このことが示せれば $|x|\leq |b|\leq \max(|a|,|b|)$ かつ $|y|\leq |a|\leq \max(|a|,|b|)$ となって $\max(|x|,|y|)\leq \max(|a|,|b|)$ が成り立つことが言えます。
再帰の深さに関する帰納法で証明します。
まず再帰の深さが1回で終わるケース、つまり $a\%b=0$ のときを考えます。
このときは実際にアルゴリズムの挙動を追うことで $(0,1)$ が返されることがわかるのでOKです。
次に再帰の深さが2回以上になるケース、つまり $a\%b\neq 0$ のときを考えます。
このとき、帰納法の仮定を使いつつ示すべきことをまとめると
「 $|bX+(a\%b)Y|=\gcd(a,b)$ かつ $|X|\leq |a\%b|$ かつ $|Y|\leq |b|$ を満たす整数 $X,Y$ が与えられる。 $x=Y$ 、 $y= X - \left\lfloor\frac{a}{b}\right\rfloor * Y$ としたとき、 $|x|\leq |b|$ かつ $|y|\leq |a|$ となることを示せ」です。
$x=Y$ なので $|x|=|Y|\leq |b|$ は明らかです。
$a\%b\neq 0$ なので $|\gcd(a,b)|<|b|$ になることに注意すると、「 $a,b\neq 0$ かつ $|ax+by|=\gcd(a,b)$ かつ $|\gcd(a,b)|< |b|$ かつ $|x|\leq |b|$ 」が成り立っているので補題★を使うことができて、 $|y|\leq |a|$ が成り立つことがわかります。
よって帰納法により証明できました。

2023-08-25

Difficlutyについて

パークガイド「長くなったのでブログの方でお答えしました」https://t.co/5iCqTXMgkJ #マシュマロを投げ合おう https://t.co/2YaT6kUXWU pic.twitter.com/EDONHtZPHV
— 競技プログラミングをするフレンズ (@kyopro_friends) August 25, 2023

Difficultyに関するご質問を頂いたので私たち競プロフレンズとしての見解を述べておきます。
本来であればアライさんを筆頭とした、精力的に競プロをされているアニマルガールの方々に説明をしてもらった方がよいことかもしれませんが、kyopro_friendsとしての表明ということで、私、ミライが代表してお話しさせていただきます。
これから説明する内容はあくまでkyopro_friendsの見解であり、他のwriterの方々や、AtCoder社の見解ではないことに注意してください。

・Difficultyの逆転は良いことだと思うか
良いことではありませんが、避けられるものでもありませんし、必要以上に避けようとするものでもありません。
避けられるものではない、ということについてはまたあとでご説明します。
避けようとするものではない、というのは例えば、310ではD,Eの難易度が逆転していますが、この結果を知った上で再度同じ問題を出すとしても、私たちはこの2問の順序を入れ替えようとは思わないでしょうという意味です。

・Difficultyと配点のどちらを見るべきか
基本的にこの2つには強い相関があるので、どちらを見ても結果はほとんど同じになるはずです。ほとんどの問題では解く方の得意不得意次第で変わる程度の差しかないと思います。
難易度とdifficultyが大きく離れている問題に関しても基本的には配点の方を信じてほしいところですが、本当にまれにある313Fのような難易度想定ミスの問題や、ABC288のように難易度が高くなっているセットなどもあるので、difficultyを目安に解いた方が精進はスムーズだと思います。

さて、difficultyの逆転は避けられるものではない、という話をしましょう。

まずはコンテストでの立ち回りについて考えてみます。
ABCが始まって開始70分時点でE問題までをACしました。実力的に残り30分でFGを両方解くのは無理です。配点はF問題が500点でG問題が600点です。
G問題の方が配点が大きいので、G問題が解けるならG問題を解いた方が得です。つまり
・FGどちらも解けなければレート-20
・Fが解ければレート±0
・Gが解ければレート+20
となります。FとGどちらに手をつけますか？

もちろんコンテスト本番中には「Gが解ければレートがいくら上がるか」を正確に予測することは困難ですし、自分がF,G問題を解ける可能性を正しく見積もることも困難なので、どちらを選ぶのが正しいとも一概には言えません。

ではもしF問題が500点、G問題が525点で他は先程と同じ状況だとどうでしょうか？

一見すると全く同じ状況に見えますが、「writerは、F問題とG問題の難易度の差は小さいと思っている」という情報が増えています。
ということは、先程の状況よりもG問題を解こうとする人が増えるでしょう。

このように、配点を細かくしたことで問題間の(想定)難易度の差が示されることは、「1つ飛ばして次の問題を解く」ことにインセンティブを与えます。
したがって、仮に問題が正確に難易度順に並んでいたとしても、difficultyが逆転する可能性は以前に比べ高くなります。
また、中盤までにFGの逆転が起こってしまえば、E問題までを解いた人にとって「F問題を解いても順位が対して上がらない」という状況になるため、G問題に手を付ける理由が増し逆転は加速します。
よって、特に配点の差が小さい問題が並んでいる箇所では、今後もdifficlutyの逆転は頻繁に起こると考えられます。

最後に、ABC301以降で逆転が起きた回について確認しておきましょう

301～315(15回)
315 D > E
313 F > H (FGは配点が同じ)
312 E > G (EFは配点が同じ)
310 D > E
307 C > DE
(304 D>E) 差100未満

このうち明確に難易度想定ミスと言えるのは313Fくらいでしょう。
315Dも簡単ではありませんが、E問題とここまで大きな難易度差がある問題には思えませんし、307もD問題が比較的簡単だったので、CDが逆転することまでは理解の範疇ですが、E問題と逆転するような問題にはとても思えませんね。

2023-05-30

パークガイドが教える！　けもフレ入門編

パークガイド「気合を入れて書きました。是非読んでください」https://t.co/oPugj95QiL #マシュマロを投げ合おう https://t.co/BLH5Yfv3zp pic.twitter.com/axPvtf1Hor
— 競技プログラミングをするフレンズ (@kyopro_friends) 2023年5月30日

パークガイドのミライです。
けものフレンズ入門記事を書いて欲しいとのことでしたので、ご紹介をしていきます。現実世界での出来事・役割よりも作品そのものの説明に重きをおいて紹介します。
けものフレンズという作品自体の紹介ということで、物語の登場人物としての私ではどうにも難しいところがあるので、今日はメタな視点からお話しします。

この記事の内容は2023年5月時点のものです。

要約

現行のコンテンツを追いたい→けものフレンズ３
私たち (@kyopro_friends) が準拠する世界観を知りたい→ネクソン版
そもそもけものフレンズってなんで流行ったんだっけ？→アニメ1期

けものフレンズとは

公式サイトの説明が一番わかり易いですね

この世界のどこかに造られた超巨大総合動物園「ジャパリパーク」。そこには世界中の動物が集められ、研究・飼育が行われていました。ところがある日、神秘物質「サンドスター」の影響で、動物たちが次々とヒトの姿をした「アニマルガール」へと変身！いつしか彼女たちは“フレンズ”と呼ばれるようになり、ジャパリパークの新たな主として、にぎやかに暮らすようになりました。しかしジャパリパークにはフレンズの登場とほぼ同時期に「セルリアン」と名付けられた謎の生物も出現するようになり……。

ジャパリパークを舞台に、アニマルガールのみなさんの冒険や日常を描いた物語がさまざまなメディアで展開されています。

主要コンテンツ

発表された順に並べています。

種別	タイトル	年代	通称	備考
ソシャゲ	けものフレンズ	2015～2016	ネクソン版
漫画	けものフレンズ ‐ようこそジャパリパークへ!‐	2015～2017	フライ版
アニメ	けものフレンズ	2017	アニメ1期
舞台	舞台「けものフレンズ」	2017	舞台1
ソシャゲ	けものフレンズぱびりおん	2018～2021	ぱびりおん	現在閲覧不可
舞台	あにてれ×=LOVE ステージプロジェクト「けものフレンズ」	2018	イコラブ版
アニメ	ようこそジャパリパーク	2018～2020	ようジャパ	現在閲覧不可
舞台	舞台「けものフレンズ」2 〜ゆきふるよるのけものたち〜	2018	舞台2
アニメ	けものフレンズ２	2019	アニメ2期
漫画	けものフレンズ２	2019～2020	漫画版２
舞台	舞台けものフレンズ「JAPARI STAGE!」～おおきなみみとちいさなきせき～	2019	JS
ソシャゲ	けものフレンズ３	2019～	３

この他にもソシャゲを中心にいくつかのコンテンツがありますが、主要なものは以上の作品群です。
重要な注意点として、けものフレンズの作品は、「私たちヒトが普通にいるパーク」を舞台にしたものと、「ヒトがいないパーク」を舞台にしたものの2種類のに大別され、この2つでは作品のテイストが大きく異なります。
ここで挙げた作品のうち、『ネクソン版』『フライ版』『３』、及び『ぱびりおん』のごく一部、そしてもう1作品(ネタバレのため詳細省略)が「ヒトがいるパーク」、それ以外が「ヒトがいないパーク」での物語になります。
「ヒトがいるパーク」は現代を舞台に、「ヒトがいないパーク」はそれらよりいくらか未来を舞台にしたものであると考えられています。
近年では、全ての物語が同一世界にあるとする考え方が一般的です。ただし、ゼルダの伝説シリーズのように、「大きな出来事の結果に基づいて分岐した世界での出来事である」とする解釈や、パワポケシリーズのように「"正史"は存在するが、それが作中で語られているとは限らない」とする解釈もあります。

各コンテンツについて

一部の作品は前の作品の直接の続編などであり、履修の順序に注意する必要があります。以下の個別解説で具体的に述べます。

けものフレンズ（ソシャゲ、『ネクソン版』、2015～2016）

私たち @kyopro_friends が準拠する物語です。
新米パークガイドである私ミライと主人公である"あなた"が、サーバルさんたちとともにパークを冒険します。
サーバルさんそっくりの姿をしたセルリアンとして生まれたセーバルさんと友達になるまでの物語であり、セルリアンの手からパークを取り戻す戦いの物語でもあります。
ゲームはすでにサービス終了していますが、有志による動画により、現在でもストーリーを知ることができます。

けものフレンズ ‐ようこそジャパリパークへ!‐（漫画、『フライ版』、2015～2017）

新米飼育員であるナナさんが、キタキツネさんはじめとするアニマルガールのみなさんに振り回される日常ものです。
「ヒトがいるパーク」の日常を描いた数少ない作品の1つです。

けものフレンズ（アニメ、『アニメ1期』、2017）

正体不明の人物かばんさんが、自分を知るため、パークを知るために、サーバルさんとともにパークを冒険します。
『ネクソン版』と繋がりがあるため、『ネクソン版』を知っていた方が物語をより深く理解できますが、知らなくとも最低限の理解はできる作りになっています。

舞台「けものフレンズ」（舞台、『舞台1』、2017）

オカピさんとサーバルさんが、ジャパリパークのアイドルグループ"PPP"のライバルとしてアイドルグループを結成してライブをします。
全体的に『アニメ1期』の色が濃いですが、直接の繋がりはありません。

けものフレンズぱびりおん（ソシャゲ、『ぱびりおん』、2018～2021）

現在閲覧不可
『フライ版』とは逆に「ヒトがいないパーク」の日常ものです。ショートストーリー(数百文字～数千文字)が2000本以上あります。特定の条件を満たしこれらのストーリーを解禁することがゲームの目的の1つでした。
サービス終了時に全てのストーリーを閲覧可能としたオフライン版がしばらく公開されていましたが、現在では入手不可能となっています。

あにてれ×=LOVE ステージプロジェクト「けものフレンズ」（舞台、『イコラブ版』、2018）

ツチノコさんとニホンオオカミさんを主人公に、アニマルガールのみなさんがお芝居に挑戦するお話です。お二人の終盤のやりとりには胸を打たれます。
リョコウバトさん、オーストラリアデビルさんなど、出演メンバーは意味深なチョイスとなっています。

ようこそジャパリパーク（アニメ、『ようジャパ』、2018～2020）

現在閲覧不可
『ネクソン版』を原作にしたショートアニメ(5分程度×36話)です。
おそらく尺の都合とは思いますが、ストーリーが大幅に簡略化されているので、時間が許すのであれば原作である『ネクソン版』の方を見ていただきたいところです。
もっとも、2021年のあにてれサービス終了に伴い、現在この作品を見る手段はないようですが……。

舞台「けものフレンズ」2 〜ゆきふるよるのけものたち〜（舞台、『舞台2』、2018）

ゆきやまに住むギンギツネさんキタキツネさんを主人公にした物語です。姉妹愛がテーマの1つでしょうか。
『舞台1』と同一世界観のようですが、特に前作を知らなくとも楽しめます。

けものフレンズ２（アニメ、『アニメ2期』、2019）

正体不明の人物キュルルさんが、おうちに帰るために、サーバルさんカラカルさんとともにパークを冒険します。
『アニメ1期』の直接の続編ですが、『アニメ1期』とは異なる雰囲気と強いメッセージ性を持っています。

けものフレンズ２（漫画、『漫画版２』、2019～2020）

『アニメ2期』の漫画化です。
後半ではアニメと異なる展開を見せ、アニメとは一部の重要な点が異なる結末を迎えます。

舞台けものフレンズ「JAPARI STAGE!」～おおきなみみとちいさなきせき～（舞台、『JS』、2019）

オオミミギツネさんとシベリアンハスキーさんを主人公に、これまでのけものフレンズ作品ではあまり扱われなかった展開を巧みなシナリオで扱います。
『舞台1』『舞台2』と同一世界観のようですが、特に前作を知らなくとも楽しめます。

けものフレンズ３（ソシャゲ、『３』、2019～）

『ネクソン版』より少し後のパークを舞台に、主人公である"あなた"が探検隊の隊長として、ドールさんとともにパークを冒険します。
ジャパリパークを巡って人々の思惑が交錯するシーズン1、新種のセルリアンとその秘密に迫るシーズン2、そして、新たな来園者を迎えて現在展開中のシーズン3と、物語は今なお続いています。
この作品は『ネクソン版』と『フライ版』の直接の続編です。最低限の要素は作中で説明されますが、『ネクソン版』の事前履修を強くおすすめします。またシーズン2に触れる際には『フライ版』の事前履修も強くおすすめします。

おわりに

ここでは紹介しませんでしたが、ゲームとして「ぱずるごっこ」「ピクロス」、ソシャゲとして「FESTIVAL」「KINGDOM」、ツールとして「あらーむ」、『３』に関連するショートアニメとして「ちょこけも」「カレンダレコード」、書籍として『アニメ2期』のノベライズ、Vtuberとして「けものフレンズ Vぷろじぇくと」など、けものフレンズにはこの他にも様々なものがあります。
この記事が皆さんがけものフレンズに触れるきっかけとなれば幸いです。

2023-04-24

除原理について

スナネコです。
競プロ界隈で"除原理"と呼ばれているものについて説明します。
この言葉は厳密な定義があるものではないので、これから説明することは単に「私はこうだと思っている」というお話として聞いてください。

定義

「 $g:=\zeta f$ と $x$ が与えられるので、 $f(x)$ を求めてください」という問題を、
メビウス変換の定義に基づいて $f(x)=\sum_{y\leq x}\mu(x,y)g(y)$ と求めるのが包除原理、
小さい方から順に $f(x)=g(x)-\sum_{y< x}f(y)$ と求めるのが除原理です。
ただし、シグマの中身を定義通りに計算するものだけでなく、和をとる順序を工夫したり状態をまとめたりするものもそれぞれ包除原理、除原理に含めることにします。

例

EDPC Y問題を考えてみます。
(1,1) から (H,W) への経路それぞれに対して、i 番目の壁を通らない、通る、わからないを表す o, x, ? の長さ N の文字列を対応させます。
また、「その文字列になるような経路の個数」をその文字列そのもので表すことにします。
N=3で考えます。求めるものは ooo です。

包除原理は定義通りに書くと ooo=???-(x??+?x?+??x)+(xx?+x?x+?xx)-xxx で、
除原理は ooo=???-oox-oxo-oxx-xoo-xox-xxo-xxx ですね。
このままだとどちらも項の数が $O(2^N)$ になってしまうので計算をまとめる必要があります。
ここでは詳しい説明はしませんが、
包除原理は ooo=(xが偶数個)-(xが奇数個) に
除原理は ooo=???-x??-ox?-oox にまとめるとうまく計算できます。
kiwamachanさんの解説やけんちょんさんの解説は包除原理で、snukeさんの解説やフェネックさんの解説が除原理ですね。読み比べて見てください。

例2

「 $1\leq x,y \leq N$ であって、 $\mathop{gcd}(x,y)=1$ を満たす組 $(x,y)$ の個数 $f(N)$ を求めよ」という問題を考えてみます。
包除原理で考えると、gcdが1の倍数になるケース、2の倍数になるケース、3の倍数になるケース、……を係数の辻褄をあわせながら足し引きすればいいので $\sum_{1\leq d \leq n}\mu(d)\left(\frac{N}{d}\right)^2$ になります。エラトステネスの篩のように計算すれば $O(N\log\log N)$ 、ディリクレ級数の積を考えると $\tilde{O}(N^{2/3})$ で計算できます。
除原理で考えると、全てのケースから、gcdが2になるケース、3になるケース、……を引けばいいので $N^2 - \sum_{2\leq d \leq N}f\left(\left\lfloor\frac{N}{d}\right\rfloor\right)$ になります。これは定義通りにメモ化再帰で計算すると $O(N\log N)$ 、商列挙を組み合わせると $O(N^{3/4})$ 、小さい $x$ での $f(x)$ を別の方法で先に計算しておくことにすれば $\tilde{O}(N^{2/3})$ で計算できます。

計算量

例2で見たとおり、特別な工夫をしない限り除原理の方が包除原理よりも計算量が悪くなることが多いです。
一方で、除原理は排反な事象に分割して計算できればあとは簡単なのに対し、包除原理だと足すのか引くのか何倍するのか係数を考えるところが難しいです。
包除原理がよくわからないと思うときは、いったん除原理で式を立ててゼータ関数(順序集合のなす束の構造)を見極めてからメビウス関数を書き下して包除原理に書き直す、ということもできます。私は包除原理を考えるのは苦手なので、最初は除原理で考えて、計算量が間に合わないときだけ包除原理で考え直すことにしています。

高速メビウス変換

最初の例での ooo=???-x??-ox?-oox という計算方法は、集合に関する高速メビウス変換と同じです。
（もしわからないなら、3次元の立方体の8つの頂点を000,……,111に対応させて、高速ゼータ変換/高速メビウス変換の外側のループを1回進めるごとに、どこの値がどう足し算/引き算されているか図に描いてみてください）
さらに、集合に関する高速メビウス変換は多次元累積和の逆操作でイメージできるものです。（さっきの図は描いてみましたか？）
つまり、多次元累積和の逆変換と高速メビウス変換とこのタイプの除原理はだいたい同じものということになりますね。
約数ゼータ変換/約数メビウス変換も、「素数が2と3しかない世界」を考えてみると、2次元累積和とその逆変換になっていることがわかります。

除原理？

ここまでで説明した私のイメージでは、ABC162E「Sum of gcd of Tuples (Hard)」の公式解説のO(NlogN)解法は除原理だと思うのですが、実際には「約数包除原理」と呼ばれることが多いようです。
"除原理"という言葉を私とは違う意味で使う子もたくさんいるみたいですね。