Finish Firststep 10 Problems of Atcoder

Posted on 2 mins read

過去問精選 10 問 .. - Qiitaからリンクされている過去問を解き終えた。一部で寄り道して時間がかかった。 (無理やり自力で解こうとしがちなのは性格もあるけど、成長速度的にはあまり良くない)

現在の状況はAtCoder Problems(user=masu_mi)にある。

よくある定番処理のメモをしておく。

大量の入力

入力の処理はテンプレがある。 特に大量の入力が続く場合、 bufio.Scanner を使わないと遅すぎる場合がある。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

var n int
fmt.Scan(&n)

sc := bufio.NewScanner(os.Stdin)
sc.Split(bufio.ScanWords)
for i := 0; i < n; i++ {
  sc.Scan()
  a, _ := strconv.Atoi(sc.Text())
  // ...
}

D問題とかで一度 fmt.Scan() をループで回したらそれだけで TLE(時間制限違反) で失敗したことがあった。 それ以降は上記のようなコードを書いている。システムコールは減らさないとならない。

ソート

ソートは頻発する。最初は練習もあって自分で書いてたけど、標準ライブラリがあるので利用させてもらったほうが賢いし安全。

1
2

list := make([]int, n)
sort.Sort(sort.Reverse(sort.IntSlice(list)))

二分探索

sort パッケージを利用すると二分探索ができる。 sort.Searchは第2引数の述語について「あるインデックスで真になる場合、以降の全てのインデックスで真になること」を前提に動く。 下の場合ではある値以下であるという条件が list[i] 以降の全て成立すると前提されている。 そのためリストはすでに単調減少としてソートされていて limit-rest 以下の最大数を探していると推察できる。

1
2
3
4
5
6

var v int
sort.Sort(sort.Reverse(sort.IntSlice(list)))
idx := sort.Search(len(list), func(i int) bool { return list[i] <= limit-rest })
if idx < len(list) {
  v = rest + list[idx]
}

ヒープ

最初は、勉強のために二分ヒープを書いたけど以降は標準ライブラリで済ませた。 sort.Interface に加えて Push(x interface{}), Pop() interface{} のサポートを満たす必要がある。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

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
}

func main() {
  h := &intHeap{}
  var tmp int
  for i := 0; i < n; i++ {
    fmt.Scanf("%d", &tmp)
    h.Push(tmp)
  }
  fmt.Printf("%d", *((heap.Pop(h)).(*int)))
}

グリッド準備

高さ H 幅 W のフィールド上で何かを計算したりする問題がある。 このようなグリッドの問題では座標が 1 で始まることが多い。 また上下左右といった局所的な関係を元に計算した値を利用することがある。 せっかく 1 はじまりなので 0, H+1 の部分を無害な値にで埋めておくと便利。

下みたいな感じで書いてる。

 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

const safeBlock = "."

func main() {
  var n, w int
  fmt.Scan(&n, &w)
  grid := createGrid(n, w)
}

func createGrid(n, w int) []string {
  grid := make([]string, h+2)
  wall := createWall(w)
  grid[0] = wall
  sc := bufio.NewScanner(os.Stdin)
  for i := 1; i <= h; i++ {
    sc.Scan()
    grid[i] = safeBlock + sc.Text() + safeBlock
  }
  grid[h+1] = wall
	return grid
}

func createWall(w int) string {
  buf := bytes.NewBuffer([]byte{})
  for i := 0; i < w+2; i++ {
    buf.WriteString(safeBlock)
  }
  return buf.String()
}

感想

あと、パリティとか保存量とかを考えるとすぐに解ける問題は楽しいし証明も楽しいと感じた。 自分はどうやら線形探索とかの探索手順を作るのに慣れてないようで、一部の問題で停止する安全な探索手順を作るのに時間がかかった。

簡単な問題だと探索しない解き方が先に出てくることが多く、貪欲法や数学的な変更と条件分岐だけで解答になったりした。長期的には良くないと思ったので解き直したりしていた。 ここは練習を重ねて、プログラム的に素直な解答と数学的に色々と弄った解答とが直ぐ思いつくようになりたい。

続けている間に、kumagiさんの影響かAtCoder熱が過熱気味になっていたっぽい。付け焼き刃で競プロやるより計算科学を勉強しろよって空気をtwitterから感じた。 タイミング悪く始めたばかりで肩身の狭いなぁとか思ってしまうけど仕方ない。 科学や学問が大事で、学んだり考察するのは楽しいのはとても同意だ。そしてバランスみながら勉強してる。

comments powered by Disqus