[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.

• Es ist schade, dass ich die lokale Suchmethode, die ich in Einführung in den Heuristik-Wettbewerb gelernt habe, überhaupt nicht verwenden konnte.
• Einführung in den Heuristik-Wettbewerb hatte eine schlechte gierige Methode und bekam nicht viele Punkte, aber diesmal hatte ich das Gefühl, mein Bestes zu geben. War gut.

Zeitleiste

Unten finden Sie eine grobe Zeitleiste.

• [21:00] Ich habe das Video auf YouTube (Oi) gesehen.
• [21:07] Ah! Ich habe schnell auf https://atcoder.jp/ zugegriffen.
• [21:07] Ich nahm checker.zip und las es diagonal.
• [21:12] Nachdem ich die Problemstellung gelesen hatte, dachte ich, dass AC ohne irgendetwas durchgeführt werden würde, also reichte ich Folgendes ein und erhielt 5807500 Punkte.

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

    print(0)

• [21:25] Ich dachte, ich würde es zuerst in den meisten Farben malen, also reichte ich Folgendes ein und erhielt 49558075 Punkte.

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')

• [21:37] Wenn links und oben die gleiche Farbe haben, ist es meiner Meinung nach nicht notwendig, bereits zu malen. Reichen Sie also Folgendes ein und erhalten Sie 49649188 Punkte.

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')

• [21:42] Ich erkannte, dass ich alle Farben separat ausprobieren konnte und reichte Folgendes ein, um 49649427 Punkte zu erhalten. 99. Platz.

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')

• [22:13] Ich wollte eine Gemäldesimulation machen, also habe ich sie in die Go-Sprache portiert und abgeschlossen.
• [22:22] Senden Sie den Code mit der Gemäldesimulation und erhalten Sie 49654250 Punkte. 184. Platz.

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

• [23:00] Ich dachte, wenn Sie zuerst die weit voneinander entfernten Inseln verbinden, erhalten Sie bei jeder Verbindung 1 Punkt. Geben Sie einen zusätzlichen Pfad für die Verbindung ein und erhalten Sie 49654387 Punkte. 205. Platz.

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

• [23:15] Der Pfad zum Verbinden hat Vorrang vor der Spitze, und wenn die Spitze schlecht ist, befindet sie sich links, und wenn die linke Seite wahrscheinlich gewonnen wird, ist dies ein Verlust. Deshalb habe ich geschrieben, um zu punkten und zu entscheiden, ob ich nach oben oder links gehen soll, aber jetzt sehe ich es Aber aus irgendeinem Grund bekam ich mehr Punkte und 49656737 Punkte. 221. Platz.

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

• [00:07] Ich habe den obigen Fehler behoben und eingereicht und 49657497 Punkte erhalten. Wenn es keinen Fehler gab, bin ich um zwei Plätze auf den 238. Platz gestiegen.

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