Zenn
💬

ABC213 振り返りメモ

2021/08/17に公開
Golang
AtCoder
tech

ABC213

問題 - AtCoder Beginner Contest 213

A問題からC問題まで。

ABC213A - Bitwise Exclusive Or

  • A \ xor \ C = B ⇔ C = A \ xor \ b に気づくことができれば1行でおわり
    • まず、A + C = B ⇔ A + C - A = B - A ⇔ C = B - A というのはわかる。
    • 要は、両辺に-Aを加算すれば、Cが求められる
    • で、A \ xor \ A = 0 なので、結局、B \ xor \ A で C が求まるという寸法
  • xorの性質に気づけなかったので全探索で解いた
abc213a.go
package abc213

func AnswerABC213A(A, B int) int {
	for i := 1; i <= 255; i++ {
		if A^i == B {
			return i
		}
	}

	return 0
}
abc213a_test.go
package abc213

import "testing"

func TestAnswerABC213A(t *testing.T) {
	type args struct {
		A int
		B int
	}
	tests := []struct {
		name string
		args args
		want int
	}{
		{"入力例1", args{A: 3, B: 6}, 5},
		{"入力例2", args{A: 10, B: 12}, 6},
	}
	for _, tt := range tests {
		t.Run(tt.name, func(t *testing.T) {
			if got := AnswerABC213A(tt.args.A, tt.args.B); got != tt.want {
				t.Errorf("AnswerABC213A() = %v, want %v", got, tt.want)
			}
		})
	}
}

ABC213B - Booby Prize

  • コンポジット型をソートする問題
  • sort.Stableのインターフェイスに合わせると冗長になりがち
  • sort.Sliceにするほうが記述はスッキリ
  • 独自のstructじゃなくて、[]intでもいいと思うけど、混乱するのでやっぱり、自分で定義したい
abc213b_1.go
package abc213

import (
	"sort"
)

// AnswerABC213B1 Stable Sortにするパターン
func AnswerABC213B1(N int, A []int) int {
	users := make(Users, N)

	for i := 0; i < N; i++ {
		users[i] = User{
			Id:    i + 1,
			Score: A[i],
		}
	}

	sort.Stable(users)

	return users[N-2].Id
}

type User struct {
	Id    int
	Score int
}

type Users []User

func (us Users) Len() int {
	return len(us)
}

func (us Users) Less(i, j int) bool {
	// Score昇順にソートする
	return us[i].Score < us[j].Score
}

func (us Users) Swap(i, j int) {
	us[i], us[j] = us[j], us[i]
}
abc213b_2.go
package abc213

import "sort"

func AnswerABC213B2(N int, A []int) int {
	type player struct {
		Id    int
		Score int
	}
	players := make([]player, N)

	for i := 0; i < N; i++ {
		players[i] = player{Id: i + 1, Score: A[i]}
	}

	sort.Slice(players, func(i, j int) bool {
		return players[i].Score < players[j].Score
	})

	return players[N-2].Id
}
abc213b_1_test.go
package abc213

import "testing"

func TestAnswerABC213B1(t *testing.T) {
	type args struct {
		N int
		A []int
	}
	tests := []struct {
		name string
		args args
		want int
	}{
		{"入力例1", args{N: 6, A: []int{1, 123, 12345, 12, 1234, 123456}}, 3},
		{"入力例2", args{N: 5, A: []int{3, 1, 4, 15, 9}}, 5},
	}
	for _, tt := range tests {
		t.Run(tt.name, func(t *testing.T) {
			if got := AnswerABC213B1(tt.args.N, tt.args.A); got != tt.want {
				t.Errorf("AnswerABC213B1() = %v, want %v", got, tt.want)
			}
		})
	}
}

ABC213C - Reorder Cards

  • MEMO
    • 変換テーブルで一気に処理するイメージでO(N)
    • 座標を変換していくイメージ
    • iとjは独立に考えられる
    • 愚直シミュレーションは、HとWが大きすぎて無理
    • コンテスト時は謎のやり方でAC
abc213c.go
package abc213

import (
	"fmt"
	"sort"
	"strings"
)

func AnswerABC213C2(H, W, N int, AB [][]int) string {
	bucketA := make(map[int]int)
	bucketB := make(map[int]int)
	for i := 0; i < N; i++ {
		a := AB[i][0]
		bucketA[a] = 1

		b := AB[i][1]
		bucketB[b] = 1
	}

	uniqueA := make([]int, 0, N)
	uniqueB := make([]int, 0, N)
	for a := range bucketA {
		uniqueA = append(uniqueA, a)
	}
	for b := range bucketB {
		uniqueB = append(uniqueB, b)
	}
	sort.Ints(uniqueA)
	sort.Ints(uniqueB)

	mapA := make(map[int]int)
	mapB := make(map[int]int)

	for i, a := range uniqueA {
		mapA[a] = i + 1
	}
	for i, b := range uniqueB {
		mapB[b] = i + 1
	}

	out := make([]string, N)
	for i := 0; i < N; i++ {
		a, b := AB[i][0], AB[i][1]

		out[i] = fmt.Sprintf("%d %d", mapA[a], mapB[b])
	}

	return strings.Join(out, "\n")
}

Discussion