AtCoder Chokudai Contest 005 Rapport de participation

Celui qui finit par participer en pensant qu'il ne devrait pas participer.

Le résultat a été de 49 656 737 points, 240e sur 528. Le code final a été soumis dans la langue Go ci-dessous.

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

Impressions, points de réflexion, etc.

-C'est dommage que je n'ai pas pu utiliser la méthode de recherche locale que j'ai apprise dans Introduction to Heuristics Contest.

Introduction to Heuristics Contest avait une mauvaise méthode gourmande et n'a pas obtenu beaucoup de points, mais cette fois j'avais l'impression de faire de mon mieux. C'était bien.

Chronologie

Voici un calendrier approximatif.

[21:00] J'ai regardé la vidéo sur YouTube (Oi).
[21:07] Ah! J'ai accédé à la hâte https://atcoder.jp/.
[21:07] J'ai pris checker.zip et l'ai lu en diagonale.
[21:12] Après avoir lu l'énoncé du problème, j'ai pensé qu'AC se ferait sans rien faire, j'ai donc soumis ce qui suit et j'ai obtenu 5807500 points.

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

    print(0)

[21:25] Je pensais que je le peindrais d'abord dans le plus grand nombre de couleurs, alors j'ai soumis ce qui suit et j'ai obtenu 49558075 points.

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] Si la gauche et le haut sont de la même couleur, je pense qu'il n'est pas nécessaire de peindre déjà, alors soumettez ce qui suit et obtenez 49649188 points.

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] J'ai réalisé que je pouvais essayer toutes les couleurs séparément et j'ai soumis ce qui suit pour obtenir 49649427 points: 99e place.

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] Je voulais faire une simulation de peinture, donc je l'ai portée en langue Go et l'ai terminée.
[22:22] Soumettez le code avec la simulation de peinture et obtenez 49654250 points, 184e place.

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] Je pensais que si vous connectez les îles éloignées les unes des autres en premier, vous obtiendrez 1 point à chaque connexion. Soumettez un chemin supplémentaire pour vous connecter et obtenez 49654387 points. 205e place.

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] Le chemin pour se connecter a la priorité sur le haut, et quand le haut est mauvais, il est à gauche, et quand la gauche est susceptible d'être gagnée, c'est une perte, alors j'ai écrit pour marquer et décider de monter ou de gauche, mais maintenant je le vois Mais cela ne fonctionne pas car il est buggé, mais quand je l'ai soumis pour une raison quelconque, les points ont augmenté et j'ai obtenu 49656737 points 221e place.

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] J'ai corrigé le bogue ci-dessus et l'ai soumis, et j'ai obtenu 49657497. S'il n'y avait pas de bogue, j'ai grimpé de deux places à la 238e place.

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