ABC344 (upsolved)

Published on 2024-03-11
Last Modified 2024-03-11

Table Of Contents

贖罪

寝過ごしでABCポカしてしまった。信じられない。。
— In (@UU9782wsEdANDhp) March 9, 2024

最近参加記録を更新していませんでしたが、更新します。

問題たち

A - Spoiler

問題へのリンク

現在見ている場所が|に挟まれているかを変数に持つようにして、逐次出力するか判定します。

import std;

void main () {
    string s = readln.chomp;
    bool is_in = false;

    foreach (c; s) {
        if (c == '|') {
            is_in = is_in ? false : true;
            continue;
        }

        if (is_in) continue;
        write(c);
    }
    write("\n");
}

void read (T...) (string S, ref T args) {
    import std.conv : to;
    import std.array : split;
    auto buf = S.split;
    foreach (i, ref arg; args) {
        arg = buf[i].to!(typeof(arg));
    }
}

B - Delimiter

問題へのリンク

この問題はどういう意図なんでしょうか… 入力に0が来た時点で入力待ちをやめ、reverseして出力します。

import std;

void main () {
    int[] A;
    while (true) {
        int a = readln.chomp.to!int;
        A ~= a;
        if (a == 0) break;
    }

    A.reverse;
    foreach (a; A) writeln(a);
}

void read (T...) (string S, ref T args) {
    import std.conv : to;
    import std.array : split;
    auto buf = S.split;
    foreach (i, ref arg; args) {
        arg = buf[i].to!(typeof(arg));
    }
}

C - A+B+C

問題へのリンク

$A, B, C$から$1$個ずつ要素を選んだ和として実現可能なものの数は$O(NML)$個であり、十分少ないです。したがって、これらを先に連想配列などに登録しておけばクエリあたり高速に解くことができます。

import std;

void main () {
    int N = readln.chomp.to!int;
    auto A = readln.split.to!(int[]);
    int M = readln.chomp.to!int;
    auto B = readln.split.to!(int[]);
    int L = readln.chomp.to!int;
    auto C = readln.split.to!(int[]);

    bool[long] mp;
    foreach (a; A) foreach (b; B) foreach (c; C) mp[a + b + c] = true;

    int Q = readln.chomp.to!int;
    auto X = readln.split.to!(int[]);

    foreach (x; X) {
        if (x in mp) {
            writeln("Yes");
        }
        else {
            writeln("No");
        }
    }
}

void read (T...) (string S, ref T args) {
    import std.conv : to;
    import std.array : split;
    auto buf = S.split;
    foreach (i, ref arg; args) {
        arg = buf[i].to!(typeof(arg));
    }
}

D - String Bags

私が個人的に「とる/とらないdp」と呼んでいるものの亜種にあたる気がします。前から$i$袋に対して操作したときに、$T$の前からどこまで一致させられるかを持てば十分です。

私は慣れでdpにたどり着いてしまいましたが、dpを考えるモチベーションとしては、

ナイーブな$O((\max A _ i) ^ N)$通りの全探索を考える。
$T$を構築できるとり方のとき、最後に$s _ \mathrm{last}$をくっつけて$T$になるなら、それまでに$T$の先頭$|T| - |s _ \mathrm{last}|$文字が作れれば良いことがわかる。
これを繰り返していくと、各時点で$T$の先頭何文字なら実現できるかを変数に持てばよさそうだなとなる。
ついでに何回の採用でその状態に至るかを管理できそう。

という感じでしょうか。

import std;

void main () {
    string T = readln.chomp;
    int N = readln.chomp.to!int;
    auto S = new string[][](N, 0);
    foreach (i; 0..N) {
        auto input = readln.split;
        S[i] = input[1..$];
    }

    solve(T, N, S);
}

void solve (string T, int N, string[][] S) {
    // いい感じにdpしましょう
    auto dp = new int[][](N+1, T.length+1);
    // dp[i][j] := 前からi袋に対して操作を行い、Tの前j文字一致させる最小値段

    foreach (d; dp) d[] = int.max;
    dp[0][0] = 0;

    foreach (i; 0..N) {
        foreach (j; 0..T.length+1) {
            if (dp[i][j] == int.max) continue;

            // とる
            foreach (s; S[i]) {
                if (T.length < j + s.length) continue;
                if (T[j..j + s.length] != s) continue;
                dp[i + 1][j + s.length] = min(dp[i + 1][j + s.length], dp[i][j] + 1);
            }

            // とらない
            dp[i + 1][j] = min(dp[i + 1][j], dp[i][j]);
        }
    }

    if (dp[N][T.length] == int.max) {
        writeln(-1);
    }
    else {
        writeln(dp[N][T.length]);
    }
}

