💬

ABC212 振り返りメモ

8 min read

ABC212

A問題からD問題まで。

ABC212A - Alloy

  • 素直に場合分けすればOK
  • 制約で 0 \le A, 0 \le B が保証されているので、単純に0<A0<Bの条件はわざわざ書かなくても良いと思う。
abc212a.go
package abc212

func AnswerABC212A(A, B int) string {
	if 0 < A && B == 0 {
		return "Gold"
	}

	if 0 < B && A == 0 {
		return "Silver"
	}

	return "Alloy"
}
abc212a_test.go
package abc212

import "testing"

func TestAnswerABC212A(t *testing.T) {
	type args struct {
		A int
		B int
	}
	tests := []struct {
		name string
		args args
		want string
	}{
		{"入力例1", args{A: 5, B: 5}, "Alloy"},
		{"入力例2", args{A: 100, B: 0}, "Gold"},
		{"入力例3", args{A: 0, B: 100}, "Silver"},
		{"入力例4", args{A: 100, B: 2}, "Alloy"},
	}
	for _, tt := range tests {
		t.Run(tt.name, func(t *testing.T) {
			if got := AnswerABC212A(tt.args.A, tt.args.B); got != tt.want {
				t.Errorf("AnswerABC212A() = %v, want %v", got, tt.want)
			}
		})
	}
}

ABC212B - Weak Password

  • ポイントは、 「0の次が9」の場合。
  • こういうのは、(x + 1) \mod 10 をとればいい感じに循環に対応できる。
  • ところで、4桁なので、Weakとなる数列は、かなり少ない。 なので、「Weakとなるパターンをすべて列挙して、そのパターンに該当するか」で判定してもいいと思う(こっちのほうが実装も楽かも?)
abc212b.go
package abc212

func AnswerABC212B(X1X2X3X4 string) string {
	isAllSame := true

	for i := 0; i < 3; i++ {
		if X1X2X3X4[i] != X1X2X3X4[i+1] {
			isAllSame = false
		}
	}

	isSequential := true

	for i := 0; i < 3; i++ {
		left, right := X1X2X3X4[i]-'0', X1X2X3X4[i+1]-'0'

		if (left+1)%10 != right {
			isSequential = false
		}
	}

	if isAllSame || isSequential {
		return "Weak"
	} else {
		return "Strong"
	}
}
abc212b_test.go
package abc212

import "testing"

func TestAnswerABC212B(t *testing.T) {
	type args struct {
		X1X2X3X4 string
	}
	tests := []struct {
		name string
		args args
		want string
	}{
		{"入力例1", args{X1X2X3X4: "7777"}, "Weak"},
		{"入力例2", args{X1X2X3X4: "0112"}, "Strong"},
		{"入力例3", args{X1X2X3X4: "9012"}, "Weak"},
	}
	for _, tt := range tests {
		t.Run(tt.name, func(t *testing.T) {
			if got := AnswerABC212B(tt.args.X1X2X3X4); got != tt.want {
				t.Errorf("AnswerABC212B() = %v, want %v", got, tt.want)
			}
		})
	}
}

ABC212C - Min Difference

  • 愚直にやるとO(4 * 10^{10})で間に合わない
  • 順番が関係ないのでとりあえずソートしてみる
  • 相方が来るまで待つようなイメージでそれぞれのindexをずらして比較する
  • 計算量
    • ソート: O(logN + logM)
    • indexずらし操作: O(N + M - 1) = O(N + M)

イメージ

3 4
3 1 4
8 5 9 2
# ソートする
A 1   3 4         
B   2     5    8 9
# 初期位置
  ↓
A 1   3 4         
B   2     5    8 9
    ↑
  ----↓
A 1   3 4         
B   2     5    8 9
    ↑
    ↓
A 1   3 4         
B   2     5    8 9
    ------↑
    --↓
1   3 4         
  2     5    8 9
        ↑
        範囲外なので終了(8,9は比較してなくても最小距離はわかるのでOK)
      --↓
1   3 4          
  2     5    8 9
        ↑

code

abc212c.go
package abc212

import (
	"math"
	"sort"
)

func AnswerABC212C(N, M int, A, B []int) int {
	sort.Ints(A)
	sort.Ints(B)

	idxA, idxB := 0, 0

	minDiff := math.MaxInt64

	for (idxA < N) && (idxB < M) {
		a, b := A[idxA], B[idxB]

		diff := absInt(a - b)

		minDiff = min(minDiff, diff)

		if a < b {
			idxA++
		} else {
			idxB++
		}
	}

	return minDiff
}

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

