LoginSignup
0
0
@yaburen

【c++】ABC359 A-E問題解説【ACコード付き】（毎日ABC day23）

Posted at

AtCoder Beginner Contest 359

A,B,Cの3完。

レートは652→704の+52となり、目標であった+50の成長率に戻すことができた。

C問題までの3完に留まったが、D問題の回文が絡む問題が難しかったのと、A問題B問題をそれぞれ1.5分、2.5分とスピーディーに解くことができたのが大きかった。

パフォーマンスも人生で初めて1000を超えたので、次は1200超え、水色パフォを目標に頑張りたい。

D問題の回文判定を含む問題も、E問題の動的計画法で解く問題も惜しいところまで行ったのに間に合わなかったのが悔しかった。

先週のコンテストは調子悪くて若干萎えていたが、やはり土曜日1日を競プロの学習の時間に充てると調子が良くなる。競プロ用の脳のセッティングがある気がする。

A - Count Takahashi

与えられる $N$ 個の文字列はTakahashi か Aokiのどちらかです。
いくつTakahashiがあるかを出力してください、という問題。

シンプルにループを回してカウント。

int N;
string S;

int main()
{
	int count = 0;
	cin >> N;
	for (int i = 1; i <= N ; i++)
	{
		cin >> S;
		if (S == "Takahashi") count++;
	}
	cout << count << endl;
    return 0;
}

B - Couples

$2N$ 人が並んでおり、$N$ 個の服のペアを着ている。つまり、$i$ 人目の人が着ている服を着ている人が列の中に1人だけいる。そのようなペアの中で、一人飛ばしで並んでいる組はいくつあるか、という問題。

これもシンプルにループを回してカウント。ループの範囲に注意。

int N;
int A[100009];

int main()
{
	cin >> N;
	int count = 0;
	for (int i = 1; i <= 2 * N ; i++)cin >> A[i];
	for (int i = 1; i <= 2 * N - 2 ; i++)
	{
		if (A[i] == A[i + 2]) count++;
	}
	cout << count << endl;
    return 0;
}

C - Tile Distance 2

実際の問題文にある図を見てもらうのが一番早いが、
$2×1$ の大きさのタイルが敷き詰められており、上下左右に移動できる。

タイル間の移動に1ドルかかる時、スタート地点からゴール地点までにかかる最小の移動料金はいくらか、という問題。

基本的に縦の移動は高さの差の分の通行量がかかるが、横方向は縦の移動を行いながら、1マスずつ横に無料で移動できるので、ひたすら条件分岐で場合分けした。

コンテスト中は思考停止でゴリゴリの条件分岐に逃げてしまったが、最初からx軸とy軸の合計が奇数の場合はタイルの左側に寄せておく、という処理を噛ませることにより非常に簡便に実装が可能ということを解説を見て学んだ。

// 実際にコンテスト中に提出したコード
ll sx, sy, tx, ty;

int main() {
    cin >> sx >> sy >> tx >> ty;
    ll height = abs(ty - sy);
    ll width = abs(tx - sx);
    ll ans = height;
    
    ll tmp = width - height;
    
	if (tmp > 0)
	{
		if (tx > sx)
		{
			if (sy % 2 == 1 && sx % 2 == 0)tmp++;
			if (sy % 2 == 0 && sx % 2 == 1)tmp++;
		}
		else 
		{
			if (sy % 2 == 1 && sx % 2 == 1)tmp++;
			if (sy % 2 == 0 && sx % 2 == 0)tmp++;
		}
		if (tmp % 2 == 1) {
			if (tx > sx && sx % 2 == 1) tmp--;
			if (tx < sx && sx % 2 == 0) tmp--;
		}
		ans += (tmp / 2);
	}
    cout << ans << endl;
    return 0;
}

Youtubeの解説動画を見て学んだ要点は以下。　

  • タイルの右側だったら左側に統一
  • スタート地点を原点に揃える（ゴール地点を並行移動）
  • x軸, y軸ともに線対称なことを利用して第一象限で処理
