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

履歴一覧
差分を表示
現在との差分を表示
ソースを表示
大会告知の人の問題まとめへ行く。
- 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)

ナップサック問題†

出典：有名問題なのでなし
難易度：やや難しい

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

↑

[入力形式]†

限界重量　要素数
要素ごとの重量（要素数個）
要素ごとの価格（要素数個）

↑

[入力例]†

100 3
3 20 50
5 25 40

↑

[出力例]†

（３が６個、２０が４個で、重量3*6+20*4=98<=100,価格5*6+25*4=130）

↑

[今回の問題の入力、Easy]†

100000 10
3 78 234 537 785 2345 4865 9247 21211 69867
4 82 245 523 799 2465 5023 9010 19473 46849

↑

[今回の入力、Hard]†

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

答え確認が甘いからもしかしたら違うかも？

↑

答え（鳥）†

Easy→ ◆xc1iRlmLiw
Hard→ ◆1mznm0BWf6

↑

できるだけ面積の小さい単純多角形を出力せよ†

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）

↑

カード引いて期待値みたいな†

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%程度の問題ですっ
遅くなっちゃってごめんなさいー

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