package main import . "fmt" func main() { var n,m int Scan(&n,&m) if n == 1 { Println(0) return } else if n % 2 == 0 { Println(n*m) return } c := n - 2 z := 0 x := m for i := 32; i >= 0; i-- { b := 1 << i if b <= m { z = b x = m^b break } } for i := 32; i >= 0; i-- { b := 1 << i if (m&b) == 0 && (z|b) <= m && (x|b) <= m { z |= b x |= b } } println(Sprintf("m=%b",m)) println(Sprintf("z=%b",z)) println(Sprintf("x=%b",x)) ans := x for c >= 2 { found := false x = m y := m for i := 32; !found && i >= 0; i-- { b1 := 1 << i if b1 > m || (m&b1) == 0 || (z&b1) != 0 || (z|b1) > m { continue } for j := i-1; !found && j >= 0; j-- { b2 := 1 << j if b2 > m || (m&b2) == 0 || (z&b2) != 0 || (z|b2) > m { continue } x = m^b1 y = m^b2 if (z|b1|b2) <= m { z |= b1|b2 found = true } } } if found { for i := 32; i >= 0; i-- { b := 1 << i if (m&b) == 0 && (x|b) <= m && (y|b) <= m { x |= b y |= b } } c -= 2 ans += x + y println(Sprintf("z=%b",z)) println(Sprintf("x=%b",x)) println(Sprintf("y=%b",y)) } else { break } } ans += z ans += m * c Println(ans) } func init() { check() } /* N=1 のとき 0 N が偶数の時 N*M N>=3 の奇数のとき M が N-1 個と 0 が 1個 では最適にならず サンプル3だけ参考にすると M が N-2 個と 残り2個で M 以上になる組み合わせ探す 1個を M の最上位ビットのみ もう1個を M の最上位ビット以外の部分 この2個と M とで共通 0 になるビットのうち2個に論理和しても M 以下になるビットを埋めればよい と考えたが、WA となり不十分 2個で最適な組み合わを探すではなく 3個で探す、4個で探すを実験で確認していった結果 いくつかの M において4個の組み合わせで最適が見つかることが判明 4個の各ビット状態を確認すると何らかの法則性があると予想でき M を変えて実験した結果の解法の予想 例えば M = 30 = 0b11110、 N は N >= 5 の奇数 M 3個と0 1個を初期状態として並べると 0b11110 0b11110 0b11110 0b00000 各ビット桁の1の総数が同じなら排他的論理和も加算和も変化はない ので、0b00000 に適当に1つビットを移動する 0b11110 0b11110 0b01110 0b10000 すると 0b01110 と 0b10000 の2個は M 未満となる この2個の最下位ビットは共通で 0 でありこの両方を 1 サンプル3だけ参考にすると 排他的論理和は 0 のまま加算和は 2 増えることとなる 0b11110 0b11110 0b01111 0b10001 このビットの移動により M 未満にすることで空きの最下位の 0 のビットを埋めることができたので 最下位が 0 ビットの 0b11110 を2個選びこれらの 1 になっている桁のビットのうちを 010001 の 0 になっている桁のビットへ移動する 0b11010 0b10110 0b01111 0b11101 移動によって 0b11010 と 0b10110 は M 未満になりこれらの最下位ビットに共通の 0 を確保できたので 1 で置き換えると排他的論理和に変化なく加算和をさらに 2 増やせる 0b11011 0b10111 0b01111 0b11101 結論としては 初期状態が 0b00000 のように 0 値になっているとこに桁のビットを移動することによって M 未満になる値を2個作り共通で 0 になっている桁のビットを 1 で埋めることによって排他的論理和を変えず加算和を増やせる 桁が多い場合や 0 の桁のビットが多い場合も同様にできるはずで その際に利用できる個数は4個とは限らずもっと多いかもしれない 2個ペアで作るので4個以上でも偶数個となる M 未満を作り出す 0 値の空いている 0 となっているビット桁の数にゆとりがある限り加算和を作れる N が十分に大きければ、ビットの移動させる桁は排他的論理和や加算和の関係から位置はどの桁からでもよさそう(?)、N が十分ではなく小さい場合は上位桁から移動したほうがよさそう(上位桁の 0 の共通ビットから埋められる?) 他の例 M = 0b1111101110011 N は N >= 9 の奇数 0b1111101110011 0b1111101110011 0b1111101110011 0b1111101110011 0b1111101110011 0b1111101110011 0b1111101110011 0b0000000000000 ↓ 0b1111101110011 0b1111101110011 0b1111101110011 0b1111101110011 0b1111101110011 0b1111101110011 0b0111101110011 ← ビット移動 0b1000000000000 ↓ 0b1111101110011 0b1111101110011 0b1111101110011 0b1111101110011 0b1111101110011 0b1111101110011 0b0111111111111 ← 共通 0 埋め 0b1000010001100 ← 共通 0 埋め ↓ 0b1111101110011 0b1111101110011 0b1111101110011 0b1111101110011 0b1101101110011 ← ビット移動 0b1011101110011 ← ビット移動 0b0111111111111 0b1110010001100 ↓ 0b1111101110011 0b1111101110011 0b1111101110011 0b1111101110011 0b1101111111111 ← 共通 0 埋め 0b1011111111111 ← 共通 0 埋め 0b0111111111111 0b1110010001100 ↓ 0b1111101110011 0b1111101110011 0b1111001110011 ← ビット移動 0b1110101110011 ← ビット移動 0b1101111111111 0b1011111111111 0b0111111111111 0b1111110001100 ↓ 0b1111101110011 0b1111101110011 0b1111011111111 ← 共通 0 埋め 0b1110111111111 ← 共通 0 埋め 0b1101111111111 0b1011111111111 0b0111111111111 0b1111110001100 ↓ 0b1111101010011 ← ビット移動 0b1111100110011 ← ビット移動 0b1111011111111 0b1110111111111 0b1101111111111 0b1011111111111 0b0111111111111 0b1111111101100 ↓ 0b1111101110011 ← 参考 M 0b1111101011111 ← 共通 0 埋め 下位2個のみ ( M 未満が必要 ) 0b1111100111111 ← 共通 0 埋め 下位2個のみ ( M 未満が必要 ) 0b1111011111111 0b1110111111111 0b1101111111111 0b1011111111111 0b0111111111111 0b1111111101100 このケースではこれ以上の共通 0 埋めを作れないので終わり */ func check() { const T int = 127 - 16 - 2 - 1 tmp := T*3 println("T=",T) println(Sprintf("%b", T)) println(tmp) var ii,jj,kk,ll int for i := T; i >= 0; i-- { for j := i; j >= 0; j-- { for k :=j; k >= 0; k-- { for l:=k; l >= 0; l-- { if (i^j^k^l^T)== 0 && (i+j+k+l)> tmp { tmp = i+j+k+l ii,jj,kk,ll=i,j,k,l } } } } } println(ii,jj,kk,ll) println(Sprintf("%b", ii)) println(Sprintf("%b", jj)) println(Sprintf("%b", kk)) println(Sprintf("%b", ll)) println(tmp) println(tmp+T) }