○問題文http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1167
○解説動的計画法で解くことができますが、またしてもRubyだと想定解法でもTLEになってしまいます。
計算量は前処理10^6*180のみで入力に対してO(1)です。
前処理で10^6までの最小値を全て列挙させています。
○提出したコードMAX = 1000001
dp = Array.new(MAX, MAX)
odd_dp = Array.new(MAX, MAX)
dp[0] = odd_dp[0] = 0
for i in 1...181 do
num = i * (i + 1) * (i + 2) / 6
dp[num] = 1
if num % 2 == 1
odd_dp[num] = 1
end
for j in num...MAX do
if dp[j - num] + 1 < dp[j]
dp[j] = dp[j - num] + 1
end
if num % 2 == 1
if odd_dp[j - num] + 1 < odd_dp[j]
odd_dp[j] = odd_dp[j - num] + 1
end
end
end
end
loop do
n = gets.chomp.to_i
if n == 0
break
end
puts "#{dp[n]} #{odd_dp[n]}"
end
○問題文http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2254
○解説動的計画法で解くことができます。
dp[所持している武器の状態] = 最小時間
計算量はO(2^n * n^2)ですが、RubyだとなぜかRuntime errorになりました。
原因は分かっていません。
一応Javaで同等の処理を行いAcceptになることを確認しました。
○提出したコード①loop do
n = gets.chomp.to_i
if n == 0
break
end
t = Array.new(n) { Array.new(n + 1) }
n.times do |i|
t[i] = gets.chomp.split.map(&:to_i)
end
dp = Array.new(1 << n)
(1 << n).times do |i|
dp[i] = 10000000
end
dp[0] = 0
(1 << n).times do |i|
n.times do |j|
if (i >> j) % 2 == 1
next
end
minT = t[j][0]
n.times do |k|
if ((i >> k) % 2 == 1) && (minT > t[j][k + 1])
minT = t[j][k + 1]
end
end
if dp[i | (1 << j)] > dp[i] + minT
dp[i | (1 << j)] = dp[i] + minT
end
end
end
puts dp[(1 << n) - 1]
end
-----
import java.util.*;
public class Main
{
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
while (true) {
int n = scan.nextInt();
if (n == 0) break;
int[][] t = new int[n][n + 1];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n + 1; j++) {
t[i][j] = scan.nextInt();
}
}
int[] dp = new int[1 << n];
for (int i = 0; i < (1 << n); i++) {
dp[i] = 100000000;
}
dp[0] = 0;
for (int i = 0; i < (1 << n); i++) {
for (int j = 0; j < n; j++) {
if ((i >> j) % 2 == 1) continue;
int minT = t[j][0];
for (int k = 0; k < n; k++) {
if (((i >> k) % 2 == 1) && (minT > t[j][k + 1])) {
minT = t[j][k + 1];
}
}
if (dp[i | (1 << j)] > dp[i] + minT) {
dp[i | (1 << j)] = dp[i] + minT;
}
}
}
System.out.println(dp[(1 << n) - 1]);
}
}
}
○問題文http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2300
○解説N色の中からM色選ぶ全探索をすればよいです。
色をビットで管理してあげると実装が楽になります。
また、Rubyでは a ** 2 のような表記でa^2の計算をすることができます。
○提出したコードdef bitCount(i)
res = 0
while i > 0 do
if i % 2 == 1
res += 1
end
i /= 2
end
res
end
n, m = gets.chomp.split.map(&:to_i)
l = Array.new(n)
a = Array.new(n)
b = Array.new(n)
n.times do |i|
l[i], a[i], b[i] = gets.chomp.split.map(&:to_f)
end
ans = 0.0
(1 << n).times do |i|
if bitCount(i) != m
next
end
sum = 0.0
n.times do |j|
if (i >> j) % 2 == 0
next
end
n.times do |k|
if (i >> k) % 2 == 0 || j >= k
next
end
sum += (l[j] - l[k]) ** 2
sum += (a[j] - a[k]) ** 2
sum += (b[j] - b[k]) ** 2
end
end
if sum > ans
ans = sum
end
end
puts ans
○問題文http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2330
○解説N体を調べる場合、それを3等分にしてN/3個ずつ天秤の左右に乗せます。
天秤が傾いた側、または天秤の重さが等しければ天秤に乗せていないN/3個に目的の物が含まれているので最悪の場合でも log_3(N)回調べればよいことになります。
○提出したコードn = gets.chomp.to_i
lb = 0
ub = 1
count = 0
while n <= lb || ub < n do
lb *= 3
ub *= 3
count += 1
end
puts count
○問題文http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2253
○解説幅優先探索で解きます。
※幅優先探索とは探索アルゴリズムのうちの一つです。
各座標を配列に格納していますが、負の値が与えられる場合もあるので、それを考慮して入力で与えられた値に適当な数を足しています。
[Rubyメモ]
・多次元配列を生成するときは、Array.new(サイズ){ Array.new(サイズ, 初期値)}のような書き方ができます
・配列をqueue代わりにしていますが、shiftでpop、pushでpushの動きができます。
○提出したコードdx = [-1, -1, 0, 0, 1, 1]
dy = [-1, 0, -1, 1, 0, 1]
loop do
t, n = gets.chomp.split.map(&:to_i)
if t | n == 0
break
end
visited = Array.new(200) { Array.new(200, 0) }
field = Array.new(200) { Array.new(200, 0) }
n.times do
x, y = gets.chomp.split.map(&:to_i)
field[y + 100][x + 100] = 1
end
sx, sy = gets.chomp.split.map(&:to_i)
sx += 100
sy += 100
queue = [[sx, sy, 0]]
visited[sy][sx] = 1
while !queue.empty? do
tmp = queue.shift
if tmp[2] + 1 > t
next
end
6.times do |i|
nx = tmp[0] + dx[i]
ny = tmp[1] + dy[i]
if field[ny][nx] == 1 || visited[ny][nx] == 1
next
end
visited[ny][nx] = 1
queue.push([nx, ny, tmp[2] + 1])
end
end
ans = 0;
200.times do |i|
200.times do |j|
ans += visited[i][j]
end
end
puts ans
end