ARMERIA

Rubyと競技プログラミングの話　AtCoderやCodeforcesの問題解説記事が多め。

「答えを決め打つ」タイプの二分探索を使いこなそう

プログラミング 競技プログラミング

ゴールデンウィークの有志コンテストなどで多く出題され、話題になったので記事を書こうと思います。

対象レートはだいたい緑～水色（最後のほうは青くらいまで）です。実際のAtCoderの問題を使って説明していくので、ネタバレになる点はご了承ください。

「答えを決め打つ」タイプの二分探索とは

この記事で扱うのは、以下のような問題＆解法です。

  1. 「○○という条件を満たす X の最小値を求めよ」という問題において、
  2. 「ある値 X が与えられたとき、○○を満たすことはできるか？」という判定問題を考え、
  3. その判定問題を繰り返し解くことでYesになる X とNoになる X の間の境界を特定し、元の問題の答えを求める解法。

もちろん最小値ではなく最大値である場合もあります。実際にいくつか問題を見ていきましょう。

問題例1：花束（ARC050-B）

B - 花束

解法

持っている花から2種類の花束を作り、その合計数を最大化する問題です。制約が大きく、正攻法で取り組むのは難しいです。

ここで「ある値 X が与えられたとき、合計 X 個の花束を作ることはできるか？」という判定問題を考えます。唐突ですね。騙されたと思って考えてみましょう。

花束の個数を決めると、この判定問題は以下のように解くことができます。

  1. 全ての花束は赤青少なくとも1本ずつの花を含むので、まずは X 個分の花束の赤青1本ずつを確保する。
  2. すると残りは赤 x-1 本または青 y-1 本で花束を1個作ることができるので、赤青それぞれ独立に作れる花束の個数を計算する。
  3. 合計が X 個以上であればYes、そうでなければNo。

この判定問題を利用して、元の最大化問題を以下のように解くことができます。

  1. 判定問題がYesになることが明らかな X の値を ok という変数に、判定問題がNoになることが明らかな X の値を ng という変数に代入して初期値とする。
    • 例えば、0個の花束は明らかに作れるので ok = 0 とし、花の本数の半分を超える個数の花束は明らかに作れないので ng = (R+B)/2 + 1 とする。
  2. 以下の処理を、ok と ng の差が1になるまで繰り返す。
    • ok と ng の平均 mid = (ok+ng)/2 を取る。（小数点以下は切り捨てて良い）
    • X を mid としたときの判定問題を解き、結果がYesなら ok に、Noなら ng に mid を代入する。

そうです、二分探索です。この処理で ok と ng の差が1になるまで繰り返せば、そのときの ok の値が求めたい最大値になっているのです。

単調性の確認

さきほどの解法は何故成立するのでしょうか？この解法の正しさを保証するための重要な性質が「単調性」です。

この問題の判定問題では、 X の値が大きいほうが条件が「厳しく」なります。そして、答えがYesとなる X の範囲とNoとなる X の範囲は数直線上のある境界で綺麗に分かれている、と言うことができます。これが単調性です。

f:id:betrue12:20190511141733p:plain

別の言い方をすると、

  • Noと判定される X からより厳しいほうに変化させても、必ず答えはNoのままである。
  • Yesと判定される X からより甘いほうに変化させても、必ず答えはYesのままである。

という性質を両方満たすこと、と理解することもできます。

問題で問われている「条件を満たす最大値」は、図を見ると境界を挟んだYes側の値であることが分かります。そして先ほどの解法では、変数 ok が常に境界よりYes側に、変数 ng が常に境界よりNo側にある状態を保ちながら距離を縮めていくことができます。そのため差が1になったときには自動的に境界が求まっていて、正しい答えを求めることができます。

二分探索を思いつくポイント

この問題では花束の個数をある値 X に固定することで、赤青独立に考えるための道筋ができました。このように「正攻法で解くのが難しそう」「でも、値を固定することで何か嬉しいことがある」という特徴を持つ最小化/最大化問題は、二分探索を使うチャンスです。

ACコード（C++）

Submission #5333144 - AtCoder Regular Contest 050

問題例2：Boring Sequence（CPSCO Session4-D）

D - Boring Sequence

解法

この問題では、連続する部分列であってすべて同じ要素からなるものの長さの最大値を「退屈さ」と定義しています。そして数列の要素を K 個まで書き換えることで、この退屈さを最小にしたいです。

何となく「同じ要素がいっぱい連続しているところを切りたい」という気持ちになります。ただ同じ要素が連続しているところが複数ある、長さもバラバラ、そんなときにどのように切っていけば退屈さが一番小さくなるのかを考えるのは難しいです。（一応、正攻法でもできます。公式解説参照）

そこで「ある値 X が与えられたとき、退屈さを X 以下にすることはできるか？」という判定問題を考えます。これはつまり「同じ要素が連続している区間の長さを全て X 以下にできるか？」という問題と同じです。

このようにすると条件を満たすために最適な戦略がハッキリします。

  • 左から順に数列を見ながら連続している要素の個数を数えていき、 X を超えそうになった瞬間に値を書き換えて切る。

X さえ超えなければいくら長くなってもいいけど、どこか1箇所でも X を超えると一発アウトなので、 X を超えそうになるギリギリで値を書き換える権利を使う、という考え方です。

