Codeforces Round #420 (Div. 2)

悪魔的なコンテストだった.

oooooo 28th.

なんかアレな回だけど全完できたのはじめてかも.

A. Okabe and Future Gadget Laboratory

問題概要

${n \times n(1 \le n \le 50)}$ の二次元グリッドがあって, ${i}$ 行 ${j}$ 列目には ${a_{i, j}(1 \le a_{i, j} \le 10^5)}$ が書かれている.

${1 \le x, y \le n}$ かつ ${a_{x, y} \ne 1}$ を満たす任意の ${x, y}$ について ${a_{x, y} = a_{x, s} + a_{t, y}}$ となる ${s, t}$ が存在するか判定せよ.

解法

その答えは問題文に書かれている.

問題文に書かれていることをそのまま実装して提出するんだけど, ページが重くて問題文を読めないし提出できない.

ソース

#include<bits/stdc++.h>

using namespace std;


int main()
{
  int N;
  int mat[50][50];

  cin >> N;
  for(int i = 0; i < N; i++) {
    for(int j = 0; j < N; j++) {
      cin >> mat[i][j];
    }
  }

  for(int i = 0; i < N; i++) {
    for(int j = 0; j < N; j++) {
      if(mat[i][j] == 1) continue;
      bool flag = false;
      for(int k = 0; k < N; k++) {
        for(int l = 0; l < N; l++) {
          if(mat[i][j] == mat[i][k] + mat[l][j]) {
            flag = true;
          }
        }
      }
      if(!flag) {
        cout << "No" << endl;
        return(0);
      }
    }
  }

  cout << "Yes" << endl;
}

B. Okabe and Banana Trees

codeforces.com

問題概要

${2}$ 次元平面があって, ${0 \le x, y}$ を満たす任意の整数座標 ${(x, y)}$ には ${x + y}$ 個のバナナがある.

平面上に直線 $y = - \frac {x} {m} + b (1 \le m \le 1000, 1 \le b \le 10000)$ を引く.

直線上のある点を選び, それを左上の点とする長方形内のバナナを全て得ることが出来る.

得られるバナナの個数の最大値を求めよ.

解法

選ぶ点の候補は ${y}$ 座標が ${0, 1, \dots, b}$ の直線上の点なので ${O(b)}$ をする.

${y}$ 座標が ${i}$ とすると ${x}$ 座標は直線の式を式変形して ${x = m(b - i)}$ ということがわかる.

この座標が分かればあとははい.

ソース

#include<bits/stdc++.h>

using namespace std;

typedef long long int64;

int main()
{
  int B, M;
  cin >> M >> B;
  int64 ret = 0;

  auto sum = [&](int x)
  {
    return (1LL * x * (x + 1) / 2);
  };

  for(int i = 0; i <= B; i++) {
    int j = M * B - M * i;
    ret = max(ret, sum(i) * (j + 1) + sum(j) * (i + 1));
  }

  cout << ret << endl;
}

C. Okabe and Boxes

codeforces.com

問題概要

${1}$ から ${n(1 \le n \le 3 \times 10^5)}$ の値をスタックに追加, 削除する ${2n}$ 個のクエリが順に与えられる.

あるタイミングでスタック内のデータの順番を並び替えることが出来る.

${1}$ から ${n}$ の値が順にスタックから取り出されるようにするとき, 並び替える回数の最小値を求めよ.

解法

貪欲が成り立ってくれないと解けないので困る.

実際にスタックを用いてシミュレーションする. スタックから取り出すときに正しい順番を満たさなければ並び替える.

スタック内のどこまで並び替えたかを持っておくとはいができるのでえい.

${O(n)}$ .

ソース

#include<bits/stdc++.h>

using namespace std;

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

  int N;
  cin >> N;

  int update[300000];
  bool del[300000] = {};
  int reordered = 0;
  int ret = 0;

  stack< int > st;
  int now = 0;

  for(int i = 0; i < 2 * N; i++) {
    string q;
    cin >> q;
    if(q == "add") {
      int k;
      cin >> k;
      --k;
      update[k] = i;
      st.push(k);
    } else {
      while(!st.empty() && del[st.top()]) st.pop();
      del[now] = true;
      if(st.top() != now && update[st.top()] > reordered) {
        reordered = i;
        ++ret;
      }
      ++now;
    }
  }

  cout << ret << endl;
}

D. Okabe and City

codeforces.com

問題概要

${n \times m(2 \le n, m \le 10^4)}$ のグリッドがあって, ${(1, 1)}$ を含む ${k(2 \le k \le 10^4)}$ 個のセルは点灯している.

