【C++】文字列型と数値型の相互変換のチートシート

競プロでC++を使い始めたものの、わからなくなりがちなので

変換後の型
int string vector<char> char(xが1桁)





(x)
int - to_string(x) 先にstringに
変換する
char('0' + x)
string stoi(x) - vector<char>(x.begin(), x.end()) x[0]
vector
<char>
stoi(string(x.begin(), x.end())) string(x.begin(), x.end()) - x[0]
char int(x - '0') vector<char>({x}) string({x}) -

補足

  • #include <bits/stdc++.h>およびusing namespace std;を書いていることを前提にしています
  • to_string関数はint型以外にも、long long型、double型、float型などもstring型に変換可能
  • string型からの変換はstoi関数以外にも、stoll関数でlong long型、stod関数でdouble型、stof関数でfloat型に変換可能

結果
ググらなくてよくなる!!

【AtCoder】ARC111D:Orientation(600点)

強連結な有向グラフの作り方がわからなかったので、備忘録として。

問題

ARC111D:Orientation

前提知識

  • Lowlink

問題の概要

N\ 頂点\ M\ 辺の単純な無向グラフ\ G\ と正整数列\ c_1, c_2, \ldots ,c_N\ が与えられる。
G\ の各頂点\ v_i\ から到達できる頂点の数(v_i\ 自身も含む)が、ちょうど\ c_i\ になるように各辺に向き付けせよ。

制約

  • \ 1\leq N\leq 100\
  • \ 0\leq M\leq\frac{N(N-1)}{2}\
  • \ 1\leq c_i\leq N\
  • 与えられるグラフに自己ループや多重辺は存在しない(非連結はあり得る)
  • 与えられる入力には必ず解が存在する

解法

問題の言い換え

G\ 内の辺\ (u, v)\ を適当にとってみます。

実は、c_u\ \ c_v\ が一致していなければ、即座に向き付け可能です。
もし\ c_u > c_v\ ならば、明らかに辺の向きは\ u \rightarrow v\ とするしかありません。u \leftarrow v\ とした場合、u\ から辿れる頂点は\ v\ からも辿れるため、c_u \leq c_v\ となってしまうためです。

一方で、c_u = c_v\ の場合には、u\ \ v\ 相互に到達できる必要があります。
この条件が\ c_u = c_v\ を満たす任意の辺\ (u, v)\ について成立している必要があることから、結局以下の問題が解ければよいです。

G\ からc_u\ = c_v\ を満たす辺\ (u, v)\ のみを取り出したグラフ\ G'\ を新たに\ H\ とする。
G'\ の各連結成分\ H\ に対して、相互に到達可能(=強連結)になるように向き付けせよ。
(ただし、問題の制約上、強連結になるように向き付けできることが保証されている。)

強連結なグラフの作り方

結論から言うと、強連結にできることが保証されている任意のグラフに対して、以下の操作で構築可能です。

連結グラフの頂点を一つ選び(v\ とする)、v\ からDFSを行い、通過した頂点と辺のみを使った根付き木(DFS木)を作る。DFS木上の辺を「根→葉」、それ以外の辺(後退辺)を「葉→根」となるようにグラフに向き付けを行うと、この連結成分は強連結になっている。

公式解説では詳細な証明は省略されていたので、上記操作で構築できることの証明を以下で行います。

操作の証明

方針

橋が存在するグラフは、明らかに強連結にできないことに注目します。つまり、今回与えられるグラフ\ H\ には橋が存在しません。

  • 上記操作後のグラフが強連結でないと仮定した場合、H\ には橋が存在する

ということを証明することで、橋が存在しない\ H\ においては、操作により必ず強連結にできることを証明します。

本体

まず、適当な頂点を根として選び、これを\ 0\ とします。
0\ を始点としてDFSを行うことでDFS木を作り、辿った順番に頂点に番号をつけます。さらに、先程の操作の説明通り、DFS木上の辺を「根→葉」、後退辺を「葉→根」となるようにグラフに向き付けを行います。

ここで、Lowlinkという概念を導入します。詳細は省略しますが、定義は以下のとおりです。
なお、先程つけた頂点番号は\ ord\ と一致します。

