変なしゃくとり法 - 模擬国内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 ドキュメント

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年ぐらいしたら公式でバーチャルコンテストがサポートされてお役御免になる予定でした。 ところが非公式のサービスでみんなが満足していると公式のサポートが後回しになるのは当たり前の話で、結局雑に作って放置しているサイトがそのまま使われているという状況です。 というわけで皆さんも非公式のサービスを作ると意外と使われ続けたりするので、それなりのクオリティにした方が良いよと言い残してこの記事を締めようと思います。

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