[PYTHON] Teilnahmebericht des AtCoder Chokudai Contest 005

Teilnahmebericht des AtCoder Chokudai Contest 005

Derjenige, der am Ende teilnimmt, während er denkt, dass er nicht teilnehmen sollte.

Das Ergebnis war 49.656.737 Punkte, 240. von 528 ACs. Der endgültige Code wurde in der folgenden Go-Sprache eingereicht.

package main

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

func min(x, y int) int {
	if x < y {
		return x
	}
	return y
}

func fill(d [][]byte, i, j int, x, y byte) {
	q := [][2]int{{i, j}}
	for len(q) != 0 {
		m, n := q[0][0], q[0][1]
		q = q[1:]
		d[m][n] = x
		if m > 0 {
			if d[m-1][n] == y {
				q = append(q, [2]int{m - 1, n})
			}
		}
		if m < N-1 {
			if d[m+1][n] == y {
				q = append(q, [2]int{m + 1, n})
			}
		}
		if n > 0 {
			if d[m][n-1] == y {
				q = append(q, [2]int{m, n - 1})
			}
		}
		if n < N-1 {
			if d[m][n+1] == y {
				q = append(q, [2]int{m, n + 1})
			}
		}
	}
}

//
var (
	N int
)

func main() {
	defer flush()

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

	S := make([]string, N)
	for i := 0; i < N; i++ {
		S[i] = readString()
	}

	d := make([][]byte, N)
	for i := 0; i < N; i++ {
		d[i] = make([]byte, N)
	}

	result := make([][]string, 0, K)
	for n := 1; n <= K; n++ {
		x := byte(n + '0')
		t := make([]string, 0, 10000)

		for i := 0; i < N; i++ {
			for j := 0; j < N; j++ {
				d[i][j] = S[i][j]
			}
		}

		for i := 1; i < N-1; i++ {
			for j := 1; j < N-1; j++ {
				if d[i][j] == x {
					continue
				}

				a := 0
				b := 0
				if d[i-1][j] != d[i][j] {
					a++
					if d[i-1][j] == d[i+1][j] {
						a++
					}
					if d[i-1][j] == d[i][j+1] {
						a++
					}
				} else if d[i][j-1] != d[i][j] {
					b++
					if d[i][j-1] == d[i+1][j] {
						b++
					}
					if d[i][j-1] == d[i][j+1] {
						b++
					}
				}

				if a == 0 && b == 0 {
					continue
				}

				var c byte
				if a >= b {
					c = d[i-1][j]
				} else {
					c = d[i][j-1]
				}
				t = append(t, fmt.Sprintf("%d %d %c", i+1, j+1, c))
				fill(d, i, j, c, d[i][j])
			}
		}

		for i := 0; i < N; i++ {
			for j := 0; j < N; j++ {
				if d[i][j] == x {
					continue
				}

				t = append(t, fmt.Sprintf("%d %d %c", i+1, j+1, x))
				fill(d, i, j, x, d[i][j])
			}
		}
		result = append(result, t)
	}

	best := math.MaxInt64
	for i := 0; i < K; i++ {
		best = min(best, len(result[i]))
	}

	bestIndex := -1
	for i := 0; i < K; i++ {
		if len(result[i]) == best {
			bestIndex = i
			break
		}
	}

	println(best)
	for i := 0; i < best; i++ {
		println(result[bestIndex][i])
	}
}

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

Eindrücke, Reflexionspunkte usw.

Zeitleiste

Unten finden Sie eine grobe Zeitleiste.

    id, N, K = map(int, input().split())
    S = [input() for _ in range(N)]

    print(0)
from collections import Counter

id, N, K = map(int, input().split())
S = [input() for _ in range(N)]

c = Counter()
for i in range(N):
    c.update(S[i])
x = c.most_common(1)[0][0]

result = []
for i in range(N):
    for j in range(N):
        if S[i][j] != x:
            result.append('%d %d %s' % (i + 1, j + 1, x))
