これは2023年10月に部内向けに書いたブログを外部公開向けに書き直したものです。

はじめに

こんにちは。koukawa_ppです。
さて、今回はヤケクソなタイピングゲームを作るというタイトルで、ブログを書きます。
開発言語はPythonです。

ここでは、以下のものを作ります。

• ゲーム本体
• タイピングゲームのTASツール

また、コードは こちらの GitHub リポジトリ にて公開しております。

開発環境

• Windows 10 Home 64bit
• Python 3.11.4
• Visual Studio Code

作ることになったいきさつ

まずそもそもタイピングゲームとは、皆さんご存じの通り、ある文章を出され、それをいかに早く正確に打ち込めるかを楽しむゲームです。
まあでもタイピングゲームが得意な方なら、この手のシンプルなタイピングゲームはまあ瞬殺でしょう。
退屈していらっしゃるのではないでしょうか。
そうするとシンプルなタイピングゲームを作成するのは野暮というもの。

そのような中で、このタイピングゲームが得意な方でもタイプが遅くなるようなチャレンジングなタイピングゲームを作れないだろうか。
このような考えのもと、この企画を考えました。

ぶっちゃけて言うと、正道では対抗できそうにありません。
そこで、何か普通のタイピングゲームより難しい何か、を作ることを考えました。

ここで、以下のような工夫点を導入したタイピングゲームを作りました。

• 文字列をランダムにする
• 特殊文字を入れるようにする
• シーザー暗号を導入する

まず最初の要素によって、「このような組み合わせはよく出てくるな」や、打ちなれているキーだけでできるタイピングゲームを排除します。
次に、特殊文字を入れることにより、あたかも複雑なパスワードを入力しているように感じさせます。
これら二つの要素は、ひょっとするとどこかのタイピングゲームにあるかもしれませんが、最後の要素を導入することで、多分他にはないタイピングゲームを完成させました。
最後の「シーザー暗号を導入する」とは、以下のようなものです。

eznoafowe (2)

とあったら、これら各々の文字を2つ後ろにずらして入力する必要があるということです。
つまりこの場合は、

gbpqchqyg

と入力する必要があるわけです。
つまりこのタイピングゲームは、タイピング速度もそこそこに、アルファベットの順番を即座にずらせることも求めたものなのです。

ゲームで遊ぶ

venv を作成する

まず、今回のプログラムでは pyyaml というサードパーティ製ライブラリが必要ですので、それをインストールする仮想環境 (venv) を用意します。

今回は typing_env という名称の仮想環境を作ります。

python -m venv typing_env

そしてこれを起動します。

./typing_env/Scripts/activate

もし Linux や、または macOS もそうだったと思うのですがその場合は、

source typing_env/bin/activate

とする必要があります。


そうすると、このような感じになります。

(typing_env) PS [directory name]

環境をアクティベートしたら、pip でライブラリをインストールします。

pip install pyyaml

これでいったん仮想環境は完成です。

configファイルを作成する

では次に、conffigファイルを作成します。
configファイルはyamlファイルで提供しており、この内容を変えることでゲームの設定を変えることができます。

game_config.yamlnum_problems: 10
min_chars_length: 20
max_chars_length: 30

contain_capital_char: true
contain_number: false

# If you want problems to contain special char, you have to set.
# Otherwise, set null
contain_special_char:
  - null

caesar: 0
random_caesar: false
not_negative: true

初期設定としてはこんな感じだと思います。
各々について説明します。

この部分を変更して、遊んでみてください。

実際に動かす

では、以下のようにしてプログラムを実行してください。

python yakekuso_typing.py

そうすると、始まります。

(typing_env) PS [directory name]> python .\yakekuso_typing.py
press Enter to start. 
1   onEhBqIsdDbxGLcskUThOiK
>>> onEhBqIsdDbxGLcskUThOiK
2   DqxMHGXdneoacvZBmqQuUkuKmw
>>> DqxMHGXdneoacvZBmqQuUkuKmw
3   GnlJjOpBsiHxAdYsrObjLCxVFUpc
>>> GnlJjOpBsiHxAdYsrObjLCxVFUpc
4   cLXctVjCSZPehUEPBmPmGeUiXH
>>> cLXctVjCSZPehUEPBmPmGeUiXH
5   RXnkbMTSGvuDVoyyZLZqilL
>>> RXnkbMTSGvuDVoyyZLZqilL
6   FKuUavxxRPTRhKybsdtmJ
>>> FKuUavxxRPTRhKybsdtmJ
7   RrGVvVbYLgBrveHnIStyzuILto
>>> RrGVvVbYLgBrveHnIStyzuILto
8   YwMhVThewpHiJxZigwsJG
>>> YwMhVThewpHiJxZigwsJG
9   kRdaNZRnmMyRaXaQVIQINaf
>>> kRdaNZRnmMyRaXaQVIQINaf
10  faBdlXTMBGFJzicJWOLP
>>> faBdlXTMBGFJzicJWOLP

Spent time: 91.1295325756073
2.601 types per second.
(typing_env) PS [directory name]>

プレイにかかった時間はEnterを押してからカウントされるので、
準備ができたらEnterを押すという形でOKです。

シーザー暗号のパターンもできます。

game_config.yaml# omitted

caesar: 2
random_caesar: true
not_negative: true

このようにconfigファイルを変更して、実行してみてください。

(typing_env) PS [directory_name]> python .\yakekuso_typing.py
press Enter to start. 
1   QXXORCCWKlKtThBSQOquYSQAfZYW (1)
>>> RYYPSDDXLmLuUiCTRPrvZTRBgAZX
2   TmSKfJbZUCxpvJlBnFMPdJTrkm (2)
>>> VoUMhLdBWEzrxLnDpHORfLVtmo
3   NtrQMpnVTwmgoGZADRPWddC (0)
>>> NtrQMpnVTwmgoGZADRPWddC 
4   DeyxfmYDWTWPherccZKvfYsLm (2)
>>> FgazhoAFYVYRjgteeBMxhAuNo
5   TuwjoLtzqhRtvbdQCRfolDUl (2)
>>> VwylqNvbsjTvxdfSEThqnFWn
6   cwZdDkVSbCJvNWfNbFEaiqxoS (2)
>>> eyBfFmXUdELxPYhPdHGckszqU
7   YllpIgYwwCoNXFNItGmIcx (1)
>>> ZmmqJhZxxDpOYGOJuHnJdy
8   dVPCvUpIvNYTuJhAUewG (1)
>>> eWQDwVqJwOZUvKiBVfxH
9   qmCwtKihENzegpBomAWrQzykzBhkLH (1)
>>> rnDxuLjiFOafhqCpnBXsRazlaCilMI
10  YIWRSszClsfPoeZYDpremakA (0)
>>> YIWRSszClsfPoeZYDpremakA

Spent time: 372.90026021003723
0.662 types per second.
(typing_env) PS [directory_name]>

なぜタイピングの問題10問で6分も掛けなければならないのか、という話ですが、これ相当難しいです。
日ごろから任意の英文について文字ずらしをしていれば出来たかもしれませんが、そんな毎日毎日暗号化したい英文なんて扱うわけがないですから。
（というか今シーザー暗号してもすぐバレる）
ただとりあえず、うまくシーザー暗号のように文字ずらしができていることが分かります。
ぜひいろいろなconfigにして、試してみてください。

TASツールを作る

さて、タイピングゲームとなれば、よく使われるのはTASツールです。
しかもオープンソースのタイピングゲームみたいなものですから、アルゴリズムも丸わかりです。
そうなると、最速でクリアしたいという感想が出てくるのは当たりまえです。
無論人力で最速を目指せればそれもすごいですが、TASツールを作るのもまた一つの手だと思います。

次のようなコードを作成しました。

tas_typing_game.py# Reference:
# https://qiita.com/HidKamiya/items/e192a55371a2961ca8a4#subprocesspopen%E3%81%AB%E3%82%88%E3%82%8B%E8%87%AA%E7%94%B1%E5%BA%A6%E3%81%AE%E9%AB%98%E3%81%84%E5%87%A6%E7%90%86

import re
import subprocess

from yakekuso_typing import caesar_encrypt

if __name__ == '__main__':
    p = subprocess.Popen(['typing_env/Scripts/python.exe', 'yakekuso_typing.py'],
                         stdin=subprocess.PIPE,
                         stdout=subprocess.PIPE,
                         stderr=subprocess.PIPE,
                         encoding='utf8')

    p.stdin.write('\n')
    p.stdin.flush()
    while p.poll() is None:
        line = p.stdout.readline().strip()
        
        if re.search('press Enter to', line):
            p.stdin.write('\n')
            p.stdin.flush()
        elif re.search('Spent time', line) or re.search('types per second', line):
            print(line, flush=True)
            p.stdin.write('print()\n')
            p.stdin.flush()
        elif re.search('[0-9][0-9\s][0-9\s] (\S+) \([\-0-9]+\)', line):
            print(line, flush=True)
            m = re.search('([0-9][0-9\s][0-9\s]) (\S+) \(([\-0-9]+)\)', line)
            p.stdin.write(f'{caesar_encrypt(m.group(2), int(m.group(3)))}\n')
            p.stdin.flush()
        elif re.search('[0-9][0-9\s][0-9\s] (\S+)', line):
            print(line, flush=True)
            m = re.search('([0-9][0-9\s][0-9\s]) (\S+)', line)
            p.stdin.write(f'{m.group(2)}\n')
            p.stdin.flush()

今回は subprocess という標準ライブラリを使っています。
これを使うことで、このPythonプログラムを実行しながら、他のプログラムを別プロセスで実行できます。
また、reは、正規表現を扱うためのライブラリです。
Regular Expression の略です。
また、yakekuso_typing.pyからシーザー暗号で暗号化する関数をインポートしています。
ソースコードをそのまま保存しているので、簡単に再利用できます。

さて、実行においては yaml が必要なので、これまでと同様 typing_env 内で実行してください。

(typing_env) PS [directory name]> python .\tas_typing_game.py
>>> 1   vYfBBhgPBIrHEApzddZJlWO (2)
>>> 2   nycYSUdOjGrVYhNqKyzULNNQILz (1)
>>> 3   YwezVOGnscquhFrbFKFukvydOZgpVa (0)
>>> 4   DCVqjKxsgaVdDggsfxcPtYu (1)
>>> 5   CdKVamkVelTcJqYfBtOAUItzLEoAO (0)
>>> 6   dhAVcJTEbKLCChYDTvOGemH (0)
>>> 7   juIZbrkwWrZvBNBSagdYDvMI (2)
>>> 8   vCiGCzAVWGBASuJSQLWnGOiM (0)
>>> 9   DvUsENKbVrZdsoczGaVagEQIv (1)
>>> 10  BSJcmfjmvoEIuIygfmyaAnYkLZqdD (1)
Spent time: 0.00768733024597168
33431.633 types per second.
(typing_env) PS [directory_name]> 

こんな感じで出てきます。
平均して一秒あたり33431回ほどタイプしていることになっていることが分かります。

ちなみに config で caesar を0にしたとき、
tas_typing_game.pyは以下のような感じで実行できます。

(typing_env) PS [directory name]> python .\tas_typing_game.py
>>> 1   SgzxWXQVOAyJYDOJXXAWxh
>>> 2   tDevbinTnlfxSvSKmkptYYZ      
>>> 3   dnWLvBhusCwsmeBSXalSjVpircjoO
>>> 4   EdFNZcrsVoDZuxbKmltS
>>> 5   zFTmkzrpIWeRFwzMgtRsaAZi     
>>> 6   IRvROZVmKRyFhPMrlRqkuTmKwCFW 
>>> 7   VToRbXqNYizmRHMpomehdrTnhlH  
>>> 8   OHMSWCVhGPGqZsnPBuHtBU       
>>> 9   fXWJrPUMJECsvRlbxajwL        
>>> 10  lYgJSVgSOwCUKoVjSJCgV        
Spent time: 0.0046956539154052734    
50472.204 types per second.
(typing_env) PS [directory name]>

ここでは caesar_encrypt などを動かす必要が無くなるので、
実行速度がまた速くなります。
平均して一秒あたり50472回ほどタイプしていることになっていることが分かります。

体験版

以下に今回のタイピングゲームで、文字がズレるバージョンを実装いたしました。
このバージョンのコードも GitHub に上げておりますので、よろしければご覧ください。

時間などは測定しておりません。
下の入力欄には0以上3以下の数字を入力できます。最大この文字数分だけずれます。
入力欄において数字を入力したら、「変更」ボタンを押すことでその範囲内で出題されます。

おわりに

本日はタイピングゲームを作り、紹介してきました。
ぜひプレイして楽しんでください。
最後までお読みいただき、ありがとうございました。

このブログ記事は、2023年8月に部内向けに書いたものを外部公開向けに変更したものです。

はじめに

こんにちは。koukawa_ppです。

さて、螺旋はお好きですか？
ここでいう螺旋とは、二次元平面における螺旋です。

こういうタイプのもです。
こういった螺旋について、今回は深く掘り下げていこうというお話です。

なお、今回取り上げる螺旋には、以下のようなものがあります。

• アルキメデスの螺旋
• サックスの螺旋
• ウラムの螺旋

これらについて、特にPythonのコードも交えながら、色々螺旋を描いてみましたので、共有したいと思います。

なお、今回のコードや画像ファイルは全てこちらのGitHubリポジトリに入れてあります。
ぜひご覧ください。

実行環境

• Windows 10 Home 64bit
• Python 3.9.13
• Visual Studio Code

