TopCoder SRM 705 Div2 Med (Div1 Easy): AlphabetOrder

(追記: Div1 Easy と Div2 Med が完全に同じ問題なのでタイトルを変更しました)

今回のSRMは大勝利したので嬉しい。Medが個人的に良問だと思ったので記事を書きます。

問題概要

原文 → TopCoder Statistics - Problem Statement

英小文字のみで構成された文字列がいくつか与えられる。各文字列について、先頭から順に見た時にアルファベットが昇順に並んでいるような文字列は「良い文字列」と呼ばれる。アルファベットの順番を適切に定義したとき、全ての文字列を「良い文字列」にできるならば Possible を、できないならば Impossible を出力せよ。

解説

愚直解法 (アルファベットの順番を全て試す) は、 通りもあるため当然試せません。

そこで、グラフに落として考えてみましょう。文字列の 文字目から 文字目 に向かって、有向辺を張ります。これを全ての の組み合わせについて行います。

例えば、文字列 abcd の場合は、以下のようになります。

常に左側のノードから右側のノードに向かって辺を張っているため、グラフが DAG になっていることがわかりますね。

さて、このグラフに意地悪をしてみましょう。文字列 ba を考えます。この文字列と abcd の1文字目・2文字目を考慮すると、明らかに全ての文字列を「良い文字列」にすることができませんね。実際に辺を張るとどうなるでしょうか？

このように、閉路ができてしまいます。閉路があるということは、アルファベットの順番を指し示していたはずの矢印がぐるぐる回っていることになりますので、Impossible であることと同義ですね。

以上より、この方針で解いていけばよいです。

• 各文字列に対して、 を満たす全ての の組み合わせを考え、( 文字目のアルファベット) ( 文字目のアルファベット) の方向に有向辺を張る
• できたグラフが DAG であれば Possible で、DAG でなければ Impossible

あとは DAG の判定をどうするかですが、これについては過去に @Darsein 先生から教えを受けていたのでした。

@_TTJR_ トポロジカルソートするだけ

— DはD論のD (@Darsein) 2016年12月27日

トポロジカルソートは入次数0のノードと、そのノードから出ている辺をどんどん消していくことで得られます。閉路があると入次数0 のノードがいずれ出来なくなるので、閉路判定は トポロジカルソートの結果のサイズがグラフの頂点数と等しいかどうか でできるというわけです。今回の問題の場合、連結でないグラフができる場合がありますが、閉路さえなければトポロジカルソートのサイズは頂点数と等しくなるので問題ないです。

ちなみに、ワーシャルフロイドでも閉路判定できるのですが、連結でないグラフの場合少し面倒なことに加え、頂点数が多くなると TLE するのでイマイチです。(この問題の場合は TLE しませんが)

ソースコード

トポロジカルソートのソースコードは省略します。

class AlphabetOrderDiv2 {
    public:
    string isOrdered(vector<string> words) {
        Graph(int) G(26);
        set<int> s;
        rep(i,0,words.size()) {
            rep(j,0,words[i].length()) {
                int d = words[i][j] - 'a';
                s.insert(d);
                rep(k,j+1,words[i].length()) {
                    int d2 = words[i][k] - 'a';
                    if(d != d2) {
                        G[d].pb(Edge<int>(d2, 1));
                    }
                }
            }
        }

        vector<int> v = tpsort_Kahn(G);
        if(v.size() != 26) return "Impossible";
        else return "Possible";
    }
};

次で青になれたらいいなあ・・・

東京工業大学プログラミングコンテスト2015 D: 文字列と素数

競プロに逃げすぎてレポートが進みません。

問題概要

原文 → D: 文字列と素数 - 東京工業大学プログラミングコンテスト2015 | AtCoder

文字列 が与えられる。各文字を、同じ文字は同じ数字・違う文字は違う数字になるように '1', '3', '5', '7', '9' のいずれかに変換する。文字列を素数に変換できるならばその素数を出力し、できないならば -1 を出力せよ。

解説

map と permutation を使って全探索するだけです。next_permutation とかそんなに使わないので備忘録的に書きました。

文字列を反転させておくことで計算が楽になります。文字列から数字にしたりとか、桁数がやたら多かったりとかするときはこれで幸せになることが多い気がします。

ソースコード

bool isprime(int n) {
    if(n == 1) return false;
    for(int i=2; i*i<=n; i++) {
        if(!(n%i)) return false;
    }
    return true;
}

signed main() {
    string s; cin >> s;
    map<char, int> m;
    int cnt = 0;
    reverse(s.begin(), s.end());
    rep(i,0,s.length()) {
        if(!m.count(s[i])) {
            m[s[i]] = cnt++;
        }
    }

    if(cnt > 5) {
        cout << -1 << endl;
        return 0;
    }
    int a[] = {1, 3, 5, 7, 9};
    do {
        int d = 1;
        int num = 0;
        rep(i,0,s.length()) {
            num += d * a[ m[s[i]] ];
            d *= 10;
        }
        if(isprime(num)) {
            cout << num << endl;
            return 0;
        }
    }while(next_permutation(a, a+5));
    cout << -1 << endl;
    return 0;
}

AOJ 0037: Path on a Grid

バグが取れなくて相当苦労した。

問題概要

原文 → 格子状の経路 | Aizu Online Judge

格子の各辺が壁であるかどうかの情報が与えられる。壁に右手をついたまま1周するときの経路を出力せよ。

解説

前回の記事 と同様の方法で解いてみました。

今見ている方向を とおくと、

• 右手に壁がない場合、 の方向に向き直す
• 進行方向に壁がある場合、 の方向に向き直す

というように動けばよいです。終了条件にも気をつけましょう。

ソースコード

#define S 6
// right, down, left, up
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};

int main() {
    bool board[S][S][4] = {};
    rep(i,0,9) {
        int l, n;
        if(i % 2 == 0) l = 4;
        else l = 5;
        rep(j,0,l) {
            scanf("%1d", &n);
            if(n == 1) {
                if(i % 2 == 0) {
                    board[i/2][j+1][1] = true;
                    board[i/2+1][j+1][3] = true;
                }
                else {
                    board[i/2+1][j][0] = true;
                    board[i/2+1][j+1][2] = true;
                }
            }
        }
    }

    string d = "RDLU";
    string ret;
    int dir = 0;
    int nx = 0, ny = 1;
    for(int i=0; i<150; i++) {
        if(nx == 1 && ny == 0 && dir == 2) break;
        if(nx == 0 && ny == 0 && dir == 3) break;
        int x, y;
        x = nx + dx[dir], y = ny + dy[dir];
        if(board[nx][ny][(dir + 1) % 4] == 0) {
            dir = (dir + 1) % 4;
            nx = nx + dx[dir], ny = ny + dy[dir];
        }
        else if(board[nx][ny][dir] == 1) {
            ret += d[dir];
            dir = (dir - 1 + 4) % 4;
        }
        else {
            ret += d[dir];
            nx = x, ny = y;
        }
    }
    cout << ret << endl;
    return 0;
}

自分の実装の方法が悪いのか、バグ直しに相当時間がかかってしまった・・・。他の実装方法も考えたい。まずは enum 使って書きなおしたほうがいいよなあ。