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

AtCoder Beginner Contestの第8回。

月一更新のために無理やり途中で投稿しちゃう奴。

atcoder.jp

総評

前回同様全体的に難しくなっているような。
C、D問題の100点解法は青レベルなのでABCerには難しすぎるのではないか。
という気持ちもあるが、要するにそもそも部分点が己の力量と照らし合わせれば実質満点と思えばまあ食らいつけなくはない。
でもなんか、99点って言われると複雑な気持ちにはなる。
A、Bはほぼいつも通り。Bはほんの少し難し目かもしれない。
CとDの100点は難易度高いのでスルーしてもいいかも。
C、Dの詳しい解説や総評については後日追加予定。

満点解法を追記しました。 (2020/12/12)

適当解法

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

以下解説

A - アルバム

続・ありがちなA問題。

略解

	cin >> S >> T;

	cout << T - S + 1 << endl;

ポイント

SからTまでの枚数をカウントすればいい。
境界部分のSとTを含めるかどうかを気を付ければ解けるはず。
1000枚程度なのでforで回して数えたとしても無駄は多いが解ける。

B - 投票

要するに多数決。
本当にそれは多数決で決めていいのか！(問題無視)

略解

	// 名前と得票数のペア.
	pair<string, int> Mans[50];
	int Count = 0;//投票される人数の記憶用.
	int N;// 組織の人数.

	// Mansの初期化.
	for (int i = 0; i < 50; i++)
	{
		Mans[i].first = "";
		Mans[i].second = 0;
	}


	cin >> N;
	for (int i = 0; i < N; i++)
	{
		string S;
		cin >> S;
		bool IsExist = false;
		for (int i = 0; i < Count; i++)
		{
			if (Mans[i].first == S)
			{
				Mans[i].second++;
				IsExist = true;
				break;
			}
		}
		if (!IsExist)
		{
			Mans[Count].first = S;
			Mans[Count].second = 1;
			Count++;
		}

	}

	// もっとも高いものを確認する.
	{
		int BestScore = 0;
		string BestName = "";
		for (int i = 0; i < Count; i++)
		{
			if (Mans[i].second > BestScore)
			{
				BestScore = Mans[i].second;
				BestName = Mans[i].first;
			}
		}

		cout << BestName << endl;
	}

ポイント

名前と出現回数をペアでもっておくと楽。もちろんバラで配列を二つにしてもよい。
ペアにする利点はその気になったら出現数でソートすればいちいち自前で実装しなくてもすぐに最大が求められること。
たかだか５０人なので毎回既存のリストと見比べてすでにいるかどうか確認しても問題ない。

全部一度入力してから確認追加という流れより、入力しながら確認追加のほうがメモリ的のも速度的にも効率が良い。
業務的にはXMLやHTMLみたいな形式をまるごと読み込むとメモリが爆発するが、タグごとに読み出せばメモリの使用量もすごい少ない。(もちろん仮想読みしてタグごとに読み出せるような関数を使えばの話だが)
規模が大きくなると影響力が大きくなるので複雑になり過ぎない範囲なら入力とデータ整形は同時に行った方がいい。

C - コイン

わかりそうでわからない、とけそうでとけない。
なんかありがちな問題な気がするんだけどな。

部分点解法

	int N;// コインの数.
	int C[100];// コインの数字.
	bool IsFront[100];// 表裏.
	int sum = 0;// 表の数の合計.
	int setnum = 0;// 順列組み合わせの数.

	cin >> N;
	for (int i = 0; i < N; i++)
	{
		cin >> C[i];
	}
	
	// next_permutationのために辞書順にする.
	sort(C, C + N);

	// 部分点 実際に実行してみる.
	do{
		// 組み合わせ数をカウント.
		setnum++;

		for (int i = 0; i < N; i++)
		{
			// 初めはみんな表.
			IsFront[i] = true;
		}

		// あるコイン列の時の実際の操作.
		for (int i = 0; i < N; i++)
		{
			for (int j = i + 1; j < N; j++)
			{
				// 倍数ってことはあまりが0ってこと.
				if (C[j] % C[i] == 0)
				{
					// 表裏反転.
					IsFront[j] = !IsFront[j];
				}
			}
		}

		// 表の数をカウント.
		for (int i = 0; i < N; i++)
		{
			if (IsFront[i])
			{
				sum++;
			}
		}

		// 次のコイン列に.
	} while (next_permutation(C, C + N));


	cout << std::fixed << std::setprecision(10) << sum / (double)setnum << endl;

部分点解法のポイント

部分点はN<=8なのですべてのパターンを数え上げられれば部分点である99点が得られる。
ここでのポイントはnext_permutation()という関数で、これを知らないとおそらくかなりしんどかったのではと思う。
next_permutation()は要するに辞書順で次になる順列を返してくれるというものである。
元が123ならnext_permutation()は132になる。
辞書的に最後である321までいくとfalseが返る。
こういった仕様なので、正しく利用するためには初めに配列をソートをしておく必要がある。
これができれば全パターンのコイン順が分かるのであとは律義に操作して表の数を数えるだけだ。

