The one who ends up participating while thinking that he shouldn't participate.
The result was 49,656,737 points, 240th out of 528 ACs. The final code was submitted in Go language below.
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...)
}
-It's a pity that I couldn't use the local search method I learned in Introduction to Heuristics Contest at all. -Introduction to Heuristics Contest had a bad greedy algorithm and didn't get much points, but this time I felt like I was doing my best. Was good.
Below is a rough timeline.
-[21:00] I watched the video on YouTube (ぉ). -[21:07] Ah! I hurriedly accessed https://atcoder.jp/. -[21:07] I picked up checker.zip and read it diagonally. -[21:12] After reading the problem statement, I thought that AC would be done without doing anything, so I submitted the following and got 5807500 points.
id, N, K = map(int, input().split())
S = [input() for _ in range(N)]
print(0)
-[21:25] I thought I'd paint it in the most colors first, so I submitted the following and got 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] If the left and top are the same color, I think it is not necessary to paint already, so submit the following and get 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] I realized that I could try all colors separately, so I submitted the following and got 49649427 points. 99th 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] I wanted to do a painting simulation, so I ported it to the Go language and completed it. -[22:22] Submit the code with the painting simulation and get 49654250 points. 184th 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] I thought that if you connect the islands that are far apart first, you will get 1 point each time you connect. Add the connecting pass and submit it, and get 49654387 points. 205th 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] The path to connect is given priority to the top, and when the top is bad, it is on the left, and when the left is likely to be gained, it is a loss, so I wrote to score and decide whether it is top or left, but now I see it But it is not working because it is buggy. But for some reason, I got more points and got 49656737 points. 221st 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] I fixed the above bug and submitted it, and got 49657497 points. If there was no bug, I went up two and was 238th.
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