hotpepsiの練習帳

SRM 542

00:26

Div1 Easy (250) PatrolRoute

問題

• X×Yの大きさの空間がある。
• x座標とy座標がそれぞれ異なる任意の3点を選ぶ。
• それらをユークリッド距離が最短かつループするように結ぶ。
• 最短距離minTと最大距離maxTが与えられるとき、3点の選び方が何通りあるか求める。

方針

• 隅を決めてDPみたいなの書いてみるがうまくいかない
• submitできずに終了
• 解きなおし
• いろいろ解き方がある
• 3点の座標の上端、下端、左端、右端で四角形を形成すると考える
• パトロールする距離は、この四角形の横と縦のサイズの2倍になる
• 3点をA,B,Cとして、左上をA、右下をBとして固定してみる
• もう一つの点Cは中央の(横サイズ-1)×(縦サイズ-1)のどこに置いてもいい
• 上端、下端、左端、右端の座標をAx,Ay,Bx,Byとしたとき、Cの座標をAx,Ay,Bx,Byのどれかと交換しても四角形のサイズが同じになり、これが6通りある
• x座標Ax,Bx,Cxの置き方が3!通り、y座標Ay,By,Cyの置き方が3!通りで、点A,B,Cは順不同なので並べ方3!通りは重複分だから(3!×3!)÷3!＝6通り、な気がする
• 四角形全体の移動(X-横サイズ)×(Y-縦サイズ)を考慮
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_542/PatrolRoute.cpp

Div2 Easy (250) WorkingRabbits

問題

• N匹のうさぎがいる。
• うさぎの生産性は、別のうさぎとの仕事の総和の平均である。
• 全うさぎの個々の仕事量が与えられる。
• うさぎの生産性を求める。

方針

• 半分は同じもの
• 半分だけ合計して(N×(N-1))÷2で割る
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_542/WorkingRabbits.cpp

結果

--- 0pt 286th rating 1420 -> 1368 (-52)

メモ用紙に何通りか列挙してようやくわかった。

ちなみに1000000007はエマープ(emirp)とのこと。