ord[ v ] = \ 頂点\ v \ に初めて到達した時刻
low[ v ] = \min \{ ord [ u ]\ |\ u:\ 頂点 \ v\ からDFS木上の辺を葉方向に0回以上、後退辺を高々1回以下辿って到達できる頂点\} \

↓こんな感じ

f:id:tmg_dayo:20220109140736p:plain

さて、操作後のグラフが強連結でないと仮定します。すると仮定より、ある頂点\ w\ から頂点\ 0\ には辿り着けないことがわかります。
(証明:DFS木の定義上、頂点\ 0\ からは任意の頂点に辿り着けることから、任意の頂点から頂点\ 0\ に辿り着けたら自動的に強連結になってしまうため。)

このとき、ある頂点\ v\ について、low[v] = v\ が成立します。
(証明:low\ の定義より、v\ から頂点番号\ low[v]\ の頂点までは辿ることができるので、\ low[v] < v\ となる場合はより番号が小さい頂点に到達できることになってしまい、これを繰り返すと最終的に\ 0\ に到達できてしまうため。)

また、DFS木の作り方から、ある頂点\ u(< v)\ について、DFS木上の辺\ u \rightarrow v\ が存在します。

この辺について\ ord[u] < low[v]\ が成立していますが、
この式が成立しているとき、H\ 上の辺\ (u, v)\ は橋になっているという有名な事実があります。
(「橋 列挙 アルゴリズム」などで検索すると色々出てきます。こちらなど→グラフ探索アルゴリズムとその応用

よって、「上記操作で強連結にできない→橋が存在する」が証明できたため、この操作でうまくいくことが示されました。

コード(Python3)

提出コード(Python3:54ms)

def main():
    # 入力
    N, M = map(int, input().split())
    AB = [list(map(int, input().split())) for _ in [0]*M]
    C = list(map(int, input().split()))
    # 隣接グラフGの構築
    G = [[] for _ in [0]*N]
    for a, b in AB:
        G[a-1].append(b-1)
        G[b-1].append(a-1)
    # 辺に番号をつける
    edge = dict()
    for i in range(M):
        a, b = AB[i]
        edge[(a-1, b-1)] = i
    # 各頂点を始点にDFSを行い、両端のCが同じ辺のみを抽出、連結成分ごとに分解
    # 両端のCが異なる辺は即座に向き付け可能
    ans = [None]*M  # 各頂点の向き
    visited = [False]*N  # 探索済みかどうか
    G2 = []  # 各連結成分を保存
    for s in range(N):
        if visited[s]:
            continue
        visited[s] = True
        stack = [s]  # 探索用スタック
        H = set()  # 連結成分の辺を保存、重複の可能性があるのでsetで
        while stack:
            u = stack.pop()
            for v in G[u]:
                # 決まらない場合
                if C[u] == C[v]:
                    # 辺を保存
                    H.add((u, v))
                    if not visited[v]:
                        stack.append(v)
                        visited[v] = True
                # 決まる場合
                elif C[u] > C[v]:
                    if (u, v) in edge.keys():
                        ans[edge[(u, v)]] = "->"
                    else:
                        ans[edge[(v, u)]] = "<-"
                else:
                    if (u, v) in edge.keys():
                        ans[edge[(u, v)]] = "<-"
                    else:
                        ans[edge[(v, u)]] = "->"
        if H:
            # リストに直して格納
            G2.append(list(H))
    # 各連結成分について、DFSを行い木を作る
    edge_count = [0]*N  # 何番目の辺まで見たか
    for H in G2:
        # Hは隣接グラフになっていないので、隣接グラフH_graphを作る
        H_graph = [[] for _ in [0]*N]
        for u, v in H:
            H_graph[u].append(v)
            H_graph[v].append(u)
        root = H[0][0]  # 適当な頂点を根とする
        dist = [-1]*N  # 根からの距離
        dist[0] = 0
        stack = [root]
        # DFSを行う
        while stack:
            u = stack[-1]
            # 全ての辺を見終わっていた場合
            if edge_count[u] >= len(H_graph[u]):
                stack.pop()
                continue
            # 次の探索先を選ぶ
            v = H_graph[u][edge_count[u]]
            edge_count[u] += 1
            # 探索先が未訪問だった場合
            if edge_count[v] == 0:
                visited[v] = True
                dist[v] = len(stack)
                stack.append(v)
                # DFS木の根方向から葉方向に向き付け
                if (u, v) in edge.keys():
                    ans[edge[(u, v)]] = "->"
                else:
                    ans[edge[(v, u)]] = "<-"
        # 後退辺は根方向に向き付け
        for u, v in H:
            if (u, v) not in edge.keys():
                v, u = u, v
            # 向き付け済みの場合はスルー
            if ans[edge[(u, v)]] is not None:
                continue
            if dist[u] > dist[v]:
                ans[edge[(u, v)]] = "->"
            else:
                ans[edge[(u, v)]] = "<-"
    # 出力
    for elm in ans:
        print(elm)
main()

【AtCoder】ARC114C:Sequence Scores(600点)

問題

ARC114C:Sequence Scores

問題の概要

すべての項が\ 0\ である長さ\ N\ の数列\ X\ に対して以下の操作を繰り返し、各項の値が\ 1\ 以上\ M\ 以下の数列\ A\ を作ることを考える。

  • 区間\ [l, r]\ \ 1\leq m\leq M\ を選択し、各\ l\leq i\leq r\ について、X_i\ \ \max(X_i, m)\ で置き換える。

\ X\ から\ A\ を作るための最小回数を\ f(A)\ とおいたとき、すべての数列\ A\ に対する\ f(A)\ の総和を\ 998244353\ で割った余りを求めよ。

制約

  • \ 1\leq N, M\leq5000\
  • \ N, M\ は整数

解法

方針

f(A)\ を数列\ A\ を作るためのコストと捉えて問題を考えてみます。

まず、数列の各項に対して1つ1つ左から順番に上記の操作を適用した場合を考えると、明らかに任意の\ A\ に対して、N\ 回の操作で\ A\ を作れることがわかります。作れる数列は\ M^N\ 通りなので、f(A)\ の和は\ NM^N\ 以下です。

最悪でも操作に\ N\ 回しかかからないことがわかりましたが、実際にはもっとコストを削減できる場合もあるはずです。
関数\ f\ を、項数が\ N\ の場合以外にも拡張して考えてみます。
例えば、f(\{3\})\ は明らかに\ 1\ ですが、これに\ 3\ を追加した\ f(\{3, 3\})\ も同様に\ 1\ になります。

つまり、空の数列\ A'\ \ A\ の項を初項から順番に1つずつ追加していくことを考えたときに、条件次第では追加の前後で\ f(A')\ の値は変わらない、すなわちノーコストで項が追加できることがわかります。

