ABC097 C D

C K-th Substring

Submission #2500157 - AtCoder Beginner Contest 097 | AtCoder

問題概要

文字列sと整数Kが与えられる。sの辞書順K番目のsubstringを求めよ。

取った方針

setはソートされており順番に要素を取り出せ、かつ重複を許さないデータ構造である。
文字列に使われている文字を1文字ずつsetに入れていくことで文字列に使われている文字を重複せず得ることができる。このsetをcharSetとする。
次に、charSetから1文字ずつ取り出し(setはソート済みなので辞書順で小さい順に出てくる)、sを1文字目から全探索しその文字を探す。
その文字が見つかったら長さK以下の部分文字列を全列挙し、ansSet(set)に追加する。ansSetの要素数がKを超えたら全探索をやめ、K番目の文字列を出力すればそれが解となる。
ただし、ansSetの要素数がKを超えているか判定するのはcharSetから1文字取り出した瞬間である。(ansSetの要素数がKを超えてもその後ろにもっと辞書順で小さい文字列が存在する可能性があるため)

正しい方針

同上

得られた知見

・setの使い方、setを使おうという気持ち

解くのに必要な要素

・set

周辺調査によって得られた知見

特になし

D Equals

Submission #2502844 - AtCoder Beginner Contest 097 | AtCoder

所見

同じ連結成分内では好きに値を入れ替えられる、まで確信に至らず、そんな気がする、というだけでUnionFindを張り付けて通してしまったので、安定してこのパフォーマンスが出せるかというと、うーん、という感じ。
この問題がグラフに見えて連結判定問題に見える、というのは精進の成果かなあと思う。

問題概要

1からNまでの整数を並び替えた順列とM個の(x,y)の組が与えられた時、i番目の組を(xi,yi)とする。1<=j<=Mについて、xj番目の数とyj番目の数を入れ替えることができる時、i番目にiを置くことができるiはいくつあるか。

取った方針

(x,y)の組をエッジと見ると、M個の(x,y)をグラフとして見ることができる。
「i番目にiを置くことができる」というのは、iがj番目にあるとき、複数の交換を組み合わせてi番目の数とj番目の数を交換することができる、というのと同値であるので(ほんまか)、グラフ上でiからjへのパスがあるか、で求めることができる。
パスがあるかどうかだけならUnionFindで求めることができるので、ネッツからUnionFindの実装をコピペするとACできる。

正しい方針

同上

得られた知見

・libalgoにあるUnionFindの使い方
・変換を繰り返す系の問題はグラフアルゴリズムの使用を疑う(感覚的にはこれ)
・i番目とj番目を入れ替える、という操作を一つの辺としてみなすことでグラフアルゴリズムを適用できる可能性がある。
・一般化すると、操作として2つの数値(src からdst に変換、とかでもいいし対象を交換、でもいいし、そんな感じ)とコストが与えられる場合はそれを辺としたグラフアルゴリズムの使用を考えるべき？(まさかり求)

解くのに必要な要素

・UnionFind
・i番目とj番目を入れ替える、という操作をedge(i,j)と見なす

周辺調査によって得られた知見

特になし