#author("2026-07-16T14:23:26+09:00;2023-02-23T23:33:35+09:00","default:vip","vip")
#author("2026-07-16T15:17:11+09:00;2023-02-23T23:33:35+09:00","default:vip","vip")
[[練習問題]]
----
#contents

----
一部修正あり

*始まり [#beginning]
[[wwwww.2ch.net/test/read.cgi/news4vip/1195140334/>https://kako.5ch.io/test/read.cgi/news4vip/1195140334/#744]]
 744 大会告知の人[] 2007/11/17(土) 22:55:05.49 ID:FHOAEBBy0
 TopCoderSRM377 02:00~
 スポンサーがついてないから今回は賞金なしだけど、出たい人は忘れずにっ
 
 あまりに反応がなくて悲しいから、次回から告知と同時に簡単めな大会系問題を出そうかなと考え中
 問題文とSampleInput、Outputを多少用意して、難しい例のOutputをトリップにして問題にするみたいな
 自分で考えてたらネタ絶対なくなるからTopCoder過去問になると思うけど

*正方形は何種類作れるか [#various-squares]
[[wwwww.2ch.net/test/read.cgi/news4vip/1195372921/>https://kako.5ch.io/test/read.cgi/news4vip/1195372921/#15]]
 15 大会告知の人 ◆Kaw7LaKFbg [] 2007/11/18(日) 17:22:58.14ID:ncGjqjjR0
 大会告知があるわけでもないけど、過疎ってるから今日のTopCoderの問題置いていきますね
 反応がよければ今後も続けようかなと思ったり

 TopCoder SRM377 Div1.easy/Div2.medium改題
 width,heightの二つの数値が与えられる。
 0<=x=<width,0<=y<=heightを満たす(x,y)に頂点が作れるものとして、
 正方形は何種類作れるかを出力せよ。出力の仕方はなんでもいいや
 
 Sample
 1 1 → 1
 1*1の幅しかなかったら(0,0)(0,1)(1,0)(1,1)の4点で作る一つのみ
 2 3 → 10
 1*1のが6個、2*2のが2個、あと◇みたいなのが2個
 3 3 → 20
 27 19 → 23940

 101 99 → ? この出力をトリップに
 
 最速レベル:3分
 1軍標準レベル:10分
 2軍標準レベル:30分

答え &color(transparent,#000){8665800};

*左反復累乗(テトレーションではない) [#left-repeated-exp]
*左反復累乗 [#left-repeated-exp]
[[テトレーション>https://ja.wikipedia.org/?curid=1524759]]ではない

[[yutori.2ch.net/test/read.cgi/news4vip/1195750977/>https://kako.5ch.io/test/read.cgi/news4vip/1195750977/#614]]
 614 大会告知の人[] 2007/11/24(土) 01:09:15.55 ID:9aaGTnTy0
 出典:一応自作
 Easy
 n(>=1)が与えられます。nに対しn-1回n乗したときの答えを返しなさい。
 Sample
 1 → 1
   1は1です。
 2 → 2^2 = 4
 3 → (3^3)^3 = ? トリップに入力
 Normal
 nがある程度大きくなると数が異常に大きくなるので、上の条件で99999999で割ったあまりを答えなさい。
 4 → ((4^4)^4)^4 = 30955873
 5 → 60895022
 37 → ?
 Hard
 もっとでっかいnでもがんばれっ
 654321→ ? (手元プログラムで2秒ほどかかります。)

 Easyは手動で計算できそうだけどプログラムで書いてねっ

 Easy→ ◆XjX0gbuAJI
 Normal→ ◆iF0rbvDk82
 Hard→ ◆uw93XkzB/I

答え Easy:&color(transparent,#030){19683}; Normal:&color(transparent,#330){54455482}; Hard:&color(transparent,#300){33987654};

*未知の言語 [#unknown-lang]
[[yutori.2ch.net/test/read.cgi/news4vip/1196066303/>https://kako.5ch.io/test/read.cgi/news4vip/1196066303/#417]]
 417 大会告知の人[] 2007/11/27(火) 21:36:43.86 ID:KZ01x1iR0 ?2BP(20)
 難易度が高い問題だし無駄に問題長くてややこしいからスルーされそうだけど一応

 TopCoderSRM377 Div1Hard改題
 昨日、ある宇宙人の太古の言語が発見されました。その言語の特徴として、
 1、P種類の母音とQ種類の子音がある
 2、子音も母音も一つの単語にそれぞれN+1個以上含まれていない
 3、単語は全て、連続した母音の後に連続した子音がくる。
 (aaaabbbbみたいな感じ。aeieoailghflkfghみたいな)
 4、単語は必ず1文字以上である
 5、単語にはアクセントがあり、母音の中に最大1個、子音の中に最大1個、合計最大2個がある
   アクセントのない単語ももちろんある。アクセントを置く文字の後に'をつけ。
 6、同じ文字列である2つの単語でも、アクセントの位置が違えば別の単語とみなす
 このルールに従うと、P,Q,N,Mが与えられたとき、何種類の単語が作れるかを出力せよ
 なお、P,Q,Nが大きくなると莫大な数字となるので、Mで割ったあまりを出力することとする
 
 Sample
 1 1 1 9 → 8
 (母音a、子音bとして、a,a',b,b',ab,a'b,ab',a'b'の8種類)
 2 3 2 1000 → 577
 4 5 3 99999999 → ?(Easy→ ◆W/i7k5x.Aw)
 1 1 1000000000 1000000000 → 0
 12 34 56 87654321 → 15609959
 12345678 87654321 99999999 98765432 → ?(Hard→ ◆cC1DFEEHDE)

*自然数の分解 [#factor]
[[yutori.2ch.net/test/read.cgi/news4vip/1200842382/>https://kako.5ch.io/test/read.cgi/news4vip/1200842382/#147]]
 147 大会告知の人[sage] 2008/01/21(月) 17:29:27.52 ID:bCEKGZP30
 TopCoderSRM368 Div1Easy/Div2Hard解題
 自然数n,kが与えられる。
 1~nまでの自然数の中で、kまでの数字のみの積で表すことが可能な整数の個数を出力せよ
 
 例、
 10 3 → 7 (5,7,10を除く7つの数が表せる、3*3=9みたいに同じ数字は何回かけてもOK)
 15 3 → 8
 123456 123 → 23855

 Easy
 100000 100 → ? この部分をトリップに入力 ◆UBuvZue3nU
 Hard
 5000000 1000 → ? この部分をトリップに入力 ◆41qcr8q2Ig

答え Easy:&color(transparent,#030){17442}; Hard:&color(transparent,#300){1196525};

*コラッツ予想 [#collatz]
参考: [[コラッツの問題 - Wikipedia>https://ja.wikipedia.org/?curid=415796]]

[[yutori.2ch.net/test/read.cgi/news4vip/1204489345/>https://kako.5ch.io/test/read.cgi/news4vip/1204489345/#235]]
 235 大会告知の人 ◆ENhx0vsFzI [sage] 2008/03/03(月) 18:22:11.11 ID:EjBHjRPf0
 じゃあ久しぶりの問題投下ってことでっ、なんか数学っぽい問題で申し訳ないけどっ
 数学っぽいの苦手な人はスルー推奨でよろですっ
 なんかもうちょっとプログラマっぽく楽しげな問題を探してるんだけど・・・うーんw

 TopCoderOpen2006 Round2 Medium改題
 関数f(x)を次のように定義する。
 xが偶数のとき、f(x)=x/2
 xが奇数のとき、f(x)=3x+1
 あるnに対しこの関数に連続で入れる作業をやったとき、偶数の処理が行われた場合A、
 奇数の処理が行われた場合をBを表記することにする。
 例えば、n=4のとき、4→2→1→4→2→1・・・となるので、AABAABAAB・・・となる。
 ここで、あるAとBのみで構成された文字列が与えられる。
 この文字列と、この方法で生成された文字列の先頭が完全に一致する全てのnを、
 n=ak+bの形で求めよ。a,bは常に0以上の整数で最小のものとする。
 
 例
 AAA → 8k+0
 3回連続2で割り切れるということは8の倍数なのでこうなる
 BA → 2k+1
 最初にBがくれば、次の数は必然的に偶数となるので、2k+1のままとなる。
 BAB → 4k+3
 やってみればわかるよっ、としかいいようがないやw
 AAAABAAAABAAAABAAAABAAAABAAAABAAAABAAAABAAAABAAAAB → 2199023255552k+1014933810256

 問題
 AABAAAAAABABAABABABABABABABABAAAAAAAA → 67108864k+???
 ???の部分を#???のような形でトリップに入力しなさい。

*金貨を銀貨に [#gold-to-silver]
本人海外遠征のため代理出題
[[yutori.2ch.net/test/read.cgi/news4vip/1209765343/>https://kako.5ch.io/test/read.cgi/news4vip/1209765343/#207]]
 207 大会告知の人2[] 2008/05/04(日) 03:44:33.51 ID:KA0Cf1ke0
 大会告知の人が旅立つとのことで帰ってくるまで変わりに出題してくれと頼まれました。
 そういうわけで変わりに出題するねー。

 -問題
 金の硬貨か銀の硬貨のどちらか1枚のみを持った人がそれぞれn人ずつ、計2n人いる。
 ある日、突然硬貨を没収されることになった。理不尽である。
 さすがにそれは酷すぎたので金の硬貨を没収された人は銀の硬貨をもらえることになった。理不尽である。
 回収の仕方は、とある箱の前に適当に並んで先頭から順に箱に硬貨を入れていくという方法である。
 このとき金の硬貨を入れた場合のみ、箱から銀の硬貨を取ることができる。
 しかしながら最初、箱には何も入っていないため、回収する順番を工夫しないと
 銀の硬貨が不足して金の硬貨を入れた人が銀の硬貨をもらえなくなってしまう。理不尽である。
 このとき、銀の硬貨が不足せずに硬貨を回収できるような並び方は全部で何通りあるか答えよ。
 
 -Easy
 Input
 4
 Output
 14
 
 -Normal
 Input
 10
 Output
 16796

 -Hard
 Input
 15
 Output
 答えはトリップ!◆JPtTyZJJ2c
答え &color(transparent,#100){9694845};

 -Very Hard
 Input
 20
 Output
 答えを9999991で割ったあまりをトリップに書いてください。◆jYckAHAkA.
 
 この答えは32bit整数を使って計算してると正しい答えが出ない場合があります。
 その場合は、__int64 とか long long とかの64bit整数を使いましょう。
 64bitで計算して、最後に上記値で割ってあまりを出すのもよし。
 途中の計算で常に上記値で割ってあまりを出してその値を使って計算するもよし。
 後者だと32bit整数のままでも計算できます。 
答え &color(transparent,#200){4126324};

 -Super Hard
 Input
 100
 Output
 答えを9999991で割ったあまりをトリップに書いてください。◆gZCSRkh/AQ
答え &color(transparent,#300){1293182};

 -(∵)
 Input
 200
 Output
 答えを9999991で割ったあまりをトリップに書いてください。◆bKrjdO02PA
答え &color(transparent,#400){9189994};

 -Σ(∵)
 Input
 1000
 Output
 答えを9999991で割ったあまりをトリップに書いてください。◆TqZmev98wk
答え &color(transparent,#500){1891219};

*漸化式 [#recurrence-formula]
本人海外遠征のため代理出題
[[yutori.2ch.net/test/read.cgi/news4vip/1209765343/>https://kako.5ch.io/test/read.cgi/news4vip/1209765343/#367]]
 367 大会告知の人2[] 2008/05/04(日) 16:48:42.80 ID:KA0Cf1ke0
 関数fは以下の式で与えられる。
     { 2 (n=0)
 f(n)= { 5 (n=1)
     { 2*f(n-1) - f(n-2) (n>=2)
 
 nが与えられたとき、f(n)を答えよ。
 
 
 -Easy
 Input
 5
 Output
 17
 
 -Normal
 Input
 20
 Output
 62

 -Hard
 Input
 39
 Output
 答えはトリップ!◆ToxyFMVOts
答え &color(transparent,#100){119};

 -Very Hard
 Input
 100
 Output
 答えはトリップ!◆fY2C9do16k
答え &color(transparent,#200){302};

 -Super Hard
 Input
 10000
 Output
 答えはトリップ!◆jiH7uGCSqQ
答え &color(transparent,#300){30002};

 -(∵)
 Input
 123456
 Output
 答えはトリップ!◆huORiY5Mic
答え &color(transparent,#400){370370};

 -Σ(∵)
 Input
 123456789987654321
 Output
 答えを9999991で割ったあまりをトリップに!◆vpK0qdfSl.
 
 64bit整数で計算することをおすすめします。
答え &color(transparent,#500){6595926};

*誕生日のパラドックス [#birthday-paradox]
[[yutori.2ch.net/test/read.cgi/news4vip/1208042507/>https://kako.5ch.io/test/read.cgi/news4vip/1208042507/#55]]
 55 大会告知の人 ◆5nE7B1ir6g[sage] 2008/04/13(日) 17:13:49.38 ID:lYjy216A0
 有名問題だし解いたこともある人も多いと思うけど、今回はいい問題が見つからなかったのでorz

 今週の問題 出典:有名問題なのでなし 難易度:かなり低い
 ある星では、1年がn日あります
 nが与えられるので、あるランダムで選んだk人の誕生日が一人でも重複している
 確率が1/2以上となる最低のkを出力せよ

 入力例
 365
 出力例
 23

 入力
 99999999
 出力
 ここの答えをトリップに入力っ!

答え &color(transparent,#000){11775};
~参考: [[誕生日のパラドックス - Wikipedia>https://ja.wikipedia.org/?curid=37507]]

*ナップサック問題 [#knapsack]
[[ex25.2ch.net/test/read.cgi/news4vip/1208600786>https://kako.5ch.io/test/read.cgi/news4vip/1208600786#99]]
 99 大会告知の人[sage] 2008/04/20(日) 14:43:33.41 ID:0YUwfltE0
 今週も忙しめなので有名問題でっ

 ~今週の問題~
 出典:有名問題なのでなし
 難易度:やや難しい

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

 [入力形式]
 限界重量 要素数
 要素ごとの重量(要素数個)
 要素ごとの価格(要素数個)

 [入力例]
 100 3
 3 20 50
 5 25 40

 [出力例]
 130
 (3が6個、20が4個で、重量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

答え Easy:&color(transparent,#030){102570}; Hard:&color(transparent,#300){99605};
~参考: [[ナップサック問題 - Wikipedia>https://ja.wikipedia.org/?curid=44980]]

*カッコをつける [#parentheses]
[[yutori.2ch.net/test/read.cgi/news4vip/1220110495/>https://kako.5ch.io/test/read.cgi/news4vip/1220110495/#9]]
 9 大会告知の人[sage] 2008/08/31(日) 00:57:28.38 ID:HpRjEhge0
 お久しぶりですっ,久々の問題投下ですっ
 いくつか企画を用意していますが,前回久しぶりに大型企画やったら滑ったので
 とりあえず普段の問題を1問投下して様子を見てみますっw
 
 トリップ回答方式がちょっと厳しくなってきたので,通常の問題形式にしましたっ
 解けてるかどうかすぐわかる問題なので,多分チェックいらないんじゃないかな・・・?
 前の形式の方がいいーとかいうのが言ってくださいっ
 できちゃったらソース貼っちゃっていただけるとうれしいですー,いろんな言語のソース期待してますっ

 [問題]
 「 ( 」と「) 」の2つが連続して含まれている文字列が与えられる.
 左側に「 ( 」を,右側に「 ) 」を最小の個数追加し,括弧が全て閉じた状態になったものを出力せよ.

 [入力例]→[出力例]
 ))((
 →(())(())
 )(()((
 →()(()(()))
 (())
 →(())
 )))()())))()))())()))()((((())())))((((())(((((())()((()()()(((()()((()()((((()()(((
 →((((((((((()))()())))()))())()))()((((())())))((((())(((((())()((()()()(((()()((()()((((()()((()))))))))))))))))))))

*ロト6 [#lot-six]
[[yutori.2ch.net/test/read.cgi/news4vip/1220623646/>https://kako.5ch.io/test/read.cgi/news4vip/1220623646/#377]]
 377 大会告知の人[sage] 2008/09/07(日) 00:02:25.61 ID:cAg7KSSz0
 [問題] 高校生クイズ2008より引用・改題
 1から1000000までのくじが与えられる.このうち6つを選ぶとき,くじの番号が連続せず,さらにくじの番号の合計値がM以下になる選び方が何通りあるかを出力せよ.
 ただし,答えが12345678を超える場合は,12345678で割ったあまりを出力せよ.

 [入力] Mのみが与えられる

 [例]
 30 → 0 少ないと一個も作れませんっ
 36 → 1 1,3,5,7,9,11の1通りのみっ
 37 → 2 ↑と1,3,5,7,9,12の2通りっ
 38 → 4 ↑に加え1,3,5,7,9,13と1,3,5,7,10,12の2通りが追加っ
 39 → 7 
 50 → 388

 [問題の入力]
 Easy: 100
 Medium: 20000
 Hard: 1000000

 できちゃったらソースコード貼っちゃって構いませんっ
 あってるかどうかのテストはトリップにてっ #答えで確認できますっ

 [答えのトリップ]
 Easy→ ◆zjxfidaX.I
 Medium→ ◆g47vo8.Hx.
 Hard→ ◆duf6uJCGfU

答え Easy:&color(transparent,#030){336339}; Medium:&color(transparent,#330){3947889}; Hard:&color(transparent,#300){6989838};

*最善手オセロ [#othello]
[[yutori.2ch.net/test/read.cgi/news4vip/1221215324/>https://kako.5ch.io/test/read.cgi/news4vip/1221215324/#335]]
 335 大会告知の人(東京都)[sage] 2008/09/14(日) 00:25:33.93 ID:ipWraHTq0
 日曜日なので問題投下ですっ,ちょっと今回は問題考えてなかったのでトリップまだ用意してませんっ
 今回は手でも解けそうな問題なので携帯の人もがんばってくださいなっ

 [問題]
 4×4のオセロがあります.お互い最善手を打ったときに,
 最終的に先手と後手の残ったのの数がいくつになるかを名前欄に記入しなさい.(黒11白5なら11-5)
 ただし,最善手とは,自分の数/(自分の数+相手の数)が最終的に多くなるような手であり,
 同数の場合は,自分の数ができるだけ少なくなるものを最善とする.

*降りられるカードギャンブルの期待値 [#cards]
*降りられるカードギャンブル [#cards]
[[jfk.2ch.net/test/read.cgi/news4vip/1226120601/>https://kako.5ch.io/test/read.cgi/news4vip/1226120601/#177]]
 177 大会告知の人[sage] 2008/11/09(日) 19:50:27.63 ID:gl9AUnYh0
 >>89-90
 ごめんなさいーっ、完全に忘れてましたっ
 ってことで即興で簡単めの問題投下ですっ
 
 TopCoder SRM420 Div1 Medium問題より引用、改題
 裏の状態で判別のできない赤いカードがA枚、青いカードがB枚混ざったカードの束をよくシャッフルします。
 あなたは、上から順番にカードを1枚ずつ引いていきます。赤いカードが出たら+1点、青いカードが出たら-1点です。
 あなたが好きなタイミングでこのゲームを止められるとき、あなたが得られる得点の期待値を答えなさい
 小数点含めて8文字目まであってれば、トリップ判別なので正解になりますw
 
 入力:A(赤の枚数) B(青)の順番
 
 サンプル:
 6 0 → 6
 全部引いて6点絶対もらえますっ
 
 0 3 → 0
 1枚も引かなければ0点以下にはなりませんっ
 
 2 2 → 0.666666666...
 最初当たる→そこでやめて1点(50%)
 最初外れる→次当たる(33%)→次当たってやめる、1点(16%)
                   →次外れて全回収、0点(16%)
         →次も外れて全回収(16%)
 となるので、期待値は0.666ってなりますっ
 
 問題:Easy
 11 12 → この結果をトリップに入力! ◆qWKqM3PuXA
 
 問題:Hard
 4950 4772→この答えをトリップに入力! ◆h3aDMKlUPY
 
 TopCoder1軍で正答率50%程度の問題ですっ
 遅くなっちゃってごめんなさいー

*ランダム順列(Shuffle) [#shuffle]
[[takeshima.2ch.net/test/read.cgi/news4vip/1231592620/>https://kako.5ch.io/test/read.cgi/news4vip/1231592620/#57]]
 57 以下、名無しにかわりましてVIPがお送りします[sage] 2009/01/10(土) 23:45:33.23 ID:KZ+jMLWv0
 じゃあ久々になんか投下するよっ、手抜きだけどっ
 1~1000000までの数字をランダムな順番に1回ずつすべて出現するように、
 適当なテキストファイルに書き込むプログラムを作りなさいっ、標準入出力でもいいよっ
 偏りとかが発生せず、毎回結果が変わって、1秒以内に終わるプログラムでお願いしますっ

* 詳細消失 [#lost]

**最大の正方形の大きさ [#largest-square]
入力ファイル消失 [[yutori.2ch.net/test/read.cgi/news4vip/1206811539/>https://kako.5ch.io/test/read.cgi/news4vip/1206811539/#123]]
 123 大会告知の人  ◆57MYyJXAgE [sage] 2008/03/30(日) 20:42:48.88 ID:6udFZA3Q0
 過疎みたいだから即興で久しぶりの問題投下だよっ
 <問題> 出典:特になし、有名問題?
 データのサイズnと、n*nの0か1のみで構成されたデータが与えられる
 1のみで構成されている最大の正方形の大きさを出力せよ
 
 入力例
 4
 1 1 1 1
 1 1 1 1
 1 1 0 1
 1 1 1 1
 
 出力例
 2
 (中まで全て1でないとだめなので、3や4は不可)

 入力
 ttp://www8.uploader.jp/dl/vipprog/vipprog_uljp00296.txt.htmlに掲載
 1000*1000のデータなのでやたら重たいので注意してくださいっ
 
 いつもどおり出力結果をトリップに入力してねっ

**電光掲示板 [#signage]
入力ファイル消失 [[yutori.2ch.net/test/read.cgi/news4vip/1207331519/>https://kako.5ch.io/test/read.cgi/news4vip/1207331519/#306]]
 306 ◆V/8NkpecHM [sage] 2008/04/06(日) 14:08:56.64 ID:vrmMRwMA0
 なんか>>1にコテ帰れって書いてあるからとりあえず名無しでっ、解答用酉はつけるけど・・・
 毎週日曜日に変更になった問題投下ですっ、答えを酉で入力して参加してくださいっ

 今週の問題(TopCoderSingleRoundMatch393 Div1Medium改題)
 ある電光掲示板があり、あなたはその電光掲示板のすべての正しい出力パターンを知っています。
 電光掲示板は、いくつものON,OFFのみのライトで構成されています。
 あなたはしばらく電光掲示板を眺めていたのですが、いくつかのライトが壊れているようなので、
 しばらく見ていて電光掲示板の実際に光ったライトの組み合わせをメモしました。
 正常に動いているランプの個数、壊れているランプの個数、さらに壊れているかどうかわからない
 ランプの個数を答えなさい。
 ただし、ランプが壊れているときは、ランプが常に消えた状態(0)になります。
 
 入力例
 3 ←正しい点灯パターンの個数
 11110
 11100 ←正しい点灯パターン。ONは1、OFFは0を表す
 11001
 2 ←観察していて現れた点灯パターンの個数、全てのパターンが観察中に現れるとは限らない
 01100 ←観察していて現れた転倒パターン
 01000
 出力例
 Y2N2?1 ←左から順番に、正常動作している個数、壊れている個数、わからない個数をこんな感じで出力
 左から順番に、壊れているのをYとして、この例だと左からNYY?Nとなります。

 入力
 ttp://www8.uploader.jp/dl/vipprog/vipprog_uljp00302.txt.html
 出力
 この部分をトリップに入力っ

 わかりにくいと思うので、わからない部分は質問してくださいっ

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

トップ   編集 差分 履歴 添付 複製 名前変更 リロード   新規 一覧 検索 最終更新   ヘルプ   最終更新のRSS