SRM607 div2 med PalindromicSubstringsDiv2

TopCoder Statistics - Match Overview

問題概要

  • 文字列Sの中に回文が何個あるか

制約

  • |S| ≦ 5000

解説

文字列Aが回文の時Aの両サイドに同じ文字が連結した文字列も回文となる。

同じ文字でない文字が連結したらその時点で回文では無くなる。

回文の中心がsiとなるような回文が何個あるかはO(|S|)で求められる。

よって中心の候補はO(|S|)なので、全体の計算量はO(|S|^2)で間に合う。

回文の長さが奇数の時と偶数の時で調べる必要がある。

コード

class PalindromicSubstringsDiv2 {
public:
  int count(vector <string> S1, vector <string> S2) {
    string s = "";
    FOR(i,0,S1.size()) s += S1[i];
    FOR(i,0,S2.size()) s += S2[i];
    int len = s.length();
    int ret = 0;
    // even
    FOR(i,0,len) {
      int l = i, r = i + 1;
      while(l >= 0 && r < len && s[l] == s[r]) {
        ret++;
        l--;
        r++;
      }
    }
    // odd
    FOR(i,0,len) {
      int l = i, r = i;
      while(l >= 0 && r < len && s[l] == s[r]) {
        ret++;
        l--;
        r++;
      }
    }
    return ret;
  }
};

SRM606 div2 med EllysNumberGuessing

TopCoder Statistics - Match Overview

問題概要

  • Aさんが1以上1000000000以下の数字を思い浮かべる
  • BさんがAさんが思い浮かべた数字がx1,x2,...,xnかどうか聞く
  • Aさんは思い浮かべた数字とxとの差の絶対値yを答える
  • Aさんが思い浮かべた数字が一意に定まる時はその答えを、複数考えられる場合は-1、矛盾する場合は-2を答えよ

制約

  • n ≦ 50
  • Aさんが思い浮かべる数字は1以上1000000000以下

解説

思い浮かべた数字の候補はxi±yiである。

map[候補となる数字] := 回答より候補となった回数とする。

候補となる数字は1以上1000000000以下であることに注意。

map == nとなる数字が1つだけならそれが答え、2つあるなら-1、1つもないなら-2。

コード

class EllysNumberGuessing {
public:
  int getNumber(vector <int> guesses, vector <int> answers) {
    int n = answers.size();
    map<int, int> MAP;
    FOR(i,0,n) {
      int c = guesses[i] + answers[i];
      int d = guesses[i] - answers[i];
      MAP[c]++;
      if(c != d) MAP[d]++;
    }
    int cnt = 0;
    int ret = 0;
    for(auto m : MAP) {
      if(m.second == n && m.first > 0 && m.first <= 1e9) {
        cnt++;
        ret = m.first;
      }
    }
    if(cnt == 0) return -2;
    else if(cnt == 1) return ret;
    else return -1;
  }
};

SRM605 div2 med AlienAndGame

TopCoder Statistics - Match Overview

解説

1 * 1, 2 * 2, ...の正方形が作れるかどうか順に調べた。

左からi右からjのマスが正方形の左上として調べた。

コード

class AlienAndGame {
public:
  int getNumber(vector <string> board) {
    int H = board.size();
    int W = board[0].length();
    int ret = 1;
    FOR(s,1,W+1) {
      FOR(i,0,H) {
        FOR(j,0,W) {
          bool ok = true;
          FOR(k,0,s) {
            if(i + k >= H) {
              ok = false;
              break;
            }
            if(!(board[i+k].substr(j, s) == string(s, 'W') || board[i+k].substr(j, s) == string(s, 'B'))) {
              ok = false;
              break;
            }
          }
          if(ok) ret = s;
        }
      }
    }
    return ret * ret;
  }
};

SRM604 div2 med PowerOfThreeEasy

問題概要

  • step k でx方向かy方向に3k進む
  • stepは0から始まる
  • xとyが与えられるのでその座標にちょうど到達できるか判定せよ

