What's New Qiita

20190523のGoに関する記事は6件です。

  • 投稿日：2019-05-23T23:42:21+09:00

【初心者向け】Goプログラムを手軽に書いて実行してみた

Go初心者向けの投稿です。
まずはGo言語を始めるにあたっての簡単なコマンドとテストコードを書いて実行しています。

go run

「Hello,world!」をGoで書くと次のようになります。

main.go
package main

import (
  "fmt"
)

func main () {
  fmt.Println("Hello,World!")
}

$go run hello.go

Goは基本的にコンパイルを前提としているがgo runコマンンドでビルドプロセスを隠蔽できます。便利ですね。

参照のないパッケージについて

Goでは使用していない不要なパッケージがimportされているとエラーになります。
これはプログラムにゴミを残さないためにも大切ですが、エラーになるのが面倒な場合は下記指定「アンダーバー」でバイパスが可能です。

import (
  _ "fmt"  // 参照されないパッケージを取り込む方法
)

go build

hoge.goファイルをコンパイルして実行ファイルを作成することが出来ます。
$ go build -o hoge hoge.go
ビルドに成功するとGoプログラムと同じディレクトリに実行ファイルが作成されます。

go run と go buildの違い

go run も go build もコンパイルして実行ファイルのの作成をしてくれるが、go run の場合go buildのようにカレントディレクトリ以下のすべてのファイルが読み込まれるわけではないです。

goの実行ファイルはgoファイルよりも容量が大きくなる

GoはOSによって提供される標準的なライブラリに依存されないようにするため、プログラムが必要とするパッケージを実行ファイルの中に組み込んでいます。
そのため容量は大きくなります。

パッケージとディレクトリ

Goでは「１つのディレクトリには１つのパッケージ定義のみ」という原則があります。
この原則に従わない状態でビルドを行うとエラーになります。

実際に動かしてみよう

スクリーンショット 2019-05-23 23.10.38.png

main.go
package main

import (
    "fmt"
    "./animals"
)

func  main() {
    fmt.Println(animals.CatCry())
    fmt.Println(animals.DogCry())
    fmt.Println(animals.RabitCry())
}
cat.go
package animals

func CatCry() string{
    return "nya---n"
}
dog.go
package animals

func DogCry() string{
    return "wanwan!!!"
}
rabit.go
package animals

func RabitCry() string {
    return "usagidayo--!!!"
}

簡単なファイルが用意できたらgo runで動かします！

$ go run main.go
nya---n
wanwan!!!
usagidayo--!!!

想定通りに動いてますね。

testの記載方法について

goには標準でパッケージの機能をテストするための機能が組み込まれています。

animals_test.go
package animals

import (
    "testing"
)

func TestCatCry(t *testing.T) {
    expect := "nya---n"
    actual := CatCry()

    if expect != actual {
        t.Errorf("%s != %s", expect, actual)
    }
}

testの実行

$ go test ./animals
ok      _/hello-go/animals    0.006s

okとなっているので成功しているのが解ります。
せっかくなのでコードを変えて失敗させてみます。

変更前：

expect := "nya---n"

変更後：

expect := "wawanwanda-"

変更したらバチーンとtestコマンドを実行します。

$ go test ./animals
--- FAIL: TestCatCry (0.00s)
    animals_test.go:12: wawanwanda- != nya---n
FAIL
FAIL    _/hello-go/animals    0.006s

FAILとなってテストが失敗しているのがわかります。どこで失敗しているのかも出ているので簡単に追えますね。

まとめ

はじめてGoに触れましたが、コマンドが豊富で記載も簡潔。開発者に優しい設計になっていますね。これからどんどん触ってどんどん投稿していきます。

  • このエントリーをはてなブックマークに追加
  • Qiitaで続きを読む
  • 投稿日：2019-05-23T23:42:21+09:00

[初心者向け]Goプログラムを手軽に書いて実行してみた

Go初心者向けの投稿です。
まずはGo言語を始めるにあたっての簡単なコマンドとテストコードを書いて実行しています。

go run

「Hello,world!」をGoで書くと次のようになります。

main.go
package main

import (
  "fmt"
)

func main () {
  fmt.Println("Hello,World!")
}

