AtCoder ABC 381E - 11/22 Subsequence 偽ACのソースを晒します

ABC 381 E問題で、TLEになるはずの回答でACとって喜んでいたので戒めのために晒します😌

晒し用にある程度ソースを整えて、念のためジャッジに出したらTLE になったので不思議に思っていたら、コンテスト後にテストパターンが追加になっていたのですね。

言い訳だけど、コンテスト中も気づいてはいたので～。これだと最終的に '/' の回数、ほぼ総当たりなので、極端に '/' が多いパターンは TLE になるな、と思いながら、残り時間があと9分だったから、5分ペナよりジャッジに出して、どの程度正解になるか確認しよう、って出したら通って「あれ？ なんか俺が思い違いしたかな？」ってなって。

寝る前と起きてから少し考えて、やっぱりあの回答はダメだよな？ と思って自分で試験パターン作って確認しよう。その前に記事書いて晒そう、と思って今ココ！です。競技プログラミングだと、通ればよかろうなのだっていうのもあるでしょうけど、これを仕事でやって、仮にもしここがRT のクリティカルセッションだったりしたらえらいこっちゃなので、反省反省。

本当の正解は解説配信とか拝見して今から考えます、はい😌 今のところ自分では、連続する '/' を潰しておくぐらいしか思いつかないけど、それでもさらに都合の悪い入力だとなんとなく足りない気がするので、どうしようかな。

Main.cpp

#include <bits/stdc++.h>
using ll = long long;
using namespace std;

// 1, 2 の出現回数の累計和
ll gPreSum1[100009];
ll gPreSum2[100009];

int main( void )
{
	// 入力
	ll N, Q;
	string S;
	cin >> N >> Q >> S;

	// スラッシュの位置一覧
	vector<ll> vecPosSlash;

	for( ll i = 1; i <= N; ++i)
	{
		gPreSum1[i] = gPreSum1[i-1];
		gPreSum2[i] = gPreSum2[i-1];

		if( S[i-1] == '1' )
		{
			++gPreSum1[i];
		}
		else if ( S[i-1] == '2' )
		{
			++gPreSum2[i];
		}
		else
		{
			vecPosSlash.push_back(i);
		}
	}

	for( ll i = 0; i < Q; ++i)
	{
		ll L, R;
		cin >> L >> R;

		// L と以上のスラッシュの位置を探す
		auto itr = lower_bound( vecPosSlash.begin(), vecPosSlash.end(), L);
		if( itr == vecPosSlash.end())
		{	// そもそもない
			cout << "0" << endl;
			continue;
		}
		if( R < *itr)
		{	// あるが R よりでかい
			cout << "0" << endl;
			continue;
		}

		// 少なくとも / はある
		ll result = 1;
		while( itr != vecPosSlash.end() && *itr <= R )
		{
			// / の位置から前の1の数
			ll cnt1 = gPreSum1[*itr] - gPreSum1[L-1];
			// / の位置から後ろの2の数
			ll cnt2 = gPreSum2[R] - gPreSum2[*itr];
			// 短いほうの2倍+ / 分の長さ
			ll tmp = min(cnt1, cnt2) * 2 + 1;
			result = max( result, tmp);

			++itr; // 次の / も評価する
 		}
		cout << result << endl;
	}

	return 0;
}