秘密の本棚

気になることをなんでも書きます

一定速度で発射した物体が描く放物線の包絡線

経緯

前にこんなツイートを見かけました。


実はこれ、京大の過去問にあります('00後期)。
最大の初速度v_0で、あらゆる方向に打ち分けることができる最強の打者を考慮して、ドーム球場(屋根付き野球場)を設計したい。座標の原点Oをホームベース上にとり、ボールが飛ぶ鉛直面内で原点Oから水平方向にx軸を、また鉛直上向きにy軸をとる。ただし、簡単のため、ボールは原点Oで打たれるものとする。また、重力加速度の大きさをgとし、空気抵抗およびボールの大きさは無視できるものとする。
初速度v_0で打たれたボールが、打ち上げ角度に拘わらずドームの天井に当たらないためには、ホームベースからRだけ離れた地点での天井の高さはいくつより大きくなければならないか。
要するに、以下の図で\thetaが変化するときボールが通過しうる領域はどこかという問題です。
f:id:nexusuica:20181111230158p:plain:w400
(図:https://physnotes.jp/exercises/shahou_orb/

まずやることは適当な角度\thetaでの物体の軌跡を求めることです。これは、時刻tにおける物体の位置
 \displaystyle x=v_0t\cos\theta,\ y=v_0t\sin\theta-\frac12gt^2
からtを消去して、
 \displaystyle  y=x\tan\theta-\frac{gx^2}{2v_0^2\cos^2\theta},\ y\geq0
となります。あとはこれを0<\theta<\frac{\pi}2で変化させたときにこの放物線が通過する領域を求めればよいわけです。通過領域を求めるには

  • 順像法
  • 逆像法
  • 包絡線の計算

の3つのやり方があり、どれでもできます。とりあえず\thetaが複雑で鬱陶しいのでa=\tan\thetaとおいておけば
 \displaystyle y=ax-\frac{(1+a^2)gx^2}{2v_0^2}
となります。

順像法

順像法とは、「ある直線上のみでの通過範囲を求める」ことによって通過領域を求める方法です。今回であれば「あるx座標のみを考えたときに、\thetaを変化させたとしてどこを通過するか?」を考えます。つまり、xを固定してy\thetaの関数と見てその値域を求めることになります。
いま、ya=\tan\thetaの2次関数なのでその値域は平方完成することによって容易に求まり、
  \displaystyle y=-\frac{gx^2}{2v_0^2}\left(a-\frac{v_0^2}{gx}\right)^2+\frac{v_0^4-g^2x^2}{2gv_0^2}
より、yの値域は
  \displaystyle 0\leq y\leq \frac{v_0^4-g^2x^2}{2gv_0^2}
となります。結局これは鉛直投げ上げ運動の最高到達点\displaystyle \frac{v_0^2}{2g}を頂点とする放物線になっています。
www.desmos.com

逆像法

今度は逆像法です。逆像法とは、「ある点(x,y)を曲線が通過するようなパラメータの値が存在するかどうか」という存在条件から通過領域を求める方法です。今回は軌跡の方程式をパラメータaの方程式とみてaの存在条件を求めます。方程式をaについて整理すると
 gx^2a^2-2v_0xa+2v_0^2y+gx^2=0
となります。いまaの取りうる範囲はa>0なので、この範囲に解を少なくとも1つもつ(x,y)の条件を求めればよいことになります。左辺はaの2次関数になっていて、その放物線の軸はx>0のもとではa>0に存在します。また、左辺をf(a)とおくとき
  f(0)=2v_0^2y+gx^2>0
より、a\leq 0には実数解は存在しえないことがわかり、結局たんに実数解をもつ条件のみを求めればよいです。これは判別式を使って、
  \displaystyle (v_0x)^2-gx^2(2v_0^2y+gx^2)\geq 0\Leftrightarrow y\leq \frac{v_0^4-g^2x^2}{2gv_0^2}
と、同じ結果が得られます。

包絡線を直接求める

これまでは関数の値域や文字の存在条件から曲線の通過領域を求めましたが、この通過領域の境目には、もとの放物線が接しながら動きます(先ほどのグラフを参照)。このようにある曲線のパラメータを変化させたときにその曲線が常に接しながら動く曲線のことを包絡線といい、これを直接求める方法が存在します。
詳しいことはここに書いてあります。
mathtrain.jp
ここでは曲線を
  \displaystyle f(x,y,a)=ax-\frac{(1+a^2)gx^2}{2v_0^2}-y
とし、f(x,y,a)=0\displaystyle \frac{\partial}{\partial a}f(x,y,a)=0を連立して解きます。
  \displaystyle \frac{\partial}{\partial a}f(x,y,a)=x-\frac{agx^2}{v_0^2}
なので頑張ってaを消去して計算すると、包絡線として \displaystyle y=\frac{v_0^4-g^2x^2}{2gv_0^2}が得られます。

というわけで、野球ドームの天井は放物線にしておけばよいという結論(?)が得られました。

AtCoder Beginner Contest 113

C - ID

問題

C - ID

考察

N個にグループ分けされる、順序付きのM個の要素があり、グループごとに順番に番号を振って最後に与えられた順に番号を出力する。
愚直に入力をグループ分けしてまずソートして番号を振ったのち、すべての要素を合体して与えられた順にソートし直せばよい。重いけど構造体で管理しようか。

コード

struct city{ll num, pref, year; str id;};
bool comp_year(city a, city b){
  return a.year<b.year;
}
bool comp_num(city a, city b){
  return a.num<b.num;
}

int main(){
  ll n,m;
  cin >> n >> m;
  vector<city> prefs[n];
  REP(i,m){
    city temp;
    temp.num = i;
    cin >> temp.pref >> temp.year;
    temp.pref--;
    prefs[temp.pref].push_back(temp);
  }
  vector<city> all;
  REP(i,n){
    sort(prefs[i].begin(),prefs[i].end(),comp_year);
    ostringstream sout;
    sout << setfill('0') << setw(6) << i+1;
    str pref_str = sout.str();
    REP(j,prefs[i].size()){
      ostringstream sout2;
      sout2 << setfill('0') << setw(6) << j+1;
      str order_str = sout2.str();
      prefs[i][j].id = pref_str + order_str;
      all.push_back(prefs[i][j]);
    }
  }
  sort(all.begin(),all.end(),comp_num);
  REP(i,all.size()){
    cout << all[i].id << endl;
  }
  return 0;
}

D - Number of Amidakuji

考察

W列、高さHの縦棒に対して適当に横棒を入れてあみだくじをつくり、一番左から出発してK番目に到達するあみだくじの個数を求める。
動的計画法で「高さiにおける左からj本目へ到達するあみだくじの横棒の置き方」をカウントしていけばよい。iからi+1への推移は、高さi+1での横棒の置き方すべてに対して、あみだくじとして不適切なものを除いて適宜加算を行う。今回はH\leq 8がキーとなる。
なお、さらに考察するとO(HW)でも行ける模様。
sigma1113.hatenablog.com

コード

const ll p = 1000000007;

int main(){
  ll h, w, k;
  cin >> h >> w >> k;
  ll dp[h+1][w];
  fill(dp[0],dp[h+1],0);
  REP(i,w){
    if(i==0) dp[0][i] = 1;
    else dp[0][i] = 0;
  }
  REP(i,h){
    REP(j,1<<(w-1)){
      bool ignore = false;
      REP(l,w-2){
        if(j>>l&1&&j>>(l+1)&1){
          ignore = true;
        }
      }
      if(!ignore){
        REP(l,w){
          if(l!=0&&j>>(l-1)&1) dp[i+1][l]+=dp[i][l-1];
          else if(l!=w-1&&j>>l&1) dp[i+1][l]+=dp[i][l+1];
          else dp[i+1][l]+=dp[i][l];
          dp[i+1][l] %= p;
        }
      }
    }
  }
  cout << dp[h][k-1] << endl;
  return 0;
}

雑感

なぜか今回は日曜開催で、参加できず。実は水色CoderになったのでいずれにせよUnratedだったのですが。
Dは難しいですね。

ハロウィーンなのでMacの背景をスクリプトから変更する

今日はハロウィーンですね。Bingの背景がこれになってました。

f:id:nexusuica:20181031190611j:plain

以前WindowsAndroidの背景をBingの画像に設定するアプリを紹介したのですが、Macのアプリは有料でした。
nexusuica.hatenablog.jp
今回はBingの背景画像を取り込んで背景に設定するプログラムを自前で書いてみました。

流行りのPythonで実装

Bingの背景画像は以下のURLからjson形式でフェッチできます。

http://www.bing.com/HPImageArchive.aspx?format=js&idx=0&n=1

f:id:nexusuica:20181031193619p:plain

このjsonから画像のURL部分を取り出し、ファイルをローカルにダウンロードしたのち、AppleScriptMacのデスクトップの背景に設定します。実装はなんでもよかったのですがPythonでやってみました。

import json
import urllib.request
import subprocess
from os.path import join, expanduser

#ディレクトリを指定
dir = join(expanduser("~"), 'Documents/bing-wallpaper')

#画像をフェッチ
url = "http://www.bing.com/HPImageArchive.aspx?format=js&n=1"
response = urllib.request.urlopen(url)
content = json.loads(response.read().decode('utf8'))
print(content['images'][0]['url'])
image_url = "http://www.bing.com"+content['images'][0]['url']
date = content['images'][0]['fullstartdate']
print(image_url)
filename = date+".jpg"
filepath = join(dir, filename)
urllib.request.urlretrieve(image_url,"{0}".format(filepath))

#背景に設定
script = """/usr/bin/osascript<<END
tell application "System Events"
set picture of every desktop to POSIX file "%s"
end tell
END"""
subprocess.Popen(script%filepath,shell=True)

あとはこのスクリプトを定期的に実行させてやれば毎日画像が変わります。cronを設定してもよいのですが面倒だったのでBetterTouchToolでスリープ解除後に実行させるように設定しました。
nexusuica.hatenablog.jp

これで毎日背景に飽きません。Bingの画像は季節感もありますしクオリティが高いので良いですね。ハッピーハロウィーン

f:id:nexusuica:20181031192908j:plain

紅葉の谷川岳に登ってきた!

関東を代表する紅葉の名所

曇りや雨が続いていた10月でしたが、先週末は久しぶりにすっきりとした晴れ予報。これはどこかに行かねばという使命感から、谷川岳に行くことを決断しました。今まで行ったことがなく一度は行きたいと思っていたので、この紅葉の時期に行かないという選択肢はありませんでした。

ただ、世の中だいたい考えることは似通っているので、週末の谷川岳は大変な混雑になると予想できました。最も混雑すると言われる紅葉の時期の晴れた週末に、どれだけ混雑を避けて行けるか、綿密な作戦を練って向かいました。

越後湯沢に前泊

イカーで谷川岳に行く場合は、できるだけ朝早く出発すれば混雑は避けられます。ただ、マイカーだと往復とも運転しなければならないため、登山もするとなると負担が大きく躊躇してしまいます。一方で、公共交通機関のみを使って谷川岳に行くとなると選択肢がかなり狭まってきます。

谷川岳の登山口とロープウェーの駅は上越線土合駅から徒歩20分ほどのところにあり、水上駅上毛高原駅からバスも出ています。ただ、東京から順当に行って最も早く到着する乗り継ぎだと混雑は避けられないので、ここは裏をかいて新潟県から南下することにしました。越後湯沢駅周辺に宿泊し、始発の上り列車に乗ることで、土合駅には6:37、登山口には7時前に到着し、ロープウェーの営業開始とほぼ同時に到着することができます。今回は越後湯沢駅から徒歩5分ほどの温泉のある宿に素泊まりし、翌朝早く出発しました。

f:id:nexusuica:20181023124034j:plain
f:id:nexusuica:20181023124106j:plain
前泊からの上越線始発列車。E129系に乗るのは初。

ロープウェーで一気に登る!

土合駅からロープウェーの土合口駅までは徒歩20分ほど。到着した頃にはすでにチケットを買う長い列ができていました。もっと遅かったら大変なことになっていただろうな…と想像しつつ列に並ぶも、列の進みは速く意外とすぐにチケットを買ってロープウェーに乗ることができました。朝一番はロープウェーに乗るための列は全くできていませんでした。

ロープウェーに乗り込んで見下ろすと、朝日を浴びて色づいた木々がとても綺麗でした。

f:id:nexusuica:20181023124131j:plain

紅葉の斜面を空中散歩

天神尾根から山頂を目指す

谷川岳山頂を目指すルートとして最もポピュラーなのが、ロープウェーを降りてから天神尾根伝いに進むルート。まずはこのルートで素直に山頂に向かいました。かなり冷え込んでいたこともあり、木がは凍ってツルツルになっている部分があって怖かったです。「魔の山谷川岳、恐るべしです。初心者向けコースとはいえ途中に岩場もあり、ナメてかかってはいけません。

f:id:nexusuica:20181023124152j:plain

天神尾根は木道の区間も長い

f:id:nexusuica:20181023124232j:plain

途中の岩場は渋滞しがち

山頂の1つのトマノ耳まではロープウェイから2時間半程度が目安。山頂が近づくと高い樹木はなくなって徐々に視界が開けてきて、山肌の紅葉が目に入るようになってきます。

f:id:nexusuica:20181023124351j:plain

山頂付近は笹が多い

f:id:nexusuica:20181023124328j:plain

谷間の紅葉が美しい

f:id:nexusuica:20181023124454j:plain

浅間山方面は雲がかかっていた

山頂からは大絶景

谷川岳の山頂についた頃は雲ひとつない快晴。360度の大パノラマでした。

f:id:nexusuica:20181023124447j:plain
f:id:nexusuica:20181023124422j:plain
トマノ耳・オキノ耳

オキノ耳からは一ノ倉沢もよく見ることができ、特に紅葉が綺麗でした。

f:id:nexusuica:20181023124257j:plain

オキノ耳から見る一ノ倉沢の紅葉

オキノ耳からトマノ耳に戻る途中、急に雲の中に入って視界が悪くなるタイミングがありました。この日は天気自体は崩れませんでしたが、山の上はこのようなこともあるので油断できませんね。

f:id:nexusuica:20181023124415j:plain

かなり視界が悪くなることも

下山はスリリングな岩場

山頂からの帰り、本来はまたロープウェーに乗るつもりでしたが、時間的な余裕があったので西黒尾根から足で下山することに。ロープウェーができる前はメインで使われていた登山道ですが、急な岩場・鎖場があり、高度感があってかなりスリリングです。

f:id:nexusuica:20181023124337j:plain

急峻な西黒尾根を降りていく

f:id:nexusuica:20181023124305j:plain

滑りやすい一枚岩

山頂付近は急な岩場の連続でヒヤヒヤしっぱなし。上りよりも下りが怖いです。1時間ほどスリルに耐えきると、樹林帯に入ってひたすら進んでいきます。この樹林帯はちょうど紅葉が進んでいて気持ちが良かったです。

f:id:nexusuica:20181023124218j:plain

西黒尾根の樹林帯

家に帰るまでが山行です

西黒尾根を駆け下り、土合駅まで徒歩で戻ります。時刻は12:30。まだまだ時間は余裕です。

f:id:nexusuica:20181023124202j:plain

上越線のこの雰囲気がたまらなく好き

電車が来るまで少し時間があったので、「日本一のモグラ駅」として有名なこの土合駅モグラ具合を見ていくことにしました。土合駅の下り線のホームは地下のトンネルの中にあり、地上の改札からはなんと500段近くの階段を下っていかないと到着できません。エスカレータやエレベータはなく、頼れるのは自分の足だけです。登山の後に往復できる自信がなかったので、上から覗いて写真を撮ってみました。今度時間と体力に余裕があるときに階段を登ってみたいです。

なぜこんなことになっているのかというと、以前上越線が単線だったときは地上のホームを使っていたものの、複線化する際にトンネルを掘ったことで地下にホームを設けざるを得なくなったからです。上越線は貨物列車も多く走っている重要な幹線なので、複線化は絶対必要だったのだろうと思います。

f:id:nexusuica:20181023124122j:plain

土合駅の地下ホームへ至る階段。別世界のようだ
f:id:nexusuica:20181023124241j:plain
f:id:nexusuica:20181023124058j:plain
地上の駅舎と上り線ホーム

土合駅から水上駅までは電車で10分ほど。途中ループ線を通るのが見どころです。ループ線は途中の湯檜曽駅から見ることができました。

水上駅では時間つぶしも兼ねて昼食。駅前のそば屋「くぼ田」で舞茸天ぷらのそばを頂きました。舞茸はみなかみの特産で、サクサクに揚がっていて美味しかったです。

f:id:nexusuica:20181023124314j:plain

「くぼ田」の舞茸天ぷらそば

水上駅は最近は高崎駅からSLの運行があり、以前訪問したときと比べて駅が綺麗に整備されていました。ただ駅前はまだまだ寂しい感じがあるので、これから活性化していってほしいところです。

水上駅からは上越線吾妻線を乗り継ぎ、小野上温泉駅へ。ここで日帰り温泉「さちのゆ」に立ち寄りました。

f:id:nexusuica:20181023124407j:plain

広々とした日帰り入浴施設。リーズナブルなのも良い

内風呂と露天風呂、サウナの3点を揃えた入浴施設で、410円ととてもリーズナブル。泉質は弱アルカリ性でお肌すべすべヌルヌルでした。特に露天風呂が開放的で好印象でした。日曜の夕方と一番混む時間帯でしたが、東京の芋洗い状態に比べればまだまだ余裕でした。

わざわざ吾妻線に乗って小野上温泉に行ったのには理由があります。それは、臨時列車「はちおうじやまどり」に乗車するためです。「はちおうじやまどり」は「リゾートやまどり」というゴージャスな車両で運転される全車指定の臨時快速列車で、吾妻線長野原草津口駅から高崎線武蔵野線・中央線を経由し八王子駅まで運転されます。乗車券に加えて520円の指定席券を買えば乗車できるので、特急やグリーン車よりもお得感があり、なにより運転日も限られているのでなかなか乗れません。ちょうど日程が合ったのでこの「はちおうじやまどり」に乗って東京まで戻ります。

f:id:nexusuica:20181023124439j:plain
f:id:nexusuica:20181023124019j:plain
車内は3列のシートでかなり広々

車内はすべて1+2列のシートで、シートピッチも非常に余裕がありました。新幹線のグリーン車よりも広かったと思います。列車内には小さな子供が遊べるプレイルームや畳のあるブースなどがあり、さらに運転席のすぐ後ろには展望スペースがあって運転士気分になれます。日曜日の夕方、マイカーであれば関越自動車道の地獄の渋滞にハマるところですが電車であればラクラク。群馬方面の外出であればまた活用したいと思いました。

この旅の締めは、立川駅駅ナカの焼きそばでした。久しぶりに行ったのですが、ここの焼きそばが美味しいのです。

f:id:nexusuica:20181023124112j:plain

疲れた体には味の濃い焼きそば

というわけで2日間かけて谷川岳に登って、寄り道しながら帰ってきました。温泉に登山、鉄道に写真撮影と自分の趣味を完全に詰め込んだ、ロマンあるものになったと思っています(笑)