5分探索による高速な貪欲行動判定- AHC061

atcoder.jp

AIの行動決定に時間がかかるので高速化したい。本記事では貪欲行動を扱う。

貪欲行動は以下の値を求めて最大値を取る移動先を決める。

  • [A] 誰の領土でもない場合: V * wa
  • [B] 自分の領土でレベルが U 未満の場合: V * wb
  • [X] 自分の領土でレベルが U の場合: 0
  • [C] 他のプレイヤーの領土でレベルが 1 の場合: V * wc
  • [D] 他のプレイヤーの領土でレベルが 2 以上の場合: V * wd

Xのパターンはほとんど選ばれないのでA,B,C,Dについてのみ考える。

ここで大事なのはA~Dのどのパターンも、そのパターン内でVが最大の移動先を選ぶことである。したがってVを事前にソートしておけば、各パターン内の移動候補に対して2分探索などを行うことで最大値を求めることができ、最後にA~Dの中から最大値を選べば良い。

まずは1つのパターンの中から最大のVを求める方法を考える。

詳細は省略するが、NxNマスの情報をbitboardとして128bit整数で持ち、A~Dの各パターンに対応するbitboardを差分更新することが可能である。（ただし領土が削られた場合は、行動可能範囲を表すbitboardをBFSをやり直して求める必要がある。）

事前に以下のようなbitboard 100個を用意しておく。

  • 全てのbitが1のbitboard
  • ...
  • Vが最大と2番目に大きいbitと3番目に大きいbitのみ1のbitboard
  • Vが最大と2番目に大きいbitのみ1のbitboard
  • Vが最大のbitのみ1のbitboard

これらのbitboardと各パターンで動ける範囲を表すbitboardのandをとると、最初に0でない値が並びその後に0が並ぶようになる。そして求めたいのは0でない最後の位置である。これは2分探索などで高速に求めることができる。

ここからが本題

2分探索はメモリ上で飛び飛びの位置にアクセスするので、普通に実装するとキャッシュメモリになかなかヒットせず、速度が低下してしまう。今回はキャッシュのラインサイズの512bitを意識することで高速化を行う。

（キャッシュのラインサイズの説明は省略するが、メモリ上で連続する512bitにまとめてアクセスできると得であると認識してもらえれば今回は問題ない。）

今回のbitboardは128bitを使っているので512bitには4つ収まる。そこで、20番目・40番目・60番目・80番目をメモリ上で連続して並べておき、一気に判定を行う。この結果、求める値は[0, 20), [20, 40), [40, 60), [60, 80), [80, 100)の5つの範囲のどれに存在するかがわかる。

次にその20個の中での4番目・8番目・12番目・16番目をメモリ上で連続して並べておき、一気に判定を行う。この結果、求める値の候補は4つまで絞られる。

最後のその4つのうち1番目・2番目・3番目をメモリ上で連続して並べておき、一気に判定を行う。

この手順で判定を行うことで、毎回の判定で使うbitboardたちが512bitに収まるようになり、高速化される。

bitboardは具体的には以下のような順で並んでいる。

[20, 40, 60, 80] [4, 8, 12, 16] [1, 2, 3] [5, 6, 7] [9, 10, 11] [13, 14, 15] [17, 18, 19] [24, 28, 32, 36] ... [44, 48, 52, 56] ... [64, 68, 72, 76] ... [84, 88, 92, 96] ...

さらに速くする

Vをソートしておき各パターンに対応する最大値を求める方法は、パターンA~Dの4回の探索を行う必要がある。しかし、wa, wb, wc, wdの大きい順に探索を行うことで、探索範囲を狭めることができる。

例えばwa > wb > wc > wdであったとする。まずはじめにパターンAの探索を[0, 100)で行う。この結果、パターンAでの最大値をとるのはmax_a番目であったとする。すると、パターンBの探索は[max_a+1, 100)で行うことができる。なぜなら、[0, max_a)の範囲にパターンBの解があったとしてもV[max_a] * wa > V[max_b] * wbであり、パターンBから最終結果が採用されることはないからである。同じようにパターンCは[max(max_a+1, max_b+1), 100)、パターンDは[max(max_a+1, max_b+1, max_c+1), 100)の範囲で探索すれば十分である。この探索は範囲が動的に決まるため先ほどの5分探索を適用することはできないが、範囲が狭まっているため2分探索でも高速に動作する。

