Problem H ねこ鍋改造計画(仮) 秋葉 拓哉.

Slides:



Advertisements
Similar presentations
授業展開#12 コンピュータの扱いにくい問 題. 扱いにくい問題  処理時間がかかる。  メモリを大量に必要とする。  プログラムの優劣、アルゴリズムの優劣 を比較するためには、標準的なコン ピュータで比較する必要がある。  処理時間を計るのに、コンピュータのモ デルとして、チューリングマシンを考え、
Advertisements

Problem A : Everlasting...? 原案 : 泉 模範解答 : 黄・野田 解説 : 野田.
G 問題 コードアート オンライン 原案:西出 ライタ:伊藤 テスタ:西出. 問題概要 0 大きさのさまざまな n 個の円に多角形 m 個を入れら れるか判定する問題 0 ただし、同じ円に複数の多角形を入れることはでき ない 0 もし、入れられる場合は、辞書順最小の入れ方を出 力 ① ② ③ ① ②.
SlothLib.LinearAlgebra.FeatureVector 特徴ベクトル. SlothLib.LinearAlgebra.FeatureVector でできること ► 特徴ベクトル  次元は可変に増やすことができる  次元としてあらゆるデータ型が利用可能 ► string 型がよく使われる=文書の特徴ベクトル.
ACM/ICPC と アルゴリズム 「実践的プログラミング」 稲葉 一浩. 自己紹介 ﻪ 理Ⅰ → 理学部情報科学科 → 情報理工学系研究科コンピュータ科学専攻 ﻩ 博士課程1年 ﻩXML を扱う専用言語の研究など ﻪ 個人的には ﻩ ﻯD.
原案 : 野田 解答 : 野田・山 口 問題文 : 野田 PROBLEM E: PSYCHIC ACCELERATOR ~ とある超能力の物体加速器~
Problem C: Grated Radish ~大根おろし~. 成績 Submit 数: 0 Accept 数: 0 問題セットの中で最難問題なので解けな くても仕方が無いかなと思いつつ, 1 チー ム位 submit して欲しかった.
模擬国内予選2013 Problem F テトラ姫のパズル 原案:須藤 解答:大友、須藤 解説:須藤.
Wilcoxon の順位和検定 理論生態学研究室 山田 歩. 使用場面 2 標本 離散型分布 連続型分布(母集団が正規分布でない時など 効果的) ただパラメトリックな手法が使える条件がそ ろっている時に、ノンパラメトリックな手法 を用いると検出力(対立仮説が正しいときに 帰無仮説を棄却できる確率)が低下するとい.
J: Magical Switches JAG 模擬地区予選 2013 原案:保坂 解答:保坂・楠本 解説:保坂.
第6回 線形計画法の解法(4) 混合最小値問題 山梨大学.
4.3 マージソート.
3次元nクイーン問題の 解に関する研究 論理工学研究室 伊藤精一
Writter: slip0110 Tester: kioa341
ICPC夏合宿09 Day3 Problem D : Luigi‘s Tavern -ルイージの酒場-
Revenge of the Round Table
Day2 Problem I: Memory Match ~神経衰弱~
Problem H: Queen’s case
Problem A: ねこかわいがり♪ 問題作成: 山本 解法作成: 山本・高橋 解説: 山本.
1 正の数・負の数 2章 正の数・負の数の計算 §1 正の数・負の数の加法    ・減法  (8時間)
動的計画法 表の作成 制約の追加 練習問題.
動的計画法 表の作成 制約の追加 練習問題.
アルゴリズムとデータ構造1 2008年7月22日
アルゴリズムとデータ構造 第8回 ソート(3).
Alice in Foxland ~狐の国のアリス~
近似アルゴリズム 第10章 終了時刻最小化スケジューリング
A: Attack the Moles 原案:高橋 / 解説:保坂.
3.エネルギー.
演習00-0 “Hello,world![改行]”を表示するプログラムを作成せよ. 1 1.
5個の数字0,1,2,3,4から異なる3個を選んで3桁の整数を作る。
問題作成・解説: 北村 解答作成協力: 小西・松本
Problem G : Entangled Tree
出題: 大橋 テスト: 大橋・平原・秋葉 解説: 大橋(スライド)・平原(登壇)
初級ミクロ経済学 -生産者行動理論復習と前回宿題解説-
原案:阿部 担当:福澤, 笠原 英訳:寺島 解説:福澤
第10回 ソート(1):単純なソートアルゴリズム
JAG Regional Practice Contest 2012 問題C: Median Tree
データ構造と アルゴリズム 第二回 知能情報学部 新田直也.
 Combinations(2)        古川 勇輔.