判定問題ではこの戦略をシミュレートし、合計 K 回の操作で連続している要素の個数が X を超えないようにできるかを確かめればよいです。先ほどの問題と同様、「判定問題がYesになることが明らかな値」「判定問題がNoになることが明らかな値」をから始めて二分探索をすることで答えを求めることができます。

単調性の確認

単調性を確認しましょう。ここで言い換えが「退屈さを X 以下にすることはできるか？」だったことを思い出してください。

もしこれを「退屈さを X ぴったりにすることはできるか？」と言い換えてしまうと、この解法は失敗してしまいます。「あまり X が大きいと逆に実現不可能になる」みたいな現象が起こってしまいます。この場合は判定問題も解きにくくなってしまうので散々ですね。

「 X 以下にすることはできるか？」という問題にすることで、 X が大きいほど条件が甘く、小さいほど条件が厳しくなり、単調性を満たすことができます。この判定問題の作り方については、後ほどまた触れたいと思います。

二分探索を思いつくポイント

この問題も、退屈さの値を固定すると嬉しいことがあるタイプの問題です。

特に、「できる操作に自由度があって最適な戦略が分かりづらい」「でも値を固定することで、ギリギリまで粘る・貪欲に取るなど最適な戦略がはっきりする」という点が特徴的で、このような場合には二分探索が有効です。

ACコード（C++）

Submission #5285338 - CPSCO2019 Session4

ここまでのまとめ

ここまでの解説の繰り返しになりますが、「答えを決め打つ」タイプの二分探索を見破るコツをまとめておきます。

  1. 「ある値 X が与えられたとき、○○を満たすことはできるか？」という判定問題が解きやすい。値を固定すると何か嬉しいことがある。
  2. 単調性がある。 X の値の大小と、条件の「厳しさ」が直結している。

これひょっとして二分探索なのでは？と思う問題があったら、是非この2点を満たしているかどうか確認してみてください。

典型パターン「最大値の最小化」

「Boring Sequence」のように、「○○の最大値を最小化せよ」という問題から「○○の最大値を X 以下にできるか？」という判定問題を導くのは、予め知っていないと難しいかもしれません。このような「最大値の最小化」「最小値の最大化」は二分探索で解けることが非常に多い問題なので、典型パターンとして覚えてしまいましょう。

  • 「○○の最大値の最小化」は、「○○の最大値を X 以下にできるか？」という判定問題を使って二分探索に持ち込むことができます。これは「全ての○○を X 以下にできるか？」という問題と同じです。境界で分けた時に X が大きい方が「Yes」側、小さい方が「No」側で、「Yes」側の境界値が答えです。
  • 「○○の最小値の最大化」は、「○○の最小値を X 以上にできるか？」という判定問題を使って二分探索に持ち込むことができます。これは「全ての○○を X 以上にできるか？」という問題と同じです。境界で分けた時に X が小さい方が「Yes」側、大きい方が「No」側で、「Yes」側の境界値が答えです。

もう1つの典型パターン、「 K 番目の要素の値」

これまでの内容と比べるとぐっと難易度が上がりますが、思いつくのに慣れが必要な決め打ち二分探索の代表例なので紹介しておきます。

問題例3：Median of Medians（ARC101-D）

D - Median of Medians

解法

この問題は以下のような構成をしています。

  • 長さ N の数列から、ある規則で M = \frac{N(N+1)}{2} 個の要素を生成する。（ M が非常に大きく、全列挙が難しい）
  • 生成した要素を昇順にソートする。 K = \frac{M}{2} + 1 として、このソートした数列の K 番目の要素を求めよ。

このような問題は、なんと決め打ち二分探索で解くことができます。

これまでのように最小化/最大化問題ですらない、どこがどう二分探索なんだ…と見えるかもしれませんが、こう言い換えてみましょう。

  1. 要素たちを昇順にソートした数列において、 K 番目の要素は X 以下である。
  2. 要素たちの中に、 X 以下の値が K 個以上含まれる。

この2つは必要十分条件になっています。そのため「ある値 X が与えられたとき、要素たちの中に、 X 以下の値が K 個以上含まれるか？」という判定問題を考えることで二分探索が適用できます。

ではその判定問題をどう解くか…は、前に書いたこの問題の解説記事を参照してください。この記事では「以下」ではなく「以上」で言い換えをしているので、上の説明とは少し違ってしまいますが…

ARC101 参加記録 - ARMERIA

これも二分探索に落とし込める1つのパターンとして、覚えてしまったほうが良いと思います。

実装について

今回の記事ではほとんど触れていない実装について、参考資料をいくつか紹介しておきます。

競技プログラミングでは「めぐる式二分探索」と呼ばれる実装パターンが広く知られています。私も完全に同じではないですが、めぐる式二分探索の利点を多く取り入れています。機会があればまた別記事を書くかも。

問題集

最後に「決め打ち二分探索」で解くことができる問題をたくさん紹介して終わりたいと思います。問題の解法を知りたくない、という人はここで読むのをやめてください。

読んでいただきありがとうございました。「答えを決め打つ」タイプの二分探索は初めは天才解法に見えるかもしれませんが、数をこなして慣れていくとどんどん見抜けるようになり、個人的にも好きな解法の1つです。本文中で挙げた見抜くコツや典型パターンを覚えて攻略していきましょう！

AtCoder橙になりました

