hotpepsiの練習帳

SRM 549

01:06

Div1 Easy (250) PointyWizardHats

問題

• 上用のコーンと下用のコーンを使って帽子を作りたい。
• 下コーンに上コーンを載せたとき、下コーンの頂点が上コーンに当たらず、かつ、下コーンが隠れないようにしたい。
• 最大でいくつの帽子が作れるか求める。

方針

• 何通りの帽子が作れるか、と読んでしまい時間を浪費。反省
• なんかDPっぽいなあと思いつつ、適当に貪欲で書く
• 終了30秒前にサンプル通るだけのコードを提出
• 終わったあたりで二部マッチングの存在を思い出す
• 被撃墜...すばらしい読解力だ!
• 蟻本を写経したら通った。しかし理解していない...
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_549/PointyWizardHats.cpp

結果

x-- 0pt 382nd rating 1392 -> 1339 (-53)

余分な部分をカットすればもっとたくさん帽子が作れますよ!