2018-09-24

山陰の小京都、津和野を巡る

旅行

経緯

先日山口県山口市で研究室の合宿があったのですが、そこからただ帰るのも芸がないので少し寄り道をしてきました。山口駅から山口線に乗り、島根県の西南端に位置する津和野町へ向かいました。キハ40系の鈍い加速を存分に楽しめます。

f:id:nexusuica:20180924221725j:plain — キハ40系。ラッピングもなくスッキリしている

沿線は最初は住宅街ですが、だんだんと田園になり、最後は県境の山を越えて津和野に滑り込みます。普通列車で1時間15分ほどの道のりです。ちなみに同じ区間を「SLやまぐち号」も走っていますが、所要時間は1時間40分です。ずいぶんとゆっくり走るんですね。

瑠璃光寺 五重塔

順番が前後するのですが、この前に山口市内で瑠璃光寺に行っていました。室町時代の大内氏の文化を伝える寺院で、特に五重塔は最高傑作とも評されているそうです。法隆寺、醍醐寺とともに日本三名塔のひとつともいわれています。

f:id:nexusuica:20180924221713j:plain — あいにくの雨だったが、木の艶が美しかった

この五重塔、夜はライトアップがされているようで、近くの湯田温泉からシャトルバスも出ているようでした。　また、地元の方が無料でガイドをしてくださるので、背景知識がなくても楽しめます。

この五重塔から少し歩いたところに、「うぐいす張りの石畳」というところがあります。

f:id:nexusuica:20180924221702j:plain — 一見普通の石畳だが、ここで手をたたくと…？

見た感じは普通の石畳なのですが、ちょうどこれを撮影しているあたりで手を叩いたり足踏みをしたりすると、どこからともなく「ギィン」という反響音が返ってきます。ちょっと不思議。

津和野駅

さて、話をもとに戻して列車で津和野へ。朝11:00頃到着しましたが、この頃はまだ駅のあたりは閑散としていました。

f:id:nexusuica:20180924221954j:plain — 人気がない小京都の駅前。

f:id:nexusuica:20180924221943j:plain — 人気がない小京都の駅前。

実はこの日は3連休の中日。この空き具合で津和野は大丈夫だろうかと勝手に心配しつつ、駅を出て右手にある観光案内所で地図をもらい、散策にでかけました。

しばらく歩くと殿町通りという、津和野を代表するスポットに到着します。この通りは古い町並みと水路を泳ぐコイが有名です。

f:id:nexusuica:20180924221934j:plain — 酒屋などが並ぶ殿町通り

f:id:nexusuica:20180924221736j:plain — 津和野といえばこの光景。赤や白の鯉が写真映えする

この通りには昔からある酒屋や屋敷のほか、お土産物屋やカフェも並んでいて、お昼時は賑わっていました。特にツアーで来ている年配の方が多かったですが、車で来たと思われる若者もいました。

太鼓谷稲成神社

殿町通りから山口線の鉄橋をくぐってしばらく歩くと、太鼓谷稲成神社の参道の入口に到着します。ここから千本鳥居を登っていきます。

f:id:nexusuica:20180924221848j:plain — この鉄橋も味があっていい…。

f:id:nexusuica:20180924221910j:plain — 千本鳥居。つづら折りになっている

太鼓谷稲成神社は1773年に京都の伏見稲荷から分霊を迎えてでき、今では島根県で出雲大社に次ぐ参拝者数（年間100万人）を誇っているそうです。登りきると本殿があります。本殿の近くには大きな駐車場があり、この千本鳥居を通らなくても本殿には行けてしまうのですが、せっかくなのでこの千本鳥居を登っていきたいですね。この千本鳥居は山の斜面にあるので、山口線の車内からもよく見えていました。

津和野城跡

太鼓谷稲成神社から少し歩くと観光リフトの乗り場があります。古そうで一人乗りなので不安になりますが、これより上に行くには乗るしかありません。