アルキメデスの螺旋を描く

そもそも、なぜ螺旋を描きたいとなったのかと言いますと、まずどこかで、「素数螺旋」というものがある、ということを耳にしたためです。
とは言えその時は螺旋について詳しく知らなかったので、とりあえず何も考えずにオーソドックスな螺旋を描こうという話になりました。

ここでいうオーソドックスな螺旋こそが、アルキメデスの螺旋です。
すなわち、極座標表示すれば、$r=a\theta$ と表される曲線です。
最初は無知故適当に見えればよいかという形で描画していたのですが、あとから調べてみるとこちら や数Ⅲの教科書などに載っていたので、これに則って描画することにしました。
この参考のページには、コンパスと定規で描く近似法を示していただいています。

次の問題です。
$r=a\theta$ という式を得られたわけですから、
あとはこれを $x=r\cos x,y=r\sin x$ という形で変数変換すれば、
これを描画することはお手の物です。
しかし、このまま何も考えずに $\frac{\pi }{180}$ ラジアンずつなどと描画すると、こうなります。

そうです、直径が大きくなればなるほど、
もっと言ってしまえば $\theta$ が大きくなればなるほど、
点と次の点の間があまりにも空きすぎてしまい、
綺麗な螺旋を描けなくなってしまうのです。

これを改善するために、螺旋上に等間隔に点を打つ必要が出てきました。
これを実現する方法は簡単です。

1. ある基準の長さ $d$ を設定する。
2. ある時点で最後に打った点と基準線のなす角度を $\alpha$ として、次に打つべき点と基準線のなす角度を $\beta$ とするとき、螺旋の $\alpha \leqq \theta \leqq \beta$ の部分における曲線の長さが、$d$ と一致すればよい。
3. 2.から、適切な角度 $\beta$ を求める。

発想としてはそこまで難しくありません。
しかし、行うは難しです。
螺旋の長さなんてそう簡単に求められるわけがありません。
……いや、求めます。

調べてみると、極座標における曲線の長さを求める公式がありました。
$\theta$ が ${\theta }_0$ から ${\theta }_1$ までにおける曲線の長さ $L$ は、

$$L={\int }_{{\theta }_0}^{{\theta }_1}\sqrt{r^2+{\left(\frac{dr}{d\theta }\right)}^{2}d\theta }$$

で与えられるとのことです。詳しくは こちら をご覧ください。いつもお世話になっております。
なのでこの曲線の長さは、

$$L={\int }_{\alpha }^{\beta }\sqrt{r^2+{\left(\frac{dr}{d\theta }\right)}^2}d\theta ={\int }_{\alpha }^{\beta }\sqrt{(a\theta {)}^2+a^2}d\theta =a{\int }_{\alpha }^{\beta }\sqrt{{\theta }^2+1}d\theta$$

と表されます。
次に こちら によれば

$$\int \sqrt{x^2+a^2}dx=\frac{1}{2}(x\sqrt{x^2+a^2}+a^2\log x+\sqrt{x^2+a^2})$$

とのことですので、つまり

