SRM初参加
TopCoderで行われたSRM647に初参加しました。もちろんDiv2です。
参加登録
最も時間のかかった問題でした。Javaアプレットから参加登録ができることになかなか気づきませんでした。
Easy
普通に解けたと思っていたのですが、配列の取り方がまずくて要素が1つ足りてないという初歩的なミスをしました。
機械翻訳を使えば思ったより英語が読めることに気づきました。
Medium
結構読むのに苦労しましたが、分かりやすい貪欲だったのでアルゴリズム自体はEasyよりも簡単な気がしました。
Hard
アルゴリズムを思い付いたのでテンション上がって実装したら、サンプルインプットでREをくらいました。
それで制約を見返すと配列が取れないことに気づきました。
ちなみにその時考えていた解法は、
建物に高さ制限のある場所の制限された高さからKずつ増加させると、ある場所における最大の高さはいくつになるか、というDP(のようななにか？)を1～NとN～1の双方向で行い、
ans = max(ans,min(dp1[i],dp2[i])) としていました。
しかしこれだと10^9の配列が2つ必要になり、REでした。
単調なKずつの増加なので、メモリを節約するには計算すればよいですかね...？
結果
Mediumだけ通りました。
感想
Easyの問題が解けないレベルかと思っていたのですがわりと戦えたので、これからもDiv2で遊んでいきたいです。
Hardの問題は、結局実装してません。
