ICPC夏合宿09 Day3 Problem D : Luigi‘s Tavern -ルイージの酒場-

Slides:



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

G 問題 コードアート オンライン 原案:西出 ライタ:伊藤 テスタ:西出. 問題概要 0 大きさのさまざまな n 個の円に多角形 m 個を入れら れるか判定する問題 0 ただし、同じ円に複数の多角形を入れることはでき ない 0 もし、入れられる場合は、辞書順最小の入れ方を出 力 ① ② ③ ① ②.
統計学 西山. 平均と分散の標本分布 指定した値は μ = 170 、 σ 2 = 10 2 、データ数は 5 個で反復 不偏性 母分散に対して バイアスを含む 正規分布カイ二乗分布.
ACM/ICPC と アルゴリズム 「実践的プログラミング」 稲葉 一浩. 自己紹介 ﻪ 理Ⅰ → 理学部情報科学科 → 情報理工学系研究科コンピュータ科学専攻 ﻩ 博士課程1年 ﻩXML を扱う専用言語の研究など ﻪ 個人的には ﻩ ﻯD.
原案 : 野田 解答 : 野田・山 口 問題文 : 野田 PROBLEM E: PSYCHIC ACCELERATOR ~ とある超能力の物体加速器~
模擬国内予選2013 Problem F テトラ姫のパズル 原案:須藤 解答:大友、須藤 解説:須藤.
シミュレーション論Ⅰ 第 7 回 待ち行列のシミュレーション(2). 第 6 回のレポート(解答例) 乱数表より乱数を記入し、到着間隔・サービス時間にした がってグラフを作成する 例) 最大待ち人数:2人 最大待ち時間:5分 平均待ち時間:3分.
J: Magical Switches JAG 模擬地区予選 2013 原案:保坂 解答:保坂・楠本 解説:保坂.
到着時刻と燃料消費量を同時に最適化する船速・航路計画
SPSS操作入門 よい卒業研究をめざして 橋本明浩.
Day2 Problem I: Memory Match ~神経衰弱~
Problem H: Queen’s case
ネットワーク理論講義補助資料 Text. 組合せ最適化とアルゴリズム 4.5 節 主・双対法 pp
数理統計学 西 山.
原案:西出 テスト 伊藤.
電子情報工学科5年(前期) 7回目(21/5/2015) 担当:古山彰一
プログラミング基礎I(再) 山元進.
Problem J Tile Puzzle 原案:野田 担当:平野,吉田,泉,松本.
計算機リテラシーM 第2回 メール 伊藤 高廣.
総評 野田久順.
ICPC夏合宿09 Day2 Problem F Voronoi Island ~ボロノイ島戦記~
統計学  第7回 西 山.
第1回 担当: 西山 統計学.
I: Tokyo Olympics Center
Intelligent Circular Perfect Cleaner(ICPC)
Accessによる SQLの操作 ~実際にテーブルを操作してみよう!~.
Problem G : Entangled Tree
プログラミング基礎I(再) 山元進.
Problem H ねこ鍋改造計画(仮) 秋葉 拓哉.
原案:阿部 担当:福澤, 笠原 英訳:寺島 解説:福澤
JAG Regional Practice Contest 2012 問題C: Median Tree
原案: 矢藤(kohyatoh) 解答: 高原(rankalee, shimejitan), 矢藤 解説: 矢藤
統計学 オリエンテーション   担当: 西山.
Problem C: Princess' Japanese
模擬国内予選2014 Problem C 壊れた暗号生成器
2013年度模擬アジア地区予選 Problem E: Putter
Problem D: King Slime ~キングスライム~
4章 平行と合同 2 多角形の外角の和.
Problem F Two-finger Programming
プログラミング入門第4回 ~レゴロボットのプログラミング3~
統計学  第6回 西山.
クラシック音楽普及プロジェクト KG:mao B3 wakutin.
情報処理 第13回.
情報検索演習 第8回 パソコンを起動しておくこと 前から4列目までに着席すること 2005年11月30日 後期 水曜5限
プロセッシング入門1 初歩のプログラミング.
オンライン説明会に関する調査 上杉裕也.
プログラミング 平成25年12月10日 森田 彦.
原案・解説 : 野田 解答 : 野田・吉田 Problem D Futon ~布団~.
文字化けの背景を知る.
経営工学基礎演習a PowerPointの利用.
練習問題アイテムバンクの開発研究 ~再生形式~
携帯ゲーム機の進化 情報モラル研修 ~Nintendo3DSを例に~
問題:The hik Revolutions 解説:田村(sune2)
統計学 西 山.
携帯ゲーム機の進化 情報モラル研修 ~Nintendo3DSを例に~
数理統計学 西 山.
First Course in Combinatorial Optimization
プログラミング 平成22年12月15日 森田 彦.
アルゴリズムとデータ構造 第3章 ヒープ 5月31日分
アルゴリズムとデータ構造 第3章 ヒープ 5月31日分の復習
問題作成、解説担当:中島 副担当:坪坂、松本
シミュレーション論Ⅰ 第7回 シミュレーションの構築と実施.
D: 壊れかけのヒープ 問題案: 稲葉.
Problem L: シャノワール 問題作成: 高橋 解法作成: 安達・高橋・前原 解説: 安達.
統計学  第9回 西 山.
プログラミング入門 電卓を作ろう・パートI!!.
ソフトウェア制作論 平成30年11月28日.
情報処理 第13回.
割り当て問題(assignment problem)
C問題 高所恐怖症 原案・ライタ : 伊藤 テスタ : 青木・西出.
Presentation transcript:

