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

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

よくある間違った定義 - 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 ドキュメント

AtCoder Virtual Contest の既知のバグ一覧

これはAtCoder関連サービス Advent Calendar 2018の2日目の記事です。 以下のAtCoder Virtual Contestの挙動は既知のバグです。 他にもあったら教えてください。

そのうち直します。

直す……! 直すが…… 今回まだその時と場所の指定まではしていない そのことをどうか諸君らも思い出していただきたい つまり…… 我々がその気になればバグの修正は

f:id:not522:20181202190440j:plain

ペナルティが減ることがある

TLE解の実行が終わる前に、その後に提出した解答がACした時などに起こることがあります。

部分点周りが壊れてる

AtCoderで解答の実行中にTLEとかが表示されるようになったのを反映していないので、部分点が正しく取得されないことがあります。

途中参加すると提出が反映されない

AVCのコンテストに参加するより前にAtCoderに提出すると反映されないことがあります。

ウィンドウ幅が狭いとコンテスト時間の表示と横線が被る Fixed

CSSは難しいね。

CSS Is Awesomeマグ???プログラマコーヒーマグ???Web開発者マグ???フロントエンド開発者マグ???フルスタック開発者マグ???HTML Mug???11オンスコーヒーMug Cup

問題がたくさんのコンテストにまたがっているとページの表示が遅くなる Fixed

これは仕様。

問題がとてもたくさんのコンテストにまたがっているとページが表示されなくなる Fixed

これも仕様。

ペナルティをめっちゃ大きくするとオーバーフローで落ちる Fixed

Challenge Succeeded.

コンテストの追加に失敗することがある

想定したURL以外を入力されてるっぽい?

問題の削除が失敗することがある

登録されてる問題の形式が壊れてることがあるっぽい?

謎のエラーが起きる

これよく分かんないんだよね。AtCoderにアクセスしすぎて蹴られてるのかな。

教訓

そもそも AtCoder Virtual Contest はほぼ一晩で作ったサイトでした。 想定していた負荷は週に1~2回コンテストが開かれる程度で、1年ぐらいしたら公式でバーチャルコンテストがサポートされてお役御免になる予定でした。 ところが非公式のサービスでみんなが満足していると公式のサポートが後回しになるのは当たり前の話で、結局雑に作って放置しているサイトがそのまま使われているという状況です。 というわけで皆さんも非公式のサービスを作ると意外と使われ続けたりするので、それなりのクオリティにした方が良いよと言い残してこの記事を締めようと思います。

いや、ほんとに直すつもりはあるんですよ。そのうち……。そのうちね……。

凸包の頂点数の話

まとめ

m\times mのグリッドに収まる格子点を頂点とする凸多角形の頂点数はO(m^{2/3})
詳しい話は論文を読んでください。
On the maximal number of edges of convex digital polygons included into an m × m-grid

はじめに

凸包を取ると考慮すべき点の数が減って嬉しい、という問題が競プロでたまに出題されます。
この類の問題の解説で頂点数のオーダーがO(\sqrt{m})と書いてあることがある*1のですが、実際はO(m^{2/3})だよという話です。*2

方針

頂点数を大きくするにはマンハッタン距離が短い辺から使うのが最適です。
マンハッタン距離がn以下の辺を使うと、頂点数が\Theta(n^2)の凸多角形が\Theta(n^3)のグリッドに収まります。

計算

めんどうなので、成分が正の部分だけ考えます。*3
そうすると使う辺は(1,1),(1,2),(2,1),(1,3),(2,2),(3,1),...となります。
これを角度でソートして並べると凸多角形の右下部分になります。
本当は成分が互いに素な辺だけを使う必要がありますが、とりあえず無視します。

マンハッタン距離がn以下の辺を全て使う場合、各座標の総和は
\sum_{i=1}^{n-1} i(n-i)=(n-1)n(n+1)/6
となります。

辺の数は
\sum_{i=1}^{n-1}i=(n-1)n/2
となります。

グリッドのサイズが\Theta(n^3)、頂点数が\Theta(n^2)なので、m\times mのグリッドに\Theta(m^{2/3})頂点の凸多角形を収めることができています。

互いに素

上の計算では成分が互いに素でない辺まで使っていましたが、互いに素である確率は定数なので、これを使わないようにしてもオーダーは変わりません。
互いに素 - Wikipedia

*1:どうやら蟻本の誤りに起因するらしい

*2:Codeforcesの記事で見たはずなんですがURLがわからなくなった

*3:辺を反時計回りにベクトルで持つとすると、一番下から一番右の部分

ナップサック問題でマラソンマッチ入門

マラソンマッチって?