AtCoder プログラミング 競技プログラミング

5月4日のAGCで、ついに橙になることができました！！！

f:id:betrue12:20190505072920p:plain

初めてratedに参加したのが昨年の4月上旬なので、およそ1年と1ヶ月での到達となりました。今年中には橙になりたいと思っていたので、予想より遥かに早くてびっくりしています。

ということで記事を書きます。ここまで来ると体系的に書けることがなくなってきたので、全体的にポエム成分が多めです。

解いた問題

f:id:betrue12:20190505082023p:plain

f:id:betrue12:20190505082204p:plain

AtCoder ProblemsのAC数と、AtCoder Scoresの精進グラフです。何だかんだでStreakをずっと繋いでいます。

全て埋めたのはABC全部と、ARCのE（昔のC）まで、AGCのDまで（今回のやつ解いていませんが）。最近はARC/AGCで残っている問題がかなり難しくなってきたので、JOIとか過去の企業コンとかを細々とやっています。

このゴールデンウィークは、コンテストに出る他はCodeforcesでDifficulty 2400くらいまでの問題をひたすら解いていました。こどふぉは最近レートが下がる一方なので復活していきたい。

これは黄色になる前も意識していたことですが、コンテスト中に考えて通せなかった問題をなるべく1～2日以内に通すようにしています。やっぱりコンテスト中に時間を費やして考えた経験は貴重ですし、その記憶が活きているうちに解ききってしまうと印象に残りやすくて効果的だと思います。

パフォーマンス推移

f:id:betrue12:20190505043918p:plain

黄色になった以降のパフォーマンスです。冷えている回もありますが、橙以上のパフォーマンスがかなりの頻度で出せるようになってきました。

たまたま最近の問題との相性が良かったという面は少なからずあります。ただ問題をたくさん解いた経験から、800点以下には（解けるかどうかは別として）気持ちで負けることはなくなりましたし、得意な問題はかなり速く、そうでない問題もコンテスト中にはACできることが多くなりました。

全般的に解ける問題の範囲が広がった、得意な問題をストレートに考察・実装して速く通せるようになった、問題が複数残っているときに自分が得意な問題を選んで取り組めるようになった、あたりが最近実感していることです。

今のところ明確に得意分野だと認識しているのは数え上げで、木の問題もわりと解ける率が高いです（木でないグラフは苦手…）。最近出た多項式の問題とかは苦手系だったり、いくつか苦手分野もありますがまあまあ平均的なタイプかなと思っています。

データ構造・アルゴリズム

私はライブラリに関しては「問題で見かけたら作る」タイプなので、あまり多く持ってはいないです。それでも黄色になりたての頃と比べるとまあまあ増えました。

高度なものは、AtCoderのratedコンテストに限って言えば必要なものはかなり少ないと思います。青上位→黄色くらいのタイミングで揃えておいたほうがいいかな？と思う代表的なものを何個か列挙しておきます。

  • セグメント木の抽象化、遅延評価セグメント木
    • 最初は蟻本ベースで「minとmaxは抽象化してないセグメント木で、sumはBITで」から始めるのが良いと思いますが、色々な演算を乗せる問題を解くようになったら頑張って抽象化しましょう。
    • 遅延評価できるものもあると便利です。遅延評価＋抽象化までできたら理想ですが、私はこれを理解するのにかなりの時間を要しました…
  • 平衡二分探索木
    • とりあえず1個あると便利。色々種類があるので好きなものを選びましょう。私は実装が楽なTreapをずっと使っています。
    • 個人的につまずきポイントだったのが、「集合」を管理するものと「列」を管理するものがあって微妙に実装や使い方が違うということ。前者を平衡二分探索木、後者を平衡二分木と呼んでいることもあるように思います。
  • フロー（最大フロー・最小カット、最小費用流）
    • ソラで書くとけっこう大変なので用意しておくと良いです。Dinic法が良いらしいですが私は最近書きました。
    • フローの問題は結構独特だと思います。入力制約がやけに小さかったり、問題で課せられる条件が複雑に関係し合っていたり…「フローに帰着させることができればあとはライブラリに突っ込むだけ」なんですが、帰着のさせ方にも慣れが要ると感じています。
  • 強連結成分分解、二重辺連結成分分解
    • 閉路を潰すことで、それぞれ有向グラフをDAGに・無向グラフを木に変換するアルゴリズムです。DAGや木は扱いやすいことが多く、グラフをこれらに変換して考えられないかという視点は大事になると思います。
  • 文字列アルゴリズム、データ構造
    • Z-Algorithm、Manacher、ローリングハッシュ、Trieなど。文字列アルゴリズムといいつつ数列についても使うことが多いので、両方に対応できるライブラリだと良いと思います。
    • Suffix ArrayやAho-Corasick法など、まだ使ったことがないものもたくさんあります。習得していきたいですね。

テクニック、思考パターン

これは文章化するのがとても難しい内容なんですが、AtCoderのレート上昇に一番効くのはやっぱりここだと思います。

二分探索に持ち込む、操作列やゲームを後ろから考える、クリティカルな特徴量を見つけ出す、差分更新で計算量を削減する、余事象や包除で数えやすくする、必要条件を洗い出して十分性を検証する…こういったテクニックの引き出しはけっこう充実してきたなと思います。そしてそれをどうやって増やすのかというと、やっぱり問題を解きまくるしか無いのかなあと。

