いものやま。

雑多な知識の寄せ集め

なぜ仕様変更は納期直前にやってくるのか。

f:id:yamaimo0625:20200614154529j:plain

ITちびまる子ちゃん

Twitterで「#ITちびまる子ちゃん」というタグが流行ってて、これがなかなか面白い。

こんな時事ネタもw

いろいろ眺めてたんだけど、目についたのが次のツイート:

まさにあるあるネタw

「水の上を歩くことと、仕様書からソフトウェアを開発することは簡単だ。どちらも凍結してさえいれば」というジョークが示す通り、ソフトウェア開発が大変なのは仕様が固まってないからとも言える。

仕様変更のタイミングの謎

さて、これを単なるあるあるネタで済ましてしまうのもいいんだけど、あるあるネタということは、みんな同じ悩みを持っているということ。
なので、ちょっと冷静に考えてみたい。

なんで仕様変更は納期直前にやってくるんだろう?

ここでポイントになるのは、「納期直前に」というところ。
これがせめてもっと早い時期にやってきたのなら、まだ対処のしようもあったかもしれない。
けど、現実はそうではないので、凄惨なデスマーチへと進むことになったりする。

はてさて、なんで納期直前にこんなことになるのか。

プログラマならここで、原因を突き止めるために「差分は何なのか」を考えるはず。
何か差分があるからこそ、違いは生まれてくる。

では、納期直前とそうでないときとの差分は何なのか?

動くソフトウェア

そう、差分を考えると、それは「動くソフトウェアがあるかどうか」

要件定義や設計のときは、当然動くソフトウェアはない。
実装中も、ソフトウェアはまだユーザが使える状態ではない。
システムテストに入って、ようやく動くソフトウェアに触れることが出来るようになって、不具合なのかどうかもあやしい挙動が見つかったり、お客さんが実際に触ってみて感触を確かめることが出来るようになる。

で、そうやって動くソフトウェアに触れるようになって初めて「想定してなかったこと」が見つかったり、「使い勝手がいまいちだね」ということが分かったりする。

すると、システムテストも終盤で、いよいよリリースだねという納期直前になって、「ここは想定してなかったけどこういう動きにして」とか「ここは使い勝手がいまいちだから仕様を変えて」という仕様変更が襲いかかってくることになる。。。

よくよく考えれば、動くソフトウェアがなければ仕様変更なんか基本的にはないし、あったとしてもまだ作ってないんだから手間は変わらない。
動くソフトウェアが実際にあるからこそ、仕様変更は生まれてくる。
そして、動くソフトウェアが出来上がるのがシステムテストに入ってからなら、仕様変更が納期直前になるのは必然とも言える。

どうすべきなのか

しかし、そう考えると、仕様変更が納期直前になるのは必然であり、避けようがないようにも思える。
何か対策はないのか?

まず考えられる対策は、「上流工程をよりしっかりやる」こと。
「凍結してさえいれば」という通り、もうどう考えても抜け漏れのない完璧な仕様を作れさえすれば、たしかに仕様変更もなく楽に開発ができる。

けど、じゃあ上流工程をしっかりやろうとしてないプロジェクトがあったかというと、そんなことはないわけで。
どのプロジェクトも上流工程をしっかりとやろうとしてきたはず。
それでも現実には抜け漏れがあったりするんだから、正直これは理想論でしかない。
凍結してりゃ、そりゃ水の上も歩けるかもしれないけど、現にどんなに頑張っても凍結しないんだから、「凍結してさえいれば」なんて真にならない命題には何の意味もない。

じゃあ、どうすればいいかというと、もうこれは「動くソフトウェア」を早く作るしない。
もちろん、全部入りのソフトウェアを早く作るなんていうのは無理だから、一部の機能に限定したソフトウェアを作ることになる。
そして、実際に触れてみれば、想定してなかったことや、実際の使い勝手が見えてくる。
それを踏まえてプロジェクトの早い段階で仕様変更を受容するようにすれば、余裕をもって対応できるようになる。

まぁ、とどのつまり、アジャイル開発になるわけだけど。

面白いのは、これはソフトウェアだからできる対処法だということで、たとえば家を作るときにこんな芸当はできない。
リビングだけまず作って、次にダイニングを作って、みたいなことは不可能で、まずはちゃんと全体を設計して、土台を作って、骨組みを作って、壁を作って、と順番に作っていくしかない。
けど、ソフトウェア開発はそんな制約に縛られる必要性はない。

プロジェクトのすべての成果物を同期させることには累積効果があるので、先へ進むほど変更のコストが飛躍的に上昇します。
(中略)
少し調べてみると、その曲線が土木工学に端を発することがわかります。
(中略)
しかし、これらのルールがソフトウェア開発に当てはまるのは、私たちがそうさせたからにほかなりません。
ソフトウェアは、ソフトと呼ばれるだけあって、柔軟にできています。
ソフトウェアは容易に変更できるはずなので、正しい手法とよい道具さえあれば、非常に融通の利くものとなります。
ですから、土木工学のたとえを用いてソフトウェアを鉄筋とコンクリートになぞらえると、自分で自分の首を絞めることになります。
(『The RSpec Book』より引用)

この指摘は非常に面白くて、つまりソフトは他にも柔軟な開発方法があるだろうに、わざわざ後になるほど変更のコストが高くなる建築と同じように作れば、そりゃ後工程の変更コストがバカ高くなるのは当然よね、と。

なので、やっぱりいにしえの開発手法に縛られているのではなく、より柔軟な開発手法にシフトしていかないといけないんだろうなぁ。

今日はここまで!

『Python実践データ分析100本ノック』を読んでみた。

f:id:yamaimo0625:20190203131318j:plain

Python実践データ分析100本ノック』がいい本だったので、紹介したい。

概要

この本は、実務で実際にありそうなシーンを対象として、どういったことを考え、そして分析していけばいいのかを取り扱ってる。

各項目は100本ノックという形で実際に手を動かしながら学べるようになっているので、テンポよく進められた。

具体的には、1章から10章まであり、各10本ずつノックが用意されている。
以下ではどんな内容があったのかを説明したい。

基礎編:データ加工

1、2章は基礎編で、データ加工について。

これらの章はけっこう重要で、実際にKaggleのコンペなんか見てみると分かるとおり、現実のデータってかなり汚い。
欠損値があったり、揺れがあったり。
あるいは、分析に適した形になっていなかったり。
そういう汚いデータを、実際に手を動かしながら整えていく経験をすることができる。

機械学習の入門書はいろいろ読んでるけど、概要の説明こそあれ、実例を使って試していくのはなかなか書かれていないので、勉強になった。

実践編1:機械学習

3〜5章では、機械学習を使って予測モデルを作っていく。

といっても、やるのは大部分がデータの整理。
結局、機械学習アルゴリズムを使う部分はライブラリを叩いてポンなんで、それまでが重要ということ。

第2部で紹介したケースはオーソドックスなものですが、思ったより機械学習モデルの構築までの道のりが長いと感じたのではないでしょうか。 実際の現場では、綺麗なデータが用意されていることはほとんどなく、多くのデータ加工とプレ分析が待ち構えています。
(『Python実践データ分析100本ノック』5章より引用)

実際に手を動かしてみると、このことを身をもって理解できると思う。

実践編2:最適化問題

この本は面白いことに、6〜8章では最適化問題を扱ってる。

