n-knuu's logs

憧れ駆動。だいたい競プロ

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)の偶奇によって場合分けして考える

  1. 2*C/Nと(N-1)がともに偶数、もしくは奇数のとき
    • dは何であっても右辺は偶数になる
    • ここでa0が正の整数になるためには、dはできるだけ小さい正の整数であったほうがよい
    • よって、d=1として、a0が正になるか計算すれば良い
  2. 2*C/Nが偶数、(N-1)が奇数のとき
    • 右辺が偶数になるには、(N-1)*dが偶数でないといけないので、dは偶数
    • (i)の場合と同様、dはできるだけ小さい正の整数であったほうがよいので、d=2として、a0が正になるか計算する
  3. 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さんに聞いた問題は自分で殆ど読まずに解いてたし、なんとか上手く伝えられないか考えたい
      • そのためにブログ書いてるはずなんだけど、おざなりになったりすることもあるし、かといって時間かけすぎるのも厳しいし、なんとも...