SRM 516 (div2) Exercise

本番は遅かったので不参加。あとで解いてみた。

250がいつもよりちょっと難しめ、500は普通、1000はいつもより簡単に感じた。

250 NetworkXZeroOne

'o'と'x'からのみなる文字列を送信する。ネットワークの不調のため文字列のいくつかの部分が壊れてしまい、受信側では、"o?x?"や"????x"のような状態になっている。この文字列を復元する。ただし、文字列のすべての偶数部分列に含まれる'o'と'x'の数は等しい。

　少なくとも一つの'?'の前、もしくは後ろは、'o'か'x'になっているはず。なので、それとは違う文字を'?'に入れてやればいい。これを'?'が無くなるまで繰り返す。今回はサイズが小さいので愚直に文字全体をなめていっても間に合う。サイズが大きい場合は、queueをつかって、新しくfixした部分の周りだけ見るという工夫(priority_queueを使ってdijkstraを高速化するときと同じようなやり方)をすると高速化できる。

500 NetworkXOneTimePad

バイナリの平文（'0'と'1'からのみ構成される平文）を、あるキー文字列を使って暗号化する。

平文の集合と、暗号文の集合が与えられるので、キーとなりうる文字列の数を求める。キーとなりうるとは、すべての暗号文は、ある平文とキーから構成することができる場合を指す。

　要するに、暗号化を写像fに見立てた場合、fがonto(surjective)であればいい。

方針としては、平文集合[i]から暗号集合[0]が作られていると考えて、キーをfix。そのキーに対する写像fがontoであるなら、そのキーは妥当と判断。これをすべてのiで試す。O(n^4)解で書いたけど、適切な場所でpre-calculationすれば、O(n^3)で解ける。

1000 NetworkXMessageRecovery

アルファベットの大文字、小文字のみからなる文字列xがある。ただし、この文字列のなかに同じ文字は2回以上現れない。xの部分文字列（必ずしも連続していない）が複数個与えられるので、xが何かを予想する。xが複数個考えられる場合は、辞書順がもっとも小さいものを出力する。

例)

{"acd", "bce"}　-> "abcde"

{"ed", "dc", "cb", "ba"} -> "edcba"

　それぞれの部分列から、どの文字がどの文字より先に現れるべきかが分かる。ある文字aが別の文字bに先行する場合は、aからbへの有向枝があると考えてグラフを構成する。これをトポロジカルソートしてあげればいい。ただしトポロジカル順序の決定は辞書順が小さいものから行うようにする。O(n^3)。