初期位置 ${(1, 1)}$ から点灯している隣接するマスを通って ${(n, m)}$ に移動する.

また最初から点灯しているセルでコスト ${1}$ を払うと, 自分の位置から絶対値が ${1}$ 以下の行か列を一様に点灯することができる.

${(n, m)}$ に移動できるとき, コストの最小値を求めよ.

解法

${O(n + m + k)}$ の 0-1BFS.

状態を整理すると ${3}$ 種類の状態で表せることがわかる.

最初から点灯しているセル ${(x,y)}$ にいる.
一時的なライトをつけて ${x}$ 行目にいる.
一時的なライトをつけて ${y}$ 列目にいる.

状態が 1. から 2. 3. に移動するときコストが ${1}$ 加算され, それ以外はそのまま.

の状態数は ${k}$ 個, 2. の状態数は ${n}$ 個, 3. の状態数は ${m}$ 個である.

辺の数を考えると線形になりそうなことがわかるので解ける.

ソース

サンプルの意味がわからないなぁって思ってたら途中でサンプルが変わってア.

なんかやってるうちに問題文の意味がわからなくなってしまって冗長になってる.

#include<bits/stdc++.h>

using namespace std;

const int vy[] = {1, 0, -1, 0};
const int vx[] = {0, 1, 0, -1};

int main()
{

  int H, W, K;
  set< int > cell1[10005], cell2[10005];

  cin >> H >> W >> K;
  for(int i = 0; i < K; i++) {
    int y, x;
    cin >> y >> x;
    --y, --x;
    cell1[y].emplace(x);
    cell2[x].emplace(y);
  }

  typedef tuple< int, int, int, int > Pi;
  deque< Pi > que;
  map< pair< int, int >, int > vv[3];

  auto update = [&](int tt, int yyy, int xxx, int cs, int add)
  {
    cs += add;
    if(!vv[tt].count({yyy, xxx}) || cs < vv[tt][{yyy, xxx}]) {
      vv[tt][{yyy, xxx}] = cs;
      if(add) que.emplace_back(cs, yyy, xxx, tt);
      else que.emplace_front(cs, yyy, xxx, tt);
    }
  };

  update(0, 0, 0, 0, 0);

  while(!que.empty()) {
    int ny, nx, cost, type;
    tie(cost, ny, nx, type) = que.front();
    que.pop_front();
    if(cost > vv[type][{ny, nx}]) continue;

    if((type == 0 && ny == H - 1 && nx == W - 1) ||
       (type == 1 && ny == H - 1) ||
       (type == 2 && nx == W - 1)) {
      cout << cost << endl;
      return (0);
    }

    if(type == 0) {
      for(int i = 0; i < 4; i++) {
        int sy = ny + vy[i], sx = nx + vx[i];
        if(sy < 0 || sx < 0 || sy >= H || sx >= W) continue;
        if(cell1[sy].count(sx)) update(0, sy, sx, cost, 0);
      }
      if(ny) {
        --ny;
        update(1, ny, -1, cost, 1);
        update(2, -1, nx, cost, 1);
        ++ny;
      }
      if(nx) {
        --nx;
        update(1, ny, -1, cost, 1);
        update(2, -1, nx, cost, 1);
        ++nx;
      }
      if(ny + 1 < H) {
        ++ny;
        update(1, ny, -1, cost, 1);
        update(2, -1, nx, cost, 1);
        --ny;
      }
      if(nx + 1 < W) {
        ++nx;
        update(1, ny, -1, cost, 1);
        update(2, -1, nx, cost, 1);
        --nx;
      }
    } else if(type == 1) {
      for(auto &s : cell1[ny]) update(0, ny, s, cost, 0);
      if(ny) for(auto &s : cell1[ny - 1]) update(0, ny - 1, s, cost, 0);
      for(auto &s : cell1[ny + 1]) update(0, ny + 1, s, cost, 0);
    } else {
      for(auto &s : cell2[nx]) update(0, s, nx, cost, 0);
      if(nx) for(auto &s : cell2[nx - 1]) update(0, s, nx - 1, cost, 0);
      for(auto &s : cell2[nx + 1]) update(0, s, nx + 1, cost, 0);
    }
  }

  cout << -1 << endl;
}

E. Okabe and El Psy Kongroo

codeforces.com

問題概要

二次元平面 ${(0, 0)}$ から ${(k, 0) (1 \le k \le 10^{18})}$ まで非負整数座標を通って移動する.

