AtCoder Beginner Contest 364

A,B,Cの3完。

レートは898→880の-18となり、ついにレートダウンを経験してしまった。

A問題で一回WAを出してしまったことと、C問題まで合計で30分弱かけてしまったことが要因だと思われる。

解けなかった問題を解けるようにすることでしか、前に進むことはできないと思うので、切り替えて丁寧に復習する。

このqiitaではD, E問題は公式の解説を参考にしている。

A - Glutton Takahashi

N個の料理があり、i番目の料理がsweetかsaltyかが与えられる。ただし、連続するsweet料理を食べるとそれ以降の料理が食べられなくなってしまう。全ての料理を食べきれるかどうか判定せよ、という問題。

一番最後の料理をのぞいて、連続するsweet料理がある場合はNoを出力する。

1回目の提出の時にはsweetだけでなくsaltyも連続している場合もNGだと勘違いしており、WAを出してしまった。

ll N;
string S[1000];
vector<vector<ll>> dp;

int main()
{
	cin >> N;
	for (int i = 1; i <= N; i++)
	{
		cin >> S[i];
		if (i > 1)
		{
			if (S[i-1] == S[i] && S[i] == "sweet")
			{
				if (i == N) continue;
				cout << "No" << endl;
				return 0;
			}
		}
	}
	cout << "Yes" << endl;
	return 0;
}

B - Grid Walk

H行W列のマス目があり、各マスにが空きマスかそうでないかが与えられる。LRUDの入力が与えられた時、その方向が空きマスである限り移動を続けることができる場合、最終的にどのマスにいるかを出力せよ、という問題。

下記のコードでは今いる場所が $(cx, cy)$ なのだが、$C[cy][cx - 1]$ というように、配列の添え字が1から始まっていることに注意する。

基本的には移動できるか確認し、移動可能な空きマスであれば移動を繰り返し、最終的なマスの座標を出力する問題。

ll H, W, Si, Sj;
string C[100];
string X;

int main()
{
    cin >> H >> W >> Si >> Sj;
    for (int i = 1; i <= H; i++)
    {
        cin >> C[i];
    }
    cin >> X;
    ll cx = Sj;
    ll cy = Si;
    for (int i = 0; i < X.size(); i++)
    {
        if (X[i] == 'L')
        {
            if (cx > 1 && C[cy][cx - 2] == '.') cx--;
        }
        if (X[i] == 'R')
        {
            if (cx < W && C[cy][cx] == '.') cx++;
        }
        if (X[i] == 'U')
        {
            if (cy > 1 && C[cy - 1][cx - 1] == '.') cy--;
        }
        if (X[i] == 'D')
        {
            if (cy < H && C[cy + 1][cx - 1] == '.') cy++;
        }
    }
    cout << cy << " " << cx << endl;
    return 0;
}

C - Minimum Glutton

甘さとしょっぱさが数値で規定される料理が$N$個ある。それらを好きな順番で食べることができ、かつ甘さの合計が$X$、しょっぱさの合計が$Y$を超えると食べるのをやめる時、食べる料理は最小何品か、という問題。

先に上限が来るのがしょっぱさでも甘さでも食べるのをやめるので、全ての料理をしょっぱさと甘さそれぞれで降順にソートし、順番に食べていきどちらかが上限を超えたタイミングで終了する。

ll N, Y, X;
vector<ll> A;
vector<ll> B;

int main()
{
    cin >> N >> X >> Y;
    for (int i = 1; i <= N; i++)
    {
		ll a, b;
        cin >> a;
		A.push_back(a);
    }
    for (int i = 1; i <= N; i++)
    {
		ll b;
        cin >> b;
		B.push_back(b);
    }
	sort(A.begin(), A.end());
	sort(B.begin(), B.end());
	reverse(A.begin(), A.end());
	reverse(B.begin(), B.end());
	ll amasa = 0;
	ll karasa = 0;
	for (int i = 1; i <= N; i++)
	{
		amasa += A[i - 1];
		karasa += B[i - 1];
		if (amasa > X || karasa > Y)
		{
			cout  << i << endl;
			return 0;
		}
	}
	cout << N << endl;
    return 0;
}

D - K-th Nearest

数直線上にN個の点があり、それぞれの点の座標が与えられる。Q個のクエリが与えられ、それぞれのクエリに対して、座標がBである点から距離がA以内の点の中で、K番目に近い点の座標を出力せよ、という問題。

コンテスト中に提出したTLEコードも下に添付しているが、クエリだけで $10^5$あるので、それぞれのクエリの中で全ての要素にアクセスしていると間に合わない。実際の処理としては、クエリの中で二分探索を行うことで、計算量を減らすことができる。

ll N, Q;
vector<ll> A;

bool    ft_check_binary_search(ll b, ll k, ll x)
{
    ll R_num = lower_bound(A.begin(), A.end(), b + x + 1) - A.begin();
    ll L_num = lower_bound(A.begin(), A.end(), b - x) - A.begin();
    return (R_num - L_num >= k);
}

