生きる

助けて

合成関数の微分

関数 $f, g$ が微分可能であるとする。このとき、関数 $f(g(x))$ の点 $x=a$ における微分係数は $f'(g(a))g'(a)$ である。このことは合成関数の微分の公式として知られ、高校数学の教科書にも載っているが、そのよくある証明には厳密でない部分がある。この記事ではよくある証明を少しだけ修正することで厳密な証明を与える。

証明?

関数 $f(g(x))$ の点 $x=a$ における微分係数を求めよう。$u=g(a), y=f(u)=f(g(a))$ とおく。$a$ が $\Delta x$ だけ増加したときの $u$ の増加分を $\Delta u$、$u$ が $\Delta u$ だけ増加したときの $y$ の増加分を $\Delta y$ とする。すなわち、 \begin{align} \Delta u &= g(a+\Delta x) - g(a)\\ \Delta y &= f(u+\Delta u) - f(u)= f(g(a+\Delta x)) - f(g(a)) \end{align} と定義する。微分係数の定義により、求める極限は \begin{align} \lim_{\Delta x \rightarrow 0} \frac{f(g(a+\Delta x)) - f(g(a))}{\Delta x} \end{align} である。ここで、$\lim$ の中の式は \begin{align} \frac{f(g(a+\Delta x)) - f(g(a))}{\Delta x} = \frac{\Delta y}{\Delta x} = \frac{\Delta y}{\Delta u} \cdot \frac{\Delta u}{\Delta x} \cdots \cdots (*) \end{align} と変形できる。$g$ は連続なので $\Delta x \rightarrow 0$ のとき $\Delta u \rightarrow 0$ である。さらに $f, g$ は微分可能なので、極限値 \begin{align} \lim_{\Delta u \rightarrow 0} \frac{\Delta y}{\Delta u}, & & \lim_{\Delta x \rightarrow 0} \frac{\Delta u}{\Delta x} \end{align} が存在する。それぞれ $f'(u), g'(a)$ とおけば、求める極限値は \begin{align} \lim_{\Delta x \rightarrow 0} \frac{f(g(a+\Delta x)) - f(g(a))}{\Delta x} =\lim_{\Delta x \rightarrow 0} \frac{\Delta y}{\Delta u} \cdot \frac{\Delta u}{\Delta x} =f'(u)g'(a)=f'(g(a))g'(a) \end{align} である。

問題点

上の証明には厳密でない点がある。問題は $(*)$ の変形にある。この変形は両辺が $\Delta x=0$ の十分近くで $\Delta x$ の関数として等しいことを根拠にした変形である。しかしながら、これは成り立たないケースがある。$\Delta u$($\Delta x$ によってその値が定まる)が $0$ となるような $\Delta x$ を考えよう。 このとき、$(*)$ の変形前の式の値は $0$ であるのに対し、変形後の式の値は分母に $\Delta u$ があるため未定義である。したがって $\Delta x=0$ のどれだけ近くを考えても $\Delta u=0$ となる点が存在するような関数 $g$ が与えられた場合には、$\Delta x=0$ のどれだけ近くを考えても $(*)$の両辺は $\Delta x$ の関数として異なることになり、$(*)$ の変形は非合法である。といってもほとんどの場合で問題は起きない気がするが、実際に問題が起きる例としては、関数 $g$ が定数関数である場合が挙げられる。っていうか関数 $g$ が定数関数だったら $f(g(x))$ も定数なわけで、普通は合成関数の微分しようとか思わないじゃん。

修正

イメージとしては $\Delta x$ を $0$ に近づけていくとき、 $(*)$ の最左辺と最右辺は、見えているときはいつも等しいが、最右辺だけが時折チラついているような状況である。このチラつきをなくしてやればよい。チラつきの原因は $\Delta y / \Delta u$ の部分である。この部分を次の関数で置き換える。 \begin{align} h(\Delta u) = \begin{cases} \Delta y / \Delta u & \Delta u \neq 0\\ f'(u) & \Delta u = 0 \end{cases} \end{align} そうすれば任意の $\Delta x$ について \begin{align} \frac{f(g(a+\Delta x)) - f(g(a))}{\Delta x} = h(\Delta u) \cdot \frac{\Delta u}{\Delta x} \end{align} である。つまり両者は $\Delta x$ の関数として等しい。さらに $\Delta x \rightarrow 0$ とすると、$\Delta u / \Delta x \rightarrow g'(a)$ かつたとえ $\Delta u$ の値が $0$ を取りながら $0$ に収束したとしても $h(\Delta u) \rightarrow f'(u)$ である。したがって求める極限値は $f'(u)g'(a)=f'(g(a))g'(a)$ である。

