JOIとは何だったのだろうか


おはようございます(書いてるの午後四時くらい)JOIで1番の問題文読み間違えて60点落として240点(B)になった宗安です。地学とか絶対社会科やろ(錯乱)

advent calendar の存在を忘れていて遅れましたごめんなさい
今日は僕が現状解ける今年のJOIの4番までの解説まがいのものを即興でしたいなーと思います。言語は一応C++です。
5番以降はやらなくても通るらしいのと僕にはできないのと尺の都合でやりません。

問題1 科目選択 (Selecting Subjects)

JOI 君は物理,化学,生物,地学,歴史,地理の 6 科目のテストを受けた. それぞれのテストは 100 点満点で採点された.
JOI 君は物理,化学,生物,地学の 4 科目から 3 科目を選択し,歴史,地理の 2 科目から 1 科目を選択する.
テストの合計点が最も高くなるように科目を選ぶとき, JOI 君の選んだ科目のテストの合計点を求めよ.

日本語が読めればできる問題ですが、僕は日本語が読めなかったのでできませんでした。

地学を社会に含めるとこうなりました。

#include<stdio.h>
#include <algorithm>
#include <functional>
using namespace std;
int main (){
	int a[6];
	for(int i=0;i<6;i++){
		scanf("%d",&a[i]);
	}
	sort(a,a+3, greater<int>());
	sort(a+3,a+6, greater<int>());
	printf("%d\n",a[0]+a[1]+a[3]+a[4]);
	
	return 0;
}

実際には地学は理科に含まれるらしいのでこんな感じになります。

#include<stdio.h>
#include <algorithm>
#include <functional>
using namespace std;
int main (){
	int a[6];
	for(int i=0;i<6;i++){
		scanf("%d",&a[i]);
	}
	sort(a,a+2, greater<int>());
	sort(a+2,a+6, greater<int>());
	printf("%d\n",a[0]+a[2]+a[3]+a[4]);
	
	return 0;
}

それぞれの理科と社会をそれぞれソートして上位を足せば終わりです。

問題2 ゼッケンの交換 (Swapping Bibs)

JOI 高校の N 人の生徒が東西に一列に並んでいる.列の西の端から i 番目の生徒が生徒 i である.それぞれの生徒は整数が 1 つ書かれたゼッケンを付けている.
最初,生徒 i のゼッケンには整数 Ai が書かれている.
バトンが M 個あり,バトンには 1 から M までの番号が付けられている.
k = 1, 2, …, M に対し,以下の操作を行う.バトン k (2 ≦ k ≦ M) に関する操作は,バトン k – 1 に関する操作が終わってから行う.
先生がバトン k を生徒 1 に渡す.
バトンを受け取った生徒は,以下のルールに従ってバトンを渡す.
ルール:生徒 i がバトン k を受け取ったとする.
1 ≦ i ≦ N – 1 のとき: 生徒 i のゼッケンの整数を k で割った余りが,生徒 i + 1 のゼッケンの整数を k で割った余りよりも大きいとき,
生徒 i と生徒 i + 1 がゼッケンを交換し,生徒 i は生徒 i + 1 にバトンを渡す.そうでないときは,ゼッケンを交換せずに,生徒 i は生徒 i + 1 にバトンを渡す.
i = N のとき: 生徒 N はバトンを先生に渡す.
先生が生徒 N からバトン k を受け取ったら,バトン k に関する操作は終わりである.
生徒のゼッケンに最初に書かれていた整数とバトンの個数 M が与えられたとき,先生が生徒 N からバトン M を受け取った後の,それぞれの生徒のゼッケンの整数を求めるプログラムを作成せよ.

#include<stdio.h>
int main (){
	int a[100],n,m;
	scanf("%d%d\n",&n,&m);
	for(int i=0;i<n;i++){
		scanf("%d",&a[i]);
	}
	for(int i=1;i<=m;i++){
		for(int j=0;j<n-1;j++){
			if(a[j]%i>a[j+1]%i){
				int c=a[j];
				a[j]=a[j+1];
				a[j+1]=c;
			}
		}
	}
	for(int i=0;i<n;i++){
		printf("%d\n",a[i]);
	}
	return 0;
}

そのまま再現すればおk。
最後の人の時は何もしないってところ以外は気を付けるところはないかと思います。

問題3 ロシアの旗 (Russian Flag)

K 理事長はロシアで開催される IOI 2016 に合わせて旗を作ることにした.K 理事長はまず倉庫から古い旗を取り出してきた.
この旗は N 行 M 列のマス目に分けられていて,それぞれのマスには白・青・赤のいずれかの色が塗られている.
K 理事長はこの旗のいくつかのマスを塗り替えてロシアの旗にしようとしている.ただし,この問題でいうロシアの旗とは以下のようなものである.
上から何行か (1 行以上) のマスが全て白で塗られている.
続く何行か (1 行以上) のマスが全て青で塗られている.
それ以外の行 (1 行以上) のマスが全て赤で塗られている.
K 理事長が古い旗をロシアの旗にするために塗り替える必要のあるマスの個数の最小値を求めよ.

#include<stdio.h>

