サイエンスものおきば

　New Scientist より。

■ 暴かれた：グリーンな消費者の外聞の悪い秘密
　Exposed: green consumers' dirty little secrets

　環境にやさしいモノを買うと、私たちの心もやさしくなれる。・・・エコ製品の宣伝でありそうなフレーズですが、最新の心理学の実験結果によると、実際はその逆かもしれません。環境にやさしいモノを買うことによって、人の行動は、ウソをつくなど、よりモラルを欠くように変わることが明らかになりました。

　カナダのトロント大学の Nina Mazar と Chen-Bo Zhong は、オンラインショッピングを題材にこんな実験を行いました。

　研究者たちは、ボランティアの学生を集め、オンラインショッピングのサイトで２５ドルの買い物をするよう指示しました。被験者は２つのグループに分けられていました。一方のグループは、蛍光球のような「環境にやさしい」商品ばかりが並べられたサイトで買い物をし、もう一方は、白熱球のような従来の商品ばかりのサイトで買い物をしました。

　さらに買い物の後で、学生たちは次の２つのタスクを行いました。１つ目のタスクは最後通牒ゲームと呼ばれるものです。詳しいルールは「セクシー画像で男の決断力は鈍る」などを参照して下さい。６ドルのお金を相手と配分するよう指示したところ、環境にやさしい商品を買った被験者のほうが、自分の取り分を高く設定することが分かりました。

　もう１つのタスクは、画面に表示されたドット数を比べるというタスクでした。左右に区切られた四角形の中に描かれた２０個のドットを見て、左右どちらに多くのドットがあるかを答えるというものです。正解・不正解に関わらず、左と答えると０．５セント、右と答えると５セントが賞金として得られます。こうしたタスクを９０回行いました。このタスクでも両被験者に違いが見られました。環境にやさしい商品を買った被験者は、右と答える割合が明らかに高く、従来型を買った被験者よりも、平均０．３６ドル高い賞金を得ていました。賞金ほしさにウソをついたと見られるのです。

　これだけではありません。タスクの終了後、被験者にはお金がいくらか入った封筒が渡され、賞金をそこから取るよう指示されました。やはりここでも両被験者の行動に違いがありました。エコな買い物をした被験者は、そうでない被験者と比べて、平均０．４８ドル高い額を取っていきました。盗みをはたらく割合が高かったのです。

　研究者らは、こうした現象には「モラルの自己許諾（"Moral self-licensing"）」という原理が背景にあると考えています。つまり、環境にやさしい商品を買うなどの、自分が倫理的に良い行動をしていると感じると、「非社会的で倫理的に問題のある行動をとってもよい」と考えるようになるというのです。免罪符を手に入れた気持ちになるのです。

　モラルの自己許諾は、人種差や性差などの領域で知られつつある現象です。はたしてモラルの自己許諾が今回の結果にどのぐらい影響しているかは検討の余地がありますが、エコに関する消費行動が、私たちの社会的・倫理的行動にふかく関連していることが明らかになった、と彼女たちは結論付けています。

　なるほど・・・。なかなか手の込んだ実験をやっているなあと感じました。特に、賞金をわたす場面も実は調査の一部になっているのは面白いですね。調査が終わったと見せかけて油断したところも実はチェックされてるという。

　とはいえ研究者自身も述べているように、エコな行動が直接的に倫理性を左右しているかというのはさらなる証拠がいるかもしれないと感じました。もしかすると、エコの倫理的なよしあしが影響してるんじゃなくて、目新しさとか、別の要因が効いてる可能性だって考えられる。より詳細が明らかになって欲しいところです。

【参考リンク】
・元論文：Do Green Products Make Us Better People? （ここに本文あり。）

　Science NOW より。

■ 両生類で初めて一夫一妻制がみられた
　Monogamy Seen in Amphibians for First Time

　まずはこの画像をご覧ください。アマゾンに生息する Ranitomeya imitator というカエルです。体長約２センチ。目を引くたいへんカラフルな外見です。さてこのカエル、けばけばしい見た目とは裏腹に、その夫婦活動はたいへん誠実であることが分かりました。両生類としては初めて、一夫一妻制をとることが明らかになったのです。

　このカエルはいったいどんな夫婦生活を営むのでしょうか。それを知るには、近縁種の Ranitomeya variabilis の生活と対比させてみると面白いです。

　この２種は非常によく似た外見をしています。いずれも大声で鳴いて求愛します。母カエルは葉の上に卵を産み、オスが卵を育てます。卵が孵ると、父カエルはオタマジャクシを背中に乗せて近くの水たまりへと運びます。

