tomboのブログ

競技プログラミングのことをいろいろ書きます AtCoder A茶H水

茶色コーダーが書く!例題を通して畳み込みを感覚的に理解する

tomboです。畳み込みのお気持ち解説記事を書きます。高速フーリエ変換FFT)と関係して難しいイメージがあったり、形式的冪級数FPS)を調べてみたらわけが分からなかったという人もいそうで、なるべく簡単に直感的に、畳み込みについて説明出来たらと思います。自分が茶色コーダーなので、同じ茶色コーダーでも理解できるのが目標です。


本記事では、例題としてABC248-C(茶diff)、TDPC-A、ABC352-G(橙diff)を扱います。よかったら、この3問の解説としてもお使いください。

畳み込みとは

畳み込みには連続と離散のものがありますが、今回は離散の畳み込みについて扱います。今、長さNの配列Aと長さMの配列Bがあり、これらの畳み込みCについて、畳み込みの定義を書きます。(0-indexed)


 C_i = \sum_{j=0}^i A_jB_{i-j} \> (0 \leq i \leq N+M-2)


ただし、配列外参照になるような添字が含まれている項は考えません。(係数が0と考えてよい) C の長さは  N+M-1 となります。自分は最初これを見たとき、何もわかりませんでした(終わり)しかし、これを書き下してじっと睨んでいると、何かが見えてきます(?)



C_0 = A_0B_0 \\
C_1 = A_0B_1 + A_1B_0 \\
C_2 = A_0B_2 + A_1B_1 + A_2B_0 \\
C_3 = A_0B_3 + A_1B_2 + A_2B_1 + A_3B_0 \\
... \\
C_{N+M-4} = A_{N-3}B_{m-1} + A_{N-2}B_{M-2} + A_{N-1}B_{M-3} \\
C_{N+M-3} = \hspace{6em} A_{N-2}B_{M-1} + A_{N-1}B_{M-2} \\
C_{N+M-2} = \hspace{12em} A_{N-1}B_{M-1} \\

これって、縦に見ると

 A_0(B_0, B_1, B_2, ..., B_{M-1}), A_1(B_0, B_1, B_2, ... B_{M-1})

というような、全探索っぽい感じなります。これについて、 C の各項の和を考えると、

int sum = 0;
for (int i=0; i<N; i++){
    for (int j=0; j<M; j++){
        sum += A[i]*B[j];
    }
}


のように、2重ループで全探索しながら全部の項の積の和を取っているみたいな感じになるんですよね、これは、実は多項式の積といえます。


 (A_1+A_2+...+A_N)(B_1+B_2+...+B_M)


多項式  A B の積は、すべての  A の項について、すべての  B の項とかけて足しますよね。それと同じことを畳み込みがやっています。



畳み込みと形式的冪級数の関連

では、これを競プロでどう使うのか。これは、数え上げの分野で登場します。多項式係数を場合の数指数を状態(何かの和)として考えます。これのかけ算に畳み込みを使います。ここで、形式的冪級数(けいしきてき べききゅうすう、FPS: Formal Power Series)が登場します。まず形式的冪級数とは?ですが、無限個まで項の数が拡張された多項式のようなものと思ってください。実際には、有限個の項で出てくるのが大多数だと思います。この記事では、形式的冪級数多項式は同じものと思ってもらって大丈夫です。数え上げのときに、状態を指数で表して、場合の数を指数で持っておく考え方そのものも、形式的冪級数と呼ばれてるような気がします。


実は、数え上げの問題は、多項式のかけ算と関連させて考えることができます。ここで、数え上げとは特に「和がいくつのとき、そのような場合の数はいくつか」というようなものを指します。




例として、

 Ax \times Bx^2

を考えます。これを、 Ax は「和が  1 でそのときの場合の数が  A」、 Bx^2 は「和が  2 でそのときの場合の数が  B」とします。すると、

 AxBx^2 = ABx^3

となり、和が  3 のとき、場合の数が  A \times Bというようになります。これは、DPでいうところの、和が  j のとき場合の数は  dp_{ij} = AB のようになります。


一般に、多項式で状態と場合の数が表されているとき、それらをかけると、それまでの遷移を全部合わせたとき、和がいくつの場合の数は何通りであるか、というのが、多項式の積の状態で得られます。


例えば、

 1+A_1x+A_2x^2+A_3x^3

という式が得られたら、和が  0 1 通り( 1x^0)、和が  1 _A1 通り( A_1x^1)、和が  2 A_2 通り( A_2x^2)、和が  3 A_3 通り( A_3x^3)という意味になります。これは、和についての数え上げに使うことができます。しかし計算量を考えると、多項式の積は  A の長さが  N B の長さが  M のとき、2重ループで  O(NM) かかりますね。これをできればもうちょっと速く計算したいです。

畳み込みを高速に行う

ここでフーリエ変換、特に高速フーリエ変換FFT)が出てきます。ちなみに、FFTというのは離散フーリエ変換(DFT)を高速に行うものです。

