&color(green){最終更新日時: &lastmod;};
//!!committee_edit!!
//&color(red){&size(20){編集中!by 時田.committee以外閲覧も編集もできません};};

&color(red){&size(15){このページは随時改訂されます。また、質問や回答は[[Supercomputing Contest 2012/予選・認定問題Q&A]]にまとめていきますので合わせてご覧ください。};};

*SuperCon 2012 予選問題および認定問題 [#sb8133b6]
-&ref(sc2012pre006.pdf,,印刷用PDF版(ver.006));
-&ref(sc2012pre_templates004.zip,,雛形プログラム(ver.004));
-&ref(sc2012pre_sample002.zip,,入力データのサンプルと答(ver.002)); &color(red){←2012/06/01 16:12:37差し替えました.前の版の中のREADMEでは問Aと問Cの答が逆になっていました};

''ナップサック問題とその変形:'' ナップサック問題というものがあります。これは、ある容量のナップサックと体積と価値の定められたいくつかの品物があるとき、容量を越えないように品物をナップサックに詰め込み、ナップサック内の品物の価値の和をどれだけ大きくできるかという問題です。今年のSuperConの予選問題は、この「ナップサック問題」に文字列を取り入れた問題です。以下Webの制約から下つきの記号"_"が付いたままとなっていますが,正しくは上の印刷用PDF版をご覧ください。~

以下、まず文字列についていくつかの定義を与えます。~

(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|)、Min(X,Y)はX,Yのうち大きくない方)が存在してASCIIコードの比較(アルファベット順)でA(i) < B(i)
であるか、~

 (b) A(i) ≠ B(i)であるようなiが存在せず|A| ≦ |B|
であるとします。~

例えば、(a)の場合の例は
 "con" ≦ "super"、"superaon" ≦ "superconconcon"、"superabcdefg" ≦ "superb"
などです。上の2つ目の例 A="superaon"とB="superconconcon"の場合、最初から5文字までは同じで、6文字目に初めて違いがあるので、違いの出る最小の i は6となります(A(6)≠B(6))。そして、6文字目のASCIIコードを比較すると、A(6)=aはB(6)=cより小さいので、"superaon"≦ "superconconcon"となります。この場合は7文字目以降がどんな文字列でも、またどれだけ長くても比較には影響しないことに注意してください。また、
(b)の場合の例は
 "super" ≦ "supercon", "super" ≦ "super", (空文字列) ≦ "supercon"
などです。

''SuperCon2012 予選・認定問題''~

今回の予選・認定問題では、それぞれ文字列WおよびN個の文字列w_0, w_1, ..., w_{N-1}と整数v_0, v_1, ...,
v_{N-1}が与えられます。Wはナップサックの容量に対応し、v_iはi番目の文字列w_iの"価値"です。問題は、N個の文字列から何個かを選んで、以下の条件を満たすように(辞書式順序でWより大きくならないように)結合し、なるべく価値の合計が高い文字列を作るというものです。つまり、これらの入力に対して,
 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_iの和
 V=v_{S_0} + v_{S_1} + ... +v_{S_{k-1}}
のとりうる最大値を求めてください。なお、整数列Sは長さ0でも構いません。(空文字列) ≦
Wなのでそのような選び方はいつでも制約を満たし、そのときにはV=0ということになります。

各級の認定と予選の問題については以下の制約に従うものとします。

