大会告知の人の問題まとめ の履歴差分(No.3)

• 履歴一覧
• 現在との差分 を表示
• ソース を表示
• 履歴 を表示
• 大会告知の人の問題まとめ へ行く。
  • 1 (2008-04-20 (日) 18:54:54)
  • 2 (2008-04-22 (火) 00:45:57)
  • 3 (2008-08-11 (月) 14:55:34)
  • 4 (2008-11-12 (水) 17:27:14)

• 追加された行はこの色です。
• 削除された行はこの色です。

[[練習問題]]

*ナップサック問題 [#iabfd136]
-出典：有名問題なのでなし~
-難易度：やや難しい~

遠くの町とかに、いろいろなものを売りにいくことにします。~
商品には重さと価格が設定されていて、限界重要より合計が重くなる場合、持っていくことができません。~
（等しいのはＯＫ）~
また、１１個以上の同じ商品を売ることはできません。~
１回で得ることのできる最高の売り上げを出力しなさい。~
商品は正の整数単位でしか扱えません。

**[入力形式] [#r945ff69]
 限界重量　要素数
 要素ごとの重量（要素数個）
 要素ごとの価格（要素数個）

**[入力例] [#gcb2b368]
 100 3
 3 20 50
 5 25 40
**[出力例] [#dcbdffbc]
 130
（３が６個、２０が４個で、重量3*6+20*4=98<=100,価格5*6+25*4=130）

**[今回の問題の入力、Easy] [#wef0ee43]
 100000 10
 3 78 234 537 785 2345 4865 9247 21211 69867
 4 82 245 523 799 2465 5023 9010 19473 46849

**[今回の入力、Hard] [#y9ae5a22]
 100000 20
 2 4 7 13 28 51 67 99 203 282 590 869 1037 4958 5638 7694 9304 10385 10560 16593
 3 6 8 12 36 55 69 96 212 290 608 864 1033 4860 5583 7272 8674 9374 9465 13867 


答え確認が甘いからもしかしたら違うかも？ 
**答え（鳥） [#p2d85a52]
Easy→ ◆xc1iRlmLiw~
Hard→ ◆1mznm0BWf6

*できるだけ面積の小さい単純多角形を出力せよ [#k4571b2c]
 462 名前：大会告知の人[sage] 投稿日：2008/08/03(日) 03:53:39.11 ID:C8t01WX80
 久しぶりの問題投下になりますっ
 今までの問題はパターンで解けない問題ばかりだったので、今回は発想勝負のＮＰ問題に しましたっ
 難しい問題だと思いますが、よかったら解いてみてくださいっ、誰も解いてくれない気がしてるけどorz
 今回は答えが一意に定まらないので、コンテスト形式っぽくできたらいいなーって思ってますっ
 
 ～期限～
 8/11（日）　23:59まで
 
 ～問題～　引用：SuperCon2008本戦
 ｎ個の点の座標が与えられる。できるだけ面積の小さい単純多角形を出力せよ。
 都合上、面積×２をスコアとしますっ
 
 今回は補助ツール、入力ファイル等をつけたので、詳細はこちらからっ
 結局可視化はグラフ描画ツールgnuplotに任せることにしましたorz
 ttp://www8.uploader.jp/dl/vipprog/vipprog_uljp00434.rar.html
 
 今回の問題での出力されるデータの可視化の例ですっ（スコア：3562）
#ref(out.png,,30%);