部品工場から組み立て工場への輸送などをテーマとして考えていて、(グラフ理論の)グラフを描くためのライブラリであるNetworkXを使ったり、(線形計画問題になるので)線形計画問題を解くためのライブラリであるPuLPを使ったりする。
あと、口コミが広がっていく様子をシミュレーションしたりも。
機械学習の本では見ない内容だったので、面白かった。

ちょっとだけ難点を挙げておくと、6〜8章を書いた人はおそらくPythonに不慣れで、コードがかなりPythonっぽくない。
まぁ、それをPythonっぽいコードにするのも、いい練習になるかもしれないけど。

発展編:画像処理、言語処理

9、10章では、発展的な内容ということで、画像処理と言語処理を扱ってる。

これもけっこう他の本とは違って、画像処理は深層学習を使うとかではなく、OpenCVを使っている。
それと、言語処理は形態素解析のライブラリであるMeCabを扱ってる。
これらのライブラリも使ったことがなかったので、いい勉強になった。

PythonやNumPy、Pandasの入門書ではない

一つ気をつけたいこととして、この本はPythonやNumPy、Pandasの入門書ではないということ。

Pythonの文法も知らないような人がこの本を見ても、さっぱり分からないので、そういう人はPythonのチュートリアルや入門書を読んでからの方がいい。

また、NumPyやPandasをほとんど知らない状態でこの本を読むのも、なかなか大変だと思う。
もちろん、使われてる関数を逐次調べれば読めると思うけど、あまりオススメできない・・・

むしろ、NumPyやPandasを扱ってる入門書とかを読んでみて、ある程度理解しても、実際にそれでデータ分析してみようとすると、途端に困ってしまうことが多いので、そういうタイミングで読むととてもいいと思う。

NumPyやPandasを扱ってるもので、自分がかなりマシだと思った本は、『Python Data Science Handbook』(邦題『Pythonデータサイエンスハンドブック』)。
(正直「これだ!」という本に出会ってない・・・PythonやNumPy、Pandas、あるいはMatplotlibのデザインがゴミまみれなのが原因な気もする)

Python Data Science Handbook: Essential Tools for Working with Data

Python Data Science Handbook: Essential Tools for Working with Data

これは原稿がGitHubで公開されてるので、GitHubでそのまま読むこともできるし、cloneしてきてJupyter Notebookで読むこともできる。

コードの質

もう一つ気をつけたいこととして、マシな方だとは思うけど、コードの質はそこまで高くない。

groupby()の利用

これはこの本に限らないんだけど、まず思うのは、分かりにくいgroupby()を使うんじゃなくて、pivot_table()を使った方がいいということ。
ピボットテーブル作った方が、何をやってるのかが一発で分かる。

たとえば、ノック8でgroupby()を使った次のようなコードがあった:

join_data.groupby('payment_month').sum()['price']

意味は「payment_month列の各値ごとにテーブルを分割して、各テーブルの各列をsum()で合計してから(これで1行のレコードになる)分割したテーブルを再結合して、price列だけ抜き出す」というもの。
この「分割→処理→結合」という思考はややこしいし、コードもパッと見で何をやってるか分かりにくい。

ついでに言えば、

join_data.groupby('payment_month')['price'].sum()

とした方が余分な計算がされなくなるので早くなる。
(KaggleのNotebookで%timeを使って測ると、前者が約9ms、後者は約5msだった)

けど、そもそもこれはピボットテーブル使って

join_data.pivot_table(index='payment_month', values='price', aggfunc=sum)

と書いた方が分かりやすい。
意味は「payment_month列の各値ごとにprice列の値の合計の表を作る」と明快。
%timeで時間を測ると、約11msでgroupby()より少し遅いという問題はあった)

あるいは、ノック25だと、顧客と月ごとの利用回数をgroupby()で次のように集計している:

uselog_months = uselog.groupby(["年月","customer_id"],as_index=False).count()
uselog_months.rename(columns={"log_id":"count"}, inplace=True)
del uselog_months["usedate"]

いや、パッと見でイミフでしょ。

pivot_table()を使えばもっとシンプルになる:

uselog_months = uselog.pivot_table(index='customer_id', columns='年月', aggfunc='size', fill_value=0)

なお、groupby()とは違う表になるけど、分析にはピボットテーブルの表の方が圧倒的に見やすいと思う。
もしgroupby()と同じ表にしたいなら、melt()を使うといい。

ちなみに、このあと顧客ごとの利用回数に関する集計をするんだけど、本だと

uselog_customer = uselog_months.groupby("customer_id").agg(["mean", "median", "max", "min" ])["count"]
uselog_customer = uselog_customer.reset_index(drop=False)
uselog_customer.head()

とまたgroupby()を使ってるのに対し、ピボットテーブルにした自分のコードなら、

uselog_customer = pd.DataFrame({
    'mean': uselog_months.mean(axis=1),
    'median': uselog_months.median(axis=1),
    'max': uselog_months.max(axis=1),
    'min': uselog_months.min(axis=1),
}).reset_index() # customer_idを列に戻しておく

と、各行について集計をすればいいだけなので、分かりやすい。

他にも、けっこうドッタンバッタンしてるコードがいるので、そういう部分はリファクタリングを考えながら進めるといいかも。

SettingWithCopyWarningが出る

コードを試していると、SettingWithCopyWarningという警告が出ることがあった。
けど、本では言及なし・・・(警告を抑制してる? それとも単に無視してる?)

これは何かというと、Pandasは列や行を抽出したときに、実体を返すかビューを返すかが曖昧なときがあり、そういった実体かビューかが曖昧なオブジェクトに対して実体を更新する処理をすると出る警告っぽい。
大抵は問題ないっぽいけど、どの実体が更新されるのか曖昧で、ちょっと危ないところがある。

実際に警告が出た一例は、ノック32。

# クラスタリングで得られたラベルの列を追加
customer_clustering['cluster'] = clusters.labels_ # ここで警告が出た

パッと見だとなんでこれでSettingWithCopyWarningが出るのか分からないんだけど、原因はずっと前にあった:

features = ['mean', 'median', 'max', 'min', 'membership_period']
customer_clustering = customer[features] # ここで列を抽出してる!

...

customer_clustering['cluster'] = clusters.labels_ # ここで警告が出た

原因がずっと前の方にあるので、気付きにくい。。。
これは明示的にコピーしておくと警告が出なくなった:

customer_clustering = customer[features].copy() # 実体が返されるので曖昧でなくなる

最適化問題を扱ってるコード

あと、前述の通り、最適化問題を扱ってるところのコードはけっこうアレなので、頑張って直した方がいい。

Kaggleで試すときの注意事項

実際に手を動かしながら読んだ方がいいので、KaggleでNotebookを作って試すのがオススメ。

ただし、9章、10章に関しては、ちょっと注意が必要だった。

9章の注意点

