【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点)
強連結な有向グラフの作り方がわからなかったので、備忘録として。
問題
前提知識
- Lowlink
問題の概要
頂点辺の単純な無向グラフと正整数列が与えられる。
の各頂点から到達できる頂点の数(自身も含む)が、ちょうどになるように各辺に向き付けせよ。
制約
- 与えられるグラフに自己ループや多重辺は存在しない(非連結はあり得る)
- 与えられる入力には必ず解が存在する
解法
問題の言い換え
内の辺を適当にとってみます。
実は、とが一致していなければ、即座に向き付け可能です。
もしならば、明らかに辺の向きはとするしかありません。とした場合、から辿れる頂点はからも辿れるため、となってしまうためです。
一方で、の場合には、とは相互に到達できる必要があります。
この条件がを満たす任意の辺について成立している必要があることから、結局以下の問題が解ければよいです。
からを満たす辺のみを取り出したグラフを新たにとする。
の各連結成分に対して、相互に到達可能(=強連結)になるように向き付けせよ。
(ただし、問題の制約上、強連結になるように向き付けできることが保証されている。)
強連結なグラフの作り方
結論から言うと、強連結にできることが保証されている任意のグラフに対して、以下の操作で構築可能です。
連結グラフの頂点を一つ選び(とする)、からDFSを行い、通過した頂点と辺のみを使った根付き木(DFS木)を作る。DFS木上の辺を「根→葉」、それ以外の辺(後退辺)を「葉→根」となるようにグラフに向き付けを行うと、この連結成分は強連結になっている。
公式解説では詳細な証明は省略されていたので、上記操作で構築できることの証明を以下で行います。
操作の証明
方針
橋が存在するグラフは、明らかに強連結にできないことに注目します。つまり、今回与えられるグラフには橋が存在しません。
- 上記操作後のグラフが強連結でないと仮定した場合、には橋が存在する
ということを証明することで、橋が存在しないにおいては、操作により必ず強連結にできることを証明します。
本体
まず、適当な頂点を根として選び、これをとします。
を始点としてDFSを行うことでDFS木を作り、辿った順番に頂点に番号をつけます。さらに、先程の操作の説明通り、DFS木上の辺を「根→葉」、後退辺を「葉→根」となるようにグラフに向き付けを行います。
ここで、Lowlinkという概念を導入します。詳細は省略しますが、定義は以下のとおりです。
なお、先程つけた頂点番号はと一致します。
頂点に初めて到達した時刻
頂点からDFS木上の辺を葉方向に0回以上、後退辺を高々1回以下辿って到達できる頂点
↓こんな感じ
さて、操作後のグラフが強連結でないと仮定します。すると仮定より、ある頂点から頂点には辿り着けないことがわかります。
(証明:DFS木の定義上、頂点からは任意の頂点に辿り着けることから、任意の頂点から頂点に辿り着けたら自動的に強連結になってしまうため。)
このとき、ある頂点について、が成立します。
(証明:の定義より、から頂点番号の頂点までは辿ることができるので、となる場合はより番号が小さい頂点に到達できることになってしまい、これを繰り返すと最終的にに到達できてしまうため。)
また、DFS木の作り方から、ある頂点について、DFS木上の辺が存在します。
この辺についてが成立していますが、
この式が成立しているとき、上の辺は橋になっているという有名な事実があります。
(「橋 列挙 アルゴリズム」などで検索すると色々出てきます。こちらなど→グラフ探索アルゴリズムとその応用)
よって、「上記操作で強連結にできない→橋が存在する」が証明できたため、この操作でうまくいくことが示されました。
コード(Python3)
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点)
問題
問題の概要
すべての項がである長さの数列に対して以下の操作を繰り返し、各項の値が以上以下の数列を作ることを考える。
- 区間とを選択し、各について、をで置き換える。
からを作るための最小回数をとおいたとき、すべての数列に対するの総和をで割った余りを求めよ。
制約
- は整数
解法
方針
を数列を作るためのコストと捉えて問題を考えてみます。
まず、数列の各項に対して1つ1つ左から順番に上記の操作を適用した場合を考えると、明らかに任意のに対して、回の操作でを作れることがわかります。作れる数列は通りなので、の和は以下です。
最悪でも操作に回しかかからないことがわかりましたが、実際にはもっとコストを削減できる場合もあるはずです。
関数を、項数がの場合以外にも拡張して考えてみます。
例えば、は明らかにですが、これにを追加したも同様にになります。
つまり、空の数列にの項を初項から順番に1つずつ追加していくことを考えたときに、条件次第では追加の前後での値は変わらない、すなわちノーコストで項が追加できることがわかります。
すべての数列について、ノーコストで項を追加できたインデックスを数え上げて、から引く方針で答えが出せそうな気がしてきます。
定式化
上の方針で出てきた“ノーコストで追加できる項”の個数を具体的に数式の形で表すことを考えてみましょう。
各に対し、
「番目の項としてを追加したときに、最小の操作回数が変化しなかったような長さの数列の個数」
と定義します。
”変化しなかった”と過去形で書いているのは、個の項すべてを追加し終わった後の最終的な数列の個数を数える必要があるためです。
すべてのについての和をとることにより、削減できるコストを重複・数え漏れなく数え上げることができます。
また、番目の項を追加する場合は必ずコストがかかるので、の場合は必ずとなり、は以上のときのみを考えればいいこともわかります。
以上より、関数の和を求める問題を、数列の数え上げの問題へ帰着させることができ、答えを
と表すことができました。
ノーコストで追加できる条件
定式化できたところで次に、最小の操作回数が変化しない(=ノーコストで追加できる)条件を調べてみましょう。
数列をブロックで表すこととして、いくつか例を載せてみます。
例:4番目の要素として、2を追加するとき()
上の例を観察すると、個目の要素としてを追加するときに、次のような条件を満たせばノーコストで追加できることがわかります。
① あるに対し、が成り立つ
② ①を満たす最大のに対して、「」が成り立つ
条件を図示すると以下のとおりです。
上の図の青い部分の数列の選び方の総数を左から順番に計算すると、それぞれとなります。
はの範囲を動くことから、は次の式で表すことができます。
以上の議論より、答えを以下の形で表せることがわかりました。
これはで計算できます。
高速化
このままではTLEしてしまうので、最後に計算量削減を行います。
先程の式の第2項は以下のように変形できます。
ここで、とおくと、これはすべてのに対して計算してもしかかかりません。
したがって、事前にすべてのを計算しておくことで、
と二重和の形で書くことができるため、全体としてまで削減できます。これは十分に高速なので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()