第二回日本最強プログラマー学生選手権 E,F問題メモ

第二回日本最強プログラマー学生選手権

Dから(頻出ではあるものの)若干のDPテクニックが要求され、Eからの実装はなかなか重めな印象。

夕方からの開始ということに気づかなかった。

E - Level K Palindrome

問題

  • 回文のレベルを以下のように定める(正確には問題ページ参照)
    • 'a' や 'b' はレベル1の回文
    • 'aa' や 'aba' はレベル2の回文
    • '(レベル $L$ の回文)(レベル $L$ の回文)' という回文はレベル $L+1$
    • '(レベル $L$ の回文)(任意の1文字)(レベル $L$ の回文)' という回文もレベル $L+1$
  • 文字列 $S$ と整数 $K$ が与えられる
  • $S$ を、いくつかの文字を書き換えることでちょうどレベル $K$ の文字列にできるか判定し、できる場合は書き換える必要のある最小の文字数を求めよ
  • $0 \le K \le 5 \times 10^5$
  • $1 \le |S| \le 5 \times 10^5$

解法

レベル1の回文で同じにならないといけない文字を考えると、以下のようになる。

|S| = 18 とすると、同じ高さになったindexの文字は同じである必要がある

0                                                 17
   1                                           16
      2                                     15
         3                               14
            4                         13
               5                   12
                  6             11
                     7       10
                        8  9

レベル2の回文では、さらに以下の文字が同じである必要がある。

0                       8  9                      17
   1                 7       10                16
      2           6             11          15
         3     5                   12    14
            4                         13

レベル3では

0        3     5        8  9       12    14       17
   1  2           6  7       10 11          15 16
            4                         13

レベル4……と思いきや、これはレベル5

0  1  2  3     5  6  7  8  9 10 11 12    14 15 16 17
            4                         13

各表現は、最初の折り返し直前までの文字列(レベル1なら 012345678、レベル2なら 0123、レベル3なら 01)がレベル0である(回文でない)ことを前提としているが、 レベル4のように折り返し直前までの文字列が1文字だけになったら、これはレベル1の文字列となってしまう。

よってその場合のみ、レベルが1ずれる。レベル4の文字列は作るのが不可能となる。またレベル6以上も長さ18の $S$ では作るのが不可能とわかる。

一般に、$|S|$ を2で割っていって、「1以外の、0になるまでのレベル」を作ることができる。

レベル   0   1   2   3   4   5   6   7
        18   9   4   2   1   0
作れる   o   o   o   o   x   o   x   x   ...

このように同じにならなければならない箇所は $S$ の中身によらず、$K$ と $|S|$ のみから決まるので、まずそれを求める。
(考えるのが面倒だったのでUnion-Find木を使ったが、多分ちゃんと計算すれば $O(|S|)$ で求められるはず)

そして、同じグループごとに $S$ から文字の出現回数を数えて、元からあるのが一番多い文字にそろえるのが、変更が一番小さくなる。

しかし、「ちょうど」レベル $K$ にしなければいけない。

レベルが過剰になってしまうというのは、たとえば上記の例でレベル2にしたいのに、 一番多い文字を採用すると $S_{0~3}$ が回文になってしまうようなケース。その場合レベル3以上となってしまう。

そのため、各グループ「何の文字に変更したか」「1番目でなく2番目に出現回数の多い文字を採用した場合、書き換える必要のある文字数は1番目を採用した場合から何文字増えるかの差分」を記録する。

回文となってはいけない場所が、変更の結果、回文となってしまっていないか確認し、 なっているなら差分のうち一番小さいものを2番目の文字に書き換えて回文を崩す。

そうするとちょうどレベル $K$ が保証される。

Python3

F - Max Matrix

問題

  • 長さ $N$ の数列 $a$ と、長さ $M$ の数列 $b$ がある
  • 最初、$a,b$ の要素は全て $0$
  • $Q$ 個のクエリを処理する。$i$ 個目のクエリでは $T_i,X_i,Y_i$ が与えられる
    • $T_i=1$ のとき、$a_{Xi}$ を $Y_i$ に置き換える
    • $T_i=2$ のとき、$b_{Xi}$ を $Y_i$ に置き換える
    • 毎回のクエリの処理直後に $\displaystyle \sum_{i=1}^{N} \sum_{j=1}^{M} \max(a_i,b_j)$ の値を出力する
  • $1 \le N,M \le 2 \times 10^5$
  • $1 \le Q \le 2 \times 10^5$
  • $1 \le Y_i \le 10^8$

解法

最初、全要素が0なので答えは言うまでも無く0。

たとえば $a$ の1個 $a_i$ を $5$ から $10$ に変えたときに、全体の答えがどうなるか考えると、

  • $b$ の、$10$ より小さい値について
    • その個数分だけ、新規に $\max(a_i,b_j)=10$ になる組が増える
      • 答えが「$該当個数 \times 10$」増加する
  • $b$ の、$5$ 以下の値について
    • その個数分だけ、今まで $\max(a_i,b_j)=5$ だった組が上に変わる
      • 答えが「$該当個数 \times 5$」減少する
  • $b$ の、$5$ より大きく $10$ より小さい値について
    • その総和だけ、$\max(a_i,b_j)=b_j$ として今まで答えに寄与していた分が無くなる
      • 答えが「該当する $b_j$ の総和」分だけ減少する

これで全て。
なので、差分だけ更新していくことで、クエリに高速に答えられそう。

なお、$10$ から $5$ に変わるなど値が減少するときは、3つめの増加と減少が逆転する。

範囲の個数や総和を求めたいので、セグメント木やFenwick Treeで管理すればよい。
「$a$ 用、$b$ 用」「個数用、総和用」で合計4つ、必要になる。

$Y_i$ の取り得る範囲が $10^8$ と大きいので、座標圧縮の必要がある。
今回は「$a_i$ を $Y_{old}$ から $Y_{new}$ に変えるとき、この間の個数や総和」が求まればよい、つまり $Y_i$ の大小関係さえ保たれていれば範囲指定できるので、 $Y_i$ として出てくる値をソートして小さい順に $0,1,2,...$ に対応させれば、$Q$ の長さ $2 \times 10^5$ として扱うことができる。

範囲の境界(以下なのか未満なのか、など)に注意。
どちらでもよいが、$a_i=b_j$ となる $b_j$ があり、今まで $\max(a_i,b_j)=b_j$ だった場合、それを「$\max(a_i,b_j)=a_i$ に変わったと見なし、更新対象に含めるのか(同じ値が引かれ、足されるので実質は変化ない)」「変化無しとして更新対象に含めないのか」は、3種類の更新の中で統一しておく必要がある。

Python3

programming_algorithm/contest_history/atcoder/2021/0417_jsc2021.txt · 最終更新: 2021/04/18 by ikatakos
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0