高い得点の問題で要求される考察や閃きをゼロから自力で思いつくのはやっぱり難しくて、「似たことをやったことがある」「何となく見覚えがある」という過去の問題の記憶が大きな助けになることが多いです。実際にコンテスト中に過去の問題を思い出して解説を読みに行く、ということもたまにしています。

ただ人間はどうしても忘れるものなので、記憶に定着させる方法や思い出す方法が必要だなと感じます。ブログを書いたりAC記録を付けるのは良い方法だと思います。本当は解いた後時間が経った問題を解き直すのが一番良いんでしょうけど、どうしても新しい問題を解くほうを優先させてしまうので難しいです…

モチベーション維持

ここはレート帯に関係なく多くの人が悩むところなんじゃないかと思います。時間を使わないと実力とレートは伸びませんし、競プロに時間を使おうという気持ちになるためにはモチベーションが必要です。そしてモチベーションを上げるにはレートが上がることが必要で…と循環します。

私のモチベーション維持に関して、黄色になって以降特に大きかったなと思ったのは「オンサイトコンテストの存在」と「ライバルの存在」です。

昨年度の冬はDDCCや日経コンテストなど大規模なオンサイトコンテストが多く、そこでたくさんの人達と会うことができました。普段はコンテストもオンラインでやっていますし交流もTwitterがメインなので、実際に会って話すのはとても楽しかったですし、オンサイトに行くために実力を上げて良い順位を取ろうという気持ちになりました。あの頃の精進は今かなり効いていると思います。

あとはライバルの存在です。レート帯が近い人はだいたいライバルなんですが、特にAtCoderを始めた時期も黄色になった時期も近くて実力も伯仲しているメンバーのレートや順位はコンテストのたびに意識しています。負けたくないという気持ちは大きなモチベーション源になっています。いつもありがとうございます。

競プロは他の人との実力差が数値として可視化されてしまいますし、上を見るとキリがないです。正直、「強い」人の発言を見て自分が否定されているように感じたり、自信を失うという機会もとても多いです。実力が近くて勝ったり負けたりする位の人とライバル関係を結び、ともに実力を上げていくのが理想的だと思っています。

私個人としては「長期間伸び悩む」という経験がまだないですが、次は赤なので当分は無理ですし、橙は維持するだけで大変だろうと思っています。たぶんまた黄色に落ちる経験もするでしょう。ここからモチベーションを維持して着実に実力を伸ばしていくことが大事ですね。

解説記事について

最近更新頻度がガタ落ちしています…いつも読んでくださっていた人々にはとても申し訳ないです。

自分で問題を解くほうを優先させてしまったり、特にABCオンリー回だと公式解説がかなり丁寧で補足するところがなかったり、コンテスト毎ではなく問題ごとの形式に変えたので解説が書きにくい問題は避けてしまったり…という現状なのですが、少しずつ更新頻度を復活させていきたいとは思っています。

あとは問題解説以外にも、データ構造やアルゴリズムの解説を充実させていきたいなあという気持ちもあります。私自身がたくさんの解説資料に助けられて勉強してきたので、今ちょうどいい資料がないものを埋めていくお手伝いくらいはできたらなと。何か良い題材ありますかね？ちょっと考えます。

さいごに

長文を書くのが好きなので長文になってしまいました。もう当分色上がりました記事は書けないと思うので色々書きました。

橙になっても相変わらずコンテストに出て精進し続けていると思いますので、引き続きよろしくお願いします。

いろはちゃんコンテスト Day1 L - をあ ぷろぶれむ

AtCoder プログラミング 競技プログラミング

L - をあ ぷろぶれむ

解法

初手は二分探索

この問題のように、

与えられた数列などから、列挙しきれない個数の要素（入力 N 個に対して O(N^{2}) 個など）を計算する。それらをソートしたときの K 番目の値を求めよ。

という形式の問題では、二分探索が有効なことが多いです。大きい方から K 番目の値が x であるときは x 以上の要素が K 個以上あり、「 x 以上の要素が K 個以上ある」という条件を満たす最大の x が求める答えになります。

ということで「 x を固定した時に、 x 以上の要素が K 個以上あるか？」というYes/No判定問題を考えます。

答えの範囲は \min A_{i} から A_{i} の全要素のOR値まであり得るので、全要素のOR値を A_{all} と書くことにするとこの二分探索の反復回数は O(\log A_{all}) 回です。

数え方を効率的に

さて、 x 以上の要素はどのようにすれば効率的に数えることが出来るでしょうか。

それぞれの要素は与えられた数列 A_{i} の区間ORです。区間を伸ばす（ORに参加する要素を増やす）ことでORの値が減ることはないので、ある左端 l を固定した時に区間ORが x 以上になるような右端 r の範囲には単調性があります。そのため、しゃくとり法を使うことができます。

全ての左端それぞれについて条件を満たす右端の境界を求め、区間の個数を数えます。このときの判定には「今見ている区間 \lbrack l, r) について、その区間ORは x 以上か？」という情報が必要になります。これを求める方法として2つ紹介します。

セグメント木、Sparse Tableを使う

これらのデータ構造を用いると区間ORを計算することができます。今回は更新クエリが必要ないためSparse Tableも使うことができます。