制約

  • 0≦x≦109
  • 0≦y≦109

解説

319 = 1162261467なので高々19ステップで制約の座標には到達できるかどうかわかる。

各stepでx方向に行くかy方向に行くか全探索O(219)。

コード

class PowerOfThreeEasy {
public:
  string ableToGet(int x, int y) {
    int th[20]; FOR(i,0,20) th[i] = pow(3,i);
    FOR(i,0,1<<20) {
      int X = 0, Y = 0;
      FOR(j,0,20) {
        if(X == x && Y == y) return "Possible";
        if((i>>j)&1) X += th[j];
        else Y += th[j];
      }
      if(X == x && Y == y) return "Possible";
    }
    return "Impossible";
  }
};

SRM603 div2 Med SplitIntoPairs

TopCoder Statistics - Match Overview

問題概要

  • 素数が偶数の配列Aが与えられる
  • Aの要素2つを選んでペアを|A|/2個作る
  • ペアの積がX以上となるようなペアの最大数を求めよ

制約

  • |A| % 2 = 0
  • -109≦A≦109
  • -109≦X≦-1

解説

Xが負であることがポイント。

偶数偶数と奇数奇数ペアは絶対に正になる。

できるだけ同じ符号同士でペアにすればいい。

符号が正である要素が偶数個あるなら全てのペアを同じ符号同士にできる(答えは|A|/2個)。

符号が正である要素が奇数個なら偶数*奇数のペアが1つできてしまう。

偶数の要素と奇数の要素の全ての組み合わせの積を計算して最大値がX以上であれば答えは|A|/2、そうでないなら|A|/2-1。

コード

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <bitset>
#include <cstring>
using namespace std;
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)
#define CLR(mat) memset(mat, 0, sizeof(mat))
typedef long long ll;
class SplitIntoPairs {
public:
  int makepairs(vector <int> A, int X) {
    int plus = 0;
    FOR(i,0,A.size()) {
      if(A[i] >= 0) plus++;
    }
    if(plus % 2 == 0) return A.size() / 2;
    else {
      ll mx = -2e9;
      sort(A.begin(), A.end());
      for(int i = A.size() - 1; A[i] >= 0; i--) {
        for(int j = 0; A[j] < 0; j++) {
          mx = max(mx, (ll)A[i]*(ll)A[j]);
        }
      }
      if(mx >= X) return A.size() / 2;
      else return A.size() / 2 - 1;
    }
  }
};

AGC001 B - Mysterious Light

やり直し

B: Mysterious Light - AtCoder Grand Contest 001 | AtCoder

正三角形中の光の経路の長さを求める問題。

解法

f:id:nenuon61:20171015174844p:plain

f(a, b) := 辺の長さがaとbの平行四辺形の中を光が、2回反射するまでに進む距離とする。

2回反射する時点でまた平行四辺形ができる。

a < bの時、

f(a, b) = f(a, b - a) + 2a

f(a, a) = a

を満たす。

再帰的に計算していけばOKだが辺の長さが≦1012なのでTLEしてしまう。

そこで式を、

a < bの時、

f(a, b) = f(a, b%a) + 2a * (b / a)

b % a == 0の時、

f(a, b) = 2a * (b / a) - a

とすればOK。

コード

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <bitset>
#include <cstring>
using namespace std;
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)
#define CLR(mat) memset(mat, 0, sizeof(mat))
typedef long long ll;
ll f(ll a, ll b) {
  ll x = min(a, b);
  ll y = max(a, b);
  if(y % x == 0) return y / x * x * 2 - x;
  return 2 * x * (y / x) + f(x, y % x);
}
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  ll N, X; cin >> N >> X;
  cout << N + f(X, N - X) << endl;
  return 0;
}

ABC075参加記録

100-200-300-400だったので全完できた!

実装がいつものABCより重い気がした。

A - One out of Three

A - One out of Three

A == BならCを出力
B == CならAを出力
C == AならBを出力

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  int a,b,c; cin >> a >> b >> c;
  if(a == b) cout << c << endl;
  if(b == c) cout << a << endl;
  if(a == c) cout << b << endl;
  return 0;
}

