PE

Project Euler 83 Path sum: four ways

問題を見た時からdijkstra法だと分かっていたが集中してやりたかったので敢えて取っておいた問題 #include <bits/stdc++.h> using namespace std; static const int WHITE = 1; static const int GRAY = 2; static const int BLACK = 3; static const int INF = 1<<21; stat</bits/stdc++.h>…

Project Euler 65 Convergents of e

projecteuler.net e=[2;1,2,1,1,4,1,1,6,1,...,1,2k,1,...] という連分数展開の問題後ろから深さ優先探索で解く. from fractions import Fravtionsすると分数型が出来て便利 gist.github.com

Project Euler 345 Matrix Sum

N-Queen問題の斜め無い版(N-飛車問題?,N-ルーク問題?)のアルゴリズムで考えられうる盤面を全て用意しそのマスに配置された数字の合計の中で最大のモノを探せばよい. サンプルの5*5盤面では1秒以内で出来たが15*15では時間がかかって出来なかった. もっと早…

Project Euler 145 How many reversible numbers are there below one-billion?

projecteuler.net 単純な解放 奇数の判定はビット演算を計算する. n&1==1ならnは奇数, (not n&1)==1ならnは偶数 d.hatena.ne.jp ↑参考にしたい解答 // gist.github.com

Project Euler 329 Prime Frog

PE

projecteuler.net Pythonで分数型を用いたいときは fractions.Fraction(分子,分母)で出来る. 1. 500以下の全てのマスを素数か素数でないか区別する. 2. 次にマスが素数であれば"P"と鳴く確率は2/3, "N"と鳴く確率は1/3 マスが素数でなければ"P"と鳴く確率は1…

Project Euler 96 Su Doku

PE

projecteuler.net 数独の問題 あるマスA[y][x] == 空白ならばそのマスが属する(i)横(ii)縦(iii)ブロックを探索しA[y][x]に入れるべき解の候補を探す. 解の候補の各々に対して再帰的な処理をする. 終了条件は, 答え→空白が無くなった ダメ→A[y][x]について解…

Project Euler 89

PE

難易度は20%と簡単だが, とにかく面倒くさかった. // gist.github.com ローマ数字から数字, 数字からローマ数字に変換できる関数とかはあるのかな? 【追記:すぐ】 問題文を読み落としていることに気づいた. ローマ数字は大きい方から順に書かれる. よって…

Project Euler 204 (2)

PE

// gist.github.com d.hatena.ne.jp このブログを参考に書きました. とても参考になりました. 再帰のイメージを書いて見た. (limit = 1000) pで割り切れなくてもn//pでnを小さくしていけば結局同じなんですね.

Project Euler 204

PE

type 以下の素数のリストをエラトステネスの篩で作る. その素数のみの積で表される数のうちlimit = 10**9を超えない数を数え上げれば良い. もっとも小さい素数は2であり2**n で始めてlimit を越えるのはn = 30であるので, 素数のリストから30個重複を許さな…

Project Euler 146

PE

滅茶苦茶汚いコードだし理論もクソだったのでコードは載せない. 考え方は10<= n <= 150000000まで回してその一つ一つにn^2+1, ..., n^2+27を計算しそれぞれをMR法で素数か判定する. この時全体の時間を考えるとMR法で生成する乱数は少ない方が良い. 3回もや…

Project Euler 173

PE

使うタイルの枚数をn, laminaeの輪郭の正方形の一辺の長さをa, 穴の正方形の長さをb とする. 100以下を考えるとすると b= 1のとき(穴が1*1マスのとき) a = 3, n = a**2 - b**2 =3**2 - 1**2 = 8 a = 5, n = 5**2 - 1**2 = 24 a = 7 ,n = 7**2 - 1**2 = 48 a …

Project Euler 108

PE

ディオファントス逆数の問題 について式変形してとする. これは右辺>0 であるので左辺>0で,y>0なのでとなる. とするとxが最大のときとなりでこのときよってnについてxの範囲はである. が整数になれば良いので以下のようなコードを考えた. gist.github.com し…

Project Euler 107

PE

Project Euler 107番を解く際にPrim法を使用しました. 今後使えそうなので貼っておきます. // gist.github.com