$go run hello.go

Goは基本的にコンパイルを前提としているがgo runコマンンドでビルドプロセスを隠蔽できます。便利ですね。

参照のないパッケージについて

Goでは使用していない不要なパッケージがimportされているとエラーになります。
これはプログラムにゴミを残さないためにも大切ですが、エラーになるのが面倒な場合は下記指定「アンダーバー」でバイパスが可能です。

import (
  _ "fmt"  // 参照されないパッケージを取り込む方法
)

go build

hoge.goファイルをコンパイルして実行ファイルを作成することが出来ます。
$ go build -o hoge hoge.go
ビルドに成功するとGoプログラムと同じディレクトリに実行ファイルが作成されます。

go run と go buildの違い

go run も go build もコンパイルして実行ファイルのの作成をしてくれるが、go run の場合go buildのようにカレントディレクトリ以下のすべてのファイルが読み込まれるわけではないです。

goの実行ファイルはgoファイルよりも容量が大きくなる

GoはOSによって提供される標準的なライブラリに依存されないようにするため、プログラムが必要とするパッケージを実行ファイルの中に組み込んでいます。
そのため容量は大きくなります。

パッケージとディレクトリ

Goでは「１つのディレクトリには１つのパッケージ定義のみ」という原則があります。
この原則に従わない状態でビルドを行うとエラーになります。

実際に動かしてみよう

スクリーンショット 2019-05-23 23.10.38.png

main.go
package main

import (
    "fmt"
    "./animals"
)

func  main() {
    fmt.Println(animals.CatCry())
    fmt.Println(animals.DogCry())
    fmt.Println(animals.RabitCry())
}
cat.go
package animals

func CatCry() string{
    return "nya---n"
}
dog.go
package animals

func DogCry() string{
    return "wanwan!!!"
}
rabit.go
package animals

func RabitCry() string {
    return "usagidayo--!!!"
}

簡単なファイルが用意できたらgo runで動かします！

$ go run main.go
nya---n
wanwan!!!
usagidayo--!!!

想定通りに動いてますね。

testの記載方法について

goには標準でパッケージの機能をテストするための機能が組み込まれています。

animals_test.go
package animals

import (
    "testing"
)

func TestCatCry(t *testing.T) {
    expect := "nya---n"
    actual := CatCry()

    if expect != actual {
        t.Errorf("%s != %s", expect, actual)
    }
}

testの実行

$ go test ./animals
ok      _/hello-go/animals    0.006s

okとなっているので成功しているのが解ります。
せっかくなのでコードを変えて失敗させてみます。

expect := "nya---n"

expect := "wawanwanda-"

変更したらバチーンとtestコマンドを実行します。

$ go test ./animals
--- FAIL: TestCatCry (0.00s)
    animals_test.go:12: wawanwanda- != nya---n
FAIL
FAIL    _/hello-go/animals    0.006s

FAILとなってテストが失敗しているのがわかります。どこで失敗しているのかも出ているので簡単に追えますね。

まとめ

はじめてGoに触れましたが、コマンドが豊富で記載も簡潔。開発者に優しい設計になっていますね。これからどんどん触ってどんどん投稿していきます。

  • このエントリーをはてなブックマークに追加
  • Qiitaで続きを読む
  • 投稿日：2019-05-23T20:20:25+09:00

vs code insiders のクイックスタートを色々な言語で試してみた。

vs code insidersにIDEの未来の姿を見たので、勉強を兼ねて構築手順をまとめてみました。

クイックスタートの言語毎で若干差異があるようで、かじった事のある言語を試してみました。

vs code insidersそのものの詳しい説明については他のわかりやすい記事を参照してください。
簡単に言うと、今までは開発環境と実際の動く環境は別々で、トラブルが起こりやすい状況でのプログラミングが普通だったんですが、実際の動く環境でプログラミングができる。を提供するのがvs code insidersです。

2019-05-23時点では以下の言語のクイックスタート（以下チュートリアル）があります。
https://code.visualstudio.com/docs/remote/containers

  • node
  • python
  • go
  • java
  • dotnetcore
  • php
  • rust
  • cpp

この中でnode、python、go、phpを今回試していきます。

事前準備