f:id:nexusuica:20180924221836j:plain — スリルは抜群のリフト

f:id:nexusuica:20180924231428j:plain — スリルは抜群のリフト

このリフトを降りてしばらく山道を登っていくと、津和野城跡に到着します。津和野城は江戸時代の津和野藩亀井氏の居城で、三本松城とも呼ばれていたそうです。津和野城の最大の特徴はその石垣で、最大で1つ2トンもある岩が使われています。

f:id:nexusuica:20180924221817j:plain — 立派な石垣が今も残る

津和野城は麓から高さ200mほどの高さにあるため、津和野の町並みが見渡せます。ちょうど田んぼには稲穂が実っている頃で、天気にも恵まれとても綺麗でした。よく見ると田んぼアートのSLがあります。

f:id:nexusuica:20180924221755j:plain — 眼下に広がる津和野の町

f:id:nexusuica:20180924221806j:plain — 眼下に広がる津和野の町

腹ごしらえ

昼食は殿町通り近くの「つるべ」といううどん屋でざるうどんをいただきました。のどごしがよく美味しかったです（写真を撮ったものの肝心のうどんにピントが合っていなかったので割愛）。

おやつには、津和野名物のお菓子である「源氏巻」。甘いあんこのペーストをカステラ生地で包んで焼いたもので、外はサクサク、中は柔らかい食感の和菓子です。こちらは殿町通りから太鼓谷稲成神社に行く途中にあったお店で購入。結構サイズが大きく、これだけでお腹いっぱいになりました（なんと写真を取り忘れたので割愛）。

津和野を出発する前には地元特産のゆずを使ったゆずソフトクリームを食べました。この日は暑かったのでゆずの酸っぱさがたまらなかったです。

まとめ

山陰の小京都、津和野をさっと巡りましたが、やはり小京都と言うだけあって3時間くらいあればだいたい見るべきところは見れるかなという印象でした。ただ、ここ独特の文化と見どころがあり、十分に行く価値があるとは思います。萩からも近いので山陰を巡る際には立ち寄っても良いのではないでしょうか。

ちなみに、津和野から東京へは萩・石見空港の利用が便利でした。羽田に一日2往復、ANAで快適な空の旅です。

2018-09-24

AtCoder Beginner Contest 110

AtCoder プログラミング

AtCoder Beginner Contest 110 - AtCoder

A - Maximize the Formula

問題

A - Maximize the Formula

考察

与えられた3つの1桁の数字を順不同に $l,m,n$ とするとき、 $10l+m+m$ の最大値を求める。結局 $l$ に何が入るかを場合分けすれば、取りうる値はたかだか3通りなのですべて調べればよい。

コード

int main(){
  int a,b,c;
  cin >> a >> b >> c;
  int ans = max(max(a*10+b+c,a+b*10+c),a+b+c*10);
  cout << ans << endl;
  return 0;
}

B - 1 Dimensional World's Tale

問題

B - 1 Dimensional World's Tale

考察

A帝国の首都とその支配に置きたい都市、およびB帝国の首都とその支配に置きたい都市が数直線上でオーバーラップしていないかどうかを判定すればよい。前者の座標の最大値と後者の座標の最小値を比較することで判定ができる。

コード

int main(){
  int n,m,x,y;
  cin >> n >> m >> x >> y;
  int x_max = x;
  REP(i,n){
    int xi;
    cin >> xi;
    x_max = max(x_max,xi);
  }
  int y_min = y;
  REP(i,m){
    int yi;
    cin >> yi;
    y_min = min(y_min,yi);
  }
  if(x_max<y_min){
    cout << "No War" << endl;
  }else{
    cout << "War" << endl;
  }
  return 0;
}

C - String Transformation

問題

C - String Transformation

考察