ICPC夏合宿09 Day3 Problem D : Luigi‘s Tavern -ルイージの酒場- 原案・解説 : 野田 解答 : 野田・田村

問題 Nahailaという国のルイージの酒場に集まった冒険者のパーティ編成を行う。 冒険者は勇者、戦士、僧侶、魔法使いの4種類の職業に分かれている 各パーティには各職業につき高々1名のメンバーを加えることが出来る。

問題 勇者は各パーティに必ず一人いなければならない 勇者と戦士が同じパーティにいる場合は相性が良くなければならない 戦士と僧侶が同じパーティにいる場合は相性が良くなければならない 僧侶と魔法使いが同じパーティにいる場合は相性が良くなければならない 戦士・僧侶・魔法使いについて、それぞれNW、NC、NM個のパーティは、それぞれの職業の冒険者なしでパーティを編成しても良い 僧侶を外した場合はそれ以外の職業の冒険者を外してはならない

解法 最大流 勇 戦 僧 魔 NW NC NM 枝の容量は断りが無い限りは1

簡単な例から考える もし勇者と戦士しかいない設定だったら? 二部マッチング 勇 戦 勇 戦 勇 戦

拡張してみる 僧侶を追加してみる 真ん中の枝は戦士の人数を制限するためのガード エッジ(?) 勇 戦 戦 僧 勇 戦 戦 僧 勇 戦 戦 僧

さらに拡張してみる 魔法使いを追加してみる 僧侶と同様にガードエッジをつける 勇 戦 戦 僧 僧 魔 勇 戦 戦 僧 僧 魔 勇 戦 戦 僧

もっと拡張してみる NWパーティは戦士がいなくても良い 戦士のマッチング部分を最大でNWパーティだけス キップするような枝を作る NW 戦 勇 戦 戦 僧 僧 魔 勇 戦 戦 僧 僧 魔 勇 戦 戦 僧 僧 魔

めっちゃ拡張してみる NCとNMも同様に扱う 僧侶と魔法使いについても同様に迂回ルートを作ってみる NW NC 戦 戦 僧 僧 魔 NM 勇

確かめてみる 僧侶を外した場合はそれ以外の職業の冒険者を外してはならない 僧侶をはずす → NCのルートを通る→戦士と魔法 使いは必ず入る NW NC 戦 戦 僧 僧 魔 NM 勇 戦 戦 僧 僧 魔 勇 戦 戦 僧 僧 魔 勇 戦 戦 僧 僧 魔

さらに確かめてみる 僧侶を外した場合はそれ以外の職業の冒険者を外してはならない 戦士・魔法使いをはずす→僧侶は必ず入れる NW NC 戦 戦 NM 勇 戦 戦 僧 僧 魔 勇 戦 戦 僧 僧 魔 勇 戦 戦 僧 僧 魔

サンプル入力 Input #1 戦 戦 僧 僧 魔 勇 戦 戦 僧 僧 魔 勇 答え : 2

ソースコード 野田 C++ 221行 田村 186行

結果 First submit : HITORI# (59) First accepted : HITORI# (68) Total submit : 16 Total accepted : 3

元ネタ 勇者の代わりにバラモス倒しに行くことになった 第1章その1‐ニコニコ動画(ββ) sm325909 ドラゴンクエストⅢ他 Nahaila→Aliahan→ドラゴンクエストⅢ