AtCoder Beginner Contest 051

2017年1月7日のAtCoderの記録。言語はRubyです。

問題はこちら：AtCoder Beginner Contest 051
私の回答一覧はこちら：自分の結果

難易度は、A<<B≒C<<<<<<<<<<Dくらいに感じた。D問題だけやけに辛くないですか。

A問題

問題文には色々と条件があるが、要するに","を" "に置換すれば良い。

puts gets.gsub( ",", " ")

B問題

一般的でない解法で解いたけど、普通に解いたほうが良かった気がする。
「$(0 \leq x,y,z \leq K)$っていう条件がなかったら、S個を3つの部分に分けるから$ {}_{n+2}\mathrm{C}_2$で済むのになー」と最初に思った。
数学的には、XYZ空間上の立方体$(0 \leq x,y,z \leq K)$と、平面$x+y+z=S$ との共通部分となる。で、この共通部分はSを0から増やしていくと、正三角形→六角形→正三角形と変化する。この上の格子点の個数を求めれば良い。

最初の正三角形は、条件$S \leq K$のとき。 このときは$(0 \leq x,y,z \leq K)$が無意味である。したがって、$ {}_{n+2}\mathrm{C}_2$で求まる。(三角数)
次の六角形は、正三角形から3つの正三角形を切り落とした形である。……という感じで場合分け。

k,s = gets.split(" ").map{|v|
	v.to_i
}
if k >= s then
	puts (s+2)*(s+1)/2
	exit
end
if s >= 2*k then
	t = 3*k - s
	puts (t+2)*(t+1)/2
	exit
end
puts (s+2)*(s+1)/2 - (s-k)*(s-k+1) /2*3

C問題

解法は解説そのままだったので特に説明はしない。
文字列の繰り返しは*演算子でできることを学んだ。

sx, sy, tx, ty = gets.split(" ").map{|v|
	v.to_i
}

x = tx-sx
y = ty-sy

ans = ""
ans << "R"*x
ans << "U"*y
ans << "L"*x
ans << "D"*y

ans << "D"
ans << "R"*(x+1)
ans << "U"*(y+1)
ans << "L"

ans << "U"
ans << "L"*(x+1)
ans << "D"*(y+1)
ans << "R"

puts ans

D問題

各頂点からダイクストラ法で他の全長店までの最短路を求める。で、どの最短経路にも含まれない辺の個数を出力。アルゴリズムは書き終わったけどコンパイルエラーが取れなくて、直しているうちに時間切れになった。ダイクストラ法のアルゴリズムを綺麗に忘れていて焦ったし、アルゴリズムを思い出しても全然コードに直せなかった。