Hatena::Grouptopcoder

blu_rayの日記

2011-09-21

SRM 519 Div2

| 19:02

寝過ごしたのでPractice ...

250. WhichDay

やさしい。

600. ThreeTeleports

色々考えることが出来そうですが、面倒くさいので全探索。

ワープの組は3つなので全部を通っていく場合は3!、さらにEndPointへの行き方は(x1,y1) -> (x2,y2), (x2,y2) -> (x1,y1) の2通りが存在するので、ワープへの入り方で2^3の状態を生成すれば良さそう。

書いたら計算量も3! * 2^3 * 3.

#define rep(i,n) for((i)=0;(i)<(int)n;(i)++)
#define foreach(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();i++)

struct EndPts {
  int x1, y1, x2, y2;
};
EndPts endPts[3];

class ThreeTeleports {
public:
  int calc(int ax, int ay, int bx, int by) {
    return abs(ax-bx) + abs(ay-by);
  }
  void setEndPts(const vector<string>& teleports) {
    int i, j;
    rep (i, 3) {
      int cur = 0;
      vector<int> v;
      rep (j, teleports[i].size()) if (teleports[i][j] == ' ') v.push_back(j);
      v.push_back(teleports[i].size());
      int ti[4];
      rep (j, 4) {
        ti[j] = atoi(teleports[i].substr(cur, v[j] - cur).c_str());
        cur = v[j]+1;
      }
      endPts[i] = (EndPts){ti[0], ti[1], ti[2], ti[3]};
    }
  }
  int shortestDistance(int xMe, int yMe, int xHome, int yHome, vector<string> teleports) {
    int i;
    long long ans = calc(xMe, yMe, xHome, yHome);
    setEndPts(teleports);
    int a[3] = {0,1,2};
    do {
      for (int S = 0; S<(1<<3); S++) {
        long long temp = 0;
        int x = xMe, y = yMe;
        rep (i, 3) {
          int t = a[i];
          if ((1<<i) & S) {
            temp += calc(x, y, endPts[t].x1, endPts[t].y1) + 10;
            x = endPts[t].x2, y = endPts[t].y2;
          } else {
            temp += calc(x, y, endPts[t].x2, endPts[t].y2) + 10;
            x = endPts[t].x1, y = endPts[t].y1;
          }
          ans = min(ans, temp + calc(x, y, xHome, yHome));
        }
      }
    } while (next_permutation(a, a+3));
    return ans;
  }
};

teleportsのデータの読み取りはsscanfとかistringstream使えば良かった。。

900. BinaryCards

他の人コード読んで理解。aとbのbitを調べるときに

// 問題無し
int i;
for (i .. ) if ((a >> i & 1)^(b >> i & 1)) {
  ..
}
// 問題あり
for (i .. ) if (((1 << i) & a)^((1 << i) & b)) {
  ..
}

1<<iってintになるのか</ppp>

2011-09-18

Codeforces Beta Round #87 Div2

| 23:56

oo---

A. Tram / Accepted / 492

回すだけ。

B. Little Pigs and Wolves / Accepted / 530

ぱっと見は二部マッチングだけど、

It is guaranteed that there will be at most one wolf adjacent to any little pig.

任意の豚に対し、隣接する狼は多くても1匹という制約があるから、グリッド内の豚に着目して隣接する狼と一緒に消していき、数えていけば解けるのだけど、この文章に気づくまでかなり掛かって提出がかなり遅れた。それまでずっと最大マッチングの問題だと思って四苦八苦してた。。Editorialにも、最大流(はオーバーキルですよ)を仄めかすような文章がちらほら。

自分がアルゴリズムとか書き方について知っていれば、最適解でないにしろもっと早く提出できたので、蟻本見ながら勉強して二部マッチング版も書いてみた。。

C. Party

適当に書く -> TLE -> Editorial

一番深い木の深さなのか。

確かに最も深い木の深さだけグループは必要になるし、その深さをkとすると、他のノードと比較して、最も深い木の部分木は確実にグループ数k+1で足りるし、部分木じゃなくても深さkより大きくないから結局k+1で足りることになる。

D. Lawnmower

移動する行の一つ下の行を見ればいいのかな。

rate := 1336 -> 1296

提出が遅れて順位がやばかったため

2011-09-15

SRM 518 Div2

| 18:29

oo-

250. TwiceString / Passed System Test / 175

Easyに面喰らう事が多い。

あれこれ迷いながら、1文字ずつずらして重なるか見るに着地。時間掛かった。

500. LargestSubsequence / Passed System Test / 411

Easyの方が難しいと思った。

文字列の中で最大の文字を見つけて、解に追加して、

発見した位置より右の範囲で再び最大の文字を見つけて、解に追加して、・・を繰り返すだけ。

1000. CoinReversing / Opened / 0

通してる人が多くて、コードも短めの人が多いので、出来る人には簡単だったっぽい。

本番中はTLEするような方法しか思いつかなかった...大体下記の方法がわかりやすかった。

E ≡ 期待値, prevE ≡ 一つ前の期待値
A ≡ 表向きのコインの選択される枚数期待値, B ≡ 裏向きのコインの選択される枚数期待値
(0 .. K-1).each do |i|
  A = a[i] / N * prevE
  B = a[i] - A
  E = prevE - A + B
  prevE = E
end

初期状態のprevEをNとして、その場の期待値を順番に求めていく事で最終的な答えが出る。。。

rate := 954 -> 963

2011-09-10

SRM 517 Div2

| 03:39

ox-

250. MonochromaticBoard / Passed System Test

無駄に時間かかった。

500. CompositeSmash / Failed System Test

Nをとりあえず素因数分解して、vectorに放り込んで、

vectorの長さがおそらく最大でも16前後だろうということでbitで状態生成して全探索。

とかしてるけど、そんな必要なかった。

このコードだとNとtargetが互いに素の場合(="NO")で死ぬのに気づけなかった。悔しい。

const int MAX_N = 100012;
bool sieve[MAX_N];
vector<int> prime, list;

class CompositeSmash {
public:
  bool isInvalid(int S, int size) {
    if (S == 0) return true;
    int i;
    rep(i,size) if (!((1<<i)&S)) return false;
    return true;
  }
  string thePossible(int N, int target) {
    if (N == target) return "Yes";
    if (N < target) return "No";
    int i, j;
    fill(sieve, sieve+MAX_N, true);
    sieve[0] = sieve[1] = false;
    for(i=2;i<MAX_N;i++) if (sieve[i]) {
      prime.push_back(i);
      for(j=i+i;j<MAX_N;j+=i) sieve[j] = false;
    }
    
    int temp = N;
    int sz = prime.size();
    rep(i,sz) {
      while (temp % prime[i] == 0) {
        temp /= prime[i];
        list.push_back(prime[i]);
      }
    }
        
    int lsz = list.size();
    if (lsz == 1) return "No"; // これがなくて脂肪
    for(int S=1;S<(1<<lsz);S++) {
      if (isInvalid(S, lsz)) continue;
      int rhs = 1, lhs = 1;
      rep(i,lsz) {
        if ((1<<i)&S) {
          rhs *= list[i];
        } else {
          lhs *= list[i];
        }
      }
      if (rhs % target != 0 && lhs % target != 0) return "No";      
    }
    return "Yes";
  }
};

isInvalid()は意味ないとおもう

1000. CompositeSmash / Unopened

rate := 967 -> 954

2011-09-09

Codeforces Beta Round #86 Div2

| 17:26

ox---

A.Cifera / Accepted

一応long long。

k^1の場合は"YES\n0\n"を出力しないといけない事に気づくまでかかった。

B.PFAST Inc. / Faild System Test

適当な全探索をかいてTLE。大体O(n!)だったので、その後に謎解法(頂点を端点の数でソートして少ない方から選ぶ)でsubmitして脂肪。

できてる人のを見て、n<=16, m<=16*15/2=120 で、

for(int S=0;S<(1<<n);S++)で全状態を生成して</ppp>

各々validか調べるとO(2^16*m) = 7Mくらいで余裕すぎる…。

nが少ない時は2^nで全状態生成を考えた方がいい。

C.Grammar Lessons / WA

本番中は残り20分くらいでOpenして実装ということで見てなかったけど書くだけだった。

statementの場合は色々気をつけて、wordのみの場合を見逃すようにする。

D.Petr#

見てない。problem tagsがDiv1とDiv2で結構違う。


落ち着いてきた。

rate:= 1381 -> 1336