🤖

ABC299 参加記録

2023/04/23に公開・約6,500字

AtCoder

競プロ

abc299

tech

ABC299に参加しました。A~Dの解説を書いていきます。

A - Treasure Chest

問題概要

3 種類の文字 . | * からなる、長さ $N$ の文字列 $S$ が与えられます。
$S$ には | がちょうど $2$ つ、* がちょうど $1$ つ含まれます。
$2$ つの | で囲まれた部分の中に * が含まれるか判定してください。
含まれている場合 in と、含まれていない場合 out と出力してください。

リンク:https://atcoder.jp/contests/abc299/tasks/abc299_a

解法

今までに現れた|の個数を持つ変数 $c$ を管理する。これを管理しつつ、以下を行えばよい。

$i=1,2,\dots,N$ に対して:
- $c=1$ かつ $S_i=$ * ならば、inを出力して終了する

最後まで終えたならoutを出力する。

実装例

#include <iostream>
#include <string>
using namespace std;
int main() {
    int n;
    string s;
    cin >> n >> s;
    int c = 0;
    for (int i = 0; i < n; i++) {
        if (s[i] == '|') c++;

        if (c == 1 && s[i] == '*') {
            puts("in");
            return 0;
        }
    }
    puts("out");
    return 0;
}

提出:5ms

B - Trick Taking

問題概要

$1$ から $N$ までの番号のついた $N$ 人のプレイヤーがカードゲームをします。
各プレイヤーは、カードを一枚場に出します。
各カードには、色,値のふたつの属性を持っています。
各 $i$ について、プレイヤー $i$ の出したカードの色は $C_i$ ,値は $R_i$ です。
今から、以下の方法で $1$ 人の勝者を決めます:

色が $T$ であるカードが $1$ 枚以上場に出された場合、色が $T$ であるカードのうち値が最大のものを出したプレイヤーが勝者である。

色が $T$ であるカードが場に $1$ 枚も出されなかった場合、プレイヤー $1$ が出したカードと同じ色のカードのうち値が最大のものを出したプレイヤーが勝者である。（プレイヤー $1$ 自身も勝者となり得ることに注意してください。）

勝者を決定してください。

リンク:https://atcoder.jp/contests/abc299/tasks/abc299_b

解法

なんかややこしいが、

$C_i=T$ なる $i$ が存在しなければ $T\leftarrow C_1$ と書き換える。

という操作を挟むと、勝者の決め方は1.の方を使うだけで済む。
あとは普通に実装すればよい。

実装例

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
    int n, t;
    cin >> n >> t;
    vector<int> c(n), r(n);
    for (auto& ci : c) cin >> ci;
    for (auto& ri : r) cin >> ri;

    if (find(c.begin(), c.end(), t) == c.end()) {
        t = c[0];
    }

    int ans = 0, ma = 0;
    for (int i = 0; i < n; i++) {
        if (c[i] == t && ma < r[i]) {
            ans = i;
            ma = r[i];
        }
    }
    cout << ans + 1 << '\n';
}

提出:117ms

C - Dango

問題概要

正の整数 $L$ に対して、レベル $L$ のダンゴ文字列とは、以下の条件を満たす文字列です。

o と - からなる長さ $L+1$ の文字列である。

先頭の文字と末尾の文字のうちちょうど一方が - であり、そのほかの $L$ 文字はすべて o である。

例えば、ooo- はレベル $3$ のダンゴ文字列ですが、-ooo- や oo や o-oo- などはダンゴ文字列ではありません（より正確には、どのような正の整数 $L$ に対してもレベル $L$ のダンゴ文字列ではありません)
$2$ 種類の文字 o- からなる、長さ $N$ の文字列 $S$ が与えられます。次の条件を満たすような正整数 $X$ のうち、最大のものを求めてください。

$S$ の連続する部分文字列であって、レベル $X$ のダンゴ文字列であるものが存在する。

ただし、そのような整数が存在しない場合、 $-1$ と出力してください。

$1\leq N\leq 2\times10^5$
リンク:https://atcoder.jp/contests/abc299/tasks/abc299_c

解法

要するに、次のような文字列であって最長のものの長さを求めればよい。

oのみからなる
$S$ の連続部分列として現れる
前後いずれかに-がある

これは、ランレングス圧縮をすることで容易に確認できる。

すこし考察

よくよく考えてみると、 $S$ にo,-の両方現れるならば以下が成り立つ:

oのみからなるような部分文字列には、前後のいずれかに-がついている

これを使うと、単にoのみからなる部分文字列であって最長のものを求めればよくなる。

実装例

そのまま

