すべてがFになる-「７だけが孤独」の問題を解く

森博嗣さんの「すべてがFになる」の冒頭で、ある問題が提起される。
「1から10までの数字を二組に分けて、それぞれグループの数字を全部掛け合わせる。このとき、二つの積が等しくなることはありますか？」
「ありません。片方には７があるので、その積は７の倍数になるけれど、もう片方には７がないので７の倍数にはならない。つまり二つのグループの積が等しくなることはありません」

では、７を除外した時、二つのグループの積が等しくなることはあるのでしょうか。

①まず、等しくなる時の数について考察します。
　二つのグループの積が等しいならば、そのグループ同士の積は等しくなる時の二乗となります。
　１〜１０(７を除く)の積は
　
　なので、平方根をとって等しくなる時の数は
　
　となる。
　つまり、積が720になるように二つのグループを分ければよい。

②720を素因数分解すると
　
　となる。
　これより、個々の数値が10以下である組み合わせを求めればよい。
　ここで、「5」という数が"孤独"なので、「5」を中心に考えてみよう。
　5・3・2の組み合わせで、10以下の数は「5,10()」である。
　まず、10から考える。
　(「1」はあってもなくても積に関係がないため、表記を割愛する)

　
　
　
　

　次に、「５」について考えると
　
　
　
　
　

　となる。

　よって、1〜10までの7を除く数値を二つに分けた時、積が等しくなる組み合わせは6通りあり、
　[2,4,9,10],[2,5,8,9],[3,4,6,10],[3,5,6,8],[2,3,4,5,6],[8,9,10]
　である。
　(総数は)

最後に、会議中のノートに書いた解法なので、間違っていたら悪しからず。。。

「冷たい校舎の時は止まる」の地理的考察の補足

前回の以下記事において、補足事項をまとめます。jcolap1.hatenablog.com

■「二千円。くれるって言っただろ？関東大会優勝したら。」
■県下唯一の国立中学校であるT中の受験を自分で決めた。
景子と裕二の通っていた国立T中学校での記述です。
このセリフのため、関東にあるのかと思ったのですが、以下のとおり
関東以外の中学生でも登録できるようです。
また、県内唯一のT中も不明です。
そのため、国立T中学校の場所は不定です。

関東テニス協会 公式ホームページ
国立中学校 | 日本の中学校 | 検索結果一覧-1

■S市。地元S新聞
以下のとおり、S新聞がありません。
福島県だとすると、「相馬市」「須賀川市」「白河市」になるのですが、
青南の場所の詳細な場所は不定です。

日本の新聞一覧 - Wikipedia

■山に囲まれたこの場所にある事務所で、学生の頃の自分の先生を手伝っている。弁護士の少ない場所を進んで選んだと聞いて、本当に弱いもののみかたなんだなぁと尊敬した。

山梨県は弁護士数が少ないようです。ただ、大都市以外はほとんどその傾向にあるので、
特定要素としては除外です。

・弁護士の地域分布
http://www.nichibenren.or.jp/library/ja/publication/books/data/whitepaper_bengositiikibunpu.pdf

■都道府県のローマ字表記
以下サイトを参考にしました。
ドメイン名をもとにしているようです。
ありがとうございます。

都道府県ローマ字一覧

※「太陽の座る場所」では、F県は
「東京に隣接」しており、「県内に国立の中学校と高校は大学付属の一校ずつだけ。私立青南学院高校は、県下きっての進学校だ。」
とあり、「F」はイニシャルではない、ただの記号であることが示されています。
作中の前提と当記事の内容は同一ではありませんのでご注意ください。

「冷たい校舎の時は止まる」の地理的考察

今日は10月12日ということで、辻村深月さんの小説「冷たい校舎の時は止まる」での学祭最終日です。
辻村さんの作品は場所に関する記述が多く、かつ様々な作品で同一空間上にリンクされています。
ありそうでなかったので、自分でこれらの地理的考察をまとめます。
ネタバレ全開ですので、辻村さんの作品で未読もものがある方はご注意ください。

長いので結論だけ先に書きます。
また、地図も一番下に貼っています。

!!注意!!
太陽の座る場所」では、F県は
「東京に隣接」しており、「県内に国立の中学校と高校は大学付属の一校ずつだけ。私立青南学院高校は、県下きっての進学校だ。」
とあり、「F」はイニシャルではない、ただの記号であることが示されています。
作中の前提と当記事の内容は同一ではありませんのでご注意ください。

