💬
ABC212 振り返りメモ
ABC212
A問題からD問題まで。
ABC212A - Alloy
- 素直に場合分けすればOK
- 制約で
0 \le A, 0 \le B 0<A 0<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
- まず、キューを思いついたけど、高速に最小値を取り出す方法が思いつかなかった。
- 優先度付きキューを使うのがバッチリ！
- 今回の優先度は小さい順でOK
- Goの場合
container/heap.Interface.Less()で調整すればいい - Pythonなら、
heapqがデフォルトで小さい順なのでそのまま使えて楽
- Goの場合
- 数字の小ささがそのまま優先度になるので、単純なヒープで十分
- わざわざPriorityQueueを実装したりしなくてよい感じ
- 数字じゃなくてなにかの名前とか
- 「全体に加算する」は、1つの変数で管理すればOK
- イメージは「古参ほど恩恵(+)を得るが、新参は恩恵が受けられない」って感じ
- 出し入れするときに調整する
- この「集合の全体に加算する」アイデアは色んな場所で使えそう
全体的な手順は@kyopro_friendsさんの説明が端的でわかりやすい
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