長さが等しい2つの文字列 $S$ と $T$ が、文字の入れ替え（「いっぱい」を「おっぱお」にするような入れ替え）によって変換できるかどうかを答える。これは、 $S$ の中で同じ文字は $T$ で同じ文字に対応し、 $S$ の中で違う文字は $T$ で違う文字になっているかどうかと同値である。よって、2つの文字列の各文字について「その文字が最初に出てくるその文字列内の場所」を計算しておき、比較すれば、判定ができる。

コード

int main(){
  str s,t;
  cin >> s >> t;
  int n = s.length();
  map<char,int> mp_s;
  int group_s[n];
  REP(i,n){
    if(mp_s[s[i]]==0){
      mp_s[s[i]]=i+1;
    }
    group_s[i]=mp_s[s[i]];
  }
  map<char,int> mp_t;
  int group_t[n];
  REP(i,n){
    if(mp_t[t[i]]==0){
      mp_t[t[i]]=i+1;
    }
    group_t[i] = mp_t[t[i]];
  }
  REP(i,n){
    if(group_s[i]!=group_t[i]){
      cout << "No" << endl;
      return 0;
    }
  }
  cout << "Yes" << endl;
  return 0;
}

D - Factorization

問題

D - Factorization

考察

かけて $M$ になるような $N$ 個の数のパターンの数を求める（ただし $10^9+7$ で割った余り）。とりあえず $M$ を素因数分解し、ある素数 $p$ について $a$ 乗となっているとき、この $a$ 個の $p$ を $N$ 個のグループに分割する方法は ${}_{a+N-1}C_{a}$ 通りある。これをすべての素数に関して計算して積を取ればよい。
ただし、組み合わせを計算するときはオーバーフローに注意する必要がある。 $p<30,\,n\leq 10^5$ より、 ${}_{a+N-1}C_{a}$ はlong long型でも容易にオーバーフローすることがわかるので、組み合わせを $10^9+7\equiv P$ で割ったあまりを工夫して求める必要がある。まず、
　 $\displaystyle {}_{a+N-1}C_{a}=\frac{(a+N-1)(a+N-2)\cdots N}{a\cdot (a-1)\cdot\cdots\cdot 1}$
と変形し、分子と分母を $P$ で割った余りを計算しておく。そして、「分母で割る」ことと「ある整数をかける」ことが等価となる整数（ $\mod P$ における逆元）を求め、分子にその整数をかけることによって組み合わせを $P$ で割った余りを求める。
逆元の求め方は蟻本の4-1章に記載があるほか、Web上にも資料がある。
http://hos.ac/slides/20130319_enumeration.pdf

コード

map<ll,ll> prime_factor(ll n){
  map<ll,ll> res;
  for(ll i = 2; i * i <= n; i++){
    while(n%i==0){
      ++res[i];
      n/=i;
    }
  }
  if(n!=1) res[n] = 1;
  return res;
}

const ll p = 1000000007;
ll extgcd(ll a, ll b, ll& x, ll& y){
  int d = a;
  if(b!=0){
    d = extgcd(b,a%b, y, x);
    y -= (a/b)*x;
  }else{
    x = 1; y = 0;
  }
  return d;
}
ll mod_inv(ll n){
  ll x,y;
  extgcd(n,p,x,y);
  return (p+x%p)%p;
}

int main(){
  ll n,m;
  cin >> n >> m;
  map<ll,ll> factor = prime_factor(m);

  ll ans = 1;
  for(auto b : factor){
    int x = b.second;
    ll num = 1, den = 1;
    REP(i,x){
      num = num * (x+n-1-i) % p;
      den = den * (x-i) % p;
    }
    ans *= num*mod_inv(den)%p;
    ans = ans % p;
  }
  cout << ans << endl;
  return 0;
}

雑感

今週も用事で参加できず。休日の夜は参加しづらいです。
Dは逆元やらなにやら調べていたらかなり時間がかかりました。

2018-09-12

Touch Barでメールの未読を通知する

