AtCoder 版！蟻本 (初級編)
Go言語：文法基礎まとめ
【初級編】Go言語を始める方のための落とし穴、問題の解決方法やよくある間違い
- 一気に解こうとしないこと
- 一つずつ解ける問題の幅を上げていくこと
- 時間制限を設けること
155コンテスト復習
155コンテスト
AtCoder Beginner Contest 152 C
AtCoder Beginner Contest 154 D
累積和を何も考えずに書けるようにする！ - Qiita Golangを用いた様々な計算の高速化 - Qiita
下記コンテストの復習 AtCoder Beginner Contest 154
計算量を考えていなかった。 回答は出せていたのだが、計算量を考慮していなかったので、間違いとなった。 しかしかなり良い気づき。
# 解説
# https://img.atcoder.jp/abc154/editorial.pdf
C: Distinct
単純に全ての 2 つの整数の組に関してループで回し等しいか判定する場合、計算量が O(N2) となり間に合いません。
ところが、与えられた整数列に等しい値がある場合、この整数列をソートすると隣接する場所にこれらの値が集まることになります。
そのため、一度与えられた数列をソートすると、全ての隣接する 2 項を比較し、等しい値がなければ YES で、等しい値があれば NO です。
コンテスト参加
AtCoder Beginner Contest 154
# https://detail.chiebukuro.yahoo.co.jp/qa/question_detail/q1487006889
①1÷3=0あまり1
②3÷5=0あまり3
aとbの最大公約数 →bとrの最大公約数
# https://mathtrain.jp/euclid
390 を 273 で割ると，商が 1 で余りが 117 です：
390=273⋅1+117
「390 と 273 の最大公約数」
＝「273 と 117 の最大公約数」
次に，273 を 117 で割ると、273=117⋅2+39
「273 と 117 の最大公約数」
＝「117 と 39 の最大公約数」
// 以下のように「i+1」を使用すると、
for i := 0; i < len(A); i++ {
intervals = append(intervals, A[i+1]-A[i])
fmt.Println(i)
}
// こんな実装方法がある
for i := 1; i < len(A); i++ {
intervals = append(intervals, A[i]-A[i-1])
fmt.Println(i)
}sc := bufio.NewScanner(os.Stdin)
sc.Split(bufio.ScanWords)
A := make([]int, N)
for i := range A {
A[i] = nextInt(sc)
}mapは、
Atcoder abc109_a
Atcoder abc109_b
Atcoder abc153 e
プログラミングコンテストでの動的計画法
典型的な DP (動的計画法) のパターンを整理 Part 1 ～ ナップサック DP 編 ～
動的計画法（Dynamic Programming）をサルでも分かるように説明する - その１（フィボナッチ数列）
DP法と呼ばれる。 全探索をさらに効率よく実装できる。
- トップダウン：メモ化再帰、メモ化
- ボトムアップ：分割統治法、漸化式ループ
// 2の8乗
fmt.Println(math.Pow(2,8)) // 256BFSのアルゴリズム解くよりも、問題をより多く解いていこう
なぜ、 'o'の時に、falseを返すのか (031/002_main.go)
Atcoder dfs
https://atcoder.jp/contests/arc031/submissions/7030599
https://atcoder.jp/contests/arc031/submissions/9643970
1文字ずつ取り出すことができる
String と Rune
DFS (深さ優先探索) 超入門！ 〜 グラフ・アルゴリズムの世界への入口 〜【後編】
明日やること： https://qiita.com/drken/items/4a7869c5e304883f539b
- スタートの座標、ゴールの座標を用意してあげる。
- 迷路の位置を示す配列が、文字列
sと一致 → スタートの座標として値を更新。 - 迷路の位置を示す配列が、文字列
gと一致 → ゴールの座標として値を更新。 - DFS実行
- DFSで再帰的にTrueになるまで実行する
【初級編】Go言語を始める方のための落とし穴、問題の解決方法やよくある間違い
var test [][]byte
test = make([][]byte, h)
fmt.Println(test)
// [[] [] [] []]
var test []byte
test = make([]byte, h)
fmt.Println(test)
// 4 5- 最初のあたいは、fmt.Scanで受け取る
- 次にfor文の中で、fmt.Scan()を回す
例えばビット bit に i 番目のフラグが立っているかどうかは if ((bit>>i) & 1) と書くこともできます
ビット演算 (bit 演算) の使い方を総特集！ 〜 マスクビットから bit DP まで 〜
n個の要素からなる集合 {0,1,…,n−10,1,…,n−1} の部分集合をすべて調べ上げる手法のことです
// これがbit全検索の型
for bit := 0; bit < (1 << uint64(n)); bit++ {
// fmt.Println(bit) // 3を入力した場合、0~7の計8つが出力される。
for i := 0; i < n; i++ {
// fmt.Println(i) // 3を入力した場合、0, 1, 2のセットが計8つが出力される。
if (bit>>uint64(i))&1 == 1 { // bitsのi個目の要素の状態がonかどうかチェック(ここは問題によって条件を変化させる)
}
}
}(1<<n)は2^nと覚える
bit全探索について簡単にまとめる
【Golang】Goでbit全探索をしよう
シフト演算子は左側のオペランドを右側のオペランド分だけ左または右にシフトします。 左オペランドには int, uint, long, ulong のみを、 右オペランドには int のみを取ることが出来ます。
再帰的に簡単な実装をしてみる
フィボナッチ数を扱う - 再帰呼出し お気楽 Go 言語プログラミング入門
再帰関数を学ぶと、どんな世界が広がるか
V - 2.05.再帰関数
メソッド内で、自分自身を呼び出すこと
- ベースケースをに対して、必ずreturnを実装すること
- 再帰呼び出しを行ったときの問題が、元の問題よりも小さな問題となるように再帰呼び出しを行い、そのような「より小さい問題の系列」が最終的にベースケースに辿り着くようにする
ベースケース
- 再帰呼び出しを行わずに完了できる処理をベースケースという
再帰関数が2箇所呼ばれる実装をしてしまうと、同じ計算が複数走ることになり、計算量が爆増することになる。 そんな時に活用できるのが、動的計画法。
s = "ABCDEFGhijklmn"
fmt.Println(s[4:10]) // -> "EFGhij"
# [最初の数字(どこから開始するのか、上記4文字目の以降のGo):終了する地点（: この数値は含めない）]