Zenn
⛳

ABC298 参加記録

2023/04/16に公開
AtCoder
abc
tech

ABC298に参加しました。現在ACできているのがA~Eなので、そのうちC,D,Eの解法を書いていきます。

C - Cards Query Problem

問題概要

1~N までの番号のついた箱と、無数のカードがあります。以下のクエリがQ個与えられるので、順に処理してください。

  • 1 i j:新たにカード1枚を取り、数iを書き込んでからカードを箱jに入れる
  • 2 i:箱iに入っているカードを昇順で出力する(重複は、消去しない)
  • 3 i:数字iの書かれたカードの入っている箱の番号を昇順に出力する(重複は消去する)
  • 1\leq Q\leq 10^5
  • 1 i jのクエリにおいて1\leq i\leq 2\times10^5
  • 3 iのクエリにおいて1\leq i\leq 2\times10^5
  • 出力すべき数字は、2\times10^5個以下に収まる
  • 入力はすべて整数

リンク:

解法

問題文がややこしい...というか、紛らわしいので、できるだけサンプルは試すことをお勧めする。
解法自体はそこまで難しくなく、いわゆるset,multisetを用いればよい。

実装例

c.cpp
#include <iostream>
#include <set>
#include <unordered_map>
#include <vector>
using namespace std;
int main() {
    int n;
    scanf("%d", &n);

    constexpr int CARD_MAX = 2e5;
    vector<multiset<int>> v1(n + 1);  // v1[i]:=箱iに入っているカード
    vector<set<int>> v2(CARD_MAX + 1);    //v2[i]:=数字iの書かれたカードが入っている箱

    int q;
    scanf("%d", &q);
    while (q--) {
        int t;
        scanf("%d", &t);
        if (t == 1) {
            int i,j;
            scanf("%d%d", &i, &j);
            v1[j].emplace(i);
            v2[i].emplace(j);
        } else if (t == 2) {
            int i;
            scanf("%d", &i);
            for (const auto& card : v1[i]) {
                printf("%d ", card);
            }
            printf("\n");
            
        } else {
            int i;
            scanf("%d", &i);
            for (const auto& box : v2[i]) {
                printf("%d ", box);
            }
            printf("\n");
        }
    }
}

大丈夫とは思うけれど...入出力多くなりそうなので、一応scanf,printfを使ってる。

D - Writing a Numeral

問題概要

文字列 S があり、最初 S=1 である。以下の形式のクエリが Q 個与えられるので、順に処理せよ

  • 1 x:S の末尾に数字x を追加する。
  • 2:Sの先頭の文字を削除する
  • 3:Sを10進数表示の整数と見たときの、S \bmod998244353の値を答える
  • 1\leq Q\leq 6\times10^5
  • クエリ1において0\leq x<10
  • クエリ2は、|S|>1の時のみ行われる

解法

S=\sum{10^ia_i}=10^na_n+10^{n-1}a_{n-1}+\dots+10a_1+a_0

みたいにおいてみる。文字列としてみるなら

S=a_na_{n-1}\dots a_1a_0

というかんじ。Sの末尾にxを挿入したS'は
S'=a_na_{n-1}\dots a_1a_0x

となって、これを数式で表せば

S'=10^{n+1}a_n+10^{n}a_{n-1}+\dots+10^2a_1+10a_0+x=10S+x

みたいになる。よってクエリ1は
S\leftarrow10S+x

と言い換えられる。同様に考えると、クエリ2は
S\leftarrow S-10^na_n

であることが分かる。ということで、結局は a の先頭の状況を管理すればよく、これはqueueとかでできる。

実装例

自作のmodintを使ってみる(Library)

#include <bits/stdc++.h>
#include "math/static_modint.hpp"
using namespace std;
using mint = kyopro::static_modint32<998244353>;
int main() {
    mint cur = 1;
    mint pw = 1;
    queue<int> que;
    const mint inv10 = mint(10).inv();
    que.emplace(1);
    int q;
    scanf("%d", &q);
    while (q--) {
        int t;
        scanf("%d", &t);
        if (t == 1) {
            int x;
            scanf("%d", &x);
            cur *= 10;
            cur += x;
            que.emplace(x);
            pw *= 10;
        } else if (t == 2) {
            cur -= pw * que.front();
            pw *= inv10;
            que.pop();
        } else {
            printf("%lld\n", cur.val());
        }
    }
}

ローリングハッシュをみたことあると解きやすいらしい(たしかに)

E - Unfair Sugoroku

問題概要

高橋君と青木君がすごろくをします。
高橋君ははじめ地点 A、青木君ははじめ地点 B にいて、交互にサイコロを振ります。
高橋君が振るサイコロは 1,2,\dots,P の出目が一様ランダムに出るサイコロで、青木君が振るサイコロは 1,2,\dots,Q の出目が一様ランダムに出るサイコロです。
$ 地点 x にいるときに自分の振ったサイコロの出目が i であるとき、地点 \min(x+i,N) に進みます。
地点 N に先に着いた人をすごろくの勝者とします。
高橋君が先にサイコロを振るとき、高橋君が勝つ確率を \bmod998244353 で求めてください。

  • 1\leq N\leq 100
  • 1\leq A,B\leq N
  • 1\leq P,Q\leq 10

解法

２人の位置を状態としてもってDPすればよい。手番が分かるように、それも持っておこう。
要は、以下のような dp をする。

  • dp[i][j]:=高橋君が位置iにいて青木君が位置jにいる状態で、現在の手番は高橋君。この状態から高橋君が勝てる確率
  • ep[i][j]:=高橋君が位置iにいて青木君が位置jにいる状態で、現在の手番は青木君。この状態から青木君が勝てる確率

漸化式は次のようになる。

dp[i][j]=1-\frac{1}{P}\sum_{d=1}^{P}{ep[i+d][j]}

ep[i][j]=1-\frac{1}{Q}\sum_{d=1}^{Q}{dp[i][j+d]}

これを実装すれば答えが得られる。計算量は

  • 状態数・・・O(N^2)
  • 遷移・・・O((P+Q)\log M)(M=998244353)

なので、全体 O(N^2(P+Q)\log M)で答えが求まりました。

Discussion