0505,0516,0521,0522,0532,0533

JOI過去問で精進。
まだ簡単な問題ばっかだから貯まるね。うん。

0505

生徒の好きな場所を集計してソート。
同じ値の場合、昇順にしたいのでバブルソートしてあげます。

#include <cstdio>
#include <algorithm>
#include <map>
using namespace std;

int main() {
	int n,m,num;
	while (scanf("%d %d",&n,&m) && n != 0 && m != 0) {
		pair<int, int> place[m];
		for (int i=0; i<m; i++) {
			place[i].first = 0;
			place[i].second = i+1;
		}
		for (int i=0; i<n; i++) {
			for (int j=0; j<m; j++) {
				scanf("%d",&num);
				if (num == 1) place[j].first++;
			}
		}
		for (int i=0; i<m-1; i++) {
			for (int j=m-1; j>i; j--) {
				if (place[j].first>place[j-1].first) {
					swap(place[j], place[j-1]);
				}
			}
		}
		for (int i=0; i<m; i++) {
			if (i!=0) printf(" ");
			printf("%d",place[i].second);
		}
		printf("\n");
	}
}

0516

1~nまでのk個の部分和の最大を求める。
単純なループだとTLEになるから、最初の部分和だけ求めて、あとはズラしていく感じで。。

#include <cstdio>
#include <vector>
using namespace std;
int main() {
	int n, k;
	while (scanf("%d %d",&n,&k)&&n!=0) {
		vector<int> a(n);
		for (int i=0; i<n; i++) scanf("%d",&a[i]);
		int max=0;
		for (int i=0; i<k; i++) max+=a[i];
		int tmp=max;
		for (int i=0; i<n-k; i++) {
			tmp=tmp-a[i]+a[i+k];
			if (tmp>max) max=tmp;
		}
		printf("%d\n",max);
	}
}

0521

お釣りをもっとも少なくしたときの硬貨の枚数。
貪欲法で解く。

#include <cstdio>
using namespace std;
const int coin[] = {500,100,50,10,5,1};
int main() {
	int n;
	while (scanf("%d",&n)&&n!=0) {
		int res=0,turi=1000-n,m=0;
		while (turi!=0) {
			if (turi<coin[m]) {
				m++;
			} else {
				turi -= coin[m];
				res++;
			}
		}
		printf("%d\n",res);
	}
}

0522

文字列で部分文字列としての「JOI」と「IOI」の数を数える。
Straight Forward

#include <iostream>
using namespace std;
int main() {
	string str;
	while (cin>>str) {
		int joi=0,ioi=0;
		for (int i=0; i<str.length(); i++) {
			if (str[i]=='J'&&i+2<str.length()&&str[i+1]=='O'&&str[i+2]=='I') {
				joi++;
			} else if (str[i]=='I'&&i+2<str.length()&&str[i+1]=='O'&&str[i+2]=='I') {
				ioi++;
			}
		}
		cout << joi << endl;
		cout << ioi << endl;
	}
}

0532

三人の人の勤務時間を求める。

#include <iostream>
using namespace std;
int main() {
	for (int i=0; i<3; i++) {
		int h1,m1,s1,h2,m2,s2;
		cin>>h1>>m1>>s1>>h2>>m2>>s2;
		int s=s2-s1, m=m2-m1, h=h2-h1;
		if (s<0) {
			s+=60;
			m--;
		}
		if (m<0) {
			m+=60;
			h--;
		}
		cout << h << " " << m << " " << s << endl;
	}
}

0533

W大学とK大学の得点計算

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
#define REP(i,n) for (int i=0; i<(n); i++)
#define SORT(c) sort((c).begin(),(c).end())
typedef vector<int> vi;
int main() {
	vi W(10),K(10);
	REP(i,10) scanf("%d",&W[i]);
	REP(i,10) scanf("%d",&K[i]);
	SORT(W); SORT(K);
	int w=0,k=0;
	REP(i,3) w+=W[9-i];
	REP(i,3) k+=K[9-i];
	printf("%d %d\n",w,k);
}