P沼的プログラミング

PnumaSONの雑記

だらだら競プロ適当解説：AtCoder Beginner Contest 005

競技プログラミング

AtCoder Beginner Contestの第５回。

なんやかんやで月１くらいで解いている形になっているが、この調子だと年間１２コンテストしか解けないという恐ろしい事実である。私の能力が向上すれば効率は上がると思われるが、果たしてどうであろうか。おそらく年間１２コンテスト程度では大して上がらないだろうという予想ができる。
とはいえ増やすのはちょっと心持的にも時間的にも厳しいのでゆるくやっていく。

atcoder.jp

総評

AとBはいつも通りの入出力と分岐周りができればよい感じです。
Cは思考問題でDは知識問題の節が強い。
とはいえ、D問題は比較的典型的なデータ効率化の手法の延長上にあるため、データベースをガリガリ動かすようなデータサイエンティストよりの仕事をしている人やミリ秒単位のリアルタイム処理を扱う人にとっては障壁は高くなかったかもしれない。
ただし、一般的にこのようなデータ効率化手法や高速化手法は大学教育で習わないことが多いため、知識問題であって初手で解けなくても問題ないだろう。

適当解法

https://atcoder.jp/contests/abc005/submissions?f.User=pnumason


以下解説


A - おいしいたこ焼きの作り方

今持ってる小麦粉でタコ焼き何個作れるかい？ってね

略解
	int x,y;
	cin >> x >> y;
	// intを割ったら勝手に切り捨ての整数になるよ.
	cout << y / x << endl;
ポイント

一般的な算数の問題をプログラムにできればよい。
だいたいの言語では整数型(int)の場合、割った際の小数点以下は切り捨てになる。
型宣言がないタイプの場合は切り捨て用のceil関数の類を使えばよい。これはおおよその言語で標準実装されているはずである。

B - おいしいたこ焼きの食べ方

あったかいタコ焼きが食べたいんですよ

略解
	int N;
	cin >> N;
	int ret = 100;// Tのマックス値.
	for (int i = 0; i < N; i++)
	{
		int tmp;
		cin >> tmp;
		if (ret > tmp)
			ret = tmp;
	}

	cout << ret << endl;
ポイント

一番小さい値を得られればよいことはおそらくすぐにわかる。
実装方法については一般的なforとifでできるほか、ifの代わりにmin(x,y)を使うのも悪くない。
他にもソートして一番前を返すという方法もある。
そのあたりは慣れてきたら自由に選択すればよい。
気を付けるところがあるとすれば、retの初期値をTの最大値以上(100以上)にしておくことである。
うっかり初期化せずに０になっていると正しく動作しない。

C - おいしいたこ焼きの売り方

T秒以内のたこやきだけを売って客を満足させられるか。

略解
	cin >> T >> N;
	for (int i = 0; i < N; i++)
	{
		cin >> A[i];
	}
	cin >> M;
	for (int i = 0; i < M; i++)
	{
		cin >> B[i];
	}
 
	int index = 0;
	int ret = true;
	for (int i = 0; i < M; i++)
	{
		if (index >= N)
		{
			// タコ焼きはもうない.
			ret = false;
			break;
		}
 
		if (A[index] > B[i])
		{
			// 客iに出せるタコ焼きがもうない.
			ret = false;
			break;
		}
 
		if ( A[index] + T < B[i])
		{
			//このタコ焼きでは冷めている.
			index++;
			i--;//この書き方は正直あまりお行儀が良くない.
			continue;
		}
		else
		{
			// Aindexのものを渡しました.
			index++;
		}
	}
 
	if (ret)
	{
		cout << "yes" << endl;
	}
	else
	{
		cout << "no" << endl;
	}
ポイント

ポイントは「T秒以内に焼きあがったものしか売れない」という部分を念頭に入れること、そして「全員に売れるか否かだけ考えればよい」ことをまず理解することである。
これは結果的にタコ焼きと客のどっちを軸にしてforを回すかというのを問題文から理解するということである。
客が満足すればよいということはタコ焼き側に着目する必要はないということで、これは客側に着目し、来た客来た客さばいていき渡せなくなったらお終いということである。つまるところタコ焼きが１００個余ろうが１０００個余ろうがどうでもよいことを示している。
今回はタコ焼きも客もデータはソートされているのでそのまま処理できるのでさっそく処理していく。
さて、では来た客をさばいていこう。まず客B1がやってくる。彼はT秒以内のタコ焼きしか渡せない。
つまりタコ焼きをA1から順に古い順に見ていき、T秒以内のものがあればそれを渡せばよい。T秒以内のものがなかったり、もう渡せるタコ焼きがなかったりした場合はその時点で客は不満足なので答えはnoになる。
こうやって前から順に古い物から順に渡していき皆に渡せればyesと返す問題である。


