A: Attack the Moles 原案:高橋 / 解説:保坂.

Slides:



Advertisements
Similar presentations
組合せ最適化輪講 2.3 連結性 川原 純. 2.3 連結性 内容 – グラフ上の節点をすべてたどるアルゴリズム 計算機上でのグラフの表現 – 強連結成分を求めるアルゴリズム トポロジカル順序を求める方法も – k- 連結、 k- 辺連結について – 2- 連結グラフの耳分解について.
Advertisements

I : 首都 原案 : 岸本 解法の提示 : 森田 正当性の証明 : 岸本 テスター : 岸本, 森田 解説 : 岸本.
有限幾何学 第 2 回. 有限幾何学 第 2 回 1. 様々なグラフの例 2. 道と最短経路問題 1. 用語の説明 2. 最短経路問題 3. ダイキストラのアルゴリズム.
1 高速フーリエ変換 (fast Fourier transform). 2 高速フーリエ変換とは? – 簡単に言うとフーリエ変換を効率よく計算 する方法 – アルゴリズムの設計技法は分割統治法に基 づいている 今回の目的は? – 多項式の積を求める問題を取り上げ、高速 フーリエ変換のアルゴリズムを用いた解法.
問題案 : 稲葉 解答:秋葉、稲葉.  「 + 」の辺を通ると所持金が 1 円増える  「 - 」の辺を通ると 1 円減る (文無しは通れ ない)  始点を0円で出て終点に0円で着く最短路 は?  |V| ≦ 250 =
模擬国内予選2013 Problem F テトラ姫のパズル 原案:須藤 解答:大友、須藤 解説:須藤.
Lecture02-Binary Search Trees 通信情報システム専攻 岩間伊藤研究室 M1 前田圭介.
J: Magical Switches JAG 模擬地区予選 2013 原案:保坂 解答:保坂・楠本 解説:保坂.
初年次セミナー 第13回 2次元グラフィックス(1).
到着時刻と燃料消費量を同時に最適化する船速・航路計画
制約付き最短路問題に対する実験的解析 上智大学 宮本裕一郎 o 1 d (7, 15) (9,4) (12,4)
区間グラフにおける区間表現からMPQ-treeを効率よく構成するアルゴリズム
4.3 マージソート.
Fortran と有限差分法の 入門の入門の…
データ構造と アルゴリズム 第十二回 知能情報学部 知能情報学科 新田直也.
動的計画法 表の作成 制約の追加 練習問題.
動的計画法 表の作成 制約の追加 練習問題.
2 分探索木 Binary Search Tree 実行可能な操作 計算量 木の高さは,最悪 O(n) n = |A| : 要素の個数
アルゴリズムとデータ構造 第8回 ソート(3).
近似アルゴリズム 第10章 終了時刻最小化スケジューリング
On the Enumeration of Colored Trees
Problem D: Double Sorting 原案: oxy, 解答作成: oxy, nya.
I: Tokyo Olympics Center
第四回 線形計画法(2) 混合最大値問題 山梨大学.
Problem G : Entangled Tree
数学の予備知識 ネットワークシステムⅠ 第2回.
出題: 大橋 テスト: 大橋・平原・秋葉 解説: 大橋(スライド)・平原(登壇)
原案:阿部 担当:福澤, 笠原 英訳:寺島 解説:福澤
JAG Regional Practice Contest 2012 問題C: Median Tree
データ構造と アルゴリズム 第二回 知能情報学部 新田直也.
配送計画最適化システム WebMETROご紹介
アルゴリズムとデータ構造 補足資料7-3 「単純選択ソートselsort.c」
Problem C: Princess' Japanese
2013年度模擬アジア地区予選 Problem E: Putter
Problem D: King Slime ~キングスライム~
データ構造と アルゴリズム 第八回 知能情報学部 新田直也.
最短路問題のための LMS(Levelwise Mesh Sparsification)
階層的境界ボリュームを用いた 陰関数曲面の高速なレイトレーシング法
計算量理論輪講 岩間研究室 照山順一.
ネットワーク理論講義補助資料 Text. 組合せ最適化とアルゴリズム 4.3 節 Lagrange緩和 pp
情報学研究科 通信情報システム専攻 小野寺研究室 M1 奥村 佳弘
第25章 単一始点最短路 3節 Bellman-Fordのアルゴリズム
ネットワーク理論 Text. Part 3 pp 最短路問題 pp 最大流問題 pp.85-94
グラフアルゴリズムの可視化 数理科学コース 福永研究室 高橋 優子 2018/12/29.
アルゴリズムとデータ構造1 2006年6月16日
問題:The hik Revolutions 解説:田村(sune2)
アルゴリズムとデータ構造 第3章 ヒープ 6月10日分
First Course in Combinatorial Optimization
連続領域におけるファジィ制約充足問題の 反復改善アルゴリズムによる解法 Solving by heuristic repair Algorithm of the Fuzzy Constraint Satisfaction Problems with Continuous Domains 北海道大学.
計算の理論 II 計算量 月曜5校時 大月美佳 2019/4/10 佐賀大学理工学部知能情報システム学科.
プログラミング 4 整列アルゴリズム.
プログラミング 4 探索と計算量.
第2回課題 配布した通り.氏名・学生番号を忘れないこと.
プログラミング 4 木構造とヒープ.
計算機プログラミングI 第6回 2002年11月14日(木) アルゴリズムと計算量 第1回課題の説明 平方根を計算するアルゴリズム 計算量
問題作成、解説担当:中島 副担当:坪坂、松本
Problem L: シャノワール 問題作成: 高橋 解法作成: 安達・高橋・前原 解説: 安達.
重み付き投票ゲームにおける 投票力指数の計算の高速化
アルゴリズムとデータ構造 2012年7月2日
Max Cut and the Smallest Eigenvalue 論文紹介
アルゴリズムとデータ構造 2011年6月28日
情報工学概論 (アルゴリズムとデータ構造)
Advanced Data Structure 第3回
アルゴリズムとデータ構造 2013年7月2日
ヒープソート.
コストのついたグラフの探索 分枝限定法 A*アルゴリズム.
離散数学 11. その他のアルゴリズム 五島.
ヒープソート.
C問題 高所恐怖症 原案・ライタ : 伊藤 テスタ : 青木・西出.
プログラミング論 バイナリーサーチ 1.
Presentation transcript:

