原案:阿部 担当:福澤, 笠原 英訳:寺島 解説:福澤

Slides:



Advertisements
Similar presentations
有限幾何学 第 2 回. 有限幾何学 第 2 回 1. 様々なグラフの例 2. 道と最短経路問題 1. 用語の説明 2. 最短経路問題 3. ダイキストラのアルゴリズム.
Advertisements

Problem A : Everlasting...? 原案 : 泉 模範解答 : 黄・野田 解説 : 野田.
G 問題 コードアート オンライン 原案:西出 ライタ:伊藤 テスタ:西出. 問題概要 0 大きさのさまざまな n 個の円に多角形 m 個を入れら れるか判定する問題 0 ただし、同じ円に複数の多角形を入れることはでき ない 0 もし、入れられる場合は、辞書順最小の入れ方を出 力 ① ② ③ ① ②.
原案 : 野田 解答 : 野田・山 口 問題文 : 野田 PROBLEM E: PSYCHIC ACCELERATOR ~ とある超能力の物体加速器~
模擬国内予選2013 Problem F テトラ姫のパズル 原案:須藤 解答:大友、須藤 解説:須藤.
2E37. ・分岐路別に動作を指 定 ( T 字路で右折するルート を通る) ⇒ 誤作動の リスク軽減 ⇒ プログラムの 簡略化.
J: Magical Switches JAG 模擬地区予選 2013 原案:保坂 解答:保坂・楠本 解説:保坂.
ハノイグラフの生成と最短経路の導出 東京電機大学 理工学部 村田和也 松浦昭洋
ICPC夏合宿09 Day3 Problem D : Luigi‘s Tavern -ルイージの酒場-
Day2 Problem I: Memory Match ~神経衰弱~
Problem H: Queen’s case
2009/12/4 グラフ (2) 第10講: 平成21年12月4日 (金) 4限 E252教室 コンピュータアルゴリズム.
データ構造と アルゴリズム 第十二回 知能情報学部 知能情報学科 新田直也.
原案:西出 テスト 伊藤.
Ex7. Search for Vacuum Problem
ICPC夏合宿09 Day2 Problem F Voronoi Island ~ボロノイ島戦記~
A: Attack the Moles 原案:高橋 / 解説:保坂.
Ex8. Search for Vacuum Problem(2)
    有限幾何学        第8回.