前詰めで大丈夫な根拠を簡単に挙げておくと　冷めていて先の人に渡せないものはあとの人にももちろん冷めていて渡せないからである。
問題文から読み解いて要するにA<＝B<=A+Tのもののみ渡せる。
まずA[i]＋T＜B[j]で渡せないの場合、B[j]＜B[j＋1]のため必ずA[i]＋T＜B[j＋1]である。つまり後の人にそれは渡せない。

次にA[i]＞B[j]の場合、前から処理していった結果でこのA[i]が来た時点で客B[j]に売れないことが確定する。なぜならソートされている以上任意のxに関して、A[i＋x]＞＝A[i]であってつまりA[i＋x]＞B[j]だからである。


まあこのような御託を並べずともなんとなく直感的に賞味期限の近い物から渡した方が効率よかろうみたいなことでよい気もする。


ちなみにスコアリングされ、より出来立てのほうがスコアが高く、最高スコアを返せみたいな問題になった時は、前からではなく後ろから貪欲に処理すればいい（はず）である。
理由は上記とほぼ同様である。

D - おいしいたこ焼きの焼き方

タコ焼きの盤と美味しさの値が入ってくるので一番おいしい場所で焼く。
四角形でしか焼けないという制約があるので注意。

略解
// グローバルは勘弁してください先生.
int N;
int D[50][50];
int DSum[50][50];// 累積和.行ごとに初期化する.
int DSquare[50][50];//左上からその点までの四角形のSum.
int Q;
int P[2500];
int MaxP;// 最大の約面積.
int MaxScore[2501];// 面積Xの時の最大のスコア.

/// <summary>
/// タコ焼き機を任意の長方形で全探索する.
/// </summary>
/// <param name="w">横幅</param>
/// <param name="h">縦幅</param>
/// <returns>最良の合計スコア</returns>
int search(int w, int h)
{
	int maxD = 0;
	//(i,j)を左上とした長方形を計算する.
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			//左上 右上 左下 右下.
			int y[4], x[4];
			y[0] = i;			x[0] = j;
			y[1] = i;			x[1] = j + w - 1;
			y[2] = i + h - 1;	x[2] = j;
			y[3] = i + h - 1;	x[3] = j + w - 1;

			// はみ出てたら無理.
			if (y[3] >= N || x[3] >= N)
				continue;


			// いちばんでっけえ四角から辺に接する四角を引いて
			// ちっせえ四角を足す.
			//□□□□　　　■■■■　　　■■□□　　　■■■■　　　■■□□
			//□□■■　＝　■■■■　ー　■■□□　ー　□□□□　＋　□□□□
			//□□■■　　　■■■■　　　■■□□　　　□□□□　　　□□□□

			int score = DSquare[y[3]][x[3]];
			if (x[2] - 1 >= 0)
			{
				score -= DSquare[y[2]][x[2] - 1];
			}
			if (y[1] - 1 >= 0)
			{
				score -= DSquare[y[1] - 1][x[1]];
			}
			if (x[0] - 1 >= 0 && y[0] - 1 >= 0)
			{
				score += DSquare[y[0] - 1][x[0] - 1];
			}

			maxD = max(maxD, score);
		}
	}

	return maxD;
}


int main(){
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			cin >> D[i][j];

			// 累積和を取るよ.行が変われば初期化.
			if (j != 0)
			{
				DSum[i][j] = DSum[i][j - 1] + D[i][j];
			}
			else
			{
				DSum[i][j] = D[i][j];
			}
		}
	}

	cin >> Q;//人数.

	MaxP = 0;
	for (int i = 0; i < Q; i++)
	{
		cin >> P[i];
		MaxP = max(MaxP, P[i]);
	}

	// 初期化.
	for (int i = 0; i <= MaxP; i++)
	{
		MaxScore[i] = 0;
	}

	// 行ごとの累積和から四角情報に変換する.
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			if (i == 0)
			{
				// 一行目は行毎累積和と同一になるはず.
				DSquare[i][j] = DSum[i][j];
			}
			else
			{
				// 二行目以降は一つ上の四角情報＋行毎累積和.
				DSquare[i][j] = DSquare[i - 1][j] + DSum[i][j];
			}

		}
	}


	// 最大でも１辺はN以下.
	int MaxLength = min(MaxP, N);

	for (int h = 1; h <= MaxLength; h++)
	{
		for (int w = h; w <= MaxLength; w++)
		{
			// 面積MaxP以下の長方形(i<=j)
			if (h * w <= MaxP)
			{
				//i*jで探索する.
				int score = search(w, h);
				//j*iで探索する.正方形ならいらない.
				if (h != w)
				{
					int score2 = search(h, w);
					score = max(score, score2);
				}
				if (MaxScore[w * h] < score)
				{
					MaxScore[w * h] = score;
				}
			}
		}
	}

	//マックススコアの計算し直し.(Pが3より2のほうが上のことあるので)
	{
		int tmpmax = 0;
		for (int i = 0; i <= MaxP; i++)
		{
			MaxScore[i] = max(tmpmax, MaxScore[i]);
			tmpmax = MaxScore[i];
		}

	}

	// Q人分出力する.
	for (int i = 0; i < Q; i++)
	{
		cout << MaxScore[P[i]] << endl;
	}
