AtCoder Beginner Contest 147 参戦記

ABC147A - Blackjack

2分半で突破. 書くだけ.

A1, A2, A3 = map(int, input().split())

if sum([A1, A2, A3]) >= 22:
  print('bust')
else:
  print('win')

ABC147B - Palindrome-philia

2分で突破. 書くだけ.

S = input()

result = 0
for i in range(len(S) // 2):
  if S[i] != S[-(i + 1)]:
    result += 1
print(result)

ABC147D - Xor Sum 4

46分くらい?で突破. Cを提出したら WA3 で諦めてこっちに取り掛かったのでよく分からず. ビットごとに累積 XOR をするだけ. だけって言ってもコーディングは中々大変. Python で書いたら TLE になったので、Go で書き直した. % 1000000007 がある問題はできるだけ Python で書きたいのにね.

A_i のあるビットが0の場合、A_i+1～A_Nのあるビットが1の個数をかける、A_i のあるビットが1の場合、A_i+1～A_Nのあるビットが0の個数をかけることによって、個数の累積和が取ってあれば内側のシグマはループせずに計算できる. 制約より0≤A_i<2⁶⁰なので、ビットごとに60回処理すれば良い.

package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

func main() {
	const m = 1000000007

	N := readInt()
	A := make([]int, N)
	for i := 0; i < N; i++ {
		A[i] = readInt()
	}

	result := 0
	a := make([]int, N)
	bs := make([]int, N)
	for b := 0; b < 60; b++ {
		for i := 0; i < N; i++ {
			a[i] = (A[i] >> uint(b)) & 1
		}

		bs[N-1] = a[N-1]
		for i := N - 2; i > -1; i-- {
			bs[i] = bs[i+1] + a[i]
		}

		t := 0
		for i := 0; i < N-1; i++ {
			if a[i] == 0 {
				t += bs[i+1]
			} else {
				t += (N - (i + 1)) - bs[i+1]
			}
		}
		t %= m

		v := (1 << uint(b)) % m
		result += (t * v) % m
		result %= m
	}
	fmt.Println(result)
}

const (
	ioBufferSize = 1 * 1024 * 1024 // 1 MB
)

var stdinScanner = func() *bufio.Scanner {
	result := bufio.NewScanner(os.Stdin)
	result.Buffer(make([]byte, ioBufferSize), ioBufferSize)
	result.Split(bufio.ScanWords)
	return result
}()

func readString() string {
	stdinScanner.Scan()
	return stdinScanner.Text()
}

func readInt() int {
	result, err := strconv.Atoi(readString())
	if err != nil {
		panic(err)
	}
	return result
}

追記: 結局この計算は Ai のすべての組み合わせ(Ai 自身同士は含まない)の XOR の合計なので、Ai のあるビットの立っている数の合計を c とすると、Ai のあるビットが0であった場合により計算結果に立つビットの数は c、Ai のあるビットが1であった場合により計算結果に立つビットの数は N - c になるので、あるビットに関する計算結果は c * (N -c) のビットシフトした値になる. 結果として以下の計算で解ける.

N = int(input())
A = list(map(int, input().split()))

result = 0
for bit in range(60):
    m = 1 << bit
    c = sum(a & m for a in A) >> bit
    result += (c * (N - c)) << bit
    result %= 1000000007
print(result)

ABC147C - HonestOrUnkind2

35分くらい?で突破. N≤15 なので、全組み合わせやっても 2¹⁵ でしかなく、やるだけ. だけって言ってもコーディングは中々大変. 最初 for i in range(1, 2 ** N): が for i in range(1, 2 ** N - 1): になってて WA3 だった. D問題が終わった後に見直していたら気づいた.

N人の「正直者」、「不親切な人」のすべての組み合わせを生成し、正直者の証言が組み合わせに矛盾していないか確認する. 矛盾していない組み合わせの正直者の最大数が解答.
組み合わせは bit で表現している. Nビット用意し、1が立っていると正直者、0だと不親切な人. この組み合わせ状況と正直者の証言が矛盾しないか確認する.

N = int(input())

evidences = [[] for _ in range(N)]
for i in range(N):
    A = int(input())
    for _ in range(A):
        x, y = map(int, input().split())
        evidences[i].append((x - 1, y))

result = 0
for i in range(1, 2 ** N):
    consistent = True
    for j in range(N):
        if (i >> j) & 1 == 0:
            continue
        for x, y in evidences[j]:
            if (i >> x) & 1 != y:
                consistent = False
                break
        if not consistent:
            break
    if consistent:
        result = max(result, bin(i)[2:].count('1'))
print(result)

ABC147E - Balanced Path

突破できず. 貪欲法では駄目なのは分かるけど、じゃあどうすればいいというのが思いつかなかった. 3次元DPかー(解説を見て). 解説読んでもさっぱりわかりませんね.