とりあえずAtCoder Beginners Selectionをやってみた。
復習
印象に残ったり即時に解けなかったものについてメモする。今後は全部について復習してメモするとは限らない。
今回は初めてなので真面目にやってみた。
計算量を求めるのとアルゴリズムの正しさを保存量を使ったりして証明するのは即時できるようになりたい。
(大学受験の時の感覚を思い出して懐かしくなった)
ABC086A Product
偶奇判定でビット処理を不要な入力サイズでも使ったりしてみてた。
入力範囲が非負整数だったので問題がなかったけど、負数があるときは絶対値を求める必要がある。
1
2
3
4
5
|
if a&b&1 {
fmt.Println("Odd")
} else {
fmt.Println("Even")
}
|
負数対応版のビット処理。シフト演算のためにビット数も考慮する必要がでる。
1
2
3
4
5
6
|
var a, b int32
if (a^(a>>31)-(a>>31))&(b^(b>>31)-(b>>31))&1 {
fmt.Println("Odd")
} else {
fmt.Println("Even")
}
|
ABC081A - Placing Marbles
ビット数カウント(popcount)は2進数として取り込んでテーブルを準備する方法で書いた。
そのあとに-1すると最下位ビットだけシフトするに気づいてn&n-1 != 0を利用した数え上げを試した。
どうやらもっと早い方法があるらしい。
ビットを数える
最後のリンクは分割統治法として説明していてわかりやすい。
ABC081B - Shift only
重ね合わせて最小ビットを見つければ良いのだろうってことで入力値を |= でビットを重ねて最右で立っているビットを数えた。
1
2
3
4
5
6
7
8
9
10
11
12
|
func main() {
var n, a, result int
fmt.Scanf("%d", &n)
for ; n > 0; n-- {
fmt.Scanf("%d", &a)
result |= a
}
for ; result&1 == 0; result >>= 1 {
n++
}
fmt.Printf("%d\n", n)
}
|
線形探索を極める！ 〜 for 文で色んなことができることを知るとは少し違う回答だけど、こっちの方がわかりやすいと思う。
ABC088B - Card Game for Two
初めはbinary-heapを配列上に実装したけどGoのheapパッケージで書き換えてみた。
1
2
3
4
5
6
7
8
9
10
11
12
|
type intHeap struct {
sort.IntSlice
}
func (h *intHeap) Push(x interface{}) {
h.IntSlice = append(h.IntSlice, x.(int))
}
func (h *intHeap) Pop() interface{} {
item := ([]int)(h.IntSlice)[len(h.IntSlice)-1]
h.IntSlice = ([]int)(h.IntSlice)[0 : len(h.IntSlice)-1]
return &item
}
|
また int DESC な binary heap を書いたのでアルゴリズムの勉強メモにコピーして手直しした。
なんと append() を忘れていた。スライスにappend()を使わず要素を追加して index out of range runtime error で panic を起こしてしまった。
ABC085B - Kagami Mochi
入力集合を使い入力済みか判定しながら入力を受け付けた。特に他には思いつかず。
ABC085C - Otoshidama
初めは合計金額 Y について n 枚でかかるか動的計画法で求める方向で書いてみた。
時間がかかり過ぎたので枚数 N を使って枝狩りした。
それでも計算時間が足りなかった。
いま考えると、単純に2重ループで5000円, 1000円の組み合わせの合計額のマップを作って、1万円の枚数についてループで全探索すればよかった。
その時は1000円の枚数が単調減少するような方法で目標金額に近づくように10000円, 5000円を増やしていくように調整し続けるコードを書いた。10000円が単調減少するコードでも解決できると思う。
ABC049C::白昼夢 / Daydream
これは入力値をreverseしてやると簡単に解けることに気づかずにdream系が来たら先読みで確認するように愚直に書いてしまった。
先読みを頑張る貪欲法で解いている。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
func generated(input string) bool {
for len(input) > 0 {
switch {
case eraser(input):
input = consume("eraser", input)
case erase(input):
input = consume("erase", input)
case dream(input):
candidate := consume("dream", input)
switch {
case candidate == "", dream(candidate), eraser(candidate), erase(candidate):
input = candidate
case dreamer(input):
input = consume("dreamer", input)
default:
return false
}
default:
return false
}
}
return true
}
|
しかもマッチ判定を語彙ごとに別の関数にしててコードが無駄に長い。
(consumeの方では無駄な書き方してないのに。。)
playground/study-algorithm/atcoder/ABC049Cに別解を追加した。
反転すると直ぐに解けるってのは後ろから貪欲法を使えば良いということで別解として main.suffix.go として追加した。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
|
func main() {
var input string
fmt.Scanf("%s", &input)
if generated(input) {
fmt.Println("YES")
} else {
fmt.Println("NO")
}
}
func generated(input string) bool {
MATCHING:
for len(input) > 0 {
for _, p := range []string{"eraser", "erase", "dream", "dreamer"} {
if match(p, input) {
input = consume(p, input)
continue MATCHING
}
}
return false
}
return true
}
func consume(fixed, input string) string {
return input[0 : len(input)-len(fixed)]
}
func match(key, input string) bool {
return len(input) >= len(key) &&
input[len(input)-len(key):len(input)] == key
}
|
やらなかったけどDFS,BFSやDPで解ける。振り返ればそうよねって感じ。。
また、最近はGoを使ってなくてスライスの挙動を忘れていたのだけど復習になった。
なんにせよ忘れかけているGoとかの手練習になるし過去問を探しては解いていく。
特にABSの元になった記事などを書いているdrkenさんは丁寧な解説記事が沢山あり類題も紹介されていたので追っていくつもり。