(参考:フーリエ変換と畳み込み | 高校数学の美しい物語


これは、畳み込みとフーリエ変換の関係の式です。意味としては、 f g の畳み込み  f*gフーリエ変換したものは、 f gフーリエ変換して、アダマール積を取った(要素ごとにかける、 A_1 B_1 A_2 B_2 みたいな)ものと等しいということです。アダマール積は一個ずつ見るので、 O(N) で計算することができますね。また、フーリエ変換は逆フーリエ変換することで元に戻すことができます。ここで、離散フーリエ変換 O(N^2) ですが、高速フーリエ変換 O(NlogN) で行うことができます。FFTの仕組みは自分もよく分かっていません。 _{むずそう、助けてくれ}また、逆フーリエ変換FFTと同様に  O(NlogN) で行うことができます。逆フーリエ変換はIFFTと呼ばれます。(Inverse FFT)


よって、畳み込みというのは、FFT  O(NlogN)アダマール O(N) → IFFT  O(NlogN) となり、全体で  O(NlogN) で計算できるのです。


これを使うと、長さ  N の配列  A と長さ  M の配列  B の畳み込みは、 O( (N+M)log(N+M)) で計算できます。つまり、2つの多項式の積もこの計算量で計算できることになります。

ここまでのまとめ

  • 畳み込みは多項式の積である。
  • 畳み込みは  O(NlogN) で計算できる。
  • 多項式の積は、和についての数え上げに対応する。


atcoder::convolutionについて

atcoder::convolutionは畳み込みを  O(NlogN) で計算できます。

vector<int> a(n), b(m);
vector<int> c = atcoder::convolution(a, b);

もしくは

using namespace atcoder;
convolution(a, b);

としてもいいですね。



畳み込みを使って数え上げの問題を解いてみる

ここからは例題の解説です。

ABC248 C - Dice Sum

総和が  K 以下であるような数列の場合の数ですね。まぁ普通にいけば部分和DPです。

 dp_{ij} := (i項目まで見たとき、総和がjであるような場合の数)

dp[i][j] += dp[i-1][j-k];

みたいな。これについて  j \leq K の場合の数を最後に足せばいいですね。コードも貼っておきます。
https://atcoder.jp/contests/abc248/submissions/53177007


さて、ここまで読んだ人なら、ぜひこの問題を畳み込みで解きたくなります。なりますよね?(タタハラ、畳み込みハラスメント(?))


FPSの考え方で解く場合は、まず立式をします。そして、それが間に合うなら計算し、間に合わなければ分割統治+FFTという技を使います。これはABC352-Gのときに解説します。では立式します。デン↓↓


 \sum_{i=0}^K \, \lbrack X^i \rbrack \> \prod_{j=1}^N (x+x^2+...+x^M)


こうなります。 \lbrack X^i \rbrack  X i 乗の項の係数を表します。 Σ は総和、 Π は総積です。ここで改めて係数と指数の意味を確認します。

係数:場合の数
指数:和がその値になるとき

今回は、 N 項からなる数列  A について、それぞれ  1 \leq A_i \leq M となるように要素を構築するとき、その全部の場合の数を知りたいですね。これが多項式の状態で得られれば、あとは  K 乗までの項の係数の総和が分かればいいです。それが全部の場合の数になるので。


多項式  \, \prod_{j=1}^N (x+x^2+...+x^M) を 1 回かけるのと、数列  A の項  A_i 1 個分  1 から  M まで全通り探索するのが同じような意味になっています。 X 0 乗の項の係数は、 1 \leq A_i \leq M より  0 となっています。


コードはこのようになっています。

vector<ll> g(M+1);
rep(i, 1, M+1){
    g[i] = 1;
}
vector<ll> f{1};

単位元 f としていて、 1X^0 = 1 となっています。多項式  g は数列  A の各項のすべての場合に対応しています。ここで、配列の値には係数のみ入れておきます。インデックスが指数を表しています。インデックス(=和の状態)ごとに係数(=場合の数)が独立しているイメージですね。 \lbrack 0, 1, 1, 1, 1, ... \rbrack というような感じの配列です。


次に、畳み込みを  N 回行って、各項のすべての場合について具体的に場合の数を求めていきます。

rep(_, 0, N){
    f = convolution<mod>(f, g);
}

mod const が要求されています。計算量は  O(N^2logN) です。横幅が  N 、高さが  NlogN の直角三角形の面積みたいな感じですね。個人的に、 1 から  N までの総和  N(N+1)/2 の計算量を、三角形の計算量と呼んでいます。

ll ans = 0;
rep(i, 0, K+1){
    ans += f[i];
    ans %= mod;
}
cout << ans << endl;

最後に、 f \lbrack 0 \rbrack から  f \lbrack K \rbrack までの総和(=  0 乗から  K 乗までの係数の総和)を求めて終わりです。これが、 A の総和が  K までの場合の数に対応しています。いかがでしたか?(?)



TDPC A - コンテスト

次はTDPCからの出題です。


問題をいくつか選んで解いて点数を獲得したとき、総得点の種類数が問われています。このような、選ぶか選ばないか、みたいなものはDPの典型っぽく見えて、それはFPSでも解くことができます。式は以下です。


 \prod_{}^N (1+x^p_i)


これについて、係数が正となるような項の数が答えになります。これは、指数が得点の合計を表していて、係数が正というのはそのような得点を取り得るという意味です。今は何通りか聞かれているので、場合の数が正であるなら +1 ということになります。


この  1+A_ix^N の形は有名で、使うか使わないかということです。 1 1X^0 = 1 より和の増分が  0(=使わない)、 A_ix^N は今の段階で  A_i 通りあって、これを使うと合計が  N 増えるという感じです。この式を 1 回かけるたびに、1 つの要素を使うか使わないかが探索されて、場合の数でいうと状態数が 2 倍になったということです。


コードは以下のようになっていて、 0 乗と  p_i 乗の項の係数に  1 を立てています。

vector w(N+1, vector(101, 0LL));
rep(i, 1, N+1){
    w[i][0] = 1;
    w[i][p[i]] = 1;
}


提出:https://atcoder.jp/contests/tdpc/submissions/53304681



ABC352 G - Socks 3

さて、ついに橙diffのラスボスが登場しました。対戦お願いします(?)一応想定読者は茶色以上ということになっているのですが、さすがに難しいと思うので、分かんないなーと思ったら流し読みなどでも大丈夫です。青コーダーの人くらいになると、この記事も読めるだろうし、公式解説もスラスラ読めるのかなーと思ってます。自分は3日くらい張り付いて、茶色コーダーの友達と話しあいながら公式解説を読んでいたら、少しずつ分かってきました。この記事では、公式解説をさらに自分なりに読解したようなことをしています。


この問題は、

  • 確率と期待値
  • 分割統治+FFT

の2つのフェーズに分かれています。計算量のボトルネックは分割統治+FFTです。


まず初めに、問題を確認します。靴下をランダムに選んで、非復元抽出で取り出し、最初に被ったら終了、そのときの回数の期待値を求めよ、ということですね。靴下はそれぞれ  Ai 枚あります。最初に期待値の立式をします。 i 回目ちょうどに終わる確率を  Q_i とします。すると、期待値は以下になります。


 1Q_1+2Q_2+...+(N+1)Q_{N+1}


 i 回で終わるなら、確率変数  X_i i になります。その時の確率は  Q_i なので、それらの積の和が期待値になります。このとき、鳩ノ巣原理によって  N+1 回目までに必ず終わることが分かります。


ここで、個人的天才発想を導入します。 i 回以上かかって操作を終える確率を  P_i とすると、上の式は  Q_i = P_i-P_{i+1} より、


 P_1+P_2+...+P_{N+1}


となります。これ、以上の考え方がやばいなーと思いました、知らないと出てこなさそう。 i 回以上になって逆に面倒かと思いきや、


 P_{i+1} = (i 回目までに終わらなかった確率)


となって、これは場合の数から求めることができます。特に今回は、操作が終わらなかったとき、各靴下が高々  1 個までしか選ばれていないと分かるので、その時の場合の数をFPSの考え方で計算できるということですね。


靴下の総数を  S 枚、その中から重複なく  i 枚の靴下を選ぶパターンを  f_i とすると、


 P_{i+1} = \Large \frac{f_i}{_{S}C_i}


となります。これは、全部の場合の数  _S{C}_i に対して、重複なく  i 枚靴下を選んだ場合の数ということです。あとは、この  P を求めれば、それらの総和が求める期待値ということになります。


さて、 _S{C}_i は普通に全部かけて割ればいいのでいいとして、 f_i が難しいですね。ここでさっき登場した、選ぶか選ばないかの多項式を使います。


 f_i = \lbrack X^i \rbrack \prod_{j=1}^N (1+A_jx)


となり、とりあえず  \prod_{j=1}^N (1+A_jx) を高速に求めたいです。このまま愚直にFFTで計算すると、 O(N^2logN) となって  1 \leq N \leq 3 \times 10^5 より間に合わないので、ここで分割統治+FFTを使います。


分割統治とは、マージソートのように二分木に分解して、部分問題を解決しながらマージしていくことで、全体の問題を解決する手法です。そのとき、木の高さが  O(logN) となることがポイントです。今回は、このマージを畳み込みで行います。すると、計算量は  O(Nlog^2N) となって、ちょっと重めですがTLも3秒になってて間に合います。

auto f(vector<vector<ll>> v){
    if (v.size()==1){
        return v[0];
    }
    vector<vector<ll>> left, right;
    ll n = v.size();
    rep(i, 0, n/2){
        left.push_back(v[i]);
    }
    rep(i, n/2, n){
        right.push_back(v[i]);
    }
    return convolution<mod>(f(left), f(right));
};


デーン(強いアルゴが登場した音)分割統治+FFTです。まず、左右に要素数を半分にしていきながら、帰りがけ再帰をします。引数には多項式がたくさん与えられています。返り値は畳み込まれた多項式で、これがマージの部分です。


これによって、各  f_i が得られました。 P_{i+1} = \Large \frac{f_i}{_{S}C_i} より、各  P_i も求められました。答えは  \sum_{i=1}^{N+1} P_i となり、 O(Nlog^2N) 時間で求めることができました。


提出:https://atcoder.jp/contests/abc352/submissions/53281768

まとめ

畳み込みのパワーが伝わりましたか?自分としては、結構ゴリ押しみたいな感じが強くて、分かりやすいので好きです。DPの方が簡単なパターンもありそうで、適切に使い分けていきたいなーと思っています。


初めて橙diffを解説ACできたのが、個人的に大きいです。今まで暖色の問題は、茶色コーダーにとって全く理解できないだろうと思っていたので、解説を読み込めば行けることもあるんだなーというのが印象的でした。では、畳み込みでよき数え上げライフを送ってください。最後に、自分も参加しているFPSバチャを貼っておきます。ここまで読んでくださってありがとうございました。

https://kenkoooo.com/atcoder/#/contest/show/accf2cb4-2dc4-402e-994a-055fd9297203

将棋ライクLv.20クリアしました!

(アップデートが頻繁に行われているらしくて、最新の情報じゃないかもしれないです。この記事は2024/05/04に書きました。)

今回は、主にノーマルモード(Lv.1~Lv.10)について書いていきます。

目次

  • 完走した感想
  • ゲームの概要
  • 具体的な戦略
  • おすすめコンボ
  • 駒の取得優先度ランキング
  • 意外と強くない駒
  • ハードモードについて
  • まとめ

完走した感想

面白かったです、将棋とは完全に別ゲーですが、ちゃんと頭を使って戦略を練って戦うのがすごく楽しいゲームでした。自分はちなみに将棋から入って、そしたら開幕「怨霊(倒された相手も道ずれにする)」っていうのが出てきたのでその勢い(?)でめっちゃ笑ってました。


夜10:00に始めて、朝の4:00にLv.20までクリアしました。けっこう難しかった、もっとステージがあったら無限にやってるかもしれない()運が絡んできて、場合によってはすぐに行けたり、苦戦したりすると思うので、そこも将棋と違ったゲーム要素って感じで好きです。それでは、攻略記事みたいな感じで、自分が攻略したときの情報を書いていきます。

ゲームの概要

将棋のように駒を動かして、相手の王城に3ダメ―ジ与えれば勝ちです。駒は将棋に登場するもののほかに、オリジナルのものがたくさんあり、こちらがメインになります。駒には手動と自動があり、自動の駒は手数が増える分、シンプルに強いです。また、駒には普通・銀・金の3つのランクがあり(Lv.20クリア後にシークレットが解放される)、基本的には金駒が強いですが、「機兵」と「金船」は最後まで使っていける優秀な銀駒で、取っておいて損はないです。

自動の例

  • 機兵(銀駒)
  • 機龍(金駒)
  • 金船(銀駒)
  • 不沈(金駒)
  • 腐敗(金駒)

自動に関しては、範囲内の敵を優先するので、完全にランダムというわけではなく、ある程度敵に近づいたら勝手に攻撃してくれます。

具体的な戦略

Lv.1~Lv.5

最大の関門はLv.3の女傑のような気がします。初めて出てくる金駒ですね。めちゃくちゃ強いです。対抗するためのおすすめの駒を紹介します。

  • 主盾:攻撃と防御で上回っており、シンプルに強い。
  • 魔女:女傑を豚兵に変えてしまって勝ち。
  • 金船:自動制御。防御1で倒されないので強い。不沈になるとさらに強い。
  • 機兵:自動制御。防御1で倒されないので強い。機龍になるとさらに強い。機龍は2回行動。

その他、角を成って馬で攻めたり、邪剣で殴ったりして、うまくかみ合って勝つこともあります。できれば上の4つの銀駒のどれかが欲しいかなーと思いました。

Lv.6~Lv9

Lv.6の腐敗がしんどいです。対策を知らないとけっこう負けます。おすすめの駒を紹介します。

斜めの駒で、初手角道オープン→相手の王城を直接殴る(終了)で勝てます。または、騎馬で跳ねていってそのまま重騎で殴れば勝てます。腐敗に巻き込まれないように気を付けてください。


Lv.9の女帝×2もきついかもですが、金船→不沈とか、機兵→機龍、十三でスナイプ、魔女で封印、洗脳で味方にする(下の画像)など、そこまで駒が増えたらいろいろ対策できると思います。駒の取得優先度ランキングも見てみてください。


それ以外では、例えばLv.7なら、このように不沈や機龍に攻撃させておけば、だいたいうまくいきます。

Lv.10

これ、運ゲーです。聖獣が瞬間移動して殴ってくるので、お願いしますーーーって言いながらプレイしてください。(言わなくていいです)あと、邪神と聖神が召喚してきた邪徒、聖徒の場所と被ると、召喚時にそのままダメージを受けます。輪廻で行ったりする場合は、これもお願いしますーっていいながら、慎重に横を通り抜けてください。王城に近づければあとはやるだけです。負けパターンは基本的に、道中が苦しくてたどり着けないという状況か、早々に自分の王城が攻撃されるパターンです。


突撃する駒は、機龍や不沈の自動で待っているか、手動ならぬにがいいです。輪廻審判でランダムスポーンを狙ってもいいですが、輪廻は耐久面が終わってるので、少しでも距離があるとなかなか王城にたどり着けないと思います。Lv.10は「魑魅魍魎が跋扈する」的な表現が正しそう(?)


魔獣には洗脳が通ります。


おすすめコンボ

魔女審判

脳死破壊コンボ。(?)魔女で相手の駒を豚兵にすると、審判の効果でその駒を破壊できます。魔女は個人的に癖が強くて、扱うのが難しいと思っているので、味方の駒を巻き込んだり攻めのルートを消したりしないようにしながら、相手の強い駒を倒すようにするといい感じになります。

輪廻審判

魔女審判ほど強くはないですが、輪廻は倒されると寝返って、そのとき審判の効果で倒されてもう一回寝返り、ランダムスポーンして味方として復活するので、審判が生きている限り輪廻は不死身になります。また、輪廻は攻撃3なので王城をワンパンできます。機動力が低いのが難点。

駒の取得優先度ランキング

あくまで個人的な、ざっくりとした感覚です。ステージレベルや自分のデッキによって多少変わってきます。また、人によって使いやすさや癖が強いと感じる部分があると思うので、その辺りはお任せになってます。


1位 機龍(金駒)

自動で動き、2回行動、ステータスが優秀で、メイン火力にも防御にもなります。とりあえず取っておくと、いろいろ活躍してくれて助かります。2回行動ができるのはこの駒だけです。


2位 主盾(銀駒)→ ぬに(銀駒)

防御特化かと思いきや、ゆっくり進出していってぬにとなった途端、最強のステータスになります。他の駒の能力も受けない。もちろん王城もワンパン。さすが唯一ぬに。


3位 金船(銀駒)→ 不沈(銀駒)

自動制御で、斜めに突っ込んで不沈になりやすいです。不沈になると、高いステータスに加えて、HP自動回復も付いてかなり優秀です。機龍と同じく攻めにも守りにも使えます。


4位 増殖(金駒)

分厚い層を形成して、圧縮してゴリ押しみたいなムーブになります。Lv.10で聖徒と邪徒の大群に殴り勝てます。しかし成ると死ぬので、やっぱり機龍や不沈で火力を出していきたいです。


5位 審判(銀駒)

相手の特殊召喚された駒を即座に破壊します。魔女や輪廻と相性が良いですが、自分では何もできないので状況によって選びます。タンクとして使えます。何より、Lv.10の邪徒を召喚と同時に倒せるのがデカすぎて、重宝します。聖徒には無効なので、左から殴りたいところです。


6位 魔女(銀駒)

周囲の駒をすべて豚兵にします。相手の強い駒をとりあえず豚兵にしておけば、火力を抑えられたり、そのまま審判と合わせて消してしまうなどができま
す。


7位 機兵(銀駒)→ 機龍(金駒)

機龍に成れるので、少しずつ前線に上がっていきたいです。そのままでも防御1があるので、結構戦えます。機動力が低いのが難点です。


8位 十三(金駒)

相手の強力な駒(女帝、機龍など)を開始から3ターンの間、ターンごとに1体ずつ抹消できます。(バチコリ)駒自身で戦うことはできないので、主戦力にはならないですが、厄介な駒を破壊できるのは便利です。

意外と強くない駒

  • 張飛(銀駒)
    • 飛車先の歩を突くのが遅い。(角道ならすぐに開く)
    • 飛車はデフォルトの将棋の駒であり、攻撃と体力が1、防御が0になっている。


  • 全能(金駒)
    • 相手の駒と一緒に自分の駒も消してしまうので、Lv.10の大量の駒相手に分が悪い。
    • 運が悪いといきなり主力駒が消えたりして、自傷ダメージが大きい。


ハードモードについて

ハードモードでは、金 駒 が 使 え ま せ ん 。( そ ん な ) 気合で頑張ってください、ただ、汚忍→空蝉が使えます。これが聖獣みたいな感じの瞬間移動で、かなり強烈なので、必ず取ってください。ノーマルに対して、実はハードは全然苦労しない印象でした。空蝉が強いのかも。ベースはノーマルと同じなので、機兵や金船で行けます。

まとめ

いろいろと戦略があって面白そうで、アップデートも来ているらしいので、ぜひぜひやってみてください。あと、マリオや砲塔が使えなくて大変なので、その辺の情報をください(?)ちなみに、本家の将棋も面白いです。シークレットの五条が強すぎた。

AHCのローカルテスタの使い方

AHCのローカルテスタ、自分も最初使い方が分からなかったので、それについて書きます。WindowsPowerShellなので、それ以外の環境の人はまた調べてみてください← 言語はC++を想定していますが、コンパイルやファイルの実行を言語に合わせて書き換えてください。

PowerShellのコード

Param($l, $u)
$num = 32
$num_txt = "AHC{0:D3}" -f $num
Set-Location "実行するコードへの絶対or相対パス"

g++ -O3 -D_GLIBCXX_DEBUG -std=c++2a "$num_txt.cpp" -o AHC.exe
for ($i=$l; $i-lt$u; $i++){
    $tmp="{0:D4}" -f $i

    # non-interactive
    Get-Content in/$tmp.txt | ./AHC.exe > out.txt
    Write-Host -NoNewLine $i": "
    ./vis.exe in/$tmp.txt out.txt
    
    # interactive
    # Write-Host -NoNewLine $i": "
    # Get-Content in/$tmp.txt | ./tester.exe ./AHC.exe > out.txt
}

<#
実行コマンド
ファイル名.ps1 -l 0 -u 50
#>

Param()で引数を2つ受け付けています。$numはAHCの番号です。(3桁で0埋めしています)Set-Location (Linuxのcd) で移動しています。どこで実行してもいいようにするためです。-D_GLIBCXX_DEBUGで、index out of rangeのときに表示してくれるようにしています。(行数の表示方法は分かりません)


これはC++なのでコンパイルしていますが、Pythonなどのインタプリタは、./AHC.exeのところで直接ファイルを実行してください。


入力ファイルの番号は [l, u) の半開区間になっています。4桁で0埋めしていますが、AHCではダウンロード時のデフォルトで、0000~0099までしか入力ファイルがないので、seeds.txtに欲しい入力ファイルの数字を書いて、gen.exeを実行すると生成してくれます。


実行は

ファイル名.ps1 -l 0 -u 50

で出来ます。(0000~0049の場合)

並列実行について

並列実行すれば、並列した数だけ速くなります。(それはそう)マルチプロセスのことだと思います。ちなみにマルチスレッドは、スレッドが分かれるだけで速度は変わらないと思います。並列で1万ケース回すみたいな話も聞いたりしていて、たくさん回せばその解法の評価がより正確になるので、良かったら試してみてください。自分はよく分かっていません(そんな)

まとめ

AHCは楽しいので、ぜひぜひって感じです。

マージソートを、書きます。

tomboです。マージソートを、書きます。(書くので)

安定して速いです

マージソートは安定ソートで、ソートしたいデータ数  N に対して最悪ケースの時間計算量が  O(NlogN) です。例えばクイックソートは不安定ソートで、ピボットの選び方によってはマージソートより遅く  (O(N^2)) なったりします。色々な言語のソート関数でも、内部でマージソートが実装されているんじゃないかなーと思っています。(思っているだけ)

実装の方針

分割統治法をします。「困難は分割せよ」の精神で (DP的な) 、分割してソートしながらマージしていって、最終的に全体のソートを達成します。分割は二分木のようにします。今回は再帰関数を使います。(他の実装をしらない←)

二分木の高さは、要素数 N として  O(logN) になるので、マージの処理には  O(N) かけても、全体で  O(NlogN) になることが分かります。そして、再帰的にマージするときの一番のポイントが、マージするたびに要素がソートされるということです。

問題と実装

verifyにはこの問題を使いました。
アルゴリズムと数学 演習問題集 027 - Sorting

提出
https://atcoder.jp/contests/math-and-algorithm/submissions/52793571

再帰関数の説明をします。
まず、左右に分けながら帰りがけ再帰をします。

vector<ll> left, right;
ll n = v.size();

// 左半分
rep(i, 0, n/2){
    left.push_back(v[i]);
}
// 右半分
rep(i, n/2, n){
    right.push_back(v[i]);
}

// 左右それぞれ帰りがけ再帰
vector<ll> v1, v2;
if (left.size()>=2){
    v1 = merge_sort(left);
} else {
    v1 = left;
}
if (right.size()>=2){
    v2 = merge_sort(right);
} else {
    v2 = right;
}

このとき、木の高さは  O(logN) なので、配列長が  O(N) であっても、これらの操作は間に合うことが分かります。( 1 \leq N \leq 10^5 くらいの入力の大きさを仮定しています)
素数が1になったら、そこからマージしながらreturnします。

ll i1 = 0;
ll i2 = 0;
ll n1 = v1.size();
ll n2 = v2.size();
vector<ll> ret;
while (true){
    // 両方のインデックスがsize()未満のとき
    if (i1<n1 && i2<n2){
        // 小さい方の値をretに入れる
        if (v1[i1]<=v2[i2]){
            ret.push_back(v1[i1]);
            i1++;
        } else {
            ret.push_back(v2[i2]);
            i2++;
        }
    }
    // 片方だけのときはそのまま入れる
   else if (i1<n1){
        ret.push_back(v1[i1]);
        i1++;
    }
    else if (i2<n2){
        ret.push_back(v2[i2]);
        i2++;
    }
    // 両方の値を見終わったらbreak
    else {
        break;
    }
}

return ret;

マージは、左右の配列のインデックスを進めていきながら、小さい方をretに入れていきました。ここで  O(N) でソートされた配列を構成できるのは、マージ前にすでにそれらの配列がソートされているためです。


帰りがけ再帰なので、まず再帰の一番深いところ(要素数が1)のところまで降りてから  ( O(logN) )、戻りながらマージして  ( O(N) )、マージ後には値がソートされているわけなので、  O(NlogN) でソートを達成することができました。

まとめ

分割統治法は、細かく問題を分割してそれぞれ解いてからマージするという手法です。ソート以外にも使い方があると思うので、調べてみて下さい。自分も、いつか分割統治+FFTを理解します(いつか)

初心者から初心者に向けた焼きなましのすすめ

どうも、tomboです。初めてブログを書きます。

この記事では、焼きなまし初心者が、AtCoderのアルゴやヒューリスティックの問題に焼きなましを適用して解いてみた、ということを書きます。厳密なことはよく分からないので、焼きなましの知識が全くない初心者に、直感的に伝えるみたいなことが目標になっています。それではどうぞ(?)

焼きなましとは

焼きなましとは、ある状態Xに少しの変化を加えてX'(近傍)にして、評価値を計算し、評価値と温度からその近傍を採用するかしないかを決める、ということを繰り返して、大域最適解に近づいていくという感じのアルゴリズムです。これは、山登りと呼ばれるアルゴリズムの拡張です。山登りは、近傍を取りながら、改善したときだけ採用します。それに対して、焼きなましは悪化してもある程度の確率で採用します。採用する確率は、改善した幅(負の場合も含めて)が大きいほど高くなり、スコアの変化が0以上のとき100%採用します。(スコアを最大化したいとき)

ここから評価関数を山にたとえますが、高いとは評価値がいいことを意味するとします。

まず、悪い解を採用するメリットですが、山登りが評価関数の今いる山の頂上で止まる(局所最適解)としたら、あえてそこから脱出することで、大域最適解に辿り着きやすいということです。そうして評価関数上を移動しながら、たまたま大域最適解を含む山に来たとき、遷移確率関数から、山の頂上が高いほど、その山から脱出しにくくなり、少しずつ正解の山の頂上に登っていきます。遷移確率関数は、有名なものがあるのであとで紹介します。その関数には便利な性質があり、自分も初めて見たときはすごいなーと思いました(?)

また、温度は温度関数によって決まり、線形 (1次関数) や非線形 (線形でない関数) のものがあります。これもあとから紹介します。

AHCの問題では、インタラクティブとノンインタラクティブがありますが、焼きなましは主にノンインタラクティブの、盤面を自由に動かせるようなときに使います。理由としては、インタラクティブは操作回数が制限されていて、焼きなましのポイントである大量の試行回数を稼げないためです。それに対して、毎回入力を受け取って何かを出力するようなインタラクティブでは、貪欲やビームサーチ、モンテカルロなどが採用されます。

実際に解いてみる

この記事では、言語はC++を使います。

EDPC D - Knapsack 1

みなさんおなじみ、ナップサックDPです。

dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]+v[i]);

