変なしゃくとり法 - 模擬国内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判定を呼ぶ回数が少ない。)
競プロでよくある「バランスのとれた括弧列」の定義が壊れがちな話
「空文字列でない」を入れることにしたみたいです(今日のABC-Fもそうでした)。
— きり (@kiri8128) May 10, 2020
PAST中めちゃくちゃ考えましたが、確かにこれで一意になりそうです。https://t.co/Aykgtguv14
なるほどなぁと思ったし周知しておくべきだと思ったので記事にしました。
よくある間違った定義 - 1
バランスのとれた括弧列は以下のいずれかの条件を満たす。
- 空文字列
- バランスのとれた括弧列が存在し、'(',,')'をこの順に結合した文字列
- バランスのとれた括弧列,が存在し、,をこの順に結合した文字列
よくある間違った定義 - 2
バランスのとれた括弧列は以下のいずれかの条件を満たす。
- '()'
- バランスのとれた括弧列が存在し、'(',,')'をこの順に結合した文字列
- バランスのとれた括弧列,が存在し、,をこの順に結合した文字列
Problem G: Flipping Parentheses
正しい定義 - 1
バランスのとれた括弧列は以下のいずれかのルールで構成される。
- 空文字列
- バランスのとれた括弧列が存在し、'(',,')'をこの順に結合した文字列
- バランスのとれた括弧列,が存在し、,をこの順に結合した文字列
正しい定義 - 2
バランスのとれた括弧列は以下のいずれかの条件を満たす空でない文字列である。
- '()'
- バランスのとれた括弧列が存在し、'(',,')'をこの順に結合した文字列
- バランスのとれた括弧列,が存在し、,をこの順に結合した文字列
正しい定義 - 3
バランスのとれた括弧列は以下のいずれかの条件を満たす。
- 空文字列
- バランスのとれた括弧列が存在し、'(',,')'をこの順に結合した文字列
- 空文字列でないバランスのとれた括弧列,が存在し、,をこの順に結合した文字列
正しい定義 - 4
A bracket sequence is called regular if it is possible to obtain correct arithmetic expression by inserting characters "+" and "1" into this sequence.
Codeforcesでよく使われる定義っぽい。
正しい定義 - 5
いっそのこと括弧列を
— てんぷら (@tempura_cpp) May 10, 2020
・'('と')'のみからなり個数が同じ
・すべてのiについて
0~i文字目までの'('の数>=0~i文字目までの')'の数
が成り立つ
にしちゃえばいいんじゃないかと思ったり思わなかったりする
何が問題?
集合Sが条件
— きり (@kiri8128) May 10, 2020
∀s ∈ S
(sは空文字列) or (∃A, B ∈ S, s.t. s = A + B) or (∃A ∈ S s.t. s = "(" + A + ")" )
を満たすとき、Sを「括弧の対応が取れている文字列」と定義しています。
例えばSとして「 "(" と ")" からなる任意の文字列(空集合も含む)」を取っても条件を満たします。
要するに、条件を満たす文字列集合が複数存在するのが問題です。
定義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
「() を消すことを0回以上繰り返して空文字列にできる」
— maspy (@maspy_stars) May 11, 2020
が、場合分けもなく文章も短くて、人間の手による括弧列の評価とも対応しているので、個人的に推しておきます。
普段、ルールで構成できているかよりも、正しく計算できるかで認識していそうじゃないですか?
ACM-ICPC Japan Alumni Group Summer Camp 2019 Day 3 J: Horizontal-Vertical Permutation
こういうことをしたくなります
微妙に合わないのでてきとうに直します
おわり
新概念コン2018 論文まとめ
北大・日立新概念コンピューティングコンテスト2018の参考文献を読んだのでコンテストに関係ありそうなところを雑にまとめました。
Reduction by substitution
を に置換することで次元を下げることを考えます。 この時、元の数式をに依存する部分と依存しない部分に分けると、
と書けます。 について最小化した時に が満たされるように、ペナルティ項のついた形に書き換えて
となるような定数 と高々2次の多項式 を探します。これは がとても大きく、 が の時だけ0でそれ以外は正となれば良いです。具体的には が の絶対値の最大値より大きく、
とすれば良いです。
Reducing negative-coefficient terms
係数が負の項については以下の式で次元を下げることができます。
左辺が0の時は の中が0以上となるので、 は0となり両辺が一致します。左辺が-1の時は の中が-1となるので、 は1となり両辺が一致します。
Higher-order clique reduction
の次元を良い感じに下げることを考えます。 元の式が対称式なので、変形後も についての対称式になっているものを考えます。 変形後は高々2次なので と だけ考慮すれば良いです。 頑張って探すと、
であることが分かります。同様にして4次の場合は、
となります。5次の場合はこのままではできませんが、追加する変数を増やすことにより
とできます。一般化すると、 として、次数が偶数の時は
であり、次数が奇数の時は
とできます。
Splitting of common parts
ここまでは項を一つずつ潰していましたが、ここではある変数を含む項について一気に次数を下げることを考えます。 を含む項のうち、係数が正のものを全部持ってきて
とすると、 の中の第3項だけ次数が下がってないんですが、これは係数が負になるので前に紹介した方法で解決します。 この式は Alexander Fix et al. (2011) のFigure 2を見るとイメージが分かって、 のとる値で場合分けしていて、 には が対応して、 には が対応します。
さいごに
ここで書いたアルゴリズムを実装しても全然順位上がらないんですけど、上位陣はいったい何をやってるんですか…?
JAGの作問環境
これはCompetitive Programming (1) Advent Calendar 2018の2日目の記事です。
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並列くらいにしておく必要があります。
GitHub - not522/write-problems-sample: 作問リポジトリのサンプル
問題文
問題文はGoogle docs上にMarkdownで準備しています。 校正もGoogle docsの機能で行っています。
このMarkdownからJAGの内部ツールでHTMLやPDFを生成しています。(このツールは将来的に公開したいと思っています)
この時、自動的にサンプルを挿入するようにしているため、サンプルがリボジトリと同期されないというミスをなくしています。
AtCoder Virtual Contest の既知のバグ一覧
これはAtCoder関連サービス Advent Calendar 2018の2日目の記事です。 以下のAtCoder Virtual Contestの挙動は既知のバグです。 他にもあったら教えてください。
そのうち直します。
直す……! 直すが…… 今回まだその時と場所の指定まではしていない そのことをどうか諸君らも思い出していただきたい つまり…… 我々がその気になればバグの修正は
ペナルティが減ることがある
TLE解の実行が終わる前に、その後に提出した解答がACした時などに起こることがあります。
部分点周りが壊れてる
AtCoderで解答の実行中にTLEとかが表示されるようになったのを反映していないので、部分点が正しく取得されないことがあります。
途中参加すると提出が反映されない
AVCのコンテストに参加するより前にAtCoderに提出すると反映されないことがあります。
ウィンドウ幅が狭いとコンテスト時間の表示と横線が被る Fixed
CSSは難しいね。
問題がたくさんのコンテストにまたがっているとページの表示が遅くなる Fixed
これは仕様。
問題がとてもたくさんのコンテストにまたがっているとページが表示されなくなる Fixed
これも仕様。
ペナルティをめっちゃ大きくするとオーバーフローで落ちる Fixed
Challenge Succeeded.
コンテストの追加に失敗することがある
想定したURL以外を入力されてるっぽい?
問題の削除が失敗することがある
登録されてる問題の形式が壊れてることがあるっぽい?
謎のエラーが起きる
これよく分かんないんだよね。AtCoderにアクセスしすぎて蹴られてるのかな。
教訓
そもそも AtCoder Virtual Contest はほぼ一晩で作ったサイトでした。 想定していた負荷は週に1~2回コンテストが開かれる程度で、1年ぐらいしたら公式でバーチャルコンテストがサポートされてお役御免になる予定でした。 ところが非公式のサービスでみんなが満足していると公式のサポートが後回しになるのは当たり前の話で、結局雑に作って放置しているサイトがそのまま使われているという状況です。 というわけで皆さんも非公式のサービスを作ると意外と使われ続けたりするので、それなりのクオリティにした方が良いよと言い残してこの記事を締めようと思います。
いや、ほんとに直すつもりはあるんですよ。そのうち……。そのうちね……。