Hatena::Grouptopcoder

練習帳

 TopCoder(delta2323) / Codeforces(delta) / twitter

2011-04-29

[][] Project Euler Problem 95 23:24 はてなブックマーク -  Project Euler Problem 95 - 練習帳

問題文

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

要約

 自然数nに対し,nを除く約数の合計をf(n)と表す.

n -> f(n) -> f(f(n)) -> ・・・ -> f^{k+1}(n) = n

となる列を長さkの友愛鎖(amicable chain)と呼ぶ.例えば220と284は友愛数なので,

220 -> 284 -> 220

は長さ2の友愛鎖である.列の中に現れる数字がすべて100万未満の友愛鎖の中で最も長いものを考える.その数列の中で最小の数を答えよ.

方針

 鳩の巣原理から,nから始まる鎖は次の2パターンのどちらかである

・戻ってくるタイプ(※)
                                                   |----------|
                                                   v          |
n -> f(n) -> f(f(n)) -> ... ->  f^{k'}(n) -> ... -> f^{k}(n)
・発散するタイプ
n -> f(n) -> f(f(n)) -> ... ->  f^{k'} -> ... -> f^{k}(n)( > 1000000)

 各々のnに対しfへの適用を繰り返し,どちらのパターンかが判明した段階で矢印を遡って結果(鎖の一部か,鎖の外にあるか)を変数memoに書き込む.発散タイプは値が閾値の1000000を超えるかで判定できる.一方戻ってくるタイプはこれまでたどってきた数字を記録しておき,その数字にぶつかったら引き返すとする.後者を行うために下のコードでは,memoに「計算途中」という状態も保存している.

コード例(Python)

pow = 6
INF = 10 ** (pow + 1)
N = 10 ** pow

# memo[n] :  The state of n. Each value represents the following conditions.
# INF  : not calculated yet
# -INF : It does not delong to amicable chains.
# -n   : now calculating , depth = n (n >= 0)
# otherwise : The number represents the length of amicable chain.
memo = [INF] * N

# return the amicable number of n
def f(n):
    if (n == 0 or n == 1 ) : return 0
    ret = 1
    i = 2
    while(i * i < n):
        if(n % i == 0):
            ret += i
            ret += n/i
        i += 1
    if(i * i == n):
        ret += i
    return ret

def dfs (now, depth):
    if(now >= N) : return -INF                 # This sequence turned out to be a divergent type.
    if(memo[now] == -INF) : return -INF # This sequence connected to non-amicable chain.
    elif(memo[now] <= 0):
        memo[now] = depth + memo[now] 
        return memo[now]
    elif(memo[now] != INF) : return -INF # memo[now] > 0 i.e. , this sequence collided to amicable chain. 
                                                               # That implies it is never a amicable chain. 
    memo[now] = -depth                        # This sequence turned out to be a convergent type.
    ans = dfs(f(now), depth + 1)
    if(memo[now] == ans):                    
        return -INF
    else:
        memo[now] = ans
        return ans

for i in xrange(1, N):
    if(memo[i] == INF):
        dfs(i,0)
l= [(i, memo[i]) for i in xrange(N) if memo[i] > 0]
l.sort(reverse = True, cmp = lambda (a,b), (c,d): b - d if b != d else c - a)
print l[0]

分析

上のdfs関数はちょっとがんばって書いたので,

    memo[now] = -depth

以降で何を行っているかを解説する.コードでここまで来ている時には数列が戻ってくるタイプ(つまり,友愛鎖のできるタイプ)だとわかっている.そこでまず自己衝突した場所(上の(※)でのf^{k'}(n))に友愛鎖の長さを保存し,関数自体もその長さを返す.その戻り値を用いてこれまでたどってきた道での結果をmemoに書き残す.友愛鎖の先頭は自己衝突した数であり,それは「memoに書き残した値と関数の戻り値として得られた値が等しい」という条件で判別できる(それ以外の友愛鎖では戻り値を得た時,memo[]には0以下の値が書き込まれているはずである).そこで,

    if(memo[now] == ans):                    

の条件が満たされてからはもう友愛鎖に乗らない数なので,関数は-INFを返している.

補足

 ここ*1によると,sortのcmpパラメータはPython 3では除外されているようです.実際上のコードはPython3.2でSyntax Errorを出しました.

$ sudo python_select python32
Password:
Selecting version "python32" for python
$ python --version
Python 3.2
$ python euler95.py
  File "euler95.py", line 46
    l.sort(reverse = True, cmp = lambda (a,b), (c,d): b - d if b != d else c - a)
                                        ^
SyntaxError: invalid syntax

2011-04-28

[][] Codeforces Beta Round #70 (Div. 2) 08:36 はてなブックマーク -  Codeforces Beta Round #70 (Div. 2) - 練習帳

問題一覧:Dashboard - Codeforces Beta Round #70 (Div. 2) - Codeforces

結果:Standings - Codeforces Beta Round #70 (Div. 2) - Codeforces

=.ABCDE
--00:0600:12---
1440+0/-0488952WA-1-

部屋内4位(Room 62),全体63位

Rating:1550 → 1614 (+64)

このところいい所なしなので,一矢報いたかったのです.結果は可もなく不可もなく.

続きを読む

2011-04-27

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

問題文

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

要約

 一桁の数の4つ組0<=a < b < c < d<=9に対し,a, b, c, dを適当に並べ替た後,四則演算と()を使って作れる数全体を考える.例えば(1,2,3,4)の場合,

8 = (4 * (1 + 3)) / 2
14 = 4 * (3 + 1 / 2)
19 = 4 * (2 + 3)  1
36 = 3 * 4 * (2 + 1)

などがある.数字の連結は行ってはならない.f(a,b,c,d)を,閉区間[1, n]内のすべての整数がこのように作られるようなnの中で,最大のものとする.つまり,[1, f(a,b,c,d)]はすべてa,b,c,dを組み合わせて作られるが,f(a,b,c,d)+1は作られない.f(a,b,c,d)が最大となる組を求めよ,

続きを読む

2011-04-26

[][] Project Euler Problem 90 09:47 はてなブックマーク -  Project Euler Problem 90 - 練習帳

問題文

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

要約

 それぞれの面に一桁の数字を書いたサイコロを2つ用意し,2つ並べて正面から見る事で2桁の数字(00~99)を作る.ただし,6は上下逆にして9として使え,逆に9も6として使える.一つのサイコロに書かれている6つの数字は相違である.

サイコロへの数字の書き方で,適当に並べ替えて2桁以下の平方数をすべて作る事のできる場合の数は何通りあるか.

 数字の書き方の同一視の仕方は次のルールで決める.

  • サイコロに書く数字の位置は考慮しない.つまり,面に適当に順番をつけた時,{1,3,4,5,6,8}と{5,8,1,6,3,4}は同じ書き方と見なす.
  • 6と9は別の数字と見なす.つまり,{1,3,4,5,6,8}と{1,3,4,5,9,8}は別物
  • 2つのサイコロは区別しない.つまり,({1,2,3,4,5,6},{4,5,6,7,8,9}) と({4,5,6,7,8,9}, {1,2,3,4,5,6}) は同じ書き方.

続きを読む

2011-04-24

[][] Codeforces Beta Round #69 (Div. 2) 00:02 はてなブックマーク -  Codeforces Beta Round #69 (Div. 2) - 練習帳

問題一覧:Dashboard - Codeforces Beta Round #69 (Div. 2 Only) - Codeforces

 今回は時間の都合が合わずに不参加,でも,問題は解きました.この回はDiv.2の3,4,5問目がそれぞれDiv.1の1,2,3問目に対応しているのですね,普段Div.1では3問解くのを目標としているので,今回はDiv.2を解きました.

続きを読む

2011-04-23

[][] Project Euler Problem 132 00:34 はてなブックマーク -  Project Euler Problem 132 - 練習帳

問題文

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

要約

 M = 11..11 ( 1 が 10^{9} 並んだ数)の約数かつ素数のものを小さい方から40個探し,その合計を求めよ。

続きを読む

2011-04-21

[][] Project Euler Problem 131 23:17 はてなブックマーク -  Project Euler Problem 131 - 練習帳

問題文

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

要約

 素数 p で次の条件を満たすものの個数を求めよ.

  • 正数 n , _n が存在し n^{3} + n^{2} * p = _n^{3} となる.(このような n は各 p に対し存在すれば一意である事が知られている)
  • p は 1000000 以下

続きを読む

2011-04-18

[][] Project Euler Problem 127 01:00 はてなブックマーク -  Project Euler Problem 127 - 練習帳

問題文

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

要約

 次の条件を満たす正数の三組み(a, b, c)を abc-hits と呼ぶ

  • GCD(a, b) = GCD(a, c) = GCD(b, c) = 1
  • a < b
  • a + b = c
  • rad(abc) < c

ここで,GCD(a, b) はaとbの最大公約数,rad(k) は k の radica(根基?)で,k の約数かつ素数のもの達の積と定義する。例えば rad(504) = 2 * 3 * 7 = 42.abc-hits (a, b, c) で c < 120000 となるものに対し,c の合計を求めよ( 1 つの c に対し abc-hits を作る複数の (a,b) の組があれば,その組のぶんだけ和の計算に取り入れる)。

続きを読む

2011-04-17

[][] Project Euler Problem 129 02:30 はてなブックマーク -  Project Euler Problem 129 - 練習帳

問題文

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

要約

 自然数 k に対し,R(k) = 11..11(k桁)とし,自然数 n に対し A(n) で R(k) が n で割り切れるような最小の k を表す( n が10と互いにその場合このような k が存在する事が示される)。A(n) > 1000000 となる最小のnを答えよ。

続きを読む

2011-04-16

[][] TopCoder Single Round Match 503 Div 1 05:42 はてなブックマーク -  TopCoder Single Round Match 503 Div 1 - 練習帳

 コンテスト結果概要

 個人結果(要ログイン)

2500:15:57.886Passed System Test195.43
5000:58:52.937Opened0.00
10000:47:25.603Opened0.00
Challenge..0.00

部屋(Room 8) 8位,全体 283位

Rating : 1396 → 1484 (+88)

前回落ちた分は取り戻しました.次は黄色入りを目指したい.

続きを読む

[][] Codeforces Beta Round #68 10:58 はてなブックマーク -  Codeforces Beta Round #68 - 練習帳

問題一覧:Dashboard - Codeforces Beta Round #68 - Codeforces

結果:Standings - Codeforces Beta Round #68 - Codeforces

=.ABCDE
--0:071:58---
786+0/-0486300---

部屋内 7位(Room 64),全体457位

Rating: 1607 → 1550 (-57)


続きを読む

2011-04-14

[][] Codeforces Beta Round #67 (Div. 2) 00:52 はてなブックマーク -  Codeforces Beta Round #67 (Div. 2) - 練習帳

問題一覧:Dashboard - Codeforces Beta Round #67 (Div. 2) - Codeforces

結果:Standings - Codeforces Beta Round #67 (Div. 2) - Codeforces

=.ABCDE
--0:250:591:46--
1978+0/-1400764864--

部屋内 5位(Room 60),全体70位

Rating: 1591 → 1607 (+16)

大きな失敗はしなかったので及第点だと思います.ただ,相変わらずHackができません.

続きを読む

2011-04-12

[][] TopCoder Single Round Match 502 Div1 23:22 はてなブックマーク -  TopCoder Single Round Match 502 Div1 - 練習帳

 コンテスト結果概要

 時間の都合が合わず不参加.参加していたら250だけ解けてレーティングが微増していただろうと思います.次回SRMは4月17日(日)1時から,曜日では日曜日ですが,実際には土曜日の夜なので気をつけてください.

続きを読む

2011-04-10

[][] Codeforces Beta Round 66 02:24 はてなブックマーク -  Codeforces Beta Round 66 - 練習帳

Codeforces Beta Round #

問題一覧:Dashboard - Codeforces Beta Round #66 - Codeforces

結果:Standings - Codeforces Beta Round #66 - Codeforces

=.ABCDEF
--0:421:44----
266+0/-0266WA----

部屋内 27位(Room 9),全体358位

Rating:1659 → 1591 (-68)

Div. 2 にトンボ帰り,この辺りに大きな壁を感じます.どうやって練習すればいいのでしょうか・・・.

続きを読む

2011-04-08

[][] Project Euler Problem130 06:58 はてなブックマーク -  Project Euler Problem130 - 練習帳

問題文

 no title

要約

 自然数 k に対し,R(k) = 11..11(k桁)とし,自然数 n に対し A(n) で R(k) が n で割り切れるような最小の k を表す( n が10と互いにその場合このような k が存在する事が示されている)。自然数 n > 1 で「合成数,10と互いに素,n-1 が A(n) で割り切れる」という条件を満たすものを小さい方から 25 個の和を求めよ (n が素数の場合 n-1 は A(n) で割り切れることが示される)。

方針

 基本的にはやるだけ。A(n)の存在が確かなので,A(n)を求める時に安心して無限ループを使えます。こういう時に数学の定理って強いです。

コード例

 ジェネレータを for(i = 1;;i++) の代わりとして使っています。repunitの計算で剰余をとらないと2分弱かかる一方,下のコードのようにすると6秒程度で終わりました。

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

def nat(init):
    i = init
    while(True):
        yield i
        i += 1

def modrepunits(n):
    i = 1
    while(True):
        yield i
        i = (i * 10 + 1) % n

suffice = []
for n in nat(2):
    if(isprime(n) or n % 2 == 0 or n % 5 == 0): continue
    digit = 1
    for repunit in modrepunits(n):
        if(repunit == 0):break
        digit += 1
    if((n - 1) %  digit == 0):
        suffice.append(n)
        if(len(suffice) == 25): break
print sum(suffice)

2011-04-07

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

問題文

 no title

要約

 正数 n に対して その radical(根基?)rad(n) を n の約数かつ素数のもの達の積と定義する。例えば rad(504) = 2 * 3 * 7 = 42

 1 から 100000 までを rad(n) の小さい順に並べた時(等しい場合は n そのものが小さいほうが先),10000 番目 (1-indexed) を求めよ。

続きを読む

2011-04-05

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

テーマ:DP 早解きその 2

問題文

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

要約

 1×50 の長方形のマスに 1×2,1×3,1×4 のタイルを敷く.条件は,

  • タイルは整数単位でしかずらせない
  • 異なるタイルを混ぜてよい
  • 全てのマスを埋める必要はない
  • タイルを 1 つも敷かない場合も 1 通りと数える

 敷き方の場合の数を求めよ.例えば 1×5 の場合次の 15 通り

□□□□□ 22□□□ □22□□ □□22□ □□□22
2222□ 22□22 □2222 333□□ □333□
□□333 22333 33322 4444□ □4444

続きを読む

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

テーマ:DP 早解き

問題文

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

要約

 1×50 の長方形のマスに 1×2,1×3,1×4 のタイルを敷く.条件は,

  • タイルは整数単位でしかずらせない
  • 異なるタイルを混ぜてはいけない
  • 全てのマスを埋める必要はない
  • 少なくとも 1 つのタイルを用いる.

 敷き方の場合の数を求めよ.例えば 1 × 5 の場合は次の 12 通り

22□□□ □22□□ □□22□ □□□22 2222□ 
22□22 □2222
333□□ □333□ □□333 
4444□ □4444 

続きを読む

2011-04-03

[][] Project Euler Problem 111 01:58 はてなブックマーク -  Project Euler Problem 111 - 練習帳

テーマ:高階関数,イテレータに慣れる

問題文

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

要約

 dを 0 から 9 の一桁の数字とする.n を 1 以上の正数,k を n 以下の非負数とし,d が k 個含まれる n 桁の素数を考える。そのような素数が存在する k のうち,最大のものを M(n, d) と書く.さらに,S(n, d) を d が M(n, d) 個含まれる n 桁の素数達の和とする.つまり,n 桁の素数を d が入っている数で順位をつけた時,1位タイとなっているものをすべて足しあげたのがS(n, d) である.

 Σ_{d=0}^{9} S(10, d) を求めよ.

続きを読む

2011-04-01

[][] Problem Parser Contest? 01:46 はてなブックマーク -  Problem Parser Contest? - 練習帳

Codeforces で Problem Parser Contest なるものが始まっています.

 Problem Parser Contest - Codeforces

コンテストで過去に出題した問題のアーカイブを作るときに行う作業が面倒だから,コンテスト形式にしてみんなにいいスクリプトを作ってもらおうという計画らしいです.

様々な面で通常のコンテストとは異なります.

  • マラソン形式
    • コンテスト終了は4月15日,それまでに何度もサブミットでき,最後のサブミットだけが有効
  • 賞金が出る
    • 1 位は280ドル:2万3千円くらい
  • 優秀作品は実際のシステムで使われるかも

プログラミング面での重要な点は以下の所でしょうか

  • 言語は Java 6 だけ
  • メモリ制限が厳しい
    • ヒープサイズが32M,スタックサイズが1M
    • 普段のコンテストは 256MB 程度が多い.

パーズの練習に参加すると良いのかな,ただ,Javaはあまりあつかった事がないから一人Unknown Language Contest状態になりそうです.