　ここから先の育て方は両種で異なります。R. variabilis では、母カエルは卵を産むとどこかに行ってしまい、父カエルは水たまりの周辺を警護します。基本的に子のことはほったらかしです。一方、R. imitator は、子をたいへん手厚く育てます。引越し後の数ヶ月間、父は週１回、母を水たまりへと連れてきます。そこで母カエルは、栄養たっぷりの食用の卵を産み与えます。子どもたちが大きくなるまで、両親が食事の面倒をみているのです。

　いったいなぜ、R. imitator はここまで子どもたちを過保護に育てるのでしょうか？ 研究者らは、リソースの量に何か関係があるのではないかと考えました。彼らは４０４種ものカエルに関する文献を集め、水たまりの大きさと彼らの習性との間に関連性がないか調べました。結果は特徴的でした。小さい水たまりに住まわせる習性のあるカエルほど、より過保護な子育てをしていたのです。

　さらに研究者らは、R. imitator の親子のＤＮＡを採取して調べました。この結果からも、このカエルが一夫一妻制をとる証拠が得られたとのことです――この発見は両生類で初となるものです。

　実際のカエルたちの生活もモニタされました。１２匹の R. imitator を追跡調査したところ、うち１１匹は交配シーズンになると同じパートナーを選んでいました。

　とはいえ、R. imitator がなぜ一夫一妻制をとるのか、その根本的な理由はまだ明らかになっていないません。どの方向に進化が起きたのかを含め、今後明らかにすべき点のようです。

　なるほど。。。ＤＮＡ調査や追跡調査など、いろんな角度から調べられていておもしろいです。葉から父カエルが子を運ぶなんて習性も初めて聞いたので驚き。

【参考リンク】
・元論文：A Key Ecological Trait Drove the Evolution of Biparental Care and Monogamy in an Amphibian

　New Scientist より。

■ 鳴る携帯電話を叩いて静かにする
　Silence that ringing cellphone with a whack

　映画館で感動的なシーンに、オフにし忘れたケータイ着信音が鳴り響く・・・慌ててポケットに手を突っ込むものの、つっかえてなかなか出てこない。やっとオフにできたときには既に遅し、すっかり白けた周りの視線の集中砲火。・・・こんな縮み上がるような思いをした人に朗報です。ポケットの上からケータイを叩くだけで音を止めることが可能になりそうです。

　この方式は、ピッツバーグのカーネギーメロン大学の Scott Hudson と Chris Harrison、および Intel 研究所の人々によって開発されました。

　この方式の仕組みはたいへん分かりやすいです。最近のケータイは多くに加速度センサーが搭載されています。彼らは、センサーから得た衝突や振動の数値をもとに、「叩く」動きが行われたか否かを検出するアルゴリズムを開発しました。叩く動きに対し、例えば着信音を止めるといったコマンドを割り当てたのです。

　しかし、どのぐらい正確に検出できるものなのでしょうか。彼らはこれを確かめるために、１１人のボランティアで次のような実験を行いました。ボランティアたちは加速度センサーのついたデバイスをポケットに入れて２時間外出しました。そして研究者が指示したタイミングで叩く動作を行ったところ、その全てを正しく検出することができたということです。誤検出（実際には叩いてないのに間違って検出してしまう）があったのは１人だけでした。

　将来の商用化について研究者はこう考えています。ポケットの中のケータイは向きを特定するのが困難なので、たくさんの動きのパターンを割り付けることは難しいが、それで実用上は問題ないだろうと。例えば着信音が鳴っているときであれば、マナーモードに変えるか、もしくは自動応答に切り替えるか、の２パターンだけあれば十分かもしれないと述べています。

　なるほど。これは結果がはっきりしていて分かりやすいです。わりとすぐに実用化されそうな雰囲気です。着信音やアラームを止めるという用途の以外にも、犯罪に巻き込まれた時の緊急通報用にも用途があるかもしれません。誤検出されない複雑な動作（１０回連続で叩くとか）に割り当てておいて、誘拐などのトラブルに遭遇したときに動作を行えば、自動で位置情報と一緒に警察に連絡がいくとか・・・。特に日本で好まれそう？

【参考リンク】
・元論文：Whack Gestures: Inexact and Inattentive Interaction with Mobile Devices Tangible, Embedded, and Embodied Interactionという学会で発表されました。（や さん情報ありがとうございます！）

　Science NOW より。

■ 恐ろしい記憶の消去にはタイミングが重要
　Erasing Scary Memories Is a Matter of Timing

　戦争や事故など、凄惨な体験によってＰＴＳＤを患った人々が世の中には数多くいます。そうした人々から恐ろしい記憶を取り除いてやることができないものか――「記憶の再統合」と呼ばれるプロセスを狙い撃ちにする手法によって、薬物のリスクなしで恐ろしい記憶を消去できる可能性が新たに示されました。

