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

TopCoder SRM 538 Div2

TopCoder

xo-
898905
オーダーを見極められていない思考法

300

'L'というコマンドが与えられたら左に1マス、'R'というコマンドが与えられたら右に1マス動くロボットがある。

複雑な事情により、コマンドを与えたロボットが、最大でどこまで離れるかを調べなければならなくなった。
しかし不幸な出来事が起こり、ロボットに与えたコマンドの一部が読めなくなってしまった。

読めなくなった部分のコマンドは '?' で表される。一番離れる時は何マス離れますか?

  1. えっ!easyなのにDPなの!?
  2. ああ、別にDPじゃなくても大丈夫か
  3. 怪しげな探索を書く→TLE... このコードって最大ケースだったら 2^50 じゃん... なぜ検証しなかった...

500

任意の座標から(1, 0), (0, 1), (-1, 0), (0, -1) のどれかに移動できる座標軸があり、はじめに座標(0, 0) にいます。
整数の配列 x, y が与えられるので、(x[i], y[i]) を全て最低でも1度通り、そのどれかに止まる、という経路をたどるときの経路の長さを調べます。

その経路の長さが、(偶数になりうる or 奇数になりうる) かどうか調べて下さい。


非常に怪しい嘘解法が通ってしまった。

(0, 0) から いずれかの頂点に行く道の長さが奇数の場合も偶数の場合も両方ともある→CAN
(0, 0)からの道が奇数のみ→頂点から頂点までが偶数だけ→かならず奇数
(0, 0)からの道が偶数のみ→頂点から頂点までが偶数だけ→かならず偶数

という考え方を拡張していくと、よく理解していないけれど通ってしまいました。