Problem D: Double Sorting 原案: oxy, 解答作成: oxy, nya.
Intelligent Circular Perfect Cleaner(ICPC)
Princess, a Strategiest
問題作成・解説: 北村 解答作成協力: 小西・松本
Problem G : Entangled Tree
一次関数のグラフ(式を求めること) 本時の流れ ねらい「グラフや座標など与えられた条件をもとに一次 関数の式を求める。」 ↓
一次関数のグラフ(式を求めること) 本時の流れ ねらい「グラフや座標など与えられた条件をもとに一次 関数の式を求める。」 ↓
2章 データ構造.
3 一次関数 1章 一次関数とグラフ §3 一次関数の式を求めること          (3時間).
Problem H ねこ鍋改造計画(仮) 秋葉 拓哉.
JAG Regional Practice Contest 2012 問題C: Median Tree
新春 (         ) Game Alphabet card.
15パズルの解法について 北海道情報大学 情報メディア学部 情報メディア学科 新井山ゼミ  大石 貴弘.
2013年度模擬アジア地区予選 Problem E: Putter
Problem D: King Slime ~キングスライム~
Problem F Two-finger Programming
第11講: 平成18年12月 8日 (金) 4限 E352教室 グラフ (1).
原案・解説 : 野田 解答 : 野田・吉田 Problem D Futon ~布団~.
s a b f c e d 2016年度 有限幾何学 期末試験 問1:15点
平成29年度地域力再生プロジェクト支援事業交付金活用団体 「活動発表&交流会」 参加申込み書
早わかりアントコロニー最適化 (ACO: Ant Colony Optimization)
第25章 単一始点最短路 3節 Bellman-Fordのアルゴリズム
アルゴリズムとデータ構造 2013年7月16日
グラフアルゴリズムの可視化 数理科学コース 福永研究室 高橋 優子 2018/12/29.
Ibaraki Univ. Dept of Electrical & Electronic Eng.
プロジェクト演習III,V <インタラクティブ・ゲーム制作> プログラミングコース
問題:The hik Revolutions 解説:田村(sune2)
Curriki原典
○○ English Class 2011 February 24th Day 4.
WWW上の効率的な ハブ探索法の提案と実装
知能システム論I(13) 行列の演算と応用(Matrix) 2008.7.8.
早わかりアントコロニー最適化 (Ant Colony Optimization)
b f c a d e g h a b c d e f g 図1 図2 2012年度 有限幾何学 期末試験
各 階 平 面 図 家 屋 番 号 建 物 図 面 建物の所在 A市B町一丁目30番地
連続領域におけるファジィ制約充足問題の 反復改善アルゴリズムによる解法 Solving by heuristic repair Algorithm of the Fuzzy Constraint Satisfaction Problems with Continuous Domains 北海道大学.
Ex7. Search for Vacuum Problem
2016年度 有限幾何学 中間試験 問1 次のグラフを描け.(描けない場合は理由を述べよ) 各20点
中学数学1年 4章 比例と反比例 §2 比例 (6時間).
問題作成、解説担当:中島 副担当:坪坂、松本
D: 壊れかけのヒープ 問題案: 稲葉.
ナイキストの安定判別法(簡易版) 安定余裕
地理情報システム論 第4回 コンピュータシステムおける データ表現(2)
2009/11/27 グラフ (1) 第9講: 平成21年11月27日 (金) 4限 E252教室 コンピュータアルゴリズム.
平面走査法を使った 一般線分の 交点列挙アルゴリズム
コストのついたグラフの探索 分枝限定法 A*アルゴリズム.
4 比例と反比例 1章 比例と反比例 §2 比例のグラフ         (4時間).
問2 次の問に答えよ. (ただし,握手補題,オイラーの定理,Oreの定理 は授業で紹介したものとする) (1) 握手補題を書け.
C問題 高所恐怖症 原案・ライタ : 伊藤 テスタ : 青木・西出.
3 一次関数 1章 一次関数とグラフ §4 方程式とグラフ         (3時間).
無向グラフが与えられたとき、最大位数の完全部分グラフを求める問題
長浜タウンウォークラリー 長浜の街並みを班の友だちと協力して散 策し、長浜の歴史や文化にふれよう 歴史発見コース ルール
Presentation transcript:

原案:阿部 担当:福澤, 笠原 英訳:寺島 解説:福澤 Turn Left 原案:阿部 担当:福澤, 笠原 英訳:寺島 解説:福澤

問題1 車で移動して京都観光をすることにしたタロー君たち でも免許を持っているのはタローくんだけです! さらにタローくんは右折ができません! 直進と左折だけで目的地へ行ける最短経路を求め, 最短経路が通る最小交差点数を出力せよ

問題2 Sample Inputの3つ目 烏丸五条から川端御池への経路探索 烏丸丸太町 河原町丸太町 烏丸五条 → 四条烏丸 → 烏丸五条 → 四条烏丸 →    烏丸御池 → 堀川御池 →    堀川四条 → 四条烏丸 →    四条河原町 → 河原町御池 →    河原町丸太町 → 烏丸丸太町 →    烏丸御池 → 河原町御池 →      川端御池 通る交差点数 13 二度通る交差点   四条烏丸,烏丸御池,河原町御池) 烏丸御池 川端御池 堀川御池 河原町御池 四条烏丸 四条河原町 堀川四条 烏丸五条

問題条件 通りは南北または東西方向に延びている 全ての通りは両方向とも通れる 同一座標に複数の交差点は無い 通り同士は与えられた交差点以外で交差しない 通りの間に別の交差点は無い 通りの重複区間は無い 交差点の最大数1000 以上の条件から通り数は最大でも1935

解法 ダイクストラ法 グラフを交差点と交差点へ進入した向きの組合せに拡大して構築 拡大したグラフの上でダイクストラを行う 計算量 疎なグラフに対するダイクストラ法の計算量 (E + V) log V V = 交差点数 * 隣接する交差点数 = 4K Vの頂点の最大字数は4なので,E = 2V = 8K (E+V) log V = 140K

注意点 左折のみではありません. タロー君は直進もできます! 求めるものは,最短経路の中の最小交差点数です!

結果 Submit数 : 19 Accepted数 : 5 First Submit : 77分 First Accepted : 157分 ( Makegumi )