C言語で可変長引数を取る関数を定義する

可変長引数とは、printf関数が取るような、あらかじめ個数が決まっていない形式の引数のことである。

例えば、自分用のprintfを新たに定義したいとすると、引数の部分は次のように書く。

void myprintf(char *fmt, ...) {

}

こう書くと、fmtに続く引数が可変になる。 ...の前には引数が複数あってもよいが、...の後に引数があってはならない。 つまり、...は引数の最後でなければならない。

渡された可変長引数を使うには、stdarg.hで定義されている型やマクロを使う。以下にそれらの使い方の例を示す。

#include <stdio.h>
#include <stdarg.h>

void myprintf(char *fmt, ...) {
    va_list ap;
    va_start(ap, fmt);
    
    char *p = fmt;
    
    while (*p) {
        if (*p == 'd') {
            printf("%d ", va_arg(ap, int));
            p++;
            continue;
        }

        if (*p == 'c') {
            printf("%c ", va_arg(ap, char));
            p++;
            continue;
        }
        
        fprintf(stderr, "不正な文字\n");
        exit(1);
    }
    
    printf("\n");
}

va_list型は引数のリストをイテレートするためのポインタを表す。 "va"はおそらく可変超引数を表す英語variadic argumentsの略。

va_start(ap, fmt)によって、apfmtに続く引数のリストの先頭を指している状態になる。 一般にva_startの第二引数には...の直前の引数の識別子を指定する。

引数のリストを順番に調べるには、va_argマクロを使う。va_arg(ap, int)apが指している位置の引数をint型として返し、apが指す位置を一つ先に進める。

myprintf関数は簡易的なprintfを実現する。具体的には、dcからなる文字列と可変長引数を受け取り、可変長引数を参照しながら、dを整数に、cを文字に置き換える。 例えばmyprintf("dcdcd", 1, 'a', 2, 'b', 3)を呼び出すと1 a 2 b 3と表示される。

進捗

スマホから投稿してみるテスト。

「コンピュータの構成と設計」を読むという話をして1ヶ月が経ったので、その間何をしていたのかについて。なお、当該記事(と、その前の記事)は非公開にした。公開していてもいいことがなさそうだったので。たまに爆発してしまうかもしれないけれど、可能な限り平穏に運用していきたい。

「コンピュータの構成と設計」の進捗は現在30%くらい。前に2ヶ月で読むことを目標にしていたので少し遅い。遅れた要因は寄り道をしていたのと、単純に難しかったから。想定していたペースで読み進めるのが難しいことがわかったので、ここは焦らず4ヶ月くらいかけて読むことにする。

他には、業務の都合で「まとまって何かするには短いが、かといって何もしないわけにもいかない時間」が発生していて、その間好きに勉強していていいことになったので、AIZU ONLINE JUDGEのALDS1をずっと解いていた。昔ちょっとかじっていたのも含めて7割近くの問題が終わった。LCSとか、昔よくわからなかったけど改めてやってみたらちゃんとわかって面白かった(できれば記事にしたい)。ここまで来たら全問やりたい気もする。実は螺旋本持ってるし。

あと最近はデジタル回路設計にも興味が湧いてきた。FPGAってやつを買えば自作の回路を書き込んでいろいろ試せるのかな。それで自作のCPUとか作ってみたい。今年の初めに「CPUの創りかた」を読んで、あれくらい(4bit)のCPUなら作れるかもと思った。あの本では実際に部品を買ってきて作るのを目標にしてたけどそれは別の大変さがありそうであまり気が進まない。アナログ的な話があってのデジタルなんだろうけど、今はいいかな〜と思う(全く興味がないわけではない)。

という感じで興味が広がる一方で現実は目の前の業務すらおぼつかないわけで、そんなことをやってる場合なのかという気持ちになる。どうやら英語もできないといけないみたいだし。俺は、どうすればいい。

VSCodeのC/C++拡張(ms-vscode.cpptools)のデバッグ機能がM1 Macに対応していない件

2ヶ月ぐらい前に届いたMacBook Air (M1, 2020)をやっと使い始めている。VSCodeがもうApple M1チップにネイティブ対応しているらしいので、設定をすることにした。今のところプロコンぐらいしか使い道が思い浮かばないので、すごく本格的なことができる必要はない。C/C++のコードが書けて、コンパイルできて、デバッグできればよい。