int n/*縦*/,m/*横*/,fc[50][3]/*0white 1blue 2red But it's not evangelion*/;
int min;
int main (){
	scanf("%d%d\n",&n,&m);
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			char c;
			scanf("%c",&c);
			if(c=='W'){
				fc[i][0]++;
			}else if(c=='B'){
				fc[i][1]++;
			}else{
				fc[i][2]++;
			}
		}
		scanf("\n");
	}
	min=10000;
	for(int i=1;i<n-1;i++){
		for(int j=i+1;j<n;j++){
			int num=0;
			for(int k=0;k<n;k++){
				if(k<i)num=num+m-fc[k][0];
				else if(k<j)num=num+m-fc[k][1];
				else num=num+m-fc[k][2];
			}
			if(num<min)min=num;
		}
	}
	printf("%d\n",min);
	return 0;
}

毎回すべてのマスをあたったとしても計算量はO(mn^3)で、今回はn<=50なので間に合いますが、n<=100とかになってくるとつらいので、 僕は各行にどの色がどれだけあるかをあらかじめ調べてから全探索するというやり方をしました。O(mn+n^2)

問題4

JOI 国には東西に走る 1 本の十分に長い道路がある.JOI 国の王宮が道路沿いにあり,JOI 国における道路沿いの位置は整数 A で表される.A = 0 のときは王宮の位置を表す.
A > 0 のときは,王宮から東へ A メートル進んだ位置を表す.A < 0 のときは,王宮から西へ -A メートル進んだ位置を表す. JOI 国の道路沿いには N 軒の家があり,家には西から順に 1 から N までの番号が付けられている.JOI 国には N 人の国民がいて,国民には 1 から N までの番号が付けられている. 家 i には国民 i が住んでいる.家 i の位置は 0 でない偶数 Ai で表される.A1, ..., AN は全て異なる. JOI 国では,近年国民の運動不足が問題になっている.国民の健康が気になった JOI 国の王様は,国民全員に散歩をする命令を出した. 王様が命令を出すと,全ての国民は一斉に東向きまたは西向きに歩き始める.それぞれの国民がどちらの向きに歩き始めるかは,国民ごとに決まっている.全ての国民は,歩くときは 1 秒あたり 1 メートルの速度で歩く. JOI 国の国民は皆おしゃべりが大好きである.散歩の途中にほかの国民に出会うと,その場所で立ち止まって世間話を始めてしまう. すでに立ち止まっている国民に出会った場合も同様である. 一度立ち止まった国民は,再び歩き出すことはない. JOI 国には Q 人の重要人物がいる.JOI 国の王様は,命令が出されてから T 秒後の,Q 人の重要人物の位置を把握しておきたい. 命令が出されてから T 秒後の,Q 人の重要人物の位置を求めるプログラムを作成せよ. [code language="cpp"] #include<stdio.h> long long int a[100000]/*家*/,d[100000]/*向き*/,stop[100000][2]/*位置、時間*/; int ever[100000]; long long int n,t,q,x[100000]; int main (){ scanf("%lld%lld%lld",&n,&t,&q); for(int i=0;i<n;i++){ scanf("%lld%lld",&a[i],&d[i]); if(d[i]==2&&d[i-1]==1){ stop[i][0]=(a[i]+a[i-1])/2; stop[i][1]=(a[i]-a[i-1])/2; stop[i-1][0]=(a[i]+a[i-1])/2; stop[i-1][1]=(a[i]-a[i-1])/2; ever[i]=1; ever[i-1]=1; } } if(d[0]==2){ ever[0]=1; stop[0][1]=2000000000000000000; } if(d[n-1]==1){ ever[n-1]=1; stop[n-1][1]=2000000000000000000; } for(int i=0;i<n;i++){ if(ever[i]==0){ if(d[i]==2){ stop[i][0]=stop[i-1][0]; stop[i][1]=a[i]-stop[i-1][0]; } } } for(int i=n-1;i>=0;i--){ if(ever[i]==0){ if(d[i]==1){ stop[i][0]=stop[i+1][0]; stop[i][1]=stop[i+1][0]-a[i]; } } } for(int i=0;i<q;i++){ scanf("%lld\n",&x[i]); int p=x[i]-1; if(t<stop[p][1]){ if(d[p]==1){ printf("%lld\n",a[p]+t); } if(d[p]==2){ printf("%lld\n",a[p]-t); } }else{ printf("%lld\n",stop[p][0]); } } return 0; } [/code] これは今日完成させました。 一人一人の止まる場所と時間を出せばよいことがわかります。 まず向かい合ってる人々を止めます。 つぎに右端で右向いてる場合や左端で左向いてる場合は止まる時間を十分大きく設定しています。 つぎにまだ止まっていない右向きの人を右端から順に見ていってすぐ右側の人が止まっている場所で止めます。 左向きも同様に左端から見ていきます。 出力は見たい時間が止まる時間より大きいかどうかで場合分けしています。

まとめ(というか感想)

今年は4番がでーぺーじゃなかったのでつらかったです。
来年は1番でミスしたりしたくないので日本語が読めるようになりたいと思います。
ところで明日から冬休みとかスキー講習が始まるので皆さん宿題とか頑張ってください(適当)
クリスマスまであと7日ですね。
尺の都合で今回はここまでです(次回はありませんが)それではみなさんさようなら。


コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です