【Topcoder】Rookie SRM 6 のはなし

全体12位になってました。全体的に早解き回でした。

問題概要のところは日本語に雑に訳しました。一部、簡単のために少し変えたところがありますが許してください><

Easy - BiggestDuplicate (250 pts.)

問題概要

　長さ の数列が与えられる。数列内に重複して存在する数のうち、最大の数を求めよ。そのような数が存在しない場合は -1 を返せ。

解法

　 と制約が小さいのでびっくり。降順にソートすれば、重複して存在する数どうしは隣り合うはずなので、1 番目から順にみていき、 番目と 番目の数が同じであるときは、 番目の数を返して終了すればよい。最後まで行って値を返さなかった時、重複する数が存在しないので、-1 を返して終了すればよい。

得点

　249.33 pts. でした。なんか、もっと早く実装できた気がします。

Medium - LinearSignals (500 pts.)

問題概要

　直線の道路があり、路上にいくつか信号が並んでいる。あなたは、左から の距離のところにいるとき、区間 ] 内の信号を全て一度に受け取ることができる。このとき、あなたは最大でいくつの信号を一度に受け取ることができるか？

解法

　またも制約が小さいので、全部の位置でうまいこと全探索できる。添え字の限界を超えないよう注意するだけ。

得点

　490.06 pts. でした。なぜかクソバグを繰り返したのでめっちゃ遅くなってしまいました。

Hard - SlowTerrain (1000 pts.)

問題概要

　マップ上を歩く。'S' のマスから 'D' のマスまで行き、辺で隣り合う都市へ移動することができる。各都市のマスには 0 ~ 9 までの数字がどれか 1 つ書かれており、各都市内を移動するのにその数字だけ時間がかかることを示す。この時、'S' から 'D' まで到達できる最短時間を求めよ。

解法

　基本的には dijkstra法でいける。各都市内の移動に時間はかからないと考えてよくて、各マスの数字は「隣接するマスからその都市へ行くのにその数字だけ時間がかかる」ことを示していると捉えてよい。こうすれば、頂点数もあまり多くならないので、全頂点について辺を張って、dijkstra 法を単純に回せば解ける。

得点

　906.80 pts. でした。実装が遅すぎる！！！！！

全体を通して

　早解きをもっと鍛えようね