とりあえずVSCodeのドキュメントに書いてある通りに進めた。コンパイラとデバッガはAppleのCommand Line Toolsをインストールすると入っているClangとLLDBを使う。

Configure VS Code for Clang/LLVM on macOS

ビルド(コンパイル)するところまではよかったが、デバッグのところでこんなエラーが出てうまくいかなかった。

Warning: Debuggee TargetArchitecture not detected, assuming x86_64.
ERROR: Unable to start debugging. Unexpected LLDB output from command "-exec-run". process exited with status -1 (attach failed ((os/kern) invalid argument))
The program '/Users/sitorasu/projects/helloworld/helloworld' has exited with code 42 (0x0000002a).

調べてみると、現在のところMicrosoftC/C++拡張(ms-vscode.cpptools)のデバッグ機能はApple M1チップでネイティブに動作するデバッガには対応していないらしい。

Support Apple Silicon ARM64 architecture natively for debugger · Issue #7035 · microsoft/vscode-cpptools · GitHub

このスレッドを見ると、対処法としてはrosettaを使って全部x86_64で完結させる(?)か、すでにApple M1チップに対応している別の拡張機能を使うのがいいらしい。前者はよくわからなかったので後者を選択することにした。別の拡張機能というのはCodeLLDB(vscode-lldb)というやつ。VSCode拡張機能検索でlldbとか調べれば出る。

GitHub - vadimcn/vscode-lldb: A native debugger extension for VSCode based on LLDB

どうやらこっちは対応済みらしい。

Please support Apple silicon (M1, arm64-darwin) · Issue #397 · vadimcn/vscode-lldb · GitHub

launch.jsonにはこんな感じで書く。

{
    "version": "0.2.0",
    "configurations": [
        {
            "name": "vscode-lldb",
            "type": "lldb",
            "request": "launch",
            "program": "${workspaceFolder}/${fileBasenameNoExtension}",
            "args": [],
            "cwd": "${workspaceFolder}",
            "preLaunchTask": "clang++ build active file"
        }
    ]
}

"type": "lldb"と指定することで(Microsoftのではなく)CodeLLDBがデバッグに使われるようになるっぽい。ちなみに、tasks.jsonには上のVSCodeのドキュメントに書いてある通りに書いてある。

これでちゃんとデバッグできるようになりました。めでたしめでたし。

競プロ典型90問 001 - Yokan Party

スコアを与えられた数以上にできるかどうかの判定法について。(注意:説明がくどい)

目次

問題と解説

問題はこちら→https://atcoder.jp/contests/typical90/tasks/typical90_a

出題者による解説はこちら(添付画像左)↓

解法のポイント

与えられた整数  M に対して、「スコアを  M 以上にできるか?」は簡単に判定できる

二分探索は知っていたが、この事実に気付けなかったために解けなかった。逆にこれに気付きさえすれば、「 M を動かして調べればいい」→「全範囲を調べると間に合わない」→「二分探索を使おう」という発想に至るのは難しくないと思う。しかしながら、解答を読んでも上記の問いに対する判定法の正しさをすぐには理解できなかった。そこで、以下ではその判定法について詳しく考察する。(二分探索については解説しない。)

判定のしかた

解答のステップ2にある通りだが、改めて説明する。

  • 切れ目を左から見ていく。
  • 最後に切ったところ(一度も切っていないときは左端)からの距離が初めて  M 以上になったらその切れ目で切る。これを繰り返す。
  • ただし、次の条件をいずれかを満たす場合はそれ以上切らずに繰り返しをやめる。
    • 切れ目の右端まで見終わった。
    • もし今見ている切れ目を切ると、右側の残った部分の長さが  M 未満になる。
  • トータルで切った回数が  K 以上ならスコアを  M 以上にできる。 K 未満ならできない。

この判定法を「判定法A」と呼ぶことにする。

下の図に示すような ようかん があるとする。縦線は切れ目を表し、切れ目と切れ目の間の数字はそれらの間の距離を表す。

f:id:sitorasu_today:20210508202617p:plain

このようかんを  4 回切って  5 つのピースに分けることを考える。このとき、スコアを  3 以上にできるか?は次のようにして判定できる。

f:id:sitorasu_today:20210508182207p:plain

では、スコアを  6 以上にはできるだろうか?

f:id:sitorasu_today:20210508183339p:plain

一番右の切れ目は切らないことに注意してほしい。

判定法の正しさ