print(len(result))
print(*result, sep='\n')
from collections import Counter

id, N, K = map(int, input().split())
S = [input() for _ in range(N)]

c = Counter()
for i in range(N):
    c.update(S[i])
x = c.most_common(1)[0][0]

result = []
for i in range(N):
    for j in range(N):
        if S[i][j] != x and (i == 0 or S[i][j] != S[i - 1][j]) and (j == 0 or S[i][j] != S[i][j - 1]):
            result.append('%d %d %s' % (i + 1, j + 1, x))
print(len(result))
print(*result, sep='\n')
id, N, K = map(int, input().split())
S = [input() for _ in range(N)]

result = []
for n in range(1, K + 1):
    x = str(n)
    t = []
    for i in range(N):
        for j in range(N):
            if S[i][j] != x and (i == 0 or S[i][j] != S[i - 1][j]) and (j == 0 or S[i][j] != S[i][j - 1]):
                t.append('%d %d %s' % (i + 1, j + 1, x))
    result.append(t)

best = min(len(result[i]) for i in range(K))
for i in range(K):
    if len(result[i]) == best:
        best_index = i
        break

print(len(result[best_index]))
print(*result[best_index], sep='\n')
package main

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

func min(x, y int) int {
	if x < y {
		return x
	}
	return y
}

func main() {
	defer flush()

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

	S := make([]string, N)
	for i := 0; i < N; i++ {
		S[i] = readString()
	}

	d := make([][]byte, N)
	for i := 0; i < N; i++ {
		d[i] = make([]byte, N)
	}

	result := make([][]string, 0, K)
	for n := 1; n <= K; n++ {
		x := byte(n + '0')
		t := make([]string, 0, 10000)

		for i := 0; i < N; i++ {
			for j := 0; j < N; j++ {
				d[i][j] = S[i][j]
			}
		}

		for i := 0; i < N; i++ {
			for j := 0; j < N; j++ {
				if d[i][j] != x {
					s := fmt.Sprintf("%d %d %c", i+1, j+1, x)
					t = append(t, s)
					y := d[i][j]
					q := [][2]int{[2]int{i, j}}
					for len(q) != 0 {
						m, n := q[0][0], q[0][1]
						q = q[1:]
						d[m][n] = x
						if m > 0 {
							if d[m-1][n] == y {
								q = append(q, [2]int{m - 1, n})
							}
						}
						if m < N-1 {
							if d[m+1][n] == y {
								q = append(q, [2]int{m + 1, n})
							}
						}
						if n > 0 {
							if d[m][n-1] == y {
								q = append(q, [2]int{m, n - 1})
							}
						}
						if n < N-1 {
							if d[m][n+1] == y {
								q = append(q, [2]int{m, n + 1})
							}
						}
					}
				}
			}
		}
		result = append(result, t)
	}

	best := math.MaxInt64
	for i := 0; i < K; i++ {
		best = min(best, len(result[i]))
	}

	bestIndex := -1
	for i := 0; i < K; i++ {
		if len(result[i]) == best {
			bestIndex = i
			break
		}
	}

	println(best)
	for i := 0; i < best; i++ {
		println(result[bestIndex][i])
	}
}

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...)
}
package main

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

func min(x, y int) int {
	if x < y {
		return x
	}
	return y
}

func fill(d [][]byte, i, j int, x, y byte) {
	q := [][2]int{{i, j}}
	for len(q) != 0 {
		m, n := q[0][0], q[0][1]
		q = q[1:]
		d[m][n] = x
		if m > 0 {
			if d[m-1][n] == y {
				q = append(q, [2]int{m - 1, n})
			}
		}
		if m < N-1 {
			if d[m+1][n] == y {
				q = append(q, [2]int{m + 1, n})
			}
		}
		if n > 0 {
			if d[m][n-1] == y {
				q = append(q, [2]int{m, n - 1})
			}
		}
		if n < N-1 {
			if d[m][n+1] == y {
				q = append(q, [2]int{m, n + 1})
			}
		}
	}
}

