2015年2月アーカイブ

2015年2月23日

学食やばい

 京大に行ってました。
 きれい系の学食カンフォーラでランチ。
 店内の雑誌棚に置いてあるのが、「日経サイエンス」「ナショナルジオグラフィック」「サライ」「ダヴィンチ」「芸術新潮」というラインナップ。
 違うでしょう。そういうのは、客側がドヤ顔で持ち込んで読むものであって、店側が自分で置いとくものじゃないでしょう。

 ...などと思っていたわけですが、ふと周りの客の読んでいる本のタイトルを見ると、僕の右隣りの人が「ドン・キホーテ」、左隣りの人が「イプシロン・デルタ法」だったわけで、なんというか自分の思考の浅はかさを思い知らされたのでした。

 写真は特に意味なく品川駅。
 

2015年2月15日

プロジェクトオイラーで出題した問題が20問になりました

 プロジェクトオイラーにこれまでに提案した問題が20問になったので、背景のこととかを書いてみます。
 最初の10問ぶんについてはこちら。今回は後半の10問ぶんについて書きます。

 20問とはいえ、すべてが自分のアイデアだけで作ったわけではないです。他の開発メンバーからのアイデアで内容が変わったりしてます。もちろん反対に、自分が他のメンバーの提案した問題にアレンジを加えたりもしているので、20問という数字にとりわけはっきりした意味があるわけではないです。自分が言い出しっぺの問題、というぐらいの意味で・・・。

426. Box-ball system

 箱玉系という1次元セルオートマトンを題材にしました。日本語では箱玉系と呼ばれています。
 ヒントなしで解こうとすると非常に難しい問題で、関連論文をリサーチすることが必要になると思います。箱玉系には特に日本に多くの研究者がいるようで、ネット上には日本語の関連論文がたくさん見つかるので、日本人にはかなり有利だったかもしれません。ただ、本問は調べた公式で一発で解けてしまうわけではなく、さらにそこからもう一ひねりあるので、まあこのようなリサーチ前提の問題もアリかなと思っています。(リサーチなしでもちゃんと考えれば解けるよ、という意見もチーム内ではありましたが。)

430. Range flips

 期待値に関するとある性質を利用した問題です。
 自分の大学入試のときに、この性質を使うと高速で解けるという問題が出てきました(これ)。当時の自分はそれを知らず、手間のかかるやり方で解いたのですが、最近になってその事実を初めて知りました。というわけで、リベンジというわけではないですが(むしろやつあたり)このネタを題材にした問題を考えたのでした。

438. Integer part of polynomial equation's solutions

 7次方程式の7つの解が1~7の整数部分をもつような係数の組を探す問題。
 もともと、そのような組の個数を問う問題として考えていたのですが、意図しないことに、組の個数自体はシンプルな公式で表されるものでした。これはこれで非常に興味深い結果なのですが、プロジェクトオイラーの問題にはならないよなあ、とあきらめかけていたところ、他のメンバーからの提案で、組の個数でなく係数の絶対値の和を求める問題に変わりました。
 正解者フォーラムを見ると、上の公式に気づいただけでなく、その理由を詳細に考察した人がいて、さすがだなあという思いです。

454. Diophantine reciprocals III

 あまりよく覚えてません・・・。

462. Permutation of 3-smooth numbers

 特定の条件を満たす数字の並べ方の数を求める問題。
 もともと、1~Nの整数での並べ方を問う問題として個人的にずっと解法を練っていたのですが、けっきょくギブアップして、3-smooth数に限定することで妥協しました。1~Nの整数での並べ方については未だに個人的な未解決問題です。とはいえ、3-smooth数に限定したバージョンは、数え上げ分野のとある概念と密接な関係があって面白いです。

474. Last digits of divisors

 あまりよく覚えてません・・・。

491. Double pandigital number divisible by 11

 1~9の数字を2回ずつ使って作る18桁の数の中で、11で割り切れるものはいくつ? というシンプルな設定の問題。解くのも簡単。
 ただ、11というところがポイントで、11の倍数かどうかを判定する知られた方法を使う解き方もあります。そういう意味で教育的によい問題だと思います。

496. Incenter and circumcenter of triangle

 プロジェクトオイラーでは数少ない平面幾何ネタ。大学入試から。
 自分のふだんの問題ネタ探しでは、雑誌の「大学への数学」を見ることが多いです。ただ大学入試の問題って、アルゴリズムで解くために作られたわけでは当然ないので、プロジェクトオイラーの問題ネタに発展することはきわめて稀です。さらに平面幾何の分野はもっと稀。そんなわけでこの問題は非常に珍しい部類かも。
 なおこの問題は、もともと AC = DI という条件を設けていませんでしたが、自分で解けなかったので結局この形に至りました。

498. Remainder of polynomial division

 多項式の除算に関する問題が出したいなあと思って、実験コードをこねくり回していたら面白いパターンを発見したので、それをそのまま問題に。この問題はとにかくパラメータのチョイスが絶妙と思ってます。パターンを発見しておしまいじゃなくて、実際のプログラムを組むところにも難しいポイントがあるので、プロジェクトオイラーらしい良い問題になったと思います。

503. Compromise or persist

 本日リリースされた問題。
 ネタバレ防止のためあまり多くは語れませんが、とある有名問題のアレンジです。ネットで調べるぶんにはカブりネタは見つからなかったので、問題ないはず・・・。

2015年2月 1日

今日の成果物

 ダンボール箱4つで構成しました。

 

月別 アーカイブ

このアーカイブについて

このページには、2015年2月に書かれたブログ記事が新しい順に公開されています。

前のアーカイブは2015年1月です。

次のアーカイブは2015年3月です。

最近のコンテンツはインデックスページで見られます。過去に書かれたものはアーカイブのページで見られます。