■前提
・情報については、範囲が大きい方が情報が確からしいと仮定する。[前提1]
(例えが、県と市の情報があり、矛盾している場合は県の情報が正しいとする。
これは、範囲が限定されるほど創作上の必然性が優先され、現実世界との乖離が大きくなるという
予測に基づく。)
・固有名詞を持つものについては、原則情報としない。[前提2]
(例えば、「笹倉中」や「秀英高校」などの固有名詞を検索したり、類似の場所等から
推測はしません。ただし、「長野県」や「フィリピン」等の創作上というより一般的に用いられる
固有名詞は情報とします。)
・日本国内の2004年(初版出版年)の地理構成を前提とする。[前提3]
(市町村構成や交通網は出版年に準じます。ただし、鉄道所要時間等現在では遡って補正することが難しいものは、
2015年現在の情報をもとに算出することもあります。)
・県名のアルファベットは、県名のイニシャルとする。[前提4]
(「太陽の座る場所」では、東京に隣接するF県が出てくるので、作品中でこのようなルールはありません。
あくまで筆者の中だけのルールです。)

■考察１：青南学院高等学校に関する考察
まず、青南学院高等学校(以下、青南)の所在地について考察する。
以下より、青南と景子の家は徒歩圏内にあることがわかる。

・「ああ、私はT中から。通学は中学の時より近くなったな。徒歩だよ。」(冷たい校舎の時は止まる)

したがって、景子の家の所在地を考察し、その徒歩圏内で青南の位置を求める。
景子の家の位置については、以下のとおり記述がある。

・トシの母さんは内科と小児科の医者で、家のすぐ近くにあるおじいちゃんの病院で仕事をしている。(ロードムービー)
・「ああ、あの古くてボロい病院でしょ?」(ロードムービー)

時代が違う「ロードムービー」の記述を「冷たい校舎の時は止まる」の記述と合わせて考察してよいかという問題があるが、
上記記述より、病院がボロいことから移築はせれておらず、景子の家は桐野総合病院近隣にあるということは変わらないので、
「ロードムービー」と「冷たい校舎の時は止まる」の情報を合わせて考察することは可能とする。
情報の整合をとるため、以下を仮定する。

・桐野景子は桐野総合病院に勤務している。[仮定1]

景子の家については、以下の記述がある。

・トシの住むここの隣、M県が載ったページを見開きにして机の上に伏せる。(ロードムービー)
・うん、俺、子供だけでF県出るの初めてなんだ。トシちゃんは?」(ロードムービー)

M県の対象となるのは「三重県-mie」「宮城県-miyagi」「宮崎県-miyazaki」、
F県の対象となるのは「福島県-fukushima」「福井県-fukui」「福岡県-fukuoka」である。
この中で、F県とM県が隣接することより、以下が言える。

・景子の家は「福島県」である。[結論1]

よって、以下仮定を置くことにより、青南の位置が求まる。

・景子の家と青南は同一県にある。[仮定2]
・青南は「福島県」にある。[結論2]

■考察２：榊の赴任先に関する考察
榊の赴任先について以下の記述がある。

・深月の言った通りにM県の住所が書かれていた。
・鷹野には覚えのない西の訛りを多く含んでいる。
・「新幹線が行くとこまではだいたい3時間ってとこかな。そっから鈍行。ゆっくり行こ。」(ロードムービー)
・「シズオカに行く電車がでるとこ」(ロードムービー)

M県の候補は前述のとおりであるが、「西の訛り」より、宮城県を除外する。
また、新幹線で３時間より、宮崎県を除外する。
これより、以下が言える。

・榊の赴任先は「三重県」である。[結論3]

■考察３：鷹野の事務所に関する考察
鷹野の弁護士事務所の位置について、以下のとおり記述がある。

・トシの家出計画の一番のポイントは、遠出をするということだった。県内どころか、近隣の県なんかでもない、遠く離れたY県を選ぶこと。(ロードムービー)
・それぞれ数字の下に目的地が記してある。東京方面。(ロードムービー)
・東京に着くのを待たずに、トシたちはバスを降りた。(ロードムービー)