next_permutation()を知らない場合は真面目に順列を組んでもいいが、新たに必要となる知識が少なくて済むため再帰関数を利用するのがよいかと思う。
配列から一つ取り出し、新たな配列に足すというのを繰り返す。その際に既に使ったものは-1等入れて削っておく。
面倒なのは113のように同じ数字が複数あるときだ。
これは事前にソートしておき、自分より上の同数を選んではいけないという制約を課せばおそらくできるがちょっとわかりにくい。
113ならそれぞれを1A-1B-3とすると、まず1A-1B-3、1A-3-1B、3-1A-1Bはいいとして、1B-1A-3はダメということだ。
1Bが選択されるより先に必ず1Aが選択されていなければいけないと言い換えることもできるだろう。これは選択済み情報配列を適切に管理できれば可能なはずだ。

とはいえnext_permutation()という極めて優しい関数が実在するのだから頭を悩ませる必要はない。ここで覚えておいて次からはこれを利用しよう。

満点解法

	int N;// コインの数.
	int C[100];// コインの数字.
	int Yaku[100];// あるコインiの約数の数.
	double Sum = 0;

	cin >> N;
	for (int i = 0; i < N; i++)
	{
		cin >> C[i];
		Yaku[i] = 0;// ついでに初期化.
	}

	// コインの約数の数を数える.
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			// 自分は数に入れない.
			if (i == j)
				continue;

			// 余りが0なら約数.
			if (C[i] % C[j] == 0)
			{
				Yaku[i]++;
			}
		}
	}

	// 確率を求める.
	for (int i = 0; i < N; i++)
	{
		if (Yaku[i] % 2 == 0)
		{
			Sum += (Yaku[i] + 2.0f) / (2.0f * Yaku[i] + 2.0f);
		}
		else
		{
			Sum += 0.5f;
		}
	}

	cout << std::fixed << std::setprecision(10) << Sum << endl;

満点解法のポイント

期待値の求め方は一般的に(全通りの際の表の数の総和)/(通り数)で求まるが、それを(ある条件下での表の数)/(全通り) +(ある条件下での表の数)/(全通り) +……に変換できるかという部分である。
確率の問題なので正直個人的には苦手で、高校レベルでも思いつける知識的難度ではあるが、大学レベルでもあまりこの発想に至らないかもしれない。
あるコイン１枚に注目して、そのコインが表になる数を求め、それを足し合わせるという形で実装する。
あるコインCiの約数となるコインの数Yiを事前に求めておき、約数の数から自分が表になる確率を求めることになる。
この問題ではコインの向きが関係するのはYiによってのみであり、それ以外のコインの影響は一切受けない。
このことから、注目しているコインCiの左右に何個約数にあたるコインがあるかというのを総当たりすれば全通りが求まる。
つまり、
約数の数が偶数の場合、表になるようなコインCiの位置は１、３、５……番目となるため
( (1個とばしの場所の数 = Ciが表になる場所の数) (約数の全通り)) / (全通りの数)
= ( (Yi / 2 + 1) (Yi!) )/ (Yi +1)! = (Yi + 2) / (2Yi + 2)　となる。
奇数の場合は、２、４、６……番目となるため
( (1個とばしの場所の数 = Ciが表になる場所の数) (約数の全通り) ) / (全通りの数)
= ( ( (Yi + 1) / 2) ( Yi! ) )/ ( Yi +1 )! = 1 / 2　となる。

ここで約数コイン以外の部分を完全に無視しているが、あるコインCiに着目した際の (Ciの表の数) / N! は
先の式の分母分子に、考慮しなかったすべてのコインの総当たり数である ( N! / ( Yi + 1 ) ) をかけるに過ぎない。
約数以外の部分のコインは全通りいずれでも表の確率に影響しないため結果的に打ち消されることになる。

コインCiについて求まったら他のiについても同様に計算し、総和を取れば期待値が求まることになる。

D - 金塊ゲーム

部分点なら比較的簡単、満点解法も競プロ慣れしている人ならそこそこ簡単に解けたのかもしれない。
どうやって情報を簡略化するかみたいなところがミソ。

80点解法

// マシーンの情報.
class Machine
{
public:
	pair<int, int> pos;//機械の位置.
	int boundary[4];//上下左右の金塊が途切れる位置.