#include <iostream>
#include <vector>
using namespace std;
int main() {
    int n;
    string s;
    cin >> n >> s;
    vector<pair<char, int>> run_length;
    for (int i = 0; i < n;) {
        int j = i;
        int c = 0;
        while (s[i] == s[j]) {
            ++j;
            ++c;
        }

        run_length.emplace_back(s[i], c);
        i = j;
    }
    int x = -1;
    for (int i = 0; i < (int)run_length.size(); i++) {
        if (run_length[i].first != 'o') continue;
        bool is_ok = false;
        if (i - 1 >= 0 && run_length[i - 1].first == '-') {
            is_ok = true;
        }
        if (i + 1 < (int)run_length.size() && run_length[i + 1].first == '-') {
            is_ok = true;
        }

        if (is_ok) {
            x = max(x, run_length[i].second);
        }
    }

    cout << x << '\n';
}

提出:13ms

ちょっと単純にしたやつ

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
    int n;
    string s;
    cin >> n >> s;
    if (find(s.begin(), s.end(), 'o') == s.end() ||
        find(s.begin(), s.end(), '-') == s.end()) {
        puts("-1");
        return 0;
    }
    int x = 0;
    for (int i = 0; i < n;) {
        if (s[i] == '-') {
            i++;
            continue;
        }

        int len = 0;
        while (s[i] == 'o') {
            i++, len++;
        }
        x = max(x, len);
    }
    cout << x << '\n';
}

提出:13ms

D - Find by Query

問題概要

インタラクティブ問題です。
$0,1$ のみからなる長さ $N$ の文字列 $S$ があり $S_1=0,S_N=1$ を満たしています。
あなたは、この文字列 $S$ に関して以下の形式の質問を $20$ 回まですることができます。

? i: $S_i$ の値を聞く。

$1\leq p<N$ かつ $S_p\neq S_{p+1}$ を満たすような正整数 $p$ をひとつ出力してください。このような $p$ が存在することは証明できます。

$1\leq N\leq 2\times10^5$
リンク:https://atcoder.jp/contests/abc299/tasks/abc299_d

解法

以下、1-indexで考えます。

アイデア

制約から、質問回数は $\log N$ 程度でおさめる必要がありそう。ということで、なんとなく二分探索が思いつく。

以下のようにすれば良いことが分かる

変数 $l,r$ をそれぞれ $1,N+1$ で初期化しておく
$r-l>1$ の間、以下を繰り返す。
- $m=\lfloor{\frac{l+r}{2}}\rfloor$ として、 $S_m$ の値を聞く。
  - $S_m=1$ ならば、 $r\leftarrow m$ とする。
  - $S_m=0$ ならば、 $l\leftarrow m$ とする。
$l$ を出力

正当性

変数 $l,r$ は、常に以下の条件を満たしています。

{}^\exist p\in [l,r) :S_p\neq S_{p+1}

これを確認していきましょう。まず、初期状態では明らかに条件を満たしています。
問題は、

$m=\lfloor{\frac{l+r}{2}}\rfloor$ として、 $S_m$ の値を聞く。

$S_m=1$ ならば、 $r\leftarrow m$ とする。

$S_m=0$ ならば、 $l\leftarrow m$ とする。

のところです。実際に、こうしたとしても条件を満たしていることを確認します。
$S_m=0,1$ どちらもほぼ同じなので、 $S_m=1$ の時を示します:

示すべきは、

${}^\exists p\in[l,m):S_p\neq S_{p+1}\cdots\clubsuit$
です。これを背理法で示します。 $\clubsuit$ の否定は
${}^\forall p\in[l,m):S_p=S_{p+1}$
です。これが成り立つとき、 $S_l=S_{l+1}=\dots=S_{m}$ です。

ところで $l$ は $S_l=0$ を満たしています。なぜならば

初期状態では $S_l=S_1=0$

途中で $l\leftarrow l'$ と置き換えられる時、 $S_{l'}=0$ が必要

だからです。
したがって、 $\clubsuit$ が成り立たないならば、 $S_l=S_{l+1}=\dots=S_{m}=0$ です。
しかし、これは $S_m=1$ という仮定に反します。

したがって、

{}^\exist p\in [l,r) :S_p\neq S_{p+1}

であることが分かりました。終了時には $r=l+1$ なので、 $p\in[l,l+1)$ , すなわち $p=l$ で、答えがひとつ得られます。

実装例

質問回数は $\log N$ 回程度なので、 $20$ 回で答えを出せます。

#include <iostream>
using namespace std;

int main() {
    int n;
    scanf("%d", &n);
    fflush(stdout);
    int r = n + 1;
    int l = 1;      

    while (r - l > 1) {
        int m = (r + l) / 2;  // 真ん中を聞いてみる

        printf("? %d\n", m);
        fflush(stdout);

        int res;
        scanf("%d", &res);
        if (!res) {
            l = m;
        } else {
            r = m;
        }
    }

    printf("! %d\n", l);
    fflush(stdout);
}

提出:20ms

Discussion

ログインするとコメントできます