2159 Ancient Cipher

古代の暗号を暴け！


以下の２種類の暗号化方式がある。

• Substitution cipher　あるアルファベットを他のアルファベットに置き換える
• Permutation cipher　文字列の順番を入れ替える

１つの暗号化方式だけだと弱いので、組み合わせて使う。

問題は２つの文字列がこの暗号化方式によって可換であるかを求めるというもの。

２つの文字列のアルファベットを出現頻度順に並べて、それが一致したらOKという方針で書いたら通った。
（まったく暗号化していない"APPLE"と"APPLE"もYESを出力してしまうようになってるけど通った。。。）

問題自体は簡単だけどちょっと詰まった箇所（というより未だにわかってないのだが）があるから備忘録。

最初に通ったコード

#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
#include<functional>

using namespace std;

int main() {
    char cipher[101];
    char original[101];
    scanf("%s", cipher);
    scanf("%s", original);
    int cc[26];
    int oc[26];
    memset(cc, 0, sizeof(cc));
    memset(oc, 0, sizeof(oc));
    priority_queue<int> cq;
    priority_queue<int> oq;
    for (int i = 0; cipher[i] != '\0'; ++i) {
	++cc[cipher[i]-'A'];
	++oc[original[i]-'A'];
    }
    for (int i = 0; i < 26; ++i) {
	if (cc[i] != 0) cq.push(cc[i]);
	if (oc[i] != 0) oq.push(oc[i]);
    }
    while (!cq.empty()) {
	if (cq.top() != oq.top()) {
	    printf("NO\n");
	    return 1;
	}
	cq.pop();
	oq.pop();
    }
    printf("YES\n");
}

もうなんか新しもの好き全開のコード。priority_queue使いたかったんだね…
でもちょっと遅かった(32MS)
おろろが16MSで通してたから頭の片隅にあったsortを使ってみることに。

#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
#include<functional>

using namespace std;

int main() {
    char cipher[101];
    char original[101];
    scanf("%s", cipher);
    scanf("%s", original);
    int cc[26];
    int oc[26];
    memset(cc, 0, sizeof(cc));
    memset(oc, 0, sizeof(oc));
    for (int i = 0; cipher[i] != '\0'; ++i) {
	++cc[cipher[i]-'A'];
	++oc[original[i]-'A'];
    }
    sort(cc, cc+26, greater<int>());
    sort(oc, oc+26, greater<int>());
    for (int i = 0; cc[i] != 0; ++i) {
	if (cc[i] != oc[i]) {
	    printf("NO\n");
	    return 1;
	}
    }
    printf("YES\n");
}

ccとocを直接ソートして、あとは１つめのコードと同じにしたつもりなんだけど
通らないっ！

課題だ