KUPC 2015のチラ裏的解説

Tatsuya Yatagawa
Programming Contest

こんにちはtatsyです。

今回は先日行われたKUPCをチラ裏的に解説したいと思います。僕はAからFまでしかできてないので、できているとこまでです。

たぶん、そのうち公式の解説がでるので、完全に自己満です。許してください。

A. 東京都

問題

アルファベットの小文字だけから成る文章が与えられるので、それを適当に切り分けて、tokyoあるいはkyotoが入っている断片を作る。作れる断片の最大数はいくつかを答えよ。

解法

問題の意味が若干わかりづらい気がしましたが、要するに、文字列を連続する部分列に分割して、その部分列のうちtokyoあるいはkyotoが含まれるものの個数を最大にせよ、という問題。

でも正直切り刻む必要はないので、tokyoとkyotoを文字列の中からどうとるかだけを考えればいい。

あまり簡単なやり方じゃないかもですが、僕は普通ににDPで解きました。ある文字まで読んだときのtokyoあるいはkyotoの出現回数をDP表で持つという感じですね。


#include <fstream>
#include <sstream>
#include <string>
#include <algorithm>
#include <functional>
#include <numeric>
#include <vector>
#include <map>
#include <set>
#include <bitset>
#include <queue>
#include <list>
#include <stack>
#include <tuple>
#include <utility>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <climits>
#include <typeinfo>
using namespace std;

typedef long long lint;
typedef pair<int, int> pii;
typedef pair<lint, lint> pll;

#define Integer int
#define REP(i,n) for(Integer i=0; i<n; i++)
#define REPA(i,s,e) for(Integer i=s; i<=e; i++)
#define REPD(i,s,e) for(Integer i=s; i>=e; i--)
#define SIZ(a) (Integer)(a).size()
#define ALL(a) (a).begin(), (a).end()

#define PRT(a) cerr << #a << " = " << (a) << endl
#define PRT2(a, b) cerr << #a << " = " << (a) << ", " << #b << " = " << (b) << endl
#define PRT3(a, b, c) cerr << #a << " = " << (a) << ", " << #b << " = " << (b) << ", " << #c << " = " << (c) <<  endl
template <class Ty> void print_all(Ty b, Ty e) {
    cout << "[ ";
    for (Ty p = b; p != e; ++p) {
        cout << (*p) << ", ";
    }
    cout << " ]" << endl;
}

string s;
int dp[111];

void solve() {
    memset(dp, 0, sizeof(dp));
    for (int i = 0; i < s.size(); i++) {
        string sub = "";
        if (i + 5 <= s.size()) {
            sub = s.substr(i, 5);
        }

        if (sub == "tokyo" || sub == "kyoto") {
            dp[i + 5] = max(dp[i] + 1, dp[i + 5]);
        }
        dp[i + 1] = max(dp[i], dp[i + 1]);
    }
    printf("%d\n", dp[s.size()]);
}

void coding() {
    int T;
    cin >> T;
    REP(i, T) {
        cin >> s;
        solve();
    }
}

// #define _LOCAL_TEST

int main() {
#ifdef _LOCAL_TEST
    clock_t startTime = clock();
    freopen("a.in", "r", stdin);
#endif

    coding();

#ifdef _LOCAL_TEST
    clock_t elapsedTime = clock() - startTime;
    cout << endl;
    cout << (elapsedTime / 1000.0) << " sec elapsed." << endl;
    cout << "This is local test" << endl;
    cout << "Do not forget to comment out _LOCAL_TEST" << endl << endl;
#endif
}

B. GUARDIANS

問題

10×10の盤面に鎖頭と呼ばれる謎の生物を配置して左から右に至る経路を1通りにせよ、という問題。なお鎖頭は自分が存在するマスと縦横斜め2マスに対して攻撃が可能で侵入者の通過を阻むことができる。

解法

思いつけば簡単な問題。得点の最大が100点と思われるので点数の計算方式から、5個は鎖頭を配置してもよいことがわかる。

鎖玉を2マスあけで1行に配置すると、５行分への侵入を阻める。これを下1行空けで配置して、右端か左端の1マスしか通れないようにすればいい。

というか何言ってるかわからない感じですが、答えは以下のような配置です。

..........
..........
.........C
..........
..........
..........
C..C..C..C
..........
..........
..........

そして、鎖頭の攻撃可能範囲を示したのが以下です。

