Beautiful String

問題概要

アルファベットに1〜26の点数が付いている。与えられた文字列が最高得点になる時の得点を計算せよ。

考え方

  • 多い文字に高い得点付ければいいんじゃない？
  • 文字数カウントして個数をソートすれば大丈夫っぽい。

コード

#include <algorithm>
#include <cctype>
#include <cstdlib>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

int Solve() {
  string s;
  vector<int> count(26, 0);
  getline(cin, s);
  for (int i = 0; i < s.size(); ++i) {
    if (!isalpha(s[i])) continue;
    ++count[tolower(s[i]) - 'a'];
  }
  sort(count.begin(), count.end());
  
  int cost = 0;
  for (int i = 0; i < 26; ++i) {
    cost += (i + 1) * count[i];
  }
  return cost;
}

int main(void) {
  string n_str;
  getline(cin, n_str);
  int n = atoi(n_str.c_str());
  for (int i = 0; i < n; ++i) {
    cout << "Case #" << (i + 1) << ": " << Solve() << "\n";
  }
  return 0;
}

Balanced Smileys

問題

:) やら :( やらが含まれる文字列で、カッコの対応が付いているかチェックせよ。

考え方

  • 考慮すべきカッコに種類があるわけではない。
  • Smiley が関係無い場合、カッコを潜っている段数 n を見るだけでいいテンプレ問題が有るのを思い出す。
    • 途中は n>=0 をキープし、最後に n==0 となれば OK
  • カッコの前に : があったら Smiley になる可能性があるから分岐させればいい。
  • こんなときは DP すると良さ気。
  • 最初のカッコの時だけ : チェックしない例外とか面倒だからスペース入れておこ…

コード

#include <algorithm>
#include <cstdlib>
#include <iostream>
#include <set>
#include <string>
using namespace std;

bool Solve() {
  string line;
  getline(cin, line);
  line = ' ' + line;
  set<int> a, b;
  set<int>* st = &a, * st2 = &b;
  st->insert(0);
  for (int i = 0; i < line.size(); ++i) {
    if (line[i] != '(' && line[i] != ')')
      continue;
    st2->clear();
    set<int>::iterator itr;
    if (line[i] == '(') {
      for (itr = st->begin(); itr != st->end(); ++itr)
	st2->insert(*itr + 1);
      if (line[i - 1] == ':')
	for (itr = st->begin(); itr != st->end(); ++itr)
	  st2->insert(*itr);
    } else if (line[i] == ')') {
      for (itr = st->begin(); itr != st->end(); ++itr)
	if (*itr > 0)
	  st2->insert((*itr) - 1);
      if (line[i - 1] == ':')
	for (itr = st->begin(); itr != st->end(); ++itr)
	  st2->insert(*itr);
    }
    swap(st, st2);
  }

  return (st->find(0) != st->end());
}

int main(void) {
  string line;
  getline(cin, line);
  const int n = atoi(line.c_str());
  for (int i = 0; i < n; ++i) {
    cout << "Case #" << (i + 1) << ": "
	 << (Solve() ? "YES\n" : "NO\n");
  }
  return 0;
}

Find the Min

問題

数列の内、頭の k 項が知らされている。残りについては、"直前 k 項に現れない、最小の非負整数"という条件もわかっている。この時数列の最後 n 項目は何か。

考え方

  • 初項 k 項については乱数だけど 10^9 まである掛け算だから 64bit 使おう
  • 未知部分については、とりあえず k+1 より大きい数が現れるはずはない
  • むしろ k+1 周期でループするんじゃん。
  • まずは m[0..k] を計算しておこう。
  • [k] だけは疑似乱数の枠じゃないから別計算だな。
  • m[k+1..2k+1] を求められれば m[(n-1)%(k+1)] が答えじゃん。
  • 使える／使えない数のリストを持たないとなー。
  • 使える数は最小が云々だからsetで、使えないのは配列/vectorでいいか。

コード

#include <iostream>
#include <vector>
#include <set>
using namespace std;
typedef long long int64;

void PseudoRand(const int n, vector<int>* data) {
  int64 a, b, c, r;
  cin >> a >> b >> c >> r;
  for (int64 i = 0; i < n; ++i) {
    (*data)[i] = static_cast<int>(a);
    a = (b * a + c) % r;
  }
}

int64 Solve() {
  int n, k;
  cin >> n >> k;

  // Input and generate
  vector<int> data(k + 1);
  PseudoRand(k, &data);

  // Set up
  vector<int> used(k + 1, 0);
  for (int i = 0; i < k; ++i) {
    const int d = data[i];
    if (d <= k + 1)
      ++used[d];
  }
  set<int> usable;
  for (int i = 0; i <= k; ++i) {
    if (used[i] == 0)
      usable.insert(i);
  }

  // Set m[k]
  {
    set<int>::iterator itr = usable.begin();
    data[k] = *itr;
    ++used[*itr];
    usable.erase(itr);
  }

  // Make m[(k+1) .. 2*(k+1)-1]
  for (int i = 0; i <= k; ++i) {
    const int d = data[i];
    if (d <= k + 1 && used[d] > 0) {
      --used[d];
      if (used[d] == 0)
	usable.insert(d);
    }

    set<int>::iterator itr = usable.begin();
    data[i] = *itr;
    usable.erase(itr);
  }

  return data[(n - 1) % (k + 1)];
}


int main(void) {
  int n;
  cin >> n;
  for (int i = 0; i < n; ++i) {
    cout << "Case #" << (i + 1) << ": " << Solve() << "\n";
  }
}