競技プログラミングのうち、「より良い解を求める」ことを競うコンテストをマラソン形式と呼びます。
例えば厳密解を求めることができない問題について、近似解のスコアを競ったりします。

マラソンでよく使われるアルゴリズム

マラソンで頻出なのは「ビームサーチ」と「焼きなまし法」です。
この記事ではナップサック問題を例にしてこの2つのアルゴリズムを解説します。
もちろん、この2つのアルゴリズムはどちらも近似アルゴリズムなので最適解は求められません。

ビームサーチ

まずは順番にナップサックに入るだけ入れるコードを書いてみます。

#include <iostream>

using namespace std;

int main() {
  // 個数
  const int N = 100000;
  // ナップサックの大きさ
  const int W = 100000;

  // 重さ・価値
  int w[N], v[N];
  for (int i = 0; i < N; ++i) cin >> w[i] >> v[i];

  // 今までに入れた物の重さの総和
  int s = 0;
  // 今までに入れた物の価値の総和
  long long t = 0;

  // 入るだけ入れる
  for (int i = 0; i < N; ++i) {
    if (s + w[i] <= W) {
      s += w[i];
      t += v[i];
    }
  }

  // 結果
  cout << t << endl;
}

これをビームサーチに書き換えるとこうなります。

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

int main() {
  // 個数
  const int N = 100000;
  // ナップサックの大きさ
  const int W = 100000;
  // ビーム幅
  const int BEAM = 100;

  // 重さ・価値
  int w[N], v[N];
  for (int i = 0; i < N; ++i) cin >> w[i] >> v[i];

  // 現在の状態(価値・重さ)
  vector<pair<long long, int>> curr;
  curr.emplace_back(0, 0);

  // ビームサーチ
  for (int i = 0; i < N; ++i) {
    // 次の状態(価値・重さ)
    vector<pair<long long, int>> next;
    for (const auto& s : curr) {
      next.emplace_back(s);
      if (s.second + w[i] <= W) {
        next.emplace_back(s.first + v[i], s.second + w[i]);
      }
    }
    // 価値が大きい順に並び替え
    sort(next.rbegin(), next.rend());
    // 状態をビーム幅に減らす
    if (next.size() > BEAM) next.resize(BEAM);
    curr = move(next);
  }

  // 結果
  cout << curr[0].first << endl;
}

それぞれの状態について物を入れるか入れないかの遷移を行って、スコアの良い上位100個の状態を残しています。
この100個のことをビーム幅と呼び、基本的にはこれが大きければ大きいほど良いので、ビームサーチを使うときは高速化が効果的である場合が多いです。

どれくらい改善するかを試した所、以下のようになりました。

アルゴリズム スコア
愚直 829374
ビームサーチ 3252218
厳密解 26383646

実験に使った入力はこれです。
愚直解に比べるとだいぶ改善していますが、厳密解はかなり遠いです。
これは、問題の性質を上手く使えていないのが原因です(最後に書きます)。

焼きなまし

今度はまだナップサックに入れていない荷物を選んで、選んだ荷物が入るように入っている荷物をランダムに捨てるとしてスコアが改善するなら実際に荷物を入れる、という方法を考えます。

#include <algorithm>
#include <iostream>

using namespace std;

// 乱数生成器
inline uint32_t rnd(void) {
  static uint32_t y = 2463534242;
  y = y ^ (y << 13); y = y ^ (y >> 17);
  return y = y ^ (y << 5);
}

int main() {
  // 個数
  const int N = 100000;
  // ナップサックの大きさ
  const int W = 100000;
  // ループ回数
  const int T = 1000000;

  // 重さ・価値
  int w[N], v[N];
  for (int i = 0; i < N; ++i) cin >> w[i] >> v[i];

  // 今までに入れた物の重さの総和
  int s = 0;
  // 今までに入れた物の価値の総和
  long long t = 0;
  // 今までに入れた物・入れていない物
  vector<int> used, unused(N);
  // はじめは全て使っていない
  iota(unused.begin(), unused.end(), 0);

  for (int i = 0; i < T; ++i) {
    // 次に入れる物をランダムに選ぶ
    int k = rnd() % unused.size();

    // ナップサックに収まるようにランダムに捨てる
    int ss = 0;
    long long tt = 0;
    vector<int> del;
    while (tt < v[k] && s + w[unused[k]] - ss > W) {
      int kk = rnd() % used.size();
      if (find(del.begin(), del.end(), kk) != del.end()) continue;
      ss += w[used[kk]];
      tt += v[used[kk]];
      del.emplace_back(kk);
    }

    // 価値が大きくなるなら更新
    if (tt < v[k] && s + w[unused[k]] - ss <= W) {
      s += w[k] - ss;
      t += v[k] - tt;
      unused[k] = unused.back();
      unused.pop_back();
      used.emplace_back(k);
      sort(del.rbegin(), del.rend());
      for (int kk : del) {
        used[kk] = used.back();
        used.pop_back();
        unused.emplace_back(kk);
      }
    }
  }

  // 結果
  cout << t << endl;
}

