練習問題

一部修正あり

始まり†

wwwww.2ch.net/test/read.cgi/news4vip/1195140334/

744 大会告知の人[] 2007/11/17(土) 22:55:05.49 ID:FHOAEBBy0
TopCoderSRM377 02:00～
スポンサーがついてないから今回は賞金なしだけど、出たい人は忘れずにっ

あまりに反応がなくて悲しいから、次回から告知と同時に簡単めな大会系問題を出そうかなと考え中
問題文とSampleInput、Outputを多少用意して、難しい例のOutputをトリップにして問題にするみたいな
自分で考えてたらネタ絶対なくなるからTopCoder過去問になると思うけど
↑

正方形は何種類作れるか†

wwwww.2ch.net/test/read.cgi/news4vip/1195372921/

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)の４点で作る一つのみ
2 3　→　10
1*1のが6個、2*2のが2個、あと◇みたいなのが2個
3 3　→　20
27 19　→　23940
101 99　→　？　この出力をトリップに

最速レベル：３分
１軍標準レベル：１０分
２軍標準レベル：３０分

答え 8665800

↑

左反復累乗（テトレーションではない）†

yutori.2ch.net/test/read.cgi/news4vip/1195750977/

614 大会告知の人[] 2007/11/24(土) 01:09:15.55 ID:9aaGTnTy0
出典：一応自作
Easy
ｎ(>=1)が与えられます。ｎに対し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→　？　（手元プログラムで２秒ほどかかります。）
Easyは手動で計算できそうだけどプログラムで書いてねっ
Easy→ ◆XjX0gbuAJI
Normal→ ◆iF0rbvDk82
Hard→ ◆uw93XkzB/I

答え Easy:19683 Normal:54455482 Hard:33987654

↑

未知の言語†

yutori.2ch.net/test/read.cgi/news4vip/1196066303/

417 大会告知の人[] 2007/11/27(火) 21:36:43.86 ID:KZ01x1iR0 ?2BP(20)
難易度が高い問題だし無駄に問題長くてややこしいからスルーされそうだけど一応
TopCoderSRM377 Div1Hard改題
昨日、ある宇宙人の太古の言語が発見されました。その言語の特徴として、
１、P種類の母音とQ種類の子音がある
２、子音も母音も一つの単語にそれぞれN+1個以上含まれていない
３、単語は全て、連続した母音の後に連続した子音がくる。
（aaaabbbbみたいな感じ。aeieoailghflkfghみたいな）
４、単語は必ず１文字以上である
５、単語にはアクセントがあり、母音の中に最大１個、子音の中に最大１個、合計最大２個がある
　　アクセントのない単語ももちろんある。アクセントを置く文字の後に'をつけ。
６、同じ文字列である２つの単語でも、アクセントの位置が違えば別の単語とみなす
このルールに従うと、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'の８種類）
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)
↑

自然数の因数分解†

yutori.2ch.net/test/read.cgi/news4vip/1200842382/

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を除く７つの数が表せる、3*3=9みたいに同じ数字は何回かけてもＯＫ)
15 3 → 8
123456 123 → 23855
Easy
100000 100 → ？　この部分をトリップに入力 ◆UBuvZue3nU
Hard
5000000 1000 → ？　この部分をトリップに入力 ◆41qcr8q2Ig

答え Easy:17442 Hard:1196525

↑

コラッツ予想†

参考: コラッツの問題 - Wikipedia

yutori.2ch.net/test/read.cgi/news4vip/1204489345/

235 大会告知の人 ◆ENhx0vsFzI [sage] 2008/03/03(月) 18:22:11.11 ID:EjBHjRPf0
じゃあ久しぶりの問題投下ってことでっ、なんか数学っぽい問題で申し訳ないけどっ
数学っぽいの苦手な人はスルー推奨でよろですっ
なんかもうちょっとプログラマっぽく楽しげな問題を探してるんだけど・・・うーんｗ
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=ak+bの形で求めよ。a,bは常に０以上の整数で最小のものとする。

例
AAA　→　8k+0
３回連続２で割り切れるということは８の倍数なのでこうなる
BA　→　2k+1
最初にBがくれば、次の数は必然的に偶数となるので、2k+1のままとなる。
BAB　→　4k+3
やってみればわかるよっ、としかいいようがないやｗ
AAAABAAAABAAAABAAAABAAAABAAAABAAAABAAAABAAAABAAAAB → 2199023255552k+1014933810256
問題
AABAAAAAABABAABABABABABABABABAAAAAAAA　→　67108864k+？？？
？？？の部分を#？？？のような形でトリップに入力しなさい。
↑