void read (T...) (string S, ref T args) {
    import std.conv : to;
    import std.array : split;
    auto buf = S.split;
    foreach (i, ref arg; args) {
        arg = buf[i].to!(typeof(arg));
    }
}

E - Insert or Erase

問題へのリンク

いい感じのグラフのようなものがあれば解けそうな感じです。できるだけポインタを扱いたくないので、「新しい要素の追加」を「まだ未使用な頂点を用いる」として考えるようにします。削除する必要があるので、頂点にどこからリンクされているか？という情報も持たせる必要がありそうです。

結論としては、次のようなノードを用いれば十分です。

struct node {
    int val = -1;
    int pre = -1;
    int nex = -1;
}

auto graph = new node[](N + Q);

int[int] val_to_idx;

int latest = 0;

新しいノードを追加するときはgraph[latest]をいじります。なお、先頭ノードのpreは-int.maxに、最後尾ノードのnexはint.maxにすることにします。

import std;

void main () {
    int N = readln.chomp.to!int;
    auto A = readln.split.to!(int[]);
    int Q = readln.chomp.to!int;

    solve(N, A, Q);
}

void solve (int N, int[] A, int Q) {
    // グラフ表現で答える

    struct node {
        int val = -1;
        int pre = -1;
        int nex = -1;
    }

    auto graph = new node[](N + Q);

    int[int] val_to_idx;

    int latest = 0;
    foreach (i; 0..N) {
        graph[latest] = node(A[i], i-1, i+1);

        if (i == 0) graph[latest].pre = -int.max;
        if (i == N-1) graph[latest].nex = int.max;

        val_to_idx[A[i]] = latest;
        latest++;
    }

    foreach (_; 0..Q) {
        auto input = readln.split;
        int t = input[0].to!int;

        if (t == 1) {
            int x = input[1].to!int;
            int y = input[2].to!int;

            int node_idx = val_to_idx[x];
            int next_idx = graph[node_idx].nex;

            // 新しい頂点の追加
            graph[latest] = node(y, node_idx, next_idx);

            // 元の次の頂点の書き換え
            if (next_idx < int.max) graph[next_idx].pre = latest;

            // 元の頂点の書き換え
            graph[node_idx].nex = latest;

            // 登録
            val_to_idx[y] = latest;

            latest++;
        }

        if (t == 2) {
            int x = input[1].to!int;

            int node_idx = val_to_idx[x];
            int prev_idx = graph[node_idx].pre;
            int next_idx = graph[node_idx].nex;

            // 前からのリンクの変更
            if (-int.max < prev_idx) graph[prev_idx].nex = next_idx;

            // 次からのリンクの解除
            if (next_idx < int.max) graph[next_idx].pre = prev_idx;

            // 登録解除
            val_to_idx.remove(x);
        }
    }

    int cur = -1;
    foreach (key, val; val_to_idx) {
        if (graph[val].pre == -int.max) {
            cur = val;
            break;
        }
    }

    while (true) {
        write(graph[cur].val);
        if (graph[cur].nex == int.max) {
            write("\n");
            break;
        }

        write(" ");
        cur = graph[cur].nex;
    }
}

void read (T...) (string S, ref T args) {
    import std.conv : to;
    import std.array : split;
    auto buf = S.split;
    foreach (i, ref arg; args) {
        arg = buf[i].to!(typeof(arg));
    }
}

少し前にこの問題を解いていたため、いい感じに解くことができました。一発で合わせられて満足です。

F以降

わかりません！！！！！

F問題は解説を見てもいいかなと思ったのですが、どうしても抵抗があり、今はまだupsolveしていません。 difficultyと私のこだわりの呪いにより、永遠に伸び悩んでます。

終わりに

このくらいサクッとした参加記録を書こうかなと思いました。今までのスタイルはあまりにも作成がしんどいので。

面倒くささに負けたような気もして嫌だなぁとなりますが、継続こそ価値があると思うのです。

ちなみにこの回出てたら多分温まりです。勘弁してくれー

Tags for this post: 競技プログラミング Upsolve

Prev: MMA Contest 016 (upsolved)

Next: ABC35D - トレジャーハント

ABC344 (upsolved)

贖罪

問題たち

A - Spoiler

B - Delimiter

C - A+B+C

D - String Bags

E - Insert or Erase

F以降

終わりに

Other posts tagged by "競技プログラミング"

Other posts tagged by "upsolve"