A: Attack the Moles 原案:高橋 / 解説:保坂

問題概要 もぐらたたきをする もぐらは N 匹いる.時刻 Ti で位置 Xi に現れ,叩ける (その時刻でその位置に手が存在する) と Pi 点獲得 手は 2 本あり,左手は右手より左になければならない 得点を最大化 N <= 3,000

注目点 左手と右手の位置関係の制約は無視して解いてもよい 交差するような移動があっても左右の手を入れ替えて考えればよい 「ちょうど同じ位置にいてはいけない」という制約は「もぐらを両手で叩いても 1 回しか得点に加算しない」という制約に置き換えられる 入力を Ti の値でソートすれば,もぐら 2 匹の組に対して「同じ手で両方叩けるならばどちらを先に叩かなければならないか」が定まる Xi でソートされているのは釣りです XLeft, XRight を時刻 0 得点 0 のもぐらと考えるのが楽

遅い解法 dp[i, j] := (片方の手がもぐら i,片方の手がもぐら j を最後に叩いた状態での,得られている得点の最大値) dp[i, k] + Pj (もぐら k を叩いてからもぐら j を叩ける) dp[k, j] + Pi (もぐら k を叩いてからもぐら i を叩ける) ただし i = j のときは Pi を加算しないことに注意 O(N3)

高速化 i > j のときは dp[i, j] = dp[j, i] として求めることにする dp[i, j] (i <= j) は以下の最大値 dp[i, k] + Pj (もぐら k を叩いてからもぐら j を叩ける) ただし i = j のときは Pi を加算しない 「もぐら k を叩いてからもぐら j を叩ける」ようなもぐら k たちの中での dp[i, k] の最大値を高速に拾いたい

高速化 もぐら k を叩いてからもぐら j を叩けるための条件 |Xj - Xk|<= V (Tj - Tk) ⇔ Xj - Xk <= V (Tj - Tk) and -(Xj - Xk) <= V (Tj - Tk) ⇔ V Tk - Xk <= V Tj - Xj and V Tk + Xk <= V Tj + Xj 各もぐらに関して,(V Ti - Xi, V Ti + Xi) という値が重要

高速化 dp[i, *] を計算する段階で, これらを扱うデータ構造があればよい dp[i, j] (i <= j) を計算するために,座標が [0, V Tj - Xj] × [0, V Tj + Xj] の範囲にある点に書いてある値のうち最大のものをとる dp[i, j] を計算したら,座標 (V Tj - Xj, V Tj + Xj) の点に dp[i, j] と書き込む これらを扱うデータ構造があればよい 2 次元 Binary Indexed Tree (Fenwick Tree) を使えば各操作 O((log N)2),定数倍も軽い 全体で O(N2 (log N)2) 上手い二分木を作れば O(N2 log N) も可能?

別解 最小費用流による方法 もぐら i に対して 2 つの頂点 INi と OUTi を作る INi から OUTi へ容量 1,コスト -Pi の辺を張る もぐら i を叩いてからもぐら j を叩くことができる場合,OUTi から INj へ容量 1,コスト 0 の辺を張る 始点と終点も自然につけ,流量 2 を流す

別解 最小費用流の計算量評価 負辺を解消するための Bellman-Ford O(N3) 最短路反復 (反復といっても 2 回) のための Dijkstra O(N2 log N) あるいは O(N2) 実は,負辺のグラフでのトポロジカル順序 (つまり,もぐらの出現が早い順) に処理すれば Bellman-Ford のループが 1 回で終わる 全体で O(N2 log N) あるいは O(N2)

結果 正解 / 提出: 2 / 57 提出チーム: 9 正解チーム: 2 最初の提出: yukim (00:13) 最初の正解: -Dint=char (03:05)