トップ 差分 一覧 ソース 検索 ヘルプ RSS ログイン

AtCoder Grand Contest 001

[競技プログラミング]

AtCoder Grand Contest 001

AtCoder Grand Contest 001

  A - BBQ Easy

  • 入力値からN本の串焼きを作る
  • このとき、選んだうちの短い方の1本が具材の数となる
    • 串の長さを大きい順にソートして2つずつ選んで、そのうちの小さい方の串の長さの合計値を求めればよい?
lines = $stdin.read
array = lines.split("\n")
 
N = array[0].to_i
L = array[1].split(" ").map(&:to_i).sort.reverse
 
guzai = 0
 
for i in 0..N-1
  guzai += L[i*2+1]
  #puts "plus #{i*2+1}"
end
 
puts guzai

  B - Mysterious Light

図形の定義になんかあるのだろうか?自力では回答できず。

  C - Shorten Diameter

 N 頂点の木があり、頂点には 1~N の番号がついています。

この時点で駄目だった。頂点ってどこのことを指すのか。。。

  D - Arrays and Palindrome

  E - BBQ Hard

  • 自力回答 - TLE
    • まあ、そんなに簡単にはいかない。計算量を減らさないとだめ。どうやら動的計画法(DP)を使うらしい。
lines = <<'EOS'
3
1 1
1 1
2 1
EOS

#lines = $stdin.read
array = lines.split("\n")

N = array[0].to_i

array.shift

answer = 0

array.combination(2) do |left,right|
  #printf("'%s' '%s'\n", left, right)
  meat = 0
  meat += left.split(" ")[0].to_i
  meat += right.split(" ")[0].to_i

  vegi = 0
  vegi += left.split(" ")[1].to_i
  vegi += right.split(" ")[1].to_i

  meats = Array.new(meat+vegi)
  combi = meats.combination(vegi)
  #puts "#{meat}C#{vegi} = #{combi.size}"
  answer += combi.size
end

puts answer % (10**9 + 7)
 nCr を求める方法のひとつとして格子上の経路数として説明されるDPが知られている。 この経路の始点を複数にして同時にやる。

なるほど、知らんわ。。。 csegeek.com - Dynamic Programming

 スタート地点を (-A1, -B1), ..., (-AN, -BN) のいずれかとして ゴールを (A1, B1), ..., (AN, BN) のいずれかとする場合の数を求めれば良いです。

ロジックはわかったのだが、いくら頑張っても巨大な数で死ぬ。どうすればいいのか…

  F - Wide Swap

AtCoder Grand Contest 001 - 解説

お名前: コメント: