okura diary

おもに競技プログラミングの日記

Mujin 2017 A. Robot Racing

数え上げ 順列

atcoder.jp

考察
  • 2つ前までしか移動できないので、ロボットが2つ連続で並んでいる箇所があると自由にゴールさせられない。
  • 逆にいうとそういう箇所がなければ任意の順でゴールさせられる。
  • あるロボット iに着目し、前にあるロボットをいくつゴールさせれば自分がゴールできるか考えてみる。とりあえず最初にゴールさせられるかどうかで考える。

  • ロボット iより後ろのロボットをわざわざ動かす必要はない。それより前にあるロボットを2つ連続しないように動かすことができれば最初にゴールさせられる。

  • 直感的に前が詰まり過ぎていると、連続を回避しようと前へ前へと動かすが最終的に座標1に近いあたりで頓挫することがわかる。

  • こうならない必要条件としては、前に i個ロボットがいるなら各 x(1\leq x \leq i)について pos(x) \geq 2x + 1が挙げられる。これは、最終的に座標1から一つおきに並んでいるギリギリの状態になったとするとそれぞれのロボットはその最終位置よりも右側にある、という条件である。

  • ここでこの条件が成り立っていると仮定すると、前から順に最終位置にそろえていくことで必ず着目しているロボットを最初にゴールさせられることがわかる。

  • ここまでくると各ロボットについて前のロボット達を最低何個ゴールさせなければならないか？を考えたくなる。ここで"最低"と言ったがある k個をゴールさせれて着目しているロボットをゴールさせられるならば、どの k個をゴールさせても適切に前に詰めることでロボットをゴールさせられることがわかる。

  • 一つも動かさなくてよい場合と同様に考える。1つのロボットをゴールさせられると直感的に2マス分の余裕が生まれる。したがって、前に i個ロボットがいるなら \max_{1 \leq x \leq i}{(pos(x) - (2x + 1)) / 2}個くらい取り除く必要がある予想できる。

  • 帰納法でいい感じに示せそう(雑)ということまで確認して実装するとACした。なおこの値の計算は累積maxでやると O(N)になり、これが計算できれば順列の数の計算は簡単な掛け算でできる。

感想
  • 限界の状態を考えて条件の定式化、必要条件⇒実は十分の流れがちゃんと導けたので良かった(結構苦手なタイプ)
  • ただもう少しスムーズに解きたかった。
  • 解説では初めにゴールさせられるか、の考察からstackを使った解法に至っていたが、実質的に上の予想を利用している(スタックの k番目が 2k + 1以上だったら...の部分)

Submission

void solve() {
  int N;
  cin >> N;
  vector<int> x(N);
  for (int i = 0; i < N; i++) { cin >> x[i]; }
  vector<int> c(N, -1);
  c[0] = c[1] = 0;
  vector<int> cnt(N + 1, 0);
  cnt[0] = 2;
  for (int i = 2; i < N; i++) {
    int expected = 2 * i - 1;
    c[i] = max(c[i - 1], (expected - x[i - 1] + 1) / 2);
    cnt[c[i]]++;
  }
  for (int i = 1; i <= N; i++) cnt[i] += cnt[i - 1];
  mint ans(1);
  for (int i = 0; i <= N; i++) {
    if (cnt[i] - i <= 0) break;
    ans *= mint(cnt[i] - i);
  }
  cout << ans << endl; 
  return;
}

Exawizards 2019 C. Snuke the Wizard

Binary Search ARC

atcoder.jp

考察
  • 青diffだが全然わからなくてかなり苦戦した。あることに気づけばあとは簡単。
  • 各ゴーレムはあるゴーレムよりも向こう側に行こうと思うと、そのゴーレムと一緒に行動するしかない。すなわち、消滅するゴーレムは左右の端の連続した区間となる。
  • この単調性に気づけばあとは二分探索するだけ
感想
  • 軽く1時間は溶かしたと思う。なかなか解けないときは対象(今回ならば消える/残るゴーレム)一つ一つの性質ではなく集合全体の性質を考えてみる、というのを意識したい。
  • 何かしらの単調性というのが鍵に成る問題は多い。特に1次元上の問題では今回のような性質を真っ先に疑えるような感覚を養っていけると理想。

Submission