Mac プログラミングガジェット

Dockを消したい

MacOSには下部にはDockという、起動中のアプリケーションを表示しておく場所があります。

f:id:nexusuica:20180912143915p:plain — Dock。通知のバッジも表示される

各アプリケーションのアイコンの右上には、通知がある場合にその数が赤い丸で表示されます。一目で通知があるかを確認できるので、結構便利です。
ただ、Dockは下部のスペースを占領してしまって邪魔なので、隠したいというのは本当のところ。しかしそうすると、この通知のバッジも見られなくなってしまうのでメールが来ているかどうかを一目で確認することができません。そこで今回は、Touch Bar上に未読メールがあるかどうかを表示させるようにしてみたいと思います。

未読メールがあるかどうかをチェックする

MacOSで未読メールがあるかどうかを判断する方法として、以下の2つがあります。

デフォルトのメールアプリMail.appから未読メール数を取得する
メールサーバから未読メール数を取得する

前者はオフラインでも実行できるところが優れています。ただ、Mail.appから直接未読数を取得することができないため、メールを一通ずつ取得して未読かどうかを判断し、それをカウントすることになります。コードは以下のとおりです。

tell application "Mail"
	set unread to 0
	repeat with msg in messages in inbox
		if msg's read status is not true then
			set unread to unread + 1
		end if
	end repeat
end tell
return unread

やっていることは単純で、メールボックスのメールをすべて取り出して、ループで回しています。想像はつくと思いますが、これを実行するのにはかなり時間がかかり、システムの負担も大きいです。これでは常駐させるにはあまりにも向いていないため、メールサーバにアクセスする方法を取ることにしました。
僕はメインでGmailを使っているのですが、Gmailには未読メールを簡単に取得できるURLが存在します。URLにアクセスし、ユーザ名とパスワードを入力することで、未読メール数と各メールの概要をXML形式で取得することができます。fullcountというところを読めば、未読メールがいくつあるかを取得できます。

https://mail.google.com/gmail/feed/atom

<feed xmlns="http://purl.org/atom/ns#" version="0.3">
<title>Gmail - Inbox for <メールアドレス></title>
<tagline>New messages in your Gmail Inbox</tagline>
<fullcount>1</fullcount>
<link rel="alternate" href="https://mail.google.com/mail" type="text/html"/>
<modified>2018-09-12T05:54:12Z</modified>
<entry>
<title>テスト</title>
<summary>本文です。</summary>
...
</entry>
</feed>

これを利用して、以下のスクリプトを書きました。

set xml_data to do shell script "curl -u \"<ユーザ名>\":\"<パスワード>\" --silent \"https://mail.google.com/mail/feed/atom\""
tell application "System Events"
	set xml_data to make new XML data with data xml_data
	set unread to xml_data's XML element "feed"'s XML element "fullcount"'s value
end tell
return unread

まずシェルスクリプトで先ほどのURLにアクセスしてXMLを受け取り、それをMacOSのSystem Eventsでパースし、タグを読むことで未読数を取得します。これで準備は完了です。

BetterTouchToolでウィジェットを作成

あとはこのスクリプトを組み込んだウィジェットをBetterTouchToolで作成します。
nexusuica.hatenablog.jp
定期的に上のスクリプトを実行し、実行結果が1以上であればアイコンと背景色を変更するようにしておきます（「Run Apple Script and Shown Return Value」）。また、アイコンをタッチするとMail.appが起動するようにしておきます（Action）。作成したものがこちら。

f:id:nexusuica:20180912150209j:plain — 未読メールの有無に応じて色とアイコンが変わる。必要に応じて未読数を表示することも容易。

f:id:nexusuica:20180912150212j:plain — 未読メールの有無に応じて色とアイコンが変わる。必要に応じて未読数を表示することも容易。

これでDockを隠しておいたとしてもメールに気付かないということがなくなります。Touch Barも便利なものですね。

