Problem L: シャノワール 問題作成: 高橋 解法作成: 安達・高橋・前原 解説: 安達.

Slides:



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

問題案 : 稲葉 解答:秋葉、稲葉.  「 + 」の辺を通ると所持金が 1 円増える  「 - 」の辺を通ると 1 円減る (文無しは通れ ない)  始点を0円で出て終点に0円で着く最短路 は?  |V| ≦ 250 =
原案 : 野田 解答 : 野田・山 口 問題文 : 野田 PROBLEM E: PSYCHIC ACCELERATOR ~ とある超能力の物体加速器~
模擬国内予選2013 Problem F テトラ姫のパズル 原案:須藤 解答:大友、須藤 解説:須藤.
< 3 日目内容> 出席点呼 班分けとテーマの確認 HP 更新内容の確認 課題 3 ~ 5 の説明 ( i-sys ) 今後のスケジュール プレゼンテーション方法論の講義 ネタ探し,班討論.
J: Magical Switches JAG 模擬地区予選 2013 原案:保坂 解答:保坂・楠本 解説:保坂.
Problem J: いにしえの数式 問題作成・解説: 北村 解答作成協力: 八森.
2行+αチョンプに関する考察 京都大学 ○後藤順一 伊藤大雄.
3次元nクイーン問題の 解に関する研究 論理工学研究室 伊藤精一
人工知能概論 第4回 探索(3) ゲームの理論.
Day2 Problem I: Memory Match ~神経衰弱~
Problem H: Queen’s case
パネル型クエリ生成インタフェース画像検索システムの改良
Problem A: ねこかわいがり♪ 問題作成: 山本 解法作成: 山本・高橋 解説: 山本.
11.1 表の作成 表の各部名称 列 行 セル 罫線.
懐かしき日の思ひで Aチーム リーダー 福島則行 吉武優一郎 水谷聡 石松孝之 近藤悠介
ブロック運びゲーム.
A: Attack the Moles 原案:高橋 / 解説:保坂.
スライドの説明: このスライドは,教科書「啓林館」での数図ブロックの並べ方のよさを子どもに気づかせ,定着を図るものである。
I: Tokyo Olympics Center
問題作成・解説: 北村 解答作成協力: 小西・松本
<4日目内容> 今後のスケジュール HP更新内容の確認 課題の確認 (i-sys) 発表準備・予行演習の進め方について
出題: 大橋 テスト: 大橋・平原・秋葉 解説: 大橋(スライド)・平原(登壇)
2004年度JAVAゼミコンテスト作品 「Othello」
原案:阿部 担当:福澤, 笠原 英訳:寺島 解説:福澤
モンテカルロ法によるミニ囲碁 増井拓視 情報理論工学研究所.
バスケ講座.
数独パズルの難易度判定 ~解法ロジックを用いた数値化の提案~
Problem C: Princess' Japanese
2013年度模擬アジア地区予選 Problem E: Putter
Problem D: King Slime ~キングスライム~
単位 おねだり ☆オセロ おねだり隊☆D班.
<4日目内容> 今後のスケジュール HP更新内容の確認 課題の確認 (i-sys) 高原のプレゼン 2回目
アルゴリズムとデータ構造 補足資料10-2 「nクイーン」
<4日目内容> 今後のスケジュール HP更新内容の確認 課題の確認 (i-sys) 発表準備・予行演習の進め方について
家畜ふん堆肥中の窒素の効き方を考慮した化学肥料との協調利用 普及への取り組み
JAVAでつくるオセロ 伊東飛鳥、宮島雄一 長畑弘樹、ソギ原直人.
早わかりアントコロニー最適化 (ACO: Ant Colony Optimization)
研究集会「組合せゲーム・パズル」,豊橋技術科学大学
シャノンのスイッチングゲームにおけるペアリング戦略について
シャノンのスイッチングゲームにおけるペアリング戦略の複雑さについて
Bridge It と Connections の 必勝法について
アルゴリズムとデータ構造 補足資料10-1 「騎士巡回」
リーダー 亀山奈央 プレゼンター 橘貴志 アルゴリズム 古森愛美 プログラマー 中島宏基 パワーポイント 公文ゆい
4人版リバーシYoninの解析 情報論理研究室 藤本 侑花
Problem I: Aaron と Bruce
G班メンバー リーダー 橋本望 SE 北本理紗と服部友哉 PPT作成 橋本望と山田侑加
デジタル画像とC言語.
京都大学大学院情報学研究科 宮川博光 伊藤大雄
Bridge It と Connections の 必勝法について
第4章 社会構造概念はどのように豊穣化されるか
モンテカルロ法を用いた 立体四目並べの対戦プログラム
3次元Nクイーン問題の 解の存在の検証 07-1-037-0106 前波 大貴 情報論理工学研究室 宜しくお願いします。
12 Microsoft Word(3) 12.1 表の作成 表の各部名称 列 行 セル 罫線.
問題作成、解説担当:中島 副担当:坪坂、松本
宿題を提出し,宿題用解答用紙を 1人2枚まで必要に応じてとってください 配布物:ノート 2枚 (p.85~89), 小テスト用解答用紙 1枚
本当は消去できていない!? ~データを完全消去する方法~
本当は消去できていない!? ~データを完全消去する方法~
情報処理Ⅱ 2005年1月25日(火) レポート課題2の解説.
F班 メンバー 班長 雨堤 智宏 アルゴリズム解析 角田 泰彬 竹林 秀高 ppt作成 清水 貴史
アルゴリズムとデータ構造 --- 理論編 --- 山本 真基
数値解析Ⅱ ~五目並べのプログラミング~ C班.
アルゴリズム演習2 Cody Coursework Tutorial
Othello G班         山崎 木下 山本 上手      .
原口和也 高橋隆一 丸岡章 石巻専修大学 理工学部 情報電子工学科
割り当て問題(assignment problem)
C問題 高所恐怖症 原案・ライタ : 伊藤 テスタ : 青木・西出.
人工知能概論 第4回 探索(3) ゲームの理論.
5年生 板書 問題にみんなでじっくり 取り組めるようになろう! 第1セッション 1年生の子をおいて、だれかを呼びに行く。 ピア・サポート
ペンシルパズルの大道芸ステージショーへの応用
Presentation transcript:

