Problem D: King Slime ~キングスライム~

Slides:



Advertisements
Similar presentations
Problem A : Everlasting...? 原案 : 泉 模範解答 : 黄・野田 解説 : 野田.
Advertisements

原案 : 野田 解答 : 野田・山 口 問題文 : 野田 PROBLEM E: PSYCHIC ACCELERATOR ~ とある超能力の物体加速器~
模擬国内予選2013 Problem F テトラ姫のパズル 原案:須藤 解答:大友、須藤 解説:須藤.
表計算ソフト (教科書49ペー ジ). ◎表計算ソフトとは 表から計算によって ① 知りたいデータを見つけ出し、 ② わかりやすく、見やすく加工する ことができるソフトのこと。
シミュレーション論Ⅰ 第 7 回 待ち行列のシミュレーション(2). 第 6 回のレポート(解答例) 乱数表より乱数を記入し、到着間隔・サービス時間にした がってグラフを作成する 例) 最大待ち人数:2人 最大待ち時間:5分 平均待ち時間:3分.
0章 数学基礎.
J: Magical Switches JAG 模擬地区予選 2013 原案:保坂 解答:保坂・楠本 解説:保坂.
プラットフォーム: PC プレイ人数 : 1人 ジャンル : 横スクロールアクション
3次元nクイーン問題の 解に関する研究 論理工学研究室 伊藤精一
ICPC夏合宿09 Day3 Problem D : Luigi‘s Tavern -ルイージの酒場-
エクセル(1)の目次 起動法、ブック、シート、セル ブックの開き方 エクセル画面 マウスポインターの種類 シート数の調節 データの入力法
Revenge of the Round Table
Day2 Problem I: Memory Match ~神経衰弱~
Problem H: Queen’s case
近似アルゴリズム 第10章 終了時刻最小化スケジューリング
11.1 表の作成 表の各部名称 列 行 セル 罫線.
Ex7. Search for Vacuum Problem
ICPC夏合宿09 Day2 Problem F Voronoi Island ~ボロノイ島戦記~
A: Attack the Moles 原案:高橋 / 解説:保坂.
    有限幾何学        第8回.
形状を平行移動や回転移動させて位置を変えたり,拡大・縮小して変形させる方法を説明する.
Problem D: Double Sorting 原案: oxy, 解答作成: oxy, nya.
I: Tokyo Olympics Center
Intelligent Circular Perfect Cleaner(ICPC)
Princess, a Strategiest
問題作成・解説: 北村 解答作成協力: 小西・松本
エクセル(1)の目次 起動法、ブック、シート、セル ブックの開き方 エクセル画面 マウスポインターの種類 シート数の調節 データの入力法
Problem G : Entangled Tree
Problem H ねこ鍋改造計画(仮) 秋葉 拓哉.
VO ツール利用法 Specview 国立天文台 天文データセンター 白崎 裕治.
第4回:ボールを画面内で弾ませよう! (オブジェクトの移動、二次元)
原案:阿部 担当:福澤, 笠原 英訳:寺島 解説:福澤
JAG Regional Practice Contest 2012 問題C: Median Tree
原案: 矢藤(kohyatoh) 解答: 高原(rankalee, shimejitan), 矢藤 解説: 矢藤
第二回 連立1次方程式の解法 内容 目標 連立1次方程式の掃出し法 初期基底を求める 連立1次方程式を掃出し法を用いてExcelで解析する
Problem C: Princess' Japanese
模擬国内予選2014 Problem C 壊れた暗号生成器
2013年度模擬アジア地区予選 Problem E: Putter
INSERT(x,p,L)の例 (一部) 磯 直行 2009年5月5日
原案・解説 : 野田 解答 : 野田・吉田 Problem D Futon ~布団~.
情報処理 第7回 表がある文書の作成.
「ユーザー設定リスト」の作成と削除 ◎ 新しい「リスト」の作成法
GaAs(110)表面の形成機構と緩和過程の動的モンテカルロシミュレーション
ベイジアンネット混合モデルによる 強化学習エージェントの方策改善
新しい表現を勉強しよう! × × a dog my dog a bed dog on the bed dog ○
DirectX勉強会 第5回.
プロジェクト演習III,V <インタラクティブ・ゲーム制作> プログラミングコース
演習1 : インターフェイスを使ってみよう 「10人の客(乗用車、バイク、ストーブのいずれかランダムに決定)に1~100(L)の給油をするガソリンスタンドをシミュレートする実行クラス : RefuelSimulation」を作成する。給油の際には、どの種類の客が何リットル給油したか出力すること。 実行結果例.
創造設計演習(S&V演習) 提出課題 課題内容
知能システム論I(13) 行列の演算と応用(Matrix) 2008.7.8.
ゲームプログラミング講習  第3章 ゲーム作成 ブロック崩しを作ります ゲームプログラミング講習 第3章 ゲーム作成.
Minoのブロック配置のデータ構造 K.Yonezawa.
b f c a d e g h a b c d e f g 図1 図2 2012年度 有限幾何学 期末試験
有効座席(出席と認められる座席) 左 列 中列 右列.
変換されても変換されない頑固ベクトル どうしたら頑固になれるか 頑固なベクトルは何に使える?
Ex7. Search for Vacuum Problem
12 Microsoft Word(3) 12.1 表の作成 表の各部名称 列 行 セル 罫線.
問題作成、解説担当:中島 副担当:坪坂、松本
D: 壊れかけのヒープ 問題案: 稲葉.
Problem L: シャノワール 問題作成: 高橋 解法作成: 安達・高橋・前原 解説: 安達.
Handel-Cを用いた パックマンの設計
SKS移動関連1.
プロジェクト演習III,V <インタラクティブ・ゲーム制作> プログラミングコース
ミニテスト12解答 月曜3校時 大月 美佳.
d b c e a f 年度 有限幾何学 中間試験 問1 次の用語の定義をそれぞれ述べよ.
バネモデルの シミュレータ作成 精密工学科プログラミング基礎 資料.
平面走査法を使った 一般線分の 交点列挙アルゴリズム
Molecular Devices Japan
図2 x11 図1 x6 x10 x12 x3 x5 x7 x9 x13 x2 x4 x8 x14 (0,0) (1,0) x1 x15
C問題 高所恐怖症 原案・ライタ : 伊藤 テスタ : 青木・西出.
Presentation transcript:

Problem D: King Slime ~キングスライム~ 原案:野田 解答:野田・下田 解説:野田

問題 W×Hの格子内にN(<=40,000)匹のスライムがいる スライムは一度のmoveで上下左右の方向に、外壁の手前に来るか他のスライムのいるセルに進入するまで移動することが出来る。 2匹のスライムが同一のセルにいると、合体して新しいスライムとなる 全てのスライムが合体するまでに必要な最小のmoveの数を求めよ

解答 縦横に即座に連結できるスライムは、即連結 残りは上下左右の壁のいずれかに集めて連結

連結成分の分解 上下左右に即連結可能なスライムは、連結する x座標、y座標でバケツソート UnionFindにて連結する O(N)

連結成分同士の結合 全てのスライムが連結する場合はこれ以降の処理は行わない 上下左右のいずれかの壁に集める 1つ目の連結成分をいずれかの壁に移動させる +1回 2つ目以降の連結成分をその壁に移動させ、1つ目の連結成分に結合する +(連結成分-1)×2回 ただし、いずれかの連結成分の中に初期状態で壁際にスライムがいる場合は、その壁にスライムを集める -1回

模範解答 野田: C++ 139行 下田: 73行

結果 Total Submission: 28 Total Accepted: 9