[PYTHON] AtCoder Beginner Contest 152 Participation Report

AtCoder Beginner Contest 152 Participation Report

ABC152A - AC or WA

Break through in one and a half minutes. Just write.

N, M = map(int, input().split())

if N == M:
    print('Yes')
else:
    print('No')

ABC152B - Comparing Strings

Break through in 2 minutes. Just write.

a, b = map(int, input().split())

if a < b:
    print(str(a) * b)
else:
    print(str(b) * a)

ABC152C - Low Elements

Break through in 5 minutes. As expected, the double loop is TLE, so we need to carry around the current minimum value. We spent a little time understanding the subject.

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

result = 0
m = P[0]
for i in range(N):
    if P[i] <= m:
        result += 1
        m = P[i]
print(result)

ABC152D - Handstand 2

Break through in 26 minutes. It's not difficult if you can see that it's okay to loop N times. If you count the number by the combination of the beginning and the end, it will be one shot.

N = int(input())

t = [[0] * 10 for _ in range(10)]
for i in range(1, N + 1):
    s = str(i)
    t[int(s[0])][int(s[-1])] += 1

result = 0
for i in range(1, 10):
    for j in range(1, 10):
        result += t[i][j] * t[j][i]
print(result)

ABC152E - Flatten

Lost. TLE in a naive implementation that aggregates for the least common multiple.

Postscript: Implemented as explained.

package main

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

func mpow(x int, n int) int {
	result := 1
	for n != 0 {
		if n&1 == 1 {
			result *= x
			result %= 1000000007
		}
		x *= x
		x %= 1000000007
		n >>= 1
	}
	return result
}

func main() {
	maxA := 1000000

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

	sieve := make([]int, maxA+1)
	sieve[0] = -1
	sieve[1] = -1
	for i := 2; i <= maxA; i++ {
		if sieve[i] != 0 {
			continue
		}
		sieve[i] = i
		for j := i * i; j <= maxA; j += i {
			if sieve[j] == 0 {
				sieve[j] = i
			}
		}
	}

	lcmFactors := map[int]int{}
	for i := 0; i < N; i++ {
		t := map[int]int{}
		a := A[i]
		for a != 1 {
			t[sieve[a]]++
			a /= sieve[a]
		}
		for k, v := range t {
			if lcmFactors[k] < v {
				lcmFactors[k] = v
			}
		}
	}

	lcm := 1
	for k, v := range lcmFactors {
		for i := 0; i < v; i++ {
			lcm *= k
			lcm %= 1000000007
		}
	}

	result := 0
	for i := 0; i < N; i++ {
		result += lcm * mpow(A[i], 1000000007-2)
		result %= 1000000007
	}
	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
}