Leverage Copy

メモの公開場所

online-judge-toolsをVimから呼ぶプラグイン

TL;DR

  • kmykさんのonline-judge-toolsのコマンドを呼ぶ、Vimのラッパーコマンドをプラグインにしました。
  • 自分は普段こんな感じで使っています。
  • 現状、カスタマイズ性は微妙ですが、submitコマンドは多少便利だと思うのでよかったら試してみてください。

はじめに

online-judge-toolsをVimから呼んで楽をする の内容をプラグイン化しました。

https://github.com/my0k/vim-oj-helper

READMEでは淡々と仕様について(突貫作業なので抜け漏れは多いながら)書いたつもりですが、 この記事では提案する実際の利用方法についてフランクに書いてみたいと思います。

インストール

Vimの標準のプラグインの作法に則っているため、お使いのプラグインマネージャを使えば、 特に問題なくインストールできるかと思います。私はvim-plug を使っており、以下のようにしてインストールできることを確認しました。

Plug 'my0k/vim-oj-helper'

このプラグインは、 oj のサブコマンドである download, test, submit の、Vimのラッパーコマンドを提供します。 oj が実行可能である場合のみコマンド群が定義されるため、 oj への PATH が通っていることを事前に確認してください。

使用方法

ここではABC180に参加しているという想定で説明してみたいと思います。


まずはA問題から解くとして、以下のようにA問題のディレクトリ、ファイルを開いて、 A問題のURLをコメントに書きます。

f:id:maguroguma:20201119012349p:plain
サンプルダウンロードコマンドの実行

ここで :OjDownloadSamples を実行してみましょう。

f:id:maguroguma:20201119012427p:plain
ダウンロード後

実行後、カレントバッファに開いているコードと同じディレクトリ階層に、サンプルケースがダウンロードされています。

ここから問題を解いていきましょう。

f:id:maguroguma:20201119012451p:plain
テストコマンドの実行

コードを書き終わったら、先程ダウンロードしたサンプルでテストを行います。
Pythonで参加しているため :OjLangCommandTest python のように実行してみましょう。

f:id:maguroguma:20201119012535p:plain
テスト後

テストは全て通ったので、提出して問題なさそうです。

f:id:maguroguma:20201119012557p:plain
提出コマンドの実行

カレントバッファで開いているファイルを、その問題に対して提出しましょう。 :OjSubmitCode を実行してみましょう。

f:id:maguroguma:20201119012622p:plain
提出後

これで提出が完了しました。 スクリーンショットでは省いていますが、ブラウザのタブが開いて提出画面にリダイレクトされます。


オプションについて

提出前の確認の有無、あるいは文言のアレンジ

提出はある程度慎重に行いたいものですが、人によっては邪魔かもしれません。 これに関しては、確認の有無と文言をオプションで設定できます。 また、提出可能なコンテストサイトごとに設定でき、デフォルトは以下のように全てのサイトに対して確認が行われます。

" default
let g:oj_helper_submit_confirms = {
    \'atcoder': 'AtCoder: Are you sure you want to submit?',
    \'codeforces': 'Codeforces: Are you sure you want to submit?',
    \'yukicoder': 'yukicoder: Are you sure you want to submit?',
    \'hackerrank': 'HackerRank: Are you sure you want to submit?',
    \}

私の場合、Goの環境違いによりこどふぉでのみオーバーフローで痛い目に会いまくっているので、 こどふぉに関しては提出前に確認をするように設定しています。 また、AtCoderとyukicoderに関しては、確認せずに提出できるようにしています。

" customization
let g:oj_helper_submit_confirms = {
    \'atcoder': '',
    \'codeforces': 'こどふぉだけどオーバーフロー大丈夫?',
    \'yukicoder': '',
    \}

例えばこどふぉの問題に提出しようとすると、以下のような確認がなされます。

f:id:maguroguma:20201119012648p:plain
提出前の確認

他のスクリプト言語コンパイル言語のためのコマンド

デフォルトでいくつかのスクリプト言語のためのコマンドは登録していますが、 必要なものはあとからオプションで追加したり、あるいは上書きできます。

" default
let g:oj_helper_lang_commands = {
      \'go': 'go run',
      \'python': 'python3',
      \'javascript': 'node',
      \}
let g:oj_helper_lang_extensions = {
      \'go': 'go',
      \'python': 'py',
      \'javascript': 'js',
      \}

" customization
let g:oj_helper_lang_commands = {
      \'bash': 'bash',
      \}
let g:oj_helper_lang_extensions = {
      \'bash': 'sh',
      \}

一方でコンパイル言語ですが、、正直競技プログラミングの中でコンパイル作業をしたことがないので、 どういった手段を提供するのがよいのか判断できませんでした。

とりあえず今回は、勝手に以下のような仮定を置いてしまいました。

  1. カレントバッファで開いているファイルを、同じディレクトリ階層にDLしたその問題のサンプルに対してテストしたい。
  2. カレントバッファで開いているファイルと同じディレクトリ階層に、コンパイルされてできた main という実行バイナリが存在している。
  3. :OjExecutableBinTest を実行すると、2のバイナリが1のサンプルに対して実行される。

とりあえず、実行バイナリのファイル名だけはオプションでいじれるようにしました。

" default
let g:oj_helper_executable_binary = 'main'

" customization
let g:oj_helper_executable_binary = 'main.exe'

例えば、Goの例だと以下のスクリーンショットのようになります。

f:id:maguroguma:20201119013534p:plain
バイナリによるテストとディレクトリ構造

他にもいくつかオプションはありますが、これら以外は気にしなくともさほど問題にはならないかなと思います。

おわりに

Vimを使って競技プログラミングを行っている方には、ぜひ使ってみてフィードバックをいただけると大変嬉しいです。 競技プログラミングのメイン言語であるC++に対して使いやすいとはいえないであろう点が懸念ですが。。 しかしながら、ダウンロードと提出コマンドについてはうまくフィットする人も何人かはいるんじゃないかなとも思います。

online-judge-toolsをVimから呼んで楽をする

kmykさんのonline-judge-toolsVimを組み合わせて使い始めてから半年ぐらい経ちました。 それから使い続けて以来、新たに不満は生じず「割と便利な運用なのでは?」と思えるようになってきたので、単純なものではあるものの紹介してみようと思った次第です。

競プロに便利なCUIツールを求めて

とりあえず、以下の2つの課題をなんとかしたいなと思っていました。

1. サンプルのテスト

今となってはちょっと考えられないですが、toolを導入するまでは、サンプルのチェックのために 問題のすべてのサンプルのコピペを繰り返す 、ということをしていました。

デバッグが不要で、一発で通せるぐらい自分にとって易しい問題であればこのコストを受け入れてもいいかもしれません。 しかしながら、コンテストで通すべき問題というのは、ときにはデバッグ出力を何回も確認しながら慎重に実装したり、 WAによってコードの修正とサンプルテストの何回もの繰り返しが余儀なくされるものです。 よって、 自身にとって重要な問題であるほど、このコストは大きくなっていきます。

ですので、 CUIからの一回のコマンドにより、一括で問題ごとのサンプルすべてが検証される」 のが理想的です。

2. コードの提出

tool導入前は、 「エディタのコードをコピーして、問題の提出欄にペーストし、選択言語が正しいことを確認してからボタンを押下する」 という作業をしていました。

サンプルのテストほどではないですが、これもいくつかの手順があり、更に問題になるのは以下のような事項だと思います。

  1. 選択言語を間違えてCEしてしまう(単純に時間の無駄)。
  2. 提出先の問題を間違えてREもしくはWAしてしまう(最終的にペナになる可能性があり最悪)。
  3. ブザービートに失敗する(レアケースといえばレアケースだが、逃した時のショックは大きそう)。
  4. コードのコピペをミスる(Vimだと普通にコピペするとクリップボードに載らない*1)。

よって、 「確実に今自分が目に入れているエディタのコードを、正しい問題・正しい選択言語で提出できる」 のが理想的です。

できるだけシンプルなツールを求めて

一応、atcoder-toolsの存在は知っていたのですが、 一見したところ「C++Pythonといった競プロメジャー言語に寄っているっぽい(他の言語は使えない or 使いづらい?)」 とか「特定のディレクトリ構成が強要されるっぽい(逸脱しようとすると凝ったことをしないとダメそう or 調査は必須)」 という印象を持ち、ちょっと自分の要件には合わないかなぁと思っていました*2

結局、頑張って自分用に自作していたのですが*3、 ふとしたきっかけでonline-judge-tools の存在を知り、また自分の求めているものにかなりマッチしていると気づきました。

  • サンプルのダウンロード: oj download -d {{target_directory}} {{problem_url}}
    • オプションでダウンロード先を簡単に変更できるのが嬉しい。
  • サンプルのテスト: oj test -c "go run {{target_program}}" -d {{sample_directory}} -t 4 (Goの場合)
    • オプションで実行コマンドを変えられるので、他言語の対応も簡単そう。
  • コードの提出: oj submit -y {{problem_url}} {{target_source_file}}
    • 提出言語を推定してくれるので、ヒューマンエラーがない。

また、AtCoderのみならず、Codeforces、yukicoder、AOJといった主要なサイトに対応しているのも、非常にありがたいですね。

Vimから呼び出せるよう、連携しようという試み

私は普段エディタにVim(厳密にはneovimですが)を使っており、またVimの利点として 「ターミナルやCUIとの距離感が近い」 というものがあると思っています。 個人的には、他のエディタに比べて、CUIツールとの連携が簡単にできるのではないかと感じています。

よって、 「先述のojコマンドをいい感じに呼び出すVimのコマンドを定義すること」 を目指します。

仕様

Vimコマンドラインモード(コロン打ったら遷移するモード)から、以下のコマンドを打てるようにします。

  • サンプルのダウンロードコマンド: :DonwloadSamples
    • コマンドを実行すると、 今エディタに載っている問題のサンプルが同じディレクトリ階層にDLされる。
      • 例えばコンテスト中のコードは contests/2020/08/20200815_ABC175/a/a.go みたいに整理しているのですが、この問題のサンプルは contests/2020/08/20200815_ABC175/a/test/ ディレクトリに収まってほしい、という具合です。
  • サンプルのテストコマンド: :TestCurrentBuffer
    • コマンドを実行すると、 今エディタに載っているコードに対してすべてのサンプルが検証される。
      • 先程DLしたものが素直に実行されてほしい、という具合です。
  • コードの提出コマンド: :SubmitCode
    • コマンドを実行すると、 今エディタに載っているコードが対応する問題に対して提出される。
      • 検証が済んだらそのままの流れでシームレスに提出まで持っていきたい、という具合です。

コマンドのデモ

各コマンドの動作イメージは、以下のようなものになります。

f:id:maguroguma:20200819004910g:plain
サンプルのダウンロード

f:id:maguroguma:20200819004818g:plain
サンプルのテスト

f:id:maguroguma:20200819005716g:plain
コードの提出

各コマンドを定義するVim script

各コマンドについて1つずつ観ていきます。

" ファイル上部に記述される「問題のURL」を取得する関数
function! s:ReadProblemURLFromCurrentBuffer()
  let l:lines = getline(0, line("$"))
  for l:line in l:lines
    let l:record = split(l:line, ' ')
    for l:r in l:record
      let l:url = matchstr(r, '^\(http\|https\):.*$')
      if l:url != ''
        return l:url
      endif
    endfor
  endfor
  return ''
endfunction

はい、いきなり 「コンテスタントの運用でカバー」 的な要素があります。 この関数は、 現在ロードしているソースファイルの上部に「問題のURL」が記載されていることを期待 しています。

最初は、コマンドの引数に問題のURLを渡す設計で考えていたのですが、 このURLはコード提出時にも必要になることから、 「ファイル中のコメントとしてはじめに一度だけペーストしてしまうほうが、以降の手間もミスもなくなって良いのではないか?」 と思い、このようにしました。

なので、私の競プロのルーティンとして 「問題を開いたらURLをファイルのトップにコピーする」 というものが組み込まれることとなりました*4

そして、サンプルのダウンロードコマンドが以下になります。

" サンプルダウンロードのための関数とコマンド
function! s:MakeSampleDLCommand(url)
  let l:cur_buf_dir = expand("%:h")
  let l:target_dir = l:cur_buf_dir . "/test"
  let l:dl_command = printf("oj download -d %s %s", l:target_dir, a:url)
  return l:dl_command
endfunction
function! s:DownloadSamples(url)
  let l:command = s:MakeSampleDLCommand(a:url)
  echo "[Run] " . l:command . "\n"
  call execute('vs')
  call execute('terminal ' . l:command)
endfunction

command! -nargs=0 DownloadSamples :call s:DownloadSamples(s:ReadProblemURLFromCurrentBuffer())

