「 2018年04月 」一覧

AtCoder GC023 A: Zero-Sum Ranges

問題

https://agc023.contest.atcoder.jp/tasks/agc023_a

解法

最初に問題を見て、これ本当に200点?って思うくらい悩んだ。

とりあえず、累積和をとってみる。

例えば、サイズ4の数列:{a1 a2 a3 a4}の累積和を考える。

S1 = a1
S2 = a1 + a2
S3 = a1 + a2 + a3
S4 = a1 + a2 + a3 + a4

この時、部分数列の和は累積和の差で求められるのがポイント。

例えば、{a3 a4} は、S4 – S2 で求めることが出来る。
つまり、{a3 a4} の和が0になるのは、S4 – S2 = 0、つまり、S4 = S2 な場合といえる。

よって、累積和のうち、等しいものの組み合わせを数え上げることになる。

入力例1:{1 3 -4 2 2 -2}の場合、累積和は{1 4 0 2 4 2}なので、等しいものは、2が2個と4が2個となり、

2C2 + 2C2

となる。さらに、累積和自体が0の場合はそれ単独でも組み合わせの一つとなり得る。

この場合、累積和の先頭に0を追加してやり、{0 1 4 0 2 4 2}とすることで、同様に扱うことが出来る。

2C2 + 2C2 + 2C2

実装

n = gets.chomp.to_i
a = gets.chomp.split.map(&:to_i)

s = [0]
for i in 0..(n-1)
    s[i+1] = a[i] + s[i]
end

h = Hash.new(0)

s.each do |v|
    h[v] += 1
end

ans = 0
h.each do |k, v|
    next if v == 1
    ans += v * (v-1) / 2
end
puts ans

GCJ 2017 Qualification Round B: Tidy Numbers

問題

与えられた整数Nについて、N以下で数字が左から昇順に並ぶ最大の数を求める。

例えば、132であれば、129が132以下で数字が1,2,9と昇順に並ぶ最大の数となる。

https://code.google.com/codejam/contest/3264486/dashboard#s=p1

方針

Nから順にデクリメントして条件にあうかチェック、、、みたいな実装だとSmallはクリアできてもlargeは時間がかかりすぎてしまう。

よって、単なる数字の並びの規則性という観点でロジックを考えると、

・左から数字をチェックしていき、降順になる箇所が見つかった場合、前の数字を一つ小さくし、以降の数字を全て9に変更する
 例:14548 -> 14499
・上記操作によりさらに一つ前の数字との大小関係が変わる場合は、同様の処理をもう一つ前の数字についても行う。これを繰り返す。
 例:14438 -> 14399 -> 13999

となる。

実装

gets
n = 1
STDIN.each_line do |line|
    digits =  line.chomp.chars.map(&:to_i)
    prev = digits[0]
    for i in 1..(digits.size-1)
        if digits[i-1] > digits[i] then
            digits[i] = 9
            digits[i-1] -= 1
            j = i - 1
            while(j > 0) do
                if digits[j-1] > digits[j] then
                    digits[j] = 9
                    digits[j-1] -= 1
                end
                j -= 1
            end

            for j in (i+1)..(digits.size-1)
                digits[j] = 9
            end
            break
        end
    end
    printf "Case #%d: ", n
    digits.select{|c| c > 0}.each  do |c|
        print c
    end
    printf "\n"
    n += 1
end