Hatena::Grouptopcoder

練習帳

 TopCoder(delta2323) / Codeforces(delta) / twitter

2011-07-21

[][] Project Euler Problem 125 21:49 はてなブックマーク -  Project Euler Problem 125 - 練習帳

問題文

 http://projecteuler.net/index.php?section=problems&id=125

要約

 正数で連続する数を各々2乗して足した形で書けて,しかもpalindromicであるもの達のうち,10**8未満のものの合計を求めよ.

方針

 i, j を動かしながら,i**2 + (i+1)**2 + ・・・+ j**2を求めて,これがpalindromicかを調べるi, jの動く範囲は10**4以下.

コード例(python
from copy import copy

N = 10 ** 8
M = 10 ** 4

def isPalindromic(n):
    digits = []

    while(n > 0):
	digits.append(n%10)
	n /= 10
    original = copy(digits)
    digits.reverse()
    return digits == original

hits = []
for i in xrange(1, M):
    psum = i * i
    for j in xrange(i+1, M):
	psum += j * j
	if psum >= N :
            break
	if isPalindromic(psum) :
            hits.append(psum)

ans = set(hits)
print sum(ans)

2011-07-20

[][] Project Euler Problem 128 07:19 はてなブックマーク -  Project Euler Problem 128 - 練習帳

問題文

 no title

要約

 正六角形がハニカム構造で配置され,それぞれの正六角形の中をルールに従って数字を埋めていく(ルールは問題文の図を参照してください).ある数nに対し,nと隣接する書かれているそれぞれの数字(6個ある)と差の絶対値をとり,その中にある素数の個数をPD(n)で表す.PD(n)は常に3以下である事が示せるが,PD(n)=3となるnのうち2000番目に小さい数を答えよ.

方針

 1から見て真北方向にある数と,その数の右下に隣接する数しか条件を満たし得ません(それ以外は常に4個以上が合成数になる).それらを順々に調べていきます.

N = 2000
cnt = 0

def isprime(n):
    if n < 2:
        return False
    i = 2
    while(i*i <= n):
        if n%i == 0:
            return False
        i += 1     
    return True

n = 1
hit = []
while(cnt < N+2):
    if isprime(6*n-1) and isprime(6*n+1) and isprime(12*n+5):
        hit.append(2+3*(n-1)*n)
        cnt+=1
    if isprime(6*n-1) and isprime(6*n+5) and isprime(12*n-7):
        hit.append(1+3*n*(n+1))
        cnt+=1
    n+=1
print hit[N-1]

2011-06-29

[][] Project Euler Problem 119 08:49 はてなブックマーク -  Project Euler Problem 119 - 練習帳

問題文

 http://projecteuler.net/index.php?section=problems&id=119

要約

 正数で,各桁の数を足し合わせて出来た数を何乗かするともとの正数にもどるようなもののうち,30番目に小さいもののを求めよ.例えば,81は 8 + 1 = 9で,9**2 == 81なので,81は条件を満たす(実は81はこのような条件を満たす最小の数).

方針

 sumAllDigits(i**j) == i という条件を調べれば良い.問題はi, jを調べる範囲.i**j の各桁を足した和の上限は9*log10(i**j) ( = 9*j*log10(i)) なので,この条件式から,9 * (j+1) >= i/log10(i)が得られる.従って,jを固定すればiの範囲は制限できる.そこでまず

for(int j = 1;; j++){
  for(int i = 1; theConditionAbove(i, j); i++){
   
  }
}

でループをし,答えを30個見つける.この時点での30番目の値をtempAnsと書けば,jは2 ** j <= tempAnsでjも範囲を制限できる.

コード例(python
from math import log10

def calc(n):
    ret = 0
    while(n > 0):
	ret += n % 10
	n /= 10
    return ret

hits = []
N = 30
INF = 10 ** 100

def main():
    ans = INF
    j = 1
    cnt = 0
    while 2**j < ans:
	i = 1
	while( ( i  == 1 or (i > 1 and   9 *(j+1)*log10(i) >= i) ) and  i**j < ans):
            tgt = i**j
            if calc(tgt) == i and tgt >= 10:
		hits.append(tgt)
		cnt += 1
		if(cnt == N):
                    hits.sort()
                    ans = hits[-1]

            i += 1
	j += 1
    hits.sort()
    print hits[-1]

if __name__ == "__main__":
    main()

2011-06-28

[][] Project Euler Problem 114 08:25 はてなブックマーク -  Project Euler Problem 114 - 練習帳

1週間はさすがにさぼりすぎました,反省します.

問題文

 http://projecteuler.net/index.php?section=problems&id=114

要約

 1 * 50の長方形のマスに様々な長さのタイルを敷いて行く.タイルの大きさは1 * n (n = 3, 4, 5・・・)で,タイル同士は1以上の整数分だけ離れてなければならない.また,タイルを1枚も敷かない場合も1通りと数える.タイルの並べ方の場合の数を求めよ.

 例えば,長さが50ではなく7ならば,次の17通り

■■■□□□□ ■■■□■■■ □■■■□□□ □□■■■□□ □□□■■■□ □□□□■■■ 
■■■■□□□ □■■■■□□ □□■■■■□ □□□■■■■ ■■■■■□□ □■■■■■□ 
□□■■■■■ ■■■■■■□ □■■■■■■ □■■■■■■ □□□□□□□ 
方針

 一番左にあるタイルの位置(左端,右端)で場合分けする.長さNのでの場合の数をf(N)とすると,大雑把には

f(N) = Σ_{0 <= i < j <= 50} f(50 - j - 1)

というような形になる.これを修正して,正しい答えを求めていく.

Σを取る範囲は最も左端にあるタイルが[i, j]の範囲にある事を想定している.タイルの長さは3以上なので,jの取る範囲は i + 3<= j <= 50なければならない.また,j = 49, 50の時はf(0)やf(-1)などの値が式の中に現れる.これの値はいくつとすべきか.これらの場合はタイルが右端から1個ずれてるか(49) or 右端にぴったり重なっているかである.これらも1通りに数えないとならないので,f(0) = f(-1) = 1とする.最後に,今までの話はタイルが1つ以上敷かれている事を前提としている(fの定義がそもそもそうなっている)ので,タイルを1枚も敷き詰めていない場合も含める.結局,

f(N) = Σ_{(i, j) 0 <= i <= 50, i + 3 <= j <= 50} f(50 - j - 1) + 1

が得られる.

コード例(python
N = 50
memo = [-1] * (N + 1)

def dp(n):
    if memo[n] >= 0 :  return memo[n]
    if n <= 0 : return 1
    memo[n] =  sum([dp(n - j - 1) for i in xrange(0, n)  for j in xrange(i + 3, n + 1)]) + 1
    return memo[n]

print dp(N) 

2011-06-15

[][] Project Euler Problem 123 21:56 はてなブックマーク -  Project Euler Problem 123 - 練習帳

問題文

 no title

要約

 p[n] を n 番目に小さい素数とする( n は 1-indexed)。(p[n] + 1)^{n}+(p[n] - 1)^{n}を p[n]^{2} で割った余りが 10^{10} を始めて越える n はいくつか。

方針

 2 項定理より,

(p[n] + 1)^{n} ≡              (n*p[n] + 1)  (mod p[n]^2)
(p[n] - 1)^{n} ≡ (-1)^{n-1} * (n*p[n] - 1)  (mod p[n]^2)

 従って,求める値は n が偶数なら 2, n が奇数なら 2*n*p[n] mod (p[n]^{2})。奇数について小さい数からこの値を求めれば良い。

コード例(c++)

 愚直に小さい n から順にチェックしています。それでも自分の環境で 0.1 秒でした。素数を求める範囲を決め打ちしてしまっているのであまり良いコードではないと思います。

#include <iostream>
#include <vector>
using namespace std;

typedef long long ll;

ll N = 1000000;
bool p[1000000] = {};
vector<ll> primes;
ll th = 1;

void sieve(){
  p[0] = p[1] = 1;
  for(int i = 0;i<N;i++){
    if(p[i]) continue;
    for(int j = i+i; j < N;j+=i){
      p[j] = 1;
    }
  }
}

void pack(){
  for(int i= 0;i<N;i++){
    if(!p[i])
      primes.push_back(i);
  }
  return;
}

ll f(ll n){
  return (2 * n * primes[n-1]) % (primes[n-1] * primes[n-1]);
}

int main(){
  sieve();
  pack();
  for(int  i = 0;i<10;i++){
    th *=10;
  }
  for(ll n = 3;; n+=2){
    if(f(n) > th){
      cout << n <<" " << f(n) <<endl;
      return 0;
    }
  }
}