いものやま。

雑多な知識の寄せ集め

プログラミングは名が命。

f:id:yamaimo0625:20191023151952j:plain

「プログラミングをするとき、何に気をつけるべきか?」という質問に対して、自分が思っているのは「命名を大切にする」こと。

プログラミングというのは、モヤモヤしている概念(操作なども含む)を抽出して明確にし、そこに名前をつけていくことだと思ってる。
なので、いい命名を行えるかどうかで、概念の切り出しがキレイかどうかーーすなわち、プログラムがキレイになるかどうかが決まってくる。

これを、「コードの臭い」というリファクタリングの一視点と絡めて、実際に見ていきたい。

「初心者がリファクタリングで目をつけるべき場所」

とらラボ主催のLT会で、きり丸さん(@nainaistar)による次のような発表があった:

「コードの臭い(Code Smells)」に注目してリファクタリングするといいよ、という話なんだけど、この話の多くは「いい命名をしましょう」の一言で片付いたりする。

ここで挙げられてるのは、以下:

  • Large Class(大きすぎるクラス)
  • Long Method(長すぎるメソッド)
  • Long Parameter(多すぎる引数)
  • Duplicate Code(重複したコード)
  • Magic Number(意味が読み取れない謎の値)
  • Comments(大量のコメント)
  • Arrow(深すぎるネスト)
  • Primitive Obsession(基本型に執着する)
  • Feature Envy(外部モジュールの内部データを使う)
  • Data Clumps(一緒に扱われるべきデータが個別に扱われてる)

それぞれを「命名」の観点で見てみる。

Large Class

大きすぎるクラスというのは、いくつもの責務を持っていることになる。
そうなると、あれもやってこれもやってとなるから、その名前は一言で言い表しづらいものになる。

なので、以下のような特徴が出てくる:

  • 「〜マネージャー」「〜コントローラ」etc.
  • 名前にそぐわないメソッドがある
  • 1モジュール=1クラスのstaticおじさんクラス

こういった場合、概念を切り出して名前をつけ、いくつかのクラスに分けてあげるといい。
「この概念はまとめて名前をつけられるな」とか「このデータだけ抜き出して名前をつけられるな」と考えるといい。

Long Method

長すぎるメソッドというのは、処理をダラダラと書いてしまってる。

そういう場合、大抵は

// ここでxxxする
...

// 次にxxxする
...

みたいに、空行を挟んでいくつかの処理の塊が続いてることが多いと思う。

そういったときは、それぞれの処理の塊をメソッドに切り出してやるといい。
「ここの処理の塊、何やってるの?」という質問に対して、「〜をやってるんだよ」という答えが出せるなら、その操作には名前がつけられるということになる。
なので、その名前でメソッドを用意する。
そうすると、メソッドは短くなるし、メソッド名で処理が説明されるのでコメントも不要になる。

ここで一つ気をつけたいのが、処理の重複を防ぐためにメソッドを用意するのではなく、処理の説明をするためにメソッドを用意するということ。
実装上の都合(=同じ処理を何度も書くのは嫌)から設計を考えるのではなく、概念を整理する観点(=この処理には名前をつけられる)から設計を考える。
あとでも言及するけど、これは結構重要。

Long Parameter

パラメータが多すぎるメソッドは、そもそもそのパラメータをまとめて名前をつけられることが多い。
あるいは、処理に必要な情報があまりに多いということは、責務が大きくなりすぎてる可能性もある。

前者であれば、そのまとめたものに名前をつけてクラスとして切り出すといい。
そうすればパラメータの数はグッと減る。

そして、後者の場合、部分的な処理を適切な名前をつけて別のクラスに移せば、その処理で必要になるデータは移した先のクラスが持ってればいいので、パラメータとしてデータを渡す必要がなくなる。

「パラメータをまとめたものに名前をつけられないか」「やってる処理に名前をつけて、その処理で使ってるデータに名前をつけられないか」と考えるといい。

Duplicate Code

重複したコードは、その処理に名前をつけられるはずなので、その名前でメソッドにすればいい。

ここで重要なのが、「処理が同じだから抜き出してメソッドにする」のではなく、「処理に名前がつけられるからメソッドにする」ということ。
前述の通り、実装ではなく概念が同じかに気をつけないといけない。

たとえば、スライドだと次のような変更をしてる:

// 変更前
private static int userId = 0;
private static int taskId = 0;

public static int takeUserId() { return userId++; }
public static int takeTaskId() { return taskId++; }

// 変更後
private static int id = 0;

public static int takeId() { return id++; }

これはダメな変更の例。
なぜかというと、「処理が同じだから」という理由で共通化してしまっているから。
でも、元のメソッド名が示す通り、「ユーザIDを取得する」という操作と「タスクIDを取得する」という操作は、実装は同じかもしれないけど、操作の意味が違う。
意味が違う(けど実装は同じ)処理をひとまとめにしてはダメ。
これをやってしまうと、概念ではなく実装に依存することになるので、途端に変更が難しくなる。