Problem L: シャノワール 問題作成: 高橋 解法作成: 安達・高橋・前原 解説: 安達

元ネタ http://www.gamedesign.jp/flash/chatnoir/chatn oir_jp.html

問題概要 m x nの盤面の上にねこさんがいる ねこさんは盤面の外に逃げたい ひとはねこさんが逃げないように障害物を置 く 障害物も置いてある ねこさんは盤面の外に逃げたい ねこさんは障害物のあるマス目は通れない ひとはねこさんが逃げないように障害物を置 く お互いが最適な戦略をとったとき、ねこさん は逃げられるか否か? mとnは100以下

準備 用語 リーチ リーチ連結成分 ねこさんが端から二番目のマスにいて、あと一手で端 のマスに行ける状態 その端のマスにブロックはない ねこさんのターンなら、ねこさんの勝ち ひとのターンなら、ひとは端のマスに置かないとだめ リーチ連結成分 ねこさんがリーチをかけ続けて移動できる連結なマス

枝刈り探索 行かないと決めた方向は障害物を置いたこと にしてしまってよい 行かないと決めたリーチ連結成分は全部障害 物で埋めてしまってよい 一度通ったリーチ連結成分から出たら、全部障害 物で埋めてしまってよい 一度リーチ連結成分に入ったら端のマスまで 行くと思ってよい

枝刈り探索 盤面が6x9以上のとき、ねこさんが(2,4)にいる とねこさんは逃げられない これらを利用して盤面をあらかじめ埋めてし まう

縮約 大きい盤面だと盤面の真ん中らへんは埋まっ ている 6x100以上のサイズの盤面に有効 100x100の盤面でも11x11の問題に落ちる 何列あっても変わらないので、縮約してよい 6x100以上のサイズの盤面に有効 100x100の盤面でも11x11の問題に落ちる →5xNの盤面が一番難しい 三手ぐらい先読みすると終わる (5xN)^3ぐらいの探索 もうちょっと考えると(3xN)^3ぐらいになる

結果 総提出数: 1 提出者数: 1 正解者数: 0 Judge solution 642行 18KB