大会告知の人の問題まとめ
をテンプレートにして作成
[
トップ
] [
新規
|
一覧
|
検索
|
最終更新
|
ヘルプ
|
ログイン
]
開始行:
[[練習問題]]
*ナップサック問題 [#iabfd136]
-出典：有名問題なのでなし~
-難易度：やや難しい~
遠くの町とかに、いろいろなものを売りにいくことにします。~
商品には重さと価格が設定されていて、限界重量より合計が重...
（等しいのはＯＫ）~
また、１１個以上の同じ商品を売ることはできません。~
１回で得ることのできる最高の売り上げを出力しなさい。~
商品は正の整数単位でしか扱えません。
**[入力形式] [#r945ff69]
限界重量 要素数
要素ごとの重量（要素数個）
要素ごとの価格（要素数個）
**[入力例] [#gcb2b368]
100 3
3 20 50
5 25 40
**[出力例] [#dcbdffbc]
130
（３が６個、２０が４個で、重量3*6+20*4=98<=100,価格5*6+25...
**[今回の問題の入力、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...
3 6 8 12 36 55 69 96 212 290 608 864 1033 4860 5583 7272...
答え確認が甘いからもしかしたら違うかも？
**答え（鳥） [#p2d85a52]
Easy→ ◆xc1iRlmLiw~
Hard→ ◆1mznm0BWf6
*できるだけ面積の小さい単純多角形を出力せよ [#k4571b2c]
462 名前：大会告知の人[sage] 投稿日：2008/08/03(日) 03:5...
久しぶりの問題投下になりますっ
今までの問題はパターンで解けない問題ばかりだったので、今...
難しい問題だと思いますが、よかったら解いてみてくださいっ...
今回は答えが一意に定まらないので、コンテスト形式っぽくで...
～期限～
8/11（日） 23:59まで
～問題～ 引用：SuperCon2008本戦
ｎ個の点の座標が与えられる。できるだけ面積の小さい単純多...
都合上、面積×２をスコアとしますっ
今回は補助ツール、入力ファイル等をつけたので、詳細はこち...
結局可視化はグラフ描画ツールgnuplotに任せることにしまし...
ttp://www8.uploader.jp/dl/vipprog/vipprog_uljp00434.rar....
今回の問題での出力されるデータの可視化の例ですっ（スコア...
#ref(out.png,,30%);
*カード引いて期待値みたいな [#e161b516]
177 名前：大会告知の人 ◆qWKqM3PuXA [sage] 投稿日：2008...
>>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%)
となるので、期待値は0.666ってなりますっ
問題：Easy
11 12 → この結果をトリップに入力！
178 名前：大会告知の人 Hard→ ◆h3aDMKlUPY [sage] 投稿日...
問題：Hard
4950 4772→この答えをトリップに入力！
TopCoder１軍で正答率50%程度の問題ですっ
遅くなっちゃってごめんなさいー
終了行:
[[練習問題]]
*ナップサック問題 [#iabfd136]
-出典：有名問題なのでなし~
-難易度：やや難しい~
遠くの町とかに、いろいろなものを売りにいくことにします。~
商品には重さと価格が設定されていて、限界重量より合計が重...
（等しいのはＯＫ）~
また、１１個以上の同じ商品を売ることはできません。~
１回で得ることのできる最高の売り上げを出力しなさい。~
商品は正の整数単位でしか扱えません。
**[入力形式] [#r945ff69]
限界重量 要素数
要素ごとの重量（要素数個）
要素ごとの価格（要素数個）
**[入力例] [#gcb2b368]
100 3
3 20 50
5 25 40
**[出力例] [#dcbdffbc]
130
（３が６個、２０が４個で、重量3*6+20*4=98<=100,価格5*6+25...
**[今回の問題の入力、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...
3 6 8 12 36 55 69 96 212 290 608 864 1033 4860 5583 7272...
答え確認が甘いからもしかしたら違うかも？
**答え（鳥） [#p2d85a52]
Easy→ ◆xc1iRlmLiw~
Hard→ ◆1mznm0BWf6
*できるだけ面積の小さい単純多角形を出力せよ [#k4571b2c]
462 名前：大会告知の人[sage] 投稿日：2008/08/03(日) 03:5...
久しぶりの問題投下になりますっ
今までの問題はパターンで解けない問題ばかりだったので、今...
難しい問題だと思いますが、よかったら解いてみてくださいっ...
今回は答えが一意に定まらないので、コンテスト形式っぽくで...
～期限～
8/11（日） 23:59まで
～問題～ 引用：SuperCon2008本戦
ｎ個の点の座標が与えられる。できるだけ面積の小さい単純多...
都合上、面積×２をスコアとしますっ
今回は補助ツール、入力ファイル等をつけたので、詳細はこち...
結局可視化はグラフ描画ツールgnuplotに任せることにしまし...
ttp://www8.uploader.jp/dl/vipprog/vipprog_uljp00434.rar....
今回の問題での出力されるデータの可視化の例ですっ（スコア...
#ref(out.png,,30%);
*カード引いて期待値みたいな [#e161b516]
177 名前：大会告知の人 ◆qWKqM3PuXA [sage] 投稿日：2008...
>>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%)
となるので、期待値は0.666ってなりますっ
問題：Easy
11 12 → この結果をトリップに入力！
178 名前：大会告知の人 Hard→ ◆h3aDMKlUPY [sage] 投稿日...
問題：Hard
4950 4772→この答えをトリップに入力！
TopCoder１軍で正答率50%程度の問題ですっ
遅くなっちゃってごめんなさいー
ページ名:
