P沼的プログラミング

PnumaSONの雑記

だらだら競プロ適当解説:AtCoder Beginner Contest 009

AtCoder Beginner Contestの第9回。

だいぶ昔に終わっていたのにブログ書いてなかった奴。

atcoder.jp


総評

A、Bはいつも通り。
Cは問題文にあるように少し難しめ。
とはいえソートがお手てで組めればおそらく実装可能だ。
完全にソート関数に依存して実装を理解していないと辛いかもしれない。
Dは数学がお得意でないと難しそうといった印象。

A - 引越し作業

特に必要な能力はなさそう。入出力ができてプログラム特有の余りの概念が分かれば大丈夫かな。

略解
	cin >> N;

	cout << (N + 1 )/ 2 << endl;
ポイント

同時に2個まで運べるので単純に荷物を2で割ればよい。奇数のあまり分はあとでN%2で足すか、初めからN+1を割ることで対応しよう。

B - 心配性な富豪、ファミリーレストランに行く。

2番目に高いものを買うのは果たして庶民なのか

略解
	int N;
	int A[100];
 
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		cin >> A[i];
	}
 
	sort(A, A + N);
 
	for (int i = N - 2; i >= 0; i--)
	{
		if (A[N - 1] != A[i])
		{
			cout << A[i] << endl;
			break;
		}
	}
ポイント

2番目というのだからとりあえずソートして順番に並べてしまおう。
そして高い順に確認して2番目を出力すればよい。一番高いものと次のものを比べて価格が異なればそれが二番目のものだ。

C - 辞書式順序ふたたび

ちょっとめんどくさいソートの実装。

略解
// 文字の差確認.
int Checkdiff(string &A, string &B)
{
	int count = 0;
	// ほんとはサイズもいれなあかんで.
	for (int i = 0; i < A.size(); i++)
	{
		if (A.at(i) != B.at(i))
			count++;
	}
	return count;
}
 
int main(){	
 
	//while (true)
	{
		int N, K;
		string S;
 
		cin >> N >> K;
		cin >> S;
 
		string Ssort = S; // ソートしたやつ.
		string Sorigin = S; // 元のやつ.
		sort(Ssort.begin(), Ssort.end());
 
 
		for (int i = 0; i < N; i++)// 交換文字列の添え字.
		{
			for (int j = 0; j < N; j++)// 検索用文字列の前から.
			{
				for (int k = i + 1; k < N; k++)// 交換対象の探索.
				{
					// 検索用文字列に引っかかった.
					if (Ssort.at(j) == S.at(k))
					{
						if (S[i] > S[k])
						{
							swap(S[i], S[k]);
							// 変化数の確認.
							int cnt = Checkdiff(Sorigin, S);
							if (cnt > K)
							{
								// 越えていたので戻す.
								swap(S[i], S[k]);
							}
						}
					}
				}
			}
		}
 
		cout << S << endl;
	}
	return 0;
}
ポイント

基本的には前から変更を加えたほうが辞書的に早くなるということにまず気づく必要がある。
bcadeと並んでいて一度しか交換できないなら先頭の文字を入れ替えてacbdeにするのがよいということだ。
2度入れ替えれるなら当然前から2文字目を移動するのがいいだろう。

今回はsort関数を1から作るのが面倒なのでsortしてしまって、理想的な辞書順の文字列を作ってしまった。それがSsort変数である。
変数iは0からでつまるところ先頭の文字から順に変更していくよという意味である。
変数jも0からでこれはソート済みの理想的な文字列の先頭から確認していくよということである。
なぜなら、元の文字列の先頭の文字が理想文字の先頭文字に変更されることがもっとも理想的な交換になるはずだからだ。
変数kでは交換したい文字列がどこにあるのか確認している。これは後方から探索している。なぜかというと2回出てくる場合は、後ろから交換したほうが理想的だからだ。
例えば元文字列がbcadeaの場合、acbdeaとするよりacadebとするほうが辞書的に小さい。

まず元文字列の先頭から変更を試みる。そして交換したいのは理想文字列のできるだけ前のほうの文字だ。その交換したい文字が文字列の後ろから辿ってどこにあるか確認し、スワップする。
スワップした際に交換できる文字数を超えていたら元に戻そう。

今回の面倒な部分は、2回スワップしたからといって文字が4個変更されたわけではないということだ。
例えばbcadef → acbdef → abcdefだと2回、計4文字移動が行われているが実際に変更があるのは3文字だけだ。
すでに一度移動させた文字列なら1文字変更扱いで文字列のスワップが可能だ。
このあたりのスワップ回数を真面目に計算すると面倒なのでスワップ回数のことは忘れて、逐一元文字列と比較することで文字の変更数を確かめることにした。
ほんとうはもっと高速に組めるが、これでも十分動くので良しとする。

D - 漸化式

お、数学できないやつを潰しにかかってきたな!
しかも部分点もないんでやんの!

略解
// 後日.

ポイント

後日


だらだら配信

長いので割愛