ferinの競プロ帳

競プロについてのメモ

ABC100 A - Happy Birthday!

問題ページ
A: Happy Birthday! - AtCoder Beginner Contest 100 | AtCoder

解法

a <= 8 && b <= 8 なら条件を満たしているのでYay!、違うなら:(を出力する。

abs(a-b) <= 1 ならとか考えてたら2分かかってしまった。

ソースコード

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll
using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define PB push_back

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template <typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')';
  return out;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'[';
  REP(i, a.size()) {out<<a[i];if(i!=a.size()-1)out<<',';}
  out<<']';
  return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

signed main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  string s, t;
  int a, b;
  cin >> a >> b;
  if(a <= 8 && b <= 8) cout << "Yay!" <<endl;
  else cout << ":(" << endl;

  return 0;
}

ABC100 B - Ringo's Favorite Numbers

問題ページ
B: Ringo's Favorite Numbers - AtCoder Beginner Contest 100 | AtCoder

考えたこと

  • ちょうど0回割り切れるって何だと思ってサンプルを見たら1回も割りきれないことっぽい
  • nの後ろに'0'を2d個つければいいでしょと思って投げる
  • 落ちてて何事かと思ったら"ちょうど"の部分が問題
  • D=0,n=100のときに100を出力してるけどこれは100で1回割りきれる
  • n=100なら101にすべき
  • D=1,2でn=100のときも同じ

ソースコード

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll
using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define PB push_back

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template <typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')';
  return out;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'[';
  REP(i, a.size()) {out<<a[i];if(i!=a.size()-1)out<<',';}
  out<<']';
  return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

signed main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  int d, n;
  cin >> d >> n;
  if(d == 0 && n == 100) cout << 101 << endl;
  else if(d == 1 && n == 100) cout << 10100 << endl;
  else if(d == 2 && n == 100) cout << 1010000 << endl;
  else cout << to_string(n) + string(2*d, '0') << endl;

  return 0;
}

ABC100 C - \*3 or /2

問題ページ C: *3 or /2 - AtCoder Beginner Contest 100 | AtCoder

考えたこと

  • 全ての要素に対して2で割るか3倍するのどちらかをするのかと思う
  • 全てのiに対して3倍するって何のことだと思って数分が経過する
  • 操作1回につき各要素について2で割るか3倍するかのどっちかをする、ただし全部3倍はだめってことっぽい
  • 3倍したとしても2で割る数は増えない
  • 全て3倍がだめならひとつだけ2で割って他を3倍すればいい
  • sum(a[i]を2で割れる数) が答えになる

ソースコード

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll
using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define PB push_back

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template <typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')';
  return out;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'[';
  REP(i, a.size()) {out<<a[i];if(i!=a.size()-1)out<<',';}
  out<<']';
  return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

signed main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  int n;
  cin >> n;
  VI a(n);
  REP(i, n) cin >> a[i];

  int ret = 0;
  REP(i, n) {
    while(a[i] && a[i]%2==0) a[i] /= 2, ret++;
  }
  cout << ret << endl;

  return 0;
}

ABC100 D - Patisserie ABC

問題ページ
D: Patisserie ABC - AtCoder Beginner Contest 100 | AtCoder

考えたこと

  • 与えられる値が全て正だったらx[i]+y[i]+z[i]が大きい方から取ればいいだけ
  • 最大化するのは絶対値で負がある
  • それぞれ正負を試せばいいのでは?
  • 正負を固定すればソートして大きい方から貪欲に取っていけばよさそう
  • O(nlogn) で通りそうなので投げると通る

未証明貪欲でWJで10分待つの心臓に悪い

ソースコード

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll
using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define PB push_back

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template <typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')';
  return out;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'[';
  REP(i, a.size()) {out<<a[i];if(i!=a.size()-1)out<<',';}
  out<<']';
  return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

signed main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  int n, m;
  cin >> n >> m;
  VI x(n), y(n), z(n);
  REP(i, n) cin >> x[i] >> y[i] >> z[i];

  int ans = 0;
  REP(i, 1<<3) {
    VI v;
    REP(j, n) {
      int tmp = 0;
      if(i&1) tmp += x[j];
      else tmp -= x[j];
      if(i&2) tmp += y[j];
      else tmp -= y[j];
      if(i&4) tmp += z[j];
      else tmp -= z[j];
      v.PB(tmp);
    }
    sort(ALL(v));
    reverse(ALL(v));
    int ret = 0;
    REP(j, m) ret += v[j];
    chmax(ans, ret);
  }
  cout << ans << endl;

  return 0;
}

