Hatena::Grouptopcoder

blu_rayの日記

2011-11-05

Codeforces Beta Round #92 Div2

| 00:22

ooo--

A. The number of positions / Accepted / 474

O(1)で出来ると思ったけど、N=100なのでO(N)で。

こういう0と1でうわーってなる問題が苦手…。

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

int n, a, b;

int main() {
  while (cin >> n >> a >> b) {
    int ans = 0;
    for (int i = 0; i < n; ++i) {
      if (i < a) continue;
      int behind = n - 1 - i;
      if (behind <= b) ans++;
    }
    cout << ans << endl;
  }
  return 0;
}

B. Permutations / Accepted / 852

英語が意味不明。Noteのrearrangeで(3,1,2,4)に並び替えを見るまで意味不明だった。

next_permuitation問題。

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

int n, k;

int main() {
  while (cin >> n >> k) {
    int ans = 1 << 30;
    string in[8], to[8];
    rep (i,n) cin >> in[i];
    int l[8] = { 0, 1, 2, 3, 4, 5, 6, 7 };
    
    do {
      rep (i,n) to[i] = "         ";
      rep (i,n) rep (j,k) {
        to[i][j] = in[i][ l[j] ];
      }
      int _min = 1 << 30, _max = -1;
      rep (i,n) {
        int _sum = atoi(to[i].c_str());
        _min = min(_min, _sum);
        _max = max(_max, _sum);
      }
      ans = min(ans, _max - _min);
    } while (next_permutation(l, l + k));
    cout << ans << endl;
  }
  return 0;
}

C. Prime Permutation / Accepted / 1328

|S|以下の任意の素数pに対して、Sp = Sp x iが成立するのは、

p*2 > |S|となるpについては、Sp = Sp x 1のみ考えればよいので何にも考えない。

p*2 <= |S|となるpについては、複数回Sの中に出現するため、同じ文字が必要になる。

複数回出現する際に、必ず2*pの位置で出現するため、p=2の場合の文字と同じ文字じゃないといけない。

なので、複数回出現する場合は、結局すべて同じ文字じゃないといけない。

あとは、どのくらい同じ文字が必要か考えて判定するだけ。

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

string in;
const int MAX_N = 1002;
bool sieve[MAX_N];
vector<int> primes(1,2);

int main() {
  fill(sieve, sieve + MAX_N, true);
  for (int i = 4; i < MAX_N; i+=2) sieve[i] = false;
  for (int i = 3; i < MAX_N; i+=2) if (sieve[i]) {
    primes.push_back(i);
    for (int j = i + i; j < MAX_N; j+=i) sieve[j] = false;
  }
  while (cin >> in) {
    int sz = in.size();
    bool check[MAX_N];

    fill(check, check + MAX_N, false);
    rep (i,primes.size()) {
      if (primes[i] > sz/2) break;
      for (int j = primes[i]; j < MAX_N; j+=primes[i]) check[j] = true;
    }

    int cnt = 0;
    for (int i = 1; i <= sz; ++i) if (check[i]) cnt++;

    map<char,int> m;
    rep (i,sz) {
      if (m.count(in[i])) m[ in[i] ]++;
      else m.insert(make_pair(in[i], 1));
    }
    
    int maxs = 0;
    char ch = 0;
    foreach (m,i) {
      if (maxs < i->second) {
        maxs = i->second;
        ch = i->first;
      }
    }
    
    if (maxs < cnt) { cout << "NO" << endl; continue; }
        
    queue<char> q;
    rep (i,sz) if (in[i] != ch) {
      q.push(in[i]);
    }
    
    cout << "YES" << endl;
    string res(in);
    for (int i = 1; i <= sz; ++i) {
      char c;
      if (check[i]) {
        c = ch;
      } else {
        if (!q.empty()) {
          c = q.front(); q.pop();
        } else {
          c = ch;
        }
      }
      res[i-1] = c;
    }
    cout << res << endl;
  }
  return 0;
}

D. Squares

問題は読めました。

他の人のを参考にする。

rate := 1585(+140)

あお!

2011-10-28

Codeforces Beta Round #91 Div2

| 02:15

ooox-

A. Lucky Division / Accepted / 484

与えられたnがlukcy numberで割り切れるか判定する。事前に求めておけばもちろんO(1)で判定できる。

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

const int MAX_N = 1002;
int n;
set<int> s;

void make_lucky(int a) {
  if (a > MAX_N) return;
  if (a > 0) s.insert(a);
  a *= 10;
  make_lucky(a + 4);
  make_lucky(a + 7);
}

bool check[MAX_N];

int main() {
  make_lucky(0);
  fill(check, check + MAX_N, false);
  foreach(s,i) {
    for (int j = *i; j < MAX_N; j += *i) {
      check[j] = true;
    }
  }
  
  while (cin >> n) {
    cout << ((check[n]) ? "YES" : "NO") << endl;
  }
  return 0;
}

B. Lucky Substring / Accepted / 932

”もっとも出現回数の多い”という条件があるため、結局'4'か'7'になるので、ただ数え上げるだけ。

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

string in;

int solve() {
  int sz = in.size();
  int cnt_4 = 0, cnt_7 = 0;
  rep (i,sz) {
    if (in[i] == '4') cnt_4++;
    else if (in[i] == '7') cnt_7++;
  }
  if (cnt_4 > cnt_7) {
    return 4;
  } else if (cnt_4 < cnt_7) {
    return 7;
  } else {
    if (cnt_4 && cnt_7) return 4;
  }
  return -1;
}

int main() {
  while (cin >> in) {
    cout << solve() << endl;
  }
  return 0;
}

C. Lucky Sum / Accepted / 1076

いろいろ試行錯誤しましたが、lukcy numberの配列をまわしていって足してく感じに落ち着いた。

最初、next(x)のx > 777777777以降は4444444444になるのを忘れてた。

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

const ll MAX_N = 1000000002;
int l, r;
set<ll> s;
ll list[2000];

ll solve() {
  ll ans = 0;
  ll cur = l;
  rep (i,s.size()+1) {
    if (list[i] >= cur) {
      if (list[i] < r) {
        ans += (list[i] - cur + 1) * list[i];
        cur = list[i] + 1;
      } else {
        ans += (r - cur + 1) * list[i];
        break;
      }
    }
  }
  return ans;
}

void make_lucky(ll a) {
  if (a > 0) s.insert(a);
  a *= 10;
  if (a > MAX_N) return;
  make_lucky(a + 4);
  make_lucky(a + 7);
}

int main() {
  make_lucky(0L);
  int ptr = 0;
  foreach(s,i) {
    list[ptr] = *i;
    ptr++;
  }
  list[ptr] = 4444444444LL;
  while (cin >> l >> r) {
    cout << solve() << endl;
  }
  return 0;
}

D. Lucky Transformation / TLE on 9

ほかの方のを参考にしたところ、ループの処理が大事だったみたいだ。。

447, 477のループになるのは気づいたけど別にいいやって思ってた。

修正済み。

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

int n, k;
string in;

string solve() {
  string ret = in;
  int prev = -1;
  rep (i,n-1) {
    if (in[i] == '4' && in[i+1] == '7') {
      prev = i; break;
    }
  }
  
  if (prev == -1) return ret;

  for (int i = k - 1; i >= 0; --i) {
    if (prev >= n) break;
    bool ok = false;
    // loop check
    if (prev + 2 <= n - 1) {
      if (!(prev % 2)) {
        if ((ret[prev] == '4' && ret[prev+1] == '4' && ret[prev+2] == '7') ||
           (ret[prev] == '4' && ret[prev+1] == '7' && ret[prev+2] == '7') ) {
           i %= 2;
        }
      }
    }
    if (ret[prev] == '4' && ret[prev+1] == '7') ok = true;
    if (!ok) {
      for (int j=prev; j<n; ++j) if (ret[j] == '4' && ret[j+1] == '7') {
        ret[j] = ret[j+1] = (j%2) ? '7' : '4';
        if (j > 0 && ret[j-1] == '4' && ret[j] == '7') {
          prev = j-1;
        } else if (j+2 <= n-1 && ret[j+1] == '4' && ret[j+2] == '7') {
          prev = j+1;
        } else {
          prev = j+2;
        }
        ok = true;
        break;
      }
      if (!ok) break;
    } else {
      ret[prev] = ret[prev+1] = (prev%2) ? '7' : '4';
      if (prev > 0 && ret[prev-1] == '4' && ret[prev] == '7') {
        prev = prev-1;
      } else if (prev+2 <= n-1 && ret[prev+1] == '4' && ret[prev+2] == '7') {
        prev = prev+1;
      } else {
        prev = prev+2;
      }
    }
  }
  return ret;
}

int main() {
  while (cin >> n >> k >> in) {
    cout << solve() << endl;
  }
  return 0;
}

rate := 1445 (+149)

2011-10-26

SRM 522 Div2

| 16:57

oox

250. PointErasingTwo / Passed System Test / 179

すべての場合を試すだけ。

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

int check[52][52];

class PointErasingTwo {
public:
  int getMaximum(vector <int> y) {
    int i, j, sz = y.size(), k, l;
    rep (i,52) rep (j,52) check[i][j] = 0;

    rep (i,sz) {
      check[y[i]][ i ] = 1;
    }

    int ans = 0;    
    rep (i,sz) {
      rep (j,sz) if (i != j) {
        int sx = min(i, j), sy = min(y[i], y[j]);
        int gx = max(i, j), gy = max(y[i], y[j]), cnt = 0;
        //printf("(%d,%d)->(%d,%d)\n", sx, sy, gx, gy);
        for (k = sx + 1; k < gx; ++k) {
          for (l = sy + 1; l < gy; ++l) {
            if (check[l][k]) cnt++;
          }
        }
        ans = max(ans, cnt);
      }
    }
    
    return ans;
  }
};

check[ y[i] ][i] = 1の部分をcheck[i][ y[i] ] = 1と書いた間違いに気づくまでにかなりかかり、点数ががが…

550. RowAndManyCoins / Passed System Test / 420

結局、初手で決められなければアリスの負けじゃないかという結論に

class RowAndManyCoins{
public:
  string getWinner(string cells) {
    int sz = cells.size();
    if (cells[0] == 'A' || cells[sz-1] == 'A') return "Alice";
    return "Bob";
  }
};

900. CorrectMultiplicationTwo / Failed System Test

勝手に問題を誤読してFailedした…。

調整された各A,B,Cに対しても、1以上10^6以下になるだろうと決め付けて全探索コードを出す…。

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

const int MAX_SZ = 1000000;

class CorrectMultiplicationTwo {
public:  
  int getMinimum(int a, int b, int c) {
    int i, j, ans = 1<<28;
    
    for (i = 1; i <= MAX_SZ; ++i) {
      for (j = 1; j <= MAX_SZ; ++j) {
        if (i * j > MAX_SZ) break;
        int C = i * j;
        ans = min(abs(a - i) + abs(b - j) + abs(C - c), ans);
      }
    }
    
    return ans;
  }
};

システムテストの(a,b,c) => (101, 9901, 1000000) で、恐らく最小になる組み合わせが(A,B,C) => (101, 9901, 1000001)で合計誤差が1なのだけど、if文でbreakしてるから誤差1の場合にansが更新されずに死んでた。

もちろん、MAX_SIZE = 1000001にすれば通るんだけど、これはあってるのか?

調整により生成されたCがMAX_SIZEを超えるような場合で、かつ誤差最小を満たす場合があるなら間違いなんだけど。。

でも、Div1はa,b,cの制約が1から10^9なので、Div2は全探索もおkってことなのかとか思ったり。。


rate := 1085 -> 1071

250ががが

2011-10-19

RUPC2011

| 02:40

当日バイトで参加しなかったのでまったり解いた。

A. Swap Cipher

かなりあほっぽいけど計算量は大丈夫。

int n, a[102], b[102];

int main() {
  int i, j;
  while (cin >> n, n) {
    string in;
    cin >> in;
    rep (i,n) cin >> a[i] >> b[i];
    rep (i,n) {
      a[i]--; b[i]--;
    }
    
    for (i = n - 1; i >= 0; i--) {
      int ai = a[i], bi = b[i];
      int d = abs(ai - bi);
      for (j = 0; j < d; j++) {
        in[ai]++;
        in[bi]++;
        if (in[ai] > 'z') in[ai] = 'a';
        if (in[bi] > 'z') in[bi] = 'a';
      }
      swap(in[ai], in[bi]);
    }
    
    cout << in << endl;
  }
  return 0;
}

B. Problem B

作業時間が難易度の整数倍になるけど、難易度がmより大きい場合は

作業時間の申請を0としたら通った。0倍も整数倍なんですね。。

int n, m, a[1002];

int main() {
  int i;
  while (cin >> n >> m, n|m) {
    rep (i,n) cin >> a[i];
    
    int cur_time = 0, cur = -1, cur_lv = 1002;
    bool multi = false;
    rep (i,n) {
      if (i == 0) {
        cur_time = m - (m % a[i]);
        cur = 0;
        cur_lv = a[i];
        continue;
      }
      int tmp_time = m - (m % a[i]);
      if (a[i] > m) tmp_time = 0;
      if (tmp_time > cur_time) continue;
      else if (tmp_time == cur_time) {
        if (cur_lv == a[i]) {
          multi = true;
          continue;
        }
        if (cur_lv < a[i]) continue;
        if (cur_lv > a[i]) {
          cur_lv = a[i];
          cur = i;
          continue;
        }
        multi = true; continue;
      }
      else if (tmp_time < cur_time) {
        multi = false;
        cur_time = tmp_time;
        cur = i;
        cur_lv = a[i];
      }
    }
    cout << ((multi) ? n : cur+1) << endl;
  }
  return 0;
}

C. Seishun 18 Kippu

sirokurostoneが乗る駅から2D好きな人が乗る駅までの経路 の最短コストと

2D好きな人物が乗る駅からA津大学がある駅の場所まで の最短コストを出す

typedef pair<int,int> P;

int n, m, d, t;
vector<P> V[502];
const int inf = 1<<28;
int dp[502];

int dijkstra(int s, int g) {
  priority_queue<P,vector<P>,greater<P> > q;
  fill(dp, dp + n, inf);
  dp[s] = 0;
  q.push(P(0,s));
  
  while (!q.empty()) {
    P p = q.top(); q.pop();
    int v = p.second;
    if (dp[v] < p.first) continue;
    for (int i = 0; i < V[v].size(); i++) {
      P p2 = V[v][i];
      if (dp[p2.first] > dp[v] + p2.second) {
        dp[p2.first] = dp[v] + p2.second;
        q.push(P(dp[p2.first], p2.first));
      }
    }
  }
  
  return dp[g];
}

int main() {
  int i, j;
  while (cin >> n >> m, n|m) {
    rep (i,n) V[i].clear();
    
    map<string,int> hash;
    string spg[3], a[2];
    int station_count = 0;

    rep (i,3) cin >> spg[i];
    rep (i,3) {
      if (!hash.count(spg[i])) {
        hash.insert(make_pair(spg[i], station_count));
        station_count++;
      }
    }
        
    rep (i,m) {
      cin >> a[0] >> a[1] >> d >> t;
      rep (j,2) if (!hash.count(a[j])) {
        hash.insert(make_pair(a[j], station_count));
        station_count++;
      }
      int u = hash[a[0]], v = hash[a[1]];
      int cost = d / 40 + t;
      V[u].push_back(P(v, cost));
      V[v].push_back(P(u, cost));
    }
    
    int ans = dijkstra(hash[spg[0]], hash[spg[1]]) 
      + dijkstra(hash[spg[1]], hash[spg[2]]);
    cout << ans << endl;
  }
  return 0;
}

D. The Legendary Sword

魔王が伝説の剣を壊すというのは合理的で納得した。

適当に全探索+枝狩りで解けると思ったけどTLE余裕だったので

