プログラミングの問題の書き方

[みけCAT]

プログラミングの問題を書いてみました。
形式は日本情報オリンピック予選を想定しています。

コード:

VS Apache Killer

　A君はHTTPサーバーを自作しています。ある日、A君は
自分が作っているサーバーがApache Killerの攻撃を
食らってしまう可能性に気づきました。Apache Killerの
攻撃を阻止するためには、与えられたRangeヘッダーから
返すべき正しい範囲を求めなければいけません。しかし、
A君のプログラミングの腕はいまひとつなので、A君は
このプログラムをかけません。よって、あなたがA君の
代わりにこの作業を行うプログラムを書いてあげてください。
　返すべき範囲のリストが与えられる。このリストの要素の
１個以上に含まれている範囲を全て出力するプログラムを書け。

入力
1行目：リストの個数n
m+1行目(1≦m≦n)：返すべき範囲sm em(スペース区切り)
　smバイト目からemバイト目までを返すべきである事を示す。

1≦n≦10000
0≦sm≦em≦2^31-1

出力
n行目：返すべき範囲sn en(スペース区切り)
　snバイト目からenバイト目までを返すべきである事を示す。

不連続な返すべき範囲の数だけ過不足無く行を出力する。
行の最後には必ず改行を入れる。
各行はsnの小さい順に出力する。

サンプル入出力
入力１
2
0 10
5 19
出力１
0 19

入力２
2
0 9
20 29
出力２
0 9
20 29

入力３
3
10 19
0 15
20 29
出力３
0 29 

本格的な問題を書いたことはないので、どのような書き方がいいのかよくわかりません。
問題の書き方、テストケースの作り方などを教えていただければ幸いです。
よろしくお願いします。
この問題を解くだけの返信も歓迎します。（色々な言語ででも・・・）

自分の解答ソースコードはこれです。

► スポイラーを表示

コード:

#include <stdio.h>
#include <stdlib.h>

typedef struct {
	unsigned int start;
	unsigned int end;
} range_t;

int comp(const void* x,const void* y) {
	range_t* a=(range_t*)x;
	range_t* b=(range_t*)y;
	if(a->start>b->start)return 1;
	if(a->start<b->start)return -1;
	if(a->end>b->end)return 1;
	if(a->end<b->end)return -1;
	return 0;
}

int main(void) {
	int datanum;
	int i;
	int resultnum;
	range_t input[10000];
	range_t result[10000];
	scanf("%d",&datanum);
	for(i=0;i<datanum;i++) {
		scanf("%u %u",&input[i].start,&input[i].end);
	}
	qsort(input,datanum,sizeof(range_t),comp);
	resultnum=1;
	result[0].start=input[0].start;
	result[0].end=input[0].end;
	for(i=1;i<datanum;i++) {
		if(input[i].start<=result[resultnum-1].end+1) {
			if(input[i].end>result[resultnum-1].end) {
				result[resultnum-1].end=input[i].end;
			}
		} else {
			result[resultnum].start=input[i].start;
			result[resultnum].end=input[i].end;
			resultnum++;
		}
	}
	for(i=0;i<resultnum;i++) {
		printf("%u %u\n",result[i].start,result[i].end);
	}
	return 0;
}

もしこのコードが間違っているなら、撃墜例とともに教えていただければありがたいです。
よろしくお願いします。

日記とのマルチポストです。
http://dixq.net/forum/blog.php?u=536&b=2508

2011/11/1 16:20頃
ソースコードを差し替えました。

[beatle]

問題文を書く場合、出題対象とする人々の間で常識ではない知識は説明するといいと思います。
例えば今回の問題例では（この掲示板の利用者を出題対象とするなら）「Apache Killer」や「Rangeヘッダー」を知らない人は多いはずです。
したがって、その2つを誰でも分かるように説明しましょう。
（「返すべき範囲」も意味が分かりませんが、きっと2つの説明を聞けば理解できるのでしょう）

テストケースは、すべての場合を尽くすようにすればいいと思います。
問題文はあくまで補助で、テストケースが仕様だということにすれば、
採点が楽です。

せっかくだから回答を貼っておきます。採点お願いします。

► スポイラーを表示

コード:

#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>

using namespace std;

typedef std::pair<size_t, size_t> RangeType;