変なしゃくとり法 - 模擬国内2020E

こういうことをしたくなります。

ans = 0
for i = 1, ..., m:
  for j = i, ..., m:
    if [i, j] がSAT:
      ans = max(ans, j - i + 1)
    else:
      break

SATの判定が O(N+M) なので、全体で O(M2(N+M)) になります。

j は解を更新する可能性がある範囲しか調べなくていいので i+ans から始めても良いです。

ans = 0
for i = 1, ..., m:
  for j = i+ans, ..., m:
    if [i, j] がSAT:
      ans = max(ans, j - i + 1)
    else:
      break

ただの定数倍改善に見えますが、よくみると計算量が改善していて O(M(N+M)) になっています。 SAT判定を呼ぶ範囲が計算量削減の本質で、これがしゃくとり法のような動きをします。（厳密にはしゃくとり法よりSAT判定を呼ぶ回数が少ない。）

競プロを始めて10年が経った

初めてSRMに出たのが 2010/10/21 なので今日で競プロ10周年になりました。 f:id:not522:20201021174247p:plain 自分としては蟻本が出版された後に競プロ始めた人は新入りという感覚なんですが、いつの間にか 老害 古参と言われても文句が言えない年数になってました。 今後ものんびりやっていこうかな〜という気持ちです。とりあえずJAGの運営と作問を頑張りたいですね。特に夏合宿はいまだに稀少な宿泊ありのイベントなので継続していきたいです。あとはレートを上げたいですね。レッドコーダー目指して精進します。

競プロでよくある「バランスのとれた括弧列」の定義が壊れがちな話

なるほどなぁと思ったし周知しておくべきだと思ったので記事にしました。

よくある間違った定義 - 1

バランスのとれた括弧列は以下のいずれかの条件を満たす。

  1. 空文字列
  2. バランスのとれた括弧列{ \displaystyle A }が存在し、'(',{ \displaystyle A },')'をこの順に結合した文字列
  3. バランスのとれた括弧列{ \displaystyle A },{ \displaystyle B }が存在し、{ \displaystyle A },{ \displaystyle B }をこの順に結合した文字列

E - Parentheses

C - 部分文字列と括弧

よくある間違った定義 - 2

バランスのとれた括弧列は以下のいずれかの条件を満たす。

  1. '()'
  2. バランスのとれた括弧列{ \displaystyle A }が存在し、'(',{ \displaystyle A },')'をこの順に結合した文字列
  3. バランスのとれた括弧列{ \displaystyle A },{ \displaystyle B }が存在し、{ \displaystyle A },{ \displaystyle B }をこの順に結合した文字列

Problem G: Flipping Parentheses

Problem - 1272F - Codeforces

正しい定義 - 1

バランスのとれた括弧列は以下のいずれかのルールで構成される。

  1. 空文字列
  2. バランスのとれた括弧列{ \displaystyle A }が存在し、'(',{ \displaystyle A },')'をこの順に結合した文字列
  3. バランスのとれた括弧列{ \displaystyle A },{ \displaystyle B }が存在し、{ \displaystyle A },{ \displaystyle B }をこの順に結合した文字列

Star in Parentheses

正しい定義 - 2

バランスのとれた括弧列は以下のいずれかの条件を満たす空でない文字列である。

  1. '()'
  2. バランスのとれた括弧列{ \displaystyle A }が存在し、'(',{ \displaystyle A },')'をこの順に結合した文字列
  3. バランスのとれた括弧列{ \displaystyle A },{ \displaystyle B }が存在し、{ \displaystyle A },{ \displaystyle B }をこの順に結合した文字列

正しい定義 - 3

バランスのとれた括弧列は以下のいずれかの条件を満たす。

  1. 空文字列
  2. バランスのとれた括弧列{ \displaystyle A }が存在し、'(',{ \displaystyle A },')'をこの順に結合した文字列
  3. 空文字列でないバランスのとれた括弧列{ \displaystyle A },{ \displaystyle B }が存在し、{ \displaystyle A },{ \displaystyle B }をこの順に結合した文字列

K - 括弧

F - Bracket Sequencing

正しい定義 - 4

A bracket sequence is called regular if it is possible to obtain correct arithmetic expression by inserting characters "+" and "1" into this sequence.