// 動画の解説コード。こんなにシンプルにまとまるのか。。
int main() {
    long long Sx, Sy, Tx, Ty;
    cin >> Sx >> Sy >> Tx >> Ty;

    Sx -= abs(Sy - Sx) % 2;
    Tx -= abs(Ty - Tx) % 2;

    Tx -= Sx;
    Ty -= Sy;

    Tx = abs(Tx);
    Ty = abs(Ty);

    cout << Ty + max(0LL, Tx - Ty) / 2 << endl;
}

D - Avoid K Palindrome

ビット全探索により?がAになる場合と Bになる場合を全て探索し、それぞれの文字列に対してK文字分の部分文字列をハッシュ値を用いた回文判定にかけることにより求めようとしていたが、1000個?がある場合などには計算量が大変なことになってしまい、コンテスト中はACできなかった。

// このコードはACではありません
ll N, K;
ll cur[1009];
vector<ll> free_place;
vector<ll> hash_palindol;
const ll INF = 998244353;

string S;
string tmp_S;
string S_rev;

// ハッシュ値を計算するための変数 
long long mod = 1000000007;	// なるべく大きな素数
long long T[200009];		// 文字列を数に変換するための箱
long long T_rev[200009];	// 文字列を数に変換するための箱
long long H[200009];
long long H_rev[200009];
long long Power100[200009];

// S[l,r]のハッシュ値を返す関数
// あまりの計算に注意！
long long ft_hash(int l, int r)
{
	long long val = H[r] - (H[l - 1] * Power100[r - l + 1] % mod);
	if (val < 0) val += mod;
	return val;
}

// 逆から読んだ時のハッシュ計算
long long ft_hash_rev(int l, int r)
{
	long long val = H_rev[r] - (H_rev[l - 1] * Power100[r - l + 1] % mod);
	if (val < 0) val += mod;
	return val;
}

bool ft_pallindol(int start, int end)
{
	// 部分文字列の長さを計算
	int length = end - start + 1;
	
	// tmp_Sの部分文字列を生成
	string sub_S = tmp_S.substr(start - 1, length);
	string sub_S_rev = sub_S;
	reverse(sub_S_rev.begin(), sub_S_rev.end());

	// 文字を数値に変換
	for (int i = 1; i <= length; i++) T[i] = (sub_S[i - 1] - 'a') + 1;
	for (int i = 1; i <= length; i++) T_rev[i] = (sub_S_rev[i - 1] - 'a') + 1;

	// H[1],...,H[length]を計算する
	H[0] = 0;
	for (int i = 1; i <= length; i++) H[i] = (100LL * H[i - 1] + T[i]) % mod;
	// 反転版も計算しておく
	H_rev[0] = 0;
	for (int i = 1; i <= length; i++) H_rev[i] = (100LL * H_rev[i - 1] + T_rev[i]) % mod;
	
	// ハッシュ値を比較
	long long hash1 = ft_hash(1, length);
	long long hash2 = ft_hash_rev(1, length);
	return hash1 == hash2;
}

int main()
{
	cin >> N >> K >> S;
	// 入力しながら、ビットの個数を累積和とる
	cur[0] = 0;
	for (int i = 0; i < N; i++)
	{
		if (i > 0) cur[i] = cur[i - 1];
		if (S[i] == '?')
		{
			free_place.push_back(i);
			cur[i]++;
		}
	}
	// 100のn乗を前計算しておく
	Power100[0] = 1;
	for (int i = 1; i <= N; i++) Power100[i] = 100LL * Power100[i - 1] % mod;
	// ビット全探索
	ll ans = 0;
	for (int k = 0; k <= N - K; k++)
	{
		bool tmp = true;
		// k ~ k + K の範囲の中に?がいくつあるか
		ll num_hatena = cur[k + K - 1];
		if (k != 0) num_hatena -= cur[k - 1];
		for (int i = 0; i < (1 << num_hatena); i++)
		{
			tmp_S = S;
			ll front_hatena = 0;
			
			if (k > 0) front_hatena = cur[k - 1];
			for (int j = 0; j < num_hatena; j++)
			{
				if (i >> j & 1) tmp_S[free_place[front_hatena + j]] = 'A';
				else tmp_S[free_place[front_hatena + j]] = 'B';
				if (ft_pallindol(k + 1, k + K)) tmp = false;
			}
		}
		if (tmp)
		{
			ans++;
			ans %= INF;
		}
	}
	cout << ans << endl;
	return 0;
}

