読者です 読者をやめる 読者になる 読者になる

nullnull7の日記

プログラミング、写真、旅、その他日常について。

SRM 525 Div2 (11/30)

TopCoder

スラスラ解けて調子いい…と思ったのは勘違いでした。

250. RainRoad
問題:n*2マスの地図が渡される。障害物を避けて左上から右上までいけるか? 移動はタテヨコナナメに行ける。

  • 途中まで探索する気満々だったけどそんな問題じゃなかった
  • 同じ列に障害物がなければOK

600. DropCoins
問題:複数のコインがのったテーブルがある。プレイヤーはコイン全体を上下左右にずらして、のっているコインをテーブルから落とすことができる。テーブル上のコインが丁度K枚になるような最小の手数のずらし方を求めよ

  • 枝刈りしつつbfsでいけそう。盤の状態を忠実に再現してbfs。提出
  • …がしかし撃墜される。後から試したら、計算量もメモリも足りてない。枝刈りすればいけるはずだったのだけど…
  • 他の人の解法を見ると、条件を満たす矩形を全探索すれば良いだけだった模様。

900. MagicalSquare
問題:3x3マスの魔方陣がある。陣のそれぞれのマスには何らかのアルファベットが入り、列or行の文字列をつなげたものがそれぞれの列・行に記述されている文字列と等しくなる。ありうる魔方陣のパターン数を求めよ

  • 時間は割とあったけどできなかった
  • 後から、問題文を勘違いしていたことに気付く。
    • 文字をつなげたものではなく文字の集合が記述されているアルファベットの集合に等しくなると勘違い。

Challenge Phase

  • 最初に開いた人が明らかにサンプルすら通ってない。サンプルを選んで撃墜。
    • 始めての撃墜。ちょっとドキドキした
  • 撃墜できたしここまでの点数はなかなかいいし……と浮かれていたら600が撃墜される

結果:
ox- +50 289point 3320位
レーティング 1120 -> 1172
下がったと思ったらちょっと上がった。でもまだdiv2だなー

反省タイム:

  • 600は、別の解法を十分考えられそうだった。 1つ解法を思いついても、更に簡単な解き方があるのでは、と疑うべき
    • そして、それ以前にbfsでいける、と思ってしまったことを反省。
    • そもそも、最悪ケースのテストを時間ロスを言い訳に行わなかった。面倒でもサンプルケース作ってテストするべき
  • 900を後で解く