という遷移で解けます。(詳細略)
実際の提出(DP)
https://atcoder.jp/contests/dp/submissions/52731892


これを焼きなましで通します。問題を理解していない場合は、一度読んでみてください。まず近傍を考えます。袋に1個追加する近傍と、袋から1個削除する近傍がよさそうです。今回は、袋の重さ上限を超えないようにしています。ギリギリまで詰まっているときには、一回袋から取り出してから別のものを追加しないといけないので、入れ替える近傍もあった方がよさそうです。実際に、addとremoveに加えて、swapをすることでやっと通りました。
実際の提出(焼きなまし) https://atcoder.jp/contests/dp/submissions/47296658

  • add近傍
// 20%の確率で操作を行う
if (rd<20){
    // 採用するindexを乱択する
    ll i = next_idx_add();
    // 袋に入るかどうか
    if (add_ok(i)){
        // 遷移確率を取得する
        double p = prob(value+v[not_having[i]], value, temp)*100;
        // 採用するとき
        if (p>rand(0, 100)){
            // スコアを更新する
            value += v[not_having[i]];
            // 答えを更新する
            ans = max(ans, value);
            // コストを更新する
            cost += w[not_having[i]];
            // 状態を更新する
            having.push_back(not_having[i]);
            //// 後ろに回してからpopするとO(1)
            swap(not_having[i], not_having.back());
            not_having.pop_back();
        }
    }
}