金貨を銀貨に†

本人海外遠征のため代理出題 yutori.2ch.net/test/read.cgi/news4vip/1209765343/

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
-Very Hard
Input
20
Output
答えを9999991で割ったあまりをトリップに書いてください。◆jYckAHAkA.

この答えは32bit整数を使って計算してると正しい答えが出ない場合があります。
その場合は、__int64 とか　long long とかの64bit整数を使いましょう。
64bitで計算して、最後に上記値で割ってあまりを出すのもよし。
途中の計算で常に上記値で割ってあまりを出してその値を使って計算するもよし。
後者だと32bit整数のままでも計算できます。 
-Super Hard
Input
100
Output
答えを9999991で割ったあまりをトリップに書いてください。◆gZCSRkh/AQ
-(∵)
Input
200
Output
答えを9999991で割ったあまりをトリップに書いてください。◆bKrjdO02PA
-Σ(∵)
Input
1000
Output
答えを9999991で割ったあまりをトリップに書いてください。◆TqZmev98wk
↑

漸化式†

本人海外遠征のため代理出題 yutori.2ch.net/test/read.cgi/news4vip/1209765343/

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

答え 119

-Very Hard
Input
100
Output
答えはトリップ！◆fY2C9do16k

答え 302

-Super Hard
Input
10000
Output
答えはトリップ！◆jiH7uGCSqQ

答え 30002

-(∵)
Input
123456
Output
答えはトリップ！◆huORiY5Mic

答え 370370

-Σ(∵)
Input
123456789987654321
Output
答えを9999991で割ったあまりをトリップに！◆vpK0qdfSl.

64bit整数で計算することをおすすめします。

答え 6595926

↑

誕生日のパラドックス†

参考: 誕生日のパラドックス - Wikipedia

yutori.2ch.net/test/read.cgi/news4vip/1208042507/

55 大会告知の人 ◆5nE7B1ir6g[sage] 2008/04/13(日) 17:13:49.38 ID:lYjy216A0
有名問題だし解いたこともある人も多いと思うけど、今回はいい問題が見つからなかったのでorz
今週の問題　出典：有名問題なのでなし　難易度：かなり低い
ある星では、１年がｎ日あります
ｎが与えられるので、あるランダムで選んだｋ人の誕生日が一人でも重複している
確率が1/2以上となる最低のｋを出力せよ
入力例
365
出力例
23
入力
99999999
出力
ここの答えをトリップに入力っ！

答え 11775

↑

ナップサック問題†

参考: ナップサック問題 - Wikipedia

ex25.2ch.net/test/read.cgi/news4vip/1208600786

99 大会告知の人[sage] 2008/04/20(日) 14:43:33.41 ID:0YUwfltE0
今週も忙しめなので有名問題でっ
～今週の問題～
出典：有名問題なのでなし
難易度：やや難しい
遠くの町とかに、いろいろなものを売りにいくことにします。
商品には重さと価格が設定されていて、限界重量より合計が重くなる場合、持っていくことができません。
（等しいのはＯＫ）
また、１１個以上の同じ商品を売ることはできません。
１回で得ることのできる最高の売り上げを出力しなさい。
商品は正の整数単位でしか扱えません。
[入力形式]
限界重量　要素数
要素ごとの重量（要素数個）
要素ごとの価格（要素数個）
[入力例]
100 3
3 20 50
5 25 40
[出力例]
130
（３が６個、２０が４個で、重量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:102570 Hard:99605

↑

カッコをつける†

yutori.2ch.net/test/read.cgi/news4vip/1220110495/

9 大会告知の人[sage] 2008/08/31(日) 00:57:28.38 ID:HpRjEhge0
お久しぶりですっ，久々の問題投下ですっ
いくつか企画を用意していますが，前回久しぶりに大型企画やったら滑ったので
とりあえず普段の問題を１問投下して様子を見てみますっｗ