AOJ2596 Points and Lines

問題ページ
Points and Lines | Aizu Online Judge

考えたこと

  • BNFがパッと目に入って明らかに構文解析
  • 幾何の操作がBNFの形で与えられるのでその結果を求める
  • 幾何の操作は2点から直線を作る操作とreflectionと直線の交点
  • 割と単純な操作でライブラリを貼ればいいのでここはできる
  • 構文解析パートで難しい点としてLL(1)でない
  • 1字先読みしたところで<line-factor>か<point-factor>かとかの区別がつかない
  • ここでJAG合宿2018day1Eを思い出すとpointとlineをまとめたくなる
  • pointとlineをまとめられればそもそも区別する必要がない
  • 適当な構造体を作り構造体が保持しているのがpointなのかlineなのかを変数typeで管理
  • こうすると@が来た時に左辺と右辺のtypeから@ですべき操作を把握できる
  • BNFのpointとlineの部分を以下のように書く
<pl> = <plf> | <pl>@<plf>
<plf> = (<pl>) | (<num>,<num>)
  • これはが左再帰なので除去する
<pl> = <plf><pl_tail>
<pl_tail> = @<pl><pl_tail> | empty

ソースコード

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll
using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define PB push_back

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template <typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')';
  return out;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'[';
  REP(i, a.size()) {out<<a[i];if(i!=a.size()-1)out<<',';}
  out<<']';
  return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

const double EPS = 1e-8;

using R = long double;
using P = complex<R>;
using L = pair<P,P>;
using G = vector<P>;
struct C {
  P c; R r;
  C() {}
  C(const P &a, const R &b) : c(a), r(b) {}
};
struct S : public L {
  S() {}
  S(const P &a, const P &b) : L(a,b) {}
};

inline int sgn(const R& r) { return (r>EPS) - (r<-EPS); }
inline R dot(const P& a, const P& b) {
  return real(a)*real(b) + imag(a)*imag(b);
}
inline R det(const P& a, const P& b) {
  return real(a)*imag(b) - imag(a)*real(b);
}
inline P vec(const L& l) {return l.second - l.first;}
namespace std {
    bool operator < (const P& a, const P& b) {
        return sgn(real(a-b)) ? real(a-b) < 0 : sgn(imag(a-b)) < 0;
    }
    bool operator == (const P& a, const P& b) {
        return sgn(real(a-b)) == 0 && sgn(imag(a-b)) == 0;
    }
  bool cmp_y (const P& a, const P& b) {
    return sgn(imag(a-b)) ? imag(a-b) < 0 : sgn(real(a-b)) < 0;
  }
}

// P,L,Sについて入力
inline istream& operator>>(istream& is, P& p) {
  R x, y;
  is >> x >> y;
  p = P(x, y);
  return is;
}
inline istream& operator>>(istream& is, L& l) {
  P a, b;
  is >> a >> b;
  l = L(a, b);
  return is;
}

// 射影
P inline projection(const L &l, const P &p) {
  R t = dot(p-l.first, l.first-l.second) / norm(l.first-l.second);
  return l.first + t*(l.first-l.second);
}
// 反射
P inline reflection(const L &l, const P &p) {
  return p + (R)2 * (projection(l, p) - p);
}

// 交差判定
template<bool strict=false> inline bool intersect(const L&l1, const L&l2) {
  if(strict) return sgn(det(vec(l1),vec(l2))) != 0;
  return sgn(det(vec(l1),vec(l2))) != 0 || l1 == l2;
}

// 交点 交差判定を先にすること!!!
inline P crosspoint(const L& l1, const L& l2) {
  R ratio = det(vec(l2), l2.first-l1.first)/det(vec(l2),vec(l1));
  return l1.first + vec(l1)*ratio;
}

struct node {
  int type;
  P p;
  L l;
};

node plf();
node pl_tail();
node pl();

string s;
int pos = 0;
int number() {
  int ret = 0;
  bool neg = false;
  if(s[pos] == '-') neg = true, pos++;
  while(isdigit(s[pos])) {
    ret *= 10;
    ret += s[pos] - '0';
    pos++;
  }
  if(neg) ret *= -1;
  return ret;
}

