ぬるぬるの競プロ日記

コードをぬるぬる書きたいです。

AtCoder Beginner Contest 127 D - Integer Cards

考えたこと:

・愚直解として以下のようなものがある。

 

vectorを1つ用意する。(初めにAi(i=1~N)を入れておく。)

 

各jに対して、vectorにBj枚、Cjを入れる。

 

vectorをsortする。

 

大きい方からN枚とる。

 

このN枚は明らかに最大値をとり、このようなN枚は明らかに構成できる。

 

・問題点

最大でpush_backをB_MAX*M=10^10回することになる。

間に合わない。

 

解決策

バケットソートをmapですることにする。

・普通の配列ですると、MLEする。

 

実装

#include <bits/stdc++.h>
using namespace std;
#define int long long

signed main() {
  int N, M;
  cin >> N >> M;
  map<int, int> mp;
  for (int i = 0; i < N; i++) {
    int a;
    cin >> a;
    mp[-a]++;
  }

  for (int i = 0; i < M; i++) {
    int b, c;
    cin >> b >> c;
    mp[-c] += b;
  }

  int ans = 0, cont = 0;
  for (auto x : mp) {

    if (cont + x.second >= N) {
      ans += (N - cont) * x.first * -1;
      break;
    }

    ans += x.second * x.first * -1;
    cont += x.second;
  }

  cout << ans << endl;
  return 0;
}

 

注意点:

カードの整数値にー1を掛けて大きい方から取り出しています。

(mapで範囲forをすると小さい方から取り出されるため。)

 

感想:

少し雑な解説になってしまいました。すみません。

感想としては、もう少し早く解けたかなと言う感じです。

 

 

 

AtCoder Beginner Contest 127 F - Absolute Minima

コンテスト中はEに時間を全て使ってしまいました。

自分の理解した範囲で解説していくので、間違いなどありましたら指摘して頂ければ

嬉しいです。

 

考えたこと

・bは本質ではない!順番に足していけばよい!

 

・絶対値の和の関数の最小値を取る座標は、傾きの変わる点の中央値!(典型)

 

・以下、aの中央値を求めることを主に考える。

 

・中央値を効率的に求めるアルゴリズムは知りませんが、K番目を求めるアルゴリズムは知っている!

 

 

参考:けんちょん様

k 番目の値を高速に取り出せるデータ構造のまとめ - BIT上二分探索や平衡二分探索木など

https://qiita.com/drken/items/1b7e6e459c24a83bb7fd

 

 

 

・しかし、今回の場合はK番目のKの値が変化していく。(K=N/2番目)

 

なので、上の記事に載っているpriority_queueを二つ使う方法はだめ?

 

(->解答ではpriority_queueで解いています。)

 

・となると、上の記事に載っているBITを使った解法でないと無理そう?

 

ー>実装力がないため、実装出来ず・・・

 

解答を見た。

 

priority_queueを二つ(ql,qrとする)使う方法で解けるらしい。

 

小さい方半分をql、大きい方半分をqrに管理させる。

 

真ん中(N/2番目)から自由に値を取り出したいので、qr

最小値が取り出せるようにする。(priority_queue<int,vector<int>,greater<int>>を使う)

 

qlは最大値を取り出す通常のpriority_queueを使う。

f:id:Null_Null:20190526115821j:plain

 

こうすることで、中央値の値(N/2番目)はqlの最大値ql.top()として自由に取り出せるようになった。

 

editorialではaを2つ追加することで実装を楽にしているそうだが、私はかえって混乱してしまったので素直な1つずつ追加する実装を以下に示す。

 

注意点:

・aの個数が奇数個のとき、中央値がqlの側に来るように(qlから答えの座標を取り出したいため)、qlはqrよりも1つ大きいかあるいは等しい状態に保つようにする。

 

・sumaは絶対値部分の答えの和を、sumbはbの和を表すことにする。

 

ー>sumaには追加クエリ毎に、追加前の絶対値の和の最小値と追加後の絶対値の和の最小値の差分を足している。

 

ー>aが前回の最小値区間内に含まれる場合、追加後の最小値の座標も最小値区間に含まれるため、変化するのは0。(bの変化分はある)

 

f:id:Null_Null:20190526122249j:plain

 

ー>aが区間外の場合、追加後の最小値の座標は、追加前の最小値の区間の端点のうちaに近い方となる。よって変化するのはbと、最小値の座標の変化分となる。

 

f:id:Null_Null:20190526122219j:plain

 