B - Minesweeper

B - Minesweeper

'.'の周りの8マスの'#'の個数を数える。

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  int H, W; cin >> H >> W;
  vector<string> vs(H);
  FOR(i,0,H) cin >> vs[i];
  int vy[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
  int vx[8] = {0, 1, 1, 1, 0, -1, -1, -1};
  FOR(h,0,H) {
    FOR(w,0,W) {
      if(vs[h][w] == '.') {
        int cnt = 0;
        FOR(i,0,8) {
          int y = h + vy[i];
          int x = w + vx[i];
          if(y >= 0 && y < H && x >= 0 && x < W && vs[y][x] == '#') cnt++;
        }
        vs[h][w] = char('0' + cnt);
      }
    }
  }
  FOR(i,0,H) cout << vs[i] << endl;
  return 0;
}

C - Bridge

C - Bridge

辺を1本ずつ取り除いてワーシャルフロイドを使った。

ある辺を取り除いてワーシャルフロイドし、全ての頂点間で移動可能かどうか判定し、不可能な頂点の組みがあったらans++する。

const int inf = 1e9;
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  // ワーシャルフロイド
  int n,m;// 頂点、辺
  cin >> n >> m;
  int a[100], b[100], c[100], dist[100][100];
  CLR(a);CLR(b);CLR(c);
  FOR(i,0,m){
    cin >> a[i] >> b[i];
    a[i]--;b[i]--;
    c[i] = 1;
  }
  int ans = 0;
  FOR(t,0,m) {
    FOR(i,0,n){
      FOR(j,0,n){
        if(i==j) dist[i][j] = 0;
        else dist[i][j] = inf;
      }
    }
    // 連結してるとこはcを代入
    FOR(i,0,m){
      if(i == t) continue;
      dist[a[i]][b[i]] = min(dist[a[i]][b[i]], c[i]);
      dist[b[i]][a[i]] = min(dist[b[i]][a[i]], c[i]);
    }
    FOR(k,0,n) FOR(i,0,n) FOR(j,0,n) {
      dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
    }
    bool brk = false;
    FOR(i,0,n) {
      FOR(j,0,n) {
        if(dist[i][j] == inf) {
          ans++;
          brk = true;
          break;
        }
      }
      if(brk) break;
    }
  }
  cout << ans << endl;
  return 0;
}

普通にDFSで到達可能か調べればよかった。

D - Axis-Parallel Rectangle

D - Axis-Parallel Rectangle

長方形は無限に作れるが、同じ点を含む長方形で面積が一番小さい長方形は、4辺に点がある(角に点がある場合は2辺に点があると考える)長方形である。よって考える長方形は4辺に点がある長方形だけで良い。

x軸に平行な辺上の2点と、y軸に平行な辺上の2点を全探索。

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  int N, K; cin >> N >> K;
  ll x[N], y[N];
  FOR(i,0,N) cin >> x[i] >> y[i];
  ll ans = 4e18;
  // x方向2つの点
  FOR(i,0,N) {
    FOR(j,0,N) {
      if(i == j || x[i] >= x[j]) continue;
      // y方向2つの点
      FOR(k,0,N) {
        FOR(l,0,N) {
          if(k == l || y[k] <= y[l]) continue; 
          if(x[i] <= x[k] && x[j] >= x[k] && x[i] <= x[l] && x[j] >= x[l]) {
            if(y[i] <= y[k] && y[i] >= y[l] && y[j] <= y[k] && y[j] >= y[l]) {
              int cnt = 0;
              FOR(c,0,N) {
                if(x[c] >= x[i] && x[c] <= x[j] && y[c] <= y[k] && y[c] >= y[l]) cnt++;
              }
              if(cnt >= K) {
                ans = min(ans, (x[j] - x[i]) * (y[k] - y[l]));
              }
            }
          }
        }
      }
    }
  }
  cout << ans << endl;
  return 0;
}