void MergePushRange(std::vector<RangeType>& range_data, const RangeType& range)
{
	if (range_data.empty() || range_data.back().second + 1 < range.first)
	{
		range_data.push_back(range);
	}
	else
	{
		range_data.back().second = range.second;
	}
}

int main()
{
	size_t numdata = 0;
	cin >> numdata;

	vector<RangeType> range_data;
	RangeType r;
	for (size_t i = 0; i < numdata; ++i)
	{
		cin >> r.first >> r.second;
		range_data.push_back(r);
	}

	sort(range_data.begin(), range_data.end(), [](const RangeType& a, const RangeType& b)
	{
		return a.first < b.first || a.second < b.second;
	});

	vector<RangeType> result;
	for (auto it = range_data.begin(); it != range_data.end(); ++it)
	{
		MergePushRange(result, *it);
	}

	for (auto it = result.begin(); it != result.end(); ++it)
	{
		cout << it->first << ' ' << it->second << endl;
	}
}

[みけCAT]

せっかくだから回答を貼っておきます。採点お願いします。

Ideoneで実行したところ、Runtime Error(SIGSEGV)となる入力がありました。
http://ideone.com/rsGuH
(#12は最後まで入力できていないようなので気にしないでください。

[a5ua]

C++で書きました。
（言語かぶってしまった。いろんな言語での回答に期待）

ソース（Visual C++ 2010 で作成）

► スポイラーを表示

コード:

#include <iostream>
#include <set>
#include <utility>
#include <algorithm>

typedef std::pair<int, int> range;
typedef std::set<range> range_set;

void add(range_set &ranges, range r)
{
	range_set::iterator it;

	// r ⊆ x なる x が存在する場合
	// r は不要なので終了
	it = std::find_if(ranges.begin(), ranges.end(), [r](range x) {
		return x.first <= r.first && r.second <= x.second;
	});
	if (it != ranges.end()) {
		return;
	}

	// x ⊆ r なる x が存在する場合
	// x を削除
	it = std::find_if(ranges.begin(), ranges.end(), [r](range x) {
		return r.first <= x.first && x.second <= r.second;
	});
	if (it != ranges.end()) {
		ranges.erase(it);
	}

	// r が x の右側にくっついてる場合
	// r を左側に伸ばし、x を削除
	it = std::find_if(ranges.begin(), ranges.end(), [r](range x) {
		return x.first <= r.first && r.first <= x.second + 1;
	});
	if (it != ranges.end()) {
		r.first = it->first;
		ranges.erase(it);
	}

	// r が x の左側にくっついてる場合
	// r を右に伸ばし、x を削除
	it = std::find_if(ranges.begin(), ranges.end(), [r](range x) {
		return x.first - 1 <= r.second && r.second <= x.second;
	});
	if (it != ranges.end()) {
		r.second = it->second;
		ranges.erase(it);
	}

	// 追加
	ranges.insert(r);
}

int main()
{
	int n;
	std::cin >> n;
	range_set ranges;
	while (n--) {
		range r;
		std::cin >> r.first >> r.second;
		add(ranges, r);
	}
	std::for_each(ranges.begin(), ranges.end(), [](range r) {
		std::cout << r.first << " " << r.second << std::endl;
	});
	return 0;
}

[みけCAT]

二人ともC++0xことC++11か・・・。
ふぇぇ、コンパイルが通らないよぉ。><

[bitter_fox]

Javaで書きました。
問題の解釈が難しかったです。

► スポイラーを表示

コード:

import java.awt.geom.*;
import java.io.*;
import java.util.*;

class Range implements Comparable<Range>
{
	private Line2D.Double line;

	public Range(int xMin, int xMax)
	{
		line = new Line2D.Double(xMin - 0.5, 0, xMax + 0.5, 0);
	}

	public static boolean combine(Range r1, Range r2)
	{
		if (r1.line.intersectsLine(r2.line))
		{
			r1.line.x1 = Math.min(r1.line.x1, r2.line.x1);
			r1.line.x2 = Math.max(r1.line.x2, r2.line.x2);

			r2.line.setLine(r1.line);

			return true;
		}
		return false;
	}

	public int getIntX1()
	{
		return (int)(line.x1 + 0.5);
	}

	public int getIntX2()
	{
		return (int)(line.x2 - 0.5);
	}

	public int compareTo(Range r)
	{
		Line2D.Double l1 = this.line, l2 = r.line;

		if (l1.x1 < l2.x1)
		{
			return -1;
		}
		else if (l1.x1 == l2.x1)
		{
			if (l1.x2 < l2.x2)
			{
				return -1;
			}
			else if (l1.x2 == l2.x2)
			{
				return 0;
			}
			else
			{
				return 1;
			}
		}
		else
		{
			return 1;
		}
	}
}

public class Main
{
	public static void main(String[] args) throws IOException
	{
		TreeSet<Range> inputSet = new TreeSet<>();

		try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in)))
		{
			int n = Integer.parseInt(br.readLine());

			for (int i = 0; i < n; i++)
			{
				String[] s = br.readLine().split(" ");

				inputSet.add(new Range(Integer.parseInt(s[0]), Integer.parseInt(s[1])));
			}

			TreeSet<Range> set = new TreeSet<>(
				new Comparator<Range>()
				{
					public int compare(Range r1, Range r2)
					{
						if (Range.combine(r1, r2))
						{
							return 0;
						}
						return r1.compareTo(r2);
					}
				});
			set.addAll(inputSet);

			for (Range r : set)
			{
				System.out.printf("%d %d\n", r.getIntX1(), r.getIntX2());
			}
		}
		catch (IOException ioe)
		{}
	}
}

