危険なスケート

(1)

危険なスケート解説

今西健介 _(@japlj)

Dangerous Skating

(2)

問題概要

(3)

問題概要

(4)

問題概要

(5)

問題概要

グリッド上で JOI 君がスケートをする

元いた場所に氷塊が！コワイ！はよ帰ろ……

(6)

問題概要

(7)

問題概要

(8)

問題概要

グリッド上で JOI 君がスケートをする

(9)

問題概要

(10)

問題概要

グリッド上で JOI 君がスケートをする 縦 R マス，横 C マス  最短何ステップ？制約  ・R ≦ 1,000  ・C ≦ 1,000  ・最初から氷塊のマス有

(11)

あきらかな最短路？

最短路問題に見えるが，これまでの動作によって  氷塊の配置が異なる状態になりうる  ＝位置だけで状態は確定しない直前の動き直後の動き全探索しよう！！！ O⇤(3answer)時間で小課題 ₁ が解ける _{(13 点)}

(12)

(13)

何がやばいのか

(14)

何がやばいのか

氷塊が生える

(15)

何がやばいのか

氷塊が生える

(16)

何がやばいのか

氷塊が生える

色々あって生えてきた氷を使う

(17)

何がやばいのか

氷塊が生える色々あって生えてきた氷を使うこれを覚えておく  必要がある！？

(18)

何がやばいのか

氷塊が生える色々あって生えてきた氷を使うこれを覚えておく  必要がある！？ほんとかな…

(19)

実はやばくない？

氷塊が生える

(20)

実はやばくない？

氷塊が生える

(21)

実はやばくない？

氷塊が生える

(22)

実はやばくない？

氷塊が生える

(23)

実はやばくない？

氷塊が生える色々あって生えてきた氷を使うショートカットできるし  左みたいなの考えなくて  いいんでは

(24)

実はやばくない？

氷塊が生える色々あって生えてきた氷を使うショートカットできるし  左みたいなの考えなくて  いいんではこの辺で新しく氷作って  後で使う場合  やっぱりやばくない？

(25)

実はやばくない？

氷塊が生える色々あって生えてきた氷を使うショートカットできるし  左みたいなの考えなくて  いいんではこの辺で新しく氷作って  後で使う場合  やっぱりやばくない？

実はやっぱりやばくない！！

(26)

結局どういうことか

(27)

結局どういうことか

(28)

結局どういうことか

新しく生えた氷塊は

(29)

結局どういうことか

(30)

結局どういうことか

(31)

結局どういうことか

(32)

結局どういうことか

元からある氷塊

(33)

結局どういうことか

こういう往復運動でしか使わなくてもよいのでは？

(34)

簡単な証明

氷塊が生える色々あって生えてきた氷を使うこの辺で新しく氷作って  後で使う場合  やっぱりやばくない？これが  実はやばくない  ことを示す

(35)

簡単な証明

氷塊が生える

(36)

簡単な証明

氷塊が生える

(37)

簡単な証明

氷塊が生える色々あって生えてきた氷を使うこれが最短路と仮定して新たな氷を往復以外で使う  最後の箇所をとってきた

(38)

簡単な証明

氷塊が生える色々あって生えてきた氷を使うこれが最短路と仮定して新たな氷を往復以外で使う  最後の箇所をとってきたこの辺で新しく氷作って  後で使う場合  やっぱりやばくない？

(39)

簡単な証明

後で使わない

(40)

簡単な証明

後で使わない

ショートカット可能！

(41)

つまり

元からある氷塊 1 2 3 4 5 こういう辺を張って最短路を求めれば  良いのでは？？？？？？ (Dijkstra)

(42)

つまり

元からある氷塊 1 2 3 4 5 こういう辺を張って最短路を求めれば  良いのでは？？？？？？ (Dijkstra) ほんとかな…

(43)

懸念

往復以外で新しい氷塊を使わない

⇐

往復だけ考えたらあとは氷塊は無視してよい

(44)

懸念

往復以外で新しい氷塊を使わない ⇐ 往復だけ考えたらあとは氷塊は無視してよいこれは非自明元からある氷塊

(45)

懸念

(46)

懸念

(47)

懸念

往復以外で新しい氷塊を使わない ⇐ 往復だけ考えたらあとは氷塊は無視してよいこれは非自明元からある氷塊これを忘れても  大丈夫？？

(48)

懸念

往復以外で新しい氷塊を使わない ⇐ 往復だけ考えたらあとは氷塊は無視してよいこれは非自明元からある氷塊これを忘れても  大丈夫？？色々あって

(49)

懸念

往復以外で新しい氷塊を使わない ⇐ 往復だけ考えたらあとは氷塊は無視してよいこれは非自明元からある氷塊これを忘れても  大丈夫？？色々あって ←本来無理なやつ

(50)

懸念

こういうのが最短路になると

 

やばくない？

 

(不当な解が出てしまう)

(51)

懸念

こういうのが最短路になると

 

やばくない？

 

(不当な解が出てしまう)

ならない

(52)

懸念

往復以外で新しい氷塊を使わない ⇐ 往復だけ考えたらあとは氷塊は無視してよいこれは非自明元からある氷塊色々あって ←本来無理なやつ

(53)

懸念

往復以外で新しい氷塊を使わない ⇐ 往復だけ考えたらあとは氷塊は無視してよいこれは非自明元からある氷塊色々あって ←本来無理なやつ

(54)

懸念

往復以外で新しい氷塊を使わない ⇐ 往復だけ考えたらあとは氷塊は無視してよいこれは非自明元からある氷塊色々あって ←本来無理なやつショートカット可能！

(55)

小課題

2 (65点)

元からある氷塊 1 2 3 4 5 これで Dijkstra すれば，頂点数 _O(RC) O(R + C) O(RC(R + C) log RC) 各頂点の次数がなので計算量は

(56)

辺の削減

元からある氷塊 1 2 3 4 5 実はこれは無駄が多い

(57)

辺の削減

1

2

(58)

辺の削減

よくある，こういうのを

(59)

辺の削減

よくある，こういうのをこうするやつ各頂点の次数がになって全体で  または O(1)

(60)

得点分布

0 1 2 3 4 5 6 7 8 9 10 0点 13点 78点 100点 0点 13点 78点 100点

危険なスケート