実装

#include <bits/stdc++.h>
using namespace std;
#define int long long

const int INF = 1e18;

signed main() {
  int Q;
  cin >> Q;

  int suma = 0, sumb = 0;
  priority_queue<int> ql;
  priority_queue<int, vector<int>, greater<int>> qr;

  ql.push(-INF);
  qr.push(INF);

//while(Q--)を使うと変数iが使えるのでお勧め(余談)
  while (Q--) {
    int q;
    cin >> q;

    if (q == 1) {
      int a, b;
      cin >> a >> b;
      sumb += b;
      
      if (ql.size() == qr.size()) {
          //前回の最小値の区間内にある時、増加分は0
        if (ql.top() <= a && a <= qr.top()) {
          suma += 0;
        } else {
          //aが前の最小値の区間の範囲外にあるとき。
          //このとき、次の最小値は区間の端のうち、追加する点に近い方になる。
          //よって増加分は近い方の端点との距離。
          suma += min(abs(ql.top() - a), abs(a - qr.top()));
        }
      } else {
        suma += abs(ql.top() - a);
      }
      
      if (qr.top() <= a) {
        qr.push(a);
      } else {
        ql.push(a);
      }

      //qrと比べて、qlが1大きいか等しい状態に保つ。
      if (qr.size() > ql.size()) {
        ql.push(qr.top());
        qr.pop();
        //qlがqrより2大きいとき
      } else if (ql.size() > qr.size() + 1) {
        qr.push(ql.top());
        ql.pop();
      }

    } else if (q == 2) {
      cout << ql.top() << " " << suma + sumb << endl;
    }
  }

  return 0;
}

 

感想:

もう少し実装力を付けたいです。

 

AtCoder Beginner Contest 126 F - XOR Matching

考えたこと:

・値の等しい任意のai,ajに対して題意の条件が成立するので、構築できるならば対称性がありそう。

 

・もしかして、K==0の場合にしか構築できないのでは??

ー>場合分けして提出。

ー>そんなことなかった。

 

・紙上で実験をし続けていると、どうやら

 

ABC・・・X K X・・・CBA K

というパターンが条件を満たしそうであるということがわかった。

 

満たさなければいけない条件は

X・・・CBA のxorがKと等しくなる。ことである。

 

実装:

#include <bits/stdc++.h>
using namespace std;
#define int long long

int M, K;

signed main() {
  cin >> M >> K;
  if (M == 0) {
    if (K == 0) {
      cout << 0 << " " << 0 << endl;
    } else {
      cout << -1 << endl;
    }
    return 0;
  }

  if ((1 << M) <= K) {
    cout << -1 << endl;
    return 0;
  }

  if (K == 0) {
    for (int i = 0; i < (1 << (M + 1)); i++) {
      if (i != 0) cout << " ";
      cout << i / 2;
    }
    cout << endl;
    return 0;
  }

  int tmp = 0;
  for (int i = 0; i < (1 << M); i++) {
    if (i != K) tmp ^= i;
  }

  if (tmp != K) {
    cout << -1 << endl;
    return 0;
  }

  vector<int> v;
  for (int i = 0; i < (1 << M); i++) {
    if (i != K) v.push_back(i);
  }
  vector<int> rev = v;
  reverse(rev.begin(), rev.end());
  v.push_back(K);
  rev.push_back(K);

  for (auto x : v) cout << x << " ";
  for (int i = 0; i < rev.size(); i++) {
    if (i != 0) cout << " ";
    cout << rev[i];
  }
  cout << endl;

  return 0;
}

 

感想

構築が苦手だったので解けて良かったです。

(少し好きになりました。)

 

全体としては全完できました。

高揚感がありました。楽しかったです。

AtCoder Beginner Contest 126 E - 1 or 2

考えたこと:

・Zは定数なので、ほとんど関係ない。(MOD 2をとって終わり)

 

・Ax1+Ay1のMOD 2が解っているとき、、片方の値が判明すればもう片方も判明する。(0か1しかないので)

 

・AがわかればBもわかるという関係を連結と呼ぶならば、2つの場合のみならず、3つ4つの連結な関係も考えられるのではないか?

 

ー>実際、考えられる。

 

この連結な関係はグラフで表すことが出来そう。

 

ー>UnionFindTreeで表せばもっと簡潔に表せそう。

 

実装:

 

#include <bits/stdc++.h>
using namespace std;
#define int long long

