文系プログラマーがAtCoderをする前に確認するメモ

##はじめに
AtCorderを開始する前に確認する自分用メモです。
こちらの記事は、習慣的に過去問をこなしていくときのハードルをなくすことを目的としています。

なお、私はJAVA、PHPの経験が長いですが、
現在はQAを経て、外資系コンサルティングファームに所属しており日常コードに触れる機会はありません。


##前提（以下には触れていません）
- AtCorderへのアカウント登録
- コンテストが対象の方は、参加したいコンテストの参加登録と参加日の到来

##参加対象
例です。コンテストに参加する習慣がついている方はTOPから遷移できるかと思いますが、
過去問をこなしていこうと思っている方はどこからいくんだっけ、どこまで消化したっけと迷うくらいなら直リンクで飛びましょう。
URL：https://atcoder.jp/contests/abs/tasks
やっていることメモ：[AtCoder Beginners Selection](https://atcoder.jp/contests/abs)の10問目
参考：[競技プログラミングって何？ (はじめての高校生向け)](https://qiita.com/sifue/items/d582f3af426f524e5394#%E4%BB%8A%E5%BE%8C%E3%82%82%E3%81%97%E3%82%A6%E3%83%87%E3%82%92%E4%B8%8A%E3%81%92%E3%81%9F%E3%81%84%E6%99%82)

##コンテスト（過去問や練習含む）の「参加」ボタンを押す前の準備
####1. 必ず必要となる構文をすぐにコピーできる状態にしておく
競技プログラムでは、標準入力がインプットとされます。特に**複数回にわたって与えられる標準入力を取得する方法**がイメージつかない方はかならず準備しておいてください。
#####Goの例
```:入力
a
b c
s f
```
```golang:上記入力を受け取って出力するための最低限の記述

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.よく出てくる計算や構文も同様のメモ
構文に関しては、日常業務でコーディングやられている方はソラで書けると思いますが、
業務で使わないような計算方式（公約数など）はメモしておいたほうがいいと感じました。

#####パッと出ないものの例

```golang:入力数がnの場合の取得方法
// 入力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])
}
```
```golang:文字列の分割取り出し（配列として扱う）
  s = "abc"
  string(s[0]) // "a"
```
```golang:数字の分割取り出し（桁ごとに配列として扱う）
// 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
  }
```
```golang:絶対値
import (
  "math"
)
func main() {
  n = math.Abs(float64(-5)) // Absはfloat64型のみ対応
  fmt.Println(int(n)) // Absの出力はfloat64になっているのでint利用するときはキャスト
}
```
```golang:ソート
sort.Ints(nums) // 昇順
sort.Sort(sort.Reverse(sort.IntSlice(nums))) // 降順
```
```golang:for文、range
// 普通のforの繰り返し
  for i := 0; i < 10; i++ {
  }
// while文的にも作成可能
  for n < 10 {
    n++
  }
// range
  for i, v := range s {
    fmt.Println(i, v)
  }
```

```golang:if文
  if score := 52; score > 80 {
    fmt.Println("Great!")
  } else if score > 60 {
    fmt.Println("Good!")
  } else {
    fmt.Println("soso")
  }
```
```golang:switch文
  switch signal {
    case "red":
      fmt.Println("Stop")
    default:
      fmt.Println("wrong")
  }
```
```golang:スライス
  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)
```
```golang:配列
// 宣言と代入を分ける
  var a [5]int
  a [2] = 3
// 宣言と代入を同時にする
  b := [3]int{1, 3, 6}
// 配列の個数が未定の場合
  c := [...]int{2, 4, 7, 5, 5}
```
```golang:マップ
// 空宣言
  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の基本を押さえる為のまとめ](https://qiita.com/tfrcm/items/e2a3d7ce7ab8868e37f7)

####3.macに置けるバックスラッシュの入力の仕方を思い出す
optionキーを押しながら、¥キーを押す。(Mac mini 等で Windows用のキーボードを接続している場合は Alt キー)
※IME「ことえり」の設定を変えることで「¥」を「\」にすることは可能

####4.計算量についての意識
C問題以降はループ処理を行わないと解けない問題となるため、計算量を意識する必要があります。
判定が実行時間超過 (TLE) にならない計算量目安:O(10<sup>7</sup>) = 10000000


具体的には以下のような制限の場合、AとBを二重ループをすると10<sup>10</sup>となるので間に合わない。

- 1 ≤ N ≤ 10<sup>5</sup>
- 1 ≤ A<sub>i</sub>, B<sub>i</sub>, C<sub>i</sub> ≤ 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が小さく10<sup>7</sup>に収まる範囲なら愚直に処理しても判定は通ります。

```golang:ビット全検索（二重ループしても100*100=10000)
// 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個にすることを目標とします。