//
var (
	N int
)

func main() {
	defer flush()

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

	S := make([]string, N)
	for i := 0; i < N; i++ {
		S[i] = readString()
	}

	d := make([][]byte, N)
	for i := 0; i < N; i++ {
		d[i] = make([]byte, N)
	}

	result := make([][]string, 0, K)
	for n := 1; n <= K; n++ {
		x := byte(n + '0')
		t := make([]string, 0, 10000)

		for i := 0; i < N; i++ {
			for j := 0; j < N; j++ {
				d[i][j] = S[i][j]
			}
		}

		for i := 0; i < N; i++ {
			for j := 0; j < N; j++ {
				if d[i][j] != x {
					if i > 0 && d[i-1][j] != d[i][j] {
						s := fmt.Sprintf("%d %d %c", i+1, j+1, d[i-1][j])
						t = append(t, s)
						fill(d, i, j, d[i-1][j], d[i][j])
					} else if j > 0 && d[i][j-1] != d[i][j] {
						s := fmt.Sprintf("%d %d %c", i+1, j+1, d[i][j-1])
						t = append(t, s)
						fill(d, i, j, d[i][j-1], d[i][j])
					}
				}
			}
		}

		for i := 0; i < N; i++ {
			for j := 0; j < N; j++ {
				if d[i][j] != x {
					s := fmt.Sprintf("%d %d %c", i+1, j+1, x)
					t = append(t, s)
					fill(d, i, j, x, d[i][j])
				}
			}
		}
		result = append(result, t)
	}

	best := math.MaxInt64
	for i := 0; i < K; i++ {
		best = min(best, len(result[i]))
	}

	bestIndex := -1
	for i := 0; i < K; i++ {
		if len(result[i]) == best {
			bestIndex = i
			break
		}
	}

	println(best)
	for i := 0; i < best; i++ {
		println(result[bestIndex][i])
	}
}

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...)
}
package main

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

func min(x, y int) int {
	if x < y {
		return x
	}
	return y
}

func fill(d [][]byte, i, j int, x, y byte) {
	q := [][2]int{{i, j}}
	for len(q) != 0 {
		m, n := q[0][0], q[0][1]
		q = q[1:]
		d[m][n] = x
		if m > 0 {
			if d[m-1][n] == y {
				q = append(q, [2]int{m - 1, n})
			}
		}
		if m < N-1 {
			if d[m+1][n] == y {
				q = append(q, [2]int{m + 1, n})
			}
		}
		if n > 0 {
			if d[m][n-1] == y {
				q = append(q, [2]int{m, n - 1})
			}
		}
		if n < N-1 {
			if d[m][n+1] == y {
				q = append(q, [2]int{m, n + 1})
			}
		}
	}
}

//
var (
	N int
)

func main() {
	defer flush()

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

	S := make([]string, N)
	for i := 0; i < N; i++ {
		S[i] = readString()
	}

	d := make([][]byte, N)
	for i := 0; i < N; i++ {
		d[i] = make([]byte, N)
	}

	result := make([][]string, 0, K)
	for n := 1; n <= K; n++ {
		x := byte(n + '0')
		t := make([]string, 0, 10000)

		for i := 0; i < N; i++ {
			for j := 0; j < N; j++ {
				d[i][j] = S[i][j]
			}
		}

		for i := 1; i < N-1; i++ {
			for j := 1; j < N-1; j++ {
				if d[i][j] == x {
					continue
				}

				a := 0
				b := 0
				if d[i-1][j] != d[i][j] {
					a++
					if d[i-1][j] == d[i+1][j] {
						a++
					}
					if d[i-1][j] == d[i][j+1] {
						a++
					}
				} else if d[i][j-1] != d[i][j] {
					b++
					if d[i][j-1] == d[i+1][j] {
						b++
					}
					if d[i][j-1] == d[i][j+1] {
						b++
					}
				}

				if a == 0 && b == 0 {
					continue
				}

				var c byte
				if a >= b {
					c = d[i-1][j]
				} else {
					c = d[i][j-1]
				}
				t = append(t, fmt.Sprintf("%d %d %c", i+1, j+1, c))
				fill(d, i, j, c, d[i][j])
			}
		}

		for i := 0; i < N; i++ {
			for j := 0; j < N; j++ {
				if d[i][j] == x {
					continue
				}

				t = append(t, fmt.Sprintf("%d %d %c", i+1, j+1, x))
				fill(d, i, j, x, d[i][j])
			}
		}
		result = append(result, t)
	}

	best := math.MaxInt64
	for i := 0; i < K; i++ {
		best = min(best, len(result[i]))
	}

	bestIndex := -1
	for i := 0; i < K; i++ {
		if len(result[i]) == best {
			bestIndex = i
			break
		}
	}

	println(best)
	for i := 0; i < best; i++ {
		println(result[bestIndex][i])
	}
}

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...)
}
package main

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