クエリの時間計算量はセグメント木が O(\log N) 、Sparse Tableが O(1) 。しゃくとり法が回るのに O(N) 掛かるため、全体計算量は

  • セグメント木： O(N \log N \log A_{all})
  • Sparse Table： O(N\log N + N \log A_{all})
    • ※Sparse Table構築に O(N\log N) かかるため

となります。記事末尾にACコードリンクを貼っていますが、セグメント木でもギリギリ間に合いました。

ビットごとに個数カウント

区間ORが計算できるデータ構造を持っていない…という場合にも解くことができます。

しゃくとり法で要素を区間に入れたり出したりする際には、上記のように区間の値を直接計算する他に、差分で更新する方法もよく使います。例えば区間和を扱っている場合は、要素を区間に入れる時に値を足し、区間から出す時には引けばよいです。

困ったことにOR演算の場合は、区間に入れる時には単にORで足せばよいのですが、引き算ができません。

ですが手段はあります。OR演算はビットごとに考えることができて、各ビットについて「区間内に d ビット目が立っている要素が1個以上あれば、区間ORの d ビット目は1である」ということが言えます。つまり「今区間内に d ビット目が立っている要素がいくつあるか」をビットごとに管理しておけば、区間からの出し入れはこの値を増減させることで実現できます。そしてこの値が 0 \to 1 または 1 \to 0 と変化したときに区間ORの値を変化させればよいです。

これでしゃくとり法が実現できます。ビット数が O(\log A_{all}) であることから、全体計算量は O(N \log^{2} A_{all}) となります。 A_{all} が大きめなので厳しそうですが、これでも間に合いました。

ACコード

実行時間はSparse Tableが一番良いですね。私はコンテスト本番では3つ目の方法で通しました。

Codeforces Round #554 F. Neko Rules the Catniverse

Codeforces プログラミング 競技プログラミング

Problem - F1 - Codeforces

Problem - F2 - Codeforces

問題概要

整数 n, k, m が与えられる。以下の条件を満たす要素数 k の数列 a_{1}, ..., a_{k} は何通りあるか、 \bmod 10^{9}+7 で求めよ。

  • 1 \le a_{i} \le n
  • a_{i} \le a_{i-1} + m
  • a_{i} は相異なる

制約

  • F1とF2で n の範囲が異なる。
    • F1: 1 \le n \le 10^{5}
    • F2: 1 \le n \le 10^{9}
  • 1 \le k \le \min(n, 12)
  • 1 \le m \le 4

解法

何となく数列の頭から順に決めていくDPを考えたくなりますが、「相異なる」という条件が厄介です。これをまともに扱おうとそれまで使ったことのある整数を情報として持つことが必要になり、数列の長さがたった12しかないとはいえ値の種類数 n がそこそこ大きいのでとても大変です。

見方を変えて、「値のほうを 1 から n まで順に見ていって、使う整数を数列に挿入していく」というDPを考えてみましょう。以下のようなDPテーブルを考えます。

dp\lbrack i \rbrack\lbrack j\rbrack = 整数 1 から i までを使うかどうか決めて、長さが j で、問題の条件を満たしているような数列の個数

実はこれだけでは情報として不十分ですが、いったんこんな方針だと思ってみましょう。

dp\lbrack i \rbrack\lbrack j\rbrack からの遷移を考えます。 i+1 を挿入するとき、それを挿入できる場所は

  • 先頭
  • 既に数列にある整数のうち、 i+1 \le x + m であるような x の後ろ

のいずれかです。

また、挿入する位置の後ろの整数との関係は常に条件を満たします。後ろの整数を y とすると条件式は y \le i+1+m ですが、今までの値より大きい値を常に挿入するのでこれは常に満たされます。

f:id:betrue12:20190425220354p:plain

そして数列が具体的にどのような並びであろうと、挿入できる箇所の個数は変わりません。ここが挿入DPの大きな特徴です。

そのため i+1 を挿入できる場所の個数を知るためには、 i+1-m から i までの m 個の整数が数列に存在しているかという情報があれば十分です。これをDPテーブルの状態に加えましょう。

dp\lbrack i \rbrack\lbrack j\rbrack\lbrack S \rbrack = 整数 1 から i までを使うかどうか決めて、長さが j で、 i+1-m から i までの整数のうち数列に含まれているものの集合が S であって、問題の条件を満たしているような数列の個数

ここで S は m 個の整数のある/なしを表しているので 2^{m} 通りです。実装上はそれぞれをビットで管理した整数として扱いましょう。最下位ビットを整数 i に、最上位ビットを整数 i+1-m に対応させておくと、ビットシフトで見ている範囲をずらすことができます。

こう置くと、 dp\lbrack i \rbrack\lbrack j\rbrack\lbrack S \rbrack からの遷移は

  • 整数 i+1 を使う。
    • S の立っているビットの個数を b として、 b+1 倍して dp\lbrack i+1 \rbrack\lbrack j+1\rbrack\lbrack (S\lt\lt 1) \% 2^{m} + 1 \rbrack に遷移する。
  • 整数 i+1 を使わない。
    • dp\lbrack i+1 \rbrack\lbrack j\rbrack\lbrack (S\lt\lt 1) \% 2^{m}\rbrack に遷移する。

と書くことができます。