　僕たちの頭の中で、記憶がどのようなプロセスを経るかについては、既に多くのことが知られています。中でも、「記憶の再統合（reconsolidation）」というプロセスは、短期記憶が長期記憶へと移行する過程のことをさし、これが記憶の消去に重要な役割をもつと考えられています。薬物を使うことでこのプロセスを阻害できることは知られていましたが、これには副作用のリスクが大きく、人間に対して用いることはできませんでした（*1）（*2）。

　そこで今年の初めに発表された研究では、ラットを対象に、「記憶消去のトレーニング（extinction training）」をやらせることで、薬物を使わずに恐ろしい記憶を消去できたと報じられました。この研究では、まずブザー音を鳴らした後でラットに電気ショックを与えました。これによりラットはブザー音を聞いただけで恐怖の記憶を呼び覚ますようになりました。そしてその後、電気ショックなしでブザー音を繰り返し聞かせるという、「記憶消去のトレーニング」を行いました。研究者らは、ラットの脳内で「記憶の再統合」が行われているタイミングを狙ってトレーニングを行うことで、恐怖の記憶が不安定化し、以後、ブザー音を聞いても怯えを見せなくなることを突き止めました（*3）。

　しかしながら、上記の研究はラットが対象でした。これまでのところ、人間を対象にした実験というのはなされていませんでした。

　ここまでが前置き。さて今回、ニューヨーク大学の認知神経学者 Daniela Schiller と Elizabeth Phelps は、同様の手順を人を相手に行いました。

　彼女らはまず、被験者らに、不快な体験を記憶づけました。コンピュータ画面上の青または黄色の正方形を見せ、青のときだけ、被験者の手首に軽い電気ショックを与えました。これにより被験者は青い正方形と恐怖とを関連づけました。記憶づけ後の被験者に、青い正方形を見せてみたところ、電気ショックを与えなくとも、皮膚上の微少な電流に変化が見られるようになりました。青い正方形から恐怖の記憶を呼び覚ましたのです。

　そしてその１日後、被験者らは「記憶消去のトレーニング」をおこないました。電気ショックを与えずに、青い正方形を繰り返し見せたです。以前の研究でネズミが受けたトレーニングとよく似ています。

　被験者は３つのグループに分けられていました。最初のグループは、トレーニングの１０分前に、記憶を思い出すため、青い正方形をもういちど見せられました。また別の３分の１は、トレーニングの６時間前に正方形を見て記憶を思い出しました。残る３分の１は記憶の思い出しは行いませんでした。

　記憶消去のトレーニングを行ったさらにその１日後、研究者は、すべての被験者に青い正方形をふたたび見せました。すると、その反応はグループによって異なっていました。トレーニングの１０分前に思い出しを行ったグループは、青い正方形を見ても特に恐怖を感じませんでした。しかし一方で、６時間前に思いだしを行ったグループ、思い出しを行わなかったグループは、いずれも皮膚の電流に変化が見られたのです。この傾向は１年後も同じでした。

　人間において、通常、記憶の再統合は、記憶の思い出しが行われてから３分後にはじまります。すなわち、思い出しの１０分後に記憶消去のトレーニングをやったグループにおいて、恐怖の記憶が消去されたと考えられるのです。記憶が不安定になる再統合のあいだを狙い撃ちすることで、記憶を根本から変えたのだと研究者は述べています。

　なるほど。。。記憶を思い出してから１０分後、というのが消去のトレーニングを行う上ではポイントになるようです。非常に複雑と思われる人間の記憶が、こんなにシンプルな実験で明らかな違いが見られたというのは驚きです。

　とはいえ元記事でも言及されているように、今回のようなトレーニングが、戦争や事故のような類の記憶の消去に対しても同じように効果があるかという点は注意しないといけません。人生観が変わってしまうほどの強烈な記憶だと、記憶消去のトレーニングがかえって恐怖の呼び水となる可能性だってあるかもしれない。今後の発展に期待です。

【参考リンク】
・（*1）科学ニュースあらかると：：特定の記憶を消せるだろうか
・（*2）マウスの記憶の選択的消去が可能になった
・（*3）Extinction-Reconsolidation Boundaries: Key to Persistent Attenuation of Fear Memories
・元論文：Preventing the return of fear in humans using reconsolidation update mechanisms

　Sciense NOW より。

■ 酸性の海洋はいくらかの海洋生物には恩恵かもしれない
　Acidic Oceans May Be a Boon for Some Marine Dwellers

　海洋の生物にとって、ＣＯ_２の増加による海の酸性化は常に危険なものである。従来はこのように考えられていましたが、最新の研究にて、必ずしもすべての生物でそうとは限らない可能性が指摘されました。ある種の生物では、海水の酸性化によって甲殻が大きくなるという、予想外の現象が見られたのです。

　以前の研究では、ロブスターやサンゴなど、身体が甲殻などで覆われた生物は、海洋酸性化によって甲殻が失われることが予見されていました。これにより病気や補食者、外的ストレスで死ぬ可能性が高くなると考えられていました。