int main()
{
    cin >> N >> Q;
    A.resize(N);
    for (int i = 0; i < N; i++) cin >> A[i];
    sort(A.begin(), A.end());
    // クエリの実行
    while (Q--)
    {
        ll b, k;
        cin >> b >> k;
        // -1だと絶対に存在しない、10^8だと絶対にk個以上存在する
        ll low = -1;
        ll high = 2e8;
        while (high - low > 1)
        {
            ll mid = low + (high - low) / 2;
            if (ft_check_binary_search(b, k, mid)) high = mid;
            else low = mid;
        }
        cout << high << endl;
    }
    return 0;
}

下記はコンテスト中に提出したTLEコード。

全てのクエリで配列Aの要素全てに-bをして原点中心にし、負の数を正の数へ変換してソートすることで、原点からの距離が近い順にソートされた配列を作成した。この配列のk番目の要素を出力した。

// コンテスト中に提出した、文句なしのTLEコード
ll N, Q;
vector<ll> A;
vector<ll> B;
vector<ll> K;

void ft_solve(ll b, ll k)
{
    multiset<ll> modifiedA;
    // ここで配列Aの要素を全て-bし、負の数は正の数にする
    for (ll x : A)
    {
        x -= b;
        if (x < 0) x = -x;
        modifiedA.insert(x);
    }
    // multisetをvectorに変換し、k番目の要素を出力
    auto it = modifiedA.begin();
    advance(it, k - 1);
    cout << *it << endl;
}

int main()
{
    cin >> N >> Q;
    A.resize(N);
    B.resize(Q);
    K.resize(Q);
    for (int i = 0; i < N; i++) cin >> A[i];
    for (int i = 0; i < Q; i++) cin >> B[i] >> K[i];
    for (int i = 0; i < Q; i++) ft_solve(B[i], K[i]);
    return 0;
}

E - Maximum Glutton

C問題の派生系。

甘さとしょっぱさが数値で規定される料理が$N$個ある。それらを好きな順番で食べることができ、かつ甘さの合計が$X$以内かつ、しょっぱさの合計が$Y$以内なら食べ続ける時、食べる料理は最大何品か、という問題。

DPのキーと値を入れ替えるというのは典型的なテクニックらしいので、これを機に身につけられるようにしたい。

ll N, X, Y;
const ll INF = 1e18;

int main()
{
	// 入力
    cin >> N >> X >> Y;
	vector<ll> A(N), B(N);
	for (int i = 0; i < N; i++) cin >> A[i] >> B[i];
	// dp[i][j][k]: 料理iまでの中で、甘さの合計がkとなるようにj個の料理を選んだときの最小のしょっぱさ
	vector<vector<vector<ll>>> dp(N + 1, vector(N + 1, vector<ll>(X + 1, INF)));
	// 初期状態
	dp[0][0][0] = 0;
	// 動的計画法スタート
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j <= i; j++)
		{
			for (int k = 0; k <= X; k++)
			{
				dp[i + 1][j][k] = min(dp[i + 1][j][k], dp[i][j][k]);
				// i番目の料理をえらんでも甘さがXを超えない場合
				if (k + A[i] <= X)
				{
					dp[i + 1][j + 1][k + A[i]] = min(dp[i + 1][j + 1][k + A[i]], dp[i][j][k] + B[i]);
				}
			}
		}
	}
	// N番目の料理までの中で、甘さがX, しょっぱさがY以下となる最大料理数を求める
	for (int i = N; i >= 0; i--)
	{
		for (int j = 0; j <= X; j++)
		{
			if (dp[N][i][j] <= Y)
			{
				cout << min((ll)i + 1, N) << endl;
				return 0;
			}
		}
	}
    return 0;
}

以下はコンテスト中に記述したコード。

動的計画法で行う、というところまでは想定できていたが、甘さからさの条件である$X$と$Y$の条件が　＄10^5$ という制約があるため、$O(N^2)$の計算量では間に合わず断念した。

// コンテスト中に考えた3次元DP.

ll N, X, Y;
vector<ll> A;
vector<ll> B;

int main()
{
    cin >> N >> X >> Y;
    A.resize(N);
    B.resize(N);
    for (int i = 0; i < N; i++)
    {
        cin >> A[i];
    }
    for (int i = 0; i < N; i++)
    {
        cin >> B[i];
    }

    // DPテーブルの初期化
    // dp[i][j][k] := i番目までの料理を食べて、最後にj個の料理を食べたときの満足度の最大値
    vector<vector<vector<ll>>> dp(N+1, vector<vector<ll>>(X+1, vector<ll>(Y+1, 0)));
    
	ll ans = 0;
    // DPの更新
    for (int i = 0; i < N; i++) {
        for (int x = 0; x <= X; x++) {
            for (int y = 0; y <= Y; y++) {
                // 現在の料理を食べない場合
                dp[i+1][x][y] = max(dp[i+1][x][y], dp[i][x][y]);
				ans = max(ans, dp[i+1][x][y]);
                // 現在の料理を食べる場合
                if (x + A[i] <= X && y + B[i] <= Y) {
                    dp[i+1][x + A[i]][y + B[i]] = max(dp[i+1][x + A[i]][y + B[i]], dp[i][x][y] + 1);
					ans = max(ans, dp[i+1][x + A[i]][y + B[i]]);
				}
				
            }
        }
    }
    cout << ans << endl;
    return 0;
}