hotpepsiの練習帳

SRM 566

03:03

Div1 Easy (250) PenguinSledding

問題

• ペンギンのパーシーがペンギンそり用のコースを設計する
• コースにはいくつかのチェックポイントがあり、それらを直線で結ぶ
• チェックポイントが同一直線状にないことは保証されている
• チェックポイントの座標の精度は非常に悪い可能性がある
• パーシーは慎重なので、直線が交わる可能性を排除したい
• 直線が存在しないケースも含めて、何通りの設計がありうるかを求める

方針

• 直線が交差する可能性があるとダメ
• つまりほとんどダメ。どういうのならOKなんだ...
• ゼロ本はOK
• 1本だけ残すならOK
• 点を共有する2直線はOK、つながってないのはだめ
• sample3の値が異常
• なるほど1点だけから出てるの(スター型みたいなの)はOKか
• 1～36本まで任意の組み合わせ=combinationの和かな
• それっぽい
• sample4で数が足りない
• 三角形なら3辺でもぶつからない!
• 三角形判定追加
• 提出
• Passed System Test
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_566/PenguinSledding.cpp

Div2 Easy (250) PenguinTiles

問題

• スライドパズル
• 全て同じ絵
• 右下を空けたい
• 最小の手数を求める

方針

• 右下が空いているならゼロ
• 右端か下端が空いているなら1
• それ以外は2
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_566/PenguinTiles.cpp

Div2 Medium (500) PenguinPals

問題

• ペンギンのマッチングサービス
• 青か赤のどちらが好きか聞く
• 円状に並ぶ
• 同じ色同士を直線で結ぶ
• 最大のペア数を求める
• 直線は交差してはならない

方針

• DPかな
• start,endを決めて、端点同士が同じ色なら、+1してその内側を数える
• 合わない...
• 隣り合うケースを忘れていた
• だいたい合う(だめすぎ)
• サンプル1のように並行で区切るやつしか考えていなかった
• 3等分みたいな区切り位置を考慮する必要がある
• start,endを任意の位置で区切ってメモ化
• 隣り合うやつは、端点同士の特殊な場合として吸収
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_566/PenguinPals.cpp

結果

o-- 111.06 372/701 rating 1327 -> 1373 (+46)

easyはTopCoderらしい問題だと思った。これが解けたのは非常に良かった。

そりのコースとしては全然だめだと思うが!

combinationの和は2の累乗ということに気づかなかった。

部屋はeasy提出者全員AC、medium提出者なし、チャレンジなしだった。

div2mediumが難しかった。