node plf() {
  node ret;
  pos++;
  if(s[pos] == '-' || isdigit(s[pos])) {
    int vl = number();
    pos++;
    int vr = number();
    ret.type = 0;
    ret.p = P(vl, vr);
  } else {
    ret = pl();
  }
  pos++;
  return ret;
}

node pl() {
  // plfを読む
  node ret = plf();
  // pl_tailを読む
  while(pos < s.size() && s[pos] != ')') {
    if(s[pos] == '@') {
      pos++;
      node tmp = plf();
      // ret = ret @ tmp
      if(ret.type == 0 && tmp.type == 0) {
        ret.type = 1;
        ret.l = L(ret.p, tmp.p);
      } else if(ret.type == 0 && tmp.type == 1) {
        P p = reflection(tmp.l, ret.p);
        ret.type = 0;
        ret.p = p;
      } else if(ret.type == 1 && tmp.type == 0) {
        P p = reflection(ret.l, tmp.p);
        ret.type = 0;
        ret.p = p;
      } else if(ret.type == 1 && tmp.type == 1) {
        P p = crosspoint(ret.l, tmp.l);
        ret.type = 0;
        ret.p = p;
      } else {
        assert(false);
      }
    } else {
      cout << "err" << pos << " " << s[pos] << endl;
      assert(false);
    }
  }
  return ret;
}

signed main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  while(true) {
    cin >> s;
    if(s == "#") break;

    pos = 0;
    node ret = pl();
    cout << fixed << setprecision(15) << ret.p.real() << " " << ret.p.imag() << endl;
  }

  return 0;
}

AOJ2712 Escape

問題ページ
Escape | Aizu Online Judge

考えたこと

  • 閉路が存在すればそこでUターンできる
  • つまり1->閉路->1みたいな移動ができる
  • 閉路にたどり着くまでの頂点は必ず訪れることができる
  • 閉路の先にある頂点の集合は最後に取ることしてどれか一箇所しか取れない
  • 閉路を検出したい気持ちになるので二重辺連結成分分解をする
  • 二重辺連結成分分解をしたあとの木で探索をする
  • 根の頂点1が含まれる二重辺連結成分からdfsをして閉路までを辿る
  • この探索で必ず訪れられる二重辺連結成分と一箇所しか取れない頂点集合を分類
  • 一箇所しか取れない頂点集合のうち重みが最大の集合を取るとする

二重辺連結成分初めて書いた

ソースコード

#include <bits/stdc++.h>

using namespace std;

struct twoEdgeComponents {
    int n;
    vector<vector<int>> g;             // 入力のグラフ
    vector<int> cmp;                         // 頂点iが属する連結成分
    vector<vector<int>> each_bcc;  // 連結成分iに属する頂点
    vector<pair<int,int>> bridge; // 橋の辺を列挙
    vector<int> order;                       // 頂点iを訪れた順番
    vector<bool> inS;                            // 頂点iがSに存在している
    stack<int> roots, S;                 // 根の候補、訪れた頂点のうちまだ見ていない頂点

