ランチタイムの競プロもくもく会

posts/2019-11-18diary

火曜日のランチタイムに競プロもくもく会というものをやっていて、社内向けのバーチャルコンテストをやったりしている。
いま競プロより優先順位高い事柄が多いのでここが唯一触れる時間になってる。

これまで社内バーチャルコンテストで出題された問題をいくつかやったのでせっかくだし残しておく。

A - Add Sub Mul

単純にadd, sub, mulを計算してその最大値を出力してみたらどうですかって問題。可変長引数を取れるmax関数があると便利だけどないので書く。
最初、max関数内で使ってる変数maxをvar max intで宣言してて、これは0になるからWAってしまった。。

package main

import "fmt"

func maini() {
	var a, b int
	fmt.Scan(&a, &b)

	add := a + b
	sub := a - b
	mul := a * b

	fmt.Println(max(add, sub, mul))
}

func max(args ...int) int {
	max := -100000000
	for _, v := range args {
		if max < v {
			max = v
		}
	}
	return max
}

B - Cut and Count

200点にしてはむずかしい気がする。とはいえ、愚直に分割した文字列同士で共通してる文字を数えてみたらどうですかって問題。
containsみたいなものがなかったので書いておく。

Rubyだとかなりかっこよく書けそう。

package main

import (
	"fmt"
	"strings"
)

func main() {
	var n int
	var s string
	fmt.Scan(&n)
	fmt.Scan(&s)

	max := 0
	for i := 1; i < n; i++ {
		lhs := strings.Split(s[0:i], "")
		rhs := strings.Split(s[i:n], "")

		memo := make(map[string]int)
		count := 0
		for _, ss := range lhs {
			if contains(rhs, ss) {
				_, ok := memo[ss]
				if !ok {
					memo[ss] = 1
					count++
				}
			}
		}
		if max < count {
			max = count
		}
	}

	fmt.Println(max)
}

func contains(arr []string, str string) bool {
	for _, e := range arr {
		if e == str {
			return true
		}
	}
	return false
}

初期状態で先頭の人がリーダーだった時、2人目以上の列の中にいる「東を向いた人たち」は向きを変えないといけない。
次に2人目からみていって、その人が東を向いてるか西を向いてるかで、すでに数え上げたものから差し引く必要があるか、そのままでいいかが決まる。
さらにひとつ前の人も東西どちらを向いているかによって、向きを変える必要があるのかどうかが分かる。つまり初期状態とi、i + 1、i - 1番目によって答えが求まるのでDPっぽく書いてはどうですかという問題。

ここでもまた補助的なmin関数を書いた。こういう細かいところを自分で書かないといけないのが面倒といえばめんどう。

package main

import "fmt"

func main() {
	var n int
	var s string
	fmt.Scan(&n)
	fmt.Scan(&s)

	// memo[i]は、i人目をリーダーとして選んだ時の、向く方向を変える必要がある人数
	memo := make([]int, n)

	// 初期値として2人目以降のEの数を数える
	for i := 1; i < n; i++ {
		if s[i] == 'E' {
			memo[0]++
		}
	}

	for i := 1; i < n; i++ {
		if s[i] == 'E' {
			memo[i] = memo[i-1] - 1
		} else {
			memo[i] = memo[i-1]
		}

		if s[i-1] == 'W' {
			memo[i]++
		}
	}

	fmt.Println(min(memo))
}

func min(arr []int) int {
	min := 100000000
	for _, v := range arr {
		if v < min {
			min = v
		}
	}
	return min
}

D - Xor Sum 2

500点問題なのでむずかしい（実装だけみると簡単そうだけど……）。
ある数列の中で、総和とxorが同じになる部分列はいくつありますかって問題。

和とxorが一致しないのはどんなとき？＝繰り上がりがあるとき、ってことに気づけば区間の特徴がわかって、尺取り法が使えるねってなる。
でも尺取り法は苦手。なんか適当に書いて適当にあってるって感覚。

package main

import "fmt"