なるほど、判定のしかた自体は分かった。でもどうしてこの方法で正しく判定できるのだろう?先ほどの例で考えてみよう。ようかんを  4 回切って  5 つのピースに分けるとき、スコアを  3 以上にはできるのだった。

この理由を説明するのは簡単だ。 5 回切ったうちの  1 回を切らないようにすれば、スコアを  3 以上にする切り方のひとつが構成できる。同様に、 5 回切ったうちの何回かを切らないようにすることで、 5 回以下の任意の回数切ってスコアを  3 以上にする方法が構成できる。一般に、与えられた整数  M に対して、判定法Aで  X 回切ることができたならば、 X 回以下の任意の回数切ってスコアを  M 以上にできる。

問題は、 X 回より多く切ってスコアを  M 以上にする方法が本当に存在しないのかということである。言い換えれば、 X はスコア  M 以上になるように切れる最大の回数なのかということだ。もしそうであれば判定法Aは正しい。しかし、判定法Aはパッと見ではすべての切り方を考慮しつくしているようには思えない。例えば先ほどの結果によれば、 4 回切ってスコアを  6 以上にする方法は存在しないのであった。

果たして本当にそうだろうか?違う切り方を試してみよう。例えば、最初に切る位置を少し左にずらしてみる。

f:id:sitorasu_today:20210508183914p:plain

これは全然ダメだ。今切り出したピースの長さが  6 未満なので、この時点でスコアが  6 未満になってしまうことが確定する。それでは、今度は最初に切る位置を少し右にずらしてみよう。

f:id:sitorasu_today:20210508183937p:plain

このように切っても、スコア  6 以上を保って切れる最大回数は増えそうにない。なぜならば、判定法Aで最初に切った段階よりも残り少ないようかんを、より多く切らなければならないからである。たとえるなら、テスト用紙の小さな記名欄に、自分の名前の一文字目を大きく書いてしまったような状況だ。でも実際の状況はもう少し複雑だ。今回の問題設定では切れ目の位置が決まっているし、それらが均等に配置されているとも限らないからだ。もう少しちゃんと考えることにする。

任意のようかんと切れ目と整数  M が与えられたとする。判定法Aにしたがって最初の一回を切った後、残りをスコアが  M 以上になるように切る方法のうち、切れる最大の回数を  S とする。また、最初の一回を判定法Aより右側で切り、残りをスコアが  M 以上になるように切る方法のうち、切れる最大の回数を  S' とする。

f:id:sitorasu_today:20210508193045p:plain f:id:sitorasu_today:20210508193016p:plain

このとき、 S \geq S' である。なぜなら、もし仮に  S \lt S' であるとすると、判定法Aにしたがって最初の一回を切った後、残りをスコアが  M 以上になるように  S'(\gt S) 回切ることができるからである(下図参照)。これは  S が最大であることに矛盾する。

f:id:sitorasu_today:20210508193113p:plain

したがって、一回目を判定法A以外の方法で切ってもトータルで切れる最大回数は増えないことがわかる。つまり、最初の一回は判定法Aにしたがうのが最善である。これにより、ようかん全体をスコアが  M 以上になるようにできるだけたくさん切る問題は、最初の一回を判定法Aにしたがって切り、残りをできるだけたくさん切るという、より小さな問題に帰着できる。さらに、この理屈は残りのようかんに対して繰り返し適用できる。つまり、残りのようかんを改めてようかん全体だとみなすことで、残りをできるだけたくさん切るという問題は、残りを判定法Aにしたがって一回切り、それでもなお残った部分をできるだけたくさん切るというさらに小さな問題に帰着できる(下図参照)。これを繰り返すことで元の問題は自明な問題に帰着され、最大回数を求めることができる。これは判定法Aそのものである。

f:id:sitorasu_today:20210508195103p:plain f:id:sitorasu_today:20210508195117p:plain f:id:sitorasu_today:20210508195156p:plain f:id:sitorasu_today:20210508195210p:plain f:id:sitorasu_today:20210508195240p:plain f:id:sitorasu_today:20210508195259p:plain

大きな問題を小さな問題に帰着するようすはユークリッドの互除法にも似ている。

f:id:sitorasu_today:20210508200935p:plain

類題としては以下を知っている。今回取り上げた問題とは最大最小がひっくり返ったようなかたちだ。

https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_4_D&lang=ja

こういうのを見ていると、解法が思い浮かぶかどうかというのは、理詰めでそこに至れるかどうかというよりは、過去に解いた問題と同じ匂いを感じ取れるかどうかにかかっている気がする。典型問題特有の事情なのかもしれないけど。