    twoEdgeComponents() {}
    twoEdgeComponents(vector<vector<int>> g_) : n(g_.size()), g(g_) {}
    // 辺(p,q)を追加
    void add_edge(int p, int q) {
        g[p].push_back(q);
        g[q].push_back(p);
    }
    // 橋、二重辺連結成分
    void dfs(int cur, int prev, int &k) {
        order[cur] = ++k;
        S.push(cur); inS[cur] = true;
        roots.push(cur);
        for(auto to: g[cur]) {
            if(order[to]==0) dfs(to, cur, k);
            else if(to!=prev && inS[to]) {
                while(order[roots.top()] > order[to]) roots.pop();
            }
        }
        if(cur == roots.top()) {
            if(prev!=-1) bridge.push_back({prev, cur});
            vector<int> bcc;
            while(1) {
                int node = S.top(); S.pop(); inS[node] = false;
                bcc.push_back(node);
                if(node==cur) break;
            }
            each_bcc.push_back(bcc);
            roots.pop();
        }
    }
    // 橋と二重辺連結成分
    void bcc() {
        order.assign(n, 0);
        inS.assign(n, false);
        cmp.assign(n, -1);
        int k = 0;
        for(int i=0; i<n; ++i) {
            if(order[i] == 0) {
                dfs(i, -1, k);
            }
        }
        for(int i=0; i<(int)each_bcc.size(); ++i) {
            for(auto j: each_bcc[i]) {
                cmp[j] = i;
            }
        }
    }
    // 二重編連結成分分解したあとのグラフ(木)を取得
    vector<vector<int>> getbcc() {
        vector<vector<int>> h(each_bcc.size(), vector<int>());
        for(auto i: bridge) {
            int a = cmp[i.first], b = cmp[i.second];
            h[a].push_back(b);
            h[b].push_back(a);
        }
        return h;
    }
};

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> w(n);
    for(int i=0; i<n; ++i) cin >> w[i];
    vector<vector<int>> g(n);
    for(int i=0; i<m; ++i) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    twoEdgeComponents graph(g);
    graph.bcc();
    vector<vector<int>> tree = graph.getbcc();

    vector<int> W(graph.each_bcc.size());
    for(int i=0; i<(int)graph.each_bcc.size(); ++i) {
        for(int j=0; j<(int)graph.each_bcc[i].size(); ++j) {
            W[i] += w[graph.each_bcc[i][j]];
        }
    }

    vector<bool> v(n, false);
    function<bool(int,int)> dfs = [&](int x, int p) {
        bool ret = false;
        if(graph.each_bcc[x].size() >= 2) ret = true;
        for(auto i: tree[x]) {
            if(i == p) continue;
            ret |= dfs(i, x);
        }
        return v[x] = ret;
    };

    dfs(graph.cmp[0], -1);

    int ans = 0;
    for(int i=0; i<(int)graph.each_bcc.size(); ++i) {
        if(v[i]) ans += W[i];
    }

    int tmp = 0;
    vector<int> v2(n, 0);
    function<void(int,int,int)> dfs2 = [&](int x, int p, int cost) {
        if(!v[x]) cost += W[x];
        tmp = max(tmp, cost);
        for(auto i: tree[x]) {
            if(i == p) continue;
            dfs2(i, x, cost);
        }
    };
    dfs2(graph.cmp[0], -1, 0);

    ans += tmp;
    cout << ans << endl;

    return 0;
}

AOJ2784 Similarity of Subtrees

問題ページ
Similarity of Subtrees | Aizu Online Judge

考えたこと

  • 各頂点xを根とした部分木について配列v_xを考える
  • v_x[i]=(深さiの頂点数)とする
  • v_xが等しければその部分木は等しい
  • v_xが等しい頂点の数がa個であればa(a-1)/2個の条件を満たすペアがある
  • ある頂点yの子の配列をうまいことマージして配列v_xをつくれないか
  • マージはv_y[0]=0, v_y[i+1] = sum(v_yの子[i])になりそう
  • マージテク使えないかと思って考えるけど使える形に落ちそうにない
  • 数列v_xをハッシュ化すると簡単にならないか
  • ハッシュをローリングハッシュみたいに定義すると子のハッシュ値からハッシュが計算できそう
  • O(N)でハッシュが計算できそうなので等しいペアの数を計算すると通る

ハッシュが衝突しないかとか無駄に考えて時間を溶かした
Schwartz–Zippel lemmaで示せるらしい

ソースコード

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll
using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define PB push_back

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template <typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')';
  return out;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'[';
  REP(i, a.size()) {out<<a[i];if(i!=a.size()-1)out<<',';}
  out<<']';
  return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

int b = 1007, mo = 1e9+7;
VI g[100010];
map<int,int> v;
// 部分木xのハッシュを返す
int func(int x, int p) {
  int ret = b;
  for(int e: g[x]) {
    if(e == p) continue;
    (ret += func(e, x) * b % mo) %= mo;
  }
  v[ret]++;
  return ret;
}

signed main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  int n;
  cin >> n;
  REP(i, n-1) {
    int a, b;
    cin >> a >> b; a--, b--;
    g[a].PB(b);
    g[b].PB(a);
  }

  mo = 1e9+7;
  b = rand() % mo;
  v.clear();
  func(0, -1);

  int ret = 0;
  for(auto i: v) ret += i.second*(i.second-1)/2;
  cout << ret << endl;

  return 0;
}