やっていることは、 Vim scriptで本来ターミナルで実行したいコマンドを組み立てて、Vimtarminal コマンドに渡して実行させている」 、というだけです。 以降のコマンドでもそうですが、 system() 関数で実行し結果を echo するよりも、 見栄え的にこちらのほうがいい感じです(多分)。

続いて、ダウンロードしたサンプルの実行コマンドです。

" サンプルテストのための関数とコマンド
function! s:MakeTestSamplesCommand()
  let l:cur_buf_go = expand("%")
  let l:cur_buf_dir = expand("%:h")
  let l:sample_file_dir = l:cur_buf_dir . "/test"
  let l:test_command = printf("oj test -c \"go run %s\" -d %s -t 4", l:cur_buf_go, l:sample_file_dir)
  return l:test_command
endfunction
function! s:TestSamples()
  let l:command = s:MakeTestSamplesCommand()
  echo "[Run] " . l:command . "\n"
  call execute('vs')
  call execute('terminal ' . l:command)
endfunction

" Go版テスト実行コマンド
command! -nargs=0 TestCurrentBufferGoCode :call s:TestSamples()

これも、コマンドの組み立て部分が微妙に変わっただけで、ダウンロードとほとんど変わらないですね。 実行コマンドを差し替えたものを用意すれば、他の好きな言語の実行コマンドも作れると思います*5

最後に、コードの提出コマンドになります。

" コード提出のための関数とコマンド定義
function! s:MakeSubmitCommand(url)
  let l:cur_buf_go = expand("%")
  let l:submit_command = printf("oj submit -y %s %s", a:url, l:cur_buf_go)
  return l:submit_command
endfunction
function! s:SubmitCode(url)
  let l:command = s:MakeSubmitCommand(a:url)
  echo "[Run] " . l:command . "\n"
  call execute('vs')
  call execute('terminal ' . l:command)
endfunction

command! -nargs=0 SubmitCode :call s:SubmitCode(s:ReadProblemURLFromCurrentBuffer())

サンプルのダウンロードの際に必要となったURLが、ここでも必要となります。

以上で紹介したコマンドや関数は、すべてojが実行可能であることを前提としたものですので、 スクリプトファイルとするにあたっては、以下のように実行可能時のみ定義するようにするのが良いかと思います。

if executable('oj')
  " ファイル上部に記述される「問題のURL」を取得する関数
  function! s:ReadProblemURLFromCurrentBuffer()
  ...
  command! -nargs=0 SubmitCode :call s:SubmitCode(s:ReadProblemURLFromCurrentBuffer())
endif

最後に

もはやAtCoder Problemsと同じくらい「これがなきゃ競プロやってらんねぇ」なツールになってきたので、 感謝するだけじゃなくcommitできるようコード読まないとなぁと思います。

kmykさんおよびコミッタの皆様、本当にありがとうございます。

あと、これくらい簡単なVim scriptが書けるだけでも、自分用の便利コマンドは案外簡単に作れたりするので、ぜひVimを使いましょう!

*1:設定で、Vim内のコピー先をクリップボードと共有することはできますが、個人的に好きじゃないのでその点はデフォルトのままとしています。そのせいで以前に一度、直前の問題のコードを間違って貼って提出し、REしてペナを貰うというのをやったことがあります

*2:提示されているデフォルトの使用方法がマッチしているという方には、とても便利なツールなのだと思います。

*3:大方の機能は実装できたのですが、古いARCの問題のクローリングで早々とコケてしまい、途方に暮れていたところojに出会いました(圧倒的感謝)。

*4:案外気にならない上に、何度も提出する必要がある難しい問題になるほど、恩恵は大きくなります。後は、問題の復習をするときにコードからすぐに問題ページを開けるのもよいです。

*5:たまにBashの練習に競プロを使ったりするので、Bashバージョンも持っていたりします。

Goで再帰関数による全方位木DPを(可能な限り)抽象化

次に出題されたら絶対に落としたくないという気持ちから、再帰関数による全方位木DPを抽象化したコードを書いてみました。

セグメント木の際と同様に、型 T を都度書き換えないと駄目なのがかっこ悪いですが。。 どなたかいい方法を御存知でしたら教えて下さい。

type T int

type ReRooting struct {
    n int
    G [][]int

    ti      T
    dp, res []T
    merge   func(l, r T) T
    addNode func(t T, idx int) T
}

func NewReRooting(
    n int, AG [][]int, ti T, merge func(l, r T) T, addNode func(t T, idx int) T,
) *ReRooting {
    s := new(ReRooting)
    s.n, s.G, s.ti, s.merge, s.addNode = n, AG, ti, merge, addNode
    s.dp, s.res = make([]T, n), make([]T, n)

    s.Solve()

    return s
}

func (s *ReRooting) Solve() {
    s.inOrder(0, -1)
    s.reroot(0, -1, s.ti)
}

func (s *ReRooting) Query(idx int) T {
    return s.res[idx]
}

func (s *ReRooting) inOrder(cid, pid int) T {
    res := s.ti

    for _, nid := range G[cid] {
        if nid == pid {
            continue
        }

        res = s.merge(res, s.inOrder(nid, cid))
    }
    res = s.addNode(res, cid)
    s.dp[cid] = res

    return s.dp[cid]
}

func (s *ReRooting) reroot(cid, pid int, parentValue T) {
    childValues := []T{}
    nexts := []int{}
    for _, nid := range G[cid] {
        if nid == pid {
            continue
        }
        childValues = append(childValues, s.dp[nid])
        nexts = append(nexts, nid)
    }

    // result of cid
    rootValue := s.ti
    for _, v := range childValues {
        rootValue = s.merge(rootValue, v)
    }
    rootValue = s.merge(rootValue, parentValue)
    rootValue = s.addNode(rootValue, cid)
    s.res[cid] = rootValue

    // for children
    accum := s.merge(s.ti, parentValue)
    length := len(childValues)
    if length == 0 {
        return
    }
    if length == 1 {
        s.reroot(nexts[0], cid, s.addNode(accum, cid))
        return
    }

    // cid has more than one child
    R, L := make([]T, length), make([]T, length)
    L[0] = s.merge(s.ti, childValues[0])
    for i := 1; i < length; i++ {
        L[i] = s.merge(L[i-1], childValues[i])
    }
    R[length-1] = s.merge(s.ti, childValues[length-1])
    for i := length - 2; i >= 0; i-- {
        R[i] = s.merge(R[i+1], childValues[i])
    }

    for i, nid := range nexts {
        if i == 0 {
            s.reroot(nid, cid, s.addNode(s.merge(accum, R[1]), cid))
        } else if i == length-1 {
            s.reroot(nid, cid, s.addNode(s.merge(accum, L[length-2]), cid))
        } else {
            s.reroot(nid, cid, s.addNode(s.merge(accum, s.merge(L[i-1], R[i+1])), cid))
        }
    }
}