まず、9章では画像を表示するのにcv2.imshow()を使っているんだけど、これをKaggleのNotebooで実行すると、Notebookがリスタートする(^^;

この問題を解決するには、cv2.imshow()の代わりにMatplotlibのimshow()を使ってあげるといい:
(このとき、色をBGRからRGBに変換する必要がある)

img = cv2.imread('img01.jpg')

# 以下、エラーになる
# cv2.imshow('img', img)

# 代わりにplt.imshowで表示
img_rgb = cv2.cvtColor(img, cv2.COLOR_BGR2RGB)
fig, ax = plt.subplots(figsize=(15, 15))
ax.imshow(img_rgb);

あと、動画のキャプチャで、本ではcap.isOpened()で終了判定をしてるけど、これ、動画の最後に来てもFalseを返さないっぽい。
このせいで、動画の最後に来てるのにret, frame = cap.read()が呼ばれ、これが無限待ちになって処理が終わらなくなる。。。

これは代わりに総フレーム数を使うようにするといい:

cap = cv2.VideoCapture('mov01.avi')
count = cap.get(cv2.CAP_PROP_FRAME_COUNT)

# 以下、無限ループで終わらなくなる
# while cap.isOpened():
#     ...

# 総フレーム数を使う
for i in range(int(count)):
    ...

10章の注意点

10章の方は、MeCabのインストールがそれなりに大変。

以下のNotebookを参考にさせてもらった:

""" # インストールするときはこの行をコメントアウト
!mkdir mecab
%cd mecab
!apt install curl mecab libmecab-dev mecab-ipadic-utf8 file -y
!git clone --depth 1 https://github.com/neologd/mecab-ipadic-neologd.git
%cd mecab-ipadic-neologd
!bin/install-mecab-ipadic-neologd -n -a -y --prefix /var/lib/mecab/dic/mecab-ipadic-neologd
!sed -i -e 's@^dicdir.*$@dicdir = /var/lib/mecab/dic/mecab-ipadic-neologd@' /etc/mecabrc
!pip install mecab-python3
%cd ../..
"""; # インストールするときはこの行をコメントアウト

これでインストールできるはず。


そんな感じで、問題がまったくないわけではないけど、むしろその問題の解決も含めていい勉強になると思うので、オススメ。

今日はここまで!

ABC166を復習してみた。

f:id:yamaimo0625:20200420163532j:plain

ABC164、ABC165の復習がまだできてないんだけどABC166は簡単めだったので先に復習した。

A. A?C

場合分けして出力するだけ。

s = gets.chomp
puts (s == 'ABC') ? 'ARC' : 'ABC'

B. Trick or Treat

もらったお菓子の数を保持しておいて、最終的に0だった子の数を出すだけ。

n, k = gets.split.map(&:to_i)
count = Array.new(n, 0)
k.times do
  gets  # 使わない
  gets.split.map{|s| s.to_i - 1}.each{|i| count[i] += 1}
end
puts count.select{|i| i == 0}.size

C. Peaks

隣り合ってる展望台よりも高い展望台の数を数えるだけ。
以下のコードでは、隣り合ってる展望台の中で自分の高さ以上の展望台を探し、なければ自分が一番高いとしてる。

n, m = gets.split.map(&:to_i)
heights = gets.split.map(&:to_i)
adj = n.times.map{Array.new}
m.times do
  a, b = gets.split.map{|s| s.to_i - 1}
  adj[a].push b
  adj[b].push a
end

count = 0
n.times do |i|
  height = heights[i]
  higher = adj[i].select{|j| heights[j] >= height}
  count += 1 if higher.empty?
end

puts count

D. I hate Factorization

これが一番難しかった。

自分が考えたのは、 A^5 - B^5 = (A-B)(A^4 + A^3 B + A^2 B^2 + A B^3 + B^4)因数分解できるよなということ。
で、 X = KL K, L \in \mathbb{N}、一般性をなくすことなく K \le Lとしていい)と因数分解できるとして、  A-B \le A^4 + A^3 B + A^2 B^2 + A B^3 + B^4のはずだから(※ここ怪しいまま解いた)、  K=A-B, L= A^4 + A^3 B + A^2 B^2 + A B^3 + B^4となるはず。
で、たぶん L= A^4 + A^3 B + A^2 B^2 + A B^3 + B^4 \ge 0なので K= A-B > 0で(※ここも怪しいまま解いた)、 A-B >0となるには Aが正でないとダメ。(※これ間違い、結果的に正を仮定してもOKではあるんだけど)
そこで、 Kを決めれば Lが決まり、その状態で Aを決めれば Bが決まるので、あとは条件を満たすまでループ。
ここで、 Aを1から順に上げていくんだけど A^4 + A^3 B + A^2 B^2 + A B^3 + B^4は4乗の項が一番効くはずだから A^4 Lを超えたら次のループにいく(※これも論理的にかなり怪しい)とした。

コードにすると、以下:

x = gets.to_i

def calc(a, b)
  a**4 + a**3 * b + a**2 * b**2 + a * b**3 + b**4
end

(1..x).each do |k|
  next if x % k != 0
  l = x / k
  (1..l).each do |a|
    break if a**4 > l
    b = a - k
    if calc(a, b) == l
      puts "#{a} #{b}"
      exit(0)
    end
  end
end

論理はめちゃくちゃだったんだけど、運よく通ってしまった。。。

ここからは解説の内容。

まず、 f(n) = n^5という関数を考えると、これは単調増加する関数になってる。
なので、 a > b \Leftrightarrow f(a) > f(b)、すなわち、 a - b > 0 \Leftrightarrow f(a) - f(b) > 0
ここで、 X = A^5 - B^5 = f(A) - f(B) > 0なので、 A - B > 0ということが言える。
また、 A Bが離れるほど f(A) f(B)も離れるというのがポイント。

そして、 A Bも整数で A - B > 0なので、 A Bが一番近いのは A - B = 1のとき。
このとき、 X = f(A) - f(A-1) = A^5 - (A-1)^5なので、 X Aの関数と考えることができる。
この関数を g(A)とすると、 \ldots, g(-2), g(-1), g(0), g(1), g(2), \ldots = \ldots, 211, 31, 1, 1, 31, \ldotsと、 A=0, 1のときに最小値1をとって、負の方向もしくは正の方向に行くほど値が大きくなっていく。
ここで、 X \le 10^9なので、これを超えてしまう範囲の Aは解になりえない。
そして、ちょっとしたループを回して調べると、 g(120), g(-119) 10^9を超えることが分かる。
なので、 A-B=1のとき、 -118 \le A \le 119

じゃあ、 A-B=2のときはどうかというと、 A B A-B=1のときより離れてるので、 f(A) f(B)もより離れてることになるから、 h(A) = f(A) - f(A-2)としたときに、 h(A) > g(A)となる。
なので、 h(-119) > g(-119) > 10^9 h(120) > g(120) > 10^9となり、やはり -118 \le A \le 119を調べれば十分。
 A-B \ge 3についても同様。

で、今は X Aの関数と考えたけど、 Bの関数と考えても同様の議論ができて、 -119 \le B \le 118ということが分かる。

あとは、この全部の組み合わせについて A^5 - B^5を計算して、 Xに一致するものを見つければいい。
それぞれ約240通りだから、 240^2 = 57,600回くらいループ回せばOK。

コードは以下:

x = gets.to_i

(-118..119).each do |a|
  (-119..118).each do |b|
    value = a**5 - b**5
    if value == x
      puts "#{a} #{b}"
      exit(0)
    end
  end
end

E. This Message Will Self-Destruct in 5s

最初は普通にループ回してみて、当然のようにTLE。
そこで、アルゴリズムを考え直した。

これは、問題文では身長となってるけど、腕の長さと考えるとイメージしやすいなと思った。
つまり、 iさんは自分の位置から配列の上下に長さ A_iの腕を伸ばしていて、そこで握手することができたら、握手した人と条件を満たすことができる、という感じ。
(もう一人を jさんとすると、 iさんの手の位置は i + A_i jさんの手の位置は j - A_jで、これが一致しているのだから i + A_i = j - A_jとなっていて、 j-i = A_i + A_jとなる)

