はじめに
AtCorderを開始する前に確認する自分用メモです。
こちらの記事は、習慣的に過去問をこなしていくときのハードルをなくすことを目的としています。
なお、私はJAVA、PHPの経験が長いですが、
現在はQAを経て、外資系コンサルティングファームに所属しており日常コードに触れる機会はありません。
前提（以下には触れていません）
- AtCorderへのアカウント登録
- コンテストが対象の方は、参加したいコンテストの参加登録と参加日の到来
参加対象
例です。コンテストに参加する習慣がついている方はTOPから遷移できるかと思いますが、
過去問をこなしていこうと思っている方はどこからいくんだっけ、どこまで消化したっけと迷うくらいなら直リンクで飛びましょう。
URL：https://atcoder.jp/contests/abs/tasks
やっていることメモ：AtCoder Beginners Selectionの10問目
参考：競技プログラミングって何？ (はじめての高校生向け)
コンテスト（過去問や練習含む）の「参加」ボタンを押す前の準備
1. 必ず必要となる構文をすぐにコピーできる状態にしておく
競技プログラムでは、標準入力がインプットとされます。特に複数回にわたって与えられる標準入力を取得する方法がイメージつかない方はかならず準備しておいてください。
Goの例
a
b c
s f
package main
import (
"fmt"
)
func main() {
var a, b, c int
var s string
var f float64
fmt.Scan(&a)
fmt.Scanf("%d %s", &b, &s)
fmt.Scanf("%f", &f)
fmt.Println(a+b+c)
fmt.Printf("%d %s\n", a+b+c, s)
}
参考（Go以外の言語もこちらから）：https://practice.contest.atcoder.jp/tasks/practice_1
2.よく出てくる計算や構文も同様のメモ
構文に関しては、日常業務でコーディングやられている方はソラで書けると思いますが、
業務で使わないような計算方式（公約数など）はメモしておいたほうがいいと感じました。
パッと出ないものの例
// 入力a1 a2 .... an
nums := make([]int, n)
for i := 0; i < n; i++ {
fmt.Scan(&nums[i])
}
// 入力a1 b2 a2 b2 .... an bn
nums1 := make([]int, n)
nums2 := make([]int, n)
for i := 0; i < n; i++ {
fmt.Scan(&nums1[i], &nums2[i])
}
s = "abc"
string(s[0]) // "a"
// 83の例
// 1回目：83/10=8あまり3（1桁目の数字）
// 2回目：8/10=0あまり8（10桁目の数字）
n_sli := []int{}
for n > 0 {
n_sli = append(n_sli, n%10)
n /= 10
}
import (
"math"
)
func main() {
n = math.Abs(float64(-5)) // Absはfloat64型のみ対応
fmt.Println(int(n)) // Absの出力はfloat64になっているのでint利用するときはキャスト
}
sort.Ints(nums) // 昇順
sort.Sort(sort.Reverse(sort.IntSlice(nums))) // 降順
// 普通のforの繰り返し
for i := 0; i < 10; i++ {
}
// while文的にも作成可能
for n < 10 {
n++
}
// range
for i, v := range s {
fmt.Println(i, v)
}
if score := 52; score > 80 {
fmt.Println("Great!")
} else if score > 60 {
fmt.Println("Good!")
} else {
fmt.Println("soso")
}
switch signal {
case "red":
fmt.Println("Stop")
default:
fmt.Println("wrong")
}
a := [5]int{2, 10, 8, 15, 4}
b := a[2:4] // [8, 15]
// make関数でいきなりスライスを作成する
s1 := make([]int, 3) // [0 0 0]
// いきなり値を割り当てたスライスを作成する
s2 := []int{1, 3, 5} // 配列の宣言と似ている
// appendでスライスの末尾に要素を追加
s3 := append(s2, 8, 2, 10)
// 宣言と代入を分ける
var a [5]int
a [2] = 3
// 宣言と代入を同時にする
b := [3]int{1, 3, 6}
// 配列の個数が未定の場合
c := [...]int{2, 4, 7, 5, 5}
// 空宣言
m := map[string]int{}
// 値を指定しながら宣言する
m := map[string]int{"fujimoto": 100, "arita": 200}
// キーの存在を調べる(okにbool結果が入る）
v, ok := m["fujimoto"]
// 要素追加
m["fujimoto"] = 100
// 要素を削除する
delete(m, "fujimoto")
参考：他言語プログラマがgolangの基本を押さえる為のまとめ
3.macに置けるバックスラッシュの入力の仕方を思い出す
optionキーを押しながら、¥キーを押す。(Mac mini 等で Windows用のキーボードを接続している場合は Alt キー)
※IME「ことえり」の設定を変えることで「¥」を「\」にすることは可能
4.計算量についての意識
C問題以降はループ処理を行わないと解けない問題となるため、計算量を意識する必要があります。
判定が実行時間超過 (TLE) にならない計算量目安:O(107) = 10000000
具体的には以下のような制限の場合、AとBを二重ループをすると1010となるので間に合わない。
- 1 ≤ N ≤ 105
- 1 ≤ Ai, Bi, Ci ≤ N
解法としては単一のループを何度か実行する場合と二重ループで処理する場合の計算量はかなり違うため、単独ループで予め各値の処理を済ませておくなど多重ループを回避する処理を検討します。
// AとBとCをそれぞれ単一でループして回答した場合
// 合計の計算量1000000000000000 （100000 * 100000 * 100000）
for i := 0; i < 10; i++ { //a
for i := 0; i < 10; i++ { //b
for i := 0; i < 10; i++ { //c
}
}
}
// AとBとCをそれぞれ単一でループして回答した場合
// 合計の計算量300000 （100000 + 100000 + 100000）
for i := 0; i < 10; i++ {} //a 計算量:100000
for i := 0; i < 10; i++ {} //b 計算量:100000
for i := 0; i < 10; i++ {} //c 計算量:100000
逆に、Nが小さく107に収まる範囲なら愚直に処理しても判定は通ります。
// 100箇所にk回置いていく機会がある。
for bit := 0; bit < (1<<k); bit++ {
var dish [100]int // 置き場所の数
for i := 0; i < k; i++ {
if 0 != bit&(1 << i) {
dish[d[i]-1]++ // dの場所に置く
} else {
dish[c[i]-1]++ // cの場所に置く
}
}
}
提出が終わったらすること
2のメンテ
自身の不足点やパッと出なかったものを追加します。
ソラで書けるようになったものがあれば削除します。
次の参加対象URLを更新
これをしておくことで、次にPCを開いたとき、何をするのか考えることなく画面遷移して始められます。
おわりに
日常的にコードに触れていないことと過去の経験言語と微妙に違う書き方（for文、if文が特に）でコンパイルエラーが出てしまうことや間隔が開いたときの「何するんだっけ（どこまでしていたんだっけ）」でハードルが上がっていたので書きました。
まずは、増える一方の２のメモを0個にすることを目標とします。