大和証券プログラミングコンテスト2022 Spring(AtCoder Regular Contest 138) A,B,C,D 問題メモ

Daiwa Securities Co. Ltd. Programming Contest 2022 Spring（AtCoder Regular Contest 138）

1年に何回もスポンサーしてくれるから、なんかSpringとか付き始めちゃったよ。

A - Larger Score

• 長さ $N$ の整数列 $A=(A_1,A_2,...,A_N)$
• 先頭の $K$ 要素の総和を、この数列のスコアとする
• 隣接する要素のswap操作を、何度でも繰り返せる
• スコアを初期状態から1でもよいので増やせるか判定し、可能なら最小手数を求めよ
• $2 \le N \le 4 \times 10^5$

初期位置で先頭 $K$ 個に属する要素をまとめて $F$、それより後ろをまとめて $B$ と呼ぶことにする。

スコアを現状から変えるには、何かしら、$F$ から要素を追い出して $B$ の要素を迎え入れないといけない。
この時、2個以上の要素を追い出す必要があるか？というと、ない。

      F    |   B           入れ替える2個が、a+b < c+d ならスコアは上がるが、
...  a  b  |  c  d  ...    それなら、単独でも a < c のように、
          ↓               (a,bのいずれか) < (c,dのいずれか) が成り立つ組み合わせがあることになり、
...  c  d  |  a  b  ...    その単独同士を入れ替えた方が、絶対に操作回数は少ない

$F,B$ から1個ずつ、$B$ 由来の方が大きくなるように要素を選び、この2個の距離を近づける操作だけを行えばよい。
そのときの操作回数は、両者の初期位置の距離に等しい。

なので、$A$ の全要素を、初期位置のindexがわかるように値で降順ソートし、大きい方から調べていく。
この時、同じ値なら、$F$ の方が先になるようにしておく。

「$L$: $B$ に属する要素のうち、暫定調べた中で、最も左にある要素のindex」を更新していくと、

• 現在調べている要素 $A_i$ が $F$ に属するなら
  • 自身を $F$ から選ぶとするなら、$B$ からは $A_L$ を選ぶのが最適
  • $ans \xleftarrow[\min]{} L-i$
• $B$ に属するなら
  • $L \xleftarrow[\min]{} i$

としていけば、$O(N \log{N})$ で答えが求まる。

Python3

B - 01 Generation

• 空の数列 $x$ に要素を追加して、$0,1$ のみからなる数列を作る
• 操作は、以下の2つを好きな順で何度でも行える
  • 操作A: $x$ の全要素を反転した後、先頭に0を追加
  • 操作B: 末尾に0を追加
• 0,1のみからなる長さ $N$ の数列 $C$ が与えられるので、構築可能か判定せよ
• $1 \le N \le 2 \times 10^5$

操作をシミュレーションして作れる数列を試してみると、「先頭は必ず0」という共通点が見つかる。
たしかに、先頭が1の要素は作りようがない。

また、その先頭の0は、全要素が0でない限りは、Aによって追加されたものということになる。
全要素が0ならBだけで構築可能なので考察終わり。

どうも逆順にたどるとよさそう。
$x=C$ からはじめて、以下の操作を繰り返して、$x$ を空にできたら達成可能、という解法が思いつく。

• $x$ の先頭が1ならアウト
• $x$ の末尾が0なら、1が出てくるまで末尾を削除（操作B'）
• $x$ の先頭が0なら、先頭を削除し、$x$ の要素を全て反転（操作A'）、最初に戻る

実際には全て反転させていたらTLEなので、「今、$x$ の中身は反転して扱いますよ」フラグを切り替えて管理する。

これで上手くいくことをちゃんと証明するには、「本当は達成可能なのに、途中で末尾の0を敢えて残さないと失敗する」 パターンが絶対にないということを言わないといけないが、正直そこは曖昧なまま通した。

改めて考えると、操作B'を貪欲に適用した結果、$x$ が失敗したとして、

  失敗時点のx |  削除した文字
1 0 0 1 ... 1 | (0 0 0 1 1 0 0 0)

A'は先頭からしか見ないので、削除した文字を仮に残していたとしても、それが成功可否に与える影響は、ない。
むしろ下手に残すと、本来ならB'で削除できた要素が先頭に来た時、それが1だったため失敗、ということがあるため、切り詰められるならなるべく切り詰めた方がよい。

ので、操作B'を貪欲に適用する逆順操作で大丈夫なことがわかる。

Python3

C - Rotate and Play Game

• $N$（偶数）枚のカードがあり、番号 $i$ のカードには整数 $A_i$ が書かれている
• 2人でゲームをする
  • 先手は、好きなカードを取る
  • 後手は、残っている中で番号が最小のカードを取る
  • カードがなくなるまで繰り返し、取ったカードに書かれた値の総和がスコア
• 開始前に、先手はカードの値を好きなだけローテートすることができる
  • 1回のローテートで、番号 $1,2,...,N-1,N$ のカードに書かれた整数は $A_2,A_3,...,A_N,A_1$ になる
• 先手が適切なローテートとゲーム進行を行った上で取り得る最大スコアと、そのためのローテート回数 $k$ を求めよ
• $2 \le N \le 2 \times 10^5$

ローテートしなくても先手は相当有利で、ほぼ、$A_i$ の中で大きい方から半分（上限値）を取れる。

$A_i$ の中で大きい方から半分を「強いカード」として、