参考

ei1333さんによる全方位木DPの解説記事

ABC160-Fのすぬけさんによる解説

お二人の解説によって、全方位木DPがすっきりと理解できました。 解説を読んだ(聴いた)後、まずは抽象化を考えずに、素直にDFSを2回やる手法で、アドホックなコードを書いてみました。

いきなり抽象化から入るのは大変かもしれないので、まずはこれらを参照するのが良いかと思います。

keymoonさんによる全方位木DPの抽象化解説記事

こちらの記事を受けてGoによる実装(写経)を書いてみることで、 今回の再帰関数による抽象化も書くことができました。 keymoonさん、ありがとうございます!

Goでセグメントツリーを(可能な限り)抽象化

セグメントツリーをもう少し取り回しが効くようにしたいなぁと思った*1ので、 他の方々のブログ等を参考にしながら書き直してみました*2

実装

詳細は後述しますが、tsutajさん・ei1333さん・beetさんのお三方の解説を大いに参考にさせていただきました。

変数名やメソッド名はそれぞれの記事から拝借しているため、若干キメラになっていて読みにくいかもしれません。

また、数学的な側面の理解が浅いので、モノイド・作用素モノイド周りの命名が特に気持ち悪いかもしれません*3

通常(遅延伝搬なし)

type T int // (T, f): Monoid

type SegmentTree struct {
  sz   int              // minimum power of 2
  data []T              // elements in T
  f    func(lv, rv T) T // T <> T -> T
  ti   T                // identity element of Monoid
}

func NewSegmentTree(
  n int, f func(lv, rv T) T, ti T,
) *SegmentTree {
  st := new(SegmentTree)
  st.ti = ti
  st.f = f

  st.sz = 1
  for st.sz < n {
    st.sz *= 2
  }

  st.data = make([]T, 2*st.sz-1)
  for i := 0; i < 2*st.sz-1; i++ {
    st.data[i] = st.ti
  }

  return st
}

func (st *SegmentTree) Set(k int, x T) {
  st.data[k+(st.sz-1)] = x
}

func (st *SegmentTree) Build() {
  for i := st.sz - 2; i >= 0; i-- {
    st.data[i] = st.f(st.data[2*i+1], st.data[2*i+2])
  }
}

func (st *SegmentTree) Update(k int, x T) {
  k += st.sz - 1
  st.data[k] = x

  for k > 0 {
    k = (k - 1) / 2
    st.data[k] = st.f(st.data[2*k+1], st.data[2*k+2])
  }
}

func (st *SegmentTree) Query(a, b int) T {
  return st.query(a, b, 0, 0, st.sz)
}

func (st *SegmentTree) query(a, b, k, l, r int) T {
  if r <= a || b <= l {
    return st.ti
  }

  if a <= l && r <= b {
    return st.data[k]
  }

  lv := st.query(a, b, 2*k+1, l, (l+r)/2)
  rv := st.query(a, b, 2*k+2, (l+r)/2, r)
  return st.f(lv, rv)
}

func (st *SegmentTree) Get(k int) T {
  return st.data[k+(st.sz-1)]
}

おそらくは、モノイドの定義( T, f, ti )を適切に書き換えることだけに注力すれば、うまく動くのではないかと思います。 AOJにある典型例(RMQ, RSQ)は検証済みです*4

例: yukicoder No.875 Range Mindex Query

問題のURL

yukicoderの解説にもある通り、 最小値に加えて、最小値が入っているインデックスをもたせた構造体を要素の型とすればOKです。

以下はコードの抜粋です(提出はこちら)。

type T struct {
    v   int
    idx int
}

func main() {
    n, q := ReadInt2()
    A := ReadIntSlice(n)

    f := func(lv, rv T) T {
        t := T{}
        if lv.v < rv.v {
            t.v = lv.v
            t.idx = lv.idx
        } else {
            t.v = rv.v
            t.idx = rv.idx
        }
        return t
    }
    ti := T{v: 1<<31 - 1, idx: -1}
    st := NewSegmentTree(n, f, ti)
    for i := 0; i < n; i++ {
        st.Set(i, T{v: A[i], idx: i})
    }
    st.Build()

    for i := 0; i < q; i++ {
        c, l, r := ReadInt3()
        if c == 1 {
            ol := st.Get(l - 1)
            or := st.Get(r - 1)
            ol.idx, or.idx = or.idx, ol.idx
            st.Update(l-1, or)
            st.Update(r-1, ol)
        } else {
            e := st.Query(l-1, r)
            fmt.Println(e.idx + 1)
        }
    }
}

遅延伝搬あり

// Assumption: T == E
type T int // (T, f): Monoid
type E int // (E, h): Operator Monoid

type LazySegmentTree struct {
  sz   int
  data []T
  lazy []E
  f    func(lv, rv T) T        // T <> T -> T
  g    func(to T, from E) T    // T <> E -> T (assignment operator)
  h    func(to, from E) E      // E <> E -> E (assignment operator)
  p    func(e E, length int) E // E <> N -> E
  ti   T
  ei   E
}

func NewLazySegmentTree(
  n int,
  f func(lv, rv T) T, g func(to T, from E) T,
  h func(to, from E) E, p func(e E, length int) E,
  ti T, ei E,
) *LazySegmentTree {
  lst := new(LazySegmentTree)
  lst.f, lst.g, lst.h, lst.p = f, g, h, p
  lst.ti, lst.ei = ti, ei

  lst.sz = 1
  for lst.sz < n {
    lst.sz *= 2
  }

  lst.data = make([]T, 2*lst.sz-1)
  lst.lazy = make([]E, 2*lst.sz-1)
  for i := 0; i < 2*lst.sz-1; i++ {
    lst.data[i] = lst.ti
    lst.lazy[i] = lst.ei
  }

  return lst
}

func (lst *LazySegmentTree) Set(k int, x T) {
  lst.data[k+(lst.sz-1)] = x
}

