Supercomputing Contest 2012/予選・認定問題
をテンプレートにして作成
[
トップ
] [
新規
|
一覧
|
単語検索
|
最終更新
|
ヘルプ
]
since1995
開始行:
&color(green){最終更新日時: &lastmod;};
//!!committee_edit!!
//&color(red){&size(20){編集中!by 時田.committee以外閲...
&color(red){&size(15){このページは随時改訂されます。また...
*SuperCon 2012 予選問題および認定問題 [#sb8133b6]
-&ref(sc2012pre006.pdf,,印刷用PDF版(ver.006));
-&ref(sc2012pre_templates004.zip,,雛形プログラム(ver.004));
-&ref(sc2012pre_sample002.zip,,入力データのサンプルと答(v...
''ナップサック問題とその変形:'' ナップサック問題というも...
以下、まず文字列についていくつかの定義を与えます。~
(1)文字列A,Bに対してAとBを連結した文字列を
A+B
で表すことにします。例えば、
A="super", B="con"に対して、A+B="supercon", B+A="consuper"
となります。数値の演算記号+と異なり,ここでの文字列の連結...
(2)文字列Aに対してAの長さを
|A|
で表します。空文字列の長さは0です。例えば、
A="supercon"に対して、|A|=8
です。~
(3)文字列Aに対してAのi文字目を
A(i)
で表します。例えば、
A="supercon"に対してA(1)=s, A(2)=u, ..., A(8)=n
となります。
(4)文字列A,Bに対して、辞書式順序でAがBより大きくないと...
A ≦ B
と表記します。ここでは,A ≦ Bであることの厳密な条件は、~
(a) A(i) ≠ B(i)であるような最小の i (1 ≦ i ≦ Min(|A|,|B|...
であるか、~
(b) A(i) ≠ B(i)であるようなiが存在せず|A| ≦ |B|
であるとします。~
例えば、(a)の場合の例は
"con" ≦ "super"、"superaon" ≦ "superconconcon"、"superab...
などです。上の2つ目の例 A="superaon"とB="superconconcon"...
(b)の場合の例は
"super" ≦ "supercon", "super" ≦ "super", (空文字列) ≦ "s...
などです。
''SuperCon2012 予選・認定問題''~
今回の予選・認定問題では、それぞれ文字列WおよびN個の文字...
v_{N-1}が与えられます。Wはナップサックの容量に対応し、v_i...
w_{S_0} + w_{S_1} + ... + w_{S_{k-1}} ≦ W
(k≦N)および
0 ≦ S_0 < S_1 < ... < S_{k-1} < N
を満たすような整数列S=(S_0, S_1, ...,S_{k-1})を選んで、対...
V=v_{S_0} + v_{S_1} + ... +v_{S_{k-1}}
のとりうる最大値を求めてください。なお、整数列Sは長さ0で...
Wなのでそのような選び方はいつでも制約を満たし、そのときに...
各級の認定と予選の問題については以下の制約に従うものとし...
** 問A (スーパーコン3級認定問題 2012年度版) [#b3c7eb40]
- N = 10
- 1 ≦ |w_i| ≦ 10
- 1 ≦ |W| ≦ 100
- -1000000 ≦ v_i ≦ 1000000
- w_i, Wは小文字のアルファベット(a,b,...,z)からなる文字列
ヒント:この問題は可能な文字列の結合全ての総当りが可能で...
** 問B (スーパーコン2級認定問題 2012年度版) [#u86c3b35]
- 1 ≦ N ≦ 1000
- 1 ≦ |w_i| ≦ 1000
- 1 ≦ |W| ≦ 10000
- -1000000 ≦ v_i ≦ 1000000
- w_i, Wはaのみからなる文字列
ヒント:この問題は可能な文字列の結合全ての総当りはできま...
** 問C (スーパーコン予選問題 兼 1級認定問題 2012年度版) ...
- 1 ≦ N ≦ 1000
- 1 ≦ |w_i| ≦ 10
- 1 ≦ |W| ≦ 10000
- -1000000 ≦ v_i ≦ 1000000
- w_i, Wは小文字のアルファベット(a,b,...,z)からなる文字列
上記の条件を満たす問題例10題に対して全て,Vの最大値を正...
*注意 [#ha120a07]
-作成するプログラム
-- プログラムは入出力の部分を規定した雛形プログラムをもと...
作って下さい。作成の際には「変更可能」とコメントされてい...
-- 提出するプログラムはチーム名をファイル名とする単一ファ...
-- プログラムは C 言語で記述して下さい。詳細は以下の通り...
--- プログラムは C 言語規格(ANSI C や C99 など)に準拠する...
--- int は 32 ビット,long long は 64 ビットを仮定します.l...
--- Linux 上の gcc ver 3.3.3 を使用してコンパイルし、Linu...
--- 移植性の問題(例えばエンディアンの違い)によるトラブル...
--- 文字列の比較に対しては、string.hをインクルードしてstr...
- 審査方法(スーパーコン認定に関して)
-- 応募プログラムをコンパイルし、10題の問題例に対して各...
//-- スーパーコン認定に使用する問題例ではm,n≤50(問Cの場合...
-- 審査環境におけるメモリはおよそ 4 ギガバイトです。
//((スーパーコン認定,予選選抜のどちらも審査は東工大のスパ...
- 審査方法(予選選抜に関して)
-- 応募プログラムをコンパイルし、10 題の問題例に対して各...
//-- 予選選抜で使用する問題例では m, n, k ≤ 200 とします.
-- 審査環境におけるメモリはおよそ 4 ギガバイトです.。
//((スーパコン認定と同じ環境です.))
-- 制限時間内に正確な答えを出している問題例の個数順をもと...
-- 同順位のチームに対しては、正解を出した計算の計算時間の...
-- 以上の順位付けのもとで、東西上位 10 チームずつを本選出...
*詳細説明 [#z469990a]
** 問題例の与え方 [#i43f906a]
問題例は以下のように与えられます。
N
W
v_0 w_0
v_1 w_1
...
v_{N-1} w_{N-1}
例えば
N = 3
W = jihgfedcb
(w_0, w_1, w_2) = (jih, adgfi, ghe)
(v_0, v_1, v_2) = (10, -3, 5)
に対する入力は次のようになります。
3
jihgfedcb
10 jih
-3 adgfi
5 ghe
この場合、v_1=-3(負)なので、一見w_1は選ばない方がよいよ...
//問題例は以下のように与えられます(ただし,k は問Cのみ).
//#ref(problem_example_yosen2011.png)
//たとえば右図の格子状道路網に対する問Bのプログラムに対す...
//#ref(program_input_yosen2011.png)
** 雛形プログラムについて [#s9dc70be]
雛形プログラムでは、上記の入力問題例のデータをそれぞれ以...
N=3
W="jihgfedcb"
w[0] = "jih"
w[1] = "adgfi"
w[2] = "ghe"
v[0] = 10
v[1] = -3
v[2] = 5
//雛形プログラムでは,上記の入力問題例の辺長のデータを,次...
//#ref(program_template_yosen2011.png)
* 改訂履歴 [#a4f9787b]
//#pcomment(SuperCon2012予選・認定問題改訂履歴,10,below,r...
//- 問Cの記述中の「最短経路長 の次の長さの経路長は 10 で...
//- 問題例の与え方の記述中の「たとえば右図の格子状道路網...
- 「入力データのサンプルと答(sc2012pre_sample.zip)」の...
- 問題例の与え方の例に全角スペースが入っていたのを半角ス...
終了行:
&color(green){最終更新日時: &lastmod;};
//!!committee_edit!!
//&color(red){&size(20){編集中!by 時田.committee以外閲...
&color(red){&size(15){このページは随時改訂されます。また...
*SuperCon 2012 予選問題および認定問題 [#sb8133b6]
-&ref(sc2012pre006.pdf,,印刷用PDF版(ver.006));
-&ref(sc2012pre_templates004.zip,,雛形プログラム(ver.004));
-&ref(sc2012pre_sample002.zip,,入力データのサンプルと答(v...
''ナップサック問題とその変形:'' ナップサック問題というも...
以下、まず文字列についていくつかの定義を与えます。~
(1)文字列A,Bに対してAとBを連結した文字列を
A+B
で表すことにします。例えば、
A="super", B="con"に対して、A+B="supercon", B+A="consuper"
となります。数値の演算記号+と異なり,ここでの文字列の連結...
(2)文字列Aに対してAの長さを
|A|
で表します。空文字列の長さは0です。例えば、
A="supercon"に対して、|A|=8
です。~
(3)文字列Aに対してAのi文字目を
A(i)
で表します。例えば、
A="supercon"に対してA(1)=s, A(2)=u, ..., A(8)=n
となります。
(4)文字列A,Bに対して、辞書式順序でAがBより大きくないと...
A ≦ B
と表記します。ここでは,A ≦ Bであることの厳密な条件は、~
(a) A(i) ≠ B(i)であるような最小の i (1 ≦ i ≦ Min(|A|,|B|...
であるか、~
(b) A(i) ≠ B(i)であるようなiが存在せず|A| ≦ |B|
であるとします。~
例えば、(a)の場合の例は
"con" ≦ "super"、"superaon" ≦ "superconconcon"、"superab...
などです。上の2つ目の例 A="superaon"とB="superconconcon"...
(b)の場合の例は
"super" ≦ "supercon", "super" ≦ "super", (空文字列) ≦ "s...
などです。
''SuperCon2012 予選・認定問題''~
今回の予選・認定問題では、それぞれ文字列WおよびN個の文字...
v_{N-1}が与えられます。Wはナップサックの容量に対応し、v_i...
w_{S_0} + w_{S_1} + ... + w_{S_{k-1}} ≦ W
(k≦N)および
0 ≦ S_0 < S_1 < ... < S_{k-1} < N
を満たすような整数列S=(S_0, S_1, ...,S_{k-1})を選んで、対...
V=v_{S_0} + v_{S_1} + ... +v_{S_{k-1}}
のとりうる最大値を求めてください。なお、整数列Sは長さ0で...
Wなのでそのような選び方はいつでも制約を満たし、そのときに...
各級の認定と予選の問題については以下の制約に従うものとし...
** 問A (スーパーコン3級認定問題 2012年度版) [#b3c7eb40]
- N = 10
- 1 ≦ |w_i| ≦ 10
- 1 ≦ |W| ≦ 100
- -1000000 ≦ v_i ≦ 1000000
- w_i, Wは小文字のアルファベット(a,b,...,z)からなる文字列
ヒント:この問題は可能な文字列の結合全ての総当りが可能で...
** 問B (スーパーコン2級認定問題 2012年度版) [#u86c3b35]
- 1 ≦ N ≦ 1000
- 1 ≦ |w_i| ≦ 1000
- 1 ≦ |W| ≦ 10000
- -1000000 ≦ v_i ≦ 1000000
- w_i, Wはaのみからなる文字列
ヒント:この問題は可能な文字列の結合全ての総当りはできま...
** 問C (スーパーコン予選問題 兼 1級認定問題 2012年度版) ...
- 1 ≦ N ≦ 1000
- 1 ≦ |w_i| ≦ 10
- 1 ≦ |W| ≦ 10000
- -1000000 ≦ v_i ≦ 1000000
- w_i, Wは小文字のアルファベット(a,b,...,z)からなる文字列
上記の条件を満たす問題例10題に対して全て,Vの最大値を正...
*注意 [#ha120a07]
-作成するプログラム
-- プログラムは入出力の部分を規定した雛形プログラムをもと...
作って下さい。作成の際には「変更可能」とコメントされてい...
-- 提出するプログラムはチーム名をファイル名とする単一ファ...
-- プログラムは C 言語で記述して下さい。詳細は以下の通り...
--- プログラムは C 言語規格(ANSI C や C99 など)に準拠する...
--- int は 32 ビット,long long は 64 ビットを仮定します.l...
--- Linux 上の gcc ver 3.3.3 を使用してコンパイルし、Linu...
--- 移植性の問題(例えばエンディアンの違い)によるトラブル...
--- 文字列の比較に対しては、string.hをインクルードしてstr...
- 審査方法(スーパーコン認定に関して)
-- 応募プログラムをコンパイルし、10題の問題例に対して各...
//-- スーパーコン認定に使用する問題例ではm,n≤50(問Cの場合...
-- 審査環境におけるメモリはおよそ 4 ギガバイトです。
//((スーパーコン認定,予選選抜のどちらも審査は東工大のスパ...
- 審査方法(予選選抜に関して)
-- 応募プログラムをコンパイルし、10 題の問題例に対して各...
//-- 予選選抜で使用する問題例では m, n, k ≤ 200 とします.
-- 審査環境におけるメモリはおよそ 4 ギガバイトです.。
//((スーパコン認定と同じ環境です.))
-- 制限時間内に正確な答えを出している問題例の個数順をもと...
-- 同順位のチームに対しては、正解を出した計算の計算時間の...
-- 以上の順位付けのもとで、東西上位 10 チームずつを本選出...
*詳細説明 [#z469990a]
** 問題例の与え方 [#i43f906a]
問題例は以下のように与えられます。
N
W
v_0 w_0
v_1 w_1
...
v_{N-1} w_{N-1}
例えば
N = 3
W = jihgfedcb
(w_0, w_1, w_2) = (jih, adgfi, ghe)
(v_0, v_1, v_2) = (10, -3, 5)
に対する入力は次のようになります。
3
jihgfedcb
10 jih
-3 adgfi
5 ghe
この場合、v_1=-3(負)なので、一見w_1は選ばない方がよいよ...
//問題例は以下のように与えられます(ただし,k は問Cのみ).
//#ref(problem_example_yosen2011.png)
//たとえば右図の格子状道路網に対する問Bのプログラムに対す...
//#ref(program_input_yosen2011.png)
** 雛形プログラムについて [#s9dc70be]
雛形プログラムでは、上記の入力問題例のデータをそれぞれ以...
N=3
W="jihgfedcb"
w[0] = "jih"
w[1] = "adgfi"
w[2] = "ghe"
v[0] = 10
v[1] = -3
v[2] = 5
//雛形プログラムでは,上記の入力問題例の辺長のデータを,次...
//#ref(program_template_yosen2011.png)
* 改訂履歴 [#a4f9787b]
//#pcomment(SuperCon2012予選・認定問題改訂履歴,10,below,r...
//- 問Cの記述中の「最短経路長 の次の長さの経路長は 10 で...
//- 問題例の与え方の記述中の「たとえば右図の格子状道路網...
- 「入力データのサンプルと答(sc2012pre_sample.zip)」の...
- 問題例の与え方の例に全角スペースが入っていたのを半角ス...
ページ名: