Codeforces Round #554 (Div. 2)

bqaya

問題：ｎ個の整数列Aとｍ個の整数列Bを１：１マッチングして、足して奇数になる組を最大化せよ

考察：

それぞれで奇数偶数の数を数えます。

奇数と偶数のマッチングしかないので、それぞれの小さいほうを足せばよいです。

問題：ある整数ｘが与えられる。これを以下の操作をして2^m-1にせよ

操作：k>=0で2^k-1をXORする。+1する。

考察：

まずXORで下位bitがすべて変わることから、上から決めるほうがよさそうです。

既に1のbitは変える必要がないので、一番上にある0から下を変えましょう

下k桁がすべて0か、1が混じるかで場合分けします。

前者の場合は一番上の0の1つ下をkにして、後者の場合は一番上の0をkとすればよいです

問題：整数a,bが与えられる。a+k,b+kのLCMを最小化するkを求めよ。

考察：

a<bとします。a+kとb+kのgcdはb-aの約数にしかならないので、そのような最小のkを全探索し、各回でLCMを愚直に求めました。

WA on test 8

問題：長さ2nの（）の対応が取れた文字列を作りたい。これを木の遷移で表すとする。色のついた辺同士が頂点を共通に持たないように、辺に色を塗る。色のついた辺を最大化せよ。

考察：

valueを（で+1、）で-1するものとします。対応が取れた文字列とは、すべての地点でvalueが0以上で、最後に0になるものです。

残りの試行で全てマイナスしなければ実現不可能

いまのvalueが0のとき

上では、マイナスするしかないです。下ではプラスするしかないです。それ以外ではどちらも可能です。

これをDPします。

このとき、1つ前の辺は1つしかないです。これが塗られているか塗られていないかで場合分けでき、状況は無差別です。

したがってDP配列を2つ持てば解くことができます。

遷移先が2つ

　　前が色あり：両方塗らない

　　前が色なし：片方だけ塗る

遷移先が2つ

　　前が色あり：塗らない

　　前が色なし：塗る

この貪欲で最適解が求まります。

なぜなら、もし2連続でわざと塗らない箇所を作ると、1つ減るかそのままです。

端点までの長さの偶奇で変わりますが、増えることはないです。

以上でO(N^2)で解くことができました。