解説を参考にビットマスク探索によりAC。
今回のAと Bの場合や、スイッチのONOFFなど、2択の状況がどちらも考えられる場合はビットマスクが有効そう。

//解説を参考にしたACコードです
int main() {
    using namespace std;
    using modint = atcoder::static_modint<998244353>;

    unsigned N, K;
    cin >> N >> K;

    // 長さ K の 0/1 文字列のうち、回文でないもの
    // を二進法で表された整数として解釈したもの
    vector<unsigned> not_palindrome;
    for (unsigned i = 0; i < 1U << K; ++i) {
        bool is_palindrome = true;
        for (unsigned j = 0, k = K - 1; j < k; ++j, --k) {
            // 上から見たときと下から見たときで違うビットがあれば
            if ((1 & i >> j) != (1 & i >> k)) {
                // 回文ではない
                is_palindrome = false;
                break;
            }
        }
        // 回文でなければ追加
        if (!is_palindrome)
            not_palindrome.emplace_back(i);
    }

    string S;
    cin >> S;

    vector<modint> dp(1U << K - 1), prev(1U << K - 1);
    { // 先頭 K - 1 文字としてありえるものをすべて列挙する
        // a_mask = 'A' の場所だけ 1 になっているビットマスク
        // q_mask = '?' の場所だけ 0 になっているビットマスク
        unsigned a_mask{}, q_mask{};
        for (const auto c : S | views::take(K - 1)) {
            (a_mask *= 2) += c == 'A';
            (q_mask *= 2) += c != '?';
        }

        // q_mask のビットは常に確定させて、'?' の部分を全探索
        for (unsigned i{q_mask}; i < 1U << K - 1; ++i |= q_mask)
            dp[i ^ a_mask] = 1;
    }

    const unsigned mask{(1U << K - 1) - 1};
    for (const auto c : S | views::drop(K - 1)) {
        swap(dp, prev);
        ranges::fill(dp, modint{});

        // 'A' を追加する場合
        if (c != 'B')
            // 回文でなく、末尾が 'A'(0) であるような場合について遷移する
            for (const auto i : not_palindrome | views::filter([](auto i) { return ~i & 1; }))
                dp[i & mask] += prev[i / 2];

        // 'B' を追加する場合
        if (c != 'A')
            // 回文でなく、末尾が 'B'(1) であるような場合について遷移する
            for (const auto i : not_palindrome | views::filter([](auto i) { return i & 1; }))
                dp[i & mask] += prev[i / 2];
    }

    // すべての接尾辞に対する合計が答え
    cout << reduce(begin(dp), end(dp)).val() << endl;
    return 0;
}

E - Water Tank

頭の中でアルゴリズムを考えられてもコンテスト中の実装が間に合わなかった問題。悔しい。

新しく満たしていきたい領域の左側から、低い部分から解消して、、新しく満たしていきたい左側の崖の高さ以下の領域を無くしていく。

ll N;
ll H[200009];
vector<pair<ll, ll>> L;

int main()
{
    // 入力
    cin >> N;
    for (int i = 1; i <= N ; i++) cin >> H[i];
    ll total = 1;
    // 一つ一つ壁を越えていく
    for (int i = 1; i <= N ; i++)
    {
        ll count = 1;
        while(!L.empty() && L.back().first < H[i])
        {
            total -= L.back().first * L.back().second;
            count += L.back().second;
            L.pop_back();
        }
        total += H[i] * count;
        L.push_back(make_pair(H[i], count));
        if (i > 1) cout << " ";
        cout << total;
    }
    return 0;
}
0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
0