最初に、乱数を取得して、20%の確率でaddをしています。採用するインデックスは乱択しています(next_idx_add)。次に、袋にその荷物が入るかを判定しています(add_ok)。そして遷移確率を取得します(prob)。遷移する場合は、実際に答えと状態を更新します。今回は答えの更新がO(1)でできるので毎回行っていますが、状態のコピーにコストが大きくかかるとき、毎回コピーするとボトルネックになるので、差分更新をO(1)で行って、最後の状態をそのまま答えにすると思います。removeやswapもaddと同様に行っています。

  • 遷移確率関数

これには有名なものがあります。

 probability = e^{\Large \frac{newScore-preScore}{temperature}} \, (eは自然対数の底 \, ( \sim 2.718))
ネイピア数 - Wikipedia

例えば、温度temp=3のとき、以下のグラフになります。

xはnewScore-preScoreということで、スコアの増加分になります(最小化するときはpreScore-newScoreになります)。tempをいろいろ変えてみると、温度が高いときx=0に近づいて、低いとき遠ざかることが分かります。また、newScore>=preScoreのとき、prob>=1になり、遷移確率が100%以上になります。つまり、この関数は「評価値が改善するか同じとき、遷移確率が必ず1以上になり、そうでないとき、温度が高いほど遷移確率が上がる(1未満)」という関数になります。