　しかし、ノースカリフォルニア大学の海洋科学者 Justin Ries らは、ある種の生物では、むしろ逆に、より発達した甲殻が得られることを発見したのです。

　彼らは、酸性度を４通りに分けた水槽に、１８種類の生物をそれぞれ住まわせました。水槽の１つは、酸性度が現在のＣＯ_２のレベル相当に合わせられ、他の３つの水槽は、それぞれ工業化時代以前の２倍、３倍、１０倍のＣＯ_２のレベルに合わせられました。今から１００～７００年後の想定レベルです。

　こうした環境で育った生物には興味ぶかい特徴が見られました。ワタリガニ、ロブスター、エビは、１０倍のＣＯ_２レベルに合わせた環境でも生存できただけでなく、より重量の大きな甲殻を得ていたのです。反対に、アメリカガキ、ホタテガイ、サンゴ、チューブワームは甲殻が弱くなりました。二枚貝やパイプウニは、１０倍の環境では甲殻がすっかりなくなってしまいました。

　いったいなぜこのような違いが見られたのでしょうか？ 研究者たちは、この原因が甲殻の炭酸カルシウムの種類によることを突き止めました。が、これが全ての理由を説明するとは限らないようで、詳細な調査が今後必要です。

　また、甲殻が大きくなることによって、実際にどのような生存上の違いがあるかについても、まだハッキリとはしないようです。防御が高まるというメリットは期待できそうですが、一方で、甲殻の生成にエネルギーを費やすため免疫上のデメリットなどが存在する可能性があります。海洋酸性化がこれらの生物にとって本当にプラスだとは現時点では言い切れず、研究者自身、「酸性化への生物の反応は、私たちが思うよりもはるかに繊細で複雑である」と言うにとどめています。

　なるほど。海水の酸性度が高くなると甲殻は溶けてしまうというイメージがあるだけに、今回の反対の結果は意外に感じます。なお、当然ですが、今回の結果からは「酸性化を抑止する必要はない」という主張を引き出すことはできませんのでご注意を・・・。

【参考リンク】
・元論文：Marine calcifiers exhibit mixed responses to CO2-induced ocean acidification

　ABC Science より。

■ オバケを怖がるのは誰かを示す研究
　Study finds who is afraid of the bogeyman

　夜、子供が悪夢を見てすっかり怖がってしまいました。そんなとき、親は何と言って安心させてあげればよいでしょうか？ 新たな研究が示唆するところによると、その前にまず、どんな生き物が夢に現れたのか、尋ねてみるのがよいようです。

　米国カリフォルニア大学の心理学者 Liat Sayfan 博士は、自身の子育ての経験から、夢の中に出てきた生き物が、実在の生き物なのか、それとも空想の生き物なのかによって、子供の恐がり方が異なることに気がつきました。

　そこで彼女は、このことをよりきちんと調べるため、４８名の子供（４～７歳）を集め、ある物語を聞いてもらうという実験を行いました。物語は２種類ありました。ひとは、熊のような実在の怖い生き物に遭遇するという物語、ひとつは、魔女のような架空の生き物と遭遇する物語でした。いずれも、子供たちを本当に怯えさせてしまわないよう、あるキャラクターが主人公となっていました。

　彼女らは、聞いた後の子供たちに、物語の内容について尋ねました。

　結果はこうでした。実在の生き物の話を聞いた子供たちの反応は、性別によって異なっていました。男の子は、生き物をやっつければよいと話し、女の子は、逃げてお父さんお母さんを見つければよいと話しました。いずれも、怖い生き物を避けようとする反応を示したのです。

　一方、空想の生き物の場合は性別の違いは見られませんでした。その代わりに、年齢による違いがありました。

　未就学の子供は、状況を良いものにしようとする反応を示しました。この魔女は本当は良いおばあさんだ、などと答えたのです。一方、６、７歳の子供たちはこれとは対照的な反応を示しました。この生き物は実在していない、などと答えたのです。

　彼女はこう説明します。４歳の子供は、現実と空想の生き物の違いは分かっていても、いざ恐怖に対処するとなると、この知識をうまく使えないでいます。すなわち、空想に没頭し、現実を考えられない状態になるというのです。７歳頃になってやっとうまく知識を使えるようになるのだと述べています。

　したがって、もし幼い子がオバケの夢を見て怖がっていた場合、どう言って安心させてあげればよいか。今回の研究から言えるアドバイスはこうです。「オバケなんてウソさ」ではなく、「このオバケさんは実はとっても心が優しいんだよ」と、教えてあげましょう。

