2020-02-20

ABC080D

問題

解法

解説の解法に感動させられたが、自分なりの解法を残しておく。

まず、チャンネル毎に開始時間の早い番組から順に見ていき、同じチャンネルの連続した番組を一つの番組としてまとめる。
この操作を行う事で、全ての番組において、同じ録画機を使うには前の番組の終了時間より開始時間の方が真に遅くなければならなくなる。

あとは、開始時間が早い番組から、使用可能になる時間が一番早い録画機で録画をするようにすれば良い。
もし、一番早い録画機でも録画できない場合は、録画機を増やすことになる。
この操作は、各録画機の使用可能になる時間を優先度付きキューで管理することで、簡単に実装することができる。

計算量は、各操作共に $O(NlogN)$ であるため、問題ない。

コード

#include <iostream>
#include <queue>
using namespace std;
typedef pair<int, int> P;

int main() {
  int N, C; cin >> N >> C;
  vector<priority_queue<P, vector<P>, greater<P>>> p(C);
  for (int i = 0; i < N; i++) {
    int s, t, c; cin >> s >> t >> c;
    p[c-1].push(P(s, t));
  }

  auto comp = [](P a, P b) { return a.first > b.first; };
  priority_queue<P, vector<P>, decltype(comp)> que(comp);
  for (int i = 0; i < C; i++) {
    if (p[i].empty()) continue;
    P time = p[i].top(); p[i].pop();
    while (!p[i].empty()) {
      if (time.second == p[i].top().first) {
        time.second = p[i].top().second; p[i].pop();
      }
      else {
        que.push(time);
        time = p[i].top(); p[i].pop();
      }
    }
    que.push(time);
  }

  priority_queue<int, vector<int>, greater<int>> rec;
  rec.push(que.top().second); que.pop();
  while (!que.empty()) {
    if (rec.top() < que.top().first) rec.pop();
    rec.push(que.top().second); que.pop();
  }
  cout << rec.size() << endl;
}

感想

問題を見たときに、区間スケジューリング問題だと思い込んでしまったため、苦戦した。思い込みは良くない。

楽しくなって優先度付きキューを多用してしまったが、素直にソートした方がわかりやすい気がする。楽しいから止めるつもりはない。

2020-02-19

ABC079D

問題

D - Wall

$i$ から $j$ に書き換えるには魔力 $c_{i,j}(0 \leq i,j \leq 9)$ が必要であるとき、 $A_{i,j}$ を全て1に変えるのに必要な魔力の最小量を求めよ。

ただし、 $A_{i,j} = -1$ の場合は変えなくて良い。

解法

制約上、ワーシャルフロイド法で解けそうだったが、ダイクストラ法の経験が乏しかったため、ダイクストラ法で解くことにした。

考え方としては、数字を頂点に、書き換えるという動作を辺に、それに必要な魔力を辺の重みにすることで、各頂点から1への最短経路長を求めれば良いことになる。

これをダイクストラ法で解くとすると、1への距離を1以外の各頂点においてはINF、頂点1においては0で初期化し、1への距離が小さい順に各頂点において他の頂点の1への距離を更新していく。

あとは、各壁において必要な魔力の最小量を求めれば良い。

計算量は、ダイクストラ法においてはダイクストラ法 - Wikipedia によると $O(E+VlogV)$ らしい（良くわかっていない）

もしそうであれば、今回は完全グラフなので、 $E = V^{2}$ であり、計算量が $O(V^{2})$ になるので、priority_queueを使わない方法( $O(V^{2})$ )の方が良かったのだろう。

ただ、今回の制約では各壁を探索する $O(HW)$ の方が大きくなる場合がほとんどなので、気にする必要は無い。

コード

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
typedef vector<int> VI;
typedef vector<VI> VVI;
#define INF 1000