func main() {
	var n int
	fmt.Scan(&n)
	an := make([]int64, n)
	for i := 0; i < n; i++ {
		fmt.Scan(&an[i])
	}

	// 和とxorが同じになる部分列の数
	// じゃあどういう時に和とxorが一致しない？
	// => 繰り上がりが発生するとき
	// 例えば{4, 5}のとき、
	// sum：100 + 101 = 1001 = 9(10進数)
	// xor：100 xor 101 = 001 = 1(10進数)
	// つまり、和で繰り上がりが発生するときはダメ
	// 繰り上がりが発生するのは、各桁のビットが立ってる箇所が2つ以上あるとき
	// 和だと繰り上がるはずが、xorだと繰り上がらずに消されてしまうため
	// この範囲を数える
	// この区間にはどういう特徴があるか？
	// 区間が伸びれば伸びるほどダメになる可能性が高いし、
	// ある区間がダメなら、左端が同じでそれより長い区間は当然だめ(ビットの数が増えるから)
	// この区間は尺取り法で求める

	var ans, right int
	var sum int64
	for left := 0; left < n; left++ {
		for right < n && (sum+an[right]) == (sum^an[right]) {
			sum += an[right]
			right++
		}

		ans += right - left

		if right == left {
			right++
		} else {
			sum -= an[left]
		}
	}

	fmt.Println(ans)
}

B - Exponential

愚直に全探索できる。intを渡せるmax関数とpow関数があると便利。

package main

import (
	"fmt"
	"math"
)

func main() {
	var x int
	fmt.Scan(&x)

	sqrt := int(math.Sqrt(float64(x)))

	ans := 1
	for i := 2; i <= sqrt; i++ {
		for j := 1; j < 10; j++ {
			tmp := pow(i, j)
			if tmp > x {
				break
			}
			ans = max(ans, tmp)
		}
	}
	fmt.Println(ans)
}

func max(x, y int) int {
	return int(math.Max(float64(x), float64(y)))
}

func pow(x, y int) int {
	return int(math.Pow(float64(x), float64(y)))
}

C - Train Ticket

個々の要素について「あり」「なし」とか、「取る」「取らない」とかみたいな$$2 ^ n$$を全探索したい気持ちのときにはビット全探索が便利。
その名の通り0と1のビットを「取る」「取らない」の状態に見立てて扱う。
部分集合の列挙にも使える。

今回は、ABCDに演算子が入るスキマは3つあるので、この3つのスキマがそれぞれ「+」なのか「-」なのかを01で表現する。
Rubyだと[0, 1].repeated_permutation(len)で01のビット配列が生成できるのですごく便利。

Go1.6だとシフト演算するときのシフト量n(3 >> n)はuintじゃないとダメみたい。Go1.13からはintでよくなったらしい。

package main

import "fmt"

// abcdに演算子が入る箇所は3箇所ある
// その3箇所それぞれについて'+'か'-'を入れてみて実際に計算して7になるかどうか調べる
// それぞれについて「+」「-」の2つの状態を表すのには01つまりバイナリで表す
// 一般化すると、ある要素について「あり」「なし」とかの2つの状態を表したいときがある
// N個のものを「取る」「取らない」とかの、2^Nを表すもの
// この全探索を簡単に行えるのがいわゆるビット全探索
// Go(1.6)だとビットシフトするときにuintじゃないとCEになる。。
func main() {
	var abcd string
	fmt.Scan(&abcd)

	len := 3
	count := 0
	for bit := 0; bit < (1 << uint(len)); bit++ {
		count++
		exp := abcd[0:1]
		eval := int(abcd[0] - '0')
		for i := 0; i < len; i++ {
			literal := abcd[i+1 : i+2]
			value := int(abcd[i+1] - '0')
			if (1 & (bit >> uint(i))) == 1 {
				exp += "+" + literal
				eval += value
			} else {
				exp += "-" + abcd[i+1:i+2]
				eval -= value
			}
		}

		if eval == 7 {
			fmt.Printf("%s=7\n", exp)
			return
		}
	}
}

Golangは文字列をどうこうしようとする時に必ず詰まってしまう……。ちゃんと覚えないとなあ〜。