結果

問題 No.3254 Xor, Max and Sum
コンテスト
ユーザー ID 21712
提出日時 2026-05-02 13:48:12
言語 Go
(1.26.1)
コンパイル:
env GOCACHE=/tmp go build _filename_
実行:
./Main
結果
AC  
実行時間 25 ms / 2,000 ms
コード長 6,541 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 14,449 ms
コンパイル使用メモリ 289,720 KB
実行使用メモリ 6,400 KB
最終ジャッジ日時 2026-05-02 13:48:34
合計ジャッジ時間 16,839 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 48
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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)
}
0