func min(x, y int) int {
	if x < y {
		return x
	}
	return y
}

func fill(d [][]byte, i, j int, x, y byte) {
	q := [][2]int{{i, j}}
	for len(q) != 0 {
		m, n := q[0][0], q[0][1]
		q = q[1:]
		d[m][n] = x
		if m > 0 {
			if d[m-1][n] == y {
				q = append(q, [2]int{m - 1, n})
			}
		}
		if m < N-1 {
			if d[m+1][n] == y {
				q = append(q, [2]int{m + 1, n})
			}
		}
		if n > 0 {
			if d[m][n-1] == y {
				q = append(q, [2]int{m, n - 1})
			}
		}
		if n < N-1 {
			if d[m][n+1] == y {
				q = append(q, [2]int{m, n + 1})
			}
		}
	}
}

//
var (
	N int
)

func main() {
	defer flush()

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

	S := make([]string, N)
	for i := 0; i < N; i++ {
		S[i] = readString()
	}

	d := make([][]byte, N)
	for i := 0; i < N; i++ {
		d[i] = make([]byte, N)
	}

	result := make([][]string, 0, K)
	for n := 1; n <= K; n++ {
		x := byte(n + '0')
		t := make([]string, 0, 10000)

		for i := 0; i < N; i++ {
			for j := 0; j < N; j++ {
				d[i][j] = S[i][j]
			}
		}

		for i := 1; i < N-1; i++ {
			for j := 1; j < N-1; j++ {
				if d[i][j] == x {
					continue
				}

				a := 0
				b := 0
				if d[i-1][j] != d[i][j] {
					a++
					if d[i-1][j] == d[i+1][j] {
						a++
					}
					if d[i-1][j] == d[i][j+1] && d[i-1][j] != d[i-1][j+1] {
						a++
					}
				}
				if d[i][j-1] != d[i][j] {
					b++
					if d[i][j-1] == d[i+1][j] && d[i][j-1] != d[i+1][j-1] {
						b++
					}
					if d[i][j-1] == d[i][j+1] {
						b++
					}
				}

				if a == 0 && b == 0 {
					continue
				}

				var c byte
				if a >= b {
					c = d[i-1][j]
				} else {
					c = d[i][j-1]
				}
				t = append(t, fmt.Sprintf("%d %d %c", i+1, j+1, c))
				fill(d, i, j, c, d[i][j])
			}
		}

		for i := 0; i < N; i++ {
			for j := 0; j < N; j++ {
				if d[i][j] == x {
					continue
				}

				t = append(t, fmt.Sprintf("%d %d %c", i+1, j+1, x))
				fill(d, i, j, x, d[i][j])
			}
		}
		result = append(result, t)
	}

	best := math.MaxInt64
	for i := 0; i < K; i++ {
		best = min(best, len(result[i]))
	}

	bestIndex := -1
	for i := 0; i < K; i++ {
		if len(result[i]) == best {
			bestIndex = i
			break
		}
	}

	println(best)
	for i := 0; i < best; i++ {
		println(result[bestIndex][i])
	}
}

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