各ステップでは, 現在の位置が ${(x, y)}$ のとき ${(x + 1, y + 1), (x + 1, y), (x - 1, y)}$ に移動できる.

また ${n(1 \le n \le 100)}$ 本の条件があって x 座標が ${a_i \le x \le b_i(a_1 = 0, a_n \le k \le b_n, a_i = b_{i-1} (2 \le i \le n))}$ に位置するとき y 座標が ${0 \le y \le c_i}$ である必要がある.

歩き方の組み合わせを ${10^9 + 7}$ で割った余りで求めよ.

解法

これは解ける(解けるので). DPを行列累乗で高速化する.

${x}$ 列での各行での経路数を表した ${\boldsymbol{ S }= (s_0, s_1, \dots, s_c)^{\mathrm{T}}}$ から ${x + 1}$ 列目の経路数を表した ${\boldsymbol{ T }= (t_0, t_1, \dots, t_c)^{\mathrm{T}}}$ に遷移させることを考える.

これは行列を掛ければできる. ${\boldsymbol{ T } = \boldsymbol{ S }\boldsymbol{ A }}$ を満たすような行列 ${\boldsymbol{ A }}$ を求めたい.

${(c_i+1) \times (c_i+1)}$ の行列 ${\boldsymbol {A} = \{a_{i,j}\}}$ を考える. 積の定義より ${t_i = \sum_{j=0}^{c} {s_j a_{j,i}}}$ である. よって ${(x,j)}$ から ${(x+1,i)}$ に移動できる時 ${a_{j,i} = 1}$ , それ以外なら ${a_{j,i} = 0}$ とすればよいことがわかる.

次の次は ${\boldsymbol{ S }\boldsymbol{ A }\boldsymbol{ A } = \boldsymbol{ S } \boldsymbol{ A }^2}$ というふうに考えていくと ${k}$ 個先は ${\boldsymbol{ S } \boldsymbol{ A }^k }$ であることがわかり, これは行列累乗で効率的に求まる.

遷移行列は ${\boldsymbol{A}}$ は上限の線が変化するごとに変わるので, その都度行列を変えて計算すればよい.

${O(n c_i^3 \log k)}$

ソース

行列ライブラリをコピペしたら冪乗の引数が int になってて悲しかった.

#include<bits/stdc++.h>

using namespace std;

typedef long long int64;
const int mod = 1e9 + 7;

struct Matrix
{
  int a[17][17];

  Matrix()
  {
    memset(a, 0, sizeof(a));
  }

  Matrix operator*(const Matrix &kj)
  {
    Matrix ret;
    for(int i = 0; i < 17; i++) {
      for(int j = 0; j < 17; j++) {
        unsigned long long st = 0;
        for(int k = 0; k < 17; k++) {
          st += 1LL * a[i][k] * kj.a[k][j];
          st %= mod;
        }
        ret.a[i][j] = st;

      }
    }
    return (ret);
  }

  Matrix operator^(long long n)
  {
    Matrix ret;
    Matrix x = *this;
    for(int i = 0; i < 17; i++) ret.a[i][i] = 1;
    while(n > 0) {
      if(n & 1) ret = ret * x;
      x = x * x;
      n >>= 1;
    }
    return (ret);
  }
};

int main()
{
  int64 N, K;

  cin >> N >> K;

  vector< int > vect(17, 0);
  vect[0] = 1;
  for(int i = 0; i < N; i++) {
    Matrix mat;
    int64 A, B, C;
    cin >> A >> B >> C;
    B = min(B, K);
    for(int j = 0; j <= C; j++) {
      for(int k = -1; k <= 1; k++) {
        int nk = j + k;
        if(nk < 0 || nk > C) continue;
        mat.a[j][nk] = 1;
      }
    }
    mat = mat ^ (B - A);
    vector< int > st(17, 0);
    for(int j = 0; j <= C; j++) {
      for(int k = 0; k <= C; k++) {
        (st[j] += 1LL * mat.a[k][j] * vect[k] % mod) %= mod;
      }
    }
    st.swap(vect);
  }

  cout << vect[0] << endl;
}

ei1333の日記

ぺこい

Codeforces Round #420 (Div. 2)

A. Okabe and Future Gadget Laboratory

問題概要

解法

ソース

B. Okabe and Banana Trees

問題概要

解法

ソース

C. Okabe and Boxes

問題概要

解法

ソース

D. Okabe and City

問題概要

解法

ソース

E. Okabe and El Psy Kongroo

問題概要

解法

ソース