Codeforces Round #563 (Div. 2)

バチャ。

３０分３完で２２００位でした…低い…

D通さないといけない回だったんですかね。リサブで減点されたことを加味しても悲しい順位でした。

codeforces.com

A. Ehab Fails to Be Thanos

全ての要素が一致するときだけ-1で、他は構築可能です。

簡単な例としてソートした状態があげられます

B. Ehab Is an Odd Person

問題：ai+ajが奇数のときswap可能である。辞書順最小にせよ

考察：

もし偶数と奇数どちらもあれば自由にソートできます。

そうでなければ1回もswapできません。

前者であればソートして、後者であればそのまま出力すればよいです

なぜ自由にソートできるかというと、偶数同士A,Bをswapするとき、ある奇数とABAの順でswapすればよいからです。

ここで2ペナ踏んだのが痛かったです。いやでもこれ普通に難しくないですか？

C. Ehab and a Special Coloring Problem

問題：a2~anについてi,jが互いに素ならai!=ajであるような数列で、max(ai)が最小なものを構築せよ

考察：

まず問題文がわかりづらいです。互いに素である組では共通の素因数を持ちません。

この組は2~nの素数の種類と同じだけになります。

2~nを素数判定したらTLEしました（O(N√N)）。2~nで未探索ならnを超えるまで倍数を探索していけばよいです。高々O(NlogN)です。

D. Ehab and the Expected XOR Problem

問題：1~2^nを使って、連続する部分列のXORが0かxにならないような整数列を構築せよ。

全くわからん

解説：

まずできあがった整数列Aの前からの累積XORの列Bを考えます。

部分列のXOR：bi^bj(i!=j)

となります。

したがってbはdistinctである必要があります。

またすでに出たbiについてbi^xも使えません。2^n未満の正の整数について貪欲に追加すればよいです。

ai=bi^bi-1などで答えが求まります

感想：

天才か。累積をとるのは典型なんですけど、構築に使えるとは思いませんでした。

部分列＝累積を2つfしたものっていう考えは常に出せるようにしたいです。

E. Ehab and the Expected GCD Problem

問題：nの順列を考える。前から1つずつgcdをとったものn個のうち、distinctな種類を最大化する順列の個数を求めよ

考察：

最大化するケースを考えてみます。

2^k、2^k-1と順に減る場合が最大になります

ここで2^k-1*3がn以下なら3を含む場合があります。

以下のようなDPを用います

DP[i][j][l]：

i番目まで定まったとき、2^(k-j)までgcdが減っていて、l：gcdが3の倍数かどうかを表します。

このDPをするにあたって、2^iの倍数かつ2^i+1の倍数でないようなn以下の整数の個数をそれぞれ求めます。

またその中で3の倍数である個数も求めておきます

遷移は以下の通りです。

DP[i+1][j][0]=DP[i][j][0]*(2^(k-j)の倍数で使ってないもの)+DP[i][j][1]*(2^(k-j)の倍数で3の倍数でないもの)

DP[i+1][j+1][0]=DP[i][j][0]*(2^(k-j-1)の倍数)

DP[i+1][j+1][1]=DP[i][j][1]*(2^(k-j-1)の倍数かつ3の倍数)

初期値はDP[0][0][0]=1、DP[0][1][1]=1or0です。

この遷移をしてDP[n][k]を求めればよいです

実装してないです。こんな適当な遷移考察じゃ無理です。頭こんがらがったのでやめました。