編入試験過去の問題について

Question

編入学勉強中の者です。過去問で
公園では、n人（1<=n<=100)の人がジョギングをした、それぞれの人は、時刻、t_s(1<=n<=500)にスタートし、時刻
t_e(1<=n<=500)に走るのを終えていた。この日、最も多くの人が走っている時間帯には、何人の人が同時に走っていたかを計算するプログラムc++言語または、c言語で作成せよ。ただし,n,t_s,t_eは標準入力から与えられるものとし、、例えば、C++言語では以下のような形で得られるものとする。必要なライブラリ等や標準入力のプログラムも記述すること。

#include<iostream>
using namespace std;
void main(){
     int i;
      int t_s[100],t_e[100];

      cin>>n;
      for(int i=0;i<n;i++){
        cin>>t_s[i];
        cin>>t_e[i];
        }
}**ボールドテキスト**

まず#include<iostream>,using namespace std;やsin>>の意味がよくわからずさらに、計算する方法が思いつきませんでした。
教えていただけないでしょうか。

#include <stdio.h>

void main()
{
	int i;
	int n;
	int t_s[100];
	int t_e[100];

	printf("何人走りましたか");
	scanf_s("%d" ,&n);

	printf("走り始めと終わりのタイムを入力してください");
	for (i = 0;i < n;i++)
	{
		printf("%d人目\n",i+1);
		scanf_s("%d" ,&t_s[i]);
		scanf_s("%d" ,&t_e[i]);


	}
}

ボールドテキスト
自分の学んでいる言語はc言語です。
この後の計算がよくわかりませんでした。（質問内容が不十分ですみません。）

Comments

[cateye]

“sin>>”は“cin>>”の間違いです。

[jimbe]

c++ は分からないと言うことのようですが, c は如何なのでしょうか.
c が出来るとすれば, c で標準入力からのデータの取得部分だけても書いてみては如何でしょう.
c も出来ないとなれば, 何の言語なら出来るでしょうか.

[coco_bauer]

何か、自力で簡単なプログラムを書くことが出来るプログラミング言語を知っていますか？
質問者がCやC#を知らないのは判りましたが、何か知っているプログラミング言語があるなら、その言語と比較して理解を深めることができるかもしれません。

[jimbe]

> c++言語または、c言語で作成せよ
なのですから, 無理に c++ でやらなくても良いのではないでしょうか.

そして,
『公園では, 10人がジョギングをした.
それぞれの人は8時以降に走り始め, 9時までに終えていた.
この日, 最も多くの人が走っている時刻には, 何人の人が同時に走っていたか.
(時刻は分単位で考えること)』
というのを机上で計算するとしたら, ayaaya さんならどのように求めるでしょうか.

Answer 1

まず#include<iostream>,using namespace std;やsin>>の意味がよくわからず

このレベルでしたら、「本を一冊買う」あるいは「どこかスクールに入る」などして、体系的に学ぶことを優先すべき場面です。

Answer 2

さらに、計算する方法が思いつきませんでした。

逆です。計算する方法がわからなければ、どんなにプログラミング言語に習熟していたとしても計算するプログラムは書けません。プログラミング言語というのは、コンピュータに命令するやり方の規則ということでしかありません。何を命令すればいいのかわからなければ、いくら命令の仕方を知っていても無駄です。

まず、その問題を日本語で解いて下さい。数学(もしかして算数?)の問題です。プログラミングの話に持ち込むのはその後です。

Answer 3

まず、C++について勉強しましょう。

#include<iostream>

については江添亮のC++入門の“簡単な1つのソースファイルからなるプログラムの実行”あたりかな？
C++日本語リファレンスも参考にｄ＾＾

Answer 4

#include <iostream>
#include <sstream>
#include <algorithm>

int main() {
  using namespace std;
  // 標準入力のかわり
  istringstream stream("3 "
                       "100 130 "
                       "110 140 "
                       "120 150 ");
  int slot[500]; // 時刻tに走っている人の数:slot[t]
  fill(slot, slot+500, 0); // slotを0で埋める
  int n;
  stream >> n;
  while ( n-- ) {
    int t_s, t_e;
    stream >> t_s >> t_e;
    while ( t_s != t_e ) { // 走ってる時刻のslotを+1する
      ++slot[t_s-1];
      ++t_s;
    }
  }
  int max_val = *max_element(slot, slot+500); // 最大値を求め、
  // 最大値であるslot# を出力する
  for ( int i = 0; i < 500; ++i ) {
    if ( slot[i] == max_val ) {
      cout << "time slot[" << i+1 << "] " << max_val << "runners" << endl;
    }
  }
}