チュートリアルを始める前に、git や vs code insiders&extention(remote development)、docker等をインストールしてください。
dockerはshared driveの設定も忘れずに。

チュートリアル ダウンロード

任意のディレクトリで以下のコマンドを実行

sh
git clone https://github.com/Microsoft/vscode-remote-try-node
git clone https://github.com/Microsoft/vscode-remote-try-python
git clone https://github.com/Microsoft/vscode-remote-try-go
git clone https://github.com/Microsoft/vscode-remote-try-php

チュートリアルの順番について

説明しやすさの観点から go → node → php → python の順番で進めます。

go

  1. vs code insidersを立ち上げて任意のディレクトリにダウンロードしたvscode-remote-try-goを開く
  2. 右下に「Folder contains〜」というポップアップが出るので「Reopen in Container」のボタンを押す
  3. 「Installing Dev Container [details]〜」に切り替わる
  4. しばらく待ち ※進捗状況は[detail]から
  5. 左下の緑の枠が「Dev Container: GO」になったら環境構築終了
  6. メニューの表示→ターミナルを開いて、go run server.goを実行
  7. Server listening on port 9000が出力されればwebサーバ立ち上げ完了
  8. http://localhost:9000/ にアクセス

出力文字を変えたい場合はserver.go の "Hello remote world!"を任意の文字列に変更し、ターミナルからCTRL+c で停止した後、再度go run server.goを実行してページをリロードすると反映されていると思います。

node

環境構築はディレクトリvscode-remote-try-nodeを開いた後はgoと途中まで一緒(上記4まで)なので割愛します。
5. 左下の緑の枠が「Dev Container: Node.js Sample」になったら環境構築終了
6. 表示→ターミナルを開いて、node server.jsを実行
7. Running on http://0.0.0.0:3000が出力されればwebサーバ立ち上げ完了
8. http://localhost:3000/ にアクセス

出力文字を変えたい場合は server.js の対象箇所を変更できます。
goと同様に停止後→再実行で反映されます。

PHP

1〜5 まで割愛
6. 表示→ターミナルを開いて、php -S localhost:8000を実行
7. F1ボタンを押してRemote-Containers: Forward Port from Container〜を選択後、「Forward 8000」をクリック
8. http://localhost:8000/ にアクセス

phpはgo、node の手順＋ポート転送の手順が必要となります。

出力文字を変えたい場合は index.phpを変更します。
また、変更にサーバの再起動は必要なく、ページのリロードのみで反映されます。

python

1〜5まで割愛
6 以降では、デフォルトの設定では動かなかった＆ポート番号(9000)がgoとカブるので以下の変更をします。

.devcontainer/devcontainer.json
"appPort": 9000,
↓
"appPort": 5000,
.vscode/devcontainer.json
"appPort": 9000,
↓
"appPort": 5000,
app.py
#以下をファイル末尾に追加
if __name__ == "__main__":
    app.run(debug=True, host='0.0.0.0', port=5000)

表示→ターミナルを開いて、python app.pyを実行

出力文字を変えたい場合は static/index.htmlを変更します。
また、変更にサーバの再起動は必要なく、ページのリロードのみで反映されます。
※goとnodeも別ファイルとしてindex.htmlを読み込むように変更すればサーバ再起動は必要ありません。

  • このエントリーをはてなブックマークに追加
  • Qiitaで続きを読む
  • 投稿日：2019-05-23T09:53:58+09:00

Go の net/http でベーシック認証の client/server を作成する

BackGround

筆者は普段は C で組み込み技術の開発をしています。
そんな筆者ですが、業務で web技術 を活用したい、と常々考えています。

そこで、web技術の基礎として、ベーシック認証ができる client/server を作成してみましたので紹介します。

今、web 技術の基本として、O'REILLY の Real World HTTP という書籍を読んでいるので、
その本で書かれている http の仕様を踏まえつつ、実践をしてみたものとなります。

Target

  • Go の標準パッケージ net/http のベーシック認証の取り扱い方がわかる
  • Go で実装した client/server を実際に動かしてベーシック認証を試せる

ベーシック認証

Basic認証（ベーシックにんしょう、Basic Authentication）とは、HTTPで定義される認証方式の一つ。

基本認証と呼ばれることも。