• 番号 $2$ までに強いカードが $1$ 枚より多く含まれる
• 番号 $4$ までに強いカードが $2$ 枚より多く含まれる
• 番号 $6$ までに強いカードが $3$ 枚より多く含まれる
• …
• 番号 $2i$ までに強いカードが $i$ 枚より多く含まれる

のどれか1つでも成り立つ場合は、先手が全て回収しきる前に後手が強いカードを取ってしまうので、上限値を達成できない。

7  1   6  8   3  4   5  2    先手が6,7,8を全て取るのに3手かかるが、
^      ^  ^          ^       後手がそれより早く、そのいずれかを取る状態になってしまう

だが、前半に強いカードが固まっているということは、後半は弱いカードの方が多いということで、 なんとなく、後手に強いカードを1枚も取らせないローテート回数がありそう。

ローテートが済み、順番が決まった後の判定は、正しい括弧列の判定と似ていて、弱いカードを+1、強いカードを-1としたときに、 $2,4,6,...$ 番目の累積和が全て非負なら成功、と言い換えられる。

   7  1   6  8   3  4   5  2
0 -1 +1  -1 -1  +1 +1  -1 +1
0 -1  0  -1 -2  -1  0  -1  0
            ~~ ←だめ

ここで「累積和の中で最低値を取る箇所の次」を先頭に持ってくれば、累積和には一律に(-最低値)がプラスされる。
結果として、累積和の全要素を非負にできる。

   3  4   5  2   7  1   6  8
0 +1 +1  -1 +1  -1 +1  -1 -1
0  1  2   1  2   1  2   1  0

これで先手は大きい方から $K$ 枚を悠々と取れる。

$A_i$ に同じ要素があって、ちょうど上位・下位半分にまたがって同じ値 $X$ があるとき。
$X$ は強いと見なすべきか、弱いと見なすべきか？

これは、数さえ合わせれば、適当に $A_i=X$ である $i$ の中から強いカードを決めてしまってよい。
どう選んでも、破綻無く上のアルゴリズムを適用できる。

Python3

D - Differ by K bits

• 以下の条件を満たす、長さ $2^N$ の数列が構築可能か判定し、可能なら1例、構築せよ
  • $0,1,...,2^N-1$ の $2^N$ 個の数が1回ずつ出現する（順列である）
  • どの隣り合う2要素も、2進数で見たときに異なる桁がちょうど $K$ 個
• $1 \le K \le N \le 18$

グレイコード、という名前自体は覚えていなかったが、 なんか本問の $K=1$ の時に相当する、bitを1箇所ずつ変えながら $N$ 桁の全ての数を巡回する方法があるのは記憶していた。

その差分となるbit位置は、LSB（Least Significant Bit）を取れば上手くいく。
（これはサンプル1を観察することでも類推できる）

• bit全探索とグレイコード - Qiita

i   Gray  iのLSB
0   0000
       v  0001
1   0001
      v   0010
2   0011
       v  0001
3   0010
     v    0100
4   0110
       v  0001
5   0111
        ：

なので今回も、 「LSBが0b0001の時にXORする、$K$ bitが立っている何らかの値」 「LSBが0b0010の時にXORする、$K$ bitが立っている何らかの値」……を事前に決めてやれば、似たようなことができないか。

試してみると、$K$ が偶数の時は不可能とわかる。popcountが偶数の数しか作れない。

また、$N=K \neq 1$ の時も不可能とわかる。0と、全bitが立った数しか作れない。
（$N=K=1$ の時は、0 1 で完結するので構築可能）

その他、つまり $K \lt N$ かつ $K$ 奇数の時は、構築可能か？

1次独立な $N$ 個の「$N$ bit 中 $K$ 個のbitが立った数」を用意できればよい。

• XORの基底をめっちゃ楽に求める方法があるらしい！！！？？？ - Qiita

• 採用が決まった数のリスト $F$
• $F$ の基底のリスト $B$
  • 現在の $F$ の要素のXORで作れる、最大bitが互いに異なる数のリスト

を、いずれも空で用意する。両者の要素が $N$ 個になるまで、以下を繰り返す。

• $N$ 個中 $K$ 個のbitが立った数を列挙し、順番に採用できるか試す
  • 採用確認中の数を $a$ とする。また、$b=a$ という変数も用意する
  • $F$ の要素から $a$ が作れるなら不採用
    • $B$ で大きい方から順番に（$B_i$ とする）、$B_i$ の最大bitが $b$ で立っていたら $b←b \oplus B_i$ とする
    • 最終的に $b=0$ となれば、$a$ は $F$ から作れる
  • 作れないなら $a$ は採用
    • $F$ に $a$ を追加
    • $B$ に（チェック後の）$b$ を追加

要素が $N$ 個になったら成功。

実際にやってみると、$K \lt N$ かつ $K$ 奇数の時は、全て可能であることがわかる。

これを元に、グレイコードよろしく、$0$ からはじめて $F_1,F_2,F_1,F_3,F_1,F_2,...$ という順番でXORを適用していけばよい。

$N$ bit中 $K$ bitをランダムで選んで立てて、それをローテートしたものを $N$ 通り用意しても、割と高確率で独立になる。

001011
010110
101100
011001
110010
100101

成功するまで最初の $K$ bitの立て方を試しても、まぁ十分な確率で成功する[要出典]。

N=6, K=3,  000111
N=9, K=3,  001001001
N=10 K=5,  0111010001

など、ローテートの過程で重複ができるもの、または0と1を反転したものが重複するものは、独立にならず失敗する。

Python3