Project Euler
Problem 107 - PukiWiki 最小全域木問題．3ms．やっぱこういうのは一度自分で作ってみると勉強になる．
大きさ n の集合 A の要素の和を S(A) で表す. 空でなく共通要素を持たないいかなる 2 つの部分集合 B と C に対しても以下の性質が真であれば, A を特殊和集合と呼ぼう. i. S(B)≠S(C); つまり, 部分集合の和が等しくてはならない. ii. B が C より多くの要…
3つの異なる点が -1000 ≤ x, y ≤ 1000 かつ三角形となるように, デカルト平面上にランダムに与えられる. 以下の2つの三角形を考える. A(-340,495), B(-153,-910), C(835,-947) X(-175,41), Y(-421,-714), Z(574,-645) 三角形ABCが原点を内部に含み, XYZは原…
数列のk個の項を与えられたときに, 次の項を確実に求めることは不可能である. その数列に合うような多項式が無限個存在するからである. 例として, 立方数の数列を考えよう. これは生成関数 un = n^3 で定義され, 1, 8, 27, 64, 125, 216, ...となる. この数…
箱の中に15個の青い円盤と6個の赤い円盤からなる21個の色のついた円盤が入っていて、無作為に2つ取り出すとき、青い円盤2つを取り出す確率P(BB)は P(BB) = (15/21) × (14/20) = 1/2 であることがわかる。 無作為に2つ取り出すとき、青い円盤2つを取り出す確…
Problem 99 - PukiWiki 各行に2つの数字が書かれた1000行のテキストファイルがある． 一つ目の数字をa，二つ目の数字をbとし，a^bを計算する(300万桁以上になるため容易には計算できない)． このとき，最大の値を計算できる数字が書かれている行番号を求めろ…
CARE という単語の各文字をそれぞれ 1, 2, 9, 6 に置き換えることによって, 平方数 1296 = 362 ができる. 注目すべきことに, 同じ数字の置換をつかうことにより, アナグラムの RACE も平方数 9216 = 962 をつくる. CARE (と RACE) を平方アナグラム単語対と…
Problem 96 - PukiWiki いわゆる"数独"(ナンプレとも呼ばれるアレ)を50問解けという問題(数独 - Wikipedia)． 最初40分くらいかかったけどどうにか40秒まで縮められた．1分切ったしもういいや．
Problem 95 - PukiWiki いずれの要素も1,000,000を超えない社交数(c.f. 社交数 - Wikipedia．ちなみに答が書いてある．)のうち，要素数が最大であるものの最小の要素を答えろ，という問題． 計算時間を短縮する方法がさっぱり思い付かない．480秒もかかった…
Problem 94 - PukiWiki 辺の長さが整数の二等辺三角形で，2つの辺の長さと1つの辺の長さが1しか違わない三角形を疑正三角形(almost equilateral triangle)と呼ぶ．辺の長さが整数の正三角形の面積は整数にならないが，疑正三角形には面積が整数になるものが…
Problem 93 - PukiWiki 遅い(170秒)上にその場しのぎだらけで汚いしパッケージの力を借りた．気分転換のつもりがすっきりしない感が増大している．なんかいろいろひどい．また調べてやり直そう．
どんな正の整数でも「各桁の数字を二乗して足す」という操作を繰り返すと1，もしくは89から始まるループに落ち着くらしい．知らなかった．それで，一千万以下の正の整数のうち89に到達するのはいくつあるのか？という問題． Problem 92 - Project Euler 37秒…
Problem 91 - Project Euler Problem 91 - PukiWiki 平面直行座標上で原点を含む3点(座標の係数はいずれも正の整数)から直角三角形を作図する。 座標の各係数が0以上50以下のとき直角三角形はいくつできるか、という問題。 こういう組み合わせが簡単に列挙で…
Problem 90 - Project Euler Problem 90 - PukiWiki 0-9までの数字のうち、互いに異なる6つの数字が6面のそれぞれに書かれた立方体がある。 立方体を2つ用意して数字を上手く選べば、100までの全ての平方数{01, 04, 09, 16, 25, 36, 49, 64, 81}を2つの立方…
Problem 89 - Project Euler Problem 89 - PukiWiki ローマ数字を書き直し、文字数をどれだけ減らせるかという問題。 390ms。Problem 88に比べたら全然簡単。
Problem 88 - Project Euler Problem 88 - PukiWiki 2つ以上の自然数の集合の積かつ和として表すことのできる数を積和数と呼ぶ。 集合の大きさkに対し、最小の積和数Nを最小積和数と呼ぶ。 2≦k≦12000について最小積和数の集合の和(集合なので重複は除く)を求…
Problem 87 - Project Euler 素数の2乗+3乗+4乗で表わされる整数のうち5千万より小さい値の個数． 400ms．こういうのはRでも早い．
Problem 86 - Project Euler クモとアリ，最短経路などでググると有名らしい問題がでてくるけど，それよりは単純．頂点から頂点への移動，その最短距離が整数になる場合を数えるだけ．なんとなく三角形作ればいいんだなってのはすぐ分かる． しかしかなり手…
Problem 85 - Project Euler 長方形の中に長方形を入れる方法がいくつあるのか、200万通りに最も近い入れ方を有す長方形の面積はどれだけか、という問題。 500msくらい。
Problem 84 - Project Euler モノポリーでどのマスに止まる確率が高いのかを求める問題。 ルールは多少単純化されているけど、モノポリーやったことないので理解するのに苦労した。例えばゾロ目が連続して出るようなとき、振るごとに移動しマスの指示に従う…
Problem 81 - Project Euler 最短経路問題。 Rなんだしパッケージ積極的に使えばいいじゃないかと開き直ってigraph使って問いた。5秒。
Problem 80 - Project Euler 平方根を整数部含めて100桁計算し、桁の値の和を求めろという問題。 開平方ムズい。 gmpをまた使ってしまって13秒。
Problem 83 - Project Euler またまた最短経路。 This problem is a significantly more challenging version of Problem 81. と書いてあるけどProblem 81のに3行足すだけで終わってしまった…。 これ例えばダイクストラのアルゴリズムを自分で実装したとして…
Problem 82 - Project Euler 引き続いて最短経路問題。 データはProblem 81と一緒だけど、開始ノードと目標ノードがそれぞれ複数候補を持っている。こういうときのアルゴリズムってあるのかな。 ちょっと無理矢理問いた感じはあるけどなんとか1分以内には終…
Problem 77 - Project Euler 分割数の様な問題。ただし支払いに使えるコインの額面は素数であると。 26秒かかった。
Problem 79 - Project Euler 長さは分からないパスコードの中から順番はそのままでランダムに3つの文字を抽出したリストがあるので、そのリストを元にパスコードを復元せよというような問題。 きっと色々な解き方がある。
Problem 78 - Project Euler 引き続き分割数の問題。100万で割り切れる最初の分割数はなにか？という問題で、今度はすぐには答が出てこない。 15秒かかった。
Problem 76 - Project Euler アンチョコ見てしまったけれども今回は久しぶりに上手くできたと思う。 200msくらい。 そしてProblem 76はアレです。分割数! そう、数学ガール!数学ガール (数学ガールシリーズ 1)作者: 結城浩出版社/メーカー: SBクリエイティブ…
Problem 75 - Project Euler 30秒。どうもここのところ時間がかかってばかりいる。
Problem 74 - Project Euler 15秒。どうも上手いやりかたが分からない。スレッドを良く読んでみるべきか。 というか、CやC++の人を見ていると結構brute forceなやり方でも常識的な時間で終わっている。Rでこの先生きのこるにはどうすれば…