トリップ回答方式がちょっと厳しくなってきたので，通常の問題形式にしましたっ
解けてるかどうかすぐわかる問題なので，多分チェックいらないんじゃないかな・・・？
前の形式の方がいいーとかいうのが言ってくださいっ
できちゃったらソース貼っちゃっていただけるとうれしいですー，いろんな言語のソース期待してますっ
[問題]
「 ( 」と「) 」の２つが連続して含まれている文字列が与えられる．
左側に「 ( 」を，右側に「 ) 」を最小の個数追加し，括弧が全て閉じた状態になったものを出力せよ．
[入力例]→[出力例]
))((
→(())(())
)(()((
→()(()(()))
(())
→(())
)))()())))()))())()))()((((())())))((((())(((((())()((()()()(((()()((()()((((()()(((
→((((((((((()))()())))()))())()))()((((())())))((((())(((((())()((()()()(((()()((()()((((()()((()))))))))))))))))))))
↑

ロト6†

yutori.2ch.net/test/read.cgi/news4vip/1220623646/

377 大会告知の人[sage] 2008/09/07(日) 00:02:25.61 ID:cAg7KSSz0
[問題]　高校生クイズ２００８より引用・改題
1から1000000までのくじが与えられる．このうち６つを選ぶとき，くじの番号が連続せず，さらにくじの番号の合計値がM以下になる選び方が何通りあるかを出力せよ．
ただし，答えが12345678を超える場合は，12345678で割ったあまりを出力せよ．
[入力] Mのみが与えられる
[例]
30 → 0　少ないと一個も作れませんっ
36 → 1　1,3,5,7,9,11の１通りのみっ
37 → 2　↑と1,3,5,7,9,12の２通りっ
38 → 4　↑に加え1,3,5,7,9,13と1,3,5,7,10,12の２通りが追加っ
39 → 7　
50 → 388
[問題の入力]
Easy: 100
Medium: 20000
Hard: 1000000
できちゃったらソースコード貼っちゃって構いませんっ
あってるかどうかのテストはトリップにてっ　#答えで確認できますっ
[答えのトリップ]
Easy→ ◆zjxfidaX.I
Medium→ ◆g47vo8.Hx.
Hard→ ◆duf6uJCGfU

答え Easy:336339 Medium:3947889 Hard:6989838

↑

最善手オセロ†

yutori.2ch.net/test/read.cgi/news4vip/1221215324/

335 大会告知の人(東京都)[sage] 2008/09/14(日) 00:25:33.93 ID:ipWraHTq0
日曜日なので問題投下ですっ，ちょっと今回は問題考えてなかったのでトリップまだ用意してませんっ
今回は手でも解けそうな問題なので携帯の人もがんばってくださいなっ
[問題]
４×４のオセロがあります．お互い最善手を打ったときに，
最終的に先手と後手の残ったのの数がいくつになるかを名前欄に記入しなさい．（黒１１白５なら11-5）
ただし，最善手とは，自分の数/（自分の数+相手の数）が最終的に多くなるような手であり，
同数の場合は，自分の数ができるだけ少なくなるものを最善とする．
↑

降りられるカードギャンブルの期待値†

jfk.2ch.net/test/read.cgi/news4vip/1226120601/

177 大会告知の人[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　→　この結果をトリップに入力！ ◆qWKqM3PuXA

問題：Hard
4950 4772→この答えをトリップに入力！ ◆h3aDMKlUPY

TopCoder１軍で正答率50%程度の問題ですっ
遅くなっちゃってごめんなさいー
↑

ランダム順列（Shuffle）†

takeshima.2ch.net/test/read.cgi/news4vip/1231592620/

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

詳細消失†

↑

最大の正方形の大きさ†

入力ファイル消失 yutori.2ch.net/test/read.cgi/news4vip/1206811539/

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でないとだめなので、３や４は不可）
入力
ttp://www8.uploader.jp/dl/vipprog/vipprog_uljp00296.txt.htmlに掲載
1000*1000のデータなのでやたら重たいので注意してくださいっ

いつもどおり出力結果をトリップに入力してねっ
↑

電光掲示板†

入力ファイル消失 yutori.2ch.net/test/read.cgi/news4vip/1207331519/

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
出力
この部分をトリップに入力っ
わかりにくいと思うので、わからない部分は質問してくださいっ
↑

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

ファイル消失により詳細不明 yutori.2ch.net/test/read.cgi/news4vip/1217616871/

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）
out.png
トップ   新規 一覧 検索 最終更新   ヘルプ   最終更新のRSS