※一般に挿入DPで考慮すべきこととして、「隣り合った要素がいったん条件に違反していても、後で他の値を間に入れることで違反が解消されるかもしれない」というものがあります。しかし今回は常に今までより大きな値を入れていくため、 a_{i} \le a_{i-1} + m に違反しているような a_{i-1}, a_{i} の間にこれらより大きな値を入れても依然違反状態であり、解消されることはないので考慮しなくて大丈夫です。

このDPを普通に計算すると計算量が O(nkm2^{m}) になります。F1の制約においてはこれは十分間に合います。

F2においては n が非常に大きく、 O(n) が掛かるような解法は厳しいです。これを解くためDPの遷移に注目すると、

  • dp\lbrack i+1 \rbrack\lbrack j\rbrack\lbrack S \rbrack は、いくつかの dp\lbrack i \rbrack\lbrack \cdot \rbrack\lbrack \cdot \rbrack に i に依存しない係数を掛けたものの和（線形結合）である。
  • dp\lbrack i \rbrack\lbrack \cdot \rbrack\lbrack \cdot \rbrack の要素数を L と置くと、 L = (k+1)2^{m} であり最大でも200程度と非常に小さい

ということが分かります。このことから遷移は長さ L のベクトルに L \times L 行列を掛けることとみなすことができて、行列累乗により O(L^{3} \log n) で解くことができます。

ACコード

競プロerのためのはてなTeX記法チートシート

基本から応用（？）までガッツリ書こうかなとも思ったんですが、はてなTeXそのものの解説記事は検索するといっぱい出てくるので、私が競プロ記事でよく使うものを箇条書きのように紹介する記事にしようと思います。

私はMarkdownモードを使っているので、Markdownモードに準じて書いていきます。他モードとは一部エスケープの扱いが異なります。

まずはじめに

はてなTeXは癖が強く、慣れないうちは必ずバグります。慣れてもバグります。

こまめにプレビューを確認しながら書く癖を付けると良いと思います。私もこの記事を書く過程で数十回プレピューを見ています。

TeX記法の使い方

数式表記にしたい範囲を [tex: ] で囲みます。

  • [tex: ax+b] → ax+b

個人的な好みとしては前後に半角スペースを入れると少し読みやすいです。

  • （スペースなし）求めたい最小値を xとします。
  • （スペースあり）求めたい最小値を x とします。

上付き文字・下付き文字

上付き文字は ^ を使い、必ず {} で囲むとよいです。

  • [tex: a^{x}] → a^{x}

下付き文字は \_ を使い、必ず {} で囲むとよいです。ただしMarkdownモード以外の場合は _ で良いようです。

  • [tex: a\_{x}] → a_{x}

バグらずに上手くパースされるためのテクは他にもいくつかあるようですが、私はこれを使っています。慣れないうちは特に下付き文字の \ を忘れてバグると思います。慣れましょう。

分数

\frac を使います。

  • [tex: \frac{a}{b}] → \frac{a}{b}

\log や \min など

TeX環境ではアルファベットは標準で斜体になり、 log のようになります。これでも読めることは読めますが、数式内でアルファベットで表記するいくつかの関数名は \ を付けることで斜体でない形式で表示することができて、そちらのほうが意味が明確になるので望ましいです。

  • [tex: \log N] → \log N

例のようにアルファベットが続く場合はスペースが必要です。スペースを空けないと \logN のようにバグります。

このように使える関数名などは こちら を参考にしてください。はてなTeXではなく一般的なLaTeXの話なので差異があるかもしれません。

競プロでよく使うのは \min, \max, \log, \gcd, \bmod あたりでしょうか。 \bmod は \bmod と書かないと出てこないので注意です。

数学記号

先ほどの \log などと同様、バックスラッシュで始まるコマンドとして入力できます。リストは こちら を参考に。ギリシャ文字もあります。

  • [tex: \forall] → \forall
  • [tex: \alpha] → \alpha

不等号

競プロ記事でよく使いますね。

  • [tex: a \lt b] → a \lt b
  • [tex: a \le b] → a \le b
  • [tex: a \gt b] → a \gt b
  • [tex: a \ge b] → a \ge b

「less than」「less than or equal to」「greater than」「greater than or equal to」と覚えましょう。

カッコとか囲む系

普通の丸カッコ () は単に () ですが、 \lbrace\rbrace や \lbrack\rbrack は専用のコマンドを使います。

  • [tex: \lbrace a \rbrace] → \lbrace a \rbrace
  • [tex: \lbrack a \rbrack] → \lbrack a \rbrack

角カッコは [tex: \[a\]] のようにエスケープしても一応 [a] のように表示できますが、左右非対称になってちょっと汚いです。 dp\lbrack i \rbrack\lbrack j \rbrack などをキレイに書く場合はちょっと面倒ですが \lbrack \rbrack を使うとよいです。

また競プロでよく使う切り捨て・切り上げの表記も、同じような記法で書くことができます。

  • [tex: \lfloor a \rfloor] → \lfloor a \rfloor
  • [tex: \lceil a \rceil] → \lceil a \rceil

二項係数

_{n}C_{k} 。ピンポイントですが競プロでよく使うので。左側に下付き文字を付けるコマンドではなく、無に下付き文字を付けることで対処します。

[tex: \_{n}C\_{k}] → _{n}C_{k}

ビット演算