合ってるかな？
[hr]
11/11/12 9：40やや修正
同 9:52使ってないメソッド削除
同 10：11もうちょっとクレバーに変更

[beatle]

再度挑戦してみました。
runtime_errorになりにくくなりました。

► スポイラーを表示

コード:

#include <iostream>
#include <map>
#include <utility>

template <typename Key0, typename Key1, typename Value0, typename Value1>
inline bool Intersect(const std::pair<Key0, Value0>& range0, const std::pair<Key1, Value1>& range1)
{
    // must be range0.first <= range1.first
    return range1.first <= range0.second + 1;
}

template <typename Key0, typename Key1, typename Value0, typename Value1>
inline bool Enclose(const std::pair<Key0, Value0>& range0, const std::pair<Key1, Value1>& range1)
{
    // must be range0.first <= range1.first
    return range1.second <= range0.second;
}

template <typename Key, typename Value>
std::pair<Key, Value> MergeAndErase(std::map<Key, Value>& ranges, std::pair<Key, Value> range,
        const typename std::map<Key, Value>::iterator& next)
{
    auto it = next;
    while (it != ranges.end() && Enclose(range, *it))
    {
        it = ranges.erase(it);
    }
    if (it != ranges.end() && Intersect(range, *it))
    {
        range.second = it->second;
        it = ranges.erase(it);
    }
    return range;
}

template <typename Key, typename Value>
void InsertOrMerge(std::map<Key, Value>& ranges, std::pair<Key, Value> range,
        const typename std::map<Key, Value>::iterator& next)
{
    range = MergeAndErase(ranges, range, next);
    ranges.insert(range);
}

template <typename Key, typename Value>
void InsertOrMerge(std::map<Key, Value>& ranges, std::pair<Key, Value> range,
        const typename std::map<Key, Value>::iterator& prev, const typename std::map<Key, Value>::iterator& next)
{
    if (Intersect(*prev, range))
    {
        range = MergeAndErase(ranges, range, next);
        if (prev->second < range.second)
        {
            prev->second = range.second;
        }
    }
    else
    {
        InsertOrMerge(ranges, range, next);
    }
}

template <typename Key, typename Value>
void InsertOrMerge(std::map<Key, Value>& ranges, const std::pair<Key, Value>& range)
{
    if (ranges.empty())
    {
        ranges.insert(range);
    }
    else
    {
        auto next = ranges.lower_bound(range.first);

        if (next != ranges.begin())
        {
            auto prev = next;
            --prev;
            InsertOrMerge(ranges, range, prev, next);
        }
        else
        {
            InsertOrMerge(ranges, range, next);
        }
    }
}

int main()
{
    using namespace std;
    typedef long IntType;

    map<IntType, IntType> ranges;

    size_t numdata = 0;
    cin >> numdata;

    IntType a = 0, b = 0;
    for (size_t i = 0; i < numdata; ++i)
    {
        cin >> a >> b;
        InsertOrMerge(ranges, make_pair(a, b));
    }

    for (auto it = ranges.begin(); it != ranges.end(); ++it)
    {
        cout << it->first << " " << it->second << endl;
    }
}