Basic認証では、ユーザ名とパスワードの組みをコロン ":" でつなぎ、Base64でエンコードして送信する。

このため、盗聴や改竄が簡単であるという欠点を持つが、ほぼ全てのWebサーバおよびブラウザで対応しているため、広く使われている。

出典: フリー百科事典『ウィキペディア（Wikipedia）』

つくるもの

  • client
    • server へベーシック認証付きのリクエストを送信し、server のレスポンスの body を標準出力へ出力する
  • server
    • client のリクエストをベーシック認証にて認証し、認証が成功したかどうかで異なるレスポンスを送信する
      • 成功した場合は Authed とレスポンスを送信する
      • 失敗した場合は Not authorized とレスポンスを送信する

できたもの

client/server は以下のように動きます。

先に server を起動し、その後 client を起動すると、
認証が成功した旨がレスポンスとして得られます。 

# server プログラムを起動する
$ ./server


# client プログラムを実行する
$ ./client
Authed

SourceCode

ソースコードは以下のようになりました。

client.go
package main

import (
    "fmt"
    "io/ioutil"
    "log"
    "net/http"
    "time"
)

func main() {
    client := &http.Client{Timeout: time.Duration(10) * time.Second}

    req, err := http.NewRequest("GET", "http://localhost:18888/basic", nil)
    if err != nil {
        log.Fatal(err)
    }
    req.SetBasicAuth("user", "pass")
    resp, err := client.Do(req)
    if err != nil {
        log.Fatal(err)
    }
    defer resp.Body.Close()

    fmt.Println(string(getContent(resp)))
}

func getContent(resp *http.Response) []byte {
    b, err := ioutil.ReadAll(resp.Body)
    if err != nil {
        log.Fatal(err)
    }
    return b
}

client は、req オブジェクトへ、 SetBasicAuth メソッドを使って、
ベーシック認証のユーザとパスワードを与えるだけでベーシック認証に対応できます。

server.go
package main

import (
    "fmt"
    "log"
    "net/http"
)

const (
    basicAuthUser     = "user"
    basicAuthPassword = "pass"
)

func main() {
    http.HandleFunc("/basic",
        func(w http.ResponseWriter, r *http.Request) {
            if user, pass, ok := r.BasicAuth(); !ok || user != basicAuthUser || pass != basicAuthPassword {
                w.Header().Add("WWW-Authenticate", `Basic realm="my private area"`)
                w.WriteHeader(http.StatusUnauthorized)
                http.Error(w, "Not authorized", 401)
                return
            }
            _, err := fmt.Fprintf(w, "Authed\n")
            if err != nil {
                log.Fatal(err)
            }
        },
    )
    log.Println(http.ListenAndServe(":18888", nil))
}

server は、req オブジェクトへ、 BasicAuth メソッドを使って、
ベーシック認証のユーザとパスワードを取得し評価するだけでベーシック認証に対応できます。

Roundup

  • パッケージの中で相対的に低水準な net/http でも、十分に抽象化されていて、簡単に取り扱うことができる
  • リクエストの送信や、サーバの作成自体も net/http にてシンプルに実装ができる

Reference

  • このエントリーをはてなブックマークに追加
  • Qiitaで続きを読む
  • 投稿日：2019-05-23T00:57:04+09:00

GO言語 DrawStringで画像に日本語を描画する

GO言語で画像に日本語を描画する方法を調べました。
同様の記事は見つけられなかったので投稿しておきます。

結論

以下のように日本語キャラクタを含む外部フォントファイルを読み込むことで、日本語を描画できました。

    ftBinary, err := ioutil.ReadFile("Koruri-Bold.ttf")
    ft, err := truetype.Parse(ftBinary)

なぜ日本語が描画できない？

日本語を描画したいと思い、下記記事を参考にさせていただき、画像に日本語を描画するソースを大雑把に作成しました。

参考 : Goでカラー絵文字を使って画像を合成する

しかし、おなじみの文字化けが発生しました。

文字化け画像
mojibake.png

文字化けソース全文

mojibake.go
package main

import (
    "bytes"
    "fmt"
    "image"
    "image/png"
    "os"

    "github.com/golang/freetype/truetype"
    "golang.org/x/image/font"
    "golang.org/x/image/font/gofont/gobold"
    "golang.org/x/image/math/fixed"
)