ポイント

計算量から考えていくとN=50なので１秒に10,000,000回理論によるとN^4の6,250,000くらいまでで処理しなければいけないことが分かる。
まず最高の値の四角形を探すにはどうあがいても全探索するほかないことに気づく必要がある。計算量的にもN=50というところが全探索系の問題っぽさを醸し出している。
さて、四角形をどうやって全探索するかという話になるが、まずは四角形の縦幅と横幅でfor文を回すというのが直感的にもよいだろう。これでN^2である。
それからあるポイントx,yを左上とした四角形として計算する。これでN^4である。
ここでさらに四角形の値の計算で横にw回と縦にh回のfor文を組んでしまうともうN^6になってしまうのでどうしようもない。

// 四角形を大きさの全通り.
for (int h = 1; h <= N; h++)
{
	for (int w = 1; w <= N; w++)
	{
		// 四角形の起点(左上の点)を全通り.
		for(int y = 0; y < N; y++)
		{
			for(int x = 0; x < N; x++)
			{
				//さらにここで四角内の値を足し算する.
				for(int i = 0; i < h; i++)
				{
					for(int j = 0; j < w; j++)
					{
						//加算処理.
					}


どこかを省く必要がある。こういう時によく出てくるのが累積和である。
累積和というのはデータの効率の良い保持方法のひとつで12321とデータがあったとしたら前の値と足す形で13689というデータを持つ。
こうすると何がいいかというと、２番目から５番目までの和を出したかったら通常は2+3+2+1をする必要があるところ9-1という形で求まる。
これは配列の要素数が少ないうちは大したことがないが、要素数が多いあるいは繰り返すときにはかなり効いてくる。
今回も直接的な累積和ではないが、こんな感じでデータの持ち方を工夫することで簡単な加算減算で表せると計算量を抑えれる。


今回の四角の計算もどうにかならないかと考えると、任意の四角領域の総和は左上を起点とした四角領域の総和の加減算で表せることがわかる。
ソースのsearch関数の記載を確認してください。
そのため、四角形の総和情報が作れれば四角形の値の計算のN^2は省けるのでちょうどN^4で解けることになる。
左上起点の四角総和情報の作成方法はどうやってもいいが、ここでN^4を超えてしまったら本末転倒である。
普通に愚直に足し算をしてもN^4で収まるのだが、ここではせっかくなので累積和を使ってみよう。
四角形の総和を求めたいという需要と総和という点でマッチしているのでちょうどいいはずである。
累積和を一行ごとにとっておくと上記のソースのようにかなり簡単に左上起点の四角形の総和が求まる。
四角形の総和のデータが求まったらあとは全探索するだけである。


そのほかちょっとしたポイントとして、５個焼けるときも５個焼くより４個焼く方がスコアが高いことがあるのでそれをmaxを使って計算することやQ人それぞれ計算するのではなく、たった一度だけ四角情報を計算することなどがあるが、共有可能な情報であることを考えれば自然な発想である。


この問題に限らずすべてにあてはまることであるが、
for内に入れ子にせずに外に出せそうな部分は外に出す：四角情報の作成と実際の計算の作成を別のforループでやる
共有できる情報は１度だけ作成する：四角情報やそれぞれの焼ける個数のスコア情報はすべての店員で共有可能である。
といったことを念頭に入れて計算量を削減していくと良いと思う。

だらだら配信

どんな感じの思考で解法に至ったのか知りたい稀有な人用。

https://youtu.be/hUmZRzKWjwk
https://youtu.be/NryqwNlJ-HM
https://youtu.be/TARV8PPqYO4