みんなのプロコン2018 決勝参加記

@Luzhiled @svjetlol @ei1333333 pic.twitter.com/wQp8mqbVF5
— 寝ました (@ei1333) 2018年2月24日

油そば　東京油組総本店赤坂見附組
らてまるたしゃっふりゅーびーとで食べに行きました.
えーおいしい, おいしいね.

@LatteMalta pic.twitter.com/6fIxeNCjP4
— 寝ました (@ei1333) 2018年2月24日

東京駅一番街　仙台牛タンねぎ塩ラーメン㐂蔵
らずひるどびーとで食べに行きました.
らずひるどくんに会う難易度が高すぎる.
えーおいしい, おいしいね.

嘘をしましたごめんなしゃい. 9位でした.

A 問題 Uncommon
おっ簡単じゃ～んって思って問題見た瞬間書き始めた
サンプルがあったので提出
FirstWA
やったぜさすが僕
よくみたらサンプルあってないやんけ
考察をするとガバガバをしていることがわかる
包除原理を使うと解けそう
包除原理がわからない(人生破滅
どうせ約数とか素因数とか使うのかなぁという気持ちになるのでその辺のコードを適当にごにょごにょする
サンプルが通る
AC(26:11)

#include <bits/stdc++.h>

using namespace std;

using int64 = long long;

map< int64, int > prime_factor(int64 n)
{
  map< int64, int > ret;
  for(int64 i = 2; i * i <= n; i++) {
    while(n % i == 0) {
      ret[i]++;
      n /= i;
    }
  }
  if(n != 1) ret[n] = 1;
  return (ret);
}

int main()
{
  int N, M;
  int add[100001] = {};

  cin >> N >> M;
  for(int i = 0; i < N; i++) {
    int x;
    cin >> x;
    for(int j = 1; j * j <= x; j++) {
      if(x % j == 0) {
        add[j]++;
        if(j * j != x) add[x / j]++;
      }
    }
  }

  for(int i = 1; i <= M; i++) {
    auto x = prime_factor(i);
    vector< pair< int, int > > v(x.begin(), x.end());
    int ret = 0;
    for(int j = 0; j < (1 << v.size()); j++) {
      int fact = 1;
      for(int k = 0; k < v.size(); k++) {
        if((j >> k) & 1) fact *= v[k].first;
      }
      int sum = add[fact];
      if(__builtin_popcount(j) % 2 == 0) ret += sum;
      else ret -= sum;
    }
    cout << ret << endl;
  }
}

時間を大量に解かしてこわれた
B 問題経路が色々
おっ構築じゃ～ん

うしさんに勝ちたいので当然600は構築ゲー
— beet (@beet_aizu) 2018年2月24日

敗北
ちょっと考える
えーなんかこれもうわかんねえな(は?
わからないことがわかる
そっ閉じ

800の(←すでにむずかしい) 構成ゲー(←人生破滅、ヘドバン, 問題をそっとじ)
— 寝ました (@ei1333) 2018年2月24日

C 問題木の問題

なんかびーとしゃんがukuku09コン用にすらっくに投げた問題でて
— 寝ました (@ei1333) 2018年2月24日

びーとしゃんのじゃなかったけど僕が作った問題が出る（ウケる
つくったけど解けなさそうということで放置していた
えーなんで詰めておかなかったんだろう
ちょっと考える
前処理でオイラーツアーしておいて, 根からの距離をこの順で格納しておく
DFSで根からの距離を更新しながら頑張ることを考えると, 区間加算クエリと配列全体である値 ${x}$ が格納されている要素の数を求めるクエリができればよさそう
平方分割で解けるね
それぞれの値の数をバケットごとに累積して持っておく必要があって, unordered_map 詐欺をすると計算量は ${O((N + Q) \sqrt N)}$ .
なんかすごくバグる
えーオイラーツアーを間違えていた（最悪
1 時間くらい戦うとサンプルがやっと通る
提出するとTLE
定数倍きつすぎか～っていってるけど
えー定数倍を軽くしたりバケットサイズを変えたり根を変えたりして適当に何回か提出すると 3973 ms / 4000ms で通る(88:42)

#include <bits/stdc++.h>

using namespace std;

using int64 = long long;

int N, Q;
vector< int > g[100000];
vector< pair< int, int > > q[100000];
int tin[100000], tout[100000], ptr;


int ans[100000];
int sqrtN = 333;

struct SqrtDecomposition
{
  int N, K;
  vector< int > data;
  vector< int > bucketAdd;
  vector< unordered_map< int, int > > dist;

  SqrtDecomposition(int n) : N(n)
  {
    K = (N + sqrtN - 1) / sqrtN;
    data.assign(n, 0);
    bucketAdd.assign(K, 0);
    dist.resize(K);
  }

  void add(int s, int t, int x)
  {
    for(int k = 0; k < K; ++k) {
      int l = k * sqrtN, r = min((k + 1) * sqrtN, (int) data.size());

      if(r <= s || t <= l)
        continue;
      if(s <= l && r <= t) {
        bucketAdd[k] += x;
      } else {
        for(int i = max(s, l); i < min(t, r); ++i) {
          dist[k][data[i]]--;
          data[i] += x;
          dist[k][data[i]]++;
        }
      }
    }
  }

  int query(int pos)
  {
    int ret = 0;
    for(int k = 0; k < K; ++k) {
      if(dist[k].count(pos - bucketAdd[k])) {
        ret += dist[k][pos - bucketAdd[k]];
      }
    }
    return (ret);
  }

};


SqrtDecomposition mex(100001);

int rec(int idx, int par = -1, int dep = 0)
{
  tin[idx] = ptr;
  mex.data[ptr] = dep;
  mex.dist[ptr / sqrtN][dep]++;
  ++ptr;
  for(auto &to : g[idx]) {
    if(to == par) continue;
    rec(to, idx, dep + 1);
  }
  tout[idx] = ptr;
}


int dfs(int idx, int par = -1)
{
  for(auto &p : q[idx]) {
    int s, k;
    tie(s, k) = p;
    ans[k] = mex.query(s);
  }
  mex.add(0, N, 1);
  for(auto to:g[idx]) {
    if(to == par)continue;
    mex.add(tin[to], tout[to], -2);
    dfs(to, idx);
    mex.add(tin[to], tout[to], 2);
  }
  mex.add(0, N, -1);
}

int main()
{
  cin >> N >> Q;
  for(int i = 1; i < N; i++) {
    int x, y;
    cin >> x >> y;
    --x, --y;
    g[x].push_back(y);
    g[y].push_back(x);
  }
  for(int i = 0; i < Q; i++) {
    int x, y;
    cin >> x >> y;
    --x;
    q[x].emplace_back(y, i);
  }
  rec(N / 2);
  dfs(N / 2);
  for(int i = 0; i < Q; i++) {
    cout << ans[i] << endl;
  }
}

残り 30 分しかないね, 悲しいね
実装が下手すぎる...
B 問題に戻る
なんか小さいグリッドを繋げたい
えーここでBを解いてもbeetさんに負けることに気づいたのでD問題に行くことにする
D 問題 LCP(prefix,suffix)
えー20分で解けるのかこんなん
問題文をがんばって読む
ちょっと考察すると, 必ず同じ文字にする文字位置のペアと, 必ず違う文字にする文字位置のペアのクエリがたくさん与えられるので矛盾がないか判定する問題に帰着できる
${O(N^2)}$ は自明でUnionFindを持って愚直に同じ文字にする文字位置のペアをuniteして, 最後に違う文字位置にする文字位置のペアのクエリに対して矛盾をチェックすれば良い
怪しいので一応出すと TLE なので合ってそう
あと 15 分くらいしかないけど
unite を効率よく処理したい
辺を書くと明らかに周期性みたいなのがあるけどどう使えばいいかわからず
えーよくわからないため適当に後ろから辺をuniteしていって, すでにuniteされていたらbreakする嘘を書く
3 ケースWA
えー前からも同じようにuniteしちゃえw（最悪
通る (113:09)

#include <bits/stdc++.h>

using namespace std;

using int64 = long long;

struct UnionFind
{
  vector< int > data;

  UnionFind(int sz)
  {
    data.assign(sz, -1);
  }

  bool unite(int x, int y)
  {
    x = find(x), y = find(y);
    if(x == y) return (false);
    if(data[x] > data[y]) swap(x, y);
    data[x] += data[y];
    data[y] = x;
    return (true);
  }

  int find(int k)
  {
    if(data[k] < 0) return (k);
    return (data[k] = find(data[k]));
  }

  int size(int k)
  {
    return (-data[find(k)]);
  }
};

int main()
{
  int N, L[300000];
  cin >> N;
  for(int i = 0; i < N; i++) {
    cin >> L[i];
  }

  if(L[N - 1] != N) {
    cout << "No" << endl;
    return (0);
  }

  UnionFind uf(N);
  set< pair< int, int > > notsame_group;

  for(int i = 0; i < N - 1; i++) {
    for(int j = L[i] - 1; j >= 0; j--) {
      if(!uf.unite(j, N - i + j - 1)) break;
    }
    for(int j = 0; j < L[i]; j++) {
      if(!uf.unite(j, N - i + j - 1)) break;
    }
    if(i + 1 != L[i]) notsame_group.emplace(L[i], N - i + (L[i] - 1));
  }

  for(auto &x : notsame_group) {
    if(uf.find(x.first) == uf.find(x.second)) {
      cout << "No" << endl;
      return (0);
    }
  }
  cout << "Yes" << endl;

}

天使は嘘解法を書かないっ
— タプリス(競プロ) (@ei13333) 2018年2月24日

おしまい。
退出しようとしたら

私は熟女好きです
— 寝ました (@ei1333) 2018年2月24日

懇親会
寿司があるね

#みんぷろ pic.twitter.com/9KUtU8uOce
— タプリス(競プロ) (@ei13333) 2018年2月24日

らてさんとコミュニケーションをしないをする
たのしかった

ei1333の日記

ぺこい

みんなのプロコン2018 決勝参加記