AtCoder Regular Contest 145 A,D問題メモ

AtCoder Regular Contest 145

なんかひらめきの調子が良かった。（ひらめきである以上、再現性はない）

A - AB Palindrome

• AとBからなる文字列 $S$ がある
• 隣接する2文字を「AB」に置き換える、という操作を繰り返して（0回でもよい） $S$ を回文にできるか判定せよ
• $2 \le N \le 2 \times 10^5$

最初よく読んでなくて、$S$ は全ての英大文字からなると思ってしまっていた。
まぁその場合でも、前後から'A','B'以外の文字が同じか調べて取り除いていけば大体同じ。

操作回数最小とかでなく単にできるかできないかの判定なら、都合のいいようにメッタメタにいじった場合を考えてよい。

ずらしながら繰り返し操作することで、'ABBB…BBB' と 'AAA…AAAB' という並びは自由に作ることができる。

• 末尾が'A'なら $1～N-1$ 文字目を 'ABBB…BBB' にすれば、'ABBB…BBBA' になる
• 先頭が'B'なら $2～N$ 文字目を 'AAA…AAAB' にすれば、'BAAA…AAAB' になる

それぞれ回文が成立する。よってこのどちらかならYes。
ただし、$N=2$ の時は最初から回文である'AA'、'BB'以外は不可能である点に注意。

逆に $S$ が 'A…B' という形なら、先頭文字は'A'、末尾文字は'B'から変えることができないので、No。

Python3

D - Non Arithmetic Progression Set

• 以下の条件を全て満たす整数集合 $S$ を1つ、構築せよ
• 条件
  • 要素数 $N$
  • 各要素は $-10^7$ 以上 $10^7$ 以下の整数で、互いに相異なる
  • 総和は $M$
  • どの相異なる3要素をとっても等差数列でない。つまり、どのように $x,y,z(x \lt y \lt z)$ を取り出しても、$y-x \neq z-y$
• $1 \le N \le 10^4$
• $|M| \le N \times 10^6$

大枠を構成するためのひらめきと、最後に条件内で総和を調整するための思考の双方が求められる。

ひとまず総和はあとから調整できそうなので、今は無視する。

なるべく数字は密に使いたいが、$0,1,2$ のように差1の数字を3つ並べるとアウト。でも2つまでならいい。
なので、2つの並びをなるべく貪欲に敷き詰めることを考えてみる。

0 1 2 3 4
o o x o o

$0,1$ を使うとして、$2$ を使わなければ、$3,4$ はまた使える。

すると、$5～8$ は、4数から作るどれかしらのペアの等差数列になってしまう。
逆に、この時点で置くと等差数列になってしまう一番大きな数字は $(0,4)$ ペアに対しての $8$ であることは簡単にわかるので、$9$ 以降はまた確実に使える。

0 1 2 3 4 5 6 7 8 9 10 11 12 13
o o x o o x x x x o  o  x  o  o

9から、0からと同じように ooxoo と置く。ooxoo の並びは、この中だけでは等差数列にならないことはわかっていて、また $(0,1,3,4)$ の塊とも十分に離れて互いに干渉しないことは先ほどの議論よりわかっているので、条件に違反しない。

次に確実に使えるのは $(0,13)$ ペアに対しての $26$ の次、$27$ なので、また同様に現状をコピーする。

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 ... 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40
o o x o o x x x x o  o  x  o  o  x ...  x  o  o  x  o  o  x  x  x  x  o  o  x  o  o

こうしていくと、実験すると $N=10000$ 個の 'o' が決まるのは、だいたい $5 \times 10^6$ 弱あたりであることがわかる。
制約的にええ感じやん、となる。

あとは総和を $M$ にする調整である。あと一歩と思いきや、これも割と曲者。

$N$ の倍数であれば全要素に +1 または -1 することで等差数列を新規発生させずに総和を調整できるので、大幅に不足、または超過している場合は、それで調整する。
その上で、微調整を、末尾要素に足すことでおこなうのが楽そうではある。が、単純にはいかない。

$N=6,M=31$ を例に取ると、上記に従ってまず $6$ 個の要素を作ると $(0,1,3,4,9,10)$ となり、この総和は $27$、残り $4$。

ここで、末尾に4を足して調整してしまうと、$(0,1,3,4,9,14)$ となり、14は上記の表で 'x' となっている通り、$(4,9,14)$ が等差数列となってしまう。

確実に新たな等差数列の発生を防げるのは、$N$ 番目の要素が含まれるブロック（構成時にまとめてコピーした塊）の、さらにその次のブロックの1番目の要素である。
つまり、上記の例では、6番目の $10$ は $(9,10,12,13)$ のブロックに含まれ、さらにその次のブロックの開始は $27$ なので、末尾要素が（先頭からの相対的な値で） $27$ 以降なら確実に等差数列とならない、といえる。

よって “次のブロックの先頭要素” を $B$ として、$1～N-1$ 要素目を $\dfrac{B - 末尾要素}{N-1}$ だけ余計に下げておくと、末尾要素を $B$ 以上にできる。

Python3