func (lst *LazySegmentTree) Build() {
  for i := lst.sz - 2; i >= 0; i-- {
    lst.data[i] = lst.f(lst.data[2*i+1], lst.data[2*i+2])
  }
}

func (lst *LazySegmentTree) propagate(k, length int) {
  if lst.lazy[k] != lst.ei {
    if k < lst.sz-1 {
      lst.lazy[2*k+1] = lst.h(lst.lazy[2*k+1], lst.lazy[k])
      lst.lazy[2*k+2] = lst.h(lst.lazy[2*k+2], lst.lazy[k])
    }
    lst.data[k] = lst.g(lst.data[k], lst.p(lst.lazy[k], length))
    lst.lazy[k] = lst.ei
  }
}

func (lst *LazySegmentTree) Update(a, b int, x E) T {
  return lst.update(a, b, x, 0, 0, lst.sz)
}

func (lst *LazySegmentTree) update(a, b int, x E, k, l, r int) T {
  lst.propagate(k, r-l)

  if r <= a || b <= l {
    return lst.data[k]
  }

  if a <= l && r <= b {
    lst.lazy[k] = lst.h(lst.lazy[k], x)
    lst.propagate(k, r-l)
    return lst.data[k]
  }

  lv := lst.update(a, b, x, 2*k+1, l, (l+r)/2)
  rv := lst.update(a, b, x, 2*k+2, (l+r)/2, r)
  lst.data[k] = lst.f(lv, rv)
  return lst.data[k]
}

func (lst *LazySegmentTree) Query(a, b int) T {
  return lst.query(a, b, 0, 0, lst.sz)
}

func (lst *LazySegmentTree) query(a, b, k, l, r int) T {
  lst.propagate(k, r-l)

  if r <= a || b <= l {
    return lst.ti
  }

  if a <= l && r <= b {
    return lst.data[k]
  }

  lv := lst.query(a, b, 2*k+1, l, (l+r)/2)
  rv := lst.query(a, b, 2*k+2, (l+r)/2, r)
  return lst.f(lv, rv)
}

func (lst *LazySegmentTree) Get(k int) T {
  return lst.Query(k, k+1)
}

大抵はそうだろうということで、混乱しないように Assumption: T == E みたいなことを書いてしまいました。 しかし、次の例に示すように、別にそうとも限らないですね。。

こちらもモノイド、作用素モノイド、 そしてそれらに関する関数オブジェクトを適切に決定することに注力しさえすればいいように書いたつもりです。

例: yukicoder No.876 Range Compress Query

問題のURL

yukicoderの解説での想定解法は「階差数列に着目して区間加算を2箇所の点加算で済むようにする」 というようなもの*5のようです。 しかし、区間加算を真に受けて遅延伝搬セグメントツリーでも解けます。

与えられた定義で計算される圧縮値の他、区間の両端の値をもたせた構造体を要素の型とすればOKです。 単位元は少し注意が必要です。

以下はコードの抜粋です(提出はこちら)。

const INF_BIT60 = 1 << 60

func main() {
    n, q := ReadInt2()
    A := ReadIntSlice(n)

    f := func(lv, rv T) T {
        t := T{}
        t.v = lv.v + rv.v
        if lv.r >= INF_BIT60 || rv.l >= INF_BIT60 {
        } else if lv.r != rv.l {
            t.v++
        }
        t.l, t.r = lv.l, rv.r
        return t
    }
    g := func(to T, from E) T {
        to.l += int(from)
        to.r += int(from)
        return to
    }
    h := func(to, from E) E {
        return to + from
    }
    p := func(e E, length int) E {
        return e
    }
    ti := T{v: 0, l: INF_BIT60, r: INF_BIT60}
    ei := 0
    lst := NewLazySegmentTree(n, f, g, h, p, ti, E(ei))

    for i := 0; i < n; i++ {
        lst.Set(i, T{v: 0, l: A[i], r: A[i]})
    }
    lst.Build()

    for i := 0; i < q; i++ {
        c := ReadInt()
        if c == 1 {
            l, r, x := ReadInt3()
            lst.Update(l-1, r, E(x))
        } else {
            l, r := ReadInt2()
            t := lst.Query(l-1, r)
            fmt.Println(t.v + 1)
        }
    }
}

type T struct {
    v, l, r int
}

type E int

参考

学習の高速道路が整備されていてありがたいなぁと感じました。

tsutajさんの解説

tsutajさんの解説記事(遅延伝搬なし)

tsutajさんの解説記事(遅延伝搬あり)

いずれもとてもわかりやすく、初学時にセグメントツリーの仕組みを理解するのにはかどりました*6

セグメント木の抽象化だけに絞るのであれば、tsutajさんのブログを理解すれば十分な気がします。

ei1333さん・beetさんの解説

ei1333さんの旧ブログ記事での解説

beetさんの旧記事での解説

遅延伝搬セグメントツリーの抽象化は独力ではできる気がしなかったため、非常に参考になりました。 お二方とも旧ブログの方を参照してしまって恐縮です。 特にbeetさんの記事の方は本当に丁寧に説明されていてわかりやすかったです。


少数の定義を渡すだけで正しく動いてくれて感動したので、個人的には満足しています。

まだ解いた問題が少なすぎるので「これでOK」とは言い難いですが、 とりあえずは運用して様子見してみようと思います。

*1:解説で「セグメントツリーでも解けます」とあるときにテンション下がるのは嫌ですよね。

*2:言語を変えただけで、基本的に写経です。

*3:アドリブでいじるときに、自分にとって意味を思い出しやすいように意識して書いたらこうなりました

*4:Tの型が複雑になるときのインスタンス化の速度への影響が、まだ十分に検証しきれていません。

*5:そちらの解法で解き直していないので間違っているかもしれません。

*6:蟻本だけでは不安だったところを補完するのに活用させていただきました

Codeforces Round No.602 Div.2 D2復習

コンテスト中に解けなかったものの復習です。

いろいろな解法(というよりも解くために用いるツールが多様)がありますが、 BITを使った方法が一番自分にとって与し易かったため、BITで解きました。

D2. Optimal Subsequences (Hard Version)

問題のURL

問題

n 要素からなる数列 A が与えられる。

この数列に対して部分列(間の要素を好きなだけ削除し、残ったものの順番を変えずに得られる数列)を考える。

ある部分列の長さ k が与えられたとき、以下の条件を満たす部分列はoptimalであるという。

  1. 考えられる長さ k のあらゆる部分列の中で、部分列の要素の総和が最大となる。
  2. 1の条件を満たす部分列の中で、元の数列の位置に関して辞書順最小である。