　なるほど・・・。記事には詳しい集計方法や具体的な数字が書かれておらず、確かなことは元論文を参照する必要がありますが、それでもアドバイス自体は、確かにそうかも、とつい頷いてしまう内容です。子供のいる方はぜひ再検証の実験をやってみて下さい。

【参考リンク】
・元論文：調べ中

　Sciense NOW より。

■ 液滴の場合、正反対同士は反発しあう
　In the Case of Droplets, Opposites Repel

　正と負、逆の電荷をもった物体は互いに引き寄せあう。言うまでもなくこれは何百年ものあいだ常識とされてきた現象ですが、今回 Nature 誌に報告された研究によると、ある条件ではこれと正反対の現象、つまり物体が反発しあうことが分かりました。

　この発見をしたのは、カリフォルニア大学の化学工学者 William Ristenpart らです。彼らは、きわめて大きな電荷をもった液滴にかぎっては、逆電荷の液滴どうしを近づけてもくっつこうとせず、むしろ元の形に戻ろうとすることを発見しました。

　一体どのような仕組みなのでしょうか？ 彼らはこれを解明すべく、高速ビデオカメラを使って液滴の形状を調べました。

　結果、カギは液滴の表面にできる円錐状の変形にあることが分かりました。異なる電荷の液滴を近づけたとき、液滴の形に変化が生じます。相手に近い部分の表面が盛り上がって、山のような形になるのです。中程度の電荷の場合、山はずんぐりとした低い形になります。しかし一方で、高電荷の場合は鋭くとがった形の山ができるのです。

　この違いがどう効いてくるのでしょうか。さらに近づけていって二つの液滴が接触すると、両者のあいだに細いブリッジができます。このとき、接点部分の電場の大きさは打ち消しあって非常に小さくなるため、液滴の形状はおもに表面張力のみに依存して決まることになります。

　表面張力は、山の角度によって働く向きが変わります。ずんぐりした山の場合、表面張力は引き合う方向、つまり液滴が一つになる方向にむかって働きます。一方、とがった山の場合、引き戻す方向に働きます。結果、ブリッジは壊れ、液滴どうしが反発するようにふるまうのです。

　実際、かれらは。両方のふるまいの境目となる角度と電荷、すなわち「臨界角」と「臨界電荷」があることを突き止めました。

　今回の結果は、石油工業への応用が大きく期待されています。現在、原油から水分を取り除くプロセスでは、電界をかけるという処理が行われており、この処理で効率化がはかれるようになるだろうと述べています。

　リンク先の元記事には、液滴がぶつかる様子をとらえたムービーがあります。二つの液滴がビリヤードの球のようにバウンドする姿が見られますのでどうぞご覧になって下さい。それにしてもよくこんなバッチリな瞬間を撮影できたなあ・・・。

【参考リンク】
・元論文：Non-coalescence of oppositely charged drops

これまで、初級編、中級編の２問を題材に説明してきました。最後は、さらに難度の上がった問題を解きます。上級編の問題はこれです。

【上級問題】 ６枚のタイルが横１列に並んでいる。 いま、左端のタイル（S）上に１匹のバッタがいる。バッタは次のルールにしたがってジャンプを繰り返し、右端のタイル（G）に向かう。
・バッタは右または左方向にジャンプする。任意の枚数のタイルを飛び越え、他のタイルに着地する。
・バッタはジャンプすると、次はその反対方向にジャンプする。
・バッタはGに到着する前に、他のすべてのタイルにちょうど一度ずつ着地する。Sは始めから着地済みとみなす。
このようにGへ到着する仕方は、全部で５通りある。
２０枚のタイルが横１列に並ぶとき、Gへ到着する仕方は何通りあるか？

前の２問とかなり雰囲気が異なる問題です。こうしたいわゆる数え上げの問題も、プロジェクトオイラーではよく出題されます。

さて、どうすれば解けるでしょうか。とりあえず、紙にペンで２０個のタイルを書いてみるわけですが、膨大なパターンを数えないといけないことに気付きます。どう数えたらよいか、途方に暮れる人もいるのではないでしょうか。

■ 問題をサイズダウンする

そんなときに有効な考え方として、「大きすぎる問題を小さな問題に分割する」やり方を試してみましょう。問題のサイズを一回り小さくすることによって、再帰的にパターン数を表せないか考えるわけです。

問題サイズを小さくするというのは、この場合は途中経過の様子を思い浮かべることを意味します。こうしたことを考えながら、しばらく図を眺めてみると、ある事実に気がつきます。結局のところ、Gへ着くパターン数は、「バッタの左側にある未訪問のタイル数と、右側にある未訪問のタイル数」のみによって決まっているのです。下の２つの例（訪問済みのタイルを水色で示しています）のように、バッタの左と右にある未訪問のタイル数さえ一緒なら、このあとGに着くパターン数は同じになるのです。