気をつけないといけないのは(というか最初間違えた)、上に伸ばした手同士で握手してもダメで、上に伸ばした手と下に伸ばした手で握手しないといけないということ。
なので、下に伸ばした手の位置と上に伸ばした手の位置は別個に持つ必要がある。

あとは各位置について、上に伸ばした手の数と下に伸ばした手の数の組み合わせだけ、条件を満たす人がいることになるので、それを数えればいい。

コードは以下:

n = gets.to_i
heights = gets.split.map(&:to_i)

low_connector = n.times.map{Array.new}
high_connector = n.times.map{Array.new}

n.times do |i|
  low_connect = i - heights[i]
  high_connect = i + heights[i]
  if low_connect >= 0
    low_connector[low_connect].push i
  end
  if high_connect < n
    high_connector[high_connect].push i
  end
end

count = 0
n.times.each do |i|
  lower = low_connector[i].size
  higher = high_connector[i].size
  count += lower * higher
end

puts count

F. Three Variables Game

ちょっと時間足りなくなって間に合わなかったけど、シンプルな深さ優先探索(DFS)書いたらサクッと通った:

N, A, B, C = gets.split.map(&:to_i)
Commands = N.times.map{gets.chomp}

def dfs(state, hist)
  a, b, c = state
  if (a < 0) or (b < 0) or (c < 0)
    return
  end

  level = hist.size
  if level == N
    puts 'Yes'
    hist.each{|s| puts(s)}
    exit(0)
  end

  command = Commands[level]
  case command
  when 'AB'
    hist.push 'A'
    bfs([a+1, b-1, c], hist)
    hist.pop
    hist.push 'B'
    bfs([a-1, b+1, c], hist)
    hist.pop
  when 'BC'
    hist.push 'B'
    bfs([a, b+1, c-1], hist)
    hist.pop
    hist.push 'C'
    bfs([a, b-1, c+1], hist)
    hist.pop
  when 'AC'
    hist.push 'A'
    bfs([a+1, b, c-1], hist)
    hist.pop
    hist.push 'C'
    bfs([a-1, b, c+1], hist)
    hist.pop
  end
end

dfs([A, B, C], [])
puts 'No'

A, B, Cのいずれかが0未満になったそこから先は調べられないのと、なんでもいいから1つ見つければいいので、かなりタフな例に当たらないと計算量が O(2^N)にならないのかも。
(ツリーを考えると最悪 O(2^N)になっててもおかしくないと思う)

今日はここまで!

ABC163を復習してみた。

f:id:yamaimo0625:20200420163532j:plain

最近、AtCoderに参戦してる。
これはアルゴリズム実技検定(PAST)を受けてみようと思ったのがキッカケ。

PASTの結果は63点でギリギリ中級だったんだけど、やはり経験値が足りてないなぁという感じ。

なので、ほぼ毎週開かれてるAtCoder Beginner Contest (通称ABC)をちゃんと復習して、経験値を高めていきたいと思う。

先週末に行われたABC163の復習をしてみる。

※なお、ABC163は開始直後にいろいろトラブルがあってレーティングはつかないことになった

A. Circle Pond

円の半径が与えられるので円周の長さを求めるだけ。

r = gets.to_i
puts 2 * Math::PI * r

B. Homework

宿題にかかる日数を合計して、夏休みの日数から引くだけ。
日数が足りない場合は-1を出力せよということなので、そういうときはmaxを使うのが数学のお約束パターン。

n = gets.split.map(&:to_i)[0]
total = gets.split.map(&:to_i).sum()
puts [n-total, -1].max

C. Management

 iさんが jさんの上司の場合(つまり A_j = iの場合)、 jさんは iさんの部下なのだから、 iさんの部下の数を1増やせばいい。
それを Aの先頭から調べていけばいいだけ。

n = gets.to_i
bosses = gets.split.map(&:to_i)

ans = Array.new(n+1,0) # 0はダミー
bosses.each do |boss|
  ans[boss] += 1
end

ans.shift # ダミーを削除
ans.each do |i|
  puts i
end

なお、インデックスを揃えるのが面倒だったので、答えの配列のサイズを一つ大きくして、そのままアクセスできるようにしてる。

このCまでは楽勝だったんだけど、Dで苦戦した・・・

D. Sum of Large Numbers

いろいろ考えて、自分が至ったのは次のような考え:

  1. まず、足す個数が違うときは、和は被らない。
    なので、足す個数がそれぞれ k, k+1, \ldots, n+1のときの和の数を求め、合計すればいい。
  2. 足す個数が i個のとき、一番小さい和は 0 + 1 + 2 + \cdots + (i-2) + (i-1)
    ここから一番最後の項を i-1, i, i+1, \ldots, n-1, nまで大きくしていける。
    これが n - (i-1) +1 = n- i +2通り。
    そしたら最後から2番目の項を i-1, i, i+1, \ldots, n-2, n-1まで大きくしていける。
    これが (n-1)-(i-1)+1=n-i+1通り。
    同様に最後から3番目の項、4番目の項、・・・、最初の項と大きくしていくと、それぞれ n-i+1通り。
    なので、 (n-i+2) + (n-i+1)(i-1)通り。

これをコードに落としたのが、以下:

n, k = gets.split.map(&:to_i)

total = 0
(k..(n+1)).each do |i|
  total += (n-i+2) + (n-i+1)*(i-1)
end

puts total % (10**9+7)

これは時間が足りなくて間に合わなかった。。。

解説読むと、この2.のところがもっとクリアに解決されてる。

まず、一番小さい和は 0+1+\cdots + (i-1)
そして、一番大きな和は (n-i+1)+(n-i+2)+\cdots+n
ここでポイントが、その間の任意の和は好きに作れるということ。
なので、一番小さい和を S_{\min}、一番大きな和を S_{\max}としたとき、

 \begin{align}
S_{\max} - S_{\min} + 1 &= \frac{1}{2} \left((n-i+1)+n \right) i - \frac{1}{2} \left(0 + (i-1)\right) i + 1 \\
&= \frac{1}{2}i(2n-i+1) - \frac{1}{2} i(i-1) + 1 \\
&= i (n-i+1) + 1
\end{align}

通りの和が作れる。

よって、以下のように書ける:

n, k = gets.split.map(&:to_i)

total = 0
(k..(n+1)).each do |i|
  total += i * (n - i + 1) + 1
end

puts total % (10**9+7)

E. Active Infants

活発度が大きい子ほど出来るだけ大きく動かした方がいいので、活発度の大きい子から順に、空きの左端もしくは右端(移動距離の大きくなる方)に移動させていけばいいだけではと思って、その単純な貪欲法を書いてみた。

n = gets.to_i
happy = gets.split.map(&:to_i)
happy.unshift 0 # ダミー

# happyが多い順にインデックスを並び替える
sorted_index = (1..n).sort_by{|i| -happy[i]}

total = 0
first = 1
last = n
sorted_index.each do |i|
  first_dist = (i - first).abs
  last_dist = (last - i).abs
  if first_dist > last_dist
    total += happy[i] * first_dist
    first += 1
  else
    total += happy[i] * last_dist
    last -= 1
  end
end

puts total

ただ、例で試したところ、例1はOKなものの、例2と例3は1足りない・・・
ということで、解けなかった。

どうやら、単に遠い方へ移動させるのだとダメなケースがあるっぽい?
なので、空きの左端に移動させた場合と右端に移動させた場合の両方について考える、動的計画法(DP)が必要とのことだった。