すべての数列\ A\ について、ノーコストで項を追加できたインデックスを数え上げて、NM^N\ から引く方針で答えが出せそうな気がしてきます。

定式化

上の方針で出てきた“ノーコストで追加できる項”の個数を具体的に数式の形で表すことを考えてみましょう。
\ 1\leq n \leq N, \ 1\leq m \leq M\ に対し、

\ g(n, m)\
 =\ n\ 番目の項として\ m\ を追加したときに、最小の操作回数が変化しなかったような長さ\ N\ の数列の個数」

と定義します。
”変化しなかった”と過去形で書いているのは、N\ 個の項すべてを追加し終わった後の最終的な数列の個数を数える必要があるためです。

すべての\ n, m\ について\ g(n, m)\ の和をとることにより、削減できるコストを重複・数え漏れなく数え上げることができます。
また、1\ 番目の項を追加する場合は必ずコストがかかるので、n= 1\ の場合は必ず\ g(n, m)= 0\ となり、n\ \ 2\ 以上のときのみを考えればいいこともわかります。

以上より、関数の和を求める問題を、数列の数え上げの問題へ帰着させることができ、答えを


\begin{aligned}
\sum_{A}f(A)=NM^N-\sum_{n=2}^{N}\sum_{m=1}^{M}g(n, m)
\end{aligned}

と表すことができました。

ノーコストで追加できる条件