int main() {
  int h, w; cin >> h >> w;
  VVI c(10, VI(10));
  for (int i = 0; i < 10; i++) {
    for (int j = 0; j < 10; j++) cin >> c[i][j];
  }

  VI d(10, INF);
  d[1] = 0;
  auto comp = [&](int a, int b) { return d[a] > d[b]; };
  priority_queue<int, VI, decltype(comp)> que(comp);
  que.push(1);
  while (!que.empty()) {
    int v = que.top(); que.pop();
    for (int u = 0; u < 10; u++) {
      if (d[u] > d[v] + c[u][v]) {
        d[u] = d[v] + c[u][v];
        que.push(u);
      }
    }
  }

  int ans = 0;
  for (int i = 0; i < h; i++) {
    for (int j = 0; j < w; j++) {
      int a; cin >> a;
      if (a >= 0) ans += d[a];
    }
  }
  cout << ans << endl;
}

感想

計算量って難しい。

2020-02-18

ABC077C

問題

C - Snuke Festival

$A_i,\ B_i,\ C_i(1 \leq i \leq N)$ において、 $A_i < B_i < C_i$ となる組み合わせは何通りあるか。]

解法

解説では二分探索で解いていたが、頭に尺取り法しか無かったため、尺取り法で解いた。

まず、単調減少である必要があるため、降順にソートする。

次に、 $A_i,\ B_i$ が大きい順に $A_i < B_i$ となる組み合わせを求める。

この時、 $B_i < C_i$ となる $C_i$ の個数を調べるのだが、 $A_i >= A_j$ の全ての場合において $A_j < B_i$ となるので、 $A_i >= A_j$ の個数を $C_i$ の個数に掛ければ良い。

$A_i < B_i$ となる組み合わせや、 $B_i < C_i$ となる $C_i$ の個数は、大きい順に見ていくことから、一つ前でどこまで見たかを覚えておけば、合計 $O(N)$ で求めることができる。

計算量は、尺取り法が $O(N)$ だが、ソートで $O(NlogN)$ 要するので、全体で $O(NlogN)$ である。]

コード

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
  int n; cin >> n;
  vector<int> a(n), b(n), c(n);
  for (int i = 0; i < n; i++) cin >> a[i];
  for (int i = 0; i < n; i++) cin >> b[i];
  for (int i = 0; i < n; i++) cin >> c[i];
  sort(a.begin(), a.end(), greater<int>());
  sort(b.begin(), b.end(), greater<int>());
  sort(c.begin(), c.end(), greater<int>());

  long long ans = 0;
  int i = 0, j = 0, k = 0;
  while (i < n) {
    while (j < n && a[i] < b[j]) {
      while (k < n && b[j] < c[k]) k++;
      ans += 1LL * (n - i) * k;
      j++;
    }
    i++;
  }
  cout << ans << endl;
}

感想

Bを軸とする発想が浮かばなかったので、二分探索を思いつくことができなかった。

尺取り法を考えていくうちにBを軸とすれば良いことはわかったが、解く時間が長くなってしまったため、考察力を磨く必要がある。

また、最近解いた問題の解法に引きずられる傾向があるので、頭をリセットして取り組めるようになりたいところ。

2020-02-17

ABC155E

問題

E - Payment

紙幣の価値が $10^{i}$ である時、価値 $N$ のたこ焼き器を買う場合の、自分と店員の使う紙幣の枚数の合計の最小値を求めよ。

解法

下位桁から順に見ていく。

4以下の場合

自分がその枚数を使う。

6以上の場合

一つ上の桁を+1し、店員が10-xの枚数を使う。

5の場合

一つ上の桁が4以下の場合

自分が5枚使う。

一つ上の桁が5以上の場合、

一つ上の桁を+1し、店員が5枚使う。

一つ上の桁が6以上の場合、元々繰り上がりは確定しているので、一つ上の桁で店員の使う枚数を1減らすことができる。

一つ上の桁が5の場合、二つ上の桁が4以下だった場合に使う枚数が1増えてしまうが、一つ上の桁で使う枚数を1減らしているため問題ない。

コード

#include <iostream>
#include <vector>
#include <string>
using namespace std;

int main() {
  string s; cin >> s;
  vector<int> n(s.size()+1);
  n[0] = 0;
  for (int i = 0; i < s.size(); i++) n[i+1] = s[i] - '0';
  long long ans = 0;
  for (int i = n.size()-1; i > 0; i--) {
    if (n[i] == 5 && n[i-1] < 5) {
      ans += 5;
    }
    else if (n[i] < 5) {
      ans += n[i];
    }
    else {
      ans += 10 - n[i];
      n[i-1]++;
    }
  }
  cout << ans + n[0] << endl;
}

