競技プログラミング等の部屋

2015年11月30日月曜日

151130

心得

2ch で次の書き込みを見た。

「競技プログラマーの強さを表す、こんな言葉を見たことがある。

初心者　わかった=自力でゼロから解き方を考えた
中級者　知ってた=アルゴリズムを知ってたので、実装するだけだった
上級者　あった=既に自前のライブラリにあったので、貼り付けるだけだった」

これを見て、知らない問題には自力で解ける力をつけないといけないが、

時間とのたたかいである以上、準備を怠らず

「こんなの貼り付けるだけ」

と言えるようにならないといけないと感じた。

2015年6月21日日曜日

150621

Project Euler

Problem 520

Simber(２進法版)を考えてみた。

すなわち、0を含むなら偶数個含み、1を含むなら奇数個含むようなものを考える。

N = 10

# nが偶数のときは存在しない

1.step(N, 2){|n|

ary = []

(2 ** (n - 1)..2 ** n - 1).each{|i|

ary0 = i.to_s(2).split('').map(&:to_i)

if ary0.count(0) % 2 == 0

if ary0.count(1) % 2 == 1 || ary0.count(1) == 0

ary.push(i.to_s(2).to_i)

end

}

p ary

}

出力結果

[1]

[100, 111]

[10000, 10011, 10101, 10110, 11001, 11010, 11100, 11111]

[1000000, 1000011, 1000101, 1000110, 1001001, 1001010, 1001100, 1001111, 1010001

, 1010010, 1010100, 1010111, 1011000, 1011011, 1011101, 1011110, 1100001, 110001

0, 1100100, 1100111, 1101000, 1101011, 1101101, 1101110, 1110000, 1110011, 11101

01, 1110110, 1111001, 1111010, 1111100, 1111111]

[100000000, 100000011, 100000101, 100000110, 100001001, 100001010, 100001100, 10

0001111, 100010001, 100010010, 100010100, 100010111, 100011000, 100011011, 10001

1101, 100011110, 100100001, 100100010, 100100100, 100100111, 100101000, 10010101

1, 100101101, 100101110, 100110000, 100110011, 100110101, 100110110, 100111001,

100111010, 100111100, 100111111, 101000001, 101000010, 101000100, 101000111, 101

001000, 101001011, 101001101, 101001110, 101010000, 101010011, 101010101, 101010

110, 101011001, 101011010, 101011100, 101011111, 101100000, 101100011, 101100101

, 101100110, 101101001, 101101010, 101101100, 101101111, 101110001, 101110010, 1

01110100, 101110111, 101111000, 101111011, 101111101, 101111110, 110000001, 1100

00010, 110000100, 110000111, 110001000, 110001011, 110001101, 110001110, 1100100

00, 110010011, 110010101, 110010110, 110011001, 110011010, 110011100, 110011111,

110100000, 110100011, 110100101, 110100110, 110101001, 110101010, 110101100, 11

0101111, 110110001, 110110010, 110110100, 110110111, 110111000, 110111011, 11011

1101, 110111110, 111000000, 111000011, 111000101, 111000110, 111001001, 11100101

0, 111001100, 111001111, 111010001, 111010010, 111010100, 111010111, 111011000,

111011011, 111011101, 111011110, 111100001, 111100010, 111100100, 111100111, 111

101000, 111101011, 111101101, 111101110, 111110000, 111110011, 111110101, 111110

110, 111111001, 111111010, 111111100, 111111111]

2015年5月26日火曜日

150526

Project Euler

Problem 512(2)

見かけが少し違うだけで、Problem 512(1) とほぼ同じ。

require 'prime'

n = 69

phi_ary = (0..n).map.to_a

Prime.each(n){|p|

p.step(n, p){|d| phi_ary[d] = phi_ary[d] * (p - 1) / p}

}

phi_ary = phi_ary[1..n]

# OEIS A000010のデータ

ary0 =

[1,1,2,2,4,2,6,4,6,4,10,4,12,6,8,8,16,6,18,8,12,

10,22,8,20,12,18,12,28,8,30,16,20,16,24,12,36,18,

24,16,40,12,42,20,24,22,46,16,42,20,32,24,52,18,

40,24,36,28,58,16,60,30,36,32,48,20,66,32,44]

# 一致の確認

p phi_ary == ary0

2015年4月21日火曜日

150421

Project Euler

Problem 512(1)

φ(n)を出力するコードを書いてみた。
（ちなみに、nが大きすぎるとエラーが出るので、

Problem 512はこの方法では解けないだろう。

私は違う方法でProblem 512を解いた。）

オンライン整数列大辞典の
A000010（http://oeis.org/A000010/list）
と比較し、答え合わせしてみる。

n = 69
phi_ary = [0]
(1..n).each{|i| phi_ary << i}
(2..n).each{|p|
if phi_ary[p] == p
p.step(n, p){|d| phi_ary[d] -= phi_ary[d] / p}
end
}
phi_ary = phi_ary[1..n]

# OEIS A000010のデータ
ary0 =
[1,1,2,2,4,2,6,4,6,4,10,4,12,6,8,8,16,6,18,8,12,
10,22,8,20,12,18,12,28,8,30,16,20,16,24,12,36,18,
24,16,40,12,42,20,24,22,46,16,42,20,32,24,52,18,
40,24,36,28,58,16,60,30,36,32,48,20,66,32,44]
# 一致の確認
p phi_ary == ary0

2015年3月8日日曜日

150308

Project Euler

Problem 506

Clock sequenceを出力するコードを書いてみた。

（Problem 506はこの数列の和に関する問題だが、

このコードを使って解ける問題ではないと思う。

私は違う方法でProblem 506を解いた。）

a = 0

ary = [1, 2, 3, 4, 3, 2]

N = 30

for i in (1..N)

n = i

s = 0

while n > 0

n -= ary[a]

s = s * 10 + ary[a]

a = (a + 1) % 6

end

p s

end

2014年9月22日月曜日

140922

Project Euler

Problem 44

P_n = n (3n - 1) / 2

副産物を記しておく。

def p(m)
(3 * m ** 2 - m) / 2
end

puts p(91650) + p(52430) == p(105586) # false

puts p(91650) + p(52430) == p(105587)
puts p(91650) - p(52430) == p(75172)

puts p(110461) + p(95506) == p(146024)
puts p(110461) - p(95506) == p(55500)

puts p(121168) + p(111972) == p(164983)
puts p(121168) - p(111972) == p(46303)

puts p(129198) + p(73745) == p(148763)
puts p(129198) - p(73745) == p(106084)

出力結果
false
true
true
true
true
true
true
true
true