naoya_t@topcoder

SRM533 - 深夜開催のSRMがちょっと辛い今日この頃

01:55 |

（http://naoyat.hatenablog.jp/entry/2012/02/20/014918 からの転載）

最近ちょっと早寝早起きサイクルになってるので2amからとかちょっときついですね。

というわけでSRM533の問題を見てみた話。配点的には250-500-1000ですが・・・

出てたら430位ぐらいでレーティング横ばい〜微減、かな。

Div1 Easy(250) CasketOfStar

250がちょっと難しかった、というか正しい筋道で考えるまでに時間がかかった。

• 両端から１つずつ減らして f(a,b) = weight[a]*weight[b] + max(f(a,b-1), f(a+1,b)) みたいに解けるからDPだ、と考えていた時期が僕にもありました、みたいな
• これではサンプルケースさえ解けない。貪欲に大きい方から行くとかも何か違いそうというか怖い
• サンプル#2の {2,2,7,6,90,5,9} の例で、90 のところで左右に分けて考えられそうな気がしたので、単にあらゆる分割点を考えて f(a,b) = weight[a]*weight[b] + max( f(a,a+1)+f(a+1,b), f(a,a+2)+f(a+2,b), ..., f(a,b-1)+f(b-1,b) ) ではどうか。f(a,b) はb-a=1のとき0とすればよさげ。
• というわけでやっぱりDP。メモ化再帰で書いたけど。
• これでAC。110.83点（46'44''）

#define found(s,e)  ((s).find(e)!=(s).end())

typedef pair<int,int> i_i;

map<i_i,int> mm;
int sub(const vector<int>& ws, int b, int e){
  i_i k(b,e); if (found(mm,k)) return mm[k];
  if (e-b <= 1) return 0;
  int s = ws[b] * ws[e];
  if (e-b == 2) return s;

  int mx = 0;
  for (int i=b+1; i<=e-1; i++) {
    mx = max(mx, sub(ws,b,i) + sub(ws,i,e));
  }
  return mm[k] = s + mx;
}

class CasketOfStar {
 public:
  int maxEnergy(vector<int> weight) {
    mm.clear();
    return sub(weight, 0, weight.size()-1);
  }
};

Div1 Medium(500) MagicBoard

51'12''かけて解いた答えが単純なテスト {"#", "#"} で落ちた。原因は S が水平方向の移動から始まらないといけないのを忘れていたから。SRMでドジっ子アピールしても何の得もないというのに。

• 一筆書きできるかどうか？
• いや、縦横縦横みたいな感じの移動でないと駄目みたい
• サンプルの最後の58（わぁい58 あかり58大好き）は間にスペースがある。移動は同一行ないし同一列ならどう飛んでもよいようだ。
• 頂点が最大2500。このどこか１つから、辺を全部（最大5000*2500ぐらい）列挙して縦横縦横縛りで移動しながらTLEせずに全部回れるのか？いや無理だろう
• 横軸から縦軸へ。縦軸から横軸へ。移動できるのはMagic Diamondのある箇所のみ。
• キーボードの配線みたいだ。そして２部グラフっぽい。
• 縦軸、横軸をノードとして、Magic Diamondを辺とすると、すべてのMagic Diamondをさらうのとすべての辺を通るのが同じなので、これはシンプルな一筆書き問題に帰着できる
• UnionFindか何かで全ノードの接続を確認した上で、各ノードから出てる辺の数を数えて、奇数の箇所が0か2なら一筆書きが可能、っていうあれだ（thanks to オイラー先生）
• コード書けた。サンプル通った。
• 提出。211.82点（51'12''）Easyで時間食ってたからこれでは間に合わない。
• しかもWA。単純なテスト {"#", "#"} で落ちてる。
• ああああああ
• S は水平方向の移動から始まらないといけないのを忘れてた
• 奇数辺のノードが２つある場合、それが縦軸ノードに２つあったらアウトだ
• そこだけ直してAC
• 問題の制約はちゃんと把握しましょう。サンプルケースが足りなければ書き足しましょう。

#include <algorithm>
#include <string>
#include <vector>
#include <set>
using namespace std;
#define rep(var,n)  for(int var=0;var<(n);var++)
typedef pair<int,int> i_i;

class UnionFind {
  vector<int> data;
 public:
  explicit UnionFind(int size) : data(size, -1) { }
  bool unionSet(int x, int y) {
    x = root(x);
    y = root(y);
    if (x != y) {
      if (data[y] < data[x]) swap(x, y);
      data[x] += data[y];
      data[y] = x;
    }
    return x != y;
  }
  bool findSet(int x, int y) { return root(x) == root(y); }
  int root(int x) { return data[x] < 0 ? x : data[x] = root(data[x]); }
  int size(int x) { return -data[root(x)]; }
  bool has(int x) { return data[x] >= 0; }
};

class MagicBoard {
 public:
  string ableToUnlock(vector<string> board) {
    int R = board.size(), C = board[0].size();
    // vector<set<i_i> > h(R), v(C);
    vector<set<int> > hv(R), vh(C);
    UnionFind uf(R+C);
    rep(r,R) rep(c,C) if (board[r][c] == '#') {
      i_i rc(r,c);
      // h[r].insert(rc); v[c].insert(rc);
      hv[r].insert(c); vh[c].insert(r);
      uf.unionSet(r, R+c);
    }

    int root = 10000;
    // int odd = 0, even = 0;
    int r_odd = 0, c_odd = 0;
    rep(r,R) {
      if (hv[r].size() == 0) continue;
      if (root == 10000) root = uf.root(r);
      else if (uf.root(r) != root) return "NO";
      // if (hv[r].size() & 1) odd++; else even++;
      if (hv[r].size() & 1) r_odd++;
    }
    rep(c,C) {
      if (vh[c].size() == 0) continue;
      else if (uf.root(R+c) != root) return "NO";
      // if (vh[c].size() & 1) odd++; else even++;
      if (vh[c].size() & 1) c_odd++;
    }

    // return odd <= 2 ? "YES" : "NO";
    if (r_odd + c_odd > 2) return "NO";
    if (r_odd == 2) return "NO";
    return "YES";
  }
};