MaximumCup2008に参加してきました - macbook air is so hot(低温やけど的な意味で)

結果はA->G->B->Dの４問ACで、前回２問しか解けなかった私は大変満足です。ふぇふぇふぇ。
MaximumCupは半分国語の問題のような気がします。

A

支持対象が無かった場合"No"になるんだけど、問題文によると「該当者なしの場合、町の人の回答は "No" という 2 文字の文字列のみである」とあって、さらに「候補者の名前は大文字と小文字は区別せず、空白文字は無視するものとする」とあるので"N o"->(空白除去)"No"とかも候補者名としてありうるかも、とか「世論調査の対象者数を "The number of pollees: n" の形式で出力せよ」のnは入力のnをそのまま出せば良いのか、とか" "->""も候補者名としてありうるかもとか、そこらへんが罠かもと思って対策しましたが、幸い一発ACだったので役に立ったのかどうか分かりません。

#include <iostream>
#include <map>
#include <vector>

using namespace std;

main () {
  string line;
  int n, CASE = 0;
  while (cin >> n, n) {
    getline(cin, line);
    map<string, int> m;
    for (int i = 0; i < n; i++) {
      getline(cin, line);
      if (line == "No") continue;
      string name;
      for (int i = 0; i < line.size(); i++) {
        if (!isspace(line[i])) {
          name += toupper(line[i]);
        }
      }
      m[name]++;
    }
    vector<pair<int, string> > v;
    for (map<string, int>::iterator it = m.begin(); it != m.end(); it++) {
      v.push_back(make_pair(-(*it).second, (*it).first));
    }
    sort(v.begin(), v.end());
    if (CASE) cout << endl;
    cout << "Case #" << ++CASE << endl;
    cout << "The number of pollees: " << n << endl;
    for (int i = 0; i < v.size(); i++) {
      cout << v[i].second << " " << -v[i].first << endl;
    }
  }
}

B

目的地に到着するまでの猶予時間の計算がややこしかった。儀式が行われるのが新月の0時なので、結局時間は29 * 24の倍数になる。「s 単位時間までしか補給なしに連続して航海することが出来ない」ルールは全ての点で補給可能かつ距離s以上の辺が存在しないので完全に無視して良い。残りはダイクストラで。

#include <iostream>
#include <queue>

using namespace std;

int dp[1001];

struct E {
  int e, w;
  bool operator < (const E &e) const { return w > e.w; }
};

main () {
  int n, m, t, s, r;
  while (cin >> n >> m >> t >> s >> r, n || m || t || s || r) {
    vector<vector<pair<int, int> > > graph(n + 1);
    for (int i = 0; i < m; i++) {
      int a, b, c;
      cin >> a >> b >> c;
      graph[a].push_back(make_pair(b, c));
    }
    if (t == 0) {
      cout << "No" << endl;
      continue;
    }
    int days = (t / 10) + (t % 10 ? 1 : 0);
    int time = (days / 7 + (days % 7 ? 1 : 0)) * 29 * 24;

    memset(dp, -1, sizeof(dp));

    E init;
    init.e = 1;
    init.w = r;

    priority_queue<E> que;
    que.push(init);

    while (1) {
      E here = que.top(); que.pop();
      if (here.e == 0) {
        cout << (here.w < time ? "Yes" : "No") << endl;
        break;
      }
      if (dp[here.e] != -1 && dp[here.e] < here.w) continue;
      for (int i = 0; i < graph[here.e].size(); i++) {
        E there(here);
        there.e = graph[here.e][i].first;
        there.w += graph[here.e][i].second;
        if (dp[there.e] != -1 && dp[there.e] <= there.w) continue;
        dp[there.e] = there.w;
        que.push(there);
      }
    }
  }
}

C

人数が最大18なので深さ優先で終わったのかも。手つかず。

D

LCS。最初文字単位でLCSかと勘違いして1000単語あったら終わらねーと思ったけど単語単位でLCSをする問題だった。最初WAを食らって悲しくなったけど、LCS計算は間違えようがないから誤差かなぁと思って、tが小数点以下3までと書いてあったので1000倍して整数にすれば良さそうな気がしたので

    if ((double)MAXSUM / wordcount > t || wordcount == 0) {

を

    if (MAXSUM * 1000 > wordcount * (int)((t * 1000) + 1e-6) || wordcount == 0) {

に変えてみたら通った。浮動小数点怖い。

#include <iostream>
#include <vector>
#include <sstream>

using namespace std;

int dp[1001][1001];

bool equal(string &a, string &b) {
  if (a.size() != b.size()) return false;
  for (int i = 0; i < a.size(); i++) {
    if (tolower(a[i]) != tolower(b[i])) return false;
  }
  return true;
}

string ng[3] = {"the", "an", "a"};

main () {
  double t;
  string line;
  while (cin >> t, t != -1.0) {
    getline(cin, line);
    string letter[2];
    for (int i = 0; i < 2; i++) {
      getline(cin, letter[i]);
    }
    vector<vector<string> > text[2];
    for (int i = 0; i < 2; i++) {
      int prev = 0, p;
      while (1) {
        p = letter[i].find('.', prev);
        if (p == string::npos) break;
        string cand(letter[i].begin() + prev, letter[i].begin() + p);
        stringstream ss(cand);
        vector<string> v;
        string tmp;
        while (ss >> tmp) {
          if (equal(tmp, ng[0]) ||
              equal(tmp, ng[1]) ||
              equal(tmp, ng[2])) continue;
          v.push_back(tmp);
        }
        text[i].push_back(v);
        prev = p + 1;
      }
    }
    int wordcount = 0;
    for (int i = 0; i < text[1].size(); i++) {
      wordcount += text[1][i].size();
    }
    int MAXSUM = 0;
    for (int i = 0; i < text[1].size(); i++) {
      int MAX = 0;
      for (int j = 0; j < text[0].size(); j++) {
        vector<string> a = text[1][i], b = text[0][j];
        int score = 0;
        for (int i = 0; i <= 1000; i++) {
          dp[i][0] = dp[0][i] = 0;
        }
        for (int k = 0; k < a.size(); k++) {
          for (int m = 1; m < a[k].size(); m++) {
            if ('A' <= a[k][m] && a[k][m] <= 'Z') {
              score = 1;
            }
          }
          for (int l = 0; l < b.size(); l++) {
            if (equal(a[k], b[l])) {
              dp[k + 1][l + 1] = dp[k][l] + 1;
            } else {
              dp[k + 1][l + 1] = max(dp[k][l + 1], dp[k + 1][l]);
            }
          }
        }
        score += dp[a.size()][b.size()];
        MAX = max(MAX, score);
      }
      MAXSUM += MAX;
    }
    if (MAXSUM * 1000 > wordcount * (int)((t * 1000) + 1e-6) || wordcount == 0) {
      cout << "SUSPICIOUS" << endl;
    } else {
      cout << "OK" << endl;
    }
  }
}

E

読んでない

F

読んでない

G

どこかで見た事がある問題。DP。dp.clear()をしないせいで前回の計算の結果が残っていてWAを食らった。あるある。

#include <iostream>
#include <map>

using namespace std;

int n, l;
int cut[100];
map<pair<int, int>, int> dp;

int rec(int left, int right) {
  pair<int, int> p = make_pair(left, right);
  int ret;
  if (dp.count(p)) {
    ret = dp[p];
  } else {
    int i = 0;
    while (cut[i] <= left) ++i;
    int j = n - 1;
    while (cut[j] >= right) --j;

    if (i > j) {
      ret = dp[p] = 0;
    } else {
      int MIN = INT_MAX;
      for (int k = i; k <= j; k++) {
        MIN = min(MIN, rec(left, cut[k]) + rec(cut[k], right));
      }
      ret = dp[p] = MIN + right - left;
    }
  }
  return ret;
}

main () {
  while (cin >> n >> l, n || l) {
    for (int i = 0; i < n; i++) {
      cin >> cut[i];
    }
    sort(cut, cut + n);
    dp.clear();
    cout << rec(0, l) << endl;
  }
}

H

(1 + 1 / n) ^ nはn->∞で自然対数の底e(=2.718281828......)になるので（だよね？）、

e * k

の少数部分を最小とする数k(ただし1 <= k <= m)を見つければ良いんだろうなと思って、m < 2 ^ 31なので1からINT_MAXまで

e * k - (double)(int)(e * k)

の最小値を更新する数(1, 2, 3, 7, 39, 110, 181, 252, ..., 98914198)を事前に計算してプログラムに埋め込んでみたけど上手くいかなかった。

ジャッジの入出力を待ちます。

(追記)
終了後にpythonで

last =  99999999999999999999
a    =  71828182845904523533
mod  = 100000000000000000000

for i in xrange(1, 2147483647):
  b = (a * i) % mod
  if last > b :
    last = b
    print "%-10.0d %020d" % (i, last)

と書いて実行してみた所

keisuke@keisuke:~/junk$ time python h.py
1 71828182845904523533
2 43656365691809047066
3 15484548537713570599
7 02797279921331664731
39 01299130990276417787
110 01100113049497588630
181 00901095108718759473
252 00702077167939930316
323 00503059227161101159
394 00304041286382272002
465 00105023345603442845
1001 00011028750428056533
9545 00005264158677122485
27634 00004763725603310922
45723 00004263292529499359
63812 00003762859455687796
81901 00003262426381876233
99990 00002761993308064670
118079 00002261560234253107
136168 00001761127160441544
154257 00001260694086629981
172346 00000760261012818418
190435 00000259827939006855
398959 00000019222804202147
5394991 00000009291319823203
15786014 00000008651155267462
26177037 00000008010990711721
36568060 00000007370826155980
46959083 00000006730661600239
57350106 00000006090497044498
67741129 00000005450332488757
78132152 00000004810167933016
88523175 00000004170003377275
98914198 00000003529838821534
109305221 00000002889674265793
119696244 00000002249509710052
130087267 00000001609345154311
140478290 00000000969180598570
150869313 00000000329016042829
312129649 00000000017867529917

real 48m34.818s
user 38m57.617s
sys 0m4.169s

こんな感じになった。コンテスト中はdoubleで計算していたので精度の問題でラスト6要素が列挙できていかなったらしい。というか(int)98914198 * (double)eの計算結果の小数部分が桁落ちして0.000000000000000になってた時点で気づくべきだよなぁ。これを埋め込めばAC来たのかなー。iwataさんのエントリ(http://d.hatena.ne.jp/wata_orz/20080803/1217744957)を参考にしてc++のlong doubleで計算しても同様の結果になりました。まぁ想定解じゃないみたいですけども。。。