一方で、 m 個のクエリが与えられる。

各クエリは k, pos の2つの1以上の整数からなり、このクエリに対して、 「長さ k のoptimalな部分列における pos 番目の値」を答える必要がある。

すべてのクエリに対して、それらの順番どおりに答えよ。

制約:

  • 1 <= n, m <= 2*10^5
  • 1 <= A[i] <= 10^9
  • 1 <= k <= n, 1 <= pos <= k

解答

Easyバージョンは制約が小さいため、愚直な解法で通りますが、こちらは賢くクエリを処理する必要があります。

まず整理すると、 1の条件よりoptimalな部分列は、元の数列を降順にソートしその先頭 k 個の数を選択したものとなります。 ただし、2の条件より、同じ要素が元の数列に複数存在する場合、できるだけ元の数列において前の方の位置に登場したものを優先的に選ぶ必要があります。

よって、元の数列 A を、まずは要素の大きさを基準に降順となるようにし、値が同じ場合は元の数列における位置に関して昇順となるようにソートします。 各クエリに答えるためには、まずこのソートした列に対して、先頭の k 要素を取得します。 そして、取得した k 要素の中から、位置に関して pos 番目に小さい要素の値を出力すればOKです。

f:id:maguroguma:20200104015921j:plain
optimal subsequenceの求め方

ただし、これを愚直に行うためには、 k 要素取得するたびにそれらを位置に関して昇順ソートする必要があります。 これは許容できないため、工夫が必要です。

まず、クエリをすべて先読みし、 k が小さい順に答えていくという工夫ができます。 こうすることで、(許されるなら)ソートしたい集合が、単純に新しい要素がappendされていくだけとなり、シンプルになります。

しかしながら、それでも k が大きくなるたびにソートするわけには行かないため、 「要素の追加」と「特定の順番の値の取得」を高速に行う必要があります。

このような操作は「BIT上の二分探索」を活用することで可能なため(詳しくは後述)、各クエリを O(logn) で処理できます。

よって、全体で O(m*logn) で解くことができます。

※1500msecぐらいかかりました。

※Sorterがうざったいかもしれませんが、AtCoderと共通化したいため、このようにしています(こどふぉのGoはバージョンが新しいので実際はもっとスマートに書けるはずです。)

var n int
var A []int
var m int

type BinaryIndexedTree struct {
    bit     []int
    n       int
    minPow2 int
}

// n(>=1) is number of elements of original data
func NewBIT(n int) *BinaryIndexedTree {
    newBit := new(BinaryIndexedTree)

    newBit.bit = make([]int, n+1)
    newBit.n = n

    newBit.minPow2 = 1
    for {
        if (newBit.minPow2 << 1) > n {
            break
        }
        newBit.minPow2 <<= 1
    }

    return newBit
}

// Sum of [1, i](1-based)
func (b *BinaryIndexedTree) Sum(i int) int {
    s := 0

    for i > 0 {
        s += b.bit[i]
        i -= i & (-i)
    }

    return s
}

// Add x to i(1-based)
func (b *BinaryIndexedTree) Add(i, x int) {
    for i <= b.n {
        b.bit[i] += x
        i += i & (-i)
    }
}

// LowerBound returns minimum i such that bit.Sum(i) >= w.
func (b *BinaryIndexedTree) LowerBound(w int) int {
    if w <= 0 {
        return 0
    }

    x := 0
    for k := b.minPow2; k > 0; k /= 2 {
        if x+k <= b.n && b.bit[x+k] < w {
            w -= b.bit[x+k]
            x += k
        }
    }

    return x + 1
}

func main() {
    n = ReadInt()
    A = ReadIntSlice(n)
    m = ReadInt()

    // クエリを先読みしてkで昇順ソート
    L := make(QueryList, 0)
    for i := 0; i < m; i++ {
        k, pos := ReadInt2()
        L = append(L, &Query{id: i, k: k, pos: pos}) // idは0-basedで格納
    }
    sort.Stable(L)

    // Aを値で降順→位置で昇順にソート
    S := make(ElementList, 0)
    for i := 0; i < n; i++ {
        S = append(S, &Element{val: A[i], pos: i}) // posは0-basedで格納
    }
    sort.Stable(S)

    // BITをOrderedSetとして扱う
    bit := NewBIT(n)
    ck := 0
    // クエリの回答保持用
    answers := make([]int, m)
    // クエリをkの小さい順に処理していく
    for i := 0; i < m; i++ {
        q := L[i]
        // BITに格納した要素数がk個になるまで追加する
        for ; ck < q.k; ck++ {
            e := S[ck]
            bit.Add(e.pos+1, 1)
        }

        // BIT中のpos番目を回答する
        ans := bit.LowerBound(q.pos)
        answers[q.id] = A[ans-1]
    }

    // まとめて回答
    for i := 0; i < m; i++ {
        fmt.Println(answers[i])
    }
}

type Query struct {
    id, k, pos int
}
type QueryList []*Query

func (l QueryList) Len() int {
    return len(l)
}
func (l QueryList) Swap(i, j int) {
    l[i], l[j] = l[j], l[i]
}

func (l QueryList) Less(i, j int) bool {
    return l[i].k < l[j].k
}

type Element struct {
    val, pos int
}
type ElementList []*Element

func (l ElementList) Len() int {
    return len(l)
}
func (l ElementList) Swap(i, j int) {
    l[i], l[j] = l[j], l[i]
}

func (l ElementList) Less(i, j int) bool {
    if l[i].val > l[j].val {
        return true
    } else if l[i].val < l[j].val {
        return false
    } else {
        return l[i].pos < l[j].pos
    }
}

BITを使って k 番目の要素を取得するテクニック

今回行ったような操作は競技プログラミングにおいては典型テクニックのようで、 例えばけんちょんさんのQiitaの記事などでも 詳しく解説されています(他にも色々わかりやすくまとめている方がたくさんおられました)。

今回は、位置に関してBITで管理するため、要素数の制約から座標圧縮する必要はありませんでした。

BIT上の二分探索とは?

hosさんのBIT解説PDFにおいて最後の方で説明がなされています。

。。が、自分には最初何をやっているのかよくわかりませんでした。

自分なりに議論を補間しつつゆっくりと追っていくと理解できたので、忘れた頃の未来の自分を第一の対象として、理解の道筋を残しておこうと思います。