プログラミングにおけるビット演算の記号は、数式ではそのまま使われないことが多いのでちょっと苦労します。私は数式モードではなく a & b とバッククォートで囲む記法に逃げることが多いですが、一応書くことはできるようです。

  • [tex: a \And b] → a \And b
  • [tex: a | b] → a | b
  • [tex: a^{\wedge} b] → a^{\wedge} b

数式における縦棒は「割り切れる」ことを示す記号として使われることのほうが多いので注意。文脈からORであることが明らかな場合は使っても良いとは思います。

XORは問題文などではよく \oplus を用いて a \oplus b と書いてあるので、私はそちらを使うことのほうが多いです。

日本語

わざわざ変数に置くのが冗長だなと思った時に、数式内に日本語を直接書いてしまうことがあります。ちょっとフォントが他の文と違って見えますが、普通に読めることが多いです。

[tex: (三角形の面積) = (底辺) \times (高さ) \div 2] → (三角形の面積) = (底辺) \times (高さ) \div 2

総和、総積

いわゆるシグマ。

  • [tex: \sum a\_{i}] → \sum a_{i}
  • [tex: \prod a\_{i}] → \prod a_{i}

これに添え字をつけようとすると \sum_{i=1}^{N} a_{i} みたいになってごちゃごちゃします。私の場合は i=1, ..., N の場合など文脈から十分読み取れるだろうと思ったら添字を省略してしまうことが多いです。後述の \displaystyle を使うという手もあります。

\displaystyle を活用する

いままでの記法では、複雑な分数が縦に潰れてしまったり、シグマの添字が見づらかったりします。これを解決するために \displaystyle というものがあります。

  • [tex: \displaystyle \sum\_{i=1}^{N} a\_{i}] → \displaystyle \sum_{i=1}^{N} a_{i}
  • [tex: \displaystyle \frac{ax+b}{cy+d}] → \displaystyle \frac{ax+b}{cy+d}

私はまだ使ったことがないですが、要所要所で使えると便利だと思います。

おわり

他に何かあれば随時追記していきます。

とりあえずこれだけ書ければ競プロ記事を書くにはあまり困らないと思います。もちろん公式解説のようにガッツリ証明を書く場合などは苦しいかもしれません…その場合は素直にはてな以外で書くことをオススメします。

慣れるまではとにかく仕様との戦いになり、記事の内容とは関係ないところで時間を使うことになると思います。そのため競プロのブログを書く全ての人にオススメできるわけではありませんが…手間をかけた分だけ記事の見た目は良くなるので、興味があれば是非試してみてください。

Tenka1 Programmer Contest 2019 F - Banned X

AtCoder プログラミング 競技プログラミング

F - Banned X

気合いで数える問題。ARC-FやAGC-Dあたりの数え上げをやりまくったおかげで解けたかな…と思います。

解法

まず、全要素の合計が X 未満かどうかで場合分けをします。

合計が X 未満である場合

要素の合計が X 未満である場合はどのように数を並べてもよいです。このような場合の数は以下のようなDPで求められます。

dp\lbrack i \rbrack\lbrack j \rbrack = 各要素の値を 0, 1, 2 から選ぶことにして、 i 個目までの値を決めて、合計が j であるような場合の数

このDPを計算して j \lt X の範囲における dp\lbrack N \rbrack\lbrack j \rbrack を全部合計すれば、要素の合計が X 未満であるような場合の数が求められます。

※後で必要になる「各要素の値を 1, 2 から選ぶことにしたときの場合の数」を利用して計算することもできます。

合計が X を超える場合

合計が X 以上の場合を考えます。ただし X ぴったりになってはいけないので、 X を超える場合を考えます。

0, 1, 2 を並べた数列の代わりに、その累積和を前から並べた数列を考えます。そしていったん 0 は考えないことにして、狭義の単調増加になっている累積和の列を考えます。

このとき、累積和が X を超えるタイミングでは X-1 から X+1 へのジャンプが起こっているはずです。そして X+1 が存在するので 1 が存在してはいけません。なので累積和の並びは、

0, 2, ..., X-1, X+1, ...

となっているはずです。

X+1 の先はどうなるでしょうか。 2 があるので X+2 を作ってはいけません。なので X+1 から増えるとすれば X+3 にまたジャンプしないといけません。そして 3 が存在してはいけないので、

0, 2, 4, ..., X-1, X+1, X+3, ...

となるはずです。

ここから規則性が掴めます。ある正の奇数を y として、数列の最大値が X + y であるとします。そのとき部分和に X が現れない条件は、累積和の数列について

  1. 0 から y+1 までは全て2ずつ増加する。
    • この過程で X が出現してはいけない。つまり X が偶数でかつ X \le y+1 のときはNG。
  2. y+1 から X-1 までは自由に増加して良い。（ y+1 \lt X-1 のとき）
  3. X-1 から X+y までは全て2ずつ増加する。
    • X が奇数で y+1 \ge X-1 のときは、これは1. の範囲と重なるので、単に 0 から X+y まで2ずつ増加するような数列になる。

と書き下すことができます。

さて、累積和がこのような条件を満たすような元の数列の個数を数えましょう。このとき 0 の存在が厄介で、上記のどのパートにも途中で 0 が入ってくる可能性があります。そのため「まずは 1, 2 だけで条件を満たす数列を作った後、 N 個に足りない個数だけ 0 を追加する」という作戦でいきます。

いくつかのパラメータを固定しましょう。まずは最大値に関わる y を固定します。