Problem - 1132A - Codeforces

Codeforcesでよく使われる定義っぽい。

正しい定義 - 5

何が問題？

要するに、条件を満たす文字列集合が複数存在するのが問題です。

定義3は本当に正しい？

定義3を満たす集合の要素は定義5を満たすことを確認しましょう。

こういうのの典型テクとして、定義3を満たす集合のある要素が定義5を満たさないとして、満たさない最短の要素を持ってきて矛盾を導くというのがあります。こうすると、それより短い要素は定義5を満たしていることになります。

この最短の要素が定義3のどの条件を満たすかで場合分けします。

1) 空文字列

これは明らかに定義5を満たしています。

2) (A)

Aは定義5を満たすので、括弧の数は対応が取れています。また、

「0～i文字目までの'('の数」 == 「Aの0～i-1文字目までの'('の数 + 1」 >= 「Aの0～i-1文字目までの')'の数 + 1」 == 「0～i文字目までの')'の数 + 1」 > 「0～i文字目までの')'の数」

となるので、(A)も定義5を満たします。

3) AB

これも定義5を満たします。（証明は読者の演習問題とする。）（書くのが面倒になった。）

以上から、定義5を満たさない最短の要素は、定義3のどの条件を満たすとしても定義5を満たしてしまうので矛盾が導けました。したがって、定義3を満たす集合の要素は定義5を満たします。

逆に、定義5を満たす文字列の集合は定義3を満たすことを示す必要がありますが、面倒になったのでこれも読者の演習問題とします。

感想

正しい問題文を書くの難しい。。。

追記：正しい定義 - 6

新概念コン2018 論文まとめ

北大・日立新概念コンピューティングコンテスト2018の参考文献を読んだのでコンテストに関係ありそうなところを雑にまとめました。

Reduction by substitution

{ \displaystyle x_1 x_2 } を { \displaystyle w } に置換することで次元を下げることを考えます。 この時、元の数式を{ \displaystyle x_1 x_2 }に依存する部分と依存しない部分に分けると、

{ \displaystyle f(x)=x_1 x_2 A(x)+B(x) }

と書けます。 { \displaystyle w } について最小化した時に { \displaystyle w=x_1 x_2 } が満たされるように、ペナルティ項のついた形に書き換えて

{ \displaystyle \tilde{f}(x;w)=wA(x)+B(x)+Mp(x_1,x_2;w) }

となるような定数 { \displaystyle M } と高々2次の多項式 { \displaystyle p } を探します。これは { \displaystyle M } がとても大きく、{ \displaystyle p } が { \displaystyle w=x_1 x_2 } の時だけ0でそれ以外は正となれば良いです。具体的には { \displaystyle M } が { \displaystyle A } の絶対値の最大値より大きく、

{ \displaystyle p(x;w)=x_1 x_2 -2x_1 w-2x_2 w+3w }

とすれば良いです。

Reducing negative-coefficient terms

係数が負の項については以下の式で次元を下げることができます。

{ \displaystyle -x_1x_2\cdots x_d = \min_{w \in \{0,1\}} w\left((d-1)- \sum_{j=1}^{d} x_j \right) }

左辺が0の時は { \displaystyle \min } の中が0以上となるので、{ \displaystyle w } は0となり両辺が一致します。左辺が-1の時は { \displaystyle \min } の中が-1となるので、{ \displaystyle w } は1となり両辺が一致します。

Higher-order clique reduction

{ \displaystyle x_1 x_2 x_3} の次元を良い感じに下げることを考えます。 元の式が対称式なので、変形後も { \displaystyle x} についての対称式になっているものを考えます。 変形後は高々2次なので { \displaystyle S_1=x_1+x_2+x_3} と { \displaystyle S_2=x_1 x_2+x_2 x_3+x_3 x_1} だけ考慮すれば良いです。 頑張って探すと、

{ \displaystyle x_1 x_2 x_3 = \min_w w(-S_1 +1 ) + S_2 }

であることが分かります。同様にして4次の場合は、

{ \displaystyle x_1 x_2 x_3 x_4= \min_w w(-2S_1 +3 ) + S_2 }

となります。5次の場合はこのままではできませんが、追加する変数を増やすことにより

{ \displaystyle x_1 x_2 x_3 x_4 x_5 = \min_{v,w} (v(-2S_1 +3) + w(-S_1 + 3 ) ) + S_2 }