2013年度模擬アジア地区予選 Problem E: Putter
第 七 回 双対問題とその解法 山梨大学.
Problem F Two-finger Programming
コンピュータと情報 第15回 Excelの使い方 その4.
コンピュータと情報 第14回 Excelの使い方 その4.
早わかりアントコロニー最適化 (ACO: Ant Colony Optimization)
決定木とランダムフォレスト 和田 俊和.
教師なしデータ 学習データ  X1, X2, …, Xn   真の情報源 テストデータ  X  .
問題:The hik Revolutions 解説:田村(sune2)
Problem I: Aaron と Bruce
25. Randomized Algorithms
3 と は、どちらが大きいでしょうか。 0 1 2 3 1 2 3 1 2 = = = 答え 分母に1、2、3をかけた数
プログラミング 4 整列アルゴリズム.
情報処理Ⅱ 第2回:2003年10月14日(火).
プログラミング 4 木構造とヒープ.
2011年度 情報科学&情報科学演習 ~ 定番プログラム(2) ~.
2016年度 有限幾何学 中間試験 問1 次のグラフを描け.(描けない場合は理由を述べよ) 各20点
Cプログラミング演習資料.
計算機プログラミングI 第6回 2002年11月14日(木) アルゴリズムと計算量 第1回課題の説明 平方根を計算するアルゴリズム 計算量
ナップサック問題 クマさん人形をめぐる熱いドラマの結末.
D: 壊れかけのヒープ 問題案: 稲葉.
重み付き投票ゲームにおける 投票力指数の計算の高速化
アルゴリズムとデータ構造 --- 理論編 --- 山本 真基
ソートのプログラムの流れ 配列の中身を小さい順に並び替える a[1],a[2],…a[n]の値を順に出力する
散らばり 本時の目標 資料の傾向をみるときは、代表値だけでなく散らばりを考える必要があることを理解する。
Chapter5 Systems of Distinct Representatives
コストのついたグラフの探索 分枝限定法 A*アルゴリズム.
C問題 高所恐怖症 原案・ライタ : 伊藤 テスタ : 青木・西出.
知能情報工学演習I 第11回(後半第5回) 課題の回答
計算技術研究会 第5回 C言語勉強会 関数(function)を使う
プログラミング論 バイナリーサーチ 1.
Presentation transcript:

Problem H ねこ鍋改造計画(仮) 秋葉 拓哉

猫 (性別, Cute, 重さ) Cute でソートしよう 性別 Cute 重さ メス 1 10 オス 4 2 8 5 6 3 9 7 19 15

デュアルねこ鍋 選んで鍋を作る 重さの和はそれぞれ W 以下 オス鍋 メス鍋 性別 Cute 重さ メス 1 10 オス 4 2 8 5 6 3 9 7 19 15 メス鍋 選んで鍋を作る 重さの和はそれぞれ W 以下

デュアルねこ鍋の評価 Cute の最大 - 最小 鍋同士の重量の差 この 2 つの大きい方 6 - 4 = 2 6 - 5 = 1 max(1, 2) = 2 Cute: 4, 6 重さの和: 5 Cute: 5 重さの和: 6 これを最小化したい!

つまり ① Cute が差 d 以下の範囲で ② 重さの差が d 以下になるような鍋 が作れる最小の d を求めたい 重さ 5 ① ② 性別 Cute 重さ メス 1 10 オス 4 2 8 5 6 3 9 7 19 15 ① ② 重さ 6 ① Cute が差 d 以下の範囲で ② 重さの差が d 以下になるような鍋 が作れる最小の d を求めたい

O(N3W) の解法 (TLE) 全ての Cute の範囲を試す ナップサックの DP O(N2) 通り O(NW) 範囲 重さ 1 2 3 性別 Cute 重さ メス 1 10 オス 4 2 8 5 6 3 9 7 19 15 範囲 重さ 1 2 3 4 5 6 7 8 9 10 11 12 オス × ○ メス

O(N2W) の解法 (TLE) 範囲を伸ばした時,ナップサック DP は直前の結果を再利用できる 性別 Cute 重さ メス 1 10 オス 4 2 8 5 6 3 9 7 19 15 1 2 3 4 5 6 7 8 9 10 11 12 × ○ 1 2 3 4 5 6 7 8 9 10 11 12 × ○

「その重量を作るために使う Cute の最小値」 O(NW log W) の解法 (TLE?) DP の値を,Yes/No から: 「その重量を作るために使う Cute の最小値」 区間を縮めることもできるようになる ある値以下を × 扱い 重さ 1 2 3 4 5 6 7 8 9 10 11 12 オス × メス

O(NW log W) の解法 (TLE?) 答えについて二分探索できるようになる 一度の判定に O(NW) 性別 Cute 重さ メス 1 10 オス 4 2 8 5 6 3 9 7 19 15 範囲の大きさ d が決まっていれば しゃくとり法のように 範囲を動かせばよい

O(NW) の解法 (想定解法) 答え=max 区間を広げる → ①が増え,②が減る 区間を縮める → ②が増え,①が減る ① Cute の最大 - 最小 ② 鍋同士の重量の差 答え=max 区間を広げる → ①が増え,②が減る 区間を縮める → ②が増え,①が減る 小さい方をさらに小さくしても意味がない 二分探索は必要なく,しゃくとり法を一度で十分

結果 First Submit: 98 min (USAGI Code) First Accept: 256 min (USAGI Code) Total Submit: 4 Total Accept: 1