.......X.X
........XX
.......XXC
........XX
XXXXXXXXXX
XXXXXXXXXX
CXXCXXCXXC
XXXXXXXXXX
XXXXXXXXXX
..........

C. 最短経路

問題

ある有向グラフの任意の2点間の最短距離が与えられているので、そのような有向グラフが存在するかを答えよ。

解法

Warshall-Floyd法の要領で、

d[i][j] >= dp[i][k] + dp[k][j]

が任意の3点の組み合わせに対して成り立っており、なおかつdp[i][i]がすべてのiについて0でればOK。

ちなみに64bit整数で計算しないと落ちるので注意(←落とした人)。


#include <fstream>
#include <sstream>
#include <string>
#include <algorithm>
#include <functional>
#include <numeric>
#include <vector>
#include 

<map>
  #include <set>
  #include <bitset>
  #include <queue>
  #include <list>
  #include <stack>
  #include <tuple>
  #include <utility>
  #include <cstring>
  #include <cmath>
  #include <ctime>
  #include <cstdio>
  #include <cstdlib>
  #include <cctype>
  #include <climits>
  #include <typeinfo>
  using namespace std;
  
  typedef long long lint;
  typedef pair<int, int> pii;
  typedef pair<lint, lint> pll;
  
  #define Integer int
  #define REP(i,n) for(Integer i=0; i<n; i++)
  #define REPA(i,s,e) for(Integer i=s; i<=e; i++)
  #define REPD(i,s,e) for(Integer i=s; i>=e; i--)
  #define SIZ(a) (Integer)(a).size()
  #define ALL(a) (a).begin(), (a).end()
  
  #define PRT(a) cerr << #a << " = " << (a) << endl
  #define PRT2(a, b) cerr << #a << " = " << (a) << ", " << #b << " = " << (b) << endl
  #define PRT3(a, b, c) cerr << #a << " = " << (a) << ", " << #b << " = " << (b) << ", " << #c << " = " << (c) <<  endl
  template <class Ty> void print_all(Ty b, Ty e) {
      cout << "[ ";
      for (Ty p = b; p != e; ++p) {
          cout << (*p) << ", ";
      }
      cout << " ]" << endl;
  }
  
  const lint INF = 1ll << 60;
  int N;
  lint table[35][35];
  
  bool solve() {
      REP(i, N) {
          if (table[i][i] != 0) return false;
      }
  
      REP(k, N) {
          REP(i, N) {
              REP(j, N) {
                  if (table[i][j] > table[i][k] + table[k][j]) return false;
              }
          }
      }
  
      return true;
  }
  
  void coding() {
      int T;
      cin >> T;
      REP(t, T) {
          memset(table, 0, sizeof(table));
          cin >> N;
          REP(i, N) {
              REP(j, N) {
                  cin >> table[i][j];
                  if (table[i][j] == -1) table[i][j] = INF;
              }
          }
          printf("%s\n", solve() ? "YES" : "NO");
      }
  }
  
  // #define _LOCAL_TEST
  
  int main() {
  #ifdef _LOCAL_TEST
      clock_t startTime = clock();
      freopen("c.in", "r", stdin);
  #endif
  
      coding();
  
  #ifdef _LOCAL_TEST
      clock_t elapsedTime = clock() - startTime;
      cout << endl;
      cout << (elapsedTime / 1000.0) << " sec elapsed." << endl;
      cout << "This is local test" << endl;
      cout << "Do not forget to comment out _LOCAL_TEST" << endl << endl;
  #endif
  }

D. 高橋君の旅行

問題

直線状にN+1個の街が与えられていて、高橋君は1番目の街から順々に町をめぐる旅行を計画している。このとき、街から街に移る際の所持金の増減量と、街に滞在した場合の所持金の増加量が与えられている。N日後に所持金が最大になるような旅程を組みなさい。

解法

それなりにすぐ思いつきそうな解答としては、今いる街とその時の残り日数に対する所持金をDPするという方法です。ですが、この問題では街の数が105あるので、この方法だと部分点しかとれません。

この問題のポイントは一回通過した街に後戻りできないという点で、N日目の終わりに到着している街が決まれば、その時までに「移動」によって変動する所持金は一定です。

ということは、どこの街まで行くかが決まれば、あとは、その途中でどの街にどのくらい滞在するかを決めればいい、ということになります。