採点お願いします＞＜

2010/11/12 12:37 プログラムミス修正（1行）
2010/11/12 14:27 プログラムミス修正（大量）

[うしお]

C# でやってみました。こういうのは頭がこんがらがりますね～脳のキレが悪いだけですが（笑
「このリストの要素の１個以上に含まれている範囲を全て出力するプログラムを書け」
これが正直わかりにくかったです。
「この範囲リストで表現される範囲を、最少個数の範囲リストで出力しなさい」
等はどうでしょう？

► スポイラーを表示

コード:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Diagnostics;

namespace VS_Apache_Killer
{
    class Range
    {
        public uint beg { set; get; }
        public uint end { set; get; }
        public override string ToString()
        {
            return beg + " " + end;
        }
    }
    class Program
    {
        static void Main(string[] args)
        {
            try
            {
                var rangeNum = int.Parse(Console.ReadLine());
                var ranges = new List<Range>(rangeNum);

                for (var i = 0; i < rangeNum; ++i)
                {
                    var buf = Console.ReadLine().Split(' ');
                    ranges.Add(new Range() { beg = uint.Parse(buf[0]), end = uint.Parse(buf[1]) });
                }
                ranges.Sort((a, b) =>
                {
                    if (b.beg < a.beg && b.end < a.end)
                    {
                        return 1;
                    }
                    else if(a.beg < b.beg && a.end < b.end)
                    {
                        return -1;
                    }
                    return 0;
                });
                var results = new List<Range>();
                results.Add(ranges[0]);
                for(var i = 1 ; i < ranges.Count ; ++i)
                {
                    var last = results.Last();
                    if (ranges[i].beg > last.end + 1) /*0-1 3-5等*/
                    {
                        results.Add(ranges[i]);
                    }
                    else /*1-2 0-4, 0-4 2-5 等*/
                    {
                        last.beg = Math.Min(last.beg, ranges[i].beg);
                        last.end = Math.Max(last.end, ranges[i].end);
                    }
                }
                Console.WriteLine("results");
                results.ForEach(Console.WriteLine);
            }
            catch (Exception e)
            {
                Debug.Print(e.ToString());
            }
        }
    }
}

Split(' ');うまく表示されないんですね・・ →Split(' ');

[beatle]

テストケースの実行を支援するアプリを書きました。

test.py

► スポイラーを表示

コード:

#!/usr/bin/python
import subprocess
import sys
import os.path

if len(sys.argv) != 2:
	exit(-1)

# テストケース名には、とりあえず0から999までの番号を使う
numfile = 1000

for i in range(0, numfile):
	# テストケース名を生成
	in_name = "%d.in" % (i, )
	out_name = "%d.out" % (i, )
	# テストケースファイルが存在するか確認
	if not os.path.exists(in_name) or not os.path.exists(out_name):
		continue
	# テストケースファイルを開く
	in_file = open(in_name)
	out_file = open(out_name)
	
	# テスト実行（引数で指定されたアプリを実行し、出力を比べる）
	p = subprocess.Popen("%s < %d.in | diff - %d.out | wc -c" % (sys.argv[1], i, i),
			shell = True, cwd = "./",
			stdin = subprocess.PIPE,
			stdout = subprocess.PIPE)
	p.wait()
	# 出力とテストケースに差がないか調べる
	if p.stdout.readline() == "0\n":
		# 差が0バイトである
		print("test %d OK" % (i, ))
	else:
		print("test %d FAILED" % (i, ))

使い方は

コード:

$ ./test.py ./a.out

です。a.outにはテスト対象のプログラムのパスを書きます。

テストケースは 0.in, 0.out のように、「N.in」と「N.out」の組で作ります。
N.inには標準入力に入力する内容を、N.outには標準出力の期待される出力内容を書きます。
例えば

0.in

コード:

2
0 10
5 19

0.out

コード:

0 19

という具合です。

試しにみけCATさんが示した3つの例を0, 1, 2とすると、テスト結果はこんな感じで出力されます。

コード:

test 0 OK
test 1 OK
test 2 FAILED

[しひ]

指摘はほとんど出ているので解答だけ。OCamlで書きました。
http://ideone.com/meBjZ