http://yukicoder.me/contests/165
以下、解説
No.512 魔法少女の追いかけっこ
http://yukicoder.me/submissions/171172
全ての隣接する交差点についてチェックしていく。
kobaさんがi番目の交差点に着いた時に、師匠がi番目とi+1番目の交差点にいることを判定する。
これは時間を測れば良い。
tx = A[i] / (X * 1000), ty = A[i + 1] / (Y * 1000)とすると、kobaさんがtx時間後に交差点iに到着、師匠がty時間後に交差点i+1に到着することが計算できる。
ここで、ty < txであれば、kobaさんがi番目の交差点に着く前に師匠がi+1番目の交差点に着いてしまうので、ダメ。
注意点として誤差があるので、小数で「A < B」と比較する時は、「A < B - EPS」とする方が安全
#define EPS 1e-10 if(a <= b + EPS) // a <= b if(a < b - EPS) // a < b if(abs(a - b) < EPS) // a == b
No.513 宝探し２
No.514 宝探し３
http://yukicoder.me/submissions/171456
宝探し２の方はやってないけれど、二分探索とかでx座標とy座標をとってくればOKです。
それぞれ独立なので、xとy座標は個別に特定していくのがいいと思います。
実はアドホックな解法がある。
以下、MAX=1e9
(0,0)からのマンハッタン距離をaとすると、求めたい座標は直線y = -x + a上にある。
(0,MAX)からのマンハッタン距離をbとすると、求めたい座標は直線y=x+(b-MAX)上にある。
あとは、連立すると交点は((a - b + MAX) / 2,(a + b - MAX)/2)であり、ココが答え。
No.515 典型LCP
http://yukicoder.me/submissions/171584
メモ化でギリギリ通ってしまった嘘解答。
実験すると周期性が見えた(気がして)LCP部分をメモ化してみたら通った。
http://yukicoder.me/submissions/171784
文字列Sを昇順ソートしておく。
この時対応するインデックスがソート後にどこに行くかを上手く控えておく。
すると、対応する2文字列のLCPが区間minで求められるようになる
1 aaaa 2 aabb 3 abab 4 abbb この状態で隣接するLCPを取る 1 aaaa 2 aabb 2 3 abab 1 4 abbb 2 こうすると… 1と3のLCPは[1+1,3]のLCPの最小値である1 2と4のLCPは[2+1,4]のLCPの最小値である1 1と2のLCPは[1+1,2]のLCPの最小値である2 のように区間minで高速に処理できる
区間minはセグメント木でも使えば間に合う。