これに類似したミスというのはよくあって、代表的なのは処理が同じだから親クラスを作って、親クラスに実装を持っていくというもの。
結果、親クラスでした変更が思わぬ問題を引き起こしたり、あるいは変更が困難になったり。

特定の処理を使いまわしたいなら、その処理を行うクラスを用意して、そのクラスに処理を委譲するようにした方がいい。
「〜の処理をするクラス」と、ここでも概念を抜き出して命名を行っている。
Rubyの場合、Mix-inが強力なので、これはModuleとしてincludeすれば実現できる)

Magic Number

これはもうそのまんまで、数字をそのまま使うんじゃなくて、名前をつけて意味が分かるようにしましょうね、ということ。

コメントではなくメソッド名で処理を説明するというのもこれと同じ。
名前をつければ、コメントを書かなくてもその名前で説明できる。

Comments

コメントが多すぎるコードというのは、つまり概念としてまとめられるコードがあるのに、それをメソッドとしてまとめてないということ。
まとめてなくてパッと見だと何をしてるか分からないから、コメントが必要になってる。

もう再三言ってるけど、コメントを書くくらいなら、適切な名前をつければいい。

ただし、「こういう方法もあるはずなのに、なんであえてこんな処理をしてるのか」という説明が必要な場合もある。
そういった場合はメソッド名だけでは説明できないので、コメントをつけた方がいい。
(大抵、何らかの問題と結びついてるはずなので、issueへのリンクを貼っておくといい)

Arrow

入れ子が深くなってる場合、いろいろ原因はあるけど、まずは処理に名前をつけて切り出せる部分がないかを探してみるといい。
切り出せればそれだけで入れ子が浅くなる。

また、スライドのようにif文がズンズン深くなってるときは、その条件判断に名前をつけて切り出すといい。
たとえば、if (args_is_valid(...)) { ... }とするとか。

ちなみに、早期returnは個人的にはOKだと思ってるけど、コーディング規約で許されない場合もあるので注意。

Primitive Obsession

基本型に固執しているというのも、やっぱり適切に命名してないということ。
概念として切り出せるのだから、それに名前をつければいい。
名前をつければ、コンパイラの型チェックの恩恵を受けられるし、何を扱ってるのかも分かりやすくなる。

Feature Envy

外部モジュールの内部データを使おうとしてるということは、つまりそのデータを使って何かやりたい操作があるということ。
なら、その操作は名前がつけられるはずだし、それはその外部モジュールの機能として(=メソッドとして)提供できることになる。

ただ、データオブジェクトの場合はちょっと微妙で、たとえば設定値を保持してるConfigクラスがあったとして、その設定値を使う処理をConfigクラスが持つべきかというと、かなり微妙。
この場合、Configクラスは値を保持するという責務だけをやるべきで、保持してる値を他のクラスが目的に合わせて使う方が、責務が明確になる。

Data Clumps

一緒に扱われるべきデータが個別に扱われているというのは、つまりそのまとまりに名前がつけられてないということ。
名前をつけてクラスにすれば、一緒に扱われるようになる。


こんな感じで、大抵のことは「いい命名をしましょう」の一言で片付く。
なので、命名は本当に大切。

これは以前書いた言葉にするということ。 - いものやま。にも通じたり。
言葉にすることで曖昧だったものが明確になるように、命名することで曖昧だった概念も明確になる。

今日はここまで!

GCPのText-to-Speechでストレッチ音声を作ってみた。

f:id:yamaimo0625:20200618193136j:plain

きっかけ

一日中パソコンに向かってることが多いので、とにかく首と肩のコリが酷い。
おそらくそれが原因で頭痛がすることも。

さらに最近は外出も自粛してるので、腰や脚の方にもけっこうコリが出ていた。

一応、整体には通っているものの、対処療法という感は拭えないので、やはりストレッチを行って根本的に改善していかないとなぁ、と。

そんな中、Twitterでなかなか良さそうな本が流れてきたので、試しに買ってみた。

猫背の改善から始まり、首・肩・背中のコリ、腰・足のコリをほぐすストレッチが、イラストで伸ばす筋肉の説明と共に合計27個紹介されている。
実際にやってみると、たしかにぐおぉという感じで伸びを感じる・・・
これは効きそう。

問題点

ということで、毎日お風呂上がりにでもやっていこうかなと思ったんだけど、ここでちょっと問題点が。

  1. 覚えられない
  2. カウントがツラい
  3. 味気ない

まず、覚えられない
27個も紹介されてると、それぞれの動きを覚えるのも大変だし、どのストレッチをまだやってないのか覚えておくのも大変。
本を開いて順番にめくっていけば問題ないとも言えるけど、1つやるたびにページをめくるのはとても手間。

