Problem J:
ねこ泥棒と金曜日のお屋敷
問題作成： 高橋
解法作成： 高橋・安達
解説： 前原
結果




総提出数: 30
提出者数: 20
正解者数: 1
最初の正解者: Yoichi Iwata (279分)
問題概要
1.
2.
3.
ねこはキャンパス内を等速度で移動する
1. 移動経路は多角形
なつめさんもキャンパス内を等速度で移動する
1. キャンパス内に障害物は無し
2. ある時間までに正門に行かないといけない
時間内に会える最大のねこ数を求めよ
1. 同数の場合は最速で正門につくもの
最重要な性質
命題
ねこに会う順番を固定したとき，
各ねこに最速で会っていくのが全体で最速
証明
「ねこよりはやーい」
全ての訪問順の中で最速のものを求める
巡回セールスマン問題！
アルゴリズム(TSP-DP)
1.
2.
OPT[S,i]:= 最後に i と会うような S 全部と会う方
法のうち，最速のものの時刻
For 全てのねこの集合 S:
For 最後に会ったねこ i ∈ S:
For 次に会うねこ j ∈ S:
OPT[S+j,j]
= OPT[S,i] + f(i,j,OPT[S,i])
O(n2 2S F)
OPT[S,i]にiと会っているとき
jと会える最速時刻
f(i,j,t)の計算
1.
時刻 s で会えるなら時刻 s’> s でも会える
∴ 時刻に関する二分探索
O(log T/ε log S)
≦s
≦s’
f(i,j,t)の計算
1.
時刻 s で会えるなら時刻 s’> s でも会える
∴ 時刻に関する二分探索
O(log T/ε log S)
≦s
≦s’
Time Limit Exceeded
f(i,j,t)の計算（想定解）
1.
2.
あるセグメントで会えれば次のセグメント
でも会える（周が違えば別のセグメント）
セグメントを固定すると最速到達時間が
解析的にわかる：
1. ねこがセグメントの始点を t0 に出発するとして
どうたらこうたら→二次方程式
∴セグメントに関する二分探索＋解析計算
O(log S)

2016/05/16

腰部疾患講習会 - 理学療法科学学会

ノーリスク脱サラ転売 セミナー アフィリオファー

アナログ信号発生器 一式 仕様書

世界遺産「官営八幡製鐵所」関連施設 製鐵所構内見学バスツアーの開始

回転テーブルの使用で、誰でも簡単に対象物 をスキャン・生成できます 。。

Charge characteristics of forest soils derived from sedimentary rocks

製品評価業務のご案内 - 長野県諏訪市 開発設計・請負の株式会社

Title bin-packingの亜種ふたつにかんする備忘録 Author(s

www.utpc.jp

リーフレット: 10G帯光モジュールのアイマスク試験に

feature ウィスパリングギャラリーモード共振器 による超狭線幅半導体レーザ

ABC 052 / ARC 067 解説

米国コンプライアンス、個人信用情報最新事情

ユーザインタフェース 第2回 - Data Engineering Lab

緩衝溶液 緩衝溶液の効果を式のうえで見ていくことにしよう。 HA H+ + A

最急降下法による情報量規準WBICの安定的計算法 渡辺

コレステリック液晶による構造色レーザ発振

ICTの活用について

スライド 1

NEWパーツ

回帰分析 - 東洋大学 トップページ