cafelier@SRM

SRM492

SRM | 21:22 |

SRM492 の成績・ソース (要ログイン) : WA/WA/- : 過去最悪

• 燃え尽きたので簡単に…

250開く

• 『x軸上の整数座標のところにN本、整数の高さの木が生えています。木の高さを適当に低くできるので、木のてっぺんが一直線上に並ぶようにしてください。高さを変える木の数を最小に。』
  • N≦50
  • 座標値の範囲は≦1000
  • 高さは整数以外に変えてもいいので注意

• DPで左から順に高さを変えていって…
  • この木をこの高さにする場合の最小コスト、みたいなの
• ああだめだ。高さ整数じゃなくてもいいのか。任意の高さまで考えると表が作れない
• でも無限の可能性は考える必要ないよな。
• x軸の間隔分の1くらいの有理数まで考えれば
• いやーでもそれは最低でも1000×1000の表が必要そうだし計算量間に合わない

• もっと巧い考え方があるんだよな…
• …
• あ
• 二本の高さを決めれば
• 一直線上に乗せるので、残りの高さは決まる。

• これだ。
• 二本選んで
• 高さを決めて
• 線を引いて他の木が全部それより上ならOK。

• パターンの数は
• 二本選ぶのが 50x50 で
• 高さを決めるのが1000x1000で…って無理だし、違う、整数とは限らないんだった。

• うーむ
• 高さ変わらない二本が必ずあるのでは
• ありそうな気がする。
• まず、全部の木の高さを減らすくらいなら平行移動して１本変えなくできる
• １本だけ残す場合も、できる直線を回したらもう一本別のに引っかかるまで回せて…
• そうでもないか地面にひっかかる。
• まあだいたい高さ変わらない１本か２本があるので、それだ。

• ※この辺りで木の高さではなく数の最大値を1000と勘違いし始める。
• これは二本固定して他の木全部の高さをチェックするので…
• 1000³？無理だー

• いやでも、１本固定して、可能な傾きの範囲を１パスで求めて
• その範囲にある傾きをmap<傾き,int>などに入れて重複が一番多いところを選ぶとかすれば
• 1000²に
• これだー

• 傾きの区間とかを有理数で管理するのめんどいなあ…
• もう30分以上時間使ってるしこのまま他の問題解けないと順位ヤバいし…
• ええい手抜き
• mapのキーだけ分子分母ペアにして比較はdoubleにしてしまえ
• 通分した整数割り算しかやらないので誤差は生じないはず…

• 書いた。submit

550開く

• 『無向グラフの頂点を、指定された順番に訪れる。（途中で他の頂点を通ってもいい）。過去に向かってタイムトラベルできるので、過去に訪れた町には時間を戻してゼロコストで行ける。コスト最小化せよ』
  • 50頂点。頂点リストの長さも50くらい

• 面白い問題設定だな。
• タイムトラベルじゃなくてルーラが使えるなら最小全域木…ではないか、シュタイナー木か
• だけど、過去に戻ってしまうと未来に行った頂点には飛べなくなる。ふむむ。

• 考え方としてはツリーだよね。
• スタートの0番頂点をルートにする。
• 普通に道を辿って歩くときは子ノードにする。
• タイムトラベルは、祖先にジャンプ、という操作

• こう考えると
  • (木の)各ノードにグラフの頂点番号が乗っていて
  • (木の)辺の重みはグラフでの対応する距離で
  • 根は0番で
• あるようなツリーで、DFSでたどったら指定の頂点訪問リストをsubsequenceとして含んでるような物
• のうち辺の重み和が最小のもの

• を求めればいい
• これ、前回のtrieを最小化する問題に似てる気がするな。
• 子ノードの個数が任意だからやっかいっぽく見えるけど、
• 単に担当を二分割する再帰でいける

• rec(cur, s, e)
• で、頂点curをルートとする、さっきの条件を満たしていて、
• 頂点リストsからeまでを訪れられる最小コスト

• を求めるようにする。よしこれだ
• うわーしかし時間が間に合わない
• あ、これサイクルで無限ループする可能性が
• 何回も回ったらいいことないからループはすぐに∞返せばいいか。
• うひー残り１分
• サンプルが…１個通らない！？あれー
• いいや思い出submit…
• (めでたくchallengeされました)