感想

コンテスト中は何となくで通してしまったので反省。

ただ、ゲームだから良いよね…。

2020-02-17

ABC155D

問題

D - Pairs

$N$ 個の整数 $A_i$ における全てのペアの積を求め、それらを小さい順に並び替えたとき、 $K$ 番目にくる数を求めよ。

解法

「積が $ans$ 以下であるペアの個数が $K$ 個」となる $ans$ の最小値を、二分探索で求める。

最左値と右辺値は入力された値から求めても良いが、正負によって場合分けしなければいけないため、 $A_i$ の範囲にしておくのが楽。

計算量は、 $O(log_{2}(2*10^{9}))$ 。

積が $ans$ 以下であるペアの個数は、積が負・正・0の場合に分けて求める。

まず、 $A_{i}$ を負・正・0に分ける。

積が負の場合、正負のどちらかのリストを絶対値が大きい方から、もう一方のリストを絶対値が小さいほうから値を取り出すことで、尺取り法をすることができる。

積が正の場合、正負のリスト共に、絶対値が大きい方からと小さい方から値を取り出すことで、尺取り法をすることができる。これは、ペアの片方を固定したとき、もう片方を固定した値よりも小さい値から選べば良いという考えに基づいている。

積が0の場合、積が負になる個数と積が0になる個数を足せば良い。

計算量は積が0の場合を除き、 $O(N)$

コード

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
#define MAXA 1000000000LL

int main() {
  ll n, k; cin >> n >> k;
  vector<ll> vm, vp;
  ll zero = 0;
  for (int i = 0; i < n; i++) {
    ll a; cin >> a;
    if (a < 0)
      vm.push_back(a);
    else if (a > 0)
      vp.push_back(a);
    else
      zero++;
  }
  sort(vm.begin(), vm.end());
  sort(vp.begin(), vp.end(), greater<ll>());

  auto f1 = [](vector<ll>& v1, vector<ll>& v2, ll x) {
    ll res = 0;
    int i = 0, j = v2.size()-1;
    while (i < v1.size() && j >= 0) {
      if (v1[i] * v2[j] <= x) {
        res += j + 1;
        i++;
      }
      else j--;
    }
    return res;
  };

  auto f2 = [](vector<ll>& v, ll x) {
    ll res = 0;
    int i = 0, j = v.size()-1;
    while (i < j) {
      if (v[i] * v[j] > x) {
        res += j - i;
        i++;
      }
      else j--;
    }
    return res;
  };

  ll way = n * (n-1) / 2;
  ll r = MAXA * MAXA, l = -r;
  while (r - l > 1) {
    ll c = (l + r) / 2;

    ll res;
    if (c < 0)
      res = f1(vm, vp, c);
    else if (c > 0)
      res = way - (f2(vm, c) + f2(vp, c));
    else {
      res = vm.size() * vp.size();
      res += (n-zero) * zero + zero * (zero-1) / 2;
    }

    if (res < k)
      l = c;
    else
      r = c;
  }
  cout << r << endl;
}

感想

二分探索と尺取り法だけでここまで考察が難しくなるのには驚かされた。

ただ、それだけに基本が詰まった面白い問題だったように思う。

（尺取り法の解説を書くのは難しい…）

2020-02-16

ABC075D

問題

D - Axis-Parallel Rectangle

2次元座標上のN個の座標のうち、K個以上を辺または内部に含む、それぞれの辺がX軸とY軸に平行な長方形の面積の最小値を求めよ。

解法

制約より、各座標のX軸・Y軸の値は異なるので、各座標をX軸の値によってソートすると、求める長方形のX軸の長さは、 $x_j - x_i (x_i < x_j,\ i+K-1 \leq r)$ のいずれかである。

あとは、これらの範囲において、Y軸の長さが最小になるように5個選ぶことを考えれば良い。これは、範囲内の座標をY軸の値によってソートすることで簡単に求められる。

計算量は $O(N^{3}logN)$ となり、 $2 \leq N \leq 50$ なので十分間に合う。