Answer 5

n人の人を、開始時刻が早い順に並べ替えます。
現在人数のカウンタと、最大人数のカウンタを用意し、それぞれ0にセットします。
終了時刻のリストを用意します。
先頭の人から順に、以下を実行します。

その人の開始時刻と、リスト中の終了時刻一覧を比較します。終了時刻が先の人がいれば、現在人数のカウンタを減らし、その終了時刻をリストから抹消します。その後、その人の終了時刻をリストに加え、現在人数のカウンタを増やします。現在人数のカウンタが最大人数のカウンタを超えたら、最大人数のカウンタを増やします。

この日本語をC訳してください。

Comments

[jimbe]

c は分かっても c++ は分からないという方にリストというのはちょっと難易度が高いのではないかと思います.

[majiponi]

別に無理にリスト構造を使う必要はなくて、配列にして消すときに-1とか番兵で上書きすればいいし、そもそもCの教本にもリスト構造の説明はある(少なくとも私が読み耽った入門書には載ってた)。なければググればいい。工夫や調査をする能力を育てる機会を敢えて奪うのは、私としてはちょっと…。
ま、彼女のために検索のキーワードを書くなら、std::multisetってとこでしょうね。

Answer 6

#include <iostream>
using namespace std;

const int N = 5;  // 100 // 人数
const int T = 10; // 500 // 時刻

int solv(int n, int t_s[], int t_e[]) {
  int max_t = 0;
  int max_runner = 0;
  for (int t = 1; t <= T; t++) {
    int count_runner = 0; 
    for (int p = 0; p < n; p++) {
      if ((t_s[p] <= t) && (t <= t_e[p])) {
        count_runner++;
      }
    }
    if (count_runner > max_runner) {
      max_runner = count_runner;
      max_t = t;
    }
  }
  return max_runner;
}

int main(){
  int n;
  int t_s[N],t_e[N];

  cout << "input n:" << endl;
  cin >> n;
  for(int i = 0; i < n; i++) {
    cout << "input start and end:" << endl;
    cin >> t_s[i];
    cin >> t_e[i];
  }
  cout << "end of data" << endl;
  int max_n = solv(n, t_s, t_e);
  cout << max_n << endl;
  return 0;
}

Answer 7

構造体は使えますか？

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

struct Data {
	int time;
	int se;    // start:1, end:-1
};

int comp(const void *x, const void *y)
{
	return ((struct Data *)x)->time - ((struct Data *)y)->time;
}

int main()
{
	struct Data data[100 * 2];
	int n, k = 0;
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d%d", &data[k].time, &data[k+1].time);
		data[k].se = 1, data[k+1].se = -1, k += 2;
	}
	qsort(data, k, sizeof *data, comp);
	int m = 0, max = 0;
	for (int i = 0; i < k; i++)
		if ((m += data[i].se) > max) max = m;
	printf("%d\n", max);
}

入力
5
0 10
3 23
5 15
12 27
18 25

出力
3

時刻 0～3 は 1人
時刻 3～5 は 2人
時刻 5～10 は 3人
時刻 10～12 は 2人
時刻 12～15 は 3人
時刻 15～18 は 2人
時刻 18～23 は 3人
時刻 23～25 は 2人
時刻 25～27 は 1人

追記
バグがあったので、qsort に与える比較関数 comp を次のように訂正します。

int comp(const void *x, const void *y)
{
	int d = ((struct Data *)x)->time - ((struct Data *)y)->time;
	return d ? d : ((struct Data *)x)->se - ((struct Data *)y)->se;
}

どういうバグかというと、
2
10 20
20 30
このような入力があった場合、時刻20 において人が入れ替わるわけですが、
これを 2人が同時に走っていると解釈してしまうことがあるのです。
コードを見ればわかるように、この入力を data[] に
10 1
20 -1
20 1
30 -1
と取り込んだ後、ソートするのですが、qsort は安定ソートではないので
2つの同じ値 20 について、どちらが先になるかが決定していません。
10 1
20 1
20 -1
30 -1
となることがあるのです。安定ソートに変更しても、入力データが
ソートされているとは限りません。
そこで、今回の comp の変更になりました。