double prob(ll new_score, ll pre_score, double temp){
    double e = 2.7;
    double p = pow(e, (new_score-pre_score)/temp);
    return p;
}


  • 温度関数

線形と非線形があります。

線形の例

double temp_init = 500;
double temp_finish = 10;
int time_limit = 1980;
double temp = temp_init-(temp_init-temp_finish)*(now-start)/time_limit;

startは開始時の時間計測、nowは現在の時間計測で、now-startで経過時間を表しています。この式は、

 tempInit-tempFinish = coolingWidth

 \Large \frac{now-start}{timeLimit} = \normalsize elapsedTimeRate

とすると、

 temp = tempInit - coolingWidth \times elapsedTimeRate

となり、初期温度から時間経過に応じて冷やしていく、というのが分かると思います。


非線形の例

double temp_init = 300;
double temp = temp_init;
double temp_finish = 5;
double max_iter = 3e5;
double change_rate = pow((temp_finish/temp_init), 1/max_iter);
for (i=0; i<max_iter; i++){
    // 処理
    temp *= change_rate;
}

これは、

tempFinish = tempInit \times decreaseRate^{maxIter}
\\ decreaseRate^{maxIter} = \Large \frac {tempFinish}{tempInit}
\\ decreaseRate = \Large \frac {tempFinish}{tempInit} ^ {\frac {1}{maxIter}}

