SnackDown 2016 Online Elimination Round
SnackDown 2016 Online Elimination Roundにe-monさんと出た
361位でTシャツラインにあと61位届かなかった
VCake
- 解法
制約から、切るのは2回だけなので、切り方は2回に対して[縦に切る, 横に切る]の2通りあるから、計4通りある。
また、どの大きさのケーキから切り出して行くかで、3!=6通りあるので、4*6=24通りについて全て調べていけばよい。
- コード
Chocolates for Everyone
- 問題
初項と公差が正の整数で、等差数列のN項の和がCになるような列について、初項と公差を1つ答えよ
もしなければNoと出力せよ
- 解法
等差数列の初項をa0, 公差をdとおくと、等差数列の和の公式より、N*(2*a0 + (N-1)*d)/2 = Cが成り立つ
よってまず、2*C%N=0が必要となる
式を整理すると、2*a0 = 2*C/N - (N-1)*d
左辺が偶数でないとダメなので、dを2*C/Nと(N-1)の偶奇によって場合分けして考える
- 2*C/Nと(N-1)がともに偶数、もしくは奇数のとき
- dは何であっても右辺は偶数になる
- ここでa0が正の整数になるためには、dはできるだけ小さい正の整数であったほうがよい
- よって、d=1として、a0が正になるか計算すれば良い
- 2*C/Nが偶数、(N-1)が奇数のとき
- 右辺が偶数になるには、(N-1)*dが偶数でないといけないので、dは偶数
- (i)の場合と同様、dはできるだけ小さい正の整数であったほうがよいので、d=2として、a0が正になるか計算する
- 2*C/Nが奇数、(N-1)が偶数のとき
- 右辺は偶数にならないので、条件を満たす等差数列は存在しない
- コード
Coloring A Tree
- 問題
N頂点の木が与えられ、木の各頂点をK色塗ることを考える
同じ色を塗ったあとの木を、違う色が接続している枝で切断したときに、同じ色の頂点が全て連結になるような塗り方は何通りあるか
- 解法
切断の仕方と、切断してできたグループの色塗り方を考えるだけでよい(入力が木なので、切断する枝が決まれば、切断後のグループが一意に決まる)
よって、i種類の色を使うときは、N-1の枝からi-1本選んで切断し、K種類からi個の色を塗るので、このときの場合の数は(N-1) C (i-1) * K P i 通りであり、これを、i=1からi=min(N, K)まで和をとれば良い
- コード
感想と反省
- チーム戦難しい
- チームメイトに問題を任せる判断とか、問題概要の伝え方とか
- 問題概要を伝えるのが苦手っぽい
- わかりやすくなるように、と思ってやってはいるものの、いくつか抜け落ちたりしていることがあった
- e-monさんに聞いた問題は自分で殆ど読まずに解いてたし、なんとか上手く伝えられないか考えたい
- そのためにブログ書いてるはずなんだけど、おざなりになったりすることもあるし、かといって時間かけすぎるのも厳しいし、なんとも...