	void Init(int x, int y, int w, int h)
	{
		pos.first = x;
		pos.second = y;
 
		boundary[0] = h + 1;//上.
		boundary[1] = 0;	//下.
		boundary[2] = 0;	//左.
		boundary[3] = w + 1;//右.
	}
	/// <summary>
	/// 金塊取集行動をする.
	/// </summary>
	/// <returns>手に入れた金塊の数</returns>
	int GetGold()
	{
		// 上下左右の境界部分までが金塊の数よ.
		int gold = 0;
		for (int i = 0; i < 2; i++)
		{
			gold += abs(boundary[i] - pos.second) - 1;//上下.
		}
		for (int i = 2; i < 4; i++)
		{
			gold += abs(boundary[i] - pos.first) - 1;//左右.
		}
 
		// 最後に自分の真下.
		gold += 1;
 
		return gold;
	}
 
	/// <summary>
	/// あるマシーンが作動した場合の境界の変化.
	/// </summary>
	/// <param name="m">マシーン</param>
	void ChangeBoundary(Machine m)
	{
 
		// 縦方向の変更.
		{
			// 変化領域内にあるか.
			if (m.boundary[2] < pos.first && m.boundary[3] > pos.first)
			{
				// 上にある場合.
				if (m.pos.second > pos.second)
				{
					boundary[0] = min(boundary[0], m.pos.second);//上.
				}
				else
				{
					boundary[1] = max(boundary[1], m.pos.second);//下.
				}
			}
		}
 
		// 横方向の変更.
		{
			if (m.boundary[1] < pos.second && m.boundary[0] > pos.second)
			{
				// 右にある場合.
				if (m.pos.first > pos.first)
				{
					boundary[3] = min(boundary[3], m.pos.first);//右.
				}
				else
				{
					boundary[2] = max(boundary[2], m.pos.first);//左.
				}
			}
		}
	}
};
 
int main(){
	int W, H;// 金塊の領域.
	int N;// マシンの個数.
 
	Machine M[30];
 
	cin >> W >> H;
	cin >> N;
 
	for (int i = 0; i < N; i++)
	{
		int x, y;
		cin >> x >> y;
		M[i].Init(x, y, W, H);
 
	}
 
	// 80点解法　全探索.
	{
		// C問題同様 next_permutationつかえば？
		int list[30];
		for (int i = 0; i < N; i++)
		{
			list[i] = i;
		}
 
		int Max = 0;
		//順列にある順でマシンを動かす.
		do{
			int sum = 0;
			Machine tmpM[30];
			memcpy(tmpM, M, sizeof(M));
 
			// それぞれのマシーンを実行.
			for (int i = 0; i < N; i++)
			{
				sum += tmpM[list[i]].GetGold();
 
				// 残りのマシーンの境界情報を更新.
				for (int j = i + 1; j < N; j++)
				{
					tmpM[list[j]].ChangeBoundary(tmpM[list[i]]);
				}
			}
 
			Max = max(Max, sum);
 
		} while (next_permutation(list, list + N));
 
		cout << Max << endl;
 
	}
	return 0;
}

80点解法のポイント

どういう形で実装するにしても全探索を行えばよい。80点解法ではN=8とかなり小さいため大体どのような手法を取っても間に合うだろう。
上記のコードでは、全探索部分はnext_permutationを利用してすべての順序パターンでマシーンを動かすという処理を取った。マシーンを動かしたときの金塊回収の処理や、地図情報修正の処理はマシーン側で保持しているが、WH=80とこちらも小さいため地図配列を作成し、逐次金塊回収処理を回してもよいと思う。

満点解法

// ある長方形の最大スコアのメモ.
ll memo[32][32][32][32];
int W, H;// 金塊の領域.
int N;// マシンの個数.

Machine M[32];// 大元のマシン情報. 入力したら絶対変更しない.


