物体の最高速はいくら?

まさかのAtcoderRegularContestのA問題で硬直したので復習兼ねて書きます。ネタもないし 何かアクションゲームを作るときに便利そうなケースを考えてみる。 というより、昔簡単なゲーム作るときに頻繁に使った。
ここに車がある。 車の現在の速度は%$0$%[dist/tick]である。 車の速度は%$1$%tick当たり%$a$%増えようとするが、%$b(0<b<1)$%の減衰を受ける。 減衰を受けるので、速度はいずれ頭打ちになるはずである。最高速度を求めたい。
ところで、「tick」は「時刻の1単位」として書いていますが、試しにググったらマダニという検索結果が出て不安です。 数式にすると、 %$V_0 = 0$% %$V_{t+1} = b(a+V_t)$% ただし、%$t$%は時刻、%$V_t$%は%$t$%[tick]後の車の速度。
それでは解いてみます。 とりあえず式を書いてみる。 %$V_0 = 0$% %$V_1 = ab$% %$V_2 = ab+ab^2$% %$V_3 = ab+ab^2+ab^3$% 増え方を観察すると、 %$V_3 = V_2+ab^3$% これを一般化すると、 %$V_t = V_{t-1}+ab^t$% 始めの式をVtに代入。 %$b(a+V_{t-1}) = V_{t-1}+ab^t$% 変形 %$ba+bV_{t-1} - V_{t-1}=ab^t$% %$(b-1)V_{t-1} = ab^t-ba$% %$V_{t-1} = \frac{a(b^t-b)}{b-1}$% 最高速を求めたかったので、%$t\rightarrow \infty$%すると%$b^t$%は0に化けるので %$V_{\rm max} = \frac{ab}{1-b}$% おしまい。 と、数年前のメモ帳を写しながら思ったのですが、これ別解法あるかも。 特殊解%$V_{t+1} = V_t = W$%を考える。 %$W = b(a+W)$% 変形 %$W = ba+bW$% %$W-bW = ab$% %$(1-b)W = ab$% %$W = \frac{ab}{1-b}$% ところで、%$t\rightarrow \infty$%の時%$V_{t+1} = V_t$%になるはずので、%$V_{\rm max} =W$%でした。 おしまい。 簡単すぎたので、上の続きとして、tの関数も求めてみる。 %$W_t = V_t-W$% %$W_t +W = V_t$% という%$W_t$%を新たに作って、これに置き換える。 %$W_{t+1}+W = b(a+W_t+W)$% 式変形がんばる %$W_{t+1}+\frac{ab}{1-b} = ab+bW_t+b\frac{ab}{1-b}$% %$W_{t+1}-bW_t = ab-\frac{ab}{1-b}+b\frac{ab}{1-b}$% %$(1-b)(W_{t+1}-bW_t) = (1-b)ab-ab+ab^2$% %$(1-b)(W_{t+1}-bW_t) = ab-ab^2-ab+ab^2$% %$(1-b)(W_{t+1}-bW_t) = 0$% 綺麗になった。 %$W_{t+1} = bW_t$% %$\frac{W_{t+1}}{W_t} = b$% 比が定数なので、等比数列。 %$W_t = W_0b^t$% ここで、%$V_t$%に書き戻す ところで、%$V_0=0$%ですが、なんとなく残しています %$V_t-W = (V_0-W)b^t$% %$V_t = (V_0-W)b^t+W$% %$V_t = V_0 b^t-Wb^t+W$% %$V_t = V_0 b^t+(1-b^t)W$% %$V_t = V_0 b^t+(1-b^t)\frac{ab}{1-b}$% %$V_t = V_0 b^t+\frac{ab-ab^{t+1}}{1-b}$% え、最初の解法と式が違うだって?もう少し変形しますか。 %$V_t = V_0 b^t+\frac{ab^{t+1}-ab}{b-1}$% ところで、最初の式 %$V_{t} = b(a+V_{t-1})$% %$V_{t}/b = a+V_{t-1}$% %$V_{t-1}=V_{t}/b -a $% なので、この式に求めた式を代入して、 %$V_{t-1} = (V_0 b^t+\frac{ab^{t+1}-ab}{b-1}) /b -a$% %$V_{t-1} = V_0 b^{t-1}+\frac{ab^t-a}{b-1} -a$% %$V_{t-1} = V_0 b^{t-1}+\frac{ab^t-a-a(b-1)}{b-1}$% %$V_{t-1} = V_0 b^{t-1}+\frac{ab^t-a+a-ab}{b-1}$% %$V_{t-1} = V_0 b^{t-1}+\frac{a(b^t-b)}{b-1}$% おー、一致しましたね。 ところで、冒頭のARCの話は一切関係ありませんでした。
スポンサーサイト

テーマ : プログラミング
ジャンル : コンピュータ

コメントの投稿

非公開コメント

プロフィール

舞葉(ぶよう)

Author:舞葉(ぶよう)
github.io
はてなブログ(競プロ)

古い記事のソースコードは色分けしていないので、高機能テキストエディタに貼り付けたほうが見やすいかも。

検索フォーム
このブログについて
自分がつまづいた話題、なんとなく書きたいと思ったこと、ググったけど殆ど資料なかったぞオイ な話等をアップする予定。通りすがりでも、参考になっていただければと。プログラムの例外入力、メモリリークは責任負いません。投稿された記事は修正・削除する場合があります。
カテゴリ
タグ

HSP3アルゴリズムとデータ構造c++RubyJavaUnity画像解析C機械学習C#LinuxcodeIQKinectMinecraftTonyuSystemraspberrypiPythonHTML5音声制御Simulinkruby俺ルール通信制御Javascriptシミュレーション

counter-shinobi
固定記事
最新記事
最新コメント
月別アーカイブ
ブロとも申請フォーム

この人とブロともになる

アクセスランキング
[ジャンルランキング]
コンピュータ
1253位
アクセスランキングを見る>>

[サブジャンルランキング]
プログラミング
219位
アクセスランキングを見る>>