というように、初期温度にdecreaseRateをmaxIter回かけて、最終的にtempFinishになってほしい、という式を変形して、1回当たり何倍すればよいのかを求めたものです。

競技プログラミングの鉄則 B23 - Traveling Salesman Problem

以降は問題についてのみ言及していきます。

この問題は、巡回セールスマン問題(Traveling Salesman Problem)で有名です。TSPといえばILS(Iterated Local Search、反復局所探索法、山登り+kick)ですね。(文脈を知らない人向け→ https://twitter.com/tombo_choco/status/1707402075540431138)(ほとんどの人が知らないと思います)(はい)
1msでfastestなので、うれしかったです。(bitDPで十分)


というのは置いておいて、まぁとにかくbitDPなわけですが、焼きなましをします(?)


実際の提出(bitDP)
https://atcoder.jp/contests/tessoku-book/submissions/50409603
実際の提出(焼きなまし)
https://atcoder.jp/contests/tessoku-book/submissions/46032854
実際の提出(ILS)(1ms)
https://atcoder.jp/contests/tessoku-book/submissions/46014747


  • 近傍

ランダムに隣り合うインデックスを選んで、順番を入れ替えています。

(参考:2-opt法によるTSP | レベルアップ問題集 | プログラミング学習サイト【paizaラーニング】
このような2-optをしたかったのですが、これがそうなっているのかよく分かっていません(そんな)
とにかく、これで通りました。

vector<ll> next_state_rand(vector<ll> v){
    if (N<=3){
        return v;
    }
    ll r = rand(v.size()-3)+1;
    ll tmp = v[r];
    v[r] = v[r+1];
    v[r+1] = tmp;
    return v;
}
double temp_init = 1e4;
double temp = temp_init;
double ans = inf;
const ll max_iter = 1e6;
ll c = 0;

while (c<=max_iter){
    c++;

    // 2-optで焼きなまし
    vector<ll> next = next_state_rand(state);
    double new_score = calc(next);
    ans = min(ans, new_score);
    double p = prob(new_score, score, temp)*100;

    // prob()の確率で遷移する
    if (p>rand(100)){
        state = next;
        score = new_score;
    }

    // 温度関数を更新する
    temp *= 0.999995;
}

今回は、temp *= 0.999995としました。

AHC024 A - Topological Map

これはヒューリスティックコンテストなので、最適解ではないですが、延長戦順位表で1849パフォが取れているので、そこそこ参考になると思います。

この解法には、山登りの前処理が含まれていて、それについても簡単に説明します。

  • 問題の概要

色の連結関係をキープし、色ごとに連結成分を1個に保ちながら、なるべく面積を小さくするというものです。

  • アプローチ
    • 行列削除山登り
    • 隣接侵食焼きなまし

(この2つの語感すき)


まず、行と列で消しても問題ない箇所があるので、それを山登りで削除します。貪欲みたいな感じですね(?)そこから焼きなましに移行します。隣り合うマスに色をコピーします。白いところを塗るのが悪化する遷移、白いマスを増やすのが改善する遷移です。制約を守るのがめんどうですが、3x3マスの中心1マスに向けて色をコピーすることを考えると、結構分かりやすくなります。詳しいことを聞きたかったら、コメントやXなどで質問してもらえれば答えます、自分に答えられる範囲で()

ビジュアライザ

  • 近傍

(山登りは省略)

// その方向から色を移せるか判定する
bool move_ok(ll i, ll j, string dir_from){

    // 変化前の9マスの中心
    ll pre_col = c[i][j];

    // 同じ色に移すときfalse
    if (dir_from=="U" && c[i-1][j]==pre_col ||
        dir_from=="D" && c[i+1][j]==pre_col ||
        dir_from=="L" && c[i][j-1]==pre_col ||
        dir_from=="R" && c[i][j+1]==pre_col){
            return false;
        }
    
    // その色がなくなるときfalse
    if (cnt_color[c[i][j]]<=1) return false;
    

    // 3x3マスをコピーする
    vector new_c(3, vector(3, ll(0)));
    rep(p, 0, 3){
        rep(q, 0, 3){
            new_c[p][q] = c[i+p-1][j+q-1];
        }
    }

    // 実際に色を移す
    ll new_i = 1;
    ll new_j = 1;
    if (dir_from=="U") new_c[new_i][new_j] = new_c[new_i-1][new_j];
    if (dir_from=="D") new_c[new_i][new_j] = new_c[new_i+1][new_j];
    if (dir_from=="L") new_c[new_i][new_j] = new_c[new_i][new_j-1];
    if (dir_from=="R") new_c[new_i][new_j] = new_c[new_i][new_j+1];

    // 変化後の9マスの中心
    ll new_col = new_c[new_i][new_j];
    
    // 色間の連結保持判定
    map<ll, set<ll>> pre_color, new_color;
    rep(p, 0, 3){
        rep(q, 0, 3){
            ll a = i+p-1;
            ll b = j+q-1;

            // 変化前の連結関係
            if (a-1>=i-1){
                pre_color[c[a][b]].insert(c[a-1][b]);
                pre_color[c[a-1][b]].insert(c[a][b]);
            }
            if (a+1<=i+1){
                pre_color[c[a][b]].insert(c[a+1][b]);
                pre_color[c[a+1][b]].insert(c[a][b]);
            }
            if (b-1>=j-1){
                pre_color[c[a][b]].insert(c[a][b-1]);
                pre_color[c[a][b-1]].insert(c[a][b]);
            }
            if (b+1<=j+1){
                pre_color[c[a][b]].insert(c[a][b+1]);
                pre_color[c[a][b+1]].insert(c[a][b]);
            }

            // 変化後の連結関係
            if (p-1>=0){
                new_color[new_c[p][q]].insert(new_c[p-1][q]);
                new_color[new_c[p-1][q]].insert(new_c[p][q]);
            }
            if (p+1<3){
                new_color[new_c[p][q]].insert(new_c[p+1][q]);
                new_color[new_c[p+1][q]].insert(new_c[p][q]);
            }
            if (q-1>=0){
                new_color[new_c[p][q]].insert(new_c[p][q-1]);
                new_color[new_c[p][q-1]].insert(new_c[p][q]);
            }
            if (q+1<3){
                new_color[new_c[p][q]].insert(new_c[p][q+1]);
                new_color[new_c[p][q+1]].insert(new_c[p][q]);
            }
        }
    }
    // 色の連結性が違ったらfalse
    if (pre_color!=new_color) return false;

    // 同一色の連結保持判定
    // 変化後の色ごとの連結成分の個数が2以上でfalse
    used.clear();
    rep(p, 0, 3){
        rep(q, 0, 3) seen[p][q] = false;
    }
    rep(p, 0, 3){
        rep(q, 0, 3) if (used.count(new_c[p][q])==0) dfs(p, q, new_c);
    }
    rep(p, 0, 3){
        rep(q, 0, 3) if (seen[p][q]==false) return false;
    }

    // 色を移すことができる
    return true;
}

近傍というか、遷移できるかどうかの判定になっています。近傍は座標を乱択しています。

// 同一色の連結保持判定
// 9マスの中で色ごとに連結成分の個数を数える
void dfs(ll p, ll q, vector<vector<ll>> new_c){
    seen[p][q] = true;
    used.insert(new_c[p][q]);
    if (p-1>=0 && new_c[p-1][q]==new_c[p][q] && !seen[p-1][q]){
        dfs(p-1, q, new_c);
    }
    if (p+1<3 && new_c[p+1][q]==new_c[p][q] && !seen[p+1][q]){
        dfs(p+1, q, new_c);
    }
    if (q-1>=0 && new_c[p][q-1]==new_c[p][q] && !seen[p][q-1]){
        dfs(p, q-1, new_c);
    }
    if (q+1<3 && new_c[p][q+1]==new_c[p][q] && !seen[p][q+1]){
        dfs(p, q+1, new_c);
    }
}

同じく、遷移できるかどうかの判定です。条件としては、色の連結関係が変わらないか、連結成分が1個であるかの2つがあるので、近傍を乱択してから判定してOKだったら遷移しています。

double temp = temp_init-(temp_init-temp_finish)*(now-start)/time_limit;

温度関数は線形ですね。遷移確率関数は上と同じです。ちなみに、乱数生成器はmt19937(メルセンヌ・ツイスタ)を使っています。

mt19937 mt(now());
ll rand(ll a, ll b) {
    if (b<=a){
        cerr << "RandRangeError" << " a:" << a << " b:" << b << endl;
        return -1;
    }
    return mt()%(b-a)+a;
}

実際の提出 https://atcoder.jp/contests/ahc024/submissions/49364292


以上で3つの問題への、焼きなましを使ったアプローチの説明を終わります。自分は、焼きなましには圧倒的なパワーがあると思っていて、GA(遺伝的アルゴリズム)のように時間がかからず、ビームサーチより汎用性が高い気がして、すごく便利だと思っています。雑に殴ればいいじゃんてきな?いや、分からないですが、楽しいのでぜひぜひって感じです。

おまけ

  • 動きが悪かったら評価値の変化が小さいかもなので100倍とかしてみてください、動きがある程度大きい方がよく解空間を探索できてうれしいです。初期温度も高くしてみてください。
  • 温度は自分は線形のものを使っています。
  • アルゴがACできると楽しいです、特にDPは割といけると思います、EDPCとか。

まとめ

いかがでしたか?(言いたいだけ)
いろいろガバかったらすみません、これはあくまで自分の感想を共有するみたいなノリで軽く眺めてほしくて、本格的に焼きなましをやりたかったらrhooさんの記事(p/tech/.md at main · rhoo19937/p · GitHub)とかも参考になると思います。C++の実装が読みにくかったり、質問があったり、間違いの指摘などがあったらどんどん言ってもらえれば、自分に対応できる範囲でいろいろやります。これからもなにか思いついたら書いていくかもなので、またよろしくお願いします(?)