まず、「BIT上の二分探索ってそもそも何?」となってしまいましたが、これは「元の配列の先頭からの累積和に関する二分探索」となります。 別の表現をすると 「1-basedなインデックス i で、 [1, i] の要素の総和が w 以上となる最小の i を探索する」 といえます。

二分探索自体の計算量が対数オーダーで、BITを使って累積和を求めるのも対数オーダーであるため、 計算量が log の2乗になるというのは納得できます。

しかし、BITの木構造をうまく利用することで、この二分探索も全体で O(logn) に落とすことができる、とのことです。 それとともに与えられたアルゴリズムが以下のものですが、これまた初見時はよくわかりませんでした。

func (b *BinaryIndexedTree) LowerBound(w int) int {
    if w <= 0 {
        return 0
    }

  // b.minPow2は、n以下の最小の2べき
  x := 0
    for k := b.minPow2; k > 0; k /= 2 {
        if x+k <= b.n && b.bit[x+k] < w {
            w -= b.bit[x+k]
            x += k
        }
    }

    return x + 1
}

これは要約すると、「先頭からの累積和を、できるだけ長い区間から足して良いかを都度判断する」ということを行っています。

流れとしては、BITの上方の区間が長いノードから順番に見ており、 k というのは現在注目している区間の長さを意味しています。

区間は、担当する区間の和を持っており、それがkey値 w よりも小さい場合は、足してから右側の次の短い長さの区間を見る必要があります。 逆にkey値よりも大きい場合は、その区間和は足さずに左側の次の短い長さの区間を見る必要があります。

以下は、ある具体例におけるアルゴリズムの様子を図示したものです(あまりわかりやすくできませんでしたが。。)。

f:id:maguroguma:20200104020050j:plain
BIT上の二分探索アルゴリズムの様子

結局、木の高さ分下ることで探索が終了するため、計算量は O(logn) となります。


クエリの先読みと、 k 番目に小さい要素の取得、という2つの典型テクニックが要求される問題だったと思います。

引用した記事でも言及されている平衡二分探索木についても、なるべく早く実装してみたいと思います。

次に出会ったときはちゃんと倒したいところです。

Codeforces Round No.594 Div.2 C復習

以前コンテストに参加して解けなかったものの復習です。

公式Editorialがハイコンテクスト過ぎてよくわからなかったのと、 数え上げの方法の典型度合いがものすごく高い気がしたので、別記事として書きました。

C. Ivan the Fool and the Probability Theory

問題のURL

問題

nm 列からなるグリッドを、黒・白の2色で塗り分けることを考える。

ただし、塗り方は「辺に関して隣接しているグリッドについて、同じ色の隣接グリッドがたかだか1つまで」とする。

このような塗り方は何通り存在するか、 10^9 + 7 で割ったあまりで答えよ。

解答

一見複雑だが、「左上から少数のグリッドの色を確定させると、他のグリッドの色は自動的に決まる」というようなことはよくある(と思う)。

とりあえず、1行目を条件に反しないように適当に塗ってみると(同じ色が連続するのは2回までとする)、 以下の図のように、同じ色が連続してしまうと、その列を中心として次の行は一意に定まってしまう。

f:id:maguroguma:20200102215055j:plain
1行目で同じ色が連続する場合

よって、このようなバターンの総数を数え上げる必要がある(※)。

また、同じ色が連続せずに、黒・白が交互に塗られる場合、 以下の図のように、次の行の1列目の色を決めた時点で、他の列の色が確定してしまう。

f:id:maguroguma:20200102215123j:plain
1行目で異なる色が交互に塗られる場合

よって、このような場合も結局、1列目の色の塗り方の総数を数え上げる必要があり、 これは、(※)の部分と同じようにして数え上げることができる。

黒・白が2つまで連続して良いという条件のもとでの、1次元グリッドの塗り分けの総数を求めることに集中できる。

とりあえず、最初の色を黒として樹形図を書いてみる。 以下の図に示すように、よくよく観察すると、 色に関係なく2つ前と1つ前の通り数の和となるように遷移する(フィボナッチ数列)ため、 dp[i-2] + dp[i-1] = dp[i] のようにまとめられる。

f:id:maguroguma:20200102215212j:plain
DPによる数え上げ

以上をもとにコーディングしていく。

同じ色が隣接することがない塗り方1通りを2重に数えない、 左上を白とした場合も数えるために2倍する、あたりを忘れないように注意する。

var n, m int64
var dp [100000 + 5]int64

func main() {
    n, m = ReadInt64_2()

    dp[0], dp[1] = 1, 2
    for i := 2; i <= 100000+3; i++ {
        dp[i] = dp[i-1] + dp[i-2]
        dp[i] %= MOD
    }

    var ans int64
    ans = dp[m-1] - 1
    ans += dp[n-1]
    ans %= MOD
    ans *= 2
    ans %= MOD

    fmt.Println(ans)
}

上記のフィボナッチ数を考えるあたりって自明なんでしょうか? 自分にはあまり自明には感じられないので、説明がかなり冗長かもしれません。

Codeforces Round No.609 Div.2 参加記録 (A〜D解答)

青になれました!やったね!

f:id:maguroguma:20191222030152p:plain

思ったより長い戦いだった。。

Codeforcesの青はAtCoderの水色」ぐらいの言説を見た気がするので、 「まぁ青ぐらいなら楽勝だろう」と思ったのですが、想像の3倍ぐらいは難しかったです。

多分青を維持するのは今の自分にはきつくて、 Codeforcesの1600はAtCoderの1400(水色の真ん中)ぐらいなんだろうなぁと感じています。

とはいえ、ミスは減ってきて実装力も向上しているとは思うので、 今後もしばらくはこの調子で頑張りたいところです。

A. Equation

問題のURL

解答

式変形すると a = n + b であるため、小さい方である b が決まれば a も自然と決まる。 そして、 a, b がともに合成数になるようにする。

2 以外の偶数はすべて合成数であることを踏まえると、

  1. n が偶数ならば、 b を適当な 2 以上の偶数とすれば n + b も当然 2 以上の偶数となる。
  2. n が奇数ならば、 b を適当な合成数である奇数とすれば n + b2 以上の偶数となる。

であり、 a, b を選択できる。

var n int

func main() {
    n = ReadInt()

    if n%2 == 0 {
        b := 4
        a := n + b
        fmt.Println(a, b)
    } else {
        b := 9
        a := n + b
        fmt.Println(a, b)
    }
}

