円周上の点による最大面積多角形(プログラム・プロムナード)
スポンサーリンク
概要
- 論文の詳細を見る
今回の問題は,2000年11月につくばで開催されたアジア地区予選の問題G,Telescopeである.半径1の円周上にn個の点が与えられる.そのうちのm個を選んで作られる多角形(m角形)のうちの最大面積を求めるのが問題である.n,mはあらかじめ与えられ,さらに各点の位置は0≤p<1なる実数値として与えられる(1は一周,すなわち360度を表す).問題の規模は3≤m≤n≤40となっている.図-1に問題の解答例を示す.最も単純に考えると,n個の点からm個を取り出す組合せをすべて生成し,その面積を求めて最大値をとればよい.しかしそのような組合せは、_nC_m=n!/(m!(n-m)!)であり,これはつまりnの指数オーダの時間を要することになる.実際,この問題の規模では_<40>C_<20>≃1.4×10^<11>だから現在の計算機でそのまま計算するのは時間的に少し苦しいことになる(問題の規模さえ十分小さければ,こういった力任せの方法も悪くはない).このような指数オーダの時間を要する組合せ問題の計算量をいかに減らすか,が今回のテーマである.
- 一般社団法人情報処理学会の論文
- 2002-06-15
著者
関連論文
- CodeDrummer: プログラム実行における関数呼び出しの可聴化手法
- 表データ操作をRDBで強化したWikiシステム
- Web情報を用いたキーワード抽出によるタグづけ支援
- Web情報を用いたキーワード抽出によるタグづけ支援
- ScoutView:Webページにおけるナビゲーション支援インタフェース
- HTTPログにおける付随リクエストの発生特性の分析(ウェブ情報とデータベースに関して(ポスター講演))
- Javaプログラムを対象とするGUI操作記録・再生型デバッグシステム
- 閲覧履歴を利用した協調フィルタリングによるWebページ推薦とその評価(夏のデータベースワークショップ2007(データ工学,一般))
- 閲覧履歴を利用した協調フィルタリングによるWebページ推薦とその評価(情報抽出および推薦,夏のデータベースワークショップ2007(データ工学,一般))
- K-001 閲覧履歴を共有するウェブブラウザ(K分野:ヒューマンコミュニケーション&インタラクション)
- クラスファイル変換によるJavaプログラムの実行制御
- 関数単位疑似逆実行の高速化
- デバッガのためのプログラム疑似逆実行方式
- 5ZF-5 表データ操作をRDBで強化したWikiシステム(Web応用,学生セッション,インタフェース,情報処理学会創立50周年記念)
- 5ZF-8 手書きを用いた動画上の非同期コミュニケーションシステム(Web応用,学生セッション,インタフェース,情報処理学会創立50周年記念)
- プログラム理解の記録・再利用のための統合ソフトウェアシステム
- 認識信頼度を用いた誤認識修正支援エディタの検討
- ダーティビット情報を用いた世代別ごみ集めのGNU Emacsへの実装
- 世代別ごみ集めでのプログラムの文脈に基づくシンボルの配置法
- フレンドリーアーティファクトのためのロバストな顔認識システム
- GNU Emacsへの世代別ごみ集めの実装
- 1N-8 Web推薦のためのP2Pネットワークの構築と評価(Webサービス提供,学生セッション,データベースとメディア)
- M-050 Peer-to-PeerにおけるPush型情報共有を介したクラスタリング(M分野:ユビキタス・モバイルコンピューティング)
- サイコロパズル(プログラム・プロムナード)
- Niklaus Wirth : Algorithms + Data Structures = Programs(20世紀の名著名論)
- ケーブルマスタ(プログラム・プロムナード)
- 充電器が足りなくて(プログラム・プロムナード)
- 世代別GCの殿堂入りポリシー : mark/cons比の限界とスタックフレームからの到達性の利用
- 木の図示(プログラム・プロムナード)
- 木の図示
- プログラム・プロムナード 丸い紙吹雪
- どこで会える?(プログラム・プロムナード)
- 六角形の組合せ(プログラム・プロムナード)
- 円周上の点による最大面積多角形(プログラム・プロムナード)
- 自動書記メタファによるGUIの提案
- 文脈自由文法を利用した再帰的画像生成への時間軸の導入
- ドラッグ操作によるJavaプログラムリファクタリングシステム
- J-001 Webブラウザを用いた手書きメモ共有システムの提案(ヒューマンコミュニケーション(1),J分野:ヒューマンコミュニケーション&インタラクション)
- K-032 SNSの機能を利用したプログラミング学習支援(教育工学(1),K分野:教育工学・福祉工学・マルチメディア応用)
- K-005 PADを利用したパズル型プログラミング学習システム(教育工学(1),K分野:教育工学・福祉工学・マルチメディア応用)
- RO-007 Webページの分類と閲覧時間を利用したコンテンツフィルタリング(情報検索,O分野:情報システム)
- M-015 スマートフォンでの利用に特化したWikiシステムの開発(モバイルアプリケーション,M分野:ユビキタス・モバイルコンピューティング)
- RM-008 Twitterにおけるリツイート経路の重ね合わせによるユーザ発見支援(行動パターン分析,M分野:ビキタス・モバイルコンピューティング)