とできます。一般化すると、{ \displaystyle n_d=\left\lfloor \frac{d-1}{2} \right\rfloor} として、次数が偶数の時は

{ \displaystyle x_1 \cdots x_d = \min_w \sum_{i=1}^{n_d} w_i(-2S_1 +4i-1 ) + S_2 }

であり、次数が奇数の時は

{ \displaystyle x_1 \cdots x_d = \min_w \left( \sum_{i=1}^{n_d-1} w_i(-2S_1 +4i-1 ) + w_{n_d}(-S_1+2n_d-1)\right) + S_2 }

とできます。

Splitting of common parts

ここまでは項を一つずつ潰していましたが、ここではある変数を含む項について一気に次数を下げることを考えます。 { \displaystyle x_1} を含む項のうち、係数が正のものを全部持ってきて

{ \displaystyle \sum_{H \in \mathcal{H}} \alpha_H \prod_{j \in H} x_j = \min_{y \in \{0,1\}} \left( \left( \sum_{H \in \mathcal{H} } \alpha_H \right) x_1 y + \sum_{H \in \mathcal{H}} \alpha_H \prod_{j \in H \backslash \{1\}} x_j - \sum_{H \in \mathcal{H}} \alpha_H y \prod_{j \in H \backslash \{1\}} x_j \right) }

とすると、 { \displaystyle \min } の中の第3項だけ次数が下がってないんですが、これは係数が負になるので前に紹介した方法で解決します。 この式は Alexander Fix et al. (2011) のFigure 2を見るとイメージが分かって、{ \displaystyle x_1 } のとる値で場合分けしていて、{ \displaystyle x_1=0 } には { \displaystyle y=1 } が対応して、 { \displaystyle x_1=1 } には { \displaystyle y=0 } が対応します。

さいごに

ここで書いたアルゴリズムを実装しても全然順位上がらないんですけど、上位陣はいったい何をやってるんですか…？

JAGの作問環境

これはCompetitive Programming (1) Advent Calendar 2018の2日目の記事です。

JAGでは作問を楽に行うために、様々な試行錯誤を行なっています。今回はデータセット・問題文の準備にどのような工夫をしているかを紹介します。作問の全体的な流れは既に記事が複数書かれているので省略します。

参考：

JAGのおしごと！ - くじらにっき++

競技プログラミングの作問進行法 (Competitive Programming Advent Calendar Div2014 Day 2) - itohjamのブログ

競技プログラミング作問ガイド - nodchipのTopCoder日記 - TopCoder部

ツール

Slack

基本的にコミュニケーションはSlack上で行なっています。 コンテスト全体用のチャンネルと各問題ごとのチャンネルを作り情報が散逸しないようにしています。

PukiWiki

問題案の投稿や全体の進捗管理に用いています。

GitHub

テストデータはGitHub上で管理しています。 また、最終版に近いHTML形式の問題文もここに置かれます。

Google Docs

問題文の推敲をここで行います。

Rime

ジャッジ解の管理やジャッジデータの生成などに使います。

データセット

// あとでちゃんと書く

データセットの生成にはジャッジ解・テストデータ生成器・テストデータ検証器の3つが必要になります。 生成器と検証器を書く人は必ず別の人が担当します。 また、余力があれば他の人も検証器を追加で書きます。 これらはRimeで管理され、GitHubのプライベートリポジトリに置かれます。

Gitの運用ポリシーは「masterに直接push」です。

また、push時に自動的にWerckerでrime wikify_fullを走らせていて、実行結果がPukiWikiで確認できるようになっています。 注意点として、Wercker上で並列数を増やしすぎると結果が返ってこないことがある（たぶんメモリを食いつぶした？）ので8並列くらいにしておく必要があります。

Rime+のススメ - Qiita

GitHub - not522/write-problems-sample: 作問リポジトリのサンプル

問題文

問題文はGoogle docs上にMarkdownで準備しています。 校正もGoogle docsの機能で行っています。

このMarkdownからJAGの内部ツールでHTMLやPDFを生成しています。（このツールは将来的に公開したいと思っています）

この時、自動的にサンプルを挿入するようにしているため、サンプルがリボジトリと同期されないというミスをなくしています。

A: A+B - Google ドキュメント