struct UnionFind {
  vector<int> data;

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

  bool same(int x, int y) {
    return find(x) == find(y);
  }

  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 N, M;
UnionFind uf(101010);

signed main() {
  cin >> N >> M;
  for (int i = 0; i < M; i++) {
    int x, y, z;
    cin >> x >> y >> z;
    x--, y--;
    uf.unite(x, y);
  }

  vector<int> v;
  for (int i = 0; i < N; i++) {
    v.push_back(uf.find(i));
  }

  sort(v.begin(), v.end());
  v.erase(unique(v.begin(), v.end()), v.end());

  cout << v.size() << endl;

  return 0;
}

 

細かい実装の部分を付け足すと、具体的な答えはUF上の連結部分の個数、すなわちUFの頂点の親の個数となる。

 

よって、vectorに親を入れていき最後にuniqueで重複部分を除いてvectorのサイズを答えている。

AtCoder Beginner Contest 126 D - Even Relation

考えたこと:

・二点間についてすべて考えてしまうとO(N^2)で間に合わなくなる。

・距離の偶奇しか問われていないので、距離の大きさは本質ではない。

・こういう問題は根付き木にして、根を起点にして考えるとよいことが多い。

 

図を書いてじっと眺めてみると・・・

f:id:Null_Null:20190522131757p:plain

赤ー>青の距離は、赤ー>Y->X->Y->青の距離からX->Yを二回引いた距離

(上図黄色線)に等しい。

 

ここで、距離の偶奇しか本質でないことを思い出すと、往復しているX->Yの距離は必ず偶数になるため考えなくてもよい。(逆に言うと付け足して考えても良い)

 

よって、二点間の距離の偶奇は、二点間への根からの距離の和の偶奇に等しいことが示せた。

 

根からの各頂点の距離はDFSすることでO(N+M)で求められる。

 

よって、

根からの距離が偶数の場合、0グループに

根からの距離が奇数の場合、1グループに

というふうに塗ってあげれば、題意を満たすことが出来る。

 

実装:

 

#include <bits/stdc++.h>
using namespace std;
#define int long long 

struct edge {
  int to, cost;
};
 
int N;
vector<edge> G[101010];
int d[101010];
 
void dfs(int n, int pre) {
  for (auto x : G[n]) {
    if (x.to != pre) {
      d[x.to] = d[n] + x.cost;
      dfs(x.to, n);
    }
  }
}
 
signed main() {
  cin >> N;
  for (int i = 0; i < N - 1; i++) {
    int u, v, w;
    cin >> u >> v >> w;
    u--, v--;
    G[u].push_back({v, w});
    G[v].push_back({u, w});
  }
 
  dfs(0, -1);
 
  for (int i = 0; i < N; i++) {
    if (d[i] % 2 == 0) {
      cout << 0 << endl;
    } else {
      cout << 1 << endl;
    }
  }
 
  return 0;
}

 

グラフが木で、二往復することで辺上のなんらかを無視できるような問題では、根を考えることで上記のような処理が出来ることがよくあるように思う。

 

ABC125

C - GCD on Blackboard

考えたこと:

・双方向から累積gcd

・すべて素因数分解してごちゃごちゃ

 

(バグったのでDに行きました。AC出来ませんでした・・・)

 

解説:

この問題を言い換えると、「N個の要素からN-1個選んだ時、GCDが最大になるようなものの値を求めよ。」です。

 

なので、N-1個のGCDを求めることを考えます。

普通にやるとN^2なので間に合いません。

 

双方向から累積和の要領でGCDを取っていきます。

GCDには逆元がないので、普通に累積和を取っても引くことが出来ません。

 

しかし、この問題では1つだけ除いたものを求めればいいので、添え字0から除くものの1つ手前までのGCDと、添え字N-1から除くものの1つ前までのGCDが解ればそれら二つのGCDを取ることで答えは求まります。

 

このほかにも、セグ木を貼ればO(N log N)で計算できたはずです。

私にとってこの問題は解かなければいけなかった問題です・・・

 

実装です・・・

#include <bits/stdc++.h>
using namespace std;

int main() {
  int N;
  cin >> N;
  vector<int> a(N + 2), l(N + 2, 0), r(N + 2, 0);
  for (int i = 1; i <= N; i++) cin >> a[i];
 
  for (int i = 1; i <= N; i++) l[i] = gcd(l[i - 1], a[i]);
  for (int i = N; i >= 0; i--) r[i] = gcd(r[i + 1], a[i]);
 
  int ans = 1;
  for (int i = 1; i <= N; i++) ans = max(ans, gcd(l[i - 1], r[i + 1]));
 
  cout << ans << endl;
  return 0;
}

 

D - Flipping Signs

 

考えたこと:

・上手くやれば、数個を除いてそれ以外を最適化できるのではないか?

・DP

 

1つ目も考えましたが、結局DPに走りました。

DPには自信があったからです。(DPまとめこんを最近やったので)

今はもう。

 

解説:

dp[i][k]:=今i番目を見ていて、i番目をひっくり返すか否か。(k=0ならひっくり返さない、k=1ならひっくり返す。) と定義します。

 

それぞれの数字の符号は、前に戻ってひっくりかえすことはないので順に考えることが出来ます。

 

実装:

#include <bits/stdc++.h>
using namespace std;

signed main() {
  int N;
  cin >> N;
  vector<int> a(N);
  for (int i = 0; i < N; i++) cin >> a[i];

  static int dp[101010][2];
  dp[0][0] = 0;
  dp[0][1] = -INF;

  for (int i = 0; i < N; i++) {
    dp[i + 1][0] = max(dp[i][0] + a[i], dp[i][1] - a[i]);
    dp[i + 1][1] = max(dp[i][0] - a[i], dp[i][1] + a[i]);
  }

  cout << dp[N][0] << endl;
  return 0;
}

本番ではメモ化再帰でごちゃごちゃしていたのですが、適当に書いたので上手くいきませんでした。(←最悪なやつです。)

 

この問題は冷静に見ても、今の私には解けなかったと思います。(DPで解く場合。)

もっと遷移を見て、丁寧にDPをするべきでした。

勉強になりました。

 

感想:

今回のブログは感情が入り乱れている状態で書いたので、解説ブログではなく日記のようになってしまいました、すみません。

 

結果は二完でした・・・

 

勝ち筋としては、Cをしっかり通してからDを丁寧に解いていれば・・・という感じです。(しかし、終わったことです。)

 

調子の悪いときに如何に精進するかが肝だと思うので、頑張りたいと思います!

 

 

 

 

 

 

 

 

 

ABC124 D - Handstand

考えたこと

・010を[1,3]で反転させると101、[2,2]を反転させて 111 とできるが、

これは左の0と右の0を別々に反転させることと同じっぽい。

(1を跨いで反転させるのは無意味そう)

 

・連続する0を反転することだけを考えればいいのではないか?

 

・(連続する0の区間)からK個の区間を反転させると考えると、離れた区間同士を反転させても、最大にはならなさそう。

 

・隣同士の区間を反転させていく「貪欲法」が成立する?

 

・一番左の0の区間を選べば、そこからK個のゼロの区間は一意に定まる。

(そこから順番にK個右に取っていけばいい)

 

・前処理をすれば右端はlower_boundで求まりそう!解けた!

 

結果

・実装でバグが大発生。

・1時間30分椅子を温めた

 

いろいろ見た結果

 

尺取り法が一番綺麗そう。

 

・それはそうで、よく考えると

「連続した0の区間の個数は、区間に対して単調増加する」

ので尺取り法がつかえる。

 

 

(「にぶたん大好きマン」なのでついつい二分探索をしてしまう。悪癖である。)

 

 

重要ポイント

・右端rが1から0に移り変わるとき、連続した0の区間の個数contは1増える。

・左端lが0から1に移り変わるとき、連続した0の区間の個数contは1減る。

・一番左の部分が0から始まる場合、cont=1で始めないといけない。

(理由:contが増えるのは左端が1から0に増えるときだが、一番左より左には文字はない。)

 

実装

#include <bits/stdc++.h>
using namespace std;

int main() {
  int N, K;
  cin >> N >> K;
  string s;
  cin >> s;

  int ans = 0, r = 0, cont = 0;

  if (s[0] == '0') cont++;

  for (int l = 0; l < N; l++) {

    while (cont <= K && r < N) {
      if (r + 1 < N && s[r] == '1' && s[r + 1] == '0') cont++;
      r++;
    }

    ans = max(ans, r - l);

    if (l + 1 < N && s[l] == '0' && s[l + 1] == '1') cont--;
  }

  cout << ans << endl;
  return 0;
}

 

我ながら美しいコードである。(自分で言うな)

 

感想:

結果としては3完だった。

悔しい。悔しい。悔しい。

もっと強くなりたい。

精進します。