void solve() {
  int N, Q;
  cin >> N >> Q;
  string s;
  cin >> s;
  vector<char> t(Q), d(Q);
  for (int i = 0; i < Q; i++) { cin >> t[i] >> d[i]; }
  auto check = [&](int x) {
    int pos = x;
    for (int i = 0; i < Q; i++) {
      if (s[pos] == t[i]) {
        if (d[i] == 'L')
          pos--;
        else
          pos++;
      }
      if (pos < 0) return -1;
      if (pos >= s.size()) return 1;
    }
    return 0;
  };
  int L, R;
  {
    int l = -1, r = s.size();
    while (r - l > 1) {
      int mid = (l + r) / 2;
      if (check(mid) < 0)
        l = mid;
      else
        r = mid;
    }
    L = r;
  }
  {
    int l = -1, r = s.size();
    while (r - l > 1) {
      int mid = (l + r) / 2;
      if (check(mid) > 0)
        r = mid;
      else
        l = mid;
    }
    R = l;
  }
  cout << R - L + 1 << endl;
  return;
}

Keyence2019 D. Double Landscape

DP 数え上げ Blue ARC

atcoder.jp

考察
  • D - 25個の整数で学んだように、最大値から順番に位置を決定していくのが筋がよさそう。
  • 最大値から順に決めていくと、数字の位置を決めることで縦と横のそれぞれ最大値になるかならないかやその数が既に置かれたマスのx,y座標の集合を管理するだけでわかる。
  • あとはその情報を用いてうまく数え上げられる。
感想
  • つい最近解いた問題で得た教訓が生きてよかった。

Submission

void solve() {
  int N, M;
  cin >> N >> M;
  vector<int> A(N), B(M);
  cin >> A;
  cin >> B;
  vector<int> r(N * M, -1);
  vector<int> c(N * M, -1);
  for (int i = 0; i < N; i++) {
    A[i]--;
    if (r[A[i]] != -1) {
      cout << 0 << endl;
      return;
    }
    r[A[i]] = i;
  }
  for (int i = 0; i < M; i++) {
    B[i]--;
    if (c[B[i]] != -1) {
      cout << 0 << endl;
      return;
    }
    c[B[i]] = i;
  }
  mint ans(1);
  set<int> R, C;
  int num = 0;
  for (int i = N * M - 1; i >= 0; i--) {
    if (r[i] == -1 && c[i] == -1) {
      int pos = (int)R.size() * C.size() - num;
      if (pos <= 0) {
        cout << 0 << endl;
        return;
      }
      ans *= mint(pos);
    } else if (r[i] == -1) {
      if (C.find(c[i]) != C.end()) {
        cout << 0 << endl;
        return;
      }
      ans *= mint(R.size());
      C.insert(c[i]);
    } else if (c[i] == -1) {
      if (R.find(r[i]) != R.end()) {
        cout << 0 << endl;
        return;
      }
      ans *= mint(C.size());
      R.insert(r[i]);
    } else {
      if (C.find(c[i]) != C.end() || R.find(r[i]) != R.end()) {
        cout << 0 << endl;
        return;
      }
      R.insert(r[i]);
      C.insert(c[i]);
    }
    num++;
  }
  cout << ans << endl;
  return;
}

ACL1 C. Moving Pieces

Min cost flow ARC

atcoder.jp

考察
  • 最小費用流の形にできそう、超頂点S,Tを用意してコマの開始位置へSから容量1コスト0の辺を張って、好きなところから1つずつ回収してTに送る容量1コスト0の辺を加える。
  • 元のグリッドグラフ上では各頂点から右と下に容量無限(コマの個数でよい)コスト-1の辺を張る(ここで-1なのはパスの長さの和を最大化したいから)。

  • しかし、最小費用流が負辺があるのは少し厄介である。今回は明らかに負の閉路はない。負の辺に対応するには

    1. グラフを変形して負辺を除去する

    2. ポテンシャルの初期化をDijkstraではなくBellman-Fordを用いる

の2通りの方法があるが、今回は1を採用した。(理由: ベルマンフォードでポテンシャル初期化するライブラリを持っていない&ACLにもなかったため)

  • グラフの変形による負辺の除去は蟻本のコラムにある。少し複雑そうにも見えるが、基本的なアイデアは負の辺にあらかじめ目一杯流しておいて後で戻すである。 流す量なども変形によって代わることに注意。
想定解&感想
  • 想定解ではもっと綺麗に最小費用流の形に言い換えていて、この方法ではグラフに負の辺ははじめから現れない。
  • 「パスの長さの和の最大化」として捉えるのではなく、「一番右下まで行ったときに比べてどれくらい損をしたか、の和を最小化」と捉えることですんなりと最小費用流で解ける。
  • グラフの変形もそこそこ面倒なのでBellman-Fordで間に合いそうな時用にライブラリ準備しておくべきだなぁ...と思った。

Submission