Y県の候補は「山形県-yamagata」「山梨県-yamanashi」「山口県-yamaguchi」である。
[結論1]より、トシは福島県から東京方面のバスに乗ったと考えられる。
また、東京に着く前にバスを降りたことから、以下が言える。

・鷹野の事務所は「山梨県」にある。[結論4]

■まとめ
・景子の家は「福島県」である。[結論1]
・青南は「福島県」にある。[結論2]
・榊の赴任先は「三重県」である。[結論3]
・鷹野の事務所は「山梨県」にある。[結論4]

・桐野景子は桐野総合病院に勤務している。[仮定1]
・景子の家と青南は同一県にある。(越県しない。)[仮定2]

図にまとめたものを以下に示す。

図1：青南周辺の考察

■今後の課題
[前提4]を外して、環境だけで地理情報をまとめる試みもやってみたい。

線形探索と番兵

番兵を使った線形探索の実装。
線形探索は床に並べたトランプと端から確認していき、目的の数を探すような
直感的なアルゴリズム。
当然、計算量はデータ量Nに対してO(N)となる。

しかし、番兵を使うと定数倍の計算量の違いがでる。

番兵を使わないと

for (int i =0; i < n;i++){
    if (A[i] == key) return i+1;
  }

のように、forとifで２回処理が発生する。
一方、番兵を使うと

//番兵をセット
A[n] = key;
while ( A[i] != key ) i++;

のように、処理が１回になる。

したがって、番兵を使わないと2N回の処理が番兵を使うとN回になった。
(現在の計算機ではよほどデータ量が多くないと効果が出にくそうですが・・・。)

ちなみに、何かにつけてif文を使ってしまうため、ループが番兵まで行った時にfalseとするとき、if文を使わずに

return i != n;

とするのは見事だと思う。

■ソース
algorithm/5-2_linearsearch.c at master · JunKojima/algorithm · GitHub

algorithm/5-2-2_linearsearch.c at master · JunKojima/algorithm · GitHub

■参考資料

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造

飛ぶ鳥のシミュレーション

以下の論文でシュミレータの元となる数式があるらしい。
手が開いたところでやってみよう。

■論文
Craig Reynolds: Flocks, Herds, and Schools: A Distributed Behavioral Model
■参考書籍

エンジニアとしての生き方　　IT技術者たちよ、世界へ出よう！ (インプレス選書)

スタック

基本的なデータ構造の学習。
ここでは、逆ポーランド記法で与えた数式をスタックで計算させる。
スタックを用いた計算方法は、東北大学の外山先生の授業がわかりやすかったが、
講義資料はHPに無いようだ。

ちなみに、ここでは演算子を"+"や"-"にしているが、別に"a"や"b"を加算や減算と定義すれば
"a"も演算子として利用出来る。
(もちろん"a"を含む文字列はすべて加算として扱われてるが・・・。)

いづれもO(1)の計算量。

atoiは、数値をint型に変換するC言語の標準ライブラリらしい。

■ソースgithub.com

■参考資料

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造

シェルソート

今までのようにループ回数から計算量を直感的に求められないアルゴリズム。
挿入ソートは、整列されていれば高速に動作し、そうでない場合にはN(N-1)/2よりO(N^2)のアルゴリズムに
なるのだった。

この特徴を生かし、あらかじめざくっと(３個ずつとか４個ずつとか)挿入ソートをしたあとで
１つずつの通常の挿入ソートを行えば、計算量はN回に近づくのではないかという方法。
詳しい方法は参考リンクの動画を参照。(すばらしい!)

コツは、間隔をGとして、G={1,4,13,40,121,...}とするh = 3*h + 1で指定しているところ。
こんなの思いつかない・・・。
一方、間隔Gを２のべき乗など、最終的にソート対象にならない要素がたくさんでるような
規則的なものにすると、効率は良くならないらしい。

ちなみに、挿入ソートは安定的だが、シェルソートは安定的でない。
(まあ、指定間隔で初期順序をシャッフルしてしまうので・・・。)

計算量はO(N^1.25)程度なようだ。求め方はわからないですが・・・。
論文等があれば更新したい。

■ソースgithub.com

■参考URL(処理方法のイメージ動画)www.codereading.com
■参考URL(間隔に関する考察)
シェルソートと間隔hの決め方【C++】 - Programming Magic

■参考資料

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造