func main() {
    // フォントの読み込み
    ft, err := truetype.Parse(gobold.TTF)
    if err != nil {
        fmt.Fprintln(os.Stderr, err)
        os.Exit(1)
    }

    opt := truetype.Options{
        Size:              90,
        DPI:               0,
        Hinting:           0,
        GlyphCacheEntries: 0,
        SubPixelsX:        0,
        SubPixelsY:        0,
    }

    imageWidth := 100
    imageHeight := 100
    textTopMargin := 90
    text := "あ"

    img := image.NewRGBA(image.Rect(0, 0, imageWidth, imageHeight))

    face := truetype.NewFace(ft, &opt)

    dr := &font.Drawer{
        Dst:  img,
        Src:  image.Black,
        Face: face,
        Dot:  fixed.Point26_6{},
    }

    dr.Dot.X = (fixed.I(imageWidth) - dr.MeasureString(text)) / 2
    dr.Dot.Y = fixed.I(textTopMargin)

    dr.DrawString(text)

    buf := &bytes.Buffer{}
    err = png.Encode(buf, img)

    if err != nil {
        fmt.Fprintln(os.Stderr, err)
        os.Exit(1)
    }

    file, err := os.Create(`test.png`)
    if err != nil {
        fmt.Fprintln(os.Stderr, err)
        os.Exit(1)
    }
    defer file.Close()

    file.Write(buf.Bytes())
}

truetype.Parse(gobold.TTF) はなにをやっているのか

フォントを読み込む truetype.Parse(gobold.TTF) は何をやっているのかソースを覗きました。

gobold.TTFより抜粋

data.go
// generated by go run gen.go; DO NOT EDIT

// Package gobold provides the "Go Bold" TrueType font
// from the Go font family. It is a proportional-width, sans-serif font.
//
// See https://blog.golang.org/go-fonts for details.
package gobold