この事実に気が付けば、バッタの左と右の未訪問タイル数が left と right のときのパターン数を求める get_count(left, right) という関数を作ればよいと分かります。関数内では、次の一手によって場合分けして、それぞれ対応する引数で get_count を再帰的に呼んでやります。

コードは以下です。

#include <stdio.h>
#define N 20

long long get_count(int left, int right)
{
　　long long count = 0;
　　if (left == 0 && right == 0) return 1;
　　if ((left + right) % 2 == 0) {　　// 左にジャンプする
　　　　for (int i = 0; i < right; i ++) {
　　　　　　count += get_count(left + i, right - 1 - i);
　　　　}
　　} else {　　// 右にジャンプする
　　　　for (int i = 0; i < left; i ++) {
　　　　　　count += get_count(i, left + right - 1 - i);
　　　　}
　　}
　　return count;
}

int main(int argc, char* argv[])
{
　　long long count = get_count(0, N - 2);
　　printf("%I64u\n", count);
　　return 0;
}

しかしながら、実行しても、何時間経っても一向に終了しません。どうやらさらにもう一ひねりが要るようです。

■ メモ化探索による改良

そもそも上のプログラムは、バッタの次の可能な行き先ごとに get_count を繰り返し呼びます。その先では、さらにその次の可能な行き先ごとに呼びます。つまり、計算を進めるごとに、関数を呼ぶ回数が爆発的に増えてしまうのです。これが、いつまで経っても終わらない理由です。

そこで、「メモ化探索（メモイズ）」というプログラミングのテクニックを使うことにしましょう。メモ化探索とは、過去に行った計算結果をキャッシュしておいて 同じ引数の計算に対して高速化を計ることを言います。

ある left と right の組み合わせのときの関数の結果を覚えておく２次元配列 memo を用意しました。始めに要素を -1 で初期化しておき、get_count() の先頭でキャッシュが計算済みかを調べます。改良後のコードは次の通りです。

#include <stdio.h>
#define N 20
#define UNDEF ((long long)(-1))
long long memo[N][N];

long long get_count(int left, int right)
{
　　if (memo[left][right] != UNDEF) return memo[left][right];
　　memo[left][right] = 0;
　　if (left == 0 && right == 0) return 1;
　　if ((left + right) % 2 == 0) {　　// 左にジャンプする
　　　　for (int i = 0; i < right; i ++) {
　　　　　　memo[left][right] += get_count(left + i, right - 1 - i);
　　　　}
　　} else {　　// 右にジャンプする
　　　　for (int i = 0; i < left; i ++) {
　　　　　　memo[left][right] += get_count(i, left + right - 1 - i);
　　　　}
　　}
　　return memo[left][right];
}

int main(int argc, char* argv[])
{
　　for (int i = 0; i < N; i ++)
　　　　for (int j = 0; j < N; j ++)
　　　　　　memo[i][j] = UNDEF;　　// キャッシュの初期化
　　long long count = get_count(0, N - 2);
　　printf("%I64u\n", count);
　　return 0;
}

さて、結果はどうでしょうか。

すぐに答え 2404879675441 が得られました。

■ さらに優れた洞察

もしあなたが、「結局これって、オイラー数（通称ジグザグ数）を求めればいいだけじゃないの？」と気づいたのであれば、さらにずっと短い手順で答にたどり着くことができます。詳しくはこちらなどを参照して下さい。

以上、３つの例題を使ってプロジェクトオイラーの問題を解いてみました。実際の問題は、これよりもずっと複雑なコーディングや、難しい数学の知識を必要とするものが多く出題されてます。ランキングの上位を狙うもよし、素晴らしいアイデアをフォーラムに投稿するもよし、いろんな遊び方を試してみてください。

最後に僕自身の思いを。プロジェクトオイラーのよいところは、解くのに制限時間が設けられていない点だと思っています。急いで答えを出すプレッシャーがなく、リラックスして問題に挑めるし、また電車内や待ち時間にぼんやりと解法を練ってもよいです。また、複雑なプログラムを細かくデバッグして、やっと正解が得られたときの満足感は、テレビゲームよりもずっと高いと思ってます。全問正解にはまだ何十問か足りませんが、いずれ世界トップにこれたらいいなあ。

今回は、初級編からさらに一歩進んだ難度の問題を解いてみます。中級編の問題はこれです。

【中級問題】 344 という数は面白い性質を持っている。 344 の平方根を小数表示した √344 = 18.547236990・・・ は、小数点を無視すると、先頭の９桁に１から９までの数字がちょうど一度ずつ現れる。344 はこのような性質を持つもっとも小さな整数である。 31078 もこの性質を持つ。√31078 = 176.28953457・・・である。31078 はこの性質を持つ10番目に小さな整数である。 この性質を持つ160万番目に小さな整数を求めよ。

初級編と比べて、すこし複雑になりました。うまく解くにはいくらか工夫が必要になります。

