AtCoder Beginner Contest 175 Virtual entry

AtCoder Beginner Contest 175 Virtual entry

I went to the mountains and didn't come back by the time, so I entered the virtual race. It's the first time I haven't been to ABC since I started AtCoder? The result was ABCD complete (TLE1) 75:49. . If it comes out, it was a rating up, Gussun

ABC175A - Rainy Season

Break through in 2 minutes. Just write.

S = input()

t = 0
result = 0
for c in S:
    if c == 'R':
        t += 1
    else:
        t = 0
    result = max(result, t)
print(result)

ABC175B - Making Triangle

It broke through in 7 minutes. First, I googled because I didn't know the condition of the length of the side where the triangle can be made. I missed "all different </ sub>". As a result, it took a long time to answer the question B.

from itertools import combinations

N, *L = map(int, open(0).read().split())

result = 0
for a, b, c in combinations(L, 3):
    if a == b or b == c or c == a:
        continue
    if a + b > c and b + c > a and c + a > b:
        result += 1
print(result)

ABC175C - Walking Takahashi

It broke through in 10 minutes. I knew immediately because I had solved similar problems in the past that I would just approach and then go back and forth, but it took a lot of time to make bugs here and there.

X, K, D = map(int, input().split())

if X > D:
    t = min(X // D, K)
    K -= t
    X -= t * D
else:
    t = min(-X // D, K)
    K -= t
    X += t * D

K %= 2

if K == 0:
    print(abs(X))
else:
    if abs(X + D) < abs(X - D):
        print(abs(X + D))
    else:
        print(abs(X - D))

ABC175D - Moving Piece

Break through in 52 minutes. TLE × 1. At first, I missed the "less than or equal to" of "K times or less", wrote the code with doubling, and wondered why the output example 1 was not 7. I noticed "the following" and reconsidered, I thought that O ( N </ i> 2 </ sup>) would not pass, and if loop detection is performed and the total in that loop is positive, the number of possible loops × I wrote it thinking that I should add the total in the loop, but TLE. I can not help it, so I rewrote it in Go language and it passed quickly.

package main

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

func max(x, y int) int {
	if x > y {
		return x
	}
	return y
}
func main() {
	defer flush()

	N := readInt()
	K := readInt()

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

	result := math.MinInt64
	for i := 0; i < N; i++ {
		p := P[i] - 1
		c := C[p]
		k := K - 1
		t := c
		for p != i && k != 0 {
			p = P[p] - 1
			c += C[p]
			t = max(t, c)
			k--
		}
		if k == 0 || c <= 0 {
			result = max(result, t)
			continue
		}
		l := K - k
		c = c * (K/l - 1)
		k = K - (K/l-1)*l
		t = c
		for k != 0 {
			p = P[p] - 1
			c += C[p]
			t = max(t, c)
			k--
		}
		result = max(result, t)
	}
	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
}

var stdoutWriter = bufio.NewWriter(os.Stdout)

func flush() {
	stdoutWriter.Flush()
}

func println(args ...interface{}) (int, error) {
	return fmt.Fprintln(stdoutWriter, args...)
}

Instead of rewriting it in Go, I just had to put it out in PyPy.

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

result = -float('inf')
for i in range(N):
    p = P[i] - 1
    c = C[p]
    k = K - 1
    t = c
    while p != i and k != 0:
        p = P[p] - 1
        c += C[p]
        t = max(t, c)
        k -= 1
    if k == 0 or c <= 0:
        result = max(result, t)
        continue
    l = K - k
    c = c * (K // l - 1)
    k = K - (K // l - 1) * l
    t = c
    while k != 0:
        p = P[p] - 1
        c += C[p]
        t = max(t, c)
        k -= 1
    result = max(result, t)
print(result)

ABC175E - Picking Goods

I couldn't break through. I thought it would be easy with DP without "However, you can only pick up up to 3 items in the same row of squares." There were quite a few people who skipped D and solved E. So, if you know something, isn't there a difference in difficulty?

Recommended Posts

AtCoder Beginner Contest 175 Virtual entry
AtCoder Beginner Contest 177
AtCoder Beginner Contest 179
AtCoder Beginner Contest 172
AtCoder Beginner Contest 180
AtCoder Beginner Contest 173
Atcoder Beginner Contest 153
AtCoder Beginner Contest 152 Review
AtCoder Beginner Contest 181 Note
AtCoder Beginner Contest 187 Note
AtCoder Beginner Contest 160 Review
AtCoder Beginner Contest 178 Review
AtCoder Beginner Contest 180 Note
AtCoder Beginner Contest 166 Review
AtCoder Beginner Contest 167 Review
AtCoder Beginner Contest 182 Note
AtCoder Beginner Contest 164 Review
AtCoder Beginner Contest 169 Review
AtCoder Beginner Contest 181 Review
AtCoder Beginner Contest 171 Review
AtCoder Beginner Contest 182 Review
AtCoder Beginner Contest 180 Review
AtCoder Beginner Contest 156 WriteUp
AtCoder Beginner Contest 177 Review
AtCoder Beginner Contest 168 Review
AtCoder Beginner Contest 179 Review
Solve AtCoder Beginner Contest 100-102
AtCoder Beginner Contest 167 Memorandum
AtCoder Beginner Contest 172 Review
AtCoder Beginner Contest 183 Note
AtCoder Beginner Contest 176 Review
AtCoder Beginner Contest 184 Note
AtCoder Beginner Contest 175 Review
AtCoder Beginner Contest 174 Review
AtCoder Beginner Contest 153 Review
AtCoder Beginner Contest 156 Review
AtCoder Beginner Contest 161 Review
AtCoder Beginner Contest 170 Review
AtCoder Beginner Contest 165 Review
AtCoder Beginner Contest 173 Review
AtCoder Beginner Contest 188 Note
AtCoder Beginner Contest 155 Review
AtCoder Beginner Contest 162 Review
AtCoder Beginner Contest 181 Participation Report
AtCoder Beginner Contest 161 Participation Report
AtCoder Beginner Contest 151 Participation Report
AtCoder Beginner Contest 176 Participation Report
AtCoder Beginner Contest 154 Participation Report
AtCoder Beginner Contest # 003 Participation Note
AtCoder Beginner Contest 166 Participation Report
AtCoder Beginner Contest 153 Participation Report
AtCoder Beginner Contest # 002 C Problem
AtCoder Beginner Contest 145 Participation Report
AtCoder Beginner Contest 184 Participation Report
AtCoder Beginner Contest 165 Participation Report
AtCoder Beginner Contest 160 Participation Report
AtCoder Beginner Contest 169 Participation Report
AtCoder Beginner Contest 178 Participation Report
AtCoder Beginner Contest 163 Participation Report
AtCoder Beginner Contest 159 Participation Report
AtCoder Beginner Contest 164 Participation Report