meumeu_yasuのブログ

競プロやってます。適当に自分の記録を。

JOI本選参加記

競プロ

JOI予選でギリギリAランク取れて本選行けたのでその時のことをメモ。

1日目

  • プラクティス

控室に行き周りを見る。

完璧に自分はぼっちだった。

何すればいいかわからずそのままプラクティスへ。

設定とかいじる。

マウスのホイールを下にやってるとたまに上にいきなり飛ぶ、多分Virtual Boxでマウス統合をしてないから。

スタッフの人にマウス統合していいか聞くがすぐにノーの返事。。。

矢印キーでの移動で我慢。

↓

  • 夜ご飯

バイキング形式で食べ放題だった。

自分はこのままぼっちかと思ったら話しかけてくれた人がいたので助かった(すごい感謝)。

自己紹介の時にたくさんのプロを見た。

↓

  • 宿舎へ

お風呂入るのぼっちは怖いからTwitterで誰か行こうといったら行ってくれた人がいた(圧倒的感謝)。

その後プロの部屋にお邪魔した。

あみだくじを見た瞬間やるだけと言って30分くらいで解いてて差を感じる＞＜

そして就寝。

2日目

  • 朝

朝に早起きしてJOI饅頭を解いた(2回目)。

30分くらいかけてしまった。

朝ごはんもTwitterのおかげでぼっちは回避。

そしてバスへ。

↓

  • 会場

会場について緊張してくる。

とりあえずTwitterで知り合ったプロと一緒にいた。

席について待機。

周りはマスコットとかお菓子とか持ってきてたので持ってくればよかった＞＜

本選前の10分とかやることなくてすごいもどかしい。

↓

  • 本選

まず1問目をみる。

ここで誤読、オレンジの順番を変えていいと思いソートをやりだす。

途中で気づいてやり直し。

1問目は1時間くらいかけてしまった。

クソ汚いコードを晒しあげておく(将来見た時に成長を感じそう？)。

1問目

とりあえず再帰を書いてメモ化。

#include <bits/stdc++.h>

using namespace std;

#define INF (1 << 30)
#define INFLL (1LL << 60)
#define ll long long

ll n,m,k;
ll a[20010] = {};
ll memo[20010];
ll rui[20010] = {};
int mina_s[20010][1010] = {};
int maxa_s[20010][1010] = {};

ll saiki(int now){
	if(memo[now] != INFLL) return memo[now];
	ll sum_mi = INFLL;
	for(int i = 1;i <= m;i++){
		if(now + i > n) break;
		ll b = 0,c = 0;
		ll maxa = 0,minb = INF;
		minb = a[mina_s[now+1][i-1]];
		maxa = a[maxa_s[now+1][i-1]];
		c = rui[now + i] - rui[now];
		b = saiki(now + i) + k + (i * (maxa - minb));
		sum_mi = min(sum_mi,b);
	}
	if(sum_mi == INFLL) sum_mi = 0;
	return memo[now] = sum_mi;
}

int main(){
	cin >> n >> m >> k;
	for(int i = 0;i < 20010;i++){
		memo[i] = INFLL;
	}
	for(int i = 1;i <= n;i++){
		cin >> a[i];
	}
	for(int i = 1;i <= n;i++){
		rui[i] = rui[i - 1] + a[i];
	}

	//a個からb個選んだ時の最小の大きさと最大の大きさを前処理
	for(int i = 1;i <= n;i++){
		int min_now = i;
		int max_now = i;
		for(int j = 0;j <= m;j++){
			if(i + j > 20010) break;
			if(a[min_now] > a[i + j]) min_now = i + j;
			mina_s[i][j] = min_now;
			if(a[max_now] < a[i + j]) max_now = i + j;
			maxa_s[i][j] = max_now;
		}
	}

	cout << saiki(0) << endl;

	return 0;
}

二問目(50点)

JとIは前後におくのが最適なのは自明、Oは全通り試した。
小問題3でTLEを出してしまい部分点だけ。
文字列からJOIの数を再帰で求めてたのが☓。

#include <bits/stdc++.h>

using namespace std;

#define INF (1 << 30)
#define INFLL (1LL << 60)
#define ll long long

int n;
string str;
ll memo[100010][4];

ll saiki(int now,int how){
	ll a = 0;
	if(now == n) return 0;
	if(memo[now][how] != INF) return memo[now][how];
	if(how == 0){
		if(str[now] == 'J') a += saiki(now + 1,how + 1);
		a += saiki(now + 1,how);
	}else if(how == 1){
		if(str[now] == 'O') a += saiki(now + 1,how + 1);
		a += saiki(now + 1,how);
	}else if(how == 2){
		if(str[now] == 'I') a += 1;
		a += saiki(now + 1,how);
	}
	return memo[now][how] = a;
}

void init(){
	for(int i = 0;i < 100010;i++){
		for(int j = 0;j < 4;j++){
			memo[i][j] = INF;
		}
	}
}

int main(){
	cin >> n >> str;
	ll ans = 0,num;
	string str2 = str;
	n++;
	str = "J" + str2;
	init();
	num = saiki(0,0);
	ans = max(ans,num);
	str = str2 + "I";
	init();
	num = saiki(0,0);
	ans = max(ans,num);
	init();
	str = "";

	for(int i = 0;i < str2.size();i++){
		for(int j = 0;j < i;j++){
			str += str2[j];
		}
		str += "O";
		for(int j = i;j < str2.size();j++){
			str += str2[j];
		}
		init();
		num = saiki(0,0);
		ans = max(num,ans);
		str = "";
	}

	cout << ans << endl;
	return 0;
}

1問と部分点しか出来なかった。。。

結構つらい。。。

2問目は家に帰ってから解き直してACした。

150点は流石にまずいと思ったのでこれから勉強の量も増やす。

来年こそ合宿に行ってやる！！