はまやんはまやんはまやん

hamayanhamayan's blog

yukicoder contest 第163回 解説

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 宝探し2

No.514 宝探し3

http://yukicoder.me/submissions/171456
宝探し2の方はやってないけれど、二分探索とかで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はセグメント木でも使えば間に合う。