2018-09-11

1,2,...,nからm個をランダムに取ってきたときの最小値の平均値

数学

事の発端

事の発端は、塾で教えている生徒から来た、ある問題に関する質問でした。

　 $100$ 個の数字 $1,2,\cdots\cdots,100$ から $3$ 個の数を任意に選んだとき、最小の数の平均値はいくつか。

僕がすぐに考えた解法は、期待値の定義どおり、ある数 $k$ が最小の数となる確率を求めて $k$ との積を取り、和を取る方法です。ただ、これをやってみると…

いま、1から100のうち、最小の数となりうるのは1から98である。この範囲のある整数を $k$ とおき、最小の数が $k$ となる確率を求めると、最小でない残り2枚を $k+1$ 以上 $100$ 以下の数から選ぶ確率なので $\displaystyle \frac{{}_{100-k}C_2}{{}_{100}C_3}$ である。よって求める期待値は
　 $\displaystyle E[k]=\frac1{{}_{100}C_3} \displaystyle \sum_{k=1}^{98}k\ {}_{100-k}C_2$
となる。

$\sum$ の中は $k$ の3次式なので手計算は一応可能で、実際に計算すると $\displaystyle \frac{101}4$ となります。ただ、この問題がもともと穴埋め式の問題だったことと、最後の答えが綺麗に $\displaystyle \frac{100+1}{3+1}$ になっていたので、何かもっと綺麗な解法があるのではないかとTwitterに助けを求めました。すると、非常に様々な解法が寄せられました。 togetter.com

最終的にこれだ、というものがあったので、その解法と地道に計算する方法、2通りの解法を紹介します。

せっかくなので一般化

先ほどの問題だと具体的すぎるので、ここから先は一般化して次の問題を考えます。

　 $n$ 個の数字 $1,2,\cdots\cdots,n$ から $m$ 個の数を任意に選んだとき、最小の数の平均値はいくつか（ただし、 $n\geq m$ とする）。

コンビネーションをガリ ガリ計算する方法

まずは先ほどと同様に定義どおり計算します。最小の数となりうる整数 $k$ について、最小の数が $k$ となる確率は、最小でない残り $m-1$ 枚を $k+1$ 以上 $n$ 以下の $n-k$ 枚から選ぶ確率なので $\displaystyle \frac{{}_{n-k}C_{m-1}}{{}_{n}C_{m}}$ となります。これを用いて期待値は
　 ${ \begin{align} E[k]&=\frac1{{}_nC_m}\sum_{k=1}^{n-m+1}k\ {}_{n-k}C_{m-1}\\ &=\frac1{{}_nC_m}\sum_{k=1}^{n-m+1}\{(n+1)-(n-k+1)\}{}_{n-k}C_{m-1}\\ \end{align} }$
と立式できます。ここで、
　 ${ \begin{align} (n-k+1){}_{n-k}C_{m-1}&=(n-k+1)\ \frac{(n-k)!}{(m-1)!(n-k-m+1)!}\\ &=m\ \frac{(n-k+1)!}{m!(n-k-m+1)!}\\ &=m\ {}_{n-k+1}C_{m} \end{align} }$
を用いることで、上の期待値は
　 $\displaystyle E[k]=\frac1{{}_nC_m} \sum_{k=1}^{n-m+1}\{ (n+1)\ {}_{n-k}C_{m-1}-m\ {}_{n-k+1}C_m \}$
と書き直すことができます。さてここでいったん、 $\displaystyle \sum_{i=k}^l{}_iC_k$ を考えます。二項係数の性質
　 ${}_iC_k+{}_iC_{k+1}={}_{i+1}C_{k+1},\ {}_kC_k={}_{k+1}C_{k+1}=1$
を繰り返し用いれば、
　 $\displaystyle{ \begin{align} \sum_{i=k}^l{}_iC_k &= {}_kC_k+{}_{k+1}C_k+{}_{k+2}C_k+{}_{k+3}C_k+\cdots+{}_lC_k\\ &= {}_{k+1}C_{k+1}+{}_{k+1}C_k+{}_{k+2}C_k+{}_{k+3}C_k+\cdots+{}_lC_k\\ &= {}_{k+2}C_{k+1}+{}_{k+2}C_k+{}_{k+3}C_k+\cdots+{}_lC_k\\ &= {}_{k+3}C_{k+1}+{}_{k+3}C_k+\cdots+{}_lC_k\\ &= {}_lC_{k+1}+{}_lC_k\\ &= {}_{l+1}C_{k+1} \end{align} }$
となることがわかります。これを $E[k]$ の $\sum$ の第1項には $k=m-1,\,l=n-1$ として、第2項には $k=m,\,l=n$ として代入することで、
　 $\displaystyle { \begin{align} E[k]&=\frac1{{}_nC_m}\{(n+1)\,{}_nC_m-m\,{}_{n+1}C_{m+1}\}\\ &=n+1-m\,\frac{{}_{n+1}C_{m+1}}{{}_nC_m}\\ &=(n+1)\left(1-\frac{m}{m+1}\right)\\ &=\frac{n+1}{m+1} \end{align}}$
が導出できました（ふう……）。