** 問A (スーパーコン3級認定問題 2012年度版) [#b3c7eb40]
- N = 10
- 1 ≦ |w_i| ≦ 10
- 1 ≦ |W| ≦ 100
- -1000000 ≦ v_i ≦ 1000000
- w_i, Wは小文字のアルファベット(a,b,...,z)からなる文字列

ヒント:この問題は可能な文字列の結合全ての総当りが可能です。上記の条件を満たす問題例10題に対して全て,Vの最大値を正しく求めた場合にスーパーコン3級を認定します。

** 問B (スーパーコン2級認定問題 2012年度版) [#u86c3b35]
- 1 ≦ N ≦ 1000
- 1 ≦ |w_i| ≦ 1000
- 1 ≦ |W| ≦ 10000
- -1000000 ≦ v_i ≦ 1000000
- w_i, Wはaのみからなる文字列

ヒント:この問題は可能な文字列の結合全ての総当りはできません。上記の条件を満たす問題例10題に対して全て,Vの最大値を正しく求めた場合にスーパーコン2級を認定します。


** 問C (スーパーコン予選問題 兼 1級認定問題 2012年度版) [#m72bd0b0]
- 1 ≦ N ≦ 1000
- 1 ≦ |w_i| ≦ 10
- 1 ≦ |W| ≦ 10000
- -1000000 ≦ v_i ≦ 1000000
- w_i, Wは小文字のアルファベット(a,b,...,z)からなる文字列

上記の条件を満たす問題例10題に対して全て,Vの最大値を正しく求めた場合にスーパーコン1級を認定します。

*注意 [#ha120a07]
-作成するプログラム
-- プログラムは入出力の部分を規定した雛形プログラムをもとに,その一部を修正する形で
作って下さい。作成の際には「変更可能」とコメントされている範囲以外は変更・削除しな いようにして下さい。したがって、ここで指定された入力,出力以外のものを期待したプロ グラムは審査対象から除外されます。その他は適宜変更や追加して構いません。また,標準 ライブラリ関数等を宣言して使用しても構いません。
-- 提出するプログラムはチーム名をファイル名とする単一ファイルとして下さい。
-- プログラムは C 言語で記述して下さい。詳細は以下の通りです。
--- プログラムは C 言語規格(ANSI C や C99 など)に準拠する C 言語で記述して下さい(インラインアセンブラの使用は禁止します)。
--- int は 32 ビット,long long は 64 ビットを仮定します.long のビット幅は環境により異なるので,64 ビットデータを扱いたい場合は long ではなく long long を使って下さい (<stdint.h> をインクルードして使える int64 t などを使うとさらに確実です)。
--- Linux 上の gcc ver 3.3.3 を使用してコンパイルし、Linux 上で実行します。この Linux は 64 ビット x86 64 版です。
--- 移植性の問題(例えばエンディアンの違い)によるトラブルには対処しません。
--- 文字列の比較に対しては、string.hをインクルードしてstrcmpやstrncmpなどを使っても構いません。

- 審査方法(スーパーコン認定に関して)
-- 応募プログラムをコンパイルし、10題の問題例に対して各々 1 分間の制限時間で実行し、すべての問題例で制限時間内に正確な答えを出している場合に合格とします。
//-- スーパーコン認定に使用する問題例ではm,n≤50(問Cの場合にはk≤50)とします.
-- 審査環境におけるメモリはおよそ 4 ギガバイトです。
//((スーパーコン認定,予選選抜のどちらも審査は東工大のスパコンTSUBAME2.0 の上で行う予定です.ただし(TSUBAME 全体では 1 万コア以上ありますが),審査では 1 コアのみ,かつメモリの制限を付けて実行するので,通常のパソコンと大差はありません.TSUBAME2.0 のスペックについての詳細に興味のある人はhttp://tsubame.gsic.titech.ac.jp/hardware-architecture を参照してください.))

- 審査方法(予選選抜に関して)
-- 応募プログラムをコンパイルし、10 題の問題例に対して各々 1 分間の制限時間で実行します。
//-- 予選選抜で使用する問題例では m, n, k ≤ 200 とします.
-- 審査環境におけるメモリはおよそ 4 ギガバイトです.。
//((スーパコン認定と同じ環境です.))
-- 制限時間内に正確な答えを出している問題例の個数順をもとに順位を決めます。
-- 同順位のチームに対しては、正解を出した計算の計算時間の合計を用いて順位を決めます (万が一、合計計算時間に優位差の無い場合には、合わせて提出されるプログラムの説明をもとに工夫度を評価して順位を決めます)。
-- 以上の順位付けのもとで、東西上位	10 チームずつを本選出場候補チームとして選びます。ただし, ''1 校からは最大 2 チームしか本戦出場できません''。本選出場候補チームには、同時にスーパーコン 1 級も授与します。

*詳細説明 [#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は選ばない方がよいように思えますが、v_2=5なのでw_2も選ぶことによりVをw_0だけ選ぶときの値V=v_0=10よりも大きな値V=10-3+5=12にすることができ、V=12が正解となります。w_1を選ばずにw_0とw_2だけを選んでV=v_0+v_2=10+5としたいところですが、w_0+w_2=jihgheとなってw_0+w_2≦Wの条件を満たさなくなってしまうので、そのような選び方はできないことにも注意してください。また、N=3, W=jihgfedcb, (w_0, w_1, w_2)=(jih, adgfi, ghe), (v_0, v_1, v_2)=(10,-3,2)の場合には、w_0だけを選ぶのがVを最大にするので、V=10が正解です。

//問題例は以下のように与えられます(ただし,k は問Cのみ).

//#ref(problem_example_yosen2011.png)

//たとえば右図の格子状道路網に対する問Bのプログラムに対する入力は次のようになります.

//#ref(program_input_yosen2011.png)

** 雛形プログラムについて [#s9dc70be]

雛形プログラムでは、上記の入力問題例のデータをそれぞれ以下のようにint型のN, char型の配列W, char型の2次元配列w, int型の配列vに格納します。それらを用いて「変更可能」とコメントされている範囲にプログラムを書いてください。

 N=3
 W="jihgfedcb"
 
 w[0] = "jih"
 w[1] = "adgfi"
 w[2] = "ghe"
 
 v[0] = 10
 v[1] = -3
 v[2] = 5

//雛形プログラムでは,上記の入力問題例の辺長のデータを,次のような配列 D[m + 1][n + 1][4] に 格納するまで行います.それを用いて計算してください.

//#ref(program_template_yosen2011.png)

* 改訂履歴 [#a4f9787b]
//#pcomment(SuperCon2012予選・認定問題改訂履歴,10,below,reply)
//- 問Cの記述中の「最短経路長 の次の長さの経路長は 10 で,その経路長を達成する経路の個数は4なので」の中の「4」を「6」に修正.
//- 問題例の与え方の記述中の「たとえば右図の格子状道路網に対する問Aのプログラムに対する入力は」の中の「問A」を「問B」に修正.

- 「入力データのサンプルと答(sc2012pre_sample.zip)」の中のREADMEの中のa.txtとc.txtの答えが逆になっていました.修正済みの現在の版(sc2012pre_sample002.zip)をお使いください.
- 問題例の与え方の例に全角スペースが入っていたのを半角スペースに修正しました。

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