SRM726 div2 easy StringHalving

概要

英アルファベットから成る文字列Sが与えられる。文字列Sは同じ種類の文字を2個ずつ含んでいる。この文字列Sを同じ種類の文字が1個ずつになるように文字を消去する。辞書順最小になるときに文字を消去したとき、文字列の最初の文字を出力しろ。

解法

辞書順の制約を無視して消去の方法について考える。先頭から順番に見ていき、同じ文字がはじめて2箇所現れた位置を考えるとその位置より後の文字が先頭に来ることはない。逆にその位置よりも前の文字はどれでも先頭に取ることが出来る。したがって同じ文字がはじめて2箇所現れた位置までの中で辞書順で最小の文字が答えになる。

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define IN(a, b, x) (a<=x&&x<b)
#define MP make_pair
#define PB push_back
const int INF = (1LL<<30);
const ll LLINF = (1LL<<60);
const double PI = 3.14159265359;
const double EPS = 1e-12;
const int MOD = 1000000007;
//#define int ll

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

bool used[30];
class StringHalving {
   public:
   string lexsmallest(string s)
  {
    memset(used, false, sizeof(used));
    char res = 'z';
    REP(i, s.size()-1) {
      if(used[s[i]-'a']) {
        string ret = "";
        ret += res;
        return ret;
      }
      chmin(res, s[i]);
      used[s[i]-'a'] = true;
    }
    assert(false);
  }
};