もっとエレガントに解く方法

さすがに二項係数の計算は疲れます。もっと直感的な解法はないのでしょうか。もう一度問題を見てみましょう。

　 $n$ 個の数字 $1,2,\cdots\cdots,n$ から $m$ 個の数を任意に選んだとき、最小の数の平均値はいくつか（ただし、 $n\geq m$ とする）。

いま、適当に選ばれた $m$ 個の数字を小さい順に $x_1,x_2,\cdots\cdots,x_m$ とします（ただし、 $x_1\geq 1,\,x_{i+1}\geq x_i+1,\, x_m\leq n$ ）。
いま、これらの差に着目して $m+1$ 個の数字 $y$ を、
　 $y_1= x_1,\ y_i=x_i-x_{i-1}\,(2\leq i\leq m),\ y_{m+1}=n+1-x_m$
によって定めます。このとき、 $(x_1,x_2,\cdots\cdots,x_m)$ と $(y_1,y_2\cdots\cdots,y_{m+1})$ は1対1に対応します。
　 $y_1+y_2+\cdots\cdots+y_{m+1}=n+1$
が常に成立すること、および最小値 $x_1=y_1$ に注意すると、以下のように問題が言い換えられることがわかります。

　 $y_1+y_2+\cdots\cdots+y_{m+1}=n+1$ が成り立つように $m+1$ 個の自然数 $y_1,y_2,\cdots\cdots,y_{m+1}$ を任意に選んだとき、 $y_1$ の平均値はいくつか。

すると、すべての $y_i$ は対称的な条件なので平均値は等しくなり、
　 $\displaystyle E[y_1]=\frac{n+1}{m+1}$
となることが容易にわかります。なんと……。
このように、適当な1対1対応を作ることで期待値が簡単に求まってしまう場合があるんですね。

秘密の本棚

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

山陰の小京都、津和野を巡る

経緯

瑠璃光寺 五重塔

津和野駅

太鼓谷稲成神社

津和野城跡

腹ごしらえ

まとめ

AtCoder Beginner Contest 110

A - Maximize the Formula

問題

考察

コード

B - 1 Dimensional World's Tale

問題

考察

コード

C - String Transformation

問題

考察

コード

D - Factorization

問題

考察

コード

雑感

Touch Barでメールの未読を通知する

Dockを消したい

未読メールがあるかどうかをチェックする

BetterTouchToolでウィジェットを作成

1,2,...,nからm個をランダムに取ってきたときの最小値の平均値

事の発端

せっかくなので一般化

コンビネーションをガリ ガリ計算する方法

もっとエレガントに解く方法