■ 単純なアプローチではうまくいかない

さて、この問題はどのように解けばよいでしょうか？

単純に考えると、344 以上の数について、片っぱしから、条件を満たすかどうか調べるやり方が思いつきます。まずはこの方法でやってみることにしましょう。

条件を満たしているかのチェックには少しプログラミングの腕が必要です。ここでは、C 標準関数の sqrt() を使って平方根の小数表示を得たあとで、整数部分が９桁になるまで小数点を右に移動させ、それを unsigned int 型にキャストして小数部分を落とします。次に１~９の各数字が使われたかを記録する bool 型の配列を用意して、各桁が他と重複していないか調べます。どれも重複していなければ、条件を満たしていると判定します。

以上の手順をコードに書きました。is_root_pandigital() という関数で、平方根が条件を満たすかのチェックを行っています。また、count という変数で、見つかった個数をカウントしています。count が 10000 増えるごとに進捗状況を出力させています。

#include <stdio.h>
#include <math.h>
#define N 1600000

bool is_root_pandigital(unsigned int n)
{
　　double r = sqrt((double)n);
　　while (r < 100000000.0) r *= 10.0;
　　unsigned int m = (unsigned int)r;
　　bool b[10];
　　b[0] = true;　　// ゼロは現れてはならない
　　for (int i = 1; i < 10; i ++) b[i] = false;
　　for (int i = 1; i < 10; i ++) {
　　　　if (b[m % 10]) return false;
　　　　b[m % 10] = true;
　　　　m /= 10;
　　}
　　return true;
}

int main(int argc, char* argv[])
{
　　int count = 0;
　　for (unsigned int n = 1; ; n ++) {
　　　　if (is_root_pandigital(n)) {
　　　　　　count ++;
　　　　　　if (count % 10000 == 0) printf("%d %u\n", count, n);
　　　　　　if (count == N) {
　　　　　　　　printf("%u\n", n);
　　　　　　　　break;
　　　　　　}
　　　　}
　　}
　　return 0;
}

さて、コードを実行してみましょう。

３分後の出力が上です。見ての通り、たった17万個しか見つかっていません。このペースだと、160万番目が見つかるのは約半時間後ということになってしまいます。

ここで、プロジェクトオイラーのもう一つの重要なルール、「１分ルール」について説明します。１分ルールというのは、「工夫したプログラムを書けば、たとえ低速なマシンでも１分以内の実行時間で正答を得ることができる」という原則のことです。プロジェクトオイラーで出題される問題は、すべてこの原則にもとづいて作成されています。

つまり、上のような何十分もかかるプログラムは、出題者の期待するレベルに達していないということです。

ではどうすればよいか？ 一つは、ひたすらプログラムの完了を待つというものです。もちろん、これでも正答を得ることは可能ですし、こうしたやり方が禁止されているわけではありません。ですが今回はせっかくですので、１分ルールを満たすようにプログラムを改良してみましょう。

■ 改良：固定する数を変える

とは言っても、一体どこをどう改良すればよいのでしょうか？ 整数をしらみつぶしに探すというさきほどのアプローチは非効率すぎたわけです。発想を変えましょう。整数を選ぶのではなく、「先頭に１~９が一度ずつ現れる数をまず固定する」と考えてみましょう。

どういうことか？ 17923.4658 という数を例にとります。これは先頭の９桁に１~９が一度ずつ現れる数です。ここで、「平方根が 17923.4658・・・ となるような整数は何か？」と考えるのがこのアイデアのポイントです。このような整数を探すのは容易です。17923.4658 ≦ √n ＜ 17923.4659 を満たすような整数 n を探せばよいわけです。各辺を２乗すれば 321250626.28376964 ≦ n ＜ 321250629.86846281 ですから、そのような n は 321250627、321250628、321250629 の３つだと分かります。

つまり、先頭に１~９が一度ずつ現れる数を小さい順に生成し、それぞれに上の手続きを使って n を求めればよいということです。

以上の内容をプログラミングしました。１~９が一度ずつ現れる数を小さい順に生成するのは少し大変ですが、順列生成としてよく知られた手順ですので、自作したり、うまくネット上のコード（ここなど）を再利用したりして下さい。下記では STL の next_permtation() を使いました。

また、同じ数を重複カウントしてしまわないように、未カウントの最小の整数を n_next に記録しました。

#include <algorithm>
#include <stdio.h>
#define N 1600000

