TopCoder SRM 574 Div2

TopCoder

Easy - CityMap

マナオさんは初めて来る街に到着したので、とりあえず地図を買うことにしました。

その地図は高さH・幅Wのグリッドとして表されていて、各セルには道路を表す '.' 、もしくは、施設の種類を表す記号として [A-Z] のアルファベット１文字（例えば 'M' は地下鉄の駅（Metro Station）を表すなど）のどちらかが記されています。

ところがその地図には、施設の種類を表す記号が何を表しているかという対応表が付いていませんでした。しかしながら、「ある施設はこの街にいくつ存在するか」という情報は載っていました。さらに都合のいいことに、この街に存在する施設の数は、種類ごとに重複していません（要するに、地下鉄の駅が3つあるなら、その他のあらゆる種類の施設の数は3つではないということ）。これだけ情報があれば、その記号が何を表しているか分かりますね！

しかしながら地図の中の記号の数を調べるのは大変です。優秀なプログラマであるあなたは、マナオさんに「『この街にk個ある施設』を表す記号は何か？」という質問に答えるプログラムを即席で作ってくれるようにお願いされました。助けてあげましょう！

TopCoderのDiv2-Easyの問題文としては、かなりReading-Hardな部類に入ると思います。

基本的に「やるだけ」なのですが、'.'を無視することを忘れないようにしましょう。問題文を読まなかった人が地球上に最低でも１人います。 油断すると

cityMap = {"..", "MM"}
POIs = { 2 }

で落ちます。

Medium - TheNumberGameDiv2

マナオさんは"The Number Game"と呼ばれる、１人用ゲームを考えました。

プレイヤーは、始めに任意の整数AとB（1 <= A, B <= 999,999,999）を選択します。ただし、AとBは10の累乗であってはいけません10進数表現で0を含んではいけません。

プレイヤーはAを操作してBにすることを目指します。プレイヤーが１回の操作で行える操作は次のどちらかです。

  • Aを10で割る（小数点以下は無視）
  • Aを文字列と見て、反転する（例：123 → 321）

このゲームを成功させるのに必要な操作の最小の回数を答えて下さい。 AからBを作れない場合には -1 を返して下さい。

制約の大きさから見ても、Aから変換によって作れる数字の個数はたかが知れています。BFSしましょう。

数値と文字列を相互に変換する方法を知らない人は、いい機会なのでテンプレートに lexical_cast を追加しましょう。

// 使い方1: string str = "123"; int num = lexical_cast<int>(str); // string -> int
// 使い方2: int num = 123; string str = lexical_cast<string>(num); // int -> string
template<class T, class U> T lexical_cast(const U& from)
{ T to; stringstream ss; ss << from; ss >> to; return to; }

int rev(int n) {
    string s = lexical_cast<string>(n);
    return lexical_cast<int>(string(s.rbegin(), s.rend())); // stringのコンストラクタに reverse_iterator を渡している
}