[[練習問題]] *ナップサック問題 [#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%); *カード引いて期待値みたいな [#e161b516] 177 名前：大会告知の人 ◆qWKqM3PuXA [sage] 投稿日：2008/11/09(日) 19:50:27.63 ID:gl9AUnYh0 >>89-90 ごめんなさいーっ、完全に忘れてましたっ ってことで即興で簡単めの問題投下ですっ TopCoder SRM420 Div1 Medium問題より引用、改題 裏の状態で判別のできない赤いカードがA枚、青いカードがB枚混ざったカードの束をよくシャッフルします。 あなたは、上から順番にカードを１枚ずつ引いていきます。赤いカードが出たら＋１点、青いカードが出たら－１点です。 あなたが好きなタイミングでこのゲームを止められるとき、あなたが得られる得点の期待値を答えなさい 小数点含めて８文字目まであってれば、トリップ判別なので正解になりますｗ 入力：A（赤の枚数） B（青）の順番 サンプル： 6 0 → 6 全部引いて６点絶対もらえますっ 0 3 → 0 １枚も引かなければ０点以下にはなりませんっ 2 2 → 0.666666666... 最初当たる→そこでやめて1点(50%) 最初外れる→次当たる(33%)→次当たってやめる、１点(16%) →次外れて全回収、０点(16%) →次も外れて全回収(16%) となるので、期待値は0.666ってなりますっ 問題：Easy 11 12 → この結果をトリップに入力！ 178 名前：大会告知の人 Hard→ ◆h3aDMKlUPY [sage] 投稿日：2008/11/09(日) 19:52:28.59 ID:gl9AUnYh0 問題：Hard 4950 4772→この答えをトリップに入力！ TopCoder１軍で正答率50%程度の問題ですっ 遅くなっちゃってごめんなさいー