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対応を作ることで期待値が簡単に求まってしまう場合があるんですね。

2018-09-10

Macを超カスタマイズできる「BetterTouchTool」

Mac ガジェット

何ができるの？

以前の記事では、MacBookを無料のソフトウェアのみを用いてカスタマイズしてみました。
nexusuica.hatenablog.jp
今回は「BetterTouchTool」という有料アプリでカスタマイズを一歩進めてみたというお話です。
「BetterTouchTool」は　トラックパッドやマウス、キーボード、トラックパッドの動作をカスタマイズできるソフトウェアで、「ある動作をしたら（トリガー）、この操作を実行する（アクション）」というような設定を非常に細かく行えます。例えば、「Commandキー+Optionキー+Cを押したら、Google Chromeを起動する」といったようなものです。

f:id:nexusuica:20180910222205p:plain — BetterTouchToolの設定画面。素っ気ないが詳細な設定が可能

BetterTouchToolは、トリガーの入力パターンが非常に多彩な上、アクションの種類も非常に豊富であるのが特長で、無料ソフトウェアにこれを追随するものはありません。特に、アクションとしてシェルスクリプトやApple Scriptの実行ができるのでかなり自由度が高いです（かなりコアなユーザー向けですが）。
僕はこのBetterTouchToolを用いて、Touch Barのヘビーカスタマイズをしてみました。

f:id:nexusuica:20180910221021j:plain — Touch Barのカスタマイズ例。想像力次第で何でもできる

このTouch Barのカスタマイズに関しては別の記事で紹介したいと思います。

購入方法

このBetterTouchToolですが、まずは購入する前に試用することが出来ます。公式サイトからダウンロードして起動すれば、45日間は無料ですべての機能を使用できます。その後、ライセンスを購入するかどうか判断できます。
https://folivora.ai
ライセンスを購入する場合、2年間のみアップデートが提供されるものと永久にアップデートを受けられるものがあります。記事執筆時点で前者が$6.50、後者が$20です。さすがに$20はちょっと高いので、2年間のアップデート付きライセンスですかね…。ただ実はこのライセンス、もっと安く買う方法が存在します。
App Storeで同じ開発者が販売しているアプリ「BetterSnapTool」（記事執筆時点で360円）を購入すると、なんと「BetterTouchTool」のライセンスをもらうことが出来ます。

BetterSnapTool

folivora.AI GmbH
Productivity
$2.99

というわけで、BetterSnapToolをApp Storeで購入すれば360円でBetterTouchToolが使えるというわけです。ちなみに、BetterSnapToolの機能であるウィンドウスナップ（ウィンドウを縦横に綺麗に分割して配置する機能）はBetterTouchToolに内蔵されているので、BetterSnapToolは購入後即アンインストールしても構いません。
Mac生活が確実に豊かになるBetterTouchTool、まずは試用してみて気に入ったら購入してみてはいかがでしょうか。

秘密の本棚

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

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個をランダムに取ってきたときの最小値の平均値

事の発端

せっかくなので一般化

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

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

Macを超カスタマイズできる「BetterTouchTool」

何ができるの？

購入方法