こんな問題に9分もかかってしまいました。

というより、公式Editorialを見ると、「9*n, 8*n でOK」とのこと、たしかに。

こどふぉのDiv2のA問題って、 O(1) 算数をしないといけなかったり、真面目に全探索しないといけなかったりで、 なかなか難しいです。

簡単と思える日が来てほしい。

B. Modulo Equality

問題のURL

解答

A, B それぞれについて、登場する値のカウントをメモしておく。

答えが x のとき、すべての A[i] に対して、 (AにおけるA[i]の個数) == (Bにおける(b = (A[i] + x) % m)の個数) となっている必要がある。

よって、このような x としてあり得るものをすべて列挙し、 それが条件を満たすか確かめれば良い。 ただし、求められている x は条件を満たす最小のものであるため、見つけるたびに小さい方で更新する。

x としてありうるものは、ある適当な A の値(以下のコード中では A[0] としている)を取り出し、 これが B のどの要素に遷移するのか?を考えることで列挙できる。

また、各 x に対して、すべての A の要素の遷移先の個数が、 A の遷移前の個数と一致するかをチェックすれば良い。

以上より、トータルの計算量は O(n^2) となり、十分高速である。

var n, m int
var A, B []int

func main() {
    n, m = ReadInt2()
    A = ReadIntSlice(n)
    B = ReadIntSlice(n)

    amemo, bmemo := make(map[int]int), make(map[int]int)
    for i := 0; i < n; i++ {
        amemo[A[i]]++
        bmemo[B[i]]++
    }

    ans := -1
    aval, anum := A[0], amemo[A[0]]
    for bval, bnum := range bmemo {
        if anum != bnum {
            continue
        }

        var x int
        if bval > aval {
            x = bval - aval
        } else {
            x = bval + m - aval
        }

        isOK := true
        for av, an := range amemo {
            bv := (av + x) % m
            bn := bmemo[bv]
            if an == bn {
                continue
            } else {
                isOK = false
                break
            }
        }

        if isOK {
            if ans == -1 {
                ans = x
            } else {
                ChMin(&ans, x)
            }
        }
    }

    if ans == m {
        ans = 0
    }

    fmt.Println(ans)
}

A[i], B[i] の範囲が 10^9 なので固定長配列ではなく辞書を使う必要があるわけですが、 あまり慣れていない操作だったので時間がかかってしまいました。

そろそろこどふぉも100問弱ぐらいACしているはずですが、まだまだ足りてないなぁと感じます。

C. Long Beautiful Integer

問題のURL

解答

自由が効くのは最初の k 桁までであり、以降の桁は k 桁までの設定に従属する。

できるだけ小さいBeautifulな数値を作ろうとすると、 貪欲に上の桁から A の桁をコピーする必要があるため、まずはそのように桁を埋めていく。

このようにして出来る数値が A 以上であるならば、それが答えとなる。

もし A 未満となってしまう場合は、自由が効く桁の一番下の桁、すなわち k 桁目から微調整することを考える。

k 桁目までは A のコピーになっているため、できるだけ下の方の桁で +1 できれば良い (必ず A よりも大きくなる)。 ただし、注目桁が 9 である場合は繰り上がりを考える必要がある。 その場合は、 9 の桁を 0 にした後、上の桁に移動してその桁の数字を +1 することを再考する。

1桁でも変更ができたらその時点で終了し、出来上がった数を出力すれば良い。

k 桁目までを変更する際は、下の方の桁も合わせて修正する必要があることには注意する。

var n, k int
var A []rune

func main() {
    n, k = ReadInt2()
    A = ReadRuneSlice()

    isBeau := true
    for i := 0; i < n; i++ {
        if i+k < n {
            if A[i] != A[i+k] {
                isBeau = false
                break
            }
        } else {
            break
        }
    }
    if isBeau {
        fmt.Println(len(A))
        fmt.Println(string(A))
        return
    }

    B := make([]rune, n)
    for i := 0; i < n; i++ {
        B[i] = 'x'
    }

    // iは起点
    for i := 0; i < k; i++ {
        digit := A[i]

        // jは飛び飛び
        for j := i; j < n; j += k {
            B[j] = digit
        }
    }

    isSmall := false
    for i := 0; i < n; i++ {
        if A[i] == B[i] {
            continue
        } else if A[i] < B[i] {
            break
        } else {
            isSmall = true
            break
        }
    }
    if !isSmall {
        fmt.Println(len(B))
        fmt.Println(string(B))
        return
    }

    // 大きくなるように正しく調整する
    for i := k - 1; i >= 0; i-- {
        if B[i] == '9' {
            // iからk飛びで0に更新
            for j := i; j < n; j += k {
                B[j] = '0'
            }
        } else {
            // iからk飛びで更新
            for j := i; j < n; j += k {
                B[j]++
            }
            break
        }
    }

    fmt.Println(len(B))
    fmt.Println(string(B))
}

桁DPでよくやる考え方の基本、という感じがしました。

多分、最初の部分の「A がすでにBeautifulかどうか?」の判定は要らないと思います。

桁数を出力するのを忘れて1WA、 isSmall の判定部分でバグっており2WAしてしまい、 もったいないことをしてしまいました。

実装がちょっと長くなってくるとこういったミスが増えてくるので、 なにか対策を考えます。

D. Domino for Young

問題のURL

解答

わからなかったため、公式Editorialの手法をなぞりました。

与えられたヤング図形市松模様(チェッカーフラグ)のように塗ります。

その時の黒と白の数を数えて、小さい方が答えです。

小さい方の色を仮に黒とすると、黒は隣接する白とで1つのドミノによって専有され、 また、すべての未使用の黒は未使用の白とペアにすることができるため、とのこと。

賢い(けど、上の説明はちょっと大雑把すぎるかもしれないです)。

var n int
var A []int64
var b, w int64

func main() {
    n = ReadInt()
    A = ReadInt64Slice(n)

    b, w = 0, 0
    for i := 0; i < n; i++ {
        l := A[i]
        if i%2 == 0 {
            // Bから塗り始める
            b += (l + (2 - 1)) / 2
            w += l / 2
        } else {
            // Wから塗り始める
            w += (l + (2 - 1)) / 2
            b += l / 2
        }
    }

    fmt.Println(Min(b, w))
}

青になれて嬉しい気持ちはありますが、目標はまだまだ上に持てているので、 引き続き頑張っていく所存です。