Supercomputing Contest 2012/予選・認定問題

最終更新日時: 2017-09-25 (月) 16:19:29

このページは随時改訂されます。また、質問や回答はSupercomputing Contest 2012/予選・認定問題Ｑ＆Ａにまとめていきますので合わせてご覧ください。

SuperCon 2012 予選問題および認定問題 †

• 印刷用PDF版(ver.006)
• 雛形プログラム(ver.004)
• 入力データのサンプルと答(ver.002) ←2012/06/01 16:12:37差し替えました．前の版の中のREADMEでは問Aと問Cの答が逆になっていました

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

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

（１）文字列A,Bに対してAとBを連結した文字列を

A+B

で表すことにします。例えば、

A="super", B="con"に対して、A+B="supercon", B+A="consuper"

となります。数値の演算記号+と異なり，ここでの文字列の連結記号+には順番があることに注意してください。

（２）文字列Aに対してAの長さを

|A|

で表します。空文字列の長さは0です。例えば、

A="supercon"に対して、|A|=8

です。

（３）文字列Aに対してAのi文字目を

A(i)

で表します。例えば、

A="supercon"に対してA(1)=s, A(2)=u, ..., A(8)=n

となります。

（４）文字列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"

などです。上の２つ目の例 A="superaon"とB="superconconcon"の場合、最初から５文字までは同じで、６文字目に初めて違いがあるので、違いの出る最小の i は６となります（A(6)≠B(6))。そして、６文字目のASCIIコードを比較すると、A(6)=aはB(6)=cより小さいので、"superaon"≦ "superconconcon"となります。この場合は７文字目以降がどんな文字列でも、またどれだけ長くても比較には影響しないことに注意してください。また、 (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年度版) †

• N = 10
• 1 ≦ |w_i| ≦ 10
• 1 ≦ |W| ≦ 100
• -1000000 ≦ v_i ≦ 1000000
• w_i, Wは小文字のアルファベット(a,b,...,z)からなる文字列

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

問B (スーパーコン2級認定問題　2012年度版) †

• 1 ≦ N ≦ 1000
• 1 ≦ |w_i| ≦ 1000
• 1 ≦ |W| ≦ 10000
• -1000000 ≦ v_i ≦ 1000000
• w_i, Wはaのみからなる文字列

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

問C (スーパーコン予選問題 兼 1級認定問題　2012年度版) †

• 1 ≦ N ≦ 1000
• 1 ≦ |w_i| ≦ 10
• 1 ≦ |W| ≦ 10000
• -1000000 ≦ v_i ≦ 1000000
• w_i, Wは小文字のアルファベット(a,b,...,z)からなる文字列

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

注意 †

• 作成するプログラム
  • プログラムは入出力の部分を規定した雛形プログラムをもとに,その一部を修正する形で 作って下さい。作成の際には「変更可能」とコメントされている範囲以外は変更・削除しな いようにして下さい。したがって、ここで指定された入力,出力以外のものを期待したプロ グラムは審査対象から除外されます。その他は適宜変更や追加して構いません。また,標準 ライブラリ関数等を宣言して使用しても構いません。
  • 提出するプログラムはチーム名をファイル名とする単一ファイルとして下さい。
  • プログラムは 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などを使っても構いません。

• 審査方法(スーパーコン認定に関して)
  • 応募プログラムをコンパイルし、１０題の問題例に対して各々 1 分間の制限時間で実行し、すべての問題例で制限時間内に正確な答えを出している場合に合格とします。
  • 審査環境におけるメモリはおよそ 4 ギガバイトです。

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

詳細説明 †

問題例の与え方 †

問題例は以下のように与えられます。

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が正解です。

雛形プログラムについて †

雛形プログラムでは、上記の入力問題例のデータをそれぞれ以下のようにint型のN, char型の配列W, char型の２次元配列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

改訂履歴 †

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