コード

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;

int main() {
  int N, K;
  cin >> N >> K;
  vector<P> v(N);
  for (int i = 0; i < N; i++) {
    ll x, y;
    cin >> x >> y;
    v[i] = P(x, y);
  }
  sort(v.begin(), v.end(), [](P a, P b) {
    return a.first < b.first;
  });

  ll ans = -1;
  for (int l = 0; l < N-K+1; l++) {
    for (int r = l+K-1; r < N; r++) {
      vector<P> v2(r-l+1);
      copy(v.begin()+l, v.begin()+r+1, v2.begin());
      sort(v2.begin(), v2.end(), [](P a, P b) {
        return a.second < b.second;
      });
      ll dx = v[r].first - v[l].first;
      for (int i = 0; i < v2.size()-K+1; i++) {
        ll dy = v2[K-1+i].second - v2[i].second;
        ll area = dx * dy;
        ans = ans < 0 ? area : min(ans, area);
      }
    }
  }
  cout << ans << endl;
}

一言

Y軸の値を小さいほうから5個選んでしまっていたため、WAを出してしまった。
（結構悩んだ）

2020-02-15

yukicoder No.990 N×Mマス計算（Kの倍数）

No.990 N×Mマス計算（Kの倍数） - yukicoder

$op$ が $+$ か $*$ のどちらかである時、 $C_{i,j} = A_i\ op\ B_j$ が $K$ の倍数であるような $(i, j)$ の組合せは何通りあるかという問題です。

WAを抜け出せなかったので解説に沿って解いたのですが、解いていて楽しかったので記事を書くことにしました。

（全面的にC++における表現を使用しています）

解法

op == '+'の場合

$A_i+B_j$ が $K$ の倍数となるのは、 $A_i,\ B_j$ を $K$ で割った余りの和が $K$ の倍数である時。

そのため、予め $B_j\ \%\ K$ の値ごとにカウントしておくことで、各 $A_i$ において $(K-A_i\ \%\ K)\ \%\ K$ の値をカウントしておいた中から探すだけで済むようになる。

注意

$K-A_i\ \%\ K$ とすると、 $A_i\ \%\ K==0$ の時、 $B_j\ \%K==K$ の値を探してしまう。

（C++では） $-A_i\ \%\ K$ とすると、負の値が出力されてしまう。

カウンターは $1 \leq K \leq 10^9$ 、 $1 \leq N,M \leq 10^5$ であることから、配列ではなくmapを使用する。

コード

    map<int, int> dict;
    for (int i = 0; i < m; i++) {
      int b; cin >> b;
      dict[b % k]++;
    }
    for (int i = 0; i < n; i++) {
      int a; cin >> a;
      ans += dict[(k - a % k) % k];
    }

op == '*'の場合

$A_i*B_j$ が $K$ の倍数となるのは、 $A_i,\ B_j$ と $K$ の最大公約数の積が $K$ の倍数である時。

そのため、予め $B_j$ と $K$ の最大公約数の値ごとにカウントしておくことで、各 $A_i$ において全ての $B_j$ との最大公約数の積が $K$ の倍数である時、それぞれの個数の積を計算するだけで済む。

注意

$K$ の約数の個数は、二重ループで間に合う範囲内である。

カウンターは $1 \leq K \leq 10^9$ であることから、配列ではなくmapを使用する。

最大公約数の積と個数の積は整数オーバーフローする。

コード

    /* typedef pair<int, int> P; */

    map<int, int> dict1;
    map<int, int> dict2;
    for (int i = 0; i < m; i++) {
      int b; cin >> b;
      dict1[gcd(b, k)]++;
    }
    for (int i = 0; i < n; i++) {
      int a; cin >> a;
      dict2[gcd(a, k)]++;
    }
    for (P p1 : dict1) {
      for (P p2 : dict2) {
        if (1LL * p1.first * p2.first % k == 0) {
          ans += 1LL * p1.second * p2.second;
        }
      }
    }

一言

記事を書くのが面倒になっているせいか、説明が適当になってしまっているので、余裕ができるまでしばらく休止した方が良いのかもしれません。