cafelier@SRM

SRM426 Div1

SRM | 22:29 |

SRM426 の成績・ソース (要ログイン) : AC/AC/WA : 問題文の意味がわからない

250 開く

• 問題文の意味がわからない
• 問題文の意味がわからない
• とりあえずカードのshuffleの仕方の定義はわかる。shuffleしまくるループだけ書いておこう。
• 問題文の意味がわからない
• 問題文の意味がわからない
• わからないけど1通りくらいしか解釈のしようがないだろうと思って、適当に実装
• サンプル通っちゃた
• わからないけどまあいいやsubmit

500 開く

• 『二次元平面上をネズミ達がばらばらに等速直線運動する。うまくタイミング狙うと軸に平行な L*L の正方形で全部のネズミを囲えるような最小の L を求めよう』という問題（と解釈しなおして理解）

• 全ての時刻 t で max( max_x - min_x, max_y - min_y ) を計算して、その最小値が求める答え

• 三分探索できるかなーと考えたけど凸かどうかまったくわからなかったので安全に行くことにする
• max_x - min_x という関数は、どれか二匹のネズミの x 座標が一致するところで曲がる折れ線になってる。y も
• てことは全ネズミ対の座標が一致するポイントを列挙してその区間毎に区切って考えれば、max_x - min_x とかは一次関数
• それなら max( max_x - min_x, max_y - min_y ) は式で計算できる。区間の数は高々2500なので十分間に合う。

• 実装あるのみ
  • それぞれの区間のなかでどのネズミが一番x座標大きいかとかは、区間の中間の時刻での座標で並べれば絶対座標が一致したりしないので安全にsortで行ける
  • さっき区切った区間内でも max_x - min_x と max_y - min_y の大小は入れ替わることがあるのでそれだけ注意
• サンプル通ったので submit

1000 開く

• 『"ここから○○Kmでどこどこ"という標識に書かれた情報が標識の並んでる順に与えられる。最後の標識から目的地どこどこまでの距離がわかるならその距離を求めてね』という問題。わからない場合や情報に矛盾がある場合、すでに目的地を通り過ぎてる場合は -1。

• 全部等式と不等式制約だから線形計画法のライブラリあれば解けそうだなー
• でもそんなもの用意してないなー

• ここはダメ元で、System Test や Challenge で「距離がわかるケースは全部の標識の座標が確定するケースだけ」なデータしか来ないことを祈って、連立一次方程式で解く！
• 掃き出し法。実装あるのみ
• サンプル通っちゃった。submit！

• (※ 案の定 System Test で落ちました)

撃墜タイム

• 三分探索何人かいたので、ほーこれでいいのかーと改めて検討してたら終わった

感想

• もう少し凸性をマジメに考察するべきだったと思う。三分探索で行けるならコード量の差が圧倒的すぎる。

• 1000点はまだ解法思いついてないです。単純に同じ目的地を指している標識間に矛盾がないように情報を確定させていく方法だと、サンプルにもあるような、標識の位置を S0, S1, S2, S3 として S0 + 4 == S3 と S1 + 5 == S2 というだけの情報が得られる的な場合が難しい。S0＜S1＜S2＜S3 になり得ないのでこれは矛盾と判断しなければいけないのだけれど…