これもグラフにしてダイクストラで通った。SとGしかない場合の処理でつまづいた。

ement

F. Farey Sequence

dp出来ないけど、なんとなく一つ前の計算結果を使うことは分かったので

あとは適当にF0からF8くらいの場合まで紙に書いて、適当に法則を見つけて実装したら通った。

typedef long long ll;

const int MAX_N = 1000002;

ll dp[MAX_N], subs[MAX_N];

bool sieve[MAX_N];

int main() {
  int T, i, j, temp;

  fill(dp, dp + MAX_N, -1);
  fill(subs, subs + MAX_N, 0);
  fill(sieve, sieve + MAX_N, true);

  sieve[0] = sieve[1] = false;
  for (i = 4; i < MAX_N; i+=2) sieve[i] = false;
  for (i = 3; i < MAX_N; i+=2) if (sieve[i]) {
    for (j = i+i; j < MAX_N; j+=i) sieve[j] = false;
  }
  
  dp[1] = 2;
  for (i = 2; i < MAX_N; i++) {
    if (sieve[i]) {
      dp[i] = dp[i-1] + i-1;
      for (j = i+i; j < MAX_N; j+=i) subs[j] += i-1;
      continue;
    }
    int add = i-1 - subs[i];
    dp[i] = dp[i-1] + add;
    for (j = i+i; j < MAX_N; j+=i) subs[j] += add;
  }
  
  cin >> T;
  rep (i,T) {
    cin >> temp;
    cout << dp[temp] << endl;
  }
  return 0;
}

SRM 521 Div2

| 02:23

xox

250. RedAndGreen / Failed System Test

まぬけなミスで落とした。250は早解きの強迫観念に負けている…。

500. MissingParentheses / Passed System Test / 489

ICPC2011のB弱体化ばーじょん。

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

class MissingParentheses { 
public: 
  int countCorrections(string par) { 
    int i, sz = par.size(); 
    stack<char> s; 
    rep (i,sz) { 
      if (s.size() == 0) { 
        s.push(par[i]); continue; 
      } 
      if (par[i] == ')' && s.top() == '(') { 
        s.pop(); continue; 
      } 
      s.push(par[i]); 
    } 
    return s.size(); 
  } 
};

250のせいで微増…。

rate := 1074 -> 1085

2011-10-06

SRM 520 Div2

| 16:58

oox

250. SRMRoomAssignmentPhase / Passed System Test / 222

ソートして見る。

500. SRMCodingPhase / Passed System Test / 353

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

const int w[3] = { 2, 4, 8 }; 

class SRMCodingPhase { 
public: 
  int countScore(vector <int> points, vector <int> skills, int luck) { 
    int i, ans = 0; 
    for (int S=0; S<(1<<3); S++) { 
      int times = 0, tl = luck, tsum = 0;       
      rep (i, 3) if (S >> i & 1) times += skills[i]; 
      if (times - luck > 75) continue; 

      for (i=2; i>=0; i--) if (S >> i & 1) { 
        int cur_t = skills[i]; 
        if (tl > 0) { 
          if (tl >= cur_t) { tl -= cur_t-1; cur_t = 1;} 
          else { cur_t -= tl; tl = 0; } 
        } 
        tsum += points[i] - w[i]*cur_t; 
      } 

      ans = max(ans, tsum); 
    } 

    return ans; 
  } 
};

買う買わないのパターンをすべて試して、あとは得点の高い方からluckを振り分ける。

submitした後に迷ったけど大丈夫でした。

1000. SRMSystemTestPhase / Opened

途中..

rate := 963 > 1074

Google Code Jam Japan 2011

16:51

372th 28/54

A. カードシャッフル ox

ナイーブ実装だけ書いてsmallだけ出す。

1枚に着目して逆からやってくのは気づかなかった。

連続部分に分解していく方法は考えたけどいい実装が思いつかなかった。

B. 最高のコーヒー ox

全探索だけ書いてsmall。

Editorial読む。

C. ビット数 oo

よく分からない方法で通った。

a,bに分解する時、片方を2^n-1の数にするようにしたら通った。

dpらしい。