void solve() {
  int N, M;
  cin >> N >> M;
  vector<string> f(N);
  cin >> f;
  int s = N * M, t = N * M + 1;
  int S = N * M + 2, T = N * M + 3;
  atcoder::mcf_graph<int, int> g(T + 1);
  auto encode = [&](int i, int j) { return i * M + j; };
 
  int C = 0;
  for (int i = 0; i < N; i++)
    for (int j = 0; j < M; j++)
      if (f[i][j] == 'o') C++;
 
  g.add_edge(S, s, C, 0);
  g.add_edge(t, T, C, 0);
 
  int F = C;
  int geta = 0;
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < M; j++) {
      if (f[i][j] == '#') continue;
      int u = encode(i, j);
      g.add_edge(u, t, 1, 0);
      if (f[i][j] == 'o') g.add_edge(s, u, 1, 0);
      if (i + 1 < N && f[i + 1][j] != '#') {
        int v = encode(i + 1, j);
        geta -= C;
        F += C;
        g.add_edge(v, u, C, 1);
        g.add_edge(S, v, C, 0);
        g.add_edge(u, T, C, 0);
      }
      if (j + 1 < M && f[i][j + 1] != '#') {
        int v = encode(i, j + 1);
        geta -= C;
        F += C;
        g.add_edge(v, u, C, 1);
        g.add_edge(S, v, C, 0);
        g.add_edge(u, T, C, 0);
      }
    }
  }
  auto res = g.flow(S, T, F);
  cout << -res.second - geta << endl;
  assert(res.first == F);
  return;
}

ACL1 B. Sum is Multiple

Math ARC

atcoder.jp

考察
  • 式を整理すると、 aを任意の整数として 2Na = k(k + 1)が成り立つような最小の kを求める問題である。
  • 2Nの素因数が k, k + 1にどのように振り分けられているのかが気になる。
  • 2N = pq と置き、 kが pの倍数、 k + 1が qの倍数であるとしよう。 pの数はそんなに多くないのでこれを固定して全部試すのは可能。
  • いまおいた仮定から、整数 x, yを用いて k = px, k + 1 = qyとなるが、ここで kを消去すると px + 1 = qy \Leftrightarrow -px + qy = 1となる。
  • これは馴染みのある形で、extgcdで解ける不定方程式である。これを解いて、 x > 0を満たす xが最小の解を求めれば、 pxが求めたかった kである。
拡張ユークリッドと中国剰余定理

この問題の想定解ではCRT(中国剰余定理)を用いている(ACL記念回なので使うのはそれはそう...)。自分もどうせCRT使うんだろうとメタ読みして居たのだが先にextgcdで解ける形になったのでそちらで解いてしまった。 自分の中でこの2つの問題は結びついていなかったが、実質的にほぼ同じであることにこの問題で気付かされた。

例えば px + qy = 1は今回の変形の逆で px = kと置くことで \begin{cases} px = k \\ qy = 1 - k \end{cases} となり \begin{cases} k \equiv 0 \ (mod p) \\ k \equiv 1 \ (mod q) \end{cases} を解くのと同じことになる。逆も似たように変形できる。

Submission

void solve() {
  ll N;
  cin >> N;
  auto fac = factorize(2 * N);
  int M = fac.size();
  ll ans = LLINF;
  for (int i = 0; i < (1 << M); i++) {
    ll mul = 1ll;
    for (int j = 0; j < M; j++) {
      if ((i >> j) & 1) mul *= fac[j].second;
    }
    ll a, b;
    ll p = mul, q = 2 * N / mul;
    extgcd(p, q, a, b);
    if (a >= 0ll) {
      ll d = ((a / q) + 1);
      a -= d * q;
      b += d * p;
    }
    if (b <= 0ll) {
      ll d = ((-b) / p + 1);
      a -= d * q;
      b += d * p;
    }
    ll d1 = (b - 1) / p;
    ll d2 = (-1 - a) / q;
    ll d = min(d1, d2);
    a -= d * q;
    b += d * p;
    assert(a <= -1);
    assert(b >= 1);
    chmin(ans, p * (-a));
  }
  cout << ans << endl;
  return;
}

AGC 046 B. Extension

DP AGC

atcoder.jp

水diffだが解けなかったので自戒の意を込めて記録。

制約から2乗のDPかと思い考えたがうまく重複せずに数えられずDPでない方針を考えた。 その結果いろいろと言い換えはできた(各ブロックは下か左のどちらかから見え、どちらからも見えるものはない等)が、うまく数え上げられず解説を見た。

この問題を解く上で大切な意識は「一つの状態を作るための操作列は様々ありうるが、一つの状態を一つの操作列に1対1に対応させる」ということだった。

今回の場合、一番上の行に黒マスが1つしかないならば最後の操作は行の追加、そうでないならば最後の列の操作である、としてよいことが鍵となる。あとは素直にDPできる。