// TTF is the data for the "Go Bold" TrueType font.
var TTF = []byte{
    0x00, 0x01, 0x00, 0x00, 0x00, 0x0e, 0x00, 0x80, 0x00, 0x03, 0x00, 0x60, 0x4f, 0x53, 0x2f, 0x32,
// 以下略

コメントよりGo Bold True Type フォントのバイナリデータ配列がgobold.TTFに登録されていることがわかりました。

コメントに記載のThe Go Blog - Go fontsを確認すると

Go fontsはWGL4キャラクタセットとのことで、日本語は含まれていません。

そのため対応する文字がないので文字化けしていると推測されます。

日本語キャラクタを含む外部フォントを読み込めば文字化けしない

冒頭に記載したように、外部フォントファイルを読み込めば文字化けせず日本語が描画できました。

日本語フォントには Koruri を利用させてもらいました。
(あらかじめダウンロードし、GOバイナリと同じ場所に配置しています。)

    ftBinary, err := ioutil.ReadFile("Koruri-Bold.ttf")
    ft, err := truetype.Parse(ftBinary)

日本語が描画できた画像

nihongook.png

ソース全文

:nihongook.go
package main

import (
    "bytes"
    "fmt"
    "image"
    "image/png"
    "os"

    "github.com/golang/freetype/truetype"
    "golang.org/x/image/font"
    "golang.org/x/image/font/gofont/gobold"
    "golang.org/x/image/math/fixed"
)

func main() {
    // フォントファイルを読み込み
    ftBinary, err := ioutil.ReadFile("Koruri-Bold.ttf")
    if err != nil {
        fmt.Fprintln(os.Stderr, err)
        os.Exit(1)
    }

    ft, err := truetype.Parse(ftBinary)
    if err != nil {
        fmt.Fprintln(os.Stderr, err)
        os.Exit(1)
    }

    opt := truetype.Options{
        Size:              90,
        DPI:               0,
        Hinting:           0,
        GlyphCacheEntries: 0,
        SubPixelsX:        0,
        SubPixelsY:        0,
    }

    imageWidth := 100
    imageHeight := 100
    textTopMargin := 90
    text := "あ"

    img := image.NewRGBA(image.Rect(0, 0, imageWidth, imageHeight))

    face := truetype.NewFace(ft, &opt)

    dr := &font.Drawer{
        Dst:  img,
        Src:  image.Black,
        Face: face,
        Dot:  fixed.Point26_6{},
    }

    dr.Dot.X = (fixed.I(imageWidth) - dr.MeasureString(text)) / 2
    dr.Dot.Y = fixed.I(textTopMargin)

    dr.DrawString(text)

    buf := &bytes.Buffer{}
    err = png.Encode(buf, img)

    if err != nil {
        fmt.Fprintln(os.Stderr, err)
        os.Exit(1)
    }

    file, err := os.Create(`test.png`)
    if err != nil {
        fmt.Fprintln(os.Stderr, err)
        os.Exit(1)
    }
    defer file.Close()

    file.Write(buf.Bytes())
}
  • このエントリーをはてなブックマークに追加
  • Qiitaで続きを読む
  • 投稿日：2019-05-23T00:00:59+09:00

Go で Tenka1 2018 Beginner, C - Align を解いてみた

Go で Tenka1 2018 Beginner C - Align を解いてみました。

問題

問題文

整数が N 個与えられます。i 個目の整数は Ai です。 これらを好きな順に一列に並べるとき、隣り合う要素の差の合計の最大値を求めてください。

制約

  • $2 \le N \le 10^5$
  • $1 \le A_i \le 10^9 $
  • 入力は全て整数である。

( https://atcoder.jp/contests/tenka1-2018-beginner/tasks/tenka1_2018_c より引用)

考えたこと

より小さいものと大きいものを隣り合わせるのが良さそう？
→ Aをソートして真ん中から大きい方、小さい方交互に埋めていけばいいんじゃね？
→ 大きい方を真ん中にするか、小さい方を真ん中にするか、Nの偶奇でいくつかパターンがあるので、全部計算して一番大きいやつ
でも、証明できないなーと思いつつサブミットしたらやはりWAでギブアップ。証明重要ですね。

正しい考え方

公式解説によれば、
最適な並び順を

$p_1, p_2, p_3, p_4, \dots , p_n $

とすると、この数列は

$p_1 \ge p_2 \le p_3 \ge p_4 \le \dots $

または

$p_1 \le p_2 \ge p_3 \le p_4 \ge \dots $

のどちらかの関係になっているはずです。

最適な並び順における大小関係

これは、次のように考えると正しいことがわかります。

数列に $ \dots \ge p_{i-1} \le p_i \le p_{i+1} \ge \dots$ という並びが存在したとします。隣り合う数字の差分はそれぞれ
$d_1 = p_i - p_{1-1}$
$d_2 = p_{i+1} - p_{i}$
であり合計は $d_1 + d_2$ です。（$d_i$ はいずれも0または正の数）

ここから $p_{i}$ を取り除き、列の末尾に移動したとすろと
$\dots \ge p_{i-1} \le p_{i+1} \ge \dots $
となり、 数字の差分は
$d_3$
$= p_{i+1} - p_{i-1}$
$= p_{i+1} - p_i + p_i - p_{i-1} $
$= d_2 + d_1$
となります。つまり差分の合計値として、この部分については $p_i$ があってもなくても変わりありません。

一方で、 $p_i$ を移動した先の列の末尾においてはどうなるでしょうか。
ここでは複数の可能性が考えられます。
もし

$p_{n-1} \le p_n \ge p_i$

であれば、もとの数列よりも $p_n - p_i$ の分だけ差分の合計値が0以上増加することになります。
もし

$p_{n-1} \le p_n \le p_i$

であれば、やはり、$p_i - p_n$ という0以上の値の分だけ差分の合計値が増加することになります。また、この場合はさきほどと同様、

$p_{n-1} \le p_i \ge p_n$

のように間にある $p_n$ を取り除き、末尾に移動することで、更に差分の合計値を増やすことが可能です。
もともとの末尾が

$p_{n-1} \ge p_n$

だったとしても、同様に考えれば、 差分の合計値が増えることは合っても、減ることはありません。
というわけで、最適な並び順における大小関係は最初に示したとおりの形になります。

最適な並び順

さて、最適な数列において、数字が

$p_1 \ge p_2 \le p_3 \ge p_4 \le \dots $

または

$p_1 \le p_2 \ge p_3 \le p_4 \ge \dots $

と並んでいるとき、隣り合う数字の差の合計はそれぞれ

$ (p_1 - p_2) + (p_3 - p_2) + (p_3 - p_4) + (p_5 - p_4) + \dots $
$ = p_1 - 2\times p_2 + 2\times p_3 - 2\times p_4 + 2\times p_5 - \dots $

または

$ (p_2 - p_1) + (p_2 - p_3) + (p_4 - p_3) + (p_4 - p_5) + \dots $
$ = - p_1 + 2\times p_2 - 2\times p_3 + 2\times p_4 - 2\times p_5 + \dots $

となります。この式からは、直感的につぎのことがわかります。

  • 両端以外にある数字は、2倍したうえで足されるグループと、2倍したうえで引かれるグループに分かれる
  • 両端にある数字はそのまま足されるグループと、そのまま引かれるグループに分かれる

ただし、$N$ の大きさや偶奇によって各グループの要素数が0になることはあります。例えば $N=3$ で $p_1 \lt p_2 \gt p_3 $ が最適な並びなら、 2倍で足されるグループは $p_2$ , 2倍で引かれるグループは空、そのまま足されるグループは空、そのまま引かれるグループは $p_1, p_3$ となります。

また、

  • より大きい数は、そのまま足すよりも2倍して足したほうが良い
  • より小さい数は、そのまま引くよりも、2倍して引いたほうが良い（大きい数を2倍して引くよりも、小さいを2倍して引いたほうがマシ）

のは明らかなので、

  • 中央値に近い値を両端（そのまま足す、または引くグループ）に持ってくる
  • 両端以外は中央値よりも大きい数（2倍して足すグループ）と、中央値よりも小さい数（2倍して引くグループ）を交互にならべる

と最適になることがわかります。

実装

$A$ をソートしたあと2分割して、もともと中央値側にあった値が新しい両端にくるように交互に組み合わせるようにすると最適になります（図1）。

図1 ソートして分割、再合成

ただし、これは中央値がちょうど2つある、 $N$ が偶数の場合です。
$N$ が奇数の場合は中央値が1つなので、中央値の上か下の数のどちらかを端の数字として使う必要があります。このため、中央値以外の数を $N$ が偶数のときと同じように組み合わせた後、中央値を足す側のグループに含める場合と、引く側のグループに含める場合のどちらが最適になるのかを調べる必要があります（図2, ☆が中央値）。

図2 Nが奇数の場合の構成

提出コード

最終的に次のようなコードを書きました（抜粋）。全体はこちら

func main() {
    defer stdout.Flush()
    N := readInt()
    A := make([]int64, N)
    for i := range A {
        A[i] = readInt64()
    }
    Sort(A, func(i, j int) bool { return A[i] < A[j] })

    small := make([]int64, N/2)
    large := make([]int64, N/2)
    m := N / 2
    if N%2 == 1 {
        m++
    }

    for i := 0; i < N/2; i++ {
        small[i] = A[i]
    }

    for i := 0; i < N/2; i++ {
        large[i] = A[m+i]
    }

    b := make([]int64, 0, N)
    for i := 0; i < N/2; i++ {
        b = append(b, large[i])
        b = append(b, small[i])
    }

    ans := calc(b)

    if N%2 == 1 {
        ans += max(b[0]-A[N/2], A[N/2]-b[len(b)-1])
    }
    println(ans)
}

func max(a, b int64) int64 {
    if a < b {
        return b
    }
    return a
}

func abs(a int64) int64 {
    if a < 0 {
        return -a
    }
    return a
}

func calc(a []int64) int64 {
    var ans int64
    for i := 0; i+1 < len(a); i++ {
        ans += abs(a[i] - a[i+1])
    }
    return ans
}

$N$ が奇数の場合は、実際には完全な数列を構成せず、中央値を取り除いて偶数の場合と同様に構成したあと、取り除いた中央値を両端どちらにつけたほうが最大になるかだけをチェックしています。

  • このエントリーをはてなブックマークに追加
  • Qiitaで続きを読む

日付別

タグ一覧