まず、単純な場合として、移動により変動する所持金がすべてプラスの場合を考えてみます。

この場合には、基本、街から街へ移動するのに所持金が足りなくなって足止めを食らうことはありません。

ですから、どこの町まで行くかを決めたら、滞在することによって一番所持金が増える街で余っている日にちを消化するのが、所持金を最大にできることが分かります。

仮に街Kまで行くとするなら、この時の所持金の最大値は

sum { A[k] : 1, ..., K } + max { B[k] : 1, ..., K - 1 } * (N - K)

で計算できます。

問題は、移動による所持金の変動が負の場合で、この時には所持金が足りず、ある街で足止めを食らう場合があります。

ですが、この時も基本の考え方は同じで、足止めを食らう可能性がある街に行くまでにある街で、滞在した時に所持金の増加が最大になる街で、十分に資金をためたあとで、一気に目的の街までいくのがよさそうです。

このアイディアをまとめたコードが以下になります。


#include <iostream>
#include <fstream>
#include <sstream>
#include <string>
#include <algorithm>
#include <functional>
#include <numeric>
#include <vector>
#include 

<map>
#include <set>
#include <bitset>
#include <queue>
#include <list>
#include <stack>
#include <tuple>
#include <utility>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <climits>
#include <typeinfo>
using namespace std;

typedef long long lint;
typedef pair<int, int> pii;
typedef pair<lint, lint> pll;

#define Integer int
#define REP(i,n) for(Integer i=0; i<n; i++)
#define REPA(i,s,e) for(Integer i=s; i<=e; i++)
#define REPD(i,s,e) for(Integer i=s; i>=e; i--)
#define SIZ(a) (Integer)(a).size()
#define ALL(a) (a).begin(), (a).end()

#define PRT(a) cerr << #a << " = " << (a) << endl
#define PRT2(a, b) cerr << #a << " = " << (a) << ", " << #b << " = " << (b) << endl
#define PRT3(a, b, c) cerr << #a << " = " << (a) << ", " << #b << " = " << (b) << ", " << #c << " = " << (c) <<  endl
template <class Ty> void print_all(Ty b, Ty e) {
    cout << "[ ";
    for (Ty p = b; p != e; ++p) {
        cout << (*p) << ", ";
    }
    cout << " ]" << endl;
}

int N;
lint A[100011];
lint B[100011];

int days[100011];
lint moneys[100011];

void solve() {
    memset(days, -1, sizeof(days));

    // ここまでの街で滞在時の所持金増加が最大のものを記録
    for (int i = 1; i < N; i++) {
        B[i] = max(B[i], B[i - 1]);
    }

    // ある街に到着するまでの最小日数を計算
    int d = 0;
    lint m = 0;
    for (int i = 0; i <= N; i++) {
        days[i] = d;
        moneys[i] = m;
        while (d < N && m + A[i] < 0) {
            d++;
            m += B[i];
        }
        
        if (d <= N) {
            d++;
            m += A[i];
        }
    }

    // 余り日数を所持金が最も増える街で消化する
    lint ans = 0;
    for (int i = 0; i <= N; i++) {
        if (days[i] != -1) {
            ans = max(ans, B[i] * (N - days[i]) + moneys[i]);
        }
    }
    cout << ans << endl;
}

void coding() {
    while (cin >> N) {
        REP(i, N) cin >> A[i];
        REP(i, N) cin >> B[i];
        solve();
    }
}

// #define _LOCAL_TEST

int main() {
#ifdef _LOCAL_TEST
    clock_t startTime = clock();
    freopen("d.in", "r", stdin);
#endif

    coding();

#ifdef _LOCAL_TEST
    clock_t elapsedTime = clock() - startTime;
    cout << endl;
    cout << (elapsedTime / 1000.0) << " sec elapsed." << endl;
    cout << "This is local test" << endl;
    cout << "Do not forget to comment out _LOCAL_TEST" << endl << endl;
#endif
}

E. マッサージチェア2015

問題

ある幅W、高さHの部屋に3つのイスを配置するときに、その椅子の間の距離の最小値が最大になるように配置し、その時の距離の最小値を答えよ。

解法

まず、最初の観察として、3つのイスのうち1つは必ず部屋の隅にありそうです。

計算を簡単にするためにここを原点(0, 0)として話を進めます。

残りの2つのイスですが、なんとなくの直感として、原点から延びる壁ではない残りの2つの壁に1つずつ椅子を配置するのがよさそうです。

