naoya_t@hatenablog

いわゆるチラシノウラであります

SRM718

x-- 0pt 1573→1503 (-70) 青い海が見えてきた
カーソルのないキーボードに替えてから初のSRM

Easy 250 InterleavingParenthesis

レーベンシュタイン距離を求める時みたいなDP(2次元のテーブルを作る必要はない。2行だけあればOK)
各セルは、そこまでの()差と、場合の数、の2つの値を持つ。
(※()差は簡単に計算できるからわざわざ保持しなくても…)
正しく終われない場合に0を返さなかったのを修正して再提出。
→撃墜されて0点

ミスが2点。

  • [ミス1] ()差が負になった場合に一律で (-1, 0) を保持していたこと。場合の数が0なのは良いが()差はいくつになっても保持すべき。s2側が先に解決してくれている場合があるので。
  • [ミス2] s1/s2お互いに、それ単体で途中まで読んで閉じ括弧の方が多い位置では場合の数は0

f:id:n4_t:20170713133945j:plain

--- InterleavingParenthesisWA.cpp       2017-07-13 13:12:51.000000000 +0900
+++ InterleavingParenthesisAC.cpp       2017-07-13 13:13:00.000000000 +0900
@@ -52,9 +52,9 @@
                 --op;
             }
             if (op >= 0)
-                d0[1+c] = llll(op, 1);
+                d0[1+c] = llll(op, d0[c].second);   // [ミス2]
             else
-                d0[1+c] = llll(-1, 0);
+                d0[1+c] = llll(op, 0);   // [ミス1]
         }
 // BEGIN CUT HERE
         cout << d0 << endl;
@@ -62,13 +62,10 @@
 
         rep(r, L2) {
             op = (s2[r] == '(') ? 1 : -1;
-            if (d0[0].first == -1) {
-                d1[0] = llll(-1,0);
+            if (d0[0].first + op < 0) {
+                d1[0] = llll(d0[0].first + op, 0);    // [ミス1]
             } else {
-                d1[0] = llll(d0[0].first + op, 1);
-                if (d1[0].first < 0) {
-                    d1[0] = llll(-1,0);
-                }
+                d1[0] = llll(d0[0].first + op, d0[0].second);    // [ミス2]
             }
             rep1(i, L1) {
 // BEGIN CUT HERE
@@ -78,7 +75,7 @@
                     d1[i] = llll(d0[i].first + op,
                             (d1[i-1].second + d0[i].second) % MOD);
                 else
-                    d1[i] = llll(-1,0);
+                    d1[i] = llll(d0[i].first + op, 0);  /// 注1
             }
             d0 = d1;

ACコード

// 略
using namespace std;

typedef long long ll;
typedef vector<int> vi;

#define sz(a)  int((a).size())
#define pb  push_back
#define rep(var,n)  for(int var=0;var<(n);++var)
#define rep1(var,n)  for(int var=1;var<=(n);++var)
#define all(c)  (c).begin(),(c).end()
#define tr(i,c)  for(auto i=(c).begin(); i!=(c).end(); ++i)
#define found(s,e)  ((s).find(e)!=(s).end())

typedef pair<int,int> ii;
typedef pair<ll,ll> llll;

#define MOD 1000000007LL

class InterleavingParenthesis {
    public:
    int countWays(string s1, string s2) {
        int L1 = s1.size(), L2 = s2.size();
        vector<llll> d0(L1+1), d1(L1+1);
        d0[0] = llll(0, 1);
        int op = 0;
        rep(c,L1){
            if (s1[c] == '(') {
                ++op;
            } else {
                --op;
            }
            if (op >= 0)
                d0[1+c] = llll(op, d0[c].second);
            else
                d0[1+c] = llll(op, 0);
        }

        rep(r, L2) {
            op = (s2[r] == '(') ? 1 : -1;
            if (d0[0].first + op < 0) {
                d1[0] = llll(d0[0].first + op, 0);
            } else {
                d1[0] = llll(d0[0].first + op, d0[0].second); // open, ways
            }
            rep1(i, L1) {
                if (d0[i].first + op >= 0)
                    d1[i] = llll(d0[i].first + op,
                            (d1[i-1].second + d0[i].second) % MOD);
                else
                    d1[i] = llll(d0[i].first + op, 0);
            }
            d0 = d1;
        }

        if (d0[L1].first == 0)
            return d0[L1].second % MOD;
        else
            return 0;
    }
};

Medium 500 CircleCity

開いたは良いが、どこから手をつけたらいいんだろう
4都市で {1,10,2,10}, k=2 みたいなケースを考えてて、最小は2になるんだけど、ポータルをAB, CDの中間あたりに置いた時がベスト(xをAからB方向へのポータル1への距離、yをCからD方向へのポータル2への距離、として連立不等式を立てると菱形の領域の内側ならどこでもOK)