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しないと通らない。

SRM 584

02:24

Div2 Easy (250) TopFox

問題

• TopFoxに参加するためにハンドルネームを決めたい
• 姓と名のそれぞれ先頭から1文字以上取って連結する
• 何通り作れるか求める

方針

• 先頭からしか取れないぽい
• 重複する可能性がある
• setに突っ込む
• Passed System Test
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_584/TopFox.cpp

Div2 Medium (500) Egalitarianism

問題

• N人の市民がいる
• 友達かどうか与えられる
• 直接の友達の財産はプラスマイナスd以内
• 任意の二人の市民の財産の差の最大値を求める

方針

• グループが2つ以上あると差が計算できなくなる
• union findでグループの数を数える
• 友達の場合、最大の距離を求める
• Warshall-Floyd
• Failed System Test
• (終了後)
• 単純なWFでよかった
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_584/Egalitarianism.cpp

Div2 Hard (1000) Excavations2

問題

• N個の遺跡があり、それぞれの種類が与えられる
• それらのうちK個だけ発見され、種類が与えられる
• 元の遺跡の組み合わせの総数を求める

方針

• 種類ごとに建物がいくつあるか数えておく
• 与えられた種類の建物は必ず含まれている
• が、いくつ発見されたかは任意
• 1個の場合、2個の場合...を数え上げるので場合の数
• dp[使った種類][残りの発見数] みたいな感じでいける
• Failed System Test
• (終了後)
• メモ化を忘れた
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_584/Excavations2.cpp

結果

oxx -1 246.67 -25pt = 221.67pt 392nd/932 rating 1180 -> 1132

間抜けなミスで落としてもったいなかった。

TCO Marathon R3

23:48

問題 CirclesSeparation

• 平面に円が50～500個程度ランダムで配置される
• それぞれの円は中心座標と半径と重さを持つ
• 円が重ならないように再配置する
• 元の座標からの距離×重さだけスコアが加算される
• スコアを最小化する

やったこと

• 公式のビジュアライザを試すが、Javaなのでデバッグしづらかった
• 素朴な衝突判定と、簡単なビジュアライザを書く
• 重い順に1つずつ配置する
• 中心から元座標への方向をベースに、重なったら距離を伸ばしていく
• 全部配置し終わったら、空いている場所を少し詰める
• 衝突判定をグリッドにした
• 配置順や配置方法を少しずつ変えてみるがスコア改善せず
• 詰めるループを1回単位で呼び出せるようにして、リアルタイム表示できるようにするなど
• 速度を持たせてシミュレーションしようとしたが、重なりが解消できなくて挫折
• 最終的にパラメータをちょっといじったものを提出して70万点くらい

結果

not rated -> 1215

初参加だったがなかなか難しい。

ビジュアライザはこんな感じ。MFCで適当に書いた。配置順(の数字)を中心に書くようにした。

https://github.com/firewood/topcoder/tree/master/mm_81

SRM 583

01:26

Div1 Easy (250) TravelOnMars

問題

• 火星にN個の駅がある電車が走っている
• 駅は円周上になっていて0とN-1がつながっている
• ある駅から直通で移動できる駅の数が与えられる
• 始点と終点が与えられたとき、直通電車の最小乗車回数を求める

方針

• WF
• Challenge Succeeded
• 駅の数より範囲が広い場合で死
• 書き直し
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_583/TravelOnMars.cpp

結果

x-- 0pt rating 1213 -> 1180

Cの場合、負の剰余は負なので(((i+j)%N)+N)%Nとか、面倒なら(i+j+100*N)%Nとか。

div2で解く楽しみを取り戻してくる。

SRM 582

22:55

Div1 Easy (250) SpaceWarDiv1

問題

• 何人かの魔法少女と、それぞれの強さが与えられる
• 何種類かのエイリアンと、その強さと数が与えられる
• 魔法少女は、自分の強さ以下の敵は倒せる
• 敵を1匹倒すごとに魔法少女の疲労が1増える
• 疲労の最大値を最小化せよ

方針

• 貪欲で試す
• サンプルと合わない
• (終了後)
• 二分探索
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_582/SpaceWarDiv1.cpp

結果

--- 0pt rating 1265 -> 1213 (-52)

基本的に弱い。