次に、カウントがツラい
1つのストレッチにつき、20秒×3セットやることが推奨されてるんだけど、20秒を自分で数えるのは大変。
タイマーを使うという手もあるかもしれないけど、1つやるたびにボタンを押したりするのは面倒。

最後に、味気ない
こう、無音の中でじっと筋肉を伸ばすのは、なんというか、ね。
せっかくだからリラックスできる音楽とか聴きながらストレッチしたいところ。

解決策

これらの問題点をどうしようかと考えて思いついたのが、音声ガイド
手順を音声で教えてくれて、カウントもお任せし、ついでにいい感じのBGMとかも一緒に流せば万事解決!

となると、問題となるのは音声データをどう作るかだけど、自分で吹き込むのはアレなので、Text-to-Speechを使って作ることにした。

macOSには標準で音声読み上げ機能がついてるんだけど、試しに使ってみたところ、かなり微妙。。。
代わりにGCPのText-to-Speechを試してみたら、なかなかいい感じだったので、GCPのText-to-Speechを使ってみることにした。

GCP Text-to-Speech

GCPのText-to-Speechは100万文字/月までは無料で使えるので、今回の用途なら無料でOK。
よく使われる言語(Rubyも含まれる)向けのライブラリも用意されてるので、簡単に使えた。

使い方はクイックスタート: クライアント ライブラリの使用  |  Cloud Text-to-Speech のドキュメントに書いてある通りに進めればOK(手抜き)。

読み上げるテキストとそれを保存するファイル名は、あとでファイル(YAML形式)で渡す形にしたかったので、次のようなRubyプログラム(text_recorder.rb)を書いてみた:

require "google/cloud/text_to_speech"
require 'yaml'

USAGE = <<~END_OF_USAGE
  Syntax:
    ruby text_recorder.rb <target>.yml

  Format of <target>.yml:
    - file: <output1>
      text: <text1 to speech>
    - file: <output2>
      text: <text2 to speech>
    ...
END_OF_USAGE

if ARGV.empty?
  puts USAGE
  exit 1
end

entries = YAML.load_file(ARGV[0])
if entries.empty?
  puts USAGE
  exit 1
end
total = entries.size

client = Google::Cloud::TextToSpeech.text_to_speech
voice = { language_code: "ja-JP", name: "ja-JP-Wavenet-B" }
audio_config = { audio_encoding: "MP3" }

entries.each_with_index do |entry, i|
  input = {text: entry['text']}
  output = entry['file']
  output += '.mp3' unless output.end_with?('.mp3')

  current = i + 1
  STDOUT.print("[#{current}/#{total}] #{output} ... ")
  STDOUT.flush

  response = client.synthesize_speech(input: input, voice: voice, audio_config: audio_config)
  File.open(output, "wb") do |file|
    file.write response.audio_content
  end

  STDOUT.puts('Done.')
end

そして、次のような入力ファイル(stretch.yml)を用意する:

- file: 僧帽筋
  text: |-
      首の後ろを伸ばします。
      両指を組み、頭の後ろに回して、脇を絞めます。
      首を真下に向け、頭を下に押して伸ばします。
- file: 胸鎖乳突筋(右)
  text: |-
      首の横を伸ばします。
      首を左に傾け、右手の甲を腰の裏に回します。
      あごを少し上に向け、左手で頭を掴み、そのまま斜め後ろに引いて伸ばします。
(以下省略)

あとはコマンドラインで以下を実行:

$ ruby text_recorder.rb stretch.yml

これで「僧帽筋.mp3」や「胸鎖乳突筋(右).mp3」などが作られ、指定された文章が読み上げられた音声データが出来る。
あとは動画編集ソフトとかを使ってちょちょいと音声データをつなぎ合わせれば、完成!

出来上がった音声データ

せっかくなのでYouTubeにアップしてみた。
(好きなBGMを合わせた方がいいと思うので、BGMなしになっている)

なお、本では27個のストレッチが紹介されてるけど、動画では18個に減らしてる。
これは、27個全部やったら1時間近くになるから・・・(左右があるので、実質50個強のストレッチをやることになる)
同様の理由で、20秒×3セットではなく、15秒×3セットにしている。

それと、菱形筋と腰方形筋のストレッチはアレンジしてある。
前者は床に座って行う手順だったんだけど、床に座るのは面倒だったので、椅子に座ったままできるように変えている。
また、後者は手を体の前に落とすイラストになっているんだけど、体の横に落とすようにした方がよく伸びたので、変えている。

あと、ストレッチの並び順も、椅子に座って行えるもの→立って行うものと変えてる。
本に書かれた順番でやるよりもずっとやりやすくなってるはず。

ちなみに、自分はBGMとして以下の音楽をつけてみた:

最初はドビュッシーピアノ曲をつけようと思ったんだけど、クラシック音楽は聴き入ると自然と体が動いてしまうので、雰囲気を出すだけのBGMの方がいいのかも。

今日はここまで!

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

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
  • メディア: 単行本(ソフトカバー)