UTPC 2012 B問題

Tatsuya Yatagawa
Programming Contest

先日開催されたUTPC2012 (東京大学プログラミングコンテスト)のB問題の答えです。
解説をはじめたはいいが全部はたぶんできないし、いったいどこまで続くか・・・

http://utpc2012.contest.atcoder.jp/tasks/utpc2012_02

気を取り直して解説していくと、この問題はある文字の並びが、実は小説の8つの章であるのだけど、章が進むことに使える文字が減っていくので、小説を見てどういう順序で使える文字が減っていったかを答えよ、というものです。

実はこの問題は最後の8文字だけを見ても一般性を失わないらしく、最後の8文字がかけるように文字を減らしていけばいいらしいです。答えは一通りとは限らず、どれでも正解になります。

僕のたてた方針はそこまで賢いものではなくて、後ろから文字を見ていったときに、はじめて現れる文字を禁止文字として配列に入れていって、出てこなかった残り文字は適当な順序で同じように配列に入れて、最後に順序を逆転させて出力するというものです。

個人的にはこっちのアイディアの方がすぐ思いつくかなと思います。

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
#include <algorithm>
#include <limits.h>
#include <string.h>
#include <ctype.h>
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <stack>
using namespace std;

typedef unsigned long long ULL;
typedef vector<int> VI;
typedef pair<int, int> PII;

#define REP(i,n) for(int i=0; i<n; i++)
#define REPD(i,n) for(int i=n; i>=0; i--)

template <typename T> inline T tmax(T t1, T t2) { return t1 > t2 ? t1 : t2; }
template <typename T> inline T tmin(T t1, T t2) { return t1 < t2 ? t1 : t2; }

int main() {
    string s;
    vector<char> dst;
    set<char> out;
    cin >> s;

    REPD(i, s.size()-1) {
        if(out.find(s[i]) != out.end()) continue;
        dst.push_back(s[i]);
        out.insert(s[i]);
    }

    for(char c='A'; c<='H'; c++) {
        if(out.find(c) != out.end()) continue;
        dst.push_back(c);
        out.insert(c);
    }

    REP(i,8) {
        printf("%c", dst[8-i-1]);
    }
    printf("n");

    return 0;
}