Supercomputing Contest 2009/予選・認定問題

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

• 印刷用PDF版

問1 (スーパーコン3級認定問題 2009年度版) †

数直線上に同じ長さの区間がいくつか与えられたとき，それら全体が覆う部分の長さを計算するプログラムを作成して下さい．
この例では，8個の区間が与えられています．どの区間の長さも4です．青で示している部分が区間によって覆われていて，その長さは22です．

注：この例では端点の座標値が負である区間もありますが，実際の入力においてすべての区間の端点は非負です．詳しくは「問1についての詳細説明」をご覧下さい．

• すべての問いに共通する注意事項
• 問1についての詳細説明
• 問1用雛形プログラム

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

平面上にx軸かy軸に平行な同じ長さの線分がいくつか与えられたとき，それらの交差として現れる点の数を計算するプログラムを作成して下さい．
この例では，x軸に平行な線分が13個，y軸に平行な線分が14個与えられています．どの線分の長さも5です．青で示している点が線分どうしの交差で，その数は21です．

• すべての問いに共通する注意事項
• 問2についての詳細説明
• 問2用雛形プログラム

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

平面上に辺の長さがすべて同じで，どの辺もx軸かy軸に平行であるような正方形がいくつか与えられたとき，それら全体が覆う部分の面積を計算するプログラムを作成して下さい．
この例では，正方形が13個与えられています．正方形の辺の長さはどれも4です．青で示している部分が覆われている箇所で，その面積は172です．

• すべての問いに共通する注意事項
• 問3についての詳細説明
• 問3用雛形プログラム

注意 †

すべての問いに共通する事項 †

1. 作成するプログラム
   1. プログラムは入出力の部分を規定した雛形プログラムをもとに，その一部を修正する形で作って下さい． 作成の際には，「変更・削除しないこと」とコメントされている行は変更・削除しないようにして下さい．したがって，ここで指定された入力，出力以外のものを期待したプログラムは審査対象から除外されます．その他は適宜変更や追加して構いません．また，関数等を宣言して使用しても構いません．
      • 問1用雛形プログラム
      • 問2用雛形プログラム
      • 問3用雛形プログラム
   2. プログラムはヘッダファイル等を使わずに1つのファイルとしてまとめたものを提出して下さい．詳しくは「認定証応募方法」および「予選応募方法」のページをご覧ください．
   3. プログラムは，ANSI C に準拠するC言語で記述して下さい．
      • intは32ビット，longは64ビットを仮定します．
      • gcc ver 3.3.3を使用してコンパイルします．
      • Endianの違いによるトラブルに対しては対処しません．
2. 審査方法
   1. スーパーコン認定では，応募プログラムをコンパイルし，複数のテストデータに対して実行し，すべてに正確な答えを出している場合に合格とします．なお，誤差は認めません．詳細説明にあるように，答えは必ず整数になります．
   2. 各データに対し，実行時間が10分を越えた場合には失格とします．
   3. 審査環境におけるメモリはおよそ1GByteです．
   4. スーパーコン09予選応募者に対しては，複数の審査用データに対して実行し，すべてに正確な答えを出したプログラムの中から，実測した合計計算時間の順で，東西それぞれ上位10チームを本選出場候補チームとして選びます．本選出場候補チームには，同時にスーパーコン1級も授与します．

詳細説明 †

問1についての詳細説明 †

入力は以下のような形式で与えられます．

n d
a1
a2
a3
...
an 

はじめの行にあるnは入力に現れる区間の数です．また，dは入力に現れる各区間の長さです．その後に続くn行にはそれぞれ1つの区間の左端点の座標が格納され，例えば「a1」はその区間の左端点がa1であることを表します．すなわち，その行は[a1, a1+d]という区間に対応します． 次の条件を入力は必ず満たしています．

• nは1以上50,000以下の整数．
• dは1以上100以下の整数．
• 各区間の端点の座標は0以上10,000以下の整数．
• 出力は1以上10,000以下の整数．
• 同じ区間は二度以上現れません． ただし，2つの区間が重なりあったり，端点を共有することはありえます．

問2についての詳細説明 †

入力は以下のような形式で与えられます．

n m d
a1 b1
a2 b2
a3 b3
...
an bn
c1 d1
c2 d2
c3 d3
...
cm dm

はじめの行にあるnは入力に現れる線分でx軸に平行なものの数です．そして，mは入力に現れる線分でy軸に平行なものの数です．また，dは入力に現れる各線分の長さを表します．その後に続くn行にはそれぞれx軸に平行な線分の左端点が格納され，例えば「a1 b1」はその線分の左端点が (a1, b1) であり，もう一方の端点が (a1+d, b1) であることを表します．最後のm行はそれぞれy軸に平行な線分の下端点であり，例えば「c1 d1」はその線分の下端点が (c1, d1) であり，もう一方の端点が (c1, d1+d) であることを表します． 次の条件を入力は必ず満たしています．

• nとmはどちらも1以上50,000以下の整数．
• dは1以上100以下の整数．
• 各線分の端点の座標は0以上10,000以下の整数．
• 出力は0以上100,000,000以下の整数．
• 同じ線分は二度以上現れません．
• x軸に平行な線分どうしは交わらず，端点も共有しません．
• y軸に平行な線分どうしは交わらず，端点も共有しません．

ただし，x軸に平行な線分とy軸に平行な線分が端点を共有することはありえます．出力として数えるべき交差は線分の内部どうしの交差，線分の内部と端点の交差，線分の端点どうしの交差のすべてです．

問3についての詳細説明 †

入力は以下のような形式で与えられます．

n d
a1 b1 
a2 b2
a3 b3
...
an bn

はじめの行にあるnは入力に現れる正方形の数です．また，dは各正方形の1辺の長さです．その後に続くn行にはそれぞれ1つの正方形の左下の頂点が格納され，例えば「a1 b1」はその正方形の左下の頂点が (a1, b1) であることを表します．このとき，右下の頂点は (a1+d, b1)，左上の頂点は (a1, b1+d)，右上の頂点は (a1+d, b1+d) になります． 次の条件を入力は必ず満たしています．

• nは1以上50,000以下の整数．
• dは1以上100以下の整数．
• 各正方形の頂点の座標は0以上10,000以下の整数．
• 出力は1以上100,000,000以下の整数．
• 同じ正方形は二度以上現れません．

ただし，正方形どうしが重なりあったり，頂点や辺の一部を共有することはありえます．

改訂履歴 †

2009/06/03：問1用雛形プログラムのコメント部分にプログラムの説明を追加．コメント部分以外には変更なし．
2009/06/15：問1の問題例の後に端点の座標値に関する注を追加．