Submission

void solve() {
  int A, B, C, D;
  cin >> A >> B >> C >> D;
  auto dp = vect(C + 1, vect(D + 1, vect(3, mint(0))));
  dp[A][B][0] = mint(1);
  for (int i = A; i <= C; i++) {
    for (int j = B; j <= D; j++) {
      if (i == A && j == B) continue;
      if (i > A) {
        dp[i][j][0] = dp[i][j - 1][0] * mint(i - 1);
        dp[i][j][1] =
            (dp[i - 1][j][0] + dp[i - 1][j][1] + dp[i - 1][j][2]) * mint(j);
        dp[i][j][2] = dp[i][j - 1][1] + dp[i][j - 1][2] * mint(i);
      } else {
        dp[i][j][0] = dp[i][j - 1][0] * mint(i - 1);
        dp[i][j][1] = dp[i][j - 1][0] + dp[i][j - 1][1] * mint(i - 1);
        dp[i][j][2] = dp[i][j - 1][1] + dp[i][j - 1][2] * mint(i);
      }
    }
  }
  cout << dp[C][D][0] + dp[C][D][1] + dp[C][D][2] << endl;
  return;
}

ARC 091 F. Strange Nim

ゲーム Grundy数 Yellow ARC

atcoder.jp

考察
  • 独立なゲームが N個あるのでGrundy数を考えてみる。 Kが例えば十分大きい偶数なら以下の様になる
0, ..., K-1 | K, ... , 2K - 1 | 2K, ...
0, 0, ....0 | 1, 0, .... 1, 0 | 2, 1, 0, 2, 1, 0...
  • Grundy数さえ高速に( 10^5 \sim 10^6くらいで)求められればXOR取るだけ
  • 愚直に求めようとすると間に合わないので周期性を用いたい
  • Kが大きい場合と小さい場合に分けてそれぞれの特徴を活かして計算するタイプのやつだろうと直感が働く
  • まず Kが大きい場合、上の例で縦棒で区切っているようにK個ごとのグループに分ける。このとき Kが大きければ(具体的には \sqrt{N}以上とか)グループ数はさほど多くない( O(\sqrt{N})程度)。 k番目のグループ内では k - 1番目のグループの最後の k個に kを加えた周期 k+1の列が繰り返される。この各グループの周期を求めるのは列の切り貼り挿入ができる平衡二分探索木を用いればlog一つくらい乗るがシミュレーションできる。
  • 次に Kが小さい場合について考えるものの、グループ数が多すぎて手に負えず困った。
  • ここで断念して解説を見た
想定解
  • Grundy数を g(N, K)と書くことにすると Nが Kの倍数でないとき g(N, K) = g(N - \lfloor{N / K}\rfloor - 1)、倍数の時 g(N, K) = N / Kが成り立つ。これは上の考察を踏まえれば簡単にわかる。
  • 基本的にはこの式にそって再帰的にもとめていく。ここで前者の場合に、 \lfloor N/K \rfloor + 1を引いてもなお Kで割った商が変化しないのであれば一気に引けるだけ引く。これは二分探索で境界を探せば簡単にできる。
  • N / Kくらいで再帰回数が抑えられ(再帰1回で1ブロック分進むから)、1ステップでだいたい \frac{K - 1}{K}倍くらいになる。
  • Kが大きいときは前者が効いてきて、小さい時は後者が効いてくることでどちらの場合も O(\sqrt{N})程度でGrundy数を求められる。
反省点
  • Grundy数の様子は把握できていたのに g(N, K)の式を立てられていなかった。周期が見えているときはそれに頼るだけでなくちゃんと定式化するべきだった。(これができていれば大きい場合はわかっていたので、 Kが小さい場合は愚直に再帰して間に合う、ARMERIAさんの解法がそれ(ARC091 F - Strange Nim - ARMERIA))

Submission

int grundy(int a, int k) {
  if (k == 1) return a;
  if (a < k) return 0;
  if (a % k == 0) return a / k;
  int b = a / k;
  int l = 1, r = a / (b + 1) + 1;
  while (r - l > 1) {
    int mid = (l + r) / 2;
    if ((a - (ll)(b + 1) * mid) / k < b)
      r = mid;
    else
      l = mid;
  }
  assert(a - (ll)(b + 1) * l >= 0);
  return grundy(a - (b + 1) * l, k);
}
 
void solve() {
  int n;
  cin >> n;
  int g = 0;
  for (int i = 0; i < n; i++) {
    int a, k;
    cin >> a >> k;
    g ^= grundy(a, k);
  }
  if (g == 0)
    cout << "Aoki" << endl;
  else
    cout << "Takahashi" << endl;
  return;
}