定式化できたところで次に、最小の操作回数が変化しない(=ノーコストで追加できる)条件を調べてみましょう。
数列をブロックで表すこととして、いくつか例を載せてみます。

例:4番目の要素として、2を追加するとき(\ n=4, m=2\

f:id:tmg_dayo:20220109014227j:plain

上の例を観察すると、\ n\ 個目の要素として\ m\ を追加するときに、次のような条件を満たせばノーコストで追加できることがわかります。

① ある\ 1\leq i < n\ に対し、\ A_i = m\ が成り立つ
② ①を満たす最大の\ i\ に対して、「\ i < j < n\Longrightarrow A_j > m \ 」が成り立つ

条件を図示すると以下のとおりです。

f:id:tmg_dayo:20220109015345p:plain

上の図の青い部分の数列の選び方の総数を左から順番に計算すると、それぞれ\ M^{i-1}, (M-m)^{n-i-1}, M^{N-n}\ となります。
i\ \ 1\leq i < n-1\ の範囲を動くことから、g(n, m)\ は次の式で表すことができます。


\begin{align}
g(n, m) &= \sum_{i=1}^{n-1}M^{N-n+i-1} \left(M-m\right)^{n-i-1} \\
&= \sum_{i=2}^{n}M^{N-\left(n-i\right)-2} \left(M-m\right)^{n-i} \\
&= \sum_{i=0}^{n-2}M^{N-i-2} \left(M-m\right)^{i}
\end{align}

以上の議論より、答えを以下の形で表せることがわかりました。


\begin{align}
\sum_{A}f(A)=NM^N-\sum_{n=2}^{N}\sum_{m=1}^{M}\sum_{i=0}^{n-2}M^{N-i-2} \left(M-m\right)^{i}
\end{align}

これは\ O(N^2M)\ で計算できます。

高速化

このままではTLEしてしまうので、最後に計算量削減を行います。
先程の式の第2項は以下のように変形できます。


\begin{align}
& \sum_{n=2}^{N}\sum_{m=1}^{M}\sum_{i=0}^{n-2}M^{N-i-2} \left(M-m\right)^{i} \\
&= \sum_{n=2}^{N}\sum_{i=0}^{n-2}M^{N-i-2}\left(\sum_{m=1}^{M} \left(M-m\right)^{i}\right) \\
&= \sum_{n=2}^{N}\sum_{i=0}^{n-2}M^{N-i-2}\left(\sum_{m=0}^{M-1} m^{i}\right)
\end{align}

ここで、s(i) = \sum_{m=0}^{M-1} m^{i}\ とおくと、これはすべての\ 0 \leq i \leq n-2\ に対して計算しても\ O(NM)\ しかかかりません。

したがって、事前にすべての\ s(i)\ を計算しておくことで、


\begin{align}
\sum_{A}f(A)=NM^N-\sum_{n=1}^{N}\sum_{i=0}^{n-2}M^{N-i-2}s(i)
\end{align}

と二重和の形で書くことができるため、全体として\ O(NM)\ まで削減できます。これは十分に高速なのでAC可能です。
なお、各式に出てくる累乗についてもその都度求めるのは時間がかかるため、これも事前に計算しておきましょう。

コード(PyPy3)

提出コード(PyPy3:1208ms)
PythonはTLEでした(涙)

def main():
    # 入力、modの定義
    N, M = map(int, input().split())
    mod = 998244353
    # 配列の事前計算(POW[i][j] = pow(i, j) % mod)
    POW = [[1]*5001 for _ in [0]*5001]
    for i in range(5001):
        tmp = 1
        for j in range(1, 5001):
            tmp = tmp*i % mod
            POW[i][j] = tmp
    # s(i)の事前計算
    s = [0]*(N-1)
    for i in range(N-1):
        tmp = 0
        for m in range(M):
            tmp += POW[m][i]
        s[i] = tmp % mod
    # 計算(本体)
    ans = N*POW[M][N] % mod
    for n in range(2, N+1):
        for i in range(0, n-1):
            ans -= POW[M][N-i-2]*s[i]
        ans %= mod
    # 出力
    print(ans)
main()