Recommended Posts

Teilnahmebericht des AtCoder Chokudai Contest 005
AtCoder Beginner Contest 181 Teilnahmebericht
AtCoder Beginner Contest 161 Teilnahmebericht
AtCoder Beginner Contest 151 Teilnahmebericht
AtCoder Beginner Contest 176 Teilnahmebericht
AtCoder Beginner Contest 154 Teilnahmebericht
AtCoder Grand Contest 041 Teilnahmebericht
AtCoder Beginner Contest 166 Teilnahmebericht
AtCoder Grand Contest 040 Teilnahmebericht
AtCoder Beginner Contest 153 Teilnahmebericht
AtCoder Beginner Contest 145 Teilnahmebericht
AtCoder Beginner Contest 184 Teilnahmebericht
AtCoder Beginner Contest 165 Teilnahmebericht
AtCoder Beginner Contest 169 Teilnahmebericht
AtCoder Beginner Contest 178 Teilnahmebericht
AtCoder Beginner Contest 163 Teilnahmebericht
AtCoder Beginner Contest 159 Teilnahmebericht
AtCoder Beginner Contest 164 Teilnahmebericht
AtCoder Regular Contest 105 Teilnahmebericht
AtCoder Beginner Contest 168 Teilnahmebericht
AtCoder Beginner Contest 150 Teilnahmebericht
AtCoder Beginner Contest 158 Teilnahmebericht
AtCoder Beginner Contest 180 Teilnahmebericht
AtCoder Regular Contest 104 Teilnahmebericht
AtCoder Beginner Contest 156 Teilnahmebericht
AtCoder Beginner Contest 162 Teilnahmebericht
AtCoder Beginner Contest 157 Teilnahmebericht
AtCoder Beginner Contest 167 Teilnahmebericht
AtCoder Beginner Contest 179 Teilnahmebericht
AtCoder Anfängerwettbewerb 182
AtCoder Anfängerwettbewerb 146 Teilnahmebericht
AtCoder Beginner Contest 152 Teilnahmebericht
AtCoder Beginner Contest 155 Teilnahmebericht
AtCoder Beginner Contest 174 Teilnahmebericht
AtCoder Beginner Contest 171 Teilnahmebericht
AtCoder Beginner Contest 149 Teilnahmebericht
AtCoder Anfängerwettbewerb 148 Teilnahmebericht
AtCoder Beginner Contest 170 Teilnahmebericht
AtCoder Grand Contest 047 Teilnahmebericht
AtCoder Beginner Contest 183 Teilnahmebericht
Teilnahmebericht des AtCoder HHKB Programmierwettbewerbs 2020
Teilnahmebericht des AtCoder Acing Programming Contest 2020
Teilnahmebericht des AtCoder Keyence Programming Contest 2020
Teilnahmebericht des AtCoder Panasonic Programming Contest 2020
Teilnahmebericht zum AtCoder Library Practice Contest (Python)
AtCoder Einführung in den Heuristik-Wettbewerbsbericht
AtCoder Judge System Update Testwettbewerb 202004 Teilnahmebericht
AtCoder Beginner Contest # 003 Teilnahmehinweis
Atcoder Anfängerwettbewerb 146 Teilnahme Tagebuch
Teilnahmebericht des AtCoder Sumitomo Mitsui Trust Bank Programmierwettbewerbs 2019
Teilnahmebericht des Programmierwettbewerbs 2020 der AtCoder Hitachi, Ltd.
AtCoder Anfängerwettbewerb 177
abc154 teilnahmebericht
AtCoder Anfängerwettbewerb 179
AtCoder Anfängerwettbewerb 172
AtCoder Anfängerwettbewerb 180
AtCoder Anfängerwettbewerb 173
Atcoder Anfänger Wettbewerb 153
AtCoder 3. Algorithmus Praktischer Test Teilnahmebericht