つまり残りの2つのイスの座標はそれぞれ、(x, H), (W, y)みたいな感じになりそうです。

この時点で最適化する変数は2つになっています。まぁ、これでもできないことはなさそうですが、被最適化関数がmaxを含んでいて、なおかつ二次なので、ちょっと難しそうです(やるとしても実装は？？)。

で、どうするかというと、もう1つ変数を減らしにかかります。二つ目の観察として、2つ目のイスを(x, H)に決めたとすると、残りのイスのy座標は1つに決まるのではないかと疑ってみます。

具体的には、原点(0, 0)と2つ目のイスの位置(x, H)の垂直二等分線と直線x = Wの交点に3つ目のイスを配置すればよさそうな気がします。

これで変数がxだけになったので、あとは1変数関数に対する最小化を解きます。この関数は今、下に凸な関数になっているので、黄金分割探索とかすればよさそうですが、実装がめんどいので三分探索で行きます。

実装したのが以下のコードです。


#include <iostream>
#include <fstream>
#include <sstream>
#include <string>
#include <algorithm>
#include <functional>
#include <numeric>
#include <vector>
#include 

<map>
#include <set>
#include <bitset>
#include <queue>
#include <list>
#include <stack>
#include <tuple>
#include <utility>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <climits>
#include <typeinfo>
using namespace std;

typedef long long lint;
typedef pair<int, int> pii;
typedef pair<lint, lint> pll;

#define Integer int
#define REP(i,n) for(Integer i=0; i<n; i++)
#define REPA(i,s,e) for(Integer i=s; i<=e; i++)
#define REPD(i,s,e) for(Integer i=s; i>=e; i--)
#define SIZ(a) (Integer)(a).size()
#define ALL(a) (a).begin(), (a).end()

#define PRT(a) cerr << #a << " = " << (a) << endl
#define PRT2(a, b) cerr << #a << " = " << (a) << ", " << #b << " = " << (b) << endl
#define PRT3(a, b, c) cerr << #a << " = " << (a) << ", " << #b << " = " << (b) << ", " << #c << " = " << (c) <<  endl
template <class Ty> void print_all(Ty b, Ty e) {
    cout << "[ ";
    for (Ty p = b; p != e; ++p) {
        cout << (*p) << ", ";
    }
    cout << " ]" << endl;
}

const double EPS = 1.0e-10;
const double PI  = 4.0 * atan(1.0);
int sign(double r) { return r < -EPS ? -1 : r > EPS ? 1 : 0; }

class P {
public:
    double x, y;
    P() {}
    P(int x_, int y_) : x(x_), y(y_) {}
    P(double x_, double y_) : x(x_), y(y_) {}
    P(const P& p) : x(p.x), y(p.y) {}
    P operator+(P p) const { return P(x+p.x, y+p.y); }
    P operator-(P p) const { return P(x-p.x, y-p.y); }
    P operator-() const { return P(-x, -y); }
    P operator*(double s) const { return P(x*s, y*s); }
    P operator/(double s) const { return P(x/s, y/s); }
    P& operator=(const P& p) { x=p.x; y=p.y; return (*this); }
    double dot(P p) const { return x*p.x + y*p.y; }
    double det(P p) const { return x*p.y - y*p.x; }
    double norm() const { return sqrt(x*x + y*y); }
    double norm2() const { return x*x + y*y; }
    P proj(const P& p) const { double k=det(p)/norm2(); return P(x*k, y*k); }
};

bool operator<(P p, P q) {
    if(sign(p.x - q.x) != 0) return p.x < q.x;
    return p.y < q.y;
}

bool operator>(P p, P q) {
    if(sign(p.x - q.x) != 0) return p.x > q.x;
    return p.y > q.y;
}


double W, H;

double calc(double x) {
    double mx = x * 0.5;
    double my = H * 0.5;

    double y = my - (W - mx) * (x / H);

    P p1(0.0, 0.0);
    P p2(x, H);
    P p3(W, y);

    return min((p1 - p2).norm(), min((p2 - p3).norm(), (p3 - p1).norm()));
}

void solve() {
    if (W > H) swap(W, H);

    double lo = 0.0;
    double hi = W;

    while (abs(hi - lo) > 1.0e-12) {
        double m1 = (2.0 * lo + hi) / 3.0;
        double m2 = (lo + 2.0 * hi) / 3.0;
        double f1 = calc(m1);
        double f2 = calc(m2);
        if (f1 < f2) {
            lo = m1;
        } else {
            hi = m2;
        }
    }
    printf("%.12f\n", calc(lo));
}

