hotpepsiの練習帳

SRM 585

00:42

Div2 Easy (250) LISNumberDivTwo

問題

• 数列が与えられる
• 昇順の部分を1グループとして区切る
• グループ総数の最小値を求める

方針

• 落ち着く
• Passed System Test
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_585/LISNumberDivTwo.cpp

Div2 Medium (500) TrafficCongestionDivTwo

問題

• 都市と道路がある
• 車が都市から都市へ道路を通る
• それぞれの都市で、通る車は1台のみとする
• 都市を節点、道路を辺として、完全2分木をなす
• 高さが与えられる
• 最小の車の台数を求める

方針

• 3つの都市を周ったらおしまいっぽい
• 3つをペアとして加算
• ということは、2段単位で加算
• 一番下の段からノード数の半分を足して、ノード数を1/4していく
• Passed System Test
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_585/TrafficCongestionDivTwo.cpp

Div2 Hard (1000) EnclosingTriangleColorful

問題

• 色の異なる4辺が与えられる
• 辺上の点は辺の色
• 4辺の内側に黒点の集合が与えられる
• 3色の点を使って三角形を作る
• 黒点を全て含む三角形がいくつできるか求める

方針

• 左端の1点を始点として決める
• 全ての黒点と傾きを求めて、一番大きなものが左端
• 上端の点の範囲がわかる(交点より左には置ける)
• 同様に右端を決めると、やはり上端の点の範囲がわかるので両方を満たすものを数える
• みたいに考えたが実装できず
• (終了後)
• くるとんさんのブログを読む
• 領域の4点を時計回りに決める
• 三角形の点について、点A→B→C→Aと時計回りに置くことにする
• 線分ABについて考えると、全ての黒点が右側(Cへの方向)にあればよい
• 線分BCもCAも、その右側に黒点があればよい
• 交差判定で、負か線上のものが該当。正の場合は逆方向(BA)が満たしていると考える
• 線分が全て判定できたら全探索で数える
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_585/EnclosingTriangleColorful.cpp

結果

oo- 245.97 + 443.87 = 689.84pt 83rd/1348 rating 1132 -> 1191 (+59)

700人以上mediumを通すという早解きの回。まあまあ早く提出できた。

mediumは下から足したが、div1 easyの制約だと、上から足してDPしないと通らない。