これを焼きなまし法に書き換えるとこうなります。

#include <algorithm>
#include <iostream>

using namespace std;

// 乱数生成器
inline uint32_t rnd(void) {
  static uint32_t y = 2463534242;
  y = y ^ (y << 13); y = y ^ (y >> 17);
  return y = y ^ (y << 5);
}

bool next(long long b, int t) {
  if (b > 0) return true;
  return exp(b / 10000.0 / pow(0.999999, t)) > double(rnd()) / numeric_limits<uint32_t>::max();
}

int main() {
  // 個数
  const int N = 100000;
  // ナップサックの大きさ
  const int W = 100000;
  // ループ回数
  const int T = 1000000;

  // 重さ・価値
  int w[N], v[N];
  for (int i = 0; i < N; ++i) cin >> w[i] >> v[i];

  // 今までに入れた物の重さの総和
  int s = 0;
  // 今までに入れた物の価値の総和
  long long t = 0;
  // 今までに入れた物・入れていない物
  vector<int> used, unused(N);
  // はじめは全て使っていない
  iota(unused.begin(), unused.end(), 0);

  for (int i = 0; i < T; ++i) {
    // 次に入れる物をランダムに選ぶ
    int k = rnd() % unused.size();

    // ナップサックに収まるようにランダムに捨てる
    int ss = 0;
    long long tt = 0;
    vector<int> del;
    while (tt < v[k] + 10000 && s + w[unused[k]] - ss > W) {
      int kk = rnd() % used.size();
      if (find(del.begin(), del.end(), kk) != del.end()) continue;
      ss += w[used[kk]];
      tt += v[used[kk]];
      del.emplace_back(kk);
    }

    // 焼きなまし
    if (next(v[k] - tt, i) && s + w[unused[k]] - ss <= W) {
      s += w[k] - ss;
      t += v[k] - tt;
      unused[k] = unused.back();
      unused.pop_back();
      used.emplace_back(k);
      sort(del.rbegin(), del.rend());
      for (int kk : del) {
        used[kk] = used.back();
        used.pop_back();
        unused.emplace_back(kk);
      }
    }
  }

  // 結果
  cout << t << endl;
}

スコアが改善しない時も、選んだ荷物をたまには使うようにします。
選んだ荷物を使う確率は、スコアの下落幅が小さい・ループの始めのほうで大きくなるようにします。
ループの後半になるに従って荷物を使う確率を下げていきますが、これに用いるパラメータを温度と呼びます。
このような温度管理によって局所解に陥ることをある程度回避することができます。

スコアは以下のようになりました。

アルゴリズム スコア
愚直 18241125
焼きなまし法 21275856
厳密解 26383646

終わりに

ビームサーチと焼きなまし法を紹介しましたが、これを使えばマラソンマッチで簡単に勝てるかというとそんなことはありません。
一番大事なのは問題の性質を理解することです。
例えば今回の問題の場合、価値÷重さでソートした後に順番に詰めていくだけでかなり良いスコアが出ます。

#include <algorithm>
#include <iostream>

using namespace std;

struct Item {
  int w, v;
  bool operator>(const Item& i) const {return (double)v / w > (double)i.v / i.w;}
};

int main() {
  // 個数
  const int N = 100000;
  // ナップサックの大きさ
  const int W = 100000;

  // 荷物
  Item item[N];
  for (int i = 0; i < N; ++i) cin >> item[i].w >> item[i].v;
  sort(item, item + N, greater<Item>());

  // 今までに入れた物の重さの総和
  int s = 0;
  // 今までに入れた物の価値の総和
  long long t = 0;

  // 入るだけ入れる
  for (int i = 0; i < N; ++i) {
    if (s + item[i].w <= W) {
      s += item[i].w;
      t += item[i].v;
    }
  }

  // 結果
  cout << t << endl;
}
アルゴリズム スコア
ビームサーチ 3252218
焼きなまし法 21275856
ソート 26382284
厳密解 26383646

この解法を元にしてビームサーチや焼きなまし法をすることはできますが、そのようなアルゴリズムの知識よりも問題の考察が重要になることが多いです。
この辺りの話はtakaptさんの記事によくまとまっています。
もちろん、知識は多いほど有利になるのは間違いありません。
ぜひマラソンマッチに参加して経験を詰んだり他の参加者から知識を吸収したりして下さい。
そう言えば今日、Chokudai Contest 001ってのがAtCoderで開催されるらしいので参加してみてはどうでしょうか(ステマ)。