int main(int argc, char* argv[])
{
　　int count = 0;
　　for (int d = 100000000; d > 0; d /= 10) {
　　　　char c[] = "123456789";
　　　　unsigned int n_next = 1;
　　　　do {
　　　　　　int m = atoi(c);
　　　　　　double d0 = (double)m / d;
　　　　　　double d1 = (double)(m + 1) / d;
　　　　　　unsigned int n0 = (unsigned int)(d0 * d0) + 1;
　　　　　　unsigned int n1 = (unsigned int)(d1 * d1);
　　　　　　if (n0 < n_next) n0 = n_next;
　　　　　　for (unsigned int n = n0; n <= n1; n ++) {
　　　　　　　　count ++;
　　　　　　　　if (count % 10000 == 0) printf("%d %u\n", count, n);
　　　　　　　　if (count == N) {
　　　　　　　　　　printf("%u\n", n);
　　　　　　　　　　goto end;
　　　　　　　　}
　　　　　　　　n_next = n + 1;
　　　　　　}
　　　　} while (std::next_permutation(c, c + 9));
　　}
end:
　　return 0;
}

実行結果は次のとおりです。

一瞬で答え 3951343689 が得られました。

と、発想を変えるだけで、圧倒的に早く答を得られるようになったことが分かると思います。プロジェクトオイラーでは、素朴なアプローチではうまくいかず、高速化が必要になる問題が出てきます。すでに正解した問題でも、１分ルールを満たすようにアプローチを変えたり、より高速になるようプログラムを改良したりするのも面白いですね。

なお、プロジェクトオイラーでは、正解者専用の掲示板が各問ごとに設けられています。他の参加者の優れたアイデアを学んだり、自分のプログラムを披露したりするのも楽しいでしょう。

以上で中級編の説明を終わります。次回は、さらに難度が上がり、ぱっと見ただけではアプローチが思い浮かばない上級編に取り組んでいきます。

前回の導入編では、プロジェクトオイラー（Project Euler）の概要を紹介しました。本記事では、実際にどんなふうに問題を解いていくか、その様子を述べてみようと思います。

それではさっそく問題にトライしてみましょう。本来なら、実際の問題を使うところなのですが、ネタバレはできるだけ書きたくないので、実物を模したオリジナル問題を３つ（初級、中級、上級）作ってみました。これを題材に、プロジェクトオイラーへの取り組み方を見ていきましょう。

初級編はこんな問題です。

【初級問題】 よく知られているように、２は１番目の素数であり、３は２番目、５は３番目、７は４番目の素数である。 n 番目の素数 p に対し、n もまた素数である場合に、p を「素数番目の素数」と呼ぶことにしよう。 ３と５は素数番目の素数だが、２と７はそうではない。 １００万以下の素数番目の素数の総和を求めよ。

素数をテーマにした問題です。プロジェクトオイラーでは、素数をあつかう問題がとてもよく出されます。

■ 初級編を解いてみよう

さて、この問題はどうすれば解けるでしょうか？ ぱっと考える感じ、条件に合う素数をすべて見つけて、順に足し算してやればよさそうです。そこでまずは１００万以下の素数をすべて求めて、何番目かを先頭からチェックしていく、というアプローチで進めてみましょう。

１００万以下の素数をすべて求めるにはどうすればよいでしょうか？ 素数のリストを求めるアルゴリズムとしてよく知られた「エラトステネスのふるい」が有効そうです。これを使って求めてみましょう。

エラトステネスのふるいについてはウィキペディアの記事（これ）を参照して下さい。まず１００万以下の整数を羅列して、２の倍数をすべて消す、３の倍数をすべて消す、４の倍数をすべて消す・・・という作業を１０００まで繰り返します。最後までやると、素数のみが消えずに残るというしくみです。

こうして得られた素数のリストを、n の値を１ずつ増やしながら順にたどり、n が素数であれば和に加えます。n が素数かどうかの判定には、いま作ったふるいがそのまま利用できます。

■ コードを書いてみる

以上の手順をＣのコードに書きました。

#include <stdio.h>
#include <string.h>
#define N 1000000

int main(int argc, char* argv[])
{
　　bool prime[N];
　　memset(prime, 1, sizeof(bool) * N);
　　prime[1] = false;　　// 1 は素数ではない
　　for (int d = 2; d <= 1000; d ++) {
　　　　for (int i = 2 * d; i < N; i += d) {
　　　　　　prime[i] = false;
　　　　}
　　}
　　unsigned int sum = 0;
　　for (int p = 2, n = 1; p < N; p ++) {
　　　　if (prime[p]) {
　　　　　　if (prime[n]) {
　　　　　　　　sum += p;
　　　　　　}
　　　　　　n ++;
　　　　}
　　}
　　printf("%u\n", sum);
　　return 0;
}

結果は次の通りです。

結果、3475059124 という答が得られました。実際にはこのあと、問題ページにあるテキストボックスに回答を入力し、正解かどうかをチェックします。みごと合っていれば、正解アイコンが現れます。

初級編はわりと単純な問題でした。次の中級編では、ひと工夫が必要な、より難度の高い問題にトライしていきます。