左側にleft人、右側にright人詰めたときの嬉しさの合計の最大値をhappysum[left][right]で表すことにする。
そうすると、その状態になるのは

  1. 左側にleft-1人、右側にright人いて、左側に1人移動させた場合
  2. 左側にleft人、右側にright-1人いて、右側に1人移動させた場合

のいずれか。
そして、直前の状態の嬉しさの最大値はそれぞれ参照できるので、それぞれの場合の嬉しさの合計を計算して、より高い方の値にすればいい、と。

ということで、あとで書き直したのが以下のコード:

n = gets.to_i
happy = gets.split.map(&:to_i)
happy.unshift 0 # ダミー

# happyが多い順にインデックスを並び替える
sorted_index = (1..n).sort_by{|i| -happy[i]}
sorted_index.unshift 0 # ダミー

# テーブルを0で初期化
happysum = (n+1).times.map do |left|  # leftは0, 1, ..., n
  Array.new(n-left, 0) # rightは0, 1, ..., n-left (left+right<=n)
end

# left=0固定
(1..n).each do |right|
  i = sorted_index[right]
  happysum[0][right] = happysum[0][right-1] + happy[i] * (n + 1 - right - i).abs
end

# right=0固定
(1..n).each do |left|
  i = sorted_index[left]
  happysum[left][0] = happysum[left-1][0] + happy[i] * (i - left).abs
end

max = [happysum[0][n], happysum[n][0]].max

# left != 0 かつ right != 0のとき
(1..n).each do |left|
  (1..(n-left)).each do |right|
    i = sorted_index[left+right]
    to_left = happysum[left-1][right] + happy[i] * (i - left).abs
    to_right = happysum[left][right-1] + happy[i] * (n + 1 - right - i).abs
    happysum[left][right] = [to_left, to_right].max
  end
  max = [max, happysum[left][n-left]].max
end

puts max

F. Path pass i

解説を読んだけど、まったく意味不明だったので、ACとってる他の人のコードで理解できそうなものを見つけて解読した。

参考にしたのは以下のコード:

根本的な考え方は、以下のようになる:

まず、サイズ nの木にあるパスの数は、

  1. 始点と終点が異なるものが \frac{1}{2}n(n-1)
  2. 始点と終点が同じものが n

なので、合計 \frac{1}{2}n(n-1) + n = \frac{1}{2}n(n+1)個になる。

そして、「色 cのノードを1回以上通るパスを求めよ」というのは逆に、「色 cを1回も通らないパスの数」を求めて、パスの総数から引けばいい。
(余事象の考え方と同じ)

じゃあ、「色 cを1回も通らないパスの数」をどう求めればいいのか、となるけど、これは色 cのノードを木から取り除いて森にして、森に含まれるパスの数を求めればいい。
その森には色 cのノードがないのだから、色 cを通るパスは存在していない。

これ森に含まれるパスの数は、色 cのノードを取り除いた森に含まれる各木同士は非連結なので、各木にあるパスの数を全部足し合わせれば求まる。

あとは、じゃあ色 cのノードを取り除いた各木のサイズをどうやって求めればいいかだけど、これは深さ優先探索(DFS)をやって、

  1. 今いるノードの色が cの場合、そこで木は切れるので、子を新しい探索のルートとして登録する
  2. 今いるノードの色が cでない場合、木はまだ連結してるので、子のサイズと自分自身を足し合わせる

とすることで求められる。

これをコードにしたのが以下:

class Tree
  def initialize(n, colors, edges)
    @n = n
    @colors = colors
    @adj = @n.times.map{Array.new}
    edges.each do |a, b|
      @adj[a].push b
      @adj[b].push a
    end

    # 計算用
    @cut_color = nil
    @root_queue = []
  end

  def get_answer
    total_path_count = all_path_count(@n)
    (1..@n).map do |color|
      tree_sizes = get_tree_sizes_for_cut_color(color)
      path_count_in_trees = tree_sizes.map{|tree_size| all_path_count(tree_size)}.sum()
      total_path_count - path_count_in_trees
    end
  end

  private

  # colorのノードを取り除いて木を森にしたとき、
  # 森に含まれる木のサイズのリストを得る
  def get_tree_sizes_for_cut_color(color)
    tree_sizes = []
    @cut_color = color
    @root_queue.push [0, -1]
    until @root_queue.empty?
      root, root_parent = @root_queue.shift
      tree_size = get_subtree_size(root, root_parent)
      tree_sizes.push tree_size if tree_size > 0
    end
    tree_sizes
  end

  # node以下の部分木のサイズを返す
  # (nodeが@cut_colorの場合、そこで木は切れるので、
  # 子を新しい木のルートとして登録する)
  def get_subtree_size(node, parent)
    size = 0
    if @colors[node] == @cut_color
      @adj[node].each do |child|
        if child != parent
          @root_queue.push [child, node]
        end
      end
    else
      size = 1 # 自分自身
      @adj[node].each do |child|
        if child != parent
          size += get_subtree_size(child, node)
        end
      end
    end
    size
  end

  # サイズnの木にあるパスの総数
  def all_path_count(n)
    n * (n + 1) / 2
  end
end

n = gets.to_i
colors = gets.split.map(&:to_i)
edges = (n-1).times.map{ gets.split.map{|e| e.to_i - 1} }

tree = Tree.new(n, colors, edges)
tree.get_answer.each do |i|
  puts i
end

これで論理的にはOKなんだけど、走らせるとTLE・・・

そこで、上記は各色について別々にループを回してるけど、これを並列していっぺんに行うことを考える。

具体的には、深さ優先探索をするときに、

  • ノードnode以下の部分木のサイズ
  • 各色について、その色を取り除いたときに、node以下の部分木でnodeから非連結になるノードの数

を返すようにする。
こうすると、nodeから連結してるノードの数は引き算をすれば求まる。

それをコードにしたのが以下:
(※参考にしたコードと等価なコード)

class Tree
  def initialize(n, colors, edges)
    @n = n
    @colors = colors
    @adj = @n.times.map{Array.new}
    edges.each do |a, b|
      @adj[a].push b
      @adj[b].push a
    end

    # 各色でのノードを取り除いて木を森にしたときに、
    # すでに訪問した木に含まれるパスの合計を累積して保持する
    @path_count_in_trees = Hash.new(0)
  end

  def get_answer
    total_path_count = all_path_count(@n)
    size, disconnected_node_sizes = get_subtree_info(0, -1)
    (1..@n).map do |color|
      tree_size = size - disconnected_node_sizes[color]
      @path_count_in_trees[color] += all_path_count(tree_size)
      total_path_count - @path_count_in_trees[color]
    end
  end

  private

  # node以下の部分木について、
  # - サイズ
  # - 各色を取り除いて非連結になるノードの数
  # を返す
  # (サイズ-各色を取り除いて非連結になるノードの数)が、
  # node以下の部分木でnodeから連結してる木のサイズ
  def get_subtree_info(node, parent)
    size = 1
    disconnected_node_sizes = Hash.new(0)

    node_color = @colors[node]
    @adj[node].each do |child|
      if child != parent
        sub_size, sub_disconnected_node_sizes = get_subtree_info(child, node)
        size += sub_size

        # node_colorについて、nodeで木が切断されるので、木のサイズが確定する
        # なので、確定した木に含まれるパスの数を足し込む
        tree_size = sub_size - sub_disconnected_node_sizes[node_color]
        @path_count_in_trees[node_color] += all_path_count(tree_size)

        # 非連結なノード数を足し込む
        # このとき、効率をよくするためにサイズの大きなオブジェクトを再利用する
        if disconnected_node_sizes.size < sub_disconnected_node_sizes.size
          disconnected_node_sizes, sub_disconnected_node_sizes \
            = [sub_disconnected_node_sizes, disconnected_node_sizes]
        end
        sub_disconnected_node_sizes.each do |color, sub_disconnected_node_size|
          disconnected_node_sizes[color] += sub_disconnected_node_size
        end
      end
    end

    # node_colorについて、nodeで木が切断されるので、
    # node以下は親から見て非連結になる
    # なので、非連結なノード数をnode以下の部分木のサイズにする
    disconnected_node_sizes[node_color] = size

    [size, disconnected_node_sizes]
  end

  # サイズnの木にあるパスの総数
  def all_path_count(n)
    n * (n + 1) / 2
  end
