第11回情オリ本選対策1日目

アリ本の2 - 5グラフのあたりをざらっと読んで、今まで避けていたベルマンフォード、ワーシャルフロイド、プリム、クラスカルを一応理解した。
2011年の過去問に手をつけてみて、あまりに解けなくて絶望。なんかもう根本的に思考力とかが足りていない感じもある。

そういえば本選の時の解説も僕の実力では何がなんだかさっぱり理解できなかった記憶があるけど、あまりそこから進歩していない感じ。本当に去年は勉強もせず練習もせず何してたんだろう…

問1は33分ぐらいかけた。解法分かってるのにカケスギィ!

#include <iostream>
#include <vector>
#include <string>
using namespace std;

class Explorer {
private:
	vector<string>& v;
	vector<vector<int> > jun, oce, ice;
public:
	Explorer(vector<string>& v) : v(v),
		jun(v.size() + 1, vector<int>(v[0].size() + 1, 0)),
		oce(v.size() + 1, vector<int>(v[0].size() + 1, 0)),
		ice(v.size() + 1, vector<int>(v[0].size() + 1, 0)) {}

	void createTableFor(char c, vector<vector<int> >& w) {
		for (int i = 0; i < v.size(); ++i)
		for (int j = 0; j < v[i].size(); ++j) {
			w[i + 1][j + 1] = w[i][j + 1]
					+ w[i + 1][j]
					- w[i][j]
					+ (v[i][j] == c ? 1 : 0);
		}
		return;
	}

	void createTable() {
		createTableFor('J', jun);
		createTableFor('O', oce);
		createTableFor('I', ice);
		return;
	}

	int getArea(int a, int b, int c, int d,
		vector<vector<int> >& w) {
		return w[c][d] - (w[a - 1][d] + w[c][b - 1]  - w[a - 1][b - 1]);
	}

	void query(int a, int b, int c, int d, int& j, int& o, int& i) {
		j = getArea(a, b, c, d, jun);
		o = getArea(a, b, c, d, oce);
		i = getArea(a, b, c, d, ice);
		return;
	}
};

int main()
{
	int M, N, K;
	cin>>M>>N>>K;

	vector<string> v(M);
	for (int i = 0; i < M; ++i)
		cin>>v[i];

	Explorer expl(v);
	expl.createTable();

	for (int i = 0; i < K; ++i) {
		int a, b, c, d;
		cin>>a>>b>>c>>d;

		int j, o, i_;
		expl.query(a, b, c, d, j, o, i_);
		cout<<j<<' '<<o<<' '<<i_<<'\n';
	}

	return 0;
}

あまりに解けなさすぎるので、とりあえず今週はアリ本のDP埋めとかを優先したほうがいいのかも。

約4時間