読者です 読者をやめる 読者になる 読者になる

何度も実行される箇所で Linq を使うことによるパフォーマンスの影響

Project Euler 23 を解いていて、Linq 使用の有無で速度差が出たのでメモ。 約数の和を求める SumProperDivisors メソッドで Linq を使う場合と、Linq を使わずに for 文で計算する場合とでどれくらい速度に差が出るか計測してみました。 using System; usin…

Project Euler 56

PE

Problem 56 using System; using System.Collections.Generic; using System.Numerics; using System.Linq; class PE056 { static void Main() { var seq = from a in Enumerable.Range(1, 99) from b in Enumerable.Range(1, 99) let sum = BigInteger.Pow(…

Project Euler 55

PE

Problem 55 using System; using System.Collections.Generic; using System.Numerics; using System.Linq; // コンパイル方法: // $ mcs 055.cs -r:System.Numerics -out:a.exe class PE055 { static bool IsPalindrome(BigInteger n) { var a = n.ToString…

Project Euler 52

PE

Problem 52 6 倍しても桁が変わらないので、最上位の桁は 1 のはず。 using System; using System.Collections.Generic; using System.Linq; class PE052 { static void Main() { for (int i = 1; /* */; i++) { string s = "1" + i; // 6 倍しても桁数が同…

Project Euler 50

PE

Problem 50 using System; using System.Collections.Generic; using System.Linq; class Prime { public static List<int> Sieve(int n) { // n 以下の全ての素数を求める bool[] tab = new bool[n+1]; for (int i = 0; i < tab.Length; i++) tab[i] = true; int</int>…

Project Euler 49

PE

Problem 49 using System; using System.Collections.Generic; using System.Linq; class Prime { public static List<int> Sieve(int n) { // n 以下の全ての素数を求める bool[] tab = new bool[n+1]; for (int i = 0; i < tab.Length; i++) tab[i] = true; int</int>…

Project Euler 46

C# PE

Problem 46 using System; class PE046 { static bool IsPrime(int n) { if (n == 2) return true; if (n % 2 == 0) return false; for (int i = 3; i*i <= n; i += 2) { if (n % i == 0) { return false; } } return true; } // n == prime * 2*x*x という…

Project Euler 43

C# PE

Problem 43 using System; using System.Collections.Generic; using System.Linq; class PE043 { static long Calc(int p, int[] digits, bool[] used) { int[] ds = { 0, 0, 2, 3, 5, 7, 11, 13, 17 }; long ret = 0; int x = 100 * digits[p-3] + 10 * di…

Project Euler 42

Problem 42 using System; using System.Collections.Generic; using System.IO; using System.Text.RegularExpressions; using System.Linq; class PE042 { static bool IsTriangleWord(string word) { int sum = word.Select(c => c - 'A' + 1).Sum(); int…

Project Euler 41

C# PE

Problem 41 リストの要素を swap する関数は stackoverflow の以下を参考にしました。 c# - Swap two items in List<T> - Stack Overflow using System; using System.Collections.Generic; using System.Linq; class PE041 { static void Swap<T>(List<T> ls, int a,</t></t></t>…

Project Euler 40

PE C#

Problem 40 10 から 99 までの整数をつなげたとき、その桁数は 桁数:2 * (100 - 10) です。 100 から 999 までの整数をつながたとき、その桁数は 桁数:3 * (1000 - 100) です。 $ pry [3] pry(main)> x = 10 => 10 [4] pry(main)> x.to_s.length * (10*x - x…

Project Euler 39

C# PE

Problem 39 right angle triangle とは直角三角形のこと p <= 1000 なので、1 辺の長さは 500 まで調べる using System; using System.Collections.Generic; using System.Linq; class PE039 { static void Main() { const int N = 500; var freq = new Dict…

Project Euler 38

C# PE

Problem 38 n > 1 なので 100000 まで調べている。もっと値は小さくできそうだけど……。 using System; class PE038 { static int Calc(int n) { string s = ""; for (int i = 1; ; i++) { s += (n * i).ToString(); int[] freq = new int[10]; int m = 0; fo…

Project Euler 37

C# PE

Problem 37 using System; using System.Collections.Generic; using System.Linq; class PE037 { static List<int> MakePrimes(int n) { var primes = new List<int>(); primes.Add(2); // 2 is prime var table = new bool[n+1]; for (int i = 3; i <= n; i += 2) { </int></int>…

Project Euler 36

C# PE

Problem 36 2 進数の回文は、末尾が必ず 1 となるので、奇数のみ調べる。 using System; using System.Collections.Generic; using System.Linq; class PE036 { static string Bin(int n) { if (n < 0) throw new Exception("n < 0"); var ls = new List<char>(); </char>…

Project Euler 35

PE C#

Problem 35 1000000 までの素数を求める(エラトステネスのふるいで素数を求める) 求めたそれぞれの素数に対して、各桁の数値を回転させた数を作成し、素数かどうか調べる using System; using System.Collections.Generic; using System.Linq; class PE035 {…

Project Euler 34

C# PE

Problem 34 最大何桁まで求めたら良いのか。 [1] pry(main)> def f(n) n < 1 ? 1 : n*f(n-1) end => :f [2] pry(main)> (1..12).each { |i| puts "i:#{i} #{i*f(9)}" } i:1 362880 i:2 725760 i:3 1088640 i:4 1451520 i:5 1814400 i:6 2177280 i:7 2540160 …

Project Euler 33

C# PE

Problem 33 問題文を読んでもどうもよく理解できずすっきりしない。 xy/yz = xz となる x, y, z を求めている。 using System; class PE033 { static int Gcd(int m, int n) { int r = m % n; while (r != 0) { m = n; n = r; r = m % n; } return n; } stat…

Project Euler 32

C# PE

Problem 32 1 桁 x 4 桁、もしくは 2 桁 x 3 桁のいずれか。 1 桁 x 3 桁はありえない。9 * 999 = 8991 なので、最大でも 8 桁にしかならないから。 3 桁 x 3 桁はありえない。100 * 100 = 10000 なので、9 桁を超えてしまうから。 using System; using Syst…

Project Euler 31

C# PE

Problem 31 動的計画法の基本的な問題。 using System; class PE031 { static void Main() { int[] coins = { 1, 2, 5, 10, 20, 50, 100, 200 }; const int N = 200; int[] dp = new int[N+1]; dp[0] = 1; for (int i = 0; i < coins.Length; i++) { for (in…

Project Euler 30

C# PE

Problem 30 上限値を考える 何桁まで調べればよいのだろうか。9 の 5 乗で調べてみる。 [11] pry(main)> (1..10).each { |i| puts "i:#{i} #{9**5 * i}" } i:1 59049 i:2 118098 i:3 177147 i:4 236196 i:5 295245 i:6 354294 i:7 413343 i:8 472392 i:9 531…

Project Euler 29

C# PE

Problem 29 using System; using System.Collections.Generic; using System.Numerics; class PE029 { static void Main() { var st = new HashSet<BigInteger>(); for (int i = 2; i <= 100; i++) { BigInteger a = i; for (int j = 2; j <= 100; j++) { st.Add(BigInte</biginteger>…

Project Euler 28

C# PE

Problem 28 using System; class PE028 { static int Calc(int size) { // N x N サイズのとき、4 隅の一番大きな数字は N^2 // 4 隅の数字のうち、一番大きな数字を除いた残りの数字は // N^2 - (n - 1) * 1 // N^2 - (n - 1) * 2 // N^2 - (n - 1) * 3 // …

Project Euler 27

C# PE

Problem 27 using System; class PE027 { static bool IsPrime(int n) { if (n <= 1) return false; if (n == 2) return true; if (n % 2 == 0) return false; for (int i = 3; i*i <= n; i += 2) { if (n % i == 0) return false; } return true; } static …

Project Euler 26

PE C#

Problem 26 素直に割っていき、余りがゼロになるかまたはサイクルするまで繰り返す。 using System; using System.Collections.Generic; using System.Linq; class PE026 { static List<int> CalcRecurringCycle(int d) { var divs = new List<int>(); var mods = new </int></int>…

Project Euler 25

C# PE

Problem 25 using System; using System.Numerics; class PE025 { static void Main() { var a = new BigInteger(1); var b = new BigInteger(1); int nth = 2; while (b.ToString().Length < 1000) { var t = a + b; a = b; b = t; nth++; } Console.WriteL…

Project Euler 24

C# PE

Problem 24 using System; using System.Collections.Generic; using System.Linq; class PE024 { static long Fact(long n) { if (n == 0) return 1; else return n * Fact(n-1); } static string Calc(long n) { var ans = new List<int>(); var digits = Enume</int>…

Project Euler 23

C# PE

Problem 23 Wikipedia で、完全数、不足数、過剰数について調べる。 完全数(perfect number) その数自身を除く約数の和が、その数自身と等しい自然数のこと。 例えば 6 (= 1 + 2 + 3)、28 (= 1 + 2 + 4 + 7 + 14) や496が完全数。 不足数(deficient number) …

Project Euler 22

PE C#

Problem 22 MatchCollection と Linq を連携させるには、Cast<Match>() が必要。 Linq のメソッドチェーンで改行するさい、インデントを深くすべきか考え中。 using System; using System.IO; using System.Text.RegularExpressions; using System.Linq; class PE02</match>…

Project Euler 21

C# PE

Problem 21 d(n) の計算は、素直に割り算している。 using System; class PE021 { static int SumProperDivisors(int n) { int sum = 0; for (int i = 1; i*2 <= n; i++) { if (n % i == 0) { sum += i; } } return sum; } static int Calc() { int ans = 0;…

Project Euler 20

C# PE

Problem 20 BigInteger を使う方法と、使わない方法の 2 通りで解いてみた。 using System; using System.Collections.Generic; using System.Numerics; using System.Linq; class PE020 { // BigInteger を使う方法 static int Calc1() { BigInteger x = 1;…

Project Euler 19

C# PE

Problem 19 using System; class PE019 { static void Main() { int ans = 0; var d = new DateTime(1901, 1, 1); var endDate = new DateTime(2000, 12, 31); while (d < endDate) { if (d.DayOfWeek == DayOfWeek.Sunday) { ans++; } d = d.AddMonths(1); …

Project Euler 15

PE

Problem 15 2 次元配列の練習。 20x20 なので 40 ステップで目的値に到達する。そのうち、水平移動は 20 ステップ行うので、40C20 を計算する方法でも良い。 『組み合わせ入門』p.2 using System; class PE015 { public static void Main() { const int N = …

Project Euler 14

C# PE

Problem 14 int で計算するとオーバーフローする。 メモ化をしたいけど、上限値がわからない。そういう場合は、ある一定値までメモ化する、というように決めてしまえばよい。この問題では N = 1000000 までとする。 ScalaでProject Euler(28) - 桃の天然水…

Project Euler 13

PE

Problem 13 System.Numerics.BigInteger を使う。 部分文字列は、Substring() メソッドを使う。 using System; using System.IO; using System.Numerics; public class PE013 { public static void Main() { var x = new BigInteger(0); foreach (string s i…

Project Euler 12

PE

Problem 12 約数の個数は、4 約数の個数 - Wikipedia のように求める。 Python の itertools.groupby が欲しい。素因数分解したあとのグループ化で使う。Enumerable.GroupBy でできるかな? using System; using System.IO; using System.Collections.Generic…

Project Euler 11

C# PE

Problem 11 C# ポケットリファレンス を読みながら、ファイル読み込みや、文字列処理を書いています。 File.ReadAllText, File.ReadAllLinesで一括でテキストを読み込む String.Split で文字列を分割 int best = 0 を var best = 0 と書いたら内部ではどう扱…

Project Euler 10

PE C#

Problem 10 配列の練習 答えは int だとオーバーフローする using System; using System.IO; using System.Collections.Generic; public class P010 { static List<int> sieve(int n) { bool[] xs = new bool[n+1]; for (int i = 0; i <= n; i++) { xs[i] = true;</int>…

Project Euler 9

PE

Problem 9 a + b + c = 1000 だから、2 重ループで a, b の値を決めて、残りの c は、c = 1000 - (a + b) で求めます。 using System; public class P009 { public static void Main() { for (int i = 0; i < 1000; i++) { for (int j = i+1; j < 1000; j++)…

Project Euler 8

PE

Problem 8 char.IsDigit(c) で文字 c が数値かどうか判定 文字 c から数値への変換は、c - '0' で出来た using System; using System.IO; using System.Collections.Generic; namespace PE { public class PE008 { public static void Calc() { string text …

Project Euler 5

PE

Problem 5 and と i のいずれでも割り切れる数は不要なので gcd で取り除く。lcm で求める方法もある。 using System; namespace PE { public class PE005 { public static void Calc() { int ans = 1; for (int i = 1; i <= 20; i++) { ans = ans / Util.Gc…

Project Euler 4

PE

Problem 4 using System; namespace PE { public class PE004 { public static bool IsPalindrome(int n) { string s = n.ToString(); for (int i = 0; i < s.Length/2; i++) { if (s[i] != s[s.Length - i - 1]) { return false; } } return true; } public…

Project Euler 3

PE

Problem 3 using System; using System.Collections.Generic; namespace PE { public class PE003 { public static void Calc() { long n = 600851475143; List<long> factors = new List<long>(); long x = 3; while (x*x <= n) { if (n % x == 0) { factors.Add(x); n </long></long>…

Project Euler 2

PE

Problem 2 using System; namespace PE { public class PE002 { public static void Calc() { const int n = 4000000; int a = 1; int b = 2; int sum = 2; while (b <= n) { int tmp = a + b; a = b; b = tmp; if (tmp % 2 == 0) sum += tmp; } Console.Wri…

Project Euler 1

PE

Problem 1 using System; namespace PE { public class PE001 { public static void Calc() { int sum = 0; for (int i = 3; i < 1000; i++) { if (i % 3 == 0 || i % 5 == 0) { sum += i; } } Console.WriteLine(sum); } } }