func absInt(n int) int {
	if 0 < n {
		return n
	} else {
		return -n
	}
}
abc212c_test.go
package abc212

import "testing"

func TestAnswerABC212C(t *testing.T) {
	type args struct {
		N int
		M int
		A []int
		B []int
	}
	tests := []struct {
		name string
		args args
		want int
	}{
		{
			"入力例1",
			args{
				N: 2,
				M: 2,
				A: []int{1, 6},
				B: []int{4, 9},
			},
			2,
		},
		{
			"入力例2",
			args{
				N: 1,
				M: 1,
				A: []int{10},
				B: []int{10},
			},
			0,
		},
		{
			"入力例3",
			args{
				N: 6,
				M: 8,
				A: []int{82, 76, 82, 82, 71, 70},
				B: []int{17, 39, 67, 2, 45, 35, 22, 24},
			},
			3,
		},
		{
			"オレオレサンプル",
			args{
				N: 3,
				M: 4,
				A: []int{3, 1, 4},
				B: []int{8, 5, 9, 2},
			},
			1,
		},
	}
	for _, tt := range tests {
		t.Run(tt.name, func(t *testing.T) {
			if got := AnswerABC212C(tt.args.N, tt.args.M, tt.args.A, tt.args.B); got != tt.want {
				t.Errorf("AnswerABC212C() = %v, want %v", got, tt.want)
			}
		})
	}
}

ABC212D - Querying Multiset

  • まず、キューを思いついたけど、高速に最小値を取り出す方法が思いつかなかった。
  • 「全体に加算する」は、1つの変数で管理すればOK
    • イメージは「古参ほど恩恵(+)を得るが、新参は恩恵が受けられない」って感じ
    • 出し入れするときに調整する
    • この「集合の全体に加算する」アイデアは色んな場所で使えそう

全体的な手順は@kyopro_friendsさんの説明が端的でわかりやすい

https://twitter.com/kyopro_friends/status/1421466894163316736
abc212d.go
package abc212

import (
	"container/heap"
	"strconv"
	"strings"
)

func AnswerABC212D(Q int, queries [][]int) string {
	h := make(IntHeap, 0, Q)
	chokin := 0

	out := make([]string, 0, Q)

	for _, query := range queries {
		p := query[0]

		switch p {
		case 1:
			// 新たに追加される値は、それまでの貯金の恩恵がないので差っ引く
			heap.Push(&h, query[1]-chokin)
		case 2:
			// 全体に加算は貯金で表現
			chokin += query[1]
		case 3:
			// 取り出すときは、貯金を適用する
			ball := heap.Pop(&h).(int) + chokin

			out = append(out, strconv.Itoa(ball))
		}
	}

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

// IntHeap https://pkg.go.dev/container/heap#example-package-PriorityQueue
type IntHeap []int

func (h IntHeap) Len() int {
	return len(h)
}

func (h IntHeap) Less(i, j int) bool {
	return h[i] < h[j]
}

func (h IntHeap) Swap(i, j int) {
	h[i], h[j] = h[j], h[i]
}

func (h *IntHeap) Push(x interface{}) {
	*h = append(*h, x.(int))
}

func (h *IntHeap) Pop() interface{} {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}
abc212d_test.go
package abc212

import "testing"

func TestAnswerABC212D(t *testing.T) {
	type args struct {
		Q       int
		queries [][]int
	}
	tests := []struct {
		name string
		args args
		want string
	}{
		{
			"2つ目を追加する前に加算が入るケース",
			args{
				Q: 5,
				queries: [][]int{
					{1, 2},
					{2, 3},
					{1, 7},
					{3},
					{3},
				},
			},
			"5\n7",
		},
		{
			"入力例1",
			args{
				Q: 5,
				queries: [][]int{
					{1, 3},
					{1, 5},
					{3},
					{2, 2},
					{3},
				},
			},
			"3\n7",
		},


		{
			"入力例2",
			args{
				Q: 6,
				queries: [][]int{
					{1, 1000000000},
					{2, 1000000000},
					{2, 1000000000},
					{2, 1000000000},
					{2, 1000000000},
					{3},
				},
			},
			"5000000000",
		},
	}
	for _, tt := range tests {
		t.Run(tt.name, func(t *testing.T) {
			if got := AnswerABC212D(tt.args.Q, tt.args.queries); got != tt.want {
				t.Errorf("AnswerABC212D() = %v, want %v", got, tt.want)
			}
		})
	}
}

Discussion

ログインするとコメントできます