AtCoder Grand Contest 037

更新日時:

AtCoder Grand Contest 037

ソースコード

解法のメモ

A - Dividing a String

模範解答

貪欲法でやっても解けるが、末尾の処理が難しいので DP で解くことにする。そのためにまず次の補題を示す。

補題 A.1:最長の分割においては、長さ $5$ 以上の部分文字列は存在しない。

証明:長さ $5$ 以上のところは、必ずさらに分割が可能であることを示す。分割の仕方は $(1, 4)$, $(2, 3)$, $(3, 2)$,$(4, 1)$ のいずれかがありうる。そもそも文字数が違うので、分割後の $2$ つの文字列が一致することはない。したがってその両隣の文字列と一致する可能性だけ考慮すればいいが、それで潰れるのはせいぜい $2$ 通りだけなので、必ず $2$ 通り以上は生き残る。これは最長の分割であるという仮定に反する。これが示すべきことであった。

よって DP で $O(N)$ で解ける。次の DP では $j = 1, 2, 3, 4$ である。

$DP[i][j] = i$ 文字目までみて、最後の文字列が $S[i - j, i)$ である場合の最長の文字列の分割の仕方。

その必要はないのだが、 $S$ の冒頭に 'X' を追加して、これを番兵とする。 $N = \lvert S \rvert$ とする。初期状態: $DP[1][1] = 0$, otherwise $0$. 答え: $\max _ j DP[N][j]$. 遷移: $i = 1, \dots, N - 1$ に対し、 $j = 1, \dots, 4$ に対し、 $k = 1, \dots, 4$ に対し、 $S[i - j, i) \neq S[i, i + k)$ ならば、 \[ DP[i + k][k] \gets \max(DP[i + k][k], DP[i][j] + 1). \] ただし範囲外参照の場合は continue; する。

ポイント

これを DP で解くのが上級者か…と思った。

B - RGB Balls

コストの言い換え

この問題のコスト $c _ i - a _ i$ をまず言い換える。文字列の上を、文字列をカードの上に管理した人が歩いていくものとする。 $RGB$ の組が完成したら文字列を消去することにする。例えば $S = ``RRRGGGBBB”$ の場合は \[ \begin{align} C _ 0 &= \emptyset, C _ 1 = \{ R \}, C _ 2 = \{ R, R \}, C _ 3 = \{ R, R, R \}, \\\ C _ 4 &= \{ RG, R, R \}, C _ 5 = \{ RG, RG, R \}, C _ 6 = \{ RG, RG, RG \}, \\\ C _ 7 &= \{ RG, RG \}, C _ 8 = \{ RG \}, C _ 9 = \emptyset. \end{align} \] となる。すると完成した各文字列について、 コストは文字列に生存期間に等しい 。すなわちコストの和は \[ \sum _ {i = 0} ^ {3N} \sharp C _ i \] に等しい。したがってこの数字を最小にすることが、我々の仕事である。

解答

すると、操作が、ある一定の自由度をのぞいてほぼ一意に定まってしまうことがわかる。

わかりやすいように今まででできた文字列について $\sharp R \leq \sharp G \leq \sharp B$ を仮定する。すると今まで $\sharp R$ 個を完成させているのが最善である。カードには $GB$ が $\sharp G - \sharp R$ 個書かれていて(管理上 $GB$ と $BG$ は区別する必要はない)、 $B$ が $\sharp B - \sharp R$ 個書かれているのが最善であることもわかる。ここに $R$ が飛び込んでくると $GB$ と結合させて生存させないようにするのが最善である。 $G$ が飛び込んでくると $B$ とくっつけるのが最善である。 $B$ が飛び込んでくると新しく $B$ を作るしかない。よって消し方、くっつけ方に自由度があるので、それを掛け算すると答えになる。

ただし最後に人に文字列を配るために $N!$ をかける必要はある。

ポイント

これは生存期間の言い換えができなくて解けなかった。

C - Numbers on a Circle

解答

$\{ B _ i \}$ に対し操作を逆にし $\{ A _ i \}$ にすることを考える。まず $B _ i > B _ {i - 1} + B _ {i + 1}$ となっている所にしか操作ができない。この場合に重要なのが、 $B _ {i - 1}$ と $B _ {i + 1}$ については 操作ができない という事実である。 $B _ i$ が大きすぎて、それらについては操作することはできない。

したがって、操作が可能である数字は、必ず $1$ 個以上飛ばして待機しているはずである。ゆえに、これらの操作の順序は最終結果には影響しないとわかる。よって操作が可能な場所は局所的に判定できるが、操作をして問題がないとわかる。

ここで操作の回数は $B _ i / (B _ {i - 1} + B _ {i + 1})$ 回であり、操作後の数字は $B _ i \% (B _ {i - 1} + B _ {i + 1})$ である。ただし $A _ i$ 未満になってはいけない。その場合はストップする必要がある。ストップしない場合に限り、次に操作が可能になる数字は $B _ {i - 1}, B _ {i + 1}$ のいずれかである。

実装

以上の操作の部分を実装すると以下のようになる。

void update(int v)
{
  int before = (v + N - 1) % N;
  int after = (v + 1) % N;
  ll a_c{B[before] + B[after]};
  ll cnt{B[v] / a_c};
  ll mod{B[v] % a_c};
  if (cnt == 0)
  {
    return;
  }
  if (mod >= A[v]) // この場合はストップしない。
  {
    B[v] = mod;
    ans += cnt;
    B_sum -= a_c * cnt;
    Q.push(before); // 隣の数字が次の候補になる。
    Q.push(after);
  }
  else
  {
    if ((A[v] - mod) % a_c == 0)
    {
      B[v] = A[v];
      cnt -= (A[v] - mod) / a_c; // 操作しすぎた分を戻す。
      ans += cnt;
      B_sum -= a_c * cnt;
    }
    else
    {
      No();
    }
  }
}

操作は、一致する可能性が出てくるところまでやる。

void solve()
{
  while (A_sum < B_sum && !Q.empty())
  {
    update(Q.front());
    Q.pop();
  }
  if (A_sum == B_sum)
  {
    same(); // 一致判定。
  }
  else
  {
    No();
  }
}

queue<int> Q; で十分である。初期状態は全部放り込んでおけばいい。

計算量について

それぞれの頂点が何回 update されるかを考察する。すると update 後は 最低でも $B[i]$ は半分になっている (かまたはストップしてそれ以上触らない)のだから、 $\log _ 2 B[i]$ 回しか操作しない。つまり $M = \max _ i B _ i$ とすると、計算量は $O(N \log M)$ で抑えられる。

ポイント

これは普通にやった。計算量の見積もりだけが自信がなかった。

D - Sorting a Grid

ポイント

E - Reversing and Concatenating

ポイント

F - Counting of Subarrays

ポイント

その他