JOI予選参加記

4完大爆死


13:10分くらいに予選が始まってることに気づく。

問1
・やるだけ
・maxとか使う
・さすがに一瞬で解けた

この時点で13:17

問2
・やるだけ
・どっかでエンバグしてた気がする

エンバグして13:40。遅すぎﾜﾛﾀ

問3
・問題見て一瞬DPを疑う
・全然DPじゃなかった
・今いる座標から移動出来る方向はどの座標でも一緒
・単に座標の数字を足したり引いたりするだけ
・それが分かれば後はクソみたいな実装をするだけ

13:59。やるだけ問題は速い。それでも遅い。

問4
・典型的JOI予選DP
・普通にDPするだけ
・最初 int dp[1000][2][2][2] とかやろうと考えてしまったけどJ,O,Iをそれぞれビットでもって[1000][8]とかするほうがビット演算使えるし楽
・dp[i][j] = sum(dp[i-1][k]) (ただしj&k!=0)
・j&kが0で無ければ誰かしら被るので、その中の誰が鍵を持ってるとかは関係ない

14:37

問5
・すごくJOIっぽい問題
・多分ダイクストラ
・やるだけ
・やったこと無いから書けない
・死

問6
・多分普通のビットDP
・やるだけ
・問5が分からない時点でやる気が無くなった
・死

	// Q1----------------------------------------------------
	#include <iostream>
	#include <algorithm>
	using namespace std;
	int main() {
	int ans = 0;
	for(int i = 0; i < 5; i++) {
	int x;
	cin >> x;
	ans += max(40, x);
	}
	cout << ans / 5 << endl;
	}
	// Q2----------------------------------------------------
	#include <iostream>
	#include <vector>
	using namespace std;
	int main() {
	int N, M;
	cin >> N >> M;
	vector<int> A;
	vector<int> B(N, 0);
	while(N--) {
	int x;
	cin >> x;
	A.push_back(x);
	}
	while(M--) {
	int b;
	cin >> b;
	for(int i = 0; i < A.size(); i++) {
	if(A[i] <= b){
	B[i]++;
	break;
	}
	}
	}
	int ans = -1;
	int max = 0;
	for(int i = 0; i < B.size(); i++) {
	if(B[i] > max) {
	max = B[i];
	ans = i + 1;
	}
	}
	cout << ans << endl;
	}
	// Q3----------------------------------------------------
	#include <iostream>
	#include <queue>
	#include <utility>
	using namespace std;
	typedef pair<int,int> P;
	int main() {
	queue<P> que;
	int W, H, N;
	cin >> W >> H >> N;
	while(N--) {
	int x, y;
	cin >> x >> y;
	que.push(P(x,y));
	}
	int cx, cy;
	cx = que.front().first;
	cy = que.front().second;
	que.pop();
	long ans = 0;
	int nx, ny;
	while(!que.empty()) {
	nx = que.front().first;
	ny = que.front().second;
	que.pop();
	while(nx > cx && ny > cy) {
	ans++;
	cx++;
	cy++;
	}
	while(nx > cx) {
	ans++;
	cx++;
	}
	while(ny > cy) {
	ans++;
	cy++;
	}
	while(nx < cx && ny < cy) {
	ans++;
	cx--;
	cy--;
	}
	while(nx < cx) {
	ans++;
	cx--;
	}
	while(ny < cy) {
	ans++;
	cy--;
	}
	}
	cout << ans << endl;
	}
	// Q4----------------------------------------------------
	#include <iostream>
	#include <string>
	#include <map>
	using namespace std;
	const int J = 4;
	const int O = 2;
	const int I = 1;
	long dp[1001][8];
	int main() {
	map<char,int> m;
	m['J'] = J;
	m['O'] = O;
	m['I'] = I;
	int N;
	string str;
	cin >> N;
	cin >> str;
	switch(str[0]) {
	case 'J':
	dp[0][J] = dp[0][J+O] = dp[0][J+I] = dp[0][J+O+I] = 1;
	break;
	case 'O':
	dp[0][J+O] = dp[0][J+O+I] = 1;
	break;
	case 'I':
	dp[0][J+I] = dp[0][J+O+I] = 1;
	break;
	}
	for(int i = 1; i < N; i++) {
	auto c = m[str[i]];
	for(int j = 0; j < 8; j++) {
	if(!(j&c))
	continue;
	for(int k = 0; k < 8; k++) {
	if(j&k) {
	dp[i][j] += dp[i-1][k];
	}
	}
	dp[i][j] %= 10007;
	}
	}
	N--;
	int ans = 0;
	for(int i = 0; i < 8; i++) {
	ans += dp[N][i];
	}
	cout << ans % 10007 << endl;
	}

view raw JOI.cc hosted with ❤ by GitHub

結果：やるだけ問題出来なくてつらぽよ