$$a{\int }_{\alpha }^{\beta }\sqrt{{\theta }^2+1}d\theta =\frac{a}{2}(\beta \sqrt{{\beta }^2+1}+\log (\beta +\sqrt{{\beta }^2+1})-\alpha \sqrt{{\alpha }^2+1}-\log (\alpha +\sqrt{{\alpha }^2+1})$$

というわけです。これが $d$ と等しくなる $\beta$ を見つけられれば、晴れて螺旋上に等間隔で点を打つことができます。


では、ある $a,\alpha$ と $d$ が与えられたとき、どのようにして $\beta$ を求めれば良いのでしょうか。
直感から、以下の方程式を解けばいいことが分かります。

$$\frac{a}{2}(\beta \sqrt{{\beta }^2+1}+\log (\beta +\sqrt{{\beta }^2+1})-\alpha \sqrt{{\alpha }^2+1}-\log (\alpha +\sqrt{{\alpha }^2+1})=d$$

ここは、文明の利器、scipy を頼ることにします。
scipy.optimize.fsolve() 関数は、第一引数に $f(x)=0$ の解を求めたい関数 $f(x)$、第二引数にその解の値に近い $x$ の値を与えることで、その方程式の近似解を求めることができるという優れものです。

ここで、$a$ と $d$ については、draw_spiral() 関数の引数の radius と distance をそれぞれ与えればよく、また $\alpha$ は、前回の $\theta$ の値をそのまま使えばよいです。
では、fsolve() 関数の第二引数には何を与えるかということですが、$\beta$ に近い値を与えればよいということなので、ここは素直に $\theta$ の値を与えればよいということになります。

これらを実現するために使っているコードというのが、

draw_spiral.pyfrom scipy import optimize

def _length(x):
    return a * (x * np.sqrt(x * x + 1) - theta * np.sqrt(theta * theta + 1) + np.log(x + np.sqrt(x * x + 1)) - np.log(theta + np.sqrt(theta * theta + 1))) / 2 - d

def draw_spiral(
        draw_index: set[int] = None,
        width: int = 1000,
        height: int = 1000,
        radius: float = 5.0,
        distance: float = 1.0,
        num_of_cycle: int = 10,
        file_name: str = None
    ) -> None:
    # 中略
    while theta < 2 * math.pi * num_of_cycle:
        # 中略
        theta = optimize.fsolve(_length, theta)[0]

というわけです。
また、どうも optimize.fsolve の第一引数にとる関数は、引数に ndarray を取る必要があるらしいので、_length() 関数にはやむなく numpy の関数を用いて、optimize.fsolve() 関数の0番目を theta に代入するという形になっています。
（最初 math を使ってたらwarningが出てきた……）
これを使って、等間隔に点を打つと以下のような感じになります。

点と次の点の間が等しくなったような気がしませんか？
これでうまく機能しました。


次に、draw_spiral() 関数に draw_index という引数があると思いますが、ここは初期値として None になっています。
ここに set を渡すと、指定されたインデックスだけの点が表示されるようになります。
たとえば、draw_index に 0, 4, 6, 9 と代入されているとすると、0, 4, 6, 9番目の点だけが表示されるようになります。
これでお分かりのように、点は0番目から開始します。
set にランダムに数字を追加すると、以下のようなランダムな螺旋が描けます。

なお、最後に ImageOps.flip() を実行していると思います。
これは、僕が左上が原点だと思っていたところ、pillow によると左下が原点であるということらしいので、つじつまを合わせるために上下反転させたということです。
GitHub の方に API リファレンスを載せておきますので、draw_spiral.py でいろいろ遊びたくなりましたらそちらをご覧ください。


さて、これで螺旋をランダムに描くと、以下のような感じになります。

まあ綺麗っちゃ綺麗かもしれませんが、
ランダムさが生んだ綺麗さですよね。

無理数も無理やり螺旋にしてみましょう。
たとえば、 $\sqrt{2}$ は、1.41421356...と続きますが、0から始めて各位の数字を足していくという数列を考えてみましょう。
つまり、$\sqrt{2}$ の小数第 $n$ 位を $b_n$ として、今回 set に追加する数字の内小さい方から $n$ 番目を $a_n$ とするなら、

$$a_0=0,a_1=1,a_{n+1}=a_n+b_n$$

とすれば良いわけです。
こうすると、$a_0=0,a_1=1,a_2=5,a_3=6$ と求められていきます。
時々 $b_n=0$ となりますが、それは $a_{n+1}=a_n$ として処理することにして、そうすると無理数から作る螺旋も一意に決定することができます。
こうして $\sqrt{2}$ から作った螺旋は以下のようになります。

$\sqrt{3}$ は以下の通り。

$\sqrt{5}$ は以下の通り。

良さげですね。

では、待ちに待った素数螺旋を描いてみましょう。
素数のところだけ表示させた螺旋は以下のようになります。

ん？規則、的？

……まあ確かに途切れてるところは似ているし？
周期的に途切れてるし？
まあ綺麗に見えるし？
素数螺旋ってこういうものなのかぁ～（棒）

ウラムの螺旋

koukawa_ppはこんらんした！
そすうの　らせんが　そこまで　うまく　みえない！

さて、こんなところで終わっていられません。
こういった模様になってくると、人によって評価が分かれるところ。
本来大多数の人が規則的だと思えなければ、あとは定量的に測るなどして、（無理やり）規則性を発見できなければ、それは単なる見た目だろ、という話になってしまいます。
多くの人に認められた黄金比でさえも、確かに美しくは見えるがなぜかはわからない、といったように、あるものが美しい理由というのが科学的に解明されたようなものは決して多いわけではありませんが、今回のこれについては大多数が美しいと感じるかと言われると、多分ハテナマークを浮かべる人が一定数いると思ったわけです。

そこでネットをいろいろ漁ってみると、「ウラムの螺旋」というものを見つけました。

こちら によると、ウラムの螺旋は、中心から螺旋を描くように描画されます。
数字は格子点上にあるようにも解釈できます。
このことから、ウラムの螺旋もPythonで描いてみようということになりました。

そうして作ったのが、draw_ulam_spiral.py です。
これは、アルゴリズムの部分が若干ややこしくなっています。

このように螺旋を描画していくのが、ウラムの螺旋です。
まず1のところを座標(0,0)として、2のところを(1,0), 4のところを(0,1)とします。
このとき、ある方向に進んで、曲がって、進んで、曲がってを繰り返すと思いますが、
この曲がる点というのは、上下左右に4つあります。

そして、各々の点について、次に曲がる点は青字のところになります。

つまり、

としておいて、これらの座標に到達したときは、
右下の点の座標は右下に、
右上の点の座標は右上に、
左上の点の座標は左上に、
左下の点の座標は左下にずらせばよいわけです。

つまり2(1, 1)にたどり着いた時は、

とすればよいのです。

さて、これらのことを使ってアルゴリズムを見ていきましょう。
まず、いくつか変数を定義しています。

draw_ulam_spiral.pyx, y = 0, 0
lrx, lry = 1, 0
urx, ury = 1, 1
ulx, uly = -1, 1
llx, lly = -1, -1
dx, dy = 1, 0

x, yは、現在いる座標を示しています。
lrx, lryは右下の座標、urx, uryは右上の座標、
ulx, ulyは左上の座標、llx, llyは左下の座標です。
また、dx, dyは次x方向およびy方向にどれだけ進むかを表しています。

(x, y)を描画したら、次の座標を求めるために、こうします。

draw_ulam_spiral.pyx += dx
y += dy

次に、今いる座標が右下、右上、左上、左下のいずれかの場合は、dxおよびdy、また右下、右上、左上、左下のうち現在いる場所の座標を次のものに変更させる必要があります。

まず右下にいる場合、次は上の方向に進む必要があるので、

draw_ulam_spiral.pydx = 0
dy = 1

とすればよいことが分かります。
次に、右下の座標を一つ右下にずらすので、

draw_ulam_spiral.pylrx += 1
lry -= 1

とすればよいことが分かります。これが、

draw_ulam_spiral.pyif x == lrx and y == lry:
    dx = 0
    dy = 1
    lrx += 1
    lry -= 1

となっている理由です。
これを他にも右上、左上、左下についてelifでくっつければOKです。
本当はdictとかで取得すればよかったと、今さらながら気がつきました。

あとこのまま行くと、点と点の間の長さを決められなくなるので、実際に描画する際は、xおよびyにdistanceを掛けることで最終的な座標を求めています。

これを使って実際にウラムの螺旋を描くと、こうなります。

……まあ、螺旋も何もないですよね。
なぜならこれは若干厄介な方法で格子点を描画しているのに過ぎないのですから。
この螺旋の本領を発揮するのは、先ほどアルキメデスの螺旋でもやったように、部分的に描画しない点を設定することです。

この描画する点を指定するのは、先ほど同様 draw_index です。
先ほどと同じように指定できます。
ただここで一つ違うのが、先ほど点は0番目からカウントと言っていましたが、ここでは base_val 番目からカウントを行います。
それゆえ、draw_spiral() 関数の引数で指定をしない限り、1番目からのカウントになることに注意してください。
ではこれで素数螺旋を描画すると、こうなります。

おっ、きれいですね。
何かx状に模様が入っています。
ただこれは、ウラムの螺旋だからこうなっただけかもしれません。
ランダムに螺旋を作ってみましょう。

確かに、先ほどのように整った螺旋には見えません。
$\sqrt{2},\sqrt{3},\sqrt{5}$ で、さっきと同じルールで作った螺旋も見てみましょう。

特段規則性は見られませんね。
素数でないと、今のところはああいった模様は描けないみたいです。

あともう一つ、先ほどの記事によれば、こんなこともあるらしいですね。

そしたらやってみるしかないですよね。
その実、そのために base_val を設定したのもあります。
というわけで、41で見てみると、以下のようになります。

確かに中心部にかなりはっきりと斜め線が見えている……。
これはオイラー素数の話に繋がってくるみたいですが、
ここではその話はしません。

ウラムの螺旋と最小公倍数

ウラムの螺旋については、これともう一つ面白いものを見つけたので、そちらも紹介していきましょう。

最初のセッティング通り、base_val を初期値1のままにして、以下のようなプログラムを実行しました。

draw_rule_ulam_spiral.pyfrom draw_ulam_spiral import draw_spiral

hmp = 150000
for rule in range(1, 1001):
    draw_index = set([i for i in range(hmp) if i % rule == 0])
    draw_spiral(draw_index=draw_index, num_all_points=hmp, file_name='rule_ulam_spiral_{}.jpg'.format(rule))

ここでのdraw_ulam_spiralは、draw_ulam_spiral.pyのことです。
こうすると、rule個おきに点を打ったウラムの螺旋の画像ファイルをゲットできます。
なお、$1\leqq rule\leqq 1000$ です。
これについて、ruleが2, 3, 6の場合を見てみましょう。

同じ雰囲気を感じませんか？
そうです、思い付けば「当然だよね」となりますが、よく考えてみると、このruleが6の場合のウラムの螺旋は、
ruleが2の場合の螺旋とruleが3の場合の螺旋を比べて、どちらにも描画されている点からなる螺旋であるということです。
これは、6が2と3の最小公倍数であることから求まります。

24の場合も同様で、8と3の螺旋のうち、重なっている点のところだけが描画されます。
下の図は、上からruleが3, 8, 24のウラムの螺旋です。

8や24の場合、右上に斜め線が見えるという形なんですよね。
実は16や32の場合は、左下に斜め線が見えます。
下の図です。

かなり不思議です。
ウラムの螺旋は今回初めて知りましたが、面白かったです。

サックスの螺旋

しかし、このまま行くと、アルキメデスの螺旋において、等間隔に点を打つということを実現するため、難しい積分の話までしていたことが無駄になってしまいます。
何とかしてアルキメデスの螺旋を使った、綺麗な素数螺旋を描くことはできないものかと調べてみました。
先ほどの記事では同時に、「サックスの螺旋」というものがあることも紹介されていました。
書き方としては、こちらのページ が詳しいと思います。
中心には0を置き、あとは周回ごとに平方数を配置するというものです。

アルゴリズム的にはアルキメデスの螺旋とさほど変わりませんが、やることは極端に複雑になっていきます。

まず、素数の処理を簡単にするために、0と1については最初に配置しておくことにします。
これを行っているのが、以下の部分です。

draw_sacks_spiral.pyd = _local_length(2 * math.pi, 4 * math.pi) / 3
if all_show:
    draw.point((width / 2, height / 2), fill=(255, 255, 255))
    num_of_points += 1

    r = radius * 2 * math.pi
    draw.point((width / 2 + r * math.cos(2 * math.pi), height / 2 + r * math.sin(2 * math.pi)), fill=(255, 255, 255))
    theta = optimize.fsolve(_length, theta)[0]

これはall_showがTrueの場合にのみ実行されるので、素数のみを見せる場合、すなわちall_showがFalseの場合は実行されません。

まず最初のdraw.pointが、0の点を描画する処理です。
その次のdraw.pointの周辺が、1の点を描画する処理です。

次に、1, 4, 9, 16, ...を配置するのは、それぞれthetaが2π, 4π, 6π, 8π, ...となるときです。
そして、2πから4πの間に2と3、4πから6πの間に5から8、6πから8πの間に10から15……といったように、それぞれ等間隔に配置する必要があります。

これは言いかえると、
2πから4πの間を3等分、
4πから6πの間を5等分、
6πから8πの間を7等分、
……という感じだと言えます。
これを一般化すると、
2nπから2(n+1)πの間を2n+1等分と言えます。
このことを使って、thetaを求めていきます。

draw_sacks_spiral.pynext_i = 2
while i < num_of_cycle * num_of_cycle + 1:
    # 中略
    if i == next_i * next_i - 1:
        theta = 2 * next_i * math.pi
    elif i == next_i * next_i:
        d = _local_length(2 * next_i * math.pi, 2 * (next_i + 1) * math.pi) / (2 * next_i + 1)
        next_i += 1
        theta = optimize.fsolve(_length, theta)[0]
    else:
        theta = optimize.fsolve(_length, theta)[0]

まず、next_iとは、現在のiより大きい最小の平方数の正の平方根を与えます。
それゆえ、iを2で初期化するときに、next_iも2で初期化されています。
（2より大きい最小の平方数は4であり、この正の平方根は2であるため）

まず、iがnext_i * next_iより1小さいときは、次のiがnext_i * next_iであることが分かります。
それゆえ、誤差を無くすために、thetaに2 * next_i * math.piを代入しています。
なぜ2 * next_i * math.piなのかということですが、これは具体例を考えればよいです。
たとえば現在のiが3のとき、次の平方数は4であり、next_iは2であるので、iはnext_i * next_iより1小さいことが分かります。
4はthetaが4πのところに配置されるべきなので、2 * next_i * math.piは成り立ちます。
または、現在のiが8のとき、次の平方数は9であり、next_iは3であるので、iはnext_i * next_iより1小さいことが分かります。
9はthetaが6πのところに配置されるべきなので、2 * next_i * math.piは成り立ちます。

次に、iがnext_i * next_iと等しい場合を考えます。
このとき、iは平方数です。これより、次のいくつかについて、どの間隔で点を配置すべきかを求める必要があります。
先ほどの話より、現在のthetaは2 * next_i * math.piであることが分かります。
つまり、

先ほど記述したこのルールに則ると、
2 * next_i * math.pi から 2 * (next_i + 1) * math.pi の間を 2 * next_i + 1 等分した値を、dに代入する必要があるということになります。

これは_local_length 関数において、α=2 * next_i * math.pi, β=2 * (next_i + 1) * math.pi を代入し、これを 2 * next_i + 1 で割ったものと一致します。
これより、dは、

draw_sacks_spiral.pyd = _local_length(2 * next_i * math.pi, 2 * (next_i + 1) * math.pi) / (2 * next_i + 1)

という更新式が得られます。
次に、next_i * next_i より大きい最小の平方数は、next_i + 1 * next_i + 1 ですから、この正の平方根は、next_i + 1 です。
ゆえに、next_i を1増やす必要があります。
そのあとはいつものように、thetaを更新すればよいです。

iがこのいずれの条件も満たさない場合は、thetaを普通に更新すればよいです。

これらのことをまとめると、先ほどのようなコードが得られます。


他のことについては、アルキメデスの螺旋でやったこととほぼ同じです。
ただし、draw_indexを無くし、その代わりにall_show引数を追加しました。
ここでall_showをTrueにすると、全ての点が表示されます。
反面、all_showをFalseにすると、素数の点だけが表示されます。

さて、all_showをTrueにして実行してみると、以下のようになります。

ここで、素数に切り替えてみます。すると、

なんか素数が連なっている部分もありそうですね。
radiusを小さくして、より大きな範囲を表示すると、以下のようになります。

なんと！という感じです。
やっぱり、なんか綺麗ですよね。
よくできてます。

おわりに

本日は、様々な螺旋をご紹介しました。
何かお気に入りの螺旋(?)は見つかりましたか？
また、付属のプログラムもいろいろいじっていただければ幸いです。
最後までお読みいただき、ありがとうございました。

こちらの記事は2022年11月に部内向けに書いたブログを、外部公開向けに書き直したものです。
そのため不勉強な部分もあるかと思いますが、温かい目でご覧いただければ幸いです。

はじめに

こんにちは。koukawa_ppです。

唐突ですが、「一度はやってみたいな」と思うことはありますか？
僕はタイトルにもありますが、「任意のファイルを音楽にできないか」という野望を抱えながら、つい最近まで過ごしてきました。
とはいえ、「どうすれば任意のファイルを音楽にできるだろうか？」という壁にぶち当たります。
今回は自分なりにですが、任意のファイルをmidiファイルに変換するプログラムを作成しましたので、皆さんに紹介したいと思います。

なお、使ったファイルは こちらのGitHubリポジトリ に入れてあります。

環境

• Windows 10 Home 64bit
• Visual Studio Code
• Python 3.11.0（ここまで新しくなくても動作するはずです）

いきさつ

ファイルをもとにして、何かしらの他のものに変えるというのは案外やりやすいと思っています。
なぜならファイルのバイナリを用いれば、そこから他のものを作り出すということはかなり容易だからです。
適当な話、これらビットに何かしらの役割を付与して、そこからmidiファイルを作り出そうという発想はありました。

では、得られたそのビット列を、どのようにして音楽にするかということです。
もちろん適当にコードとメロディーとリズムを組み合わせるだけで、それを音楽というのはいささか気が引けます。
素晴らしい音楽になるかはさておき、とりあえず「こういう曲ありそうだな」レベルまでには引き上げる必要があるわけです。

そこでこのビット列から、どのようにそういったものを作成する努力をしたか、説明していきたいと思います。

バイトの振り当て方

概要

このファイルを作るにあたって、以下のようなメモを用意しました。

1バイト
ドラムのリズム設定

2バイト
バスドラムについて1

3バイト
バスドラムについて2

4バイト
バスドラムについて3

5バイト
バスドラムについて4

6バイト
バスドラムについて5

7バイト
フィルインで叩くドラムを設定1

8バイト
フィルインで叩くドラムを設定2

9バイト
フィルインで叩くドラムを設定3

10バイト
フィルインで叩くドラムを設定4

11バイト
(1小節目)リズムを選択する

12バイト
(1小節目)コードを選択する

13~20バイト
(1小節目)鳴らす音を設定
（鳴らさないところは無視）

21バイト
(2小節目)リズムを選択する

22バイト
(2小節目)コードを選択する

23~30バイト
(2小節目)鳴らす音を設定
（鳴らさないところは無視）

31バイト
(3小節目)リズムを選択する

32バイト
(3小節目)コードを選択する

33~40バイト
(3小節目)鳴らす音を設定
（鳴らさないところは無視）

41バイト
(4小節目)リズムを選択する

42バイト
(4小節目)コードを選択する

43~50バイト
(4小節目)鳴らす音を設定
（鳴らさないところは無視）

以上のような設定に則って、どのように作ることにしたのかということをざっくり説明します。

ドラムのリズム設定(1バイト目)

そもそもドラムっていうのは、適当に作ってもかっこよく聞こえます（経験上）。
ただしそれが叩けるかどうかは別問題と言ったところです。
今回作ったリズムでは、ハイハットと同時にフィルインも鳴っているので、この状況においては叩けないリズムも作られていると思います。
いつも僕が作るときには、基本なるべく生身の人間でも叩けるように作っています。

今回、一度決めたドラムは基本的に4小節単位で繰り返されます。

まず1バイト目では、おおよそドラムのリズムを設定しています。
ビット列については、以下のように決めています。

ハイハットのリズムの選択方法については、後で説明します。

バスドラムについて(2~5バイト目)

バスドラムについては、以下のように決定しています。

2バイト目

3バイト目

4バイト目

5バイト目

6バイト目

二つ目とか四つ目の十六分音符とは何かということですが、

上のような感じです。
このような表現方法は後でも出てきます。

このことから分かるように、バスドラムについては、鳴らす確率が以下のように決められていると分かります。
（ただし、ビットの並び方が同様に確からしいとき）

基本的に1拍目と3拍目が鳴りやすいように細工しています。
2つ目だけが鳴るということはかなり稀です。

フィルインで叩くドラムを設定（7~10バイト目）

ここでは、フィルインでどういった楽器を鳴らすかを決定します。
その表は以下の通りです。
基本的に4ビットで決定していることが分かると思います。
ただし、*はワイルドカードだと思ってください。

1/16の確率で何も鳴らない（休符になる）ということです。
そして、タイミングは以下の通りです。

7バイト目

8バイト目

9バイト目

10バイト目

メロディー・コード作り(11~50バイト)

めちゃくちゃ長いように見えますが、実際はそこまで大変ではありません。
というのもここはかなりズルしているからです。

内訳としては、

• 11~20が1小節目
• 21~30が2小節目
• 31~40が3小節目
• 41~50が4小節目

となっています。
ここでは、各バイトについて、10で割った余りのバイトについて、どのような役割を担っているか説明します。

10で割った余りが1のバイトについて

ここでは、メロディーのリズムを決定しています。
方法としては、323個のリズムパターンの中から、ビット列によってリズムを決定するというものです。
0~255までしか表現できないのに、323個あったって仕方ないと思われるかもしれませんが、確かにその通りです。
とはいえ、ここでどう考えても選ばれなかったリズムについては、そこまでということにしてあります。

10で割った余りが2のバイトについて

ここでは、コード（和音）を選択しています。
方法としては、7個のダイアトニック・コードから、ビット列により一つ選択するといった具合です。
ビット列は0~255まで表現できますから、7個のダイアトニック・コードから和音をランダムに選択するのは容易です。
ダイアトニック・コードとは、あるスケールにおける音のみによって構成された和音のことを言います。
C-majorにおいて、ダイアトニック・コードを五線上において表せば、以下の通りです。

一つも#や♭が付かない親切設計というわけです。
これをつなげることにより、多少の違和感はあれど、
そこまで大きな違和感にならないというのが、今回のミソです。

10で割った余りが3~9と、0のバイトについて

10で割った余りが1のバイトにおいては、メロディーのリズムを選択しました。
これは、多くとも8分音符8つからなるメロディーです。
すなわち、使われるか否かはとりあえず置いておいて、8つの音の候補さえ用意しておけば、メロディーを完成させることができるという寸法です。

メロディーの音の選び方についてですが、もちろん聞いて選ぶことはできません。
そこで、和音の構成音からメロディーの音を選択するという方法を取ります。
昔は僕もそういう作り方をしていた時代もありましたし、今も和音の音に釣られて音を決めることは多々あります。
そういうわけで、これが一番シンプルな決め方なのです。

さて、
10で割った余りが3のバイトを1つ目の八分音符の音にして、
10で割った余りが4のバイトを2つ目の八分音符の音にして……と続け、
10で割った余りが9のバイトを7つ目の八分音符の音にして、
10で割り切れるバイトを8つ目の八分音符の音にすれば、
全ての音符に音を割り当てることが出来るようになります。

リズムパターンによっては使われないバイトも出てきますが、その時はその時でしょう。

さて、各バイトについて、どのように音を決めているかは以下の通りです。

これらを8つのバイトについて行えば、音が選択できるはずです。
時々ぶつかる音もあると思いますが、それもそれで一興です。

バイト割り当てのまとめ

以上をプログラムに書き換えることが出来れば、目的としては達成です。
今回は50バイトで4小節作ることが出来る形になっています。

プログラムを作成する

さて、ここまでは楽典でしたが、ここからはプログラムパートです。
実行だけされたい方は、GitHub のリポジトリからファイルをダウンロードして実行してください。
（「プログラムを実行する」の項まで飛んでいただきますと使い方をご覧いただけます。）

データを作成する

データは以下のようなものです。
長いので途中省略しています。
フルバージョンはGitHubからご覧ください。

projectData.pyrhythm_data = [
    # 略
]

note_list = [
    'C',
    'C#',
    'D',
    'Eb',
    'E',
    'F',
    'F#',
    'G',
    'Ab',
    'A',
    'Bb',
    'B'
]

scale_list = [
    0,
    2,
    4,
    5,
    7,
    9,
    11
]

chord_list = [
    ['C4', 'E4', 'G4'],
    ['D4', 'F4', 'A4'],
    ['E4', 'G4', 'B4'],
    ['F4', 'A4', 'C4'],
    ['G4', 'B4', 'D5'],
    ['A4', 'C5', 'E5'],
    ['B4', 'D5', 'F5'],
]

hihat_list = [
    [0, 0, 0, 0],
    [1, 0, 0, 0],
    [0, 0, 1, 0],
    [1, 0, 1, 0],
    [0, 0, 1, 1],
    [1, 1, 1, 0],
    [1, 1, 0, 1],
    [1, 0, 1, 1],
    [0, 1, 1, 1],
    [1, 1, 1, 1],
    [2, 0, 0, 0],
    [0, 0, 2, 0],
    [1, 0, 2, 0],
    [0, 1, 2, 0],
    [1, 1, 2, 0],
    [1, 1, 2, 2],
]

これを、この後作成するプログラムと同じディレクトリに保存してください。

プログラムに必要なライブラリを用意する

今回は、midiファイルを書き出す必要がありますので、そのためのライブラリを手に入れることにします。
名前は、pretty_midiです。
必要に応じて仮想環境を作成し、その中で

pip install pretty_midi

などでインストールできますので、コマンドプロンプトやターミナルなどから実行してください。
こちらのライブラリはかなり優れもので、分かりやすく書かれています。
General Midiの規格をある程度知っていれば、様々なmidiファイルを作ることができると思うのでオススメです。

プログラムの定義部を書き出す

先ほどprojectData.pyを保存したディレクトリに、filetomidi.pyというファイルを作成してください。
ここに作曲のためのプログラムを書いていきます。

filetomidi.pyimport os
import math

import pretty_midi as pm

import projectData as pd

# 変更すべき場所
bpm = 120
chord_vel = 80
drum_vel = 80
melody_vel = 100
song_path = "fileToMidi_py.mid"
file_path = "filetomidi.py"
log_path = "log.txt"

# 曲の小節の一単位。基本的にこの小節ごとにドラムのリズム等が変化する。
bar_unit = 4

# barUnit小節作るのに必要なバイト数。必要に応じて変更する必要がある。
bar4_data = 50

bar_time = 240 / bpm
beat_time = bar_time / 4
st_time = bar_time / 16

# グローバル変数
buf = []

一番上の変更すべき場所は、このプログラムを使ううえで変更することがほぼ必須のものです。
これらの説明は以下の通りです。

プログラムを実行する

さて、あとはプログラムを実行するだけです。
一つ上で若干実行方法をお伝えしましたが、ここでもう一回説明します。

1. ファイルの準備

• filetomidi.py
• projectData.py
• midiファイルに変換したいファイル

これら三つのファイルを同じディレクトリに入れます。

2. プログラムを変更する

プログラム「filetomidi.py」を若干変更します。

分からなければ、song_pathとfile_pathだけ変更しましょう。

filetomidi.pyimport os
import math

import pretty_midi as pm

import projectData as pd

# 変更すべき場所
bpm = 120
chord_vel = 80
drum_vel = 80
melody_vel = 100
song_path = "fileToMidi_py.mid"
file_path = "filetomidi.py"
log_path = "log.txt"

この上のsong_pathを、変換後のmidiファイルのファイル名、
file_pathを、midiファイルに変換するファイルのファイル名に変更してください。

3. 実行

あとはfiletomidi.pyを実行するだけです。
しばらく待てば、同じディレクトリに、指定した名前でmidiファイルが生成されるはずです。

4. 聞いてみる

せっかくなので聞いてみましょう。

注意点

一つだけお知らせしておきます。

大きめのファイルを変換すると、それだけでかなり時間が掛かります。
この「時間が掛かる」というのは、生成する時間も聞く時間もです。
生成する時間については（僕個人としては）待てるレベルですが、
再生時間は僕は待てません。

たとえば先ほど、50バイトで4小節作れると言いました。
bpmを120のままにしていれば、50バイトで8秒間の曲を作ります。
さて、100kBのファイルを入れると、曲はどれくらいの時間になるかというと、
16384秒の曲が爆誕します。これは4時間超の曲となります。
とてもではないですが聞いてられないと思います。
逆算しましょう。3分間の、カップラーメンが作れる時間であれば、
これはおよそ1kBほどのファイルが望ましいという結果になります。

試しに1kBのファイルで作ってみましたが、2分40秒でした。
このくらいが多分ちょうどいいと思います。

本来は4小節や8小節作るのにもっとビット列を使えばいいのですが、
これ以上どうやって組み合わせようかと迷ったので、
ここまでにしてあります。
もし何かほかに「こうしてほしい」などありましたら、
お知らせいただけるとやってみるかもしれません。

いろいろ作ってみる

さて、ここまでくると、持っているファイルでいろいろ試すのもありですが、
ランダムなビット列についてもやってみたいと思った方もいらっしゃるかもしれません。

そこで僕は、同様にPythonで、指定されたファイルサイズでランダムにビットを埋めるプログラムを作成しました。
以下の通りです。GitHub にも同じファイルをアップロードしています。
もしよろしければご利用ください。

filemaker.pyimport os
import math
import random

# input file name
file_path = "sample_1k"
# input file size(bytes)
file_size = 1024

with open(os.path.dirname(__file__) + "/" + file_path, "wb") as f:
    number_list = [math.floor(random.random() * 256) for _ in range(file_size)]
    f.write(bytes(number_list))

今回製作されたmidiファイルについて

今回このfiletomidi.pyで作成されたmidiファイルにつきましては、koukawa_ppは権利を主張いたしません。
ただし、この楽曲はfiletomidi.pyによって作成されたということを明記いただけますとありがたいです。

また、元のプログラムはMITライセンスで提供しておりますので、これをさらに発展させたプログラム等も大歓迎です。

おわりに

今回の内容は確かに難しいとは思いましたが、一度アイデアが出てしまえばどうにかなったので、取り組み始めのころからすれば、割合うまく事が運んだのではないかと思っています。

何かこのプログラムにおいて、「こういったものを追加してみるといいのでは」といったものがあれば、ぜひ追加してみてください。GitHubでのフォークなども大歓迎です。
最後までお読みいただき、ありがとうございました。

参考文献

https://github.com/craffel/pretty-midi
↑こちらはpretty_midiのGitHubです。

https://craffel.github.io/pretty-midi/
↑関数の説明がかなり丁寧になされています。

https://qiita.com/marshi/items/18bf9199b1b164ec1856
↑みんな大好きQiitaです。

はじめに

こんにちは。koukawa_pp です。
当サークルはデジタル創作同好会ということで、デジタルに関するあらゆる創作を包含する存在を目指しており、サークル内では「機械学習講習会」というものがかなり前に開催されていたようです。
ここからも分かるように、機械学習は今や「誰もが一度はやってみたいもの」となりました。
しかし生成AIがかなり広まった今となっても、機械学習というものそれ自体はかなり難しそう、という印象はまだぬぐえないですし、そのためにがっつりコーディングする必要があるのではないかと思われる方は多いと思います。
しかし例えばPythonではたくさんのライブラリが登場しており、かなりコーディング量を減らして機械学習を実現できるようになったのはもちろん、先述のとおり生成AIを使えば基本的な機械学習コードはいとも簡単に作ることができるようになりました。
その流れもあり、「機械学習と言えばPython」というのは、もはや常套句のように思えます。

ただここではあえて、C#を使って機械学習をしてみたいという方向を取ります。
「C#じゃめちゃくちゃコード書かないといけないんじゃないか」と思われるかもしれません。
ところがどっこい、C#のNuGetパッケージでも、機械学習を行えるものがオープンソースでMicrosoftから出されています。
その名前は、「ML.NET」というものです。
僕もいまいちよく分かっていないので勉強中ですが、とりあえずこの「ML.NET」というものを用いれば、様々なものの機械学習を行うことができるという触れ込みです。
そこで今回は、「夏目漱石」を機械学習してみようということです。

やることはざっくり言えば、

ある文が渡されたとき、それはどの作品に含まれる文か？

を当てるといったものです。
先行研究を探せば、多分たくさん出てくると思いますし、例えば「○○が書いたような文章」を生成するといったテーマで研究されている方もたくさんいらっしゃると思いますが、今回はごく簡単なものということでやってみます。

そういえば機械生成ではなく作家さんが書かれた文章ですが、「もし文豪たちが カップ焼きそばの作り方を書いたら」という本がかなり面白かったのを記憶しています。また読みたいなと思っています。

また、今回は以下の作品を用います。

• こころ
• 吾輩は猫である
• 三四郎
• 私の個人主義
• 草枕
• 坊っちゃん

選択した作品は適当です。
これらの文章を二つに分け、一方は学習、もう一方はテストに使います。
なお、今回使用したファイルはこちらのGitHubレポジトリで公開しています。
プログラムについてはMITライセンスで再利用いただけます。作品データについては青空文庫さまの利用規約に則ってご利用ください。

環境

• Windows 10 Home 64bit
• Visual Studio 2022 Community
• Visual Studio Code
• (メモ帳)

データを準備する

まず、今回用いるデータの準備を行います。
この文章に関しては、青空文庫さまのデータを使います。
ファイルの取り扱い方についてはこちらを参考にしています。
夏目漱石作品はすでに著作権が切れていますので、こちらで機械学習しやすいようにデータを編集できます。

ファイルをダウンロードする

こちらに夏目漱石作品の一覧があります。
これらの中から、

• こころ
• 吾輩は猫である
• 三四郎
• 私の個人主義
• 草枕
• 坊っちゃん

についてページを開き、それぞれzipファイルをダウンロードします。
もちろん、ダウンロードしたファイルは解凍してください。

ちなみに、ダウンロードしたファイルは以上のような感じです。

データを編集する

もっと簡単な編集方法があるかもしれませんが、僕は以下の方法で編集しました。
以下では「こころ」について示しますが、他のファイルも同様の編集を行ってください。

1. kokoro.txtをコピーし、kokoro_edit.txtを作成する

原本は残しておくつもりでいるので、一旦「kokoro.txt」を複製し、同じフォルダにコピーしてください。
また、複製したファイルの名称を「kokoro_edit.txt」に編集します。

2. kokoro_edit.txtをVSCodeで開く

詳細な文字の置換は、VSCodeでやるのが便利だと思っています。
開くと、以下のようになると思います。

3. ルビを削除する

今回の学習においては、ルビは削除します。
ここで、VSCodeの強力な「置換」機能を使います。

「正規表現を使用する」をチェックして、以下のように「検索」ボックスに入力してください。

この正規表現は、

を探しています。

本来なら《.*》と入力したいところですが、
これだと

と選択されてしまうため、不都合です。
ここで、》を除外することにより、

と選択されるようになります。

こう入力したら、「置換」のところを空欄にして、「すべて置換」を選択してください。

上部「テキスト中に現れる記号について」のルビのところも消えていますが、
ここはあとで削除するので特に不都合はありません。

4. 「ルビの付く文字列の始まりを特定する記号」を削除する

こちらはそこまで難しくないです。
|を検索ボックスに入力し、「置換」のところを空欄にしてから、
「すべて置換」を押してください。

5. 「入力者注」を削除する

ここが実は一番大変です。
まず、以下のようなものを削除します。

これだけ見ると分かりづらいですが、
この［＃５字下げ］一［＃「一」は中見出し］の上下には
一行ずつ空行が存在している状態です。
これらの空行も削除します。

まず、検索ボックスの中に\n［.*］\n\nと入力してください。
半角と全角を間違えないでください。
そうすると、以下のようにハイライトされるはずです。

これでいったん「すべて置換」してください。

次に、検索ボックスの中に［[^］]*］と入力してください。
ブラケットは、左から全角、半角、全角、半角、全角です。

よさげですね。
これもまた「置換」のところを空欄にしてから、「すべて置換」を押してください。

6. 最初と最後を削除する

最初と最後の脚注を削除してください。
ここまで来たら、「kokoro_edit.txt」を保存してください。
また、VSCodeを閉じて大丈夫です。

7. メモ帳で「kokoro_edit.txt」を開き、文字コードを変更して保存する

そもそも初めからだと思うのですが、ファイルをダウンロードした時点ですでに文字コードが「ANSI」になっています。
これはこの後プログラムで扱うときに非常に面倒なので、メモ帳で「kokoro_edit.txt」を開いたのち、「名前を付けて保存」で文字コードを「UTF-8(BOM付き)」を選択して保存してください。
名称は僕は「kokoro_utf.txt」としました。

8. （私の個人主義のみ）一部削除

も削除してください。

データを（本格的に）作成する

ここまではデータの準備です。なので、ここからはデータを作成します。

やり方としては単純です。

1. 各テキストのファイルを読み込む
2. およそ10個に一つ程度の割合で、文章をテスト用データに登録し、それ以外は訓練用データに登録する
3. 最後にそれらをファイルとして書き出す

これを実行してくれるコンソールプログラムを作成しましょう。
ただ繰り返しになりますが、このコードは2022年7月時点に書いたコードになります。
現在のコンソールアプリでは以下のような namespace や class, はては Main 関数の記述すらなく、トップレベルのステートメントが使用されるようになっています。
この形式のコードを記述する際には、「最上位レベルのステートメントを使用しない」チェックボックスをOnにすることによって行えます。
プロジェクト名は「MakeSosekiDatas」としました。

Program.csに、コードを以下の通り入力しました。

Program.csnamespace MakeSosekiData
{
    internal class Program
    {
        static int seed = Environment.TickCount;

        static readonly string _kokoroPath = Path.Combine(Environment.CurrentDirectory, "Data", "kokoro_utf.txt");
        static readonly string _wagahaiPath = Path.Combine(Environment.CurrentDirectory, "Data", "wagahaiwa_nekodearu_utf.txt");
        static readonly string _sanshiroPath = Path.Combine(Environment.CurrentDirectory, "Data", "sanshiro_utf.txt");
        static readonly string _kozinPath = Path.Combine(Environment.CurrentDirectory, "Data", "watashino_kojinshugi_utf.txt");
        static readonly string _kusaPath = Path.Combine(Environment.CurrentDirectory, "Data", "kusamakura_utf.txt");
        static readonly string _bochanPath = Path.Combine(Environment.CurrentDirectory, "Data", "bocchan_utf.txt");

        static readonly string _trainDataPath = Path.Combine(Environment.CurrentDirectory, "Data", "traindata.csv");
        static readonly string _testDataPath = Path.Combine(Environment.CurrentDirectory, "Data", "testdata.csv");

        static readonly List<(string, int)> trainDatas = new();
        static readonly List<(string, int)> testDatas = new();

        static void Main(string[] args)
        {
            //こころのデータを作る
            using FileStream kokoroStream = new(_kokoroPath, FileMode.Open, FileAccess.Read, FileShare.Read);
            using StreamReader kokoroReader = new(kokoroStream);
            ReaderToData(kokoroReader, 0);

            //吾輩は猫であるのデータを作る
            using FileStream wagahaiStream = new(_wagahaiPath, FileMode.Open, FileAccess.Read, FileShare.Read);
            using StreamReader wagahaiReader = new(wagahaiStream);
            ReaderToData(wagahaiReader, 1);

            //三四郎のデータを作る
            using FileStream sanshiroStream = new(_sanshiroPath, FileMode.Open, FileAccess.Read, FileShare.Read);
            using StreamReader sanshiroReader = new(sanshiroStream);
            ReaderToData(sanshiroReader, 2);

            //私の個人主義のデータを作る
            using FileStream kozinStream = new(_kozinPath, FileMode.Open, FileAccess.Read, FileShare.Read);
            using StreamReader kozinReader = new(kozinStream);
            ReaderToData(kozinReader, 3);

            //草枕のデータを作る
            using FileStream kusaStream = new(_kusaPath, FileMode.Open, FileAccess.Read, FileShare.Read);
            using StreamReader kusaReader = new(kusaStream);
            ReaderToData(kusaReader, 4);

            //坊っちゃんのデータを作る
            using FileStream bochanStream = new(_bochanPath, FileMode.Open, FileAccess.Read, FileShare.Read);
            using StreamReader bochanReader = new(bochanStream);
            ReaderToData(bochanReader, 5);

            //trainDatasを保存する。
            using FileStream trainStream = new(_trainDataPath, FileMode.Create, FileAccess.Write, FileShare.Read);
            using StreamWriter trainWriter = new(trainStream, System.Text.Encoding.GetEncoding("utf-8"));
            foreach (var item in trainDatas)
            {
                trainWriter.WriteLine(item.Item1 + "," + item.Item2.ToString());
            }

            //testDatasを保存する。
            using FileStream testStream = new(_testDataPath, FileMode.Create, FileAccess.Write, FileShare.Read);
            using StreamWriter testWriter = new(testStream, System.Text.Encoding.GetEncoding("utf-8"));
            foreach (var item in testDatas)
            {
                testWriter.WriteLine(item.Item1 + "," + item.Item2.ToString());
            }
        }

        static void ReaderToData(StreamReader streamReader, int sakuhinIndex)
        {
            while (!streamReader.EndOfStream)
            {
                string? str = streamReader.ReadLine();

                if (str == null)
                    break;

                if (str.Contains('。'))
                {
                    string[] vs = str.Split('。');
                    for (int i = 0; i < vs.Length; i++)
                    {
                        if (vs[i] != "")
                            RegisterData(vs[i] + "。", sakuhinIndex);
                    }
                }
                else
                    RegisterData(str, sakuhinIndex);
            }
        }

        static void RegisterData(string text, int sakuhinIndex)
        {
            if (text == "") return;

            Random random = new(seed);
            seed = random.Next();

            if (text[..1] == "　")
            {
                if (random.Next(10) == 0)
                    testDatas.Add((text[1..], sakuhinIndex));
                else
                    trainDatas.Add((text[1..], sakuhinIndex));
            }
            else
            {
                if (random.Next(10) == 0)
                    testDatas.Add((text, sakuhinIndex));
                else
                    trainDatas.Add((text, sakuhinIndex));
            }
        }
    }
}

コードはかなりごついですが、ほとんど繰り返しなのでやっていることは単純です。

Main()では最初の方で6つのテキストデータを読み込み、ReaderToData(StreamReader, int)でデータを作成しています。
その後、StreamWriterを用いて指定されたパスにデータを保存しています。

ReaderToData(StreamReader, int)では、テキストファイルの終わりまで文字列の読み込みを繰り返し、。で文章を分割して一つの文にし、それに作品のインデックスを付けることによりラベリングしています。
実際の登録はRegisterData(string, int)で行っています。

RegisterData(string, int)は、

• 10%の確率で、string + "," + intをテスト用データに追加し、
• 90%の確率で、string + "," + intを訓練用データに追加しています。

ちなみに段落明けのため、一字下げが行われているところでは、一字下げを戻すようにしています。

さて、このまま実行するとFileNotFoundExceptionを吐き出して止まるので、ファイルをきちんと登録していきましょう。

上のように行います。

1. まず、「MakeSosekiDatas」を右クリックし、「追加」→「新しいフォルダ」を行い、「Data」フォルダを追加します。
2. その中に、「○○_utf.txt」をコピーします。
3. その後、そのファイルを選択し、「プロパティ」から「出力ディレクトリにコピー」を、「新しい場合はコピーする」に変更します。

その後、各作品について、2. および 3. を繰り返します。
それを行うことにより、データの追加は完了です。

これで準備完了です。プログラムを実行してください。
こうすると、実行ファイルと同じフォルダ（最新版なら一般に MakeSosekiDatas/bin/Debug/net10.0 です）に「Data」フォルダが追加され、その中に「traindata.csv」と「testdata.csv」が作成されます。
これが今回使うデータです。

なお、データの選択はプログラムの乱数によって適当に行っているので、人によって実行結果は異なります。

機械学習を行う

いよいよ本題です。機械学習していきましょう。
とはいえ僕もきちんと分かっているわけではないので、予防線としてML.NETのチュートリアルのページを貼っておきます。
今回は「どの作品か」を当てるものなので、この中でも「多クラス分類」が一番望ましいと考えられます。
したがってここでは、「多クラス分類」のチュートリアルに則って、プログラムを作成していきましょう。
ほとんどチュートリアルのコードそのままなので、分かりづらいところはドキュメントページをご覧ください。

プロジェクトの準備を行う

まず、プロジェクトの準備を行います。
まず、NuGetパッケージから、「Microsoft.ML」をインストールしてください。
これがないと機械学習できません。

ここで一つ重要なことです。
2026年2月現在においては、.NET 8 と .NET 10 がありますが、.NET 8 を選択してください。
なぜか .NET 10 だと同じコードベースでも性能が出ません。
原因が不明なので、もし分かる方いらっしゃったら GitHub の issue に投げていただけると助かります。

次に、データを登録します。
先ほどと同様に、以下のようにデータを登録します。

上記ではコードをすでに入力していますが、無視してください。

1. 「MLSoseki」を右クリックし、「追加」→「新しいフォルダ」で、「Data」フォルダを作成します。
2. testdata.csvを追加します。
3. testdata.csvのプロパティにおいて、「出力ディレクトリにコピー」を、「新しい場合はコピーする」に変更します。
4. traindata.csvを追加します。
5. traindata.csvのプロパティにおいて、「出力ディレクトリにコピー」を、「新しい場合はコピーする」に変更します。

なお、もちろん2~3と4~5は逆でも問題ありません。

必要なクラスを作成する

次にコードを入力します。
まず、必要なクラスを作成します。
先ほどと同様に「MLSoseki」を右クリックし、「追加」→「クラス」として、ファイル名を「SosekiSentence.cs」に変更してください。
コードは以下のようにしてください。

SosekiSentence.csusing Microsoft.ML.Data;

namespace MLSoseki
{
    public class SosekiSentence
    {
        [LoadColumn(0)]
        public string Sentence { get; set; }

        [LoadColumn(1)]
        public float StoryID { get; set; }
    }

    public class SosekiPrediction
    {
        [ColumnName("PredictedLabel")]
        public float StoryID;
    }
}

Microsoft.ML.Dataを先頭に追加するのを忘れないでください。
LoadColumn()属性を付与することにより、読み込んだデータをここに登録することが出来るようです。
また、ColumnName()属性を付与し、その引数に"PredictedLabel"を与えることにより、推測を行う対象を明示することが出来るそうです。
これらについては後で使います。

なお、StoryIDのところにおいて、作品を表すインデックスを登録し、それを推測するような機械学習を行うこととします。

必要なクラス変数を定義する

では次に、Program.cs に戻り、必要な変数を定義します。
クラスのトップレベルに以下の三つの変数を定義してください。

Program.csstatic readonly string _trainDataPath = Path.Combine(Environment.CurrentDirectory, "Data", "traindata.csv");
static readonly string _testDataPath = Path.Combine(Environment.CurrentDirectory, "Data", "testdata.csv");
static readonly string _modelPath = Path.Combine(Environment.CurrentDirectory, "Data", "model.zip");

これで、訓練データ、テストデータとモデルのパスを定義できました。

ProcessData(MLContext) を作成する

次に、ProcessData(MLContext) という静的関数を作成します。
Program.csに戻り、以下のような関数を追加します。

Program.csusing Microsoft.ML;

namespace MLSoseki
{
    internal class Program
    {
        static IEstimator<ITransformer> ProcessData(MLContext mlContext)
        {
            var pipeline = mlContext.Transforms.Conversion.MapValueToKey(inputColumnName: "StoryID", outputColumnName: "Label")
                .Append(mlContext.Transforms.Text.FeaturizeText(inputColumnName: "Sentence", outputColumnName: "SentenceFeaturized"))
                .Append(mlContext.Transforms.Concatenate("Features", "SentenceFeaturized"));
            return pipeline;
        }
    }
}

一行目では、inputColumnNameのところに、予測したい値の変数名を指定し、outputColumnNameのところには"Label"を指定します。

二行目Append...のところについては、様々なオプションを付与しています。
例えばML.NETにおける機械学習においては、文字列型のデータを読み込むことは不可能とのことなので、文字列型のデータであるSentenceを数値データに変換するため、mlContext.Transforms.Text.FeaturizeText()を用いて変換しています。
これにより、Sentenceが、数値データであるSentenceFeaturizedに変換されます。

三行目Append...のところでは、
どの要素を機械学習の要素として指定するかといったところを指定します。
今回の場合、例えば読み込んだデータの中に「筆者」データがあった場合、今回は全て筆者は夏目漱石なので、機械学習の結果には影響はありませんね。
筆者だけならまだよいですが、それ以外に推測するもの（今回はどの作品であるか）と相関関係のないもの（例えばこの文の文字数など）を指定してしまった場合、モデルが関係のない値ももとに学習・推論してしまうことになる可能性があり、性能を残念なものにしてしまう可能性も考えられ面倒です。
そのため、ここでは機械学習に用いるデータ系列を指定しているわけです。
なお、第一引数には"Features"を指定することがほぼ暗黙的に決定しているようです。
第二引数以降に、必要なデータ系列を必要なだけ指定します。
ここでは数値データ"SentenceFeaturized"のみを指定します。
必要に応じて任意個指定することが出来ます。

これにより、IEstimator<ITransformer>型の変数pipelineが代入されます。

BuildAndTrainModel(MLContext, IDataView, IEstimator<ITransformer>)を作成する

次は、いよいよ与えられたデータを用いて学習する部分です。

Program.csstatic ITransformer BuildAndTrainModel(MLContext mlContext, IDataView trainDataView, IEstimator<ITransformer> pipeline)
{
    var trainingPipeline = pipeline.Append(mlContext.MulticlassClassification.Trainers.SdcaMaximumEntropy("Label", "Features"))
        .Append(mlContext.Transforms.Conversion.MapKeyToValue("PredictedLabel"));
    ITransformer trainedModel = trainingPipeline.Fit(trainDataView);
    return trainedModel;
}

基本的に先ほどのチュートリアル記事の内容に則っています。

Evaluate(MLContext, DataViewSchema, ITransformer) を作成する

ここではモデルの評価を行います。
また最後の行でモデルを保存しています。

Program.csstatic void Evaluate(MLContext mlContext, DataViewSchema trainingDataViewSchema, ITransformer trainedModel)
{
    IDataView testDataView = mlContext.Data.LoadFromTextFile<SosekiSentence>(_testDataPath, hasHeader: false, separatorChar: ',');
    var testMetrics = mlContext.MulticlassClassification.Evaluate(trainedModel.Transform(testDataView));
    Console.WriteLine($"*************************************************************************************************************");
    Console.WriteLine($"*       Metrics for Multi-class Classification model - Test Data     ");
    Console.WriteLine($"*------------------------------------------------------------------------------------------------------------");
    Console.WriteLine($"*       MicroAccuracy:    {testMetrics.MicroAccuracy:0.###}");
    Console.WriteLine($"*       MacroAccuracy:    {testMetrics.MacroAccuracy:0.###}");
    Console.WriteLine($"*       LogLoss:          {testMetrics.LogLoss:#.###}");
    Console.WriteLine($"*       LogLossReduction: {testMetrics.LogLossReduction:#.###}");
    Console.WriteLine($"*************************************************************************************************************");

    mlContext.Model.Save(trainedModel, trainingDataViewSchema, _modelPath);
}

Main() を作成する

いよいよ最後に Main() 関数を作成します。

Program.csstatic void Main(string[] args)
{
    MLContext mlContext = new(seed: 0);
    IDataView dataView = mlContext.Data.LoadFromTextFile<SosekiSentence>(_trainDataPath, hasHeader: false, separatorChar: ',');
    var pipeline = ProcessData(mlContext);
    ITransformer trainedModel = BuildAndTrainModel(mlContext, dataView, pipeline);
    Evaluate(mlContext, dataView.Schema, trainedModel);
}

とはいってもこれまで書いてきた処理を最初から呼び出すだけです。
ちなみに

Program.csIDataView dataView = mlContext.Data.LoadFromTextFile<SosekiSentence>(_trainDataPath, hasHeader: false, separatorChar: ',');

はデータを読み込んでいるだけです。
Microsoft.MLに存在するIDataViewというインターフェースが、ML.NETにおけるデータの取り扱いで非常に便利なようです。
工夫すれば、ここに全てのデータを読み込ませて、訓練用とテスト用に分けることもできるようなのですが、僕はちょっと分かっていないのでドキュメントに任せることにします。
引数もそこまで面倒ではないですよね。
しかし引数の設定忘れは面倒なのでお気を付けください。
（特にseparatorCharを指定するのを忘れないでください）

実行する

この状態で、プログラムを実行してみてください。

これが結果ですが、実は精度はあまり悪くありません。

こちらがチュートリアルをそのまま実行した結果なのですが、

こうやって比較してみると、割と悪くない結果を出してくれているように思うわけです。

実際に予測してもらう

ではここで、試しにいくつかの例について、実際にどの作品なのかを予測してもらいましょう。

僕が実際に生成したデータに基づくことにしますが、僕が実際に生成したtestdata.csvの中から、いくつかピックアップして実際にやってみます。

各々の作品から4つずつ文をピックアップしています。

こころ

• 先生はそれでなくても、冷たい眼で研究されるのを絶えず恐れていたのである。
• その感じが私をＫの墓へ毎月行かせます。
• 私は彼の生前に雑司ヶ谷近辺をよくいっしょに散歩した事があります。
• 彼の血潮の大部分は、幸い彼の蒲団に吸収されてしまったので、畳はそれほど汚れないで済みましたから、後始末はまだ楽でした。

吾輩は猫である

• 妻君が袋戸の奥からタカジヤスターゼを出して卓の上に置くと、主人は「それは利かないから飲まん」という。
• Ａ君は是非固形体を食うなという。
• 下女は国事の秘密でも語る時のように大得意である。
• 神楽坂の方から汽車がヒューと鳴って土手下を通り過ぎる。

三四郎

• 三四郎は富士山の事をまるで忘れていた。
• ところが広田さんはそれでやめてしまった。
• 麹町からあれを千駄木まで引いてくるのに、手間が五円ほどかかったなどと言う。
• 図書館へもはいったがやっぱり見当らなかった。

私の個人主義

• 私は今日初めてこの学習院というものの中に這入りました。
• 私は高等学校へ周旋してくれた先輩に半分承諾を与えながら、高等師範の方へも好い加減な挨拶をしてしまったので、事が変な具合にもつれてしまいました。
• その苦痛は無論鈍痛ではありましたが、年々歳々感ずる痛には相違なかったのであります。
• 世界の大勢に幾分か関係していないとも限らない。

草枕

• 越す事のならぬ世が住みにくければ、住みにくい所をどれほどか、寛容て、束の間の命を、束の間でも住みよくせねばならぬ。
• 雲雀の声を聞いたときに魂のありかが判然する。
• はっと思う間に、小女郎が、またはたと襖を立て切った。
• 「和尚さん、あなたには、御目に懸けた事があったかな」

坊っちゃん

• すると清は澄したものでお兄様はお父様が買ってお上げなさるから構いませんと云う。
• 卒業してから八日目に校長が呼びに来たから、何か用だろうと思って、出掛けて行ったら、四国辺のある中学校で数学の教師が入る。
• これも親譲りの無鉄砲が祟ったのである。
• おれは江戸っ子で華奢に小作りに出来ているから、どうも高い所へ上がっても押しが利かない。

さて、適当に選んだと見せかけて、かなりいろいろ考えました。
いくつかの基準を設けています。

• 登場人物の名称を入れてみる
• 地名を入れてみる
• あらすじによって推測できそうなものを入れる
• 逆に全く関係のなさそうなものも入れる

まず最初の「登場人物」は、かなり重要な要素ですよね。
ある登場人物がほかの作品に出てくるといえば、ダイパに出ていたポケモンがベストウィッシュの後半でも出てくるとかない限りはほぼないはずです。

次に地名ですが、夏目漱石は物語の舞台を、詳細な地名も入れながら書いている気がします。
例えば愛媛県では「坊っちゃん列車」といったものなどがあるくらいです。

次にあらすじに関係するもの、または全く関係しないものですが、僕はこの中でも「こころ」と「私の個人主義」は読んだことがあるような気がしており、「こころ」はそういう意味ではかなりきちんと選んでいます。
「私の個人主義」を選んだ理由ですが、これは他の作品と違い、どちらかと言えば評論文に近いものがあります。
そういった部分も推測できるかが見ものです。

さて、お待たせしました。コードを追加しましょう。

Program.csstatic void PredictWork(MLContext mlContext, ITransformer trainedModel)
{
    SosekiSentence ss00 = new() { Sentence = "先生はそれでなくても、冷たい眼で研究されるのを絶えず恐れていたのである。" };
    SosekiSentence ss01 = new() { Sentence = "その感じが私をＫの墓へ毎月行かせます。" };
    SosekiSentence ss02 = new() { Sentence = "私は彼の生前に雑司ヶ谷近辺をよくいっしょに散歩した事があります。" };
    SosekiSentence ss03 = new() { Sentence = "彼の血潮の大部分は、幸い彼の蒲団に吸収されてしまったので、畳はそれほど汚れないで済みましたから、後始末はまだ楽でした。" };

    SosekiSentence ss10 = new() { Sentence = "妻君が袋戸の奥からタカジヤスターゼを出して卓の上に置くと、主人は「それは利かないから飲まん」という。" };
    SosekiSentence ss11 = new() { Sentence = "Ａ君は是非固形体を食うなという。" };
    SosekiSentence ss12 = new() { Sentence = "下女は国事の秘密でも語る時のように大得意である。" };
    SosekiSentence ss13 = new() { Sentence = "神楽坂の方から汽車がヒューと鳴って土手下を通り過ぎる。" };

    SosekiSentence ss20 = new() { Sentence = "三四郎は富士山の事をまるで忘れていた。" };
    SosekiSentence ss21 = new() { Sentence = "ところが広田さんはそれでやめてしまった。" };
    SosekiSentence ss22 = new() { Sentence = "麹町からあれを千駄木まで引いてくるのに、手間が五円ほどかかったなどと言う。" };
    SosekiSentence ss23 = new() { Sentence = "図書館へもはいったがやっぱり見当らなかった。" };

    SosekiSentence ss30 = new() { Sentence = "私は今日初めてこの学習院というものの中に這入りました。" };
    SosekiSentence ss31 = new() { Sentence = "私は高等学校へ周旋してくれた先輩に半分承諾を与えながら、高等師範の方へも好い加減な挨拶をしてしまったので、事が変な具合にもつれてしまいました。" };
    SosekiSentence ss32 = new() { Sentence = "その苦痛は無論鈍痛ではありましたが、年々歳々感ずる痛には相違なかったのであります。" };
    SosekiSentence ss33 = new() { Sentence = "世界の大勢に幾分か関係していないとも限らない。" };

    SosekiSentence ss40 = new() { Sentence = "越す事のならぬ世が住みにくければ、住みにくい所をどれほどか、寛容て、束の間の命を、束の間でも住みよくせねばならぬ。" };
    SosekiSentence ss41 = new() { Sentence = "雲雀の声を聞いたときに魂のありかが判然する。" };
    SosekiSentence ss42 = new() { Sentence = "はっと思う間に、小女郎が、またはたと襖を立て切った。" };
    SosekiSentence ss43 = new() { Sentence = "「和尚さん、あなたには、御目に懸けた事があったかな」" };

    SosekiSentence ss50 = new() { Sentence = "すると清は澄したものでお兄様はお父様が買ってお上げなさるから構いませんと云う。" };
    SosekiSentence ss51 = new() { Sentence = "卒業してから八日目に校長が呼びに来たから、何か用だろうと思って、出掛けて行ったら、四国辺のある中学校で数学の教師が入る。" };
    SosekiSentence ss52 = new() { Sentence = "これも親譲りの無鉄砲が祟ったのである。" };
    SosekiSentence ss53 = new() { Sentence = "おれは江戸っ子で華奢に小作りに出来ているから、どうも高い所へ上がっても押しが利かない。" };

    PredictionEngine<SosekiSentence, SosekiPrediction> predictionEngine = mlContext.Model.CreatePredictionEngine<SosekiSentence, SosekiPrediction>(trainedModel);
    SosekiPrediction sp00 = predictionEngine.Predict(ss00);
    SosekiPrediction sp01 = predictionEngine.Predict(ss01);
    SosekiPrediction sp02 = predictionEngine.Predict(ss02);
    SosekiPrediction sp03 = predictionEngine.Predict(ss03);

    SosekiPrediction sp10 = predictionEngine.Predict(ss10);
    SosekiPrediction sp11 = predictionEngine.Predict(ss11);
    SosekiPrediction sp12 = predictionEngine.Predict(ss12);
    SosekiPrediction sp13 = predictionEngine.Predict(ss13);
    
    SosekiPrediction sp20 = predictionEngine.Predict(ss20);
    SosekiPrediction sp21 = predictionEngine.Predict(ss21);
    SosekiPrediction sp22 = predictionEngine.Predict(ss22);
    SosekiPrediction sp23 = predictionEngine.Predict(ss23);
    
    SosekiPrediction sp30 = predictionEngine.Predict(ss30);
    SosekiPrediction sp31 = predictionEngine.Predict(ss31);
    SosekiPrediction sp32 = predictionEngine.Predict(ss32);
    SosekiPrediction sp33 = predictionEngine.Predict(ss33);
    
    SosekiPrediction sp40 = predictionEngine.Predict(ss40);
    SosekiPrediction sp41 = predictionEngine.Predict(ss41);
    SosekiPrediction sp42 = predictionEngine.Predict(ss42);
    SosekiPrediction sp43 = predictionEngine.Predict(ss43);
    
    SosekiPrediction sp50 = predictionEngine.Predict(ss50);
    SosekiPrediction sp51 = predictionEngine.Predict(ss51);
    SosekiPrediction sp52 = predictionEngine.Predict(ss52);
    SosekiPrediction sp53 = predictionEngine.Predict(ss53);

    Console.WriteLine($"=============== Single Prediction - Sentence: {ss00.Sentence},\n Answer: {GetSentenceName(0)}, Result: {GetSentenceName(sp00.StoryID)} ===============");
    Console.WriteLine($"=============== Single Prediction - Sentence: {ss01.Sentence},\n Answer: {GetSentenceName(0)}, Result: {GetSentenceName(sp01.StoryID)} ===============");
    Console.WriteLine($"=============== Single Prediction - Sentence: {ss02.Sentence},\n Answer: {GetSentenceName(0)}, Result: {GetSentenceName(sp02.StoryID)} ===============");
    Console.WriteLine($"=============== Single Prediction - Sentence: {ss03.Sentence},\n Answer: {GetSentenceName(0)}, Result: {GetSentenceName(sp03.StoryID)} ===============");
    Console.WriteLine();
    Console.WriteLine($"=============== Single Prediction - Sentence: {ss10.Sentence},\n Answer: {GetSentenceName(1)}, Result: {GetSentenceName(sp10.StoryID)} ===============");
    Console.WriteLine($"=============== Single Prediction - Sentence: {ss11.Sentence},\n Answer: {GetSentenceName(1)}, Result: {GetSentenceName(sp11.StoryID)} ===============");
    Console.WriteLine($"=============== Single Prediction - Sentence: {ss12.Sentence},\n Answer: {GetSentenceName(1)}, Result: {GetSentenceName(sp12.StoryID)} ===============");
    Console.WriteLine($"=============== Single Prediction - Sentence: {ss13.Sentence},\n Answer: {GetSentenceName(1)}, Result: {GetSentenceName(sp13.StoryID)} ===============");
    Console.WriteLine();
    Console.WriteLine($"=============== Single Prediction - Sentence: {ss20.Sentence},\n Answer: {GetSentenceName(2)}, Result: {GetSentenceName(sp20.StoryID)} ===============");
    Console.WriteLine($"=============== Single Prediction - Sentence: {ss21.Sentence},\n Answer: {GetSentenceName(2)}, Result: {GetSentenceName(sp21.StoryID)} ===============");
    Console.WriteLine($"=============== Single Prediction - Sentence: {ss22.Sentence},\n Answer: {GetSentenceName(2)}, Result: {GetSentenceName(sp22.StoryID)} ===============");
    Console.WriteLine($"=============== Single Prediction - Sentence: {ss23.Sentence},\n Answer: {GetSentenceName(2)}, Result: {GetSentenceName(sp23.StoryID)} ===============");
    Console.WriteLine();
    Console.WriteLine($"=============== Single Prediction - Sentence: {ss30.Sentence},\n Answer: {GetSentenceName(3)}, Result: {GetSentenceName(sp30.StoryID)} ===============");
    Console.WriteLine($"=============== Single Prediction - Sentence: {ss31.Sentence},\n Answer: {GetSentenceName(3)}, Result: {GetSentenceName(sp31.StoryID)} ===============");
    Console.WriteLine($"=============== Single Prediction - Sentence: {ss32.Sentence},\n Answer: {GetSentenceName(3)}, Result: {GetSentenceName(sp32.StoryID)} ===============");
    Console.WriteLine($"=============== Single Prediction - Sentence: {ss33.Sentence},\n Answer: {GetSentenceName(3)}, Result: {GetSentenceName(sp33.StoryID)} ===============");
    Console.WriteLine();
    Console.WriteLine($"=============== Single Prediction - Sentence: {ss40.Sentence},\n Answer: {GetSentenceName(4)}, Result: {GetSentenceName(sp40.StoryID)} ===============");
    Console.WriteLine($"=============== Single Prediction - Sentence: {ss41.Sentence},\n Answer: {GetSentenceName(4)}, Result: {GetSentenceName(sp41.StoryID)} ===============");
    Console.WriteLine($"=============== Single Prediction - Sentence: {ss42.Sentence},\n Answer: {GetSentenceName(4)}, Result: {GetSentenceName(sp42.StoryID)} ===============");
    Console.WriteLine($"=============== Single Prediction - Sentence: {ss43.Sentence},\n Answer: {GetSentenceName(4)}, Result: {GetSentenceName(sp43.StoryID)} ===============");
    Console.WriteLine();
    Console.WriteLine($"=============== Single Prediction - Sentence: {ss50.Sentence},\n Answer: {GetSentenceName(5)}, Result: {GetSentenceName(sp50.StoryID)} ===============");
    Console.WriteLine($"=============== Single Prediction - Sentence: {ss51.Sentence},\n Answer: {GetSentenceName(5)}, Result: {GetSentenceName(sp51.StoryID)} ===============");
    Console.WriteLine($"=============== Single Prediction - Sentence: {ss52.Sentence},\n Answer: {GetSentenceName(5)}, Result: {GetSentenceName(sp52.StoryID)} ===============");
    Console.WriteLine($"=============== Single Prediction - Sentence: {ss53.Sentence},\n Answer: {GetSentenceName(5)}, Result: {GetSentenceName(sp53.StoryID)} ===============");
}

static string GetSentenceName(float index)
{
    return index switch
    {
        0 => "こころ",
        1 => "吾輩は猫である",
        2 => "三四郎",
        3 => "私の個人主義",
        4 => "草枕",
        5 => "坊っちゃん",
        _ => "",
    };
}

リストにしておけばよかったと後悔したのは後の祭りです。
あと皆さまにつきましても、データを自分でコードを実行して作成した場合は、訓練用データにこれらの文章が含まれている可能性があるので、あまり当てにはならないかもしれません。
必要に応じて、GitHubから僕が作成したデータをご利用ください。

そしてこう書いたら、

Program.csstatic void Main(string[] args)
{
    MLContext mlContext = new(seed: 0);
    IDataView dataView = mlContext.Data.LoadFromTextFile<SosekiSentence>(_trainDataPath, hasHeader: false, separatorChar: ',');
    var pipeline = ProcessData(mlContext);
    ITransformer trainedModel = BuildAndTrainModel(mlContext, dataView, pipeline);
    Evaluate(mlContext, dataView.Schema, trainedModel);
    PredictWork(mlContext, trainedModel);
}

のように、最後にコードを追加してください。
これで実行してみましょう。

これが結果です。
三四郎については全問正解ですね。
ただ余計に三四郎と答えている部分はあるようですが……。
また、「図書館へも……」を当てるとは思いませんでした……。

「これも親譲りの……」に関しては、一行目「親譲りの無鉄砲で……」を
学習させていたので行けるかな？と思いましたが無理でした。

「その感じが私をKの墓へ……」については、「A君」に引っ張られたのでしょうか。

意外だったのは「彼の血潮の大部分は……」を当てたところですね。
うまく推測できたのでしょうか。

おわりに

これは他の作家ならどうなんだろう？とか思いました。
実際に時間があればそちらでもやってみようと思います。

また、今度は複数の作家についてこのように学習させ、
「誰が書いた一文か」というのもしてみたいとも思っています。

最後までお読みいただき、ありがとうございました。

22B の noya2 です. ずいぶん前に抽象化された全方位木 DP のライブラリの記事を書いたのですが，今回は「木 DP の更新」を扱います.

Static Top Tree と呼ばれるデータ構造があります. 以下，STT と省略します. STT は ABC 351-G Hash on Tree において ABC の想定解法として初めて明示的に扱われました. 公式解説が丁寧に書かれており，その後も STT に関する出題や上位勢による積極的な言及もあったことから，約 2 年の月日が経ったいま，STT はだんだんと典型になっているように感じます.

つい最近行なわれた The 2026 ICPC Asia Pacific Championship において，D 問題に STT を使うだけで解ける問題が出題されました. その少し前に，ICPC 用のお手軽実装がないか，より直接的に木 DP を扱う考え方がないかを検討し，自分なりに納得のいく結果が得られていたため，本番ではすんなり通すことができました. この記事では，木 DP を変形することによって，cluster の概念を経由せずに「 ${\log }^2$ の STT」を理解することを目指します.

木の構成に自由度があり，その部分を工夫すると ${\log }^1$ になりますが，工夫せずに segment tree に丸投げすることで実装がかなり楽になっていると主張しています.

木 DP の変形

乱暴な記法や大胆な省略を行なっていますが，察してください.

根付き木上の DP を次のように定式化します.

$$dp[v]=V(v,\underset{vc\in \vec{E}}{⨁}E(vc,dp[c]))$$

• 根付き木を rooted_tree = pair<vertex, set<rooted_tree> > として構成しています.
• $V$ は根付き木に辺をつけたようなものの集合（ set<rooted_tree> ）に根を付け加える関数です.
• $E$ は根付き木の根に親に伸びる辺をつけたようなものの単元集合を生成する関数です.
• $\oplus$ は根付き木に辺をつけたようなものの集合どうしの非交和を取る関数で，集合を列だと思うことにすると可換モノイドです.

次に，$v$ が葉でないときに，$v$ のある子 $h$ を特別視します.

$$dp[v]=V(v,E(vh,dp[h])\underset{vc\in {\vec{E}}_{-}}{⨁}E(vc,dp[c]))$$

そして，関数 $f_v$ を次のように定義します.

$$f_v(x)=V(v,E(vh,x)\underset{vc\in {\vec{E}}_{-}}{⨁}E(vc,dp[c]))$$

このもとで $dp[v]$ は

$$dp[v]=f_v(dp[h])$$

と書けます. $v$ が葉であるときは $f_v(x)$ は定数で，

$$f_v(x)=V(v)(=dp[v])$$

とします. 特別視した子を辿って $v$ から葉まで至る列を $v,h,\dots ,l$ とすると，

$$\begin{array}{rl}dp[v]& =f_v(f_h(\dots f_l(\epsilon )))\\ & =(f_v\circ f_h\circ \cdots \circ f_l)(\epsilon )\end{array}$$

となります. HLD は最も大きな部分木を持つ子を特別視していくつかの heavy path に分解する手法ですが，ここでの $v,h,\dots ,l$ は $1$ つの heavy path に乗っているということになります. つまり，heavy child に優先的に潜る dfs による dfs order で $f_{\cdot }$ たちの関数合成を segment tree に乗せれば，$f_v\circ f_h\circ \cdots \circ f_l$ は segment tree 上の区間取得で計算できます.

木 DP の更新とは，$V$ や $E$ が更新されるということです. これらの更新に対して $f_v$ たちの更新を追従させることを目指します. たとえば，頂点 $v$ が与えられて，$V(v,\cdot )$ の値のみが更新されたとします. このとき，

• $v$
• $v$ の属する heavy path の最も根に近い頂点（top） $t$ の親 $v^{\prime }$
• $v^{\prime }$ の属する heavy path の top $t^{\prime }$ の親 $v^{\prime \prime }$
• $\dots$

に対応する $f_{\cdot }$ が更新されます. これらの更新点の個数は HLD の計算量解析と同じで根付き木の頂点数に対して対数です. $f_t$ は更新されませんが，$f_v$ の更新に伴って $dp[t]$ が更新されるため，これを $f_{v^{\prime }}$ の更新に反映する必要があります. この際，${⨁}_{vc\in {\vec{E}}_{-}}$ を再計算するわけにはいかないので，この差分更新は工夫する必要があります. $\oplus$ に逆元が存在する場合は簡単ですが，一般には $\oplus$ を乗せた segment tree の一点変更として処理することになります. この segment tree には，ある頂点の軽い子 $c$ が連続して並ぶような順序（たとえば bfs order）で $E(vc,dp[c])$ を乗せておけばよく，このとき $⨁$ の計算は区間取得になります.

各更新では，次のものがその時点の計算結果として正確に保持されています.

• すべての頂点 $v$ に対する $f_v$
• すべての頂点 $v$ に対する ${⨁}_{vc\in {\vec{E}}_{-}}E(vc,dp[c])$
• すべての heavy path の top $t$ に対する $dp[t]$

$f_v$ を関数合成を乗せた segment tree で，$E(vc,dp[c])$ を $\oplus$ を乗せた segment tree でそれぞれ管理すれば，$\log$ が $2$ つくらいの時間計算量で更新に追従できます.

例：The 2026 ICPC Asia Pacific Championship - D. Christmas Tree Un-decoration

問題はこちら（Codeforces）

$dp[v]:=$ $v$ を根とする部分木で必要な回数 とすると，遷移は

$$dp[v]=\max (x_v,\sum _{vc\in \vec{E}}dp[c])$$

となります. わざわざあてはめる方が分かりにくいと思いますが，上の定式化で対応するものを書いてみます.

• $V(v,E)=\max (x_v,E)$
• $E(e,V)=V$
• $\oplus =+$

のような感じになると思います. 記号は雰囲気で使っています. 今回は $E$ が $e$ を使わずに $V$ をそのまま返すので，もっと簡単です.

$v$ が葉でないとき，$v$ の子として $h$ を特別視して

$$dp[v]=\max (a_v,dp[h]+\sum _{vc\in {\vec{E}}_{-}}dp[c])$$

と書けます.

$$f_v(x)=\max (a_v,x+\sum _{vc\in {\vec{E}}_{-}}dp[c])$$

とすると，$dp[v]=f_v(dp[h])$ です.

$v$ が葉のときは $f_v(x)=\max (a_v,x-\infty )$ とします. $f_v(x)=a_v$ としても良いですが，$f_v$ を（平行移動つきの）clamp として統一的に扱うことにします.

clamp どうしの合成は clamp です. したがって，関数合成は簡単に計算・保持できます.

クエリでは $x_v$ が更新されますが，これに応じて $f_{\cdot },dp[t]$ を更新します.

• まず，$f_v$ が更新されます.
• 次に $v$ の属する heavy path の top $t$ について $dp[t]$ が更新されます.
• それに伴って，$t$ の親 $v^{\prime }$ について $f_{v^{\prime }}$ が更新されます.
• ...

$dp[t]$ が更新されたとき，$f_{v^{\prime }}$ を更新することは，$v^{\prime }$ について ${\sum }_{vc\in {\vec{E}}_{-}}dp[c]$ を保持しておくことで，差分更新できます. $+$ が逆元を持っているおかげで，$\oplus$ を集約する segment tree は不要になっています.

これで，$x_v$ の変更にすべての変更が追従できました. 最初なので，実装を載せておきます.

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
bool chmin(auto &a, auto b){ return a > b ? a = b, 1 : 0; }
bool chmax(auto &a, auto b){ return a < b ? a = b, 1 : 0; }

template<class S, auto op, auto e>
struct segtree {
    int sz;
    vector<S> d;
    segtree(vector<S> a){
        int n = a.size();
        sz = bit_ceil<uint32_t>(n);
        d.assign(sz*2,e());
        for (int i = 0; i < n; i++){
            d[sz+i] = a[i];
        }
        for (int i = sz-1; i >= 1; i--){
            d[i] = op(d[i*2],d[i*2+1]);
        }
    }
    void set(int p, S x){
        p += sz;
        d[p] = x;
        while (p > 1){
            p >>= 1;
            d[p] = op(d[p*2],d[p*2+1]);
        }
    }
    S prod(int l, int r){
        l += sz, r += sz;
        S sml = e(), smr = e();
        while (l < r){
            if (l & 1) sml = op(sml,d[l++]);
            if (r & 1) smr = op(d[--r],smr);
            l >>= 1;
            r >>= 1;
        }
        return op(sml,smr);
    }
};

//（平行移動つきの）clamp
struct S {
    // max(a, x + b)
    ll a, b;
    // x = any
    ll eval(){
        return max(a,b);
    }
};

// max(f.a, max(g.a, x + g.b) + f.b)
S op(S f, S g){
    chmax(f.a,g.a+f.b);
    f.b += g.b;
    return f;
}
S e(){
    return S{-1LL<<60,0};
}

void solve(){
    int n, q; cin >> n >> q;
    vector<int> par(n);
    vector<vector<int>> g(n);
    par[0] = -1;
    for (int i = 1; i < n; i++){
        cin >> par[i]; par[i]--;
        g[par[i]].emplace_back(i);
    }
    vector<ll> a(n);
    for (int i = 0; i < n; i++){
        cin >> a[i];
    }
    // ord[v] : dfs で v に訪ずれた時刻
    // leaf[v] : v が属する heavy path の最も深い（根から遠い）頂点
    // top[v] : v が属する heavy path の最も浅い（根に近い）頂点
    vector<int> ord(n), leaf(n), top(n); // <- HLD
    // light[v] : \bigoplus_{vc\in\vec{E}_-} E(vc,dp[c])
    vector<ll> light(n), dp(n); // <- ad-hoc
    {
        auto dfs_sz = [&](auto sfs, int v) -> int {
            int sub = 1;
            int ma = -1, id = -1;
            for (int i = -1; auto u : g[v]){
                i++;
                int ch = sfs(sfs,u);
                if (chmax(ma,ch)){
                    id = i;
                }
                sub += ch;
            }
            if (id != -1){
                swap(g[v][0],g[v][id]); // heavy child を先頭に
            }
            return sub;
        };
        dfs_sz(dfs_sz,0);
        int t = 0;
        auto dfs_hld = [&](auto sfs, int v, int ctop) -> int {
            ord[v] = t++;
            top[v] = ctop;
            if (g[v].empty()){
                leaf[v] = v;
                dp[v] = a[v]; // ad-hoc
                return v;
            }
            leaf[v] = sfs(sfs,g[v][0],ctop);
            for (int u : g[v] | views::drop(1)){
                sfs(sfs,u,u);
                light[v] += dp[u]; // ad-hoc
            }
            dp[v] = max(a[v], dp[g[v][0]] + light[v]); // ad-hoc
            return leaf[v];
        };
        dfs_hld(dfs_hld,0,0);
    }
    segtree<S,op,e> seg([&]{
        vector<S> b(n);
        for (int v = 0; v < n; v++){
            b[ord[v]] = S{a[v],light[v]};
        }
        return b;
    }());
    cout << dp[0] << '\n';
    while (q--){
        int v; cin >> v; v--;
        ll x; cin >> x;
        a[v] = x;
        while (v != -1){
            // f_v update
            seg.set(ord[v], S{a[v], light[v]});
            // dp[t] update
            int t = top[v];
            ll dpt = seg.prod(ord[t],ord[leaf[t]]+1).eval();
            int p = par[t];
            if (p != -1){
                light[p] -= dp[t];
                light[p] += dpt;
            }
            dp[t] = dpt;
            v = p;
        }
        cout << dp[0] << '\n';
    }
}

int main(){
    cin.tie(0)->sync_with_stdio(0);
    int t; cin >> t;
    while (t--){
        solve();
    }
}

例：AtCoder Beginner Contest 351 - G. Hash on Tree

問題はこちら(AtCoder)

$dp$ は問題文中の $f$ とします. 問題文中に遷移が書かれていますが，

$$dp[v]=a_v+\prod _{vc\in \vec{E}}dp[c]$$

です. ただし，葉だけ変であることに注意してください. $f_v$ を経由すれば整合性が取れます. すいません，$V,E$ の型が同じで，これも簡単ですね.

例によって，$v$ が葉でないとき，$v$ の子 $h$ を特別視して，

$$dp[v]=a_v+dp[h]\times \prod _{vc\in {\vec{E}}_{-}}dp[c]$$

と書きます.

$$f_v(x)=a_v+x\times \prod _{vc\in {\vec{E}}_{-}}dp[c]$$

とすることで $dp[v]=f_v(dp[h])$ となります. $f_v$ は affine 変換です. 葉の場合は $f_v(x)=a_v$ とすればよいです. そして，affine 変換どうしの合成は affine 変換です.

$\times$ には逆元がないので，light edge をまとめる方の segment tree も使います.

実装は bfs order 順の segment tree も追加で使う以外はほとんど一緒です.

実装(AtCoderへの提出)

例：Library Checker Point Set Tree Path Composite Sum (Fixed Root)

問題はこちら（Library Checker）

$dp[v].ans:=$ $v$ を根とする部分木で $P(\cdot )$ を定義したときの $P(\cdot )$ の総和

$dp[v].sub:=$ $v$ を根とする部分木の頂点数

とします.

遷移は affine 変換が線形であることを用いていろいろ分解できて

$$\begin{gathered} dp[v].ans=a_v+\sum _{vc\in \vec{E}}(b_{vc}dp[c].ans+c_{vc}dp[c].sub) \\ dp[v].sub=1+\sum _{vc\in \vec{E}}dp[c].sub \end{gathered}$$

と書けます.

先述の定式化においては

• $V(v,E).ans=a_v+E.sum$
• $V(v,E).sub=1+E.sub$
• $E(e,V).sum=b_{vc}V.ans+c_{vc}V.sub$
• $E(e,V).sub=V.sub$
• $\oplus =+$ (ベクトルとしての加算)

です. ようやく辺重みが登場しました.

例によって，$v$ が葉でないとき，$v$ の子 $h$ を特別視して，

$$\begin{gathered} dp[v].ans=a_v+b_{vh}dp[h].ans+c_{vh}dp[h].sub+\sum _{vc\in {\vec{E}}_{-}}(b_{vc}dp[c].ans+c_{vc}dp[c].sub) \\ dp[v].sub=1+dp[h].sub+\sum _{vc\in {\vec{E}}_{-}}dp[c].sub \end{gathered}$$

と書きます.

$$\begin{gathered} f_v(x).ans=a_v+b_{vh}x.ans+c_{vh}x.sub+\sum _{vc\in {\vec{E}}_{-}}(b_{vc}dp[c].ans+c_{vc}dp[c].sub) \\ {f}_v(x).sub=1+x.sub+\sum _{vc\in {\vec{E}}_{-}}dp[c].sub \end{gathered}$$

とすることで $dp[v]=f_v(dp[h])$ となります. $f_v$ は affine 変換です. 葉の場合は $f_v(x).ans=a_v,f_v(x).sub=1$ とすればよいです.

辺 $vc$ の更新があったとき，その辺が heavy edge であるか light edge であるかで，更新すべきものが変わります. heavy edge のときは $f_v$ が更新されます. light edge のときは ${⨁}_{vc\in {\vec{E}}_{-}}E(vc,dp[c])$ が更新されます. いずれの場合も，その先の更新は頂点 $v$ に更新があったものと思って更新していけばよいです.

affine 変換と書きましたが，これは

$$\left(\begin{array}{c}{f}_v(x).ans\\ f_v(x).sub\end{array}\right)=\left(\begin{array}{c}{a}_v+{\sum }_{vc\in {\vec{E}}_{-}}(b_{vc}dp[c].ans+c_{vc}dp[c].sub)\\ 1+{\sum }_{vc\in {\vec{E}}_{-}}dp[c].sub\end{array}\right)+\left(\begin{array}{cc}{b}_{vh}& c_{vh}\\ 0& 1\end{array}\right)\left(\begin{array}{c}x.ans\\ x.sub\end{array}\right)$$

として $2$ 次元ベクトルとして見ています. ここで，これを愚直に表現すると $f_v(x)=A_v+B_{v}x$ として $2$ 次元ベクトル $A_v$ と $2\times 2$ 行列 $B_v$ を持つことになりますが，$2$ 行目は明らかに部分木サイズの情報だけで事足りる上にこれは static なので，削減することで定数倍ではありますが大きく改善するでしょう. そもそも DP をもう少し違う形で書いた方が良いです. ここでは DP で計算するべき値がスカラーではない場合でも扱えることを確認するために，このままにしています.

実装（Library Checker への提出）

部分木サイズが static であることを用いた高速化（Library Checker への提出）

${\log }^1$ への道

heavy path 上の頂点に対する $f_{\cdot }$ を乗せた segment tree には，異なる heavy path に跨がる区間の区間取得が来ることはありません. $\oplus$ を集約する segment tree についても同様のことが言えます. このことから，そもそも集約に通常の segment tree を用いるのは無駄があると言えるでしょう. もう少し無駄を観察してみます.

• $f_{\cdot }$ を集約する segment tree には，heavy path ごとに分割すれば，suffix にしか取得クエリが来ない
• $\oplus$ を集約する segment tree には，特定の頂点の light child ごとに分割すれば，全体にしか取得クエリが来ない

これの改善を突き詰めていくと，完全ではない二分木を segment tree と見なすことで，うまく二分木を構築すると ${\log }^1$ になります. そして，そのことは，HLD が木を heavy path からなる高さが頂点数の対数になる木に分解する手法であったのと同様に，STT が木を cluster からなる高さが頂点数の対数になる二分木に分解する手法であるものとして解釈できるはずです. 筆者は cluster の扱いについて詳しくないため，これ以上のことは書けません.

根付き木の構成として，ここでは，最も一般的だと思われる rooted_tree = pair<vertex, set<rooted_tree> > を採用し，そのまま木 DP の更新を導出しました. と言うのは誤解があり，HLD は rooted_tree = vector<pair<vertex, set<rooted_tree>>> として構成していて，実際のところはこの構成に計算を乗せていると思うことができます. heavy path というのは pair::first だけ取り出した vector<vertex> にあたるものです. 難しいのは辺の情報をどこに乗せるかだと筆者は思っていて，cluster などの概念を学ぶと辺の扱いの見通しが良くなるかもしれません. ここで強調したいのは，「辺の情報は子の方が持つ」のような抽象的（標語的）な理解をする必要はなくて，式変形から直接実装が導出できるということです.

全方位化

少し難しいですが，できます. 気持ちは同じで，「子のうちひとつを特別視する」です.

$N$ 頂点の木を取ります. 全方位木 DP で部分木として扱うものは $3N-2$ 種類です. $N$ 個は各頂点を根にしたときの全体の木に対する DP で，残りの $2N-2$ 個は各辺の各向きについてそれが指す先の頂点を根とするその向きの根付き木です（伝われ〜）.

根をひとつ固定して，辺の親側・子側を定めます. 親から子へ向かう辺 $pv$ について，$pv$ に対応する DP はこれまでの方法ですでに計算できています. 一方 $vp$ に対応する DP はどうでしょうか. この場合は $p$ の親 $q$ を特別視します.

$$dp[vp]=V(p,E(pq,dp[pq])\underset{pc\in \vec{E}\setminus \{pv\}}{⨁}E(pc,dp[c]))$$

$pv$ が heavy edge であるときは $pc\in \vec{E}\setminus \{pv\}$ は $pc\in {\vec{E}}_{-}$ と同値で，${⨁}_{pc\in {\vec{E}}_{-}}E(pc,dp[c])$ は更新できるのでした.

$$g_{vp}(x)=V(p,E(pq,x)\underset{pc\in {\vec{E}}_{-}}{⨁}E(pc,dp[c]))$$

とすると $dp[vp]=g_{vp}(dp[pq])$ です. heavy path に逆向きに $g_{\cdot }$ の関数合成を乗せれば良さそうなことが分かりました. 一方，$pv$ が light edge であるときは，$g_{vp}$ を同様に定義しても $g_{vp}$ の更新はできません. $p$ の次数が大きな場合を考えると分かると思います. このときは諦めて定義通り計算することにします. $E(pc,dp[c])$ はすべて $\oplus$ を集計する segment tree に乗っているので，そこから $pv$ の部分だけ取り除いたものも計算できます. 問題は $dp[pq]$ を求める部分ですが，この部分は再帰的に計算します. この再帰は $p$ が根になるまで続きますが，light edge はそれまでに対数回しか現れないので大丈夫です.

各頂点を根にしたときの DP の値は，その頂点から親に向かう DP が計算できるのなら，当然できます.

全方位にすることで新たに保持して更新に追従するべきものは，heavy edge に対する逆向きの関数 $g_{\cdot }$ だけです.

実装例（Point Set Tree Path Composite Sum）（Library Checker への提出）

他の問題例

UCup の問題

JOI の問題

おわりに

特に数式の扱いが雑になってしまいました. ちゃんと書くと雰囲気を掴むことの邪魔になってしまいそうだった，と言い訳させていただきます. なにか分からないことがあれば X(twitter) で聞いてください. なんでも答えます.