TopCoder Member SRM 468 DIV1

Programming Algorithm TopCoder SRM

Overview

140.04 + 295.34 + 0.00(Opened) + 0=435.38
167th in Div1
SRM Rating: 1698 → 1782(+84)
なんかRating自己記録更新っぽ

250 Easy

携帯のT9入力を考える。
アルファベットにはそれぞれ1-9の番号の1つと関連づけられる。ある番号列はそれに合致するアルファベット列のうち辞書にあるもののどれかを指す。
候補が複数ある場合は、番号列に続く#と*の個数から判断する。((#の個数)+(*の個数)*5)番目の単語(辞書順で0-origin)を選択する。
0は空白を意味する。
T9に基いた入力シーケンスから入力された文字列を生成せよ。

やるだけ。C#でのDictionaryとListを覚えた。

500 Medium

一直線の道があり、町がN+1個(N<=400000)ある。町iと町i+1の間のコストが、車を使った場合と航空機を使った場合でそれぞれ定義されている。これは線形合同法による擬似乱数によって生成される。
航空機は隣接しない町の間を一回の離着陸で飛ぶことができるが、コストは単純に合計値となる。
航空機の離着陸の上限がK(K<=40)で与えられる。
最小のコストを求めよ。

ただのDP。擬似乱数を1度生成しきってから作業したりすると死ぬよ、とか、N=0のとき死ぬことがあるかもね、とか。

まあ普通に書けば落ちない。Javaで書いた。

1000 Hard

N個のフロアがあり、各フロアには頂点がいくつかある。
フロアiのいずれかの頂点とフロア(i+1)%Nのいずれかの頂点を結ぶエレベーターがいくつかある。
できるだけ多くの頂点に警備員を配置したい。あるエレベーターの両端に警備員を配置してはならない。
最大何人の警備員を配置できるか。

一般には最大安定集合なので、Nが偶数のときは一般に解があるが、Nが偶数と限らなければその一般化では解けない。
Constraintsを良く読むと、ある特定のフロアについての全探索とかで解けるらしい。

まとめ

  • ○250で問題文をちゃんと読んだこと。
  • ×250さすがに問題読むのに時間かけすぎたこと。
  • ○500のDPをそこそこの時間で思いついたこと。

今回はわりと妥当かな。

準急さんは今回は調子悪くてお休みだそうで。おだいじに。