end

n = gets.to_i
colors = gets.split.map(&:to_i)
edges = (n-1).times.map{ gets.split.map{|e| e.to_i - 1} }

tree = Tree.new(n, colors, edges)
tree.get_answer.each do |i|
  puts i
end

これでやっとACが取れた。

それにしても、難しい・・・
コード理解するの、めっちゃ時間かかった(^^;
これも慣れればスルッとできるようになるのかなぁ・・・?

今日はここまで!

『鋼のメンタルを手に入れる ゴリラ式メタ認知トレーニング』を読んでみた。

f:id:yamaimo0625:20190415223657j:plain

メンタルを鍛えないとなぁと思って読んだ『鋼のメンタルを手に入れる ゴリラ式メタ認知レーニング』が面白かったので、紹介。

鋼のメンタルを手に入れる ゴリラ式メタ認知トレーニング

鋼のメンタルを手に入れる ゴリラ式メタ認知トレーニング

  • 作者:いっちー
  • 発売日: 2020/02/26
  • メディア: 単行本(ソフトカバー)

心の中にゴリラを飼う

本書では、

  1. そもそも「鋼のメンタル」とは何か(本でのゴールの明確化)
  2. メタ認知とは何か(ゴールにいたるためのツールの紹介)
  3. なぜゴリラなのか(ゴリラとメタ認知との関係の説明)
  4. ゴリラ式メタ認知レーニン

と、非常に順序立てられて説明されてる。

けど、結論をあえて一言で言ってしまうと、

心の中にゴリラを飼おう

となる。

キーは「迷ったらゴリラに聞いてみる」こと。

たとえば、明日会社に行きたくないなぁ、となったとき、ゴリラならどう言うか考えてみる。

ゴリラ「なら、行かなきゃいいじゃん」

いやいや、そうはいかんでしょ、なぜなら・・・となるわけだけど、そこで「なぜなら・・・」と考え始められるというのが重要なポイント。
いろいろな理由を考えることができるわけだけど、それを逐次チェックして、自分のゴールに照らし合わせることで、いろいろな気づきを得られる。

メンタルがまいってしまうと、近視眼的になってしまって客観的に物事を捉えたり冷静に考えたりすることが難しくなる。
そういった中で、一旦立ち止まって冷静に考え直し、いろいろな気づきを得て、見えなくなってた選択肢を選べるようにするというのが重要ということ。

ゴリラでなくてもいいのでは?

この手法はとても面白いと思ったんだけど、同時に思ったのは、別にゴリラでなくてもいいのでは?ということ。
どうせ心の中に何かを同居させるなら、ゴリラよりもかわいい女の子の方がいいw
セクハラだと怒られてしまいそうけど、ぶっちゃけ「大丈夫? おっぱい揉む?」みたいな女の子が心の中にいた方が、いろいろ元気になりそうよねw

もうちょい真面目な話をすると、ゴリラというのはたしかにイメージしやすくていいんだけど、ちょっとカスタマイズとして足りてないと思う。

具体的には、たとえば思考の癖で自責型(原因を自分に求める)と他責型(原因を他人に求める)があるけど、それぞれによって必要な視点って変わってくると思う。
自責型の場合、他人にも問題があったんじゃないかと考え直して、自分を押し潰してしまわないことが重要。
一方、他責型の場合、自分にも問題があったんじゃないかと考え直して、自分の成長に繋げていくことが重要。

極端な考えにはまり込むのがよくないので、中庸を保てるように、自身のパーソナリティとは反対側にいるような存在が心の中にいた方が、効果が高いように思う。

だらしない人なら、真面目な人格が心の中にいるといい。
内向的な人なら、外交的な人格が心の中にいるといい。
etc.

そんな感じで、TRPGのキャラメイクのように、各個人にフィットしたキャラクターを対話の相手として作れたら、愛着も湧くし、より効果も高められそう。
たとえば、自分は性格診断をするとINTP型と出たんだけど、この対極はESFJ型なので、そんなキャラクターを作ってみるとか。

性格診断して対極にある性格をベースとし、そこにいろいろ属性とかぶち込んだキャラを作って、自身と脳内でロールしながらいくつかのサンプルシナリオを進め、困ったときはそのキャラに相談してみる、という感じの本とか作れたら、めっちゃ面白そうw

今日はここまで!

鋼のメンタルを手に入れる ゴリラ式メタ認知トレーニング

鋼のメンタルを手に入れる ゴリラ式メタ認知トレーニング

  • 作者:いっちー
  • 発売日: 2020/02/26
  • メディア: 単行本(ソフトカバー)

統計検定2級を受けてみた。

f:id:yamaimo0625:20190601142919j:plain

現在、就活中なんだけど、しばらく活動してみて全然ダメだったので、実績に少し箔をつけるために統計検定2級を受けてみた。
無事合格したので、どんな勉強をしたかなどを紹介したい。

統計検定2級とは

統計検定は、統計学に関する知識や活用力を評価する検定試験。
2級だと大学基礎課程(1・2年次学部共通)で習得すべきことが出題される。

・・・とされてるけど、数理科学科出身の自分でもこんな内容はやってない(^^;
正直、統計学は数学の中でも考え方がかなり特殊なので、数学科出身でもそれなりに勉強はしないと受からないと思う。
数学部分は問題なくても、統計的な考え方と知識がないと解けない。

試験方式は、紙の冊子が配られて回答するPBT方式と、パソコンに問題が表示されて回答するCBT方式がある。
PBT方式は基本的には年2回(6月と11月)。
一方、CBT方式はいろんな会場でほぼ毎日開かれてる。
なので、急ぎで試験を受けたかったらCBT方式がいい。
自分もCBT方式でサクッと試験を受けてきた。

試験時間は90分で、四択or五択の問題が約35問出題され、100点満点で60点以上取れれば合格(※CBT方式の場合)。

ノー勉だとさすがに無理だと思うけど、それなりに勉強して過去問を解けば普通に受かるとは思う・・・のだけど、PBT方式の合格率は40%強なので、微妙なところ。
勉強した人がどれだけ合格したかという条件付き確率が欲しい・・・
(基本情報や応用情報も合格率20%強とかみたいだし、その合格率マジで?となる)

勉強スケジュール

自分の場合、大学時代に統計の勉強はまったくやらなかった。
なので、数学はともかく、統計に関しては知識ゼロからのスタート。

思い立って勉強を始めたのが3/9(月)で、1週間ちょっとで本を読んだりWebを見たりで基本的な知識をつけた。
そのあと、3/17(火)から過去問を解き始め、分からなかったところなどを補強。
そして、3/28(土)、つまり今日、CBT方式で受検して、無事合格。

2週間くらいで取れるかなぁと思ったんだけど、試験申し込みを約1週間前にやらないといけなかったらしく、1週間ほど延びてしまった(^^;
まぁ、その分過去問を解く回数も増えたので、万全を期せた感じ。

読んだ本など

いろいろ読んだので、順番に。

『完全独習 統計学入門』

完全独習 統計学入門

完全独習 統計学入門

  • 作者:小島 寛之
  • 発売日: 2006/09/28
  • メディア: 単行本(ソフトカバー)

統計WEBでいろいろな本が紹介されてた中で、小島先生は他の本(『数学的思考の技術』)で知っていたので、この本をまず手にとってみた。

この本のいいところは、統計学の考え方が分かりやすく書かれていたこと。
最初に手にとった一冊としては、大正解だったと思う。
これは、著者の小島先生自身が統計学を「胡散臭い学問」とちゃんと認識してたからで(数学やってる人からすると統計学ってかなり異質に見える)、その上で「あぁ、統計学ではそう考えるのね!」というポイントをしっかりと掴んでるから。

推測統計の方法論は「部分から全体を推論する」という「帰納法」です。 これは数学という完全無欠の「演繹法」になじんだ筆者には、「飛躍だらけの論理体系」に見え、これを受け入れるためには、慣れ親しんだ思考法からいったん頭を切り替えなければならない、と悟ったのです。
(『完全独習 統計学入門』「おわりに」より引用)

逆にいうと、統計学ではこうするんだよーと言われて何の疑問も持たずに受け入れられてしまう幸せな頭の人は、別の本でもいいかも。

なお、統計学の基本的な考え方を伝えることに注力してるので、統計検定2級に必要な知識を得るにはかなり足りない。
なので、他の本やWebでの補足は必須。

『完全独習 ベイズ統計学入門』

完全独習 ベイズ統計学入門

完全独習 ベイズ統計学入門

  • 作者:小島 寛之
  • 発売日: 2015/11/20
  • メディア: 単行本(ソフトカバー)

上記の本のベイズ統計版。

この本も非常によかった。
面積図を使った説明は、ベイズ統計の考え方をすごく分かりやすく伝えてくれる。

統計検定2級でも事後確率を求める問題は頻出だけど、これ一冊読めばかなり理解が深まり、なんかゴチャゴチャした公式を覚えなくてもベイズ統計の問題が解けるようになると思う。

『マンガでわかる統計学入門』

マンガでわかる統計学入門

マンガでわかる統計学入門

マンガなら読みやすいかなぁと手にとった本。
電子版もあったので。

書かれてる内容は小島先生の本とほとんど同じで、もうちょっと統計学の言葉を使ったものになってる。
なので、読む必要はほとんどなかった。

『マンガでわかる統計学

マンガでわかる統計学

マンガでわかる統計学

これも有名な本。
ずっと昔に買って本棚で眠ってた・・・

マンガだけど、内容はなかなか難しい。
そして、推定や仮説検定の説明だと母平均が使われることが多いと思うのだけど、この本では独立性の検定が使われてる。
また、相関係数の他に相関比や連関係数の話が書かれてて、データの関連性に重点が置かれている感じがした。

正直、この本を入門書として読んでもさっぱりだと思う。
やはり入門は小島先生の本がいい。
その上で、データの関連性について知りたいときにはこの本を読むといいと思う。
(独立性の検定も統計検定2級でよく出る)

『マンガでわかる統計学 回帰分析編』

上記の回帰分析版。

単回帰分析、重回帰分析も統計検定2級の試験範囲でよく出るんだけど、結論から言えばこの本は参考にならなかった。
(この本自体が勉強にならないというわけではない)

試験でよく出るのはt分布を使った検定。
一方、この本ではF分布を使った検定・・・

統計学がわかる』

統計学がわかる (ファーストブック)

統計学がわかる (ファーストブック)

ハンバーガーショップでのいろいろな課題をテーマに話が進むので、読みやすかった。
推定や仮説検定の話がたっぷりと書かれてるので、小島先生の本を読んで、足りない部分を足すとよさそう。
母平均、母分散の検定の話に加え、母平均の差に関する検定の話が書かれてる。

統計学がわかる 回帰分析・因子分析編』

統計学がわかる 【回帰分析・因子分析編】 (ファーストブック)

統計学がわかる 【回帰分析・因子分析編】 (ファーストブック)

上記の本の回帰分析(&因子分析)版。

これも回帰分析の参考にはならなかった。。。
分かりやすいとは思うんだけど、知りたかったのは検定に関する話で、それについては言及ゼロだったので。

統計WEB

かなりお世話になった。

本だとどうしてもページ数に限りがあるので、載せられる検定の種類も限られる。
そこで足りなかった知識については、このサイトでほぼ網羅されてるので、調べればだいたい分かった。

とはいえ、いきなりこのサイトを見てもなかなか難しいところはあるかも。
分量もかなり多いし。
なので、本で基本を押さえ、過去問を解いて分からない問題が出たら調べるという感じが効率いいかもしれない。

『統計検定2級 公式問題集』

日本統計学会公式認定 統計検定 2級 公式問題集[2016〜2018年]

日本統計学会公式認定 統計検定 2級 公式問題集[2016〜2018年]

  • 発売日: 2019/03/20
  • メディア: 単行本(ソフトカバー)

過去3年分(合計6回分)の問題と解説が載ってる。
とはいえ、いきなり解説見ても分からないと思うので、やっぱり基本を理解してから。

この問題集をどれだけやり込んだかが合格に大きく繋がると思う。
自分は2016〜2018年の問題集と、2013〜2015年の問題集を全部解いた。

最初は90分をオーバーしてもいいから全部の問題に目を通し、分からないところを潰す。
そして、慣れてきたらちゃんと時間内に収まるように解くといいと思う。

統計検定2級をとってみて

とりあえずとってみたけど、まぁ勉強すれば普通にとれるだろうし、うーん、凄いんだろうか・・・
まぁ、就活にプラスに働くことを祈るのみ。

勉強したことは忘れないためにも近いうちにまとめて公開したいと思う。

今日はここまで!

完全独習 統計学入門

完全独習 統計学入門

  • 作者:小島 寛之
  • 発売日: 2006/09/28
  • メディア: 単行本(ソフトカバー)

完全独習 ベイズ統計学入門

完全独習 ベイズ統計学入門

  • 作者:小島 寛之
  • 発売日: 2015/11/20
  • メディア: 単行本(ソフトカバー)

マンガでわかる統計学入門

マンガでわかる統計学入門

マンガでわかる統計学

マンガでわかる統計学

統計学がわかる (ファーストブック)

統計学がわかる (ファーストブック)

統計学がわかる 【回帰分析・因子分析編】 (ファーストブック)

統計学がわかる 【回帰分析・因子分析編】 (ファーストブック)

日本統計学会公式認定 統計検定 2級 公式問題集[2016〜2018年]

日本統計学会公式認定 統計検定 2級 公式問題集[2016〜2018年]

  • 発売日: 2019/03/20
  • メディア: 単行本(ソフトカバー)

『0から分かる!ソート・選択アルゴリズムと資源配分問題』を読んでみた。

f:id:yamaimo0625:20190621155528j:plain

新型コロナの影響で技術書典8は中止になったけど、技術書典 応援祭が絶賛開催中。

そんな中で買ったねず宮ちんじろうさんの『0から分かる!ソート・選択アルゴリズムと資源配分問題』が面白かったので、紹介したい。

概要

アルゴリズムの基本とも言えるソートアルゴリズムの解説から始めて、最終的には資源配分問題を高速に解くアルゴリズムまで説明されている。
図が多く、具体例を使った議論がされてるので、とても分かりやすい。
また、資源配分問題を高速に解くアルゴリズムは、なるほどねという感じ。

資源配分問題

本書でゴールにしてる資源配分問題というのは、こんな問題:

Aさん、Bさん、Cさん、Dさんは友人から6個のりんごを貰った。
それぞれがりんごをいくつか貰った時の満足度は次の表で表される。
全体での満足度の合計値が最大となるような配分はどうなるだろうか?

人物 0個 1個 2個 3個 4個 5個 6個
A 0 13 24 33 42 48 52
B 0 17 29 37 42 45 46
C 0 16 31 38 41 43 44
D 0 20 38 52 62 67 69

この問題のポイントは、もらったリンゴの個数が増えたときの満足度の上昇が徐々に減っていっていること。
これは経済学で限界効用逓減の法則と呼ばれてる。
そして、それは数学的にみると凹関数といういい性質として捉えることができる。

さっきのツイートの通り、自分だとこの問題は何も考えずにMIP(Mixed Integer Programming, 混合整数計画問題)にして解いちゃいそうだけど、本で紹介されてるアルゴリズムはこの凹性をうまく利用していたので、とても感心した。
アルゴリズムの詳細は本を買ってのお楽しみということでw

MIPでの解法

ここからはオマケで、じゃあMIPだとどう解くのかという説明。

各自のもらうリンゴの数を求めるから、Aさんがもらうリンゴの数を x_A、Bさんのもらうリンゴの数を x_B、・・・( x_A, x_B, \ldotsは0以上の整数)としてしまいそうだけど、それだとうまくいかない。

こういうときの定石は、Aさんがリンゴを0個もらうかどうかを x_{A,0}、Aさんがリンゴを1個もらうかどうかを x_{A,1}、・・・、 Bさんがリンゴを0個もらうかどうかを x_{B,0}、・・・とバイナリ変数で表すようにする。
そうすると、Aさんがもらったリンゴの数は \sum_i i x_{A,i}と表せるし、Aさんの満足度も(Aさんが i個もらえたときの満足度を s_{A,i}で表すとして) \sum_i s_{A,i} x_{A, i}と表すことができる。

あとは、Aさんがもらうリンゴの数は0〜6個のどれか1つということに気をつければ、 x_{A,i}のうち1になるのがちょうど1個という制約が必要と気づくので、次のような最大化問題として書ける:

\displaystyle
\begin{align}
\textrm{max.} &\quad \sum_{m \in \{A, B, C, D\}} \sum_{i=0}^6 s_{m,i} x_{m,i} \\
\textrm{sub. to} &\quad \sum_{i=0}^6 x_{m,i} = 1 \qquad(\forall m \in \{A, B, C, D\}) \\
&\quad \sum_{m \in \{A, B, C, D\}} \sum_{i=0}^6 i x_{m,i} = 6 \\
&\quad x_{m,i} \in \{0, 1\}
\end{align}

あとはこれを解くだけ。

GLPKで解いてみる

小さなMIPならフリーのGLPKでも全然解けるので、GLPKで解いてみた。

まず、上記の数式をモデルにすると以下:

# リンゴの数
param AppleCount;

# メンバーとリンゴの範囲
set Member;
set AppleRange := 0..AppleCount;

# 満足度
param Satisfaction{Member,AppleRange};

# メンバーとリンゴの数に対して、配分されるか
var Distribution{Member,AppleRange} binary;

# 満足度を最大化
maximize TotalSatisfaction:
sum{m in Member, i in AppleRange} Satisfaction[m,i] * Distribution[m,i];

# 各メンバーについて、配分はどれか1つ
subject to Assignment{m in Member}:
sum{i in AppleRange} Distribution[m,i] = 1;

# 配分されるリンゴの合計はリンゴの数に等しい
subject to CountSum:
sum{m in Member, i in AppleRange} i * Distribution[m,i] = AppleCount;

# 解いて解を出力
solve;
display Distribution;

end;

与えるデータは以下:

# 入力データ
data;

param AppleCount := 6;

set Member := A B C D;

param Satisfaction: 0 1 2 3 4 5 6 :=
    A   0   13  24  33  42  48  52
    B   0   17  29  37  42  45  46
    C   0   16  31  38  41  43  44
    D   0   20  38  52  62  67  69
;

end;

これをglpsolで実行すると、こうなる:

$ glpsol -m rscprb.mod -d small.dat
(省略)
INTEGER OPTIMAL SOLUTION FOUND
Time used:   0.0 secs
Memory used: 0.1 Mb (149031 bytes)
Distribution[A,0].val = 1
Distribution[A,1].val = 0
Distribution[A,2].val = 0
Distribution[A,3].val = 0
Distribution[A,4].val = 0
Distribution[A,5].val = 0
Distribution[A,6].val = 0
Distribution[B,0].val = 0
Distribution[B,1].val = 1
Distribution[B,2].val = 0
Distribution[B,3].val = 0
Distribution[B,4].val = 0
Distribution[B,5].val = 0
Distribution[B,6].val = 0
Distribution[C,0].val = 0
Distribution[C,1].val = 0
Distribution[C,2].val = 1
Distribution[C,3].val = 0
Distribution[C,4].val = 0
Distribution[C,5].val = 0
Distribution[C,6].val = 0
Distribution[D,0].val = 0
Distribution[D,1].val = 0
Distribution[D,2].val = 0
Distribution[D,3].val = 1
Distribution[D,4].val = 0
Distribution[D,5].val = 0
Distribution[D,6].val = 0
Model has been successfully processed

見ての通り、一瞬でサクッと解けた。
(Aが0個、Bが1個、Cが2個、Dが3個)

ちなみに、練習問題に載ってた少し大きい問題も以下の通り:

# 入力データ
data;

param AppleCount := 15;

set Member := A B C D E F;

param Satisfaction:
    0   1   2   3   4   5   6   7   8   9   10  11  12  13  14  15 :=
A   0   36  67  91  109 122 131 135 135 135 135 135 135 135 135 135
B   0   40  78  113 134 149 160 165 165 165 165 165 165 165 165 165
C   0   39  66  83  95  101 105 108 108 108 108 108 108 108 108 108
D   0   26  51  71  90  104 116 126 126 126 126 126 126 126 126 126
E   0   23  36  47  55  62  64  65  65  65  65  65  65  65  65  65
F   0   37  69  97  102 106 109 109 109 109 109 109 109 109 109 109
;

end;
$ glpsol -m rscprb.mod -d large.dat
(省略)
INTEGER OPTIMAL SOLUTION FOUND
Time used:   0.0 secs
Memory used: 0.2 Mb (237295 bytes)
(省略)
Distribution[A,3].val = 1
(省略)
Distribution[B,4].val = 1
(省略)
Distribution[C,2].val = 1
(省略)
Distribution[D,2].val = 1
(省略)
Distribution[E,1].val = 1
(省略)
Distribution[F,3].val = 1
(省略)
Model has been successfully processed

こんなふうに、大きくない問題ならアルゴリズムをまったく考えないでも解けるのがMIPの嬉しいところ(^q^)

ちなみに、上記のGLPKの解説は新刊に書いているので、よかったら読んでみてほしい。(宣伝)

もちろん、MIPを使って脳死で解けるのは小さい問題に限るので、紹介した本のような内容も必要になってくる。
なので、紹介した本もぜひとも読んでみてほしい。

今日はここまで!