/// <summary>
/// 長方形領域の最大得点を求めるDP.
/// </summary>
/// <param name="M">マシンの状態</param>
/// <param name="m1">左上のXにあたるマシンID</param>
/// <param name="m2">左上のYにあたるマシンID</param>
/// <param name="m3">右下のXにあたるマシンID</param>
/// <param name="m4">右下のYにあたるマシンID</param>
ll DP(vector<Machine> vM, int m1, int m2, int m3, int m4)
{
	ll bestsum = 0;

	// あるマシンiを動かして領域を分割する.
	for (int i = 0; i < vM.size(); i++)
	{
		vector<Machine> tmpvM = vM;// 一時記憶用.
		ll sum = 0;

		// 領域のサイズから金塊の数は求まる.
		sum += (M[m3].pos.first - M[m1].pos.first + M[m2].pos.second - M[m4].pos.second - 3);

		// 分割それぞれの領域のマシン.
		vector<Machine> vDivM[4];// 左上、右上、右下、左下.

		// 領域分割.
		for (int j = 0; j < tmpvM.size(); j++)
		{
			if (j != i)
			{
				if (tmpvM.at(j).pos.second > tmpvM.at(i).pos.second)
				{
					if (tmpvM.at(j).pos.first < tmpvM.at(i).pos.first)
					{
						vDivM[0].push_back(tmpvM.at(j));// 左上.
					}
					else
					{
						vDivM[1].push_back(tmpvM.at(j));// 右上.
					}
				}
				else
				{
					if (tmpvM.at(j).pos.first > tmpvM.at(i).pos.first)
					{
						vDivM[2].push_back(tmpvM.at(j));// 右下.
					}
					else
					{
						vDivM[3].push_back(tmpvM.at(j));// 左下.
					}
				}
			}
		}


		// 分けたマシンをそれぞれ関数に投げる.
		{// 左上.
			if (memo[m1][m2][tmpvM.at(i).id][tmpvM.at(i).id] == UNREACHED)
			{
				sum += DP(vDivM[0], m1, m2, tmpvM.at(i).id, tmpvM.at(i).id);				
			}
			else
			{
				sum += memo[m1][m2][tmpvM.at(i).id][tmpvM.at(i).id];
			}
		}
		{// 右上.
			if (memo[tmpvM.at(i).id][m2][m3][tmpvM.at(i).id] == UNREACHED)
			{
				sum += DP(vDivM[1], tmpvM.at(i).id, m2, m3, tmpvM.at(i).id);
			}
			else
			{
				sum += memo[tmpvM.at(i).id][m2][m3][tmpvM.at(i).id];
			}
		}
		{// 右下.
			if (memo[tmpvM.at(i).id][tmpvM.at(i).id][m3][m4] == UNREACHED)
			{
				sum += DP(vDivM[2], tmpvM.at(i).id, tmpvM.at(i).id, m3, m4);
			}
			else
			{
				sum += memo[tmpvM.at(i).id][tmpvM.at(i).id][m3][m4];
			}
		}
		{// 左下.
			if (memo[m1][tmpvM.at(i).id][tmpvM.at(i).id][m4] == UNREACHED)
			{
				sum += DP(vDivM[3], m1, tmpvM.at(i).id, tmpvM.at(i).id, m4);
			}
			else
			{
				sum += memo[m1][tmpvM.at(i).id][tmpvM.at(i).id][m4];
			}
		}


		// ベストsumと比べて良ければそれが今回回すべきマシンということよ.
		if (bestsum < sum)
		{
			bestsum = sum;
		}
	}

	// ベスト値の更新 = メモの更新.
	memo[m1][m2][m3][m4] = bestsum;
	return memo[m1][m2][m3][m4];
}



int main(){
	cin >> W >> H;
	cin >> N;

	for (int i = 0; i < N; i++)
	{
		int x, y;
		cin >> x >> y;

		M[i].Init(x, y, W, H, i);

	}

	// 満点解法.
	{
		vector<Machine> vMachine;

		// マシーン情報をベクタに詰め直す.
		for (int i = 0; i < N; i++)
		{
			vMachine.push_back(M[i]);
		}

		// memo初期化.
		for (int i = 0; i < 32; i++)
		{
			for (int j = 0; j < 32; j++)
			{
				for (int k = 0; k < 32; k++)
				{
					for (int l = 0; l < 32; l++)
					{
						memo[i][j][k][l] = UNREACHED;
					}
				}
			}
		}

		// 境界領域用ダミーマシン.
		M[30].Init(0, H + 1, W, H, 30);// 左上境界.
		M[31].Init(W + 1, 0, W, H, 31);// 右下境界.

		// 最終的に求めたい長方形領域は
		// 左上30番のxy、右下31番のxyの一回り小さい領域.
		ll ans = DP(vMachine, 30, 30, 31, 31);

		cout << ans << endl;
	}

	return 0;
}

満点解法のポイント

いわゆる動的計画法によって問題を解くことになる。この際に、動的計画法の引数として矩形情報として処理してしまうとWHが大きくなった時にメモ配列が大きくなりすぎてメモリ不足で対応できなくなってしまう。そのため、矩形が切られるのは必ずマシンの位置ということに着目してマシンIDでメモ情報を持つという風にして対応すればよい。マシン数はたがだか30であり、初めの矩形用にダミーのマシンを２つ追加しても32個である。32^4=1,048,576であり、このメモリ量なら十分確保でき、計算量的にも間に合いそうなことが分かる。
計算方法は単にあるマシンを動かして金塊を得る→領域分割する→分割先の再帰関数を4つ回す→最大ならメモ更新　といった流れだ。かなり一般的なDPの流れなので基礎からひとつひとつ確かめて実装しよう。
今回はvectorでマシン情報を直接引数で渡したが、マシンIDだけにすることや、参照値のみで操作することでメモリの使用量の削減や高速化が見込める。
余力がある場合はいろいろ試してどれほど実行速度やメモリ使用量が変わるか確かめてみるのもいいだろう。(私はもう面倒なのでやらない)

だらだら配信

長いので割愛