y+1 \ge X-1 であるとき

y+1 \ge X-1 であるような y に関しては、 X が偶数のときは0通りです。

X が奇数のときは、 0 から X+y まで2ずつ増加します。つまり \frac{X+y}{2} 個の 2 と N - \frac{X+y}{2} 個の 0 を並べる場合の数になり、これは _{N}C_{(X+y)/2} 通りです。

y+1 \lt X-1 であるとき

この場合、 y+1 から X-1 まで自由に増加してよいパートがあります。 0 の入れ方を処理するためには要素の個数が決まっていないといけないので、さらにこのパートで要素 1 または 2 をいくつ使うかを場合分けします。ここで n 個の要素を使うとすると、各パートは

  1. 0 から y+1 までは全て2ずつ増加：要素 \frac{y+1}{2} 個、 2 を並べるだけなので1通り
  2. y+1 から X-1 までは自由に増加：要素 n 個、？？通り
  3. X-1 から X+y までは全て2ずつ増加：要素 \frac{y+1}{2} 個、 2 を並べるだけなので1通り

となります。ここで2. の場合の数は、

dp2\lbrack i \rbrack\lbrack j \rbrack = 各要素の値を 1, 2 から選ぶことにして、 i 個目までの値を決めて、合計が j であるような場合の数

というDPテーブルを前計算しておくとそこから持ってくることができます。具体的には dp2\lbrack n \rbrack\lbrack X-y-2 \rbrack です。

そして要素の個数は n+y+1 であり、合計が N 個になるように N - (n+y+1) 個の 0 を追加することになるため、 _{N}C_{n+y+1} を掛けると場合の数が求められます。

これら全てを合計すれば答えを求めることができます。計算量はDPがいずれも O(N^{2}) で、最後の場合分け（解説中の y と n ）も O(N^{2}) 通りなので、全体 O(N^{2}) で解くことができます。

ACコード

Tenka1 Programmer Contest 2019 D - Three Colors

AtCoder プログラミング 競技プログラミング

D - Three Colors

解法

三角形の成立条件は、3辺すべてについて「その辺の長さが、他の2辺の長さの合計より小さい」ことです。ただこれをそのまま扱おうとすると3辺全部の長さを管理しながらDPなどをする必要があり、難しそうです。

逆に三角形が成立しない条件を考えます。それはある辺について「その辺の長さが、他の2辺の長さの合計以上である」ことです。こうするとずっと考えやすくなります。

仮に条件を満たさない辺を R としましょう。3辺の長さの合計は与えられた a_{i} の合計になるので、この値を S と置くと R+G+B = S です。辺 R について三角形が成立しない条件は R \ge G+B と書けるので、これは R \ge \frac{S}{2} となります。これで R の長さだけを管理すれば良いことが分かり、以下のようなDPで場合の数を計算することができます。

dp\lbrack i \rbrack \lbrack j \rbrack = 各要素を赤緑青の3色に塗り分け、その色を i 個目まで決めた時に、赤を塗った要素の合計が j であるような場合の数

遷移はシンプルで、 dp\lbrack i \rbrack \lbrack j \rbrack から i+1 番目の要素を赤に塗ると dp\lbrack i+1 \rbrack \lbrack j+a_{i+1} \rbrack に遷移し、他の2色に塗った場合は（つまり、2倍して） dp\lbrack i+1 \rbrack \lbrack j \rbrack に遷移します。最終的に j \ge \frac{S}{2} であるような j に対して dp\lbrack N \rbrack \lbrack j \rbrack を合計したものが「辺 R について三角形が成立しない条件を満たすような場合の数」です。

対称性より辺 G, B についても同じなので、上記の値を3倍して全事象数 3^{N} から引けば終わり…かと思いきやそうはいきません。私もこれを実装した後サンプル2が合わなくて手が止まりました。複数の辺について同時に三角形が成立しない条件を満たすケースがあり、それらは重複して数えられているので戻してあげないといけません。

3辺について同時に条件を満たすことはありません。 S = R+G+B としたときに R \ge \frac{S}{2}, G \ge \frac{S}{2}, B \ge \frac{S}{2} が同時に成り立つことはないからです。

2辺について、例えば R, G について同時に条件を満たすことはあり得ます。その場合は必ず R = G = \frac{S}{2}, B = 0 であるはずです。このような場合の数を求めましょう。それは先ほどのDPとほぼ同じように、以下のDPを回すことで求めることができます。

dp2\lbrack i \rbrack \lbrack j \rbrack = 各要素を赤緑の2色に塗り分け、その色を i 個目まで決めた時に、赤を塗った要素の合計が j であるような場合の数

先ほどとの遷移の違いは、赤を塗らない方の遷移を2倍しないことだけです。これを計算して dp2\lbrack N \rbrack \lbrack \frac{S}{2} \rbrack が求めたい「辺 R, G について同時に三角形が成立しない条件を満たすような場合の数」です。

R, G について、 G, B について、 B, R についてそれぞれ条件を満たす場合があり得るので、対称性よりこれを3倍して答えに足し直してあげればOKです。

それぞれのDPは i が N まで、 j が \sum a_{i} まで回り、遷移は O(1) なので計算量 O(N^{2}\max a_{i}) で解くことができます。

ACコード

Submission #5045204 - Tenka1 Programmer Contest 2019