void coding() {
    int T;
    cin >> T;
    REP(t, T) {
        cin >> W >> H;
        solve();
    }
}

// #define _LOCAL_TEST

int main() {
#ifdef _LOCAL_TEST
    clock_t startTime = clock();
    freopen("e.in", "r", stdin);
#endif

    coding();

#ifdef _LOCAL_TEST
    clock_t elapsedTime = clock() - startTime;
    cout << endl;
    cout << (elapsedTime / 1000.0) << " sec elapsed." << endl;
    cout << "This is local test" << endl;
    cout << "Do not forget to comment out _LOCAL_TEST" << endl << endl;
#endif
}

F. 逆ポーランド記法

問題

逆ポーランド記法で使うべきデータ構造を誤ってキューにして実装してしまったので、キューでも動くようにスタック用の逆ポーランド記法を書き換えよ。

解法

実装は重めなのかなとは思いますが、解法はとても単純です。

要するにスタック用の逆ポーランド記法を木構造に直して、あとはそれを幅優先探索でキュー用の逆ポーランド記法に直すだけです。

以下、メモリリークありのしょっぱい実装です。


#include <iostream>
#include <fstream>
#include <sstream>
#include <string>
#include <algorithm>
#include <functional>
#include <numeric>
#include <vector>
#include 

<map>
#include <set>
#include <bitset>
#include <queue>
#include <list>
#include <stack>
#include <tuple>
#include <utility>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <climits>
#include <typeinfo>
using namespace std;

typedef long long lint;
typedef pair<int, int> pii;
typedef pair<lint, lint> pll;

#define Integer int
#define REP(i,n) for(Integer i=0; i<n; i++)
#define REPA(i,s,e) for(Integer i=s; i<=e; i++)
#define REPD(i,s,e) for(Integer i=s; i>=e; i--)
#define SIZ(a) (Integer)(a).size()
#define ALL(a) (a).begin(), (a).end()

#define PRT(a) cerr << #a << " = " << (a) << endl
#define PRT2(a, b) cerr << #a << " = " << (a) << ", " << #b << " = " << (b) << endl
#define PRT3(a, b, c) cerr << #a << " = " << (a) << ", " << #b << " = " << (b) << ", " << #c << " = " << (c) << endl
template <class Ty> void print_all(Ty b, Ty e) {
    cout << "[ ";
    for (Ty p = b; p != e; ++p) {
        cout << (*p) << ", ";
    }
    cout << " ]" << endl;
}

struct Node {
    char val;
    Node* left = nullptr;
    Node* right = nullptr;
    Node(char v) : val{v} {}
};

string s;

void solve() {
    stack<Node*> stk;
    vector<Node> nodes;
    for (int p = 0; p < s.size(); p++) {
        if ('0' <= s[p] && s[p] <= '9') {
            Node* n = new Node(s[p]);
            stk.push(n);
        } else {
            Node* A = stk.top(); stk.pop();
            Node* B = stk.top(); stk.pop();
            Node* n = new Node(s[p]);
            n->left = B;
            n->right = A;
            stk.push(n);
        }    
    }

    queue<Node*> que;
    que.push(stk.top());

    string ans;
    while (!que.empty()) {
        Node* n = que.front();
        que.pop();
        if (!n) continue;

        ans.push_back(n->val);
        que.push(n->left);
        que.push(n->right);
    }

    reverse(ALL(ans));
    cout << ans << endl;
}

void coding() {
    while (cin >> s) {
        solve();
    }
}

// #define _LOCAL_TEST

int main() {
#ifdef _LOCAL_TEST
    clock_t startTime = clock();
    freopen("f.in", "r", stdin);
#endif

    coding();

#ifdef _LOCAL_TEST
    clock_t elapsedTime = clock() - startTime;
    cout << endl;
    cout << (elapsedTime / 1000.0) << " sec elapsed." << endl;
    cout << "This is local test" << endl;
    cout << "Do not forget to comment out _LOCAL_TEST" << endl << endl;
#endif
}

まとめ

解説は以上です。そのうち公式の解法がでると思いますが、何かの参考になったら嬉しいな、と思います。

最後までお読みいただきありがとうございました。