AtCoder Beginner Contest 155 E - Payment
上から派と下から派がいたようですが、私は上からで解いたのでそちらで書きます。
解法
上の桁から見ていって、その桁までで支払う&お釣りとして受け取る硬貨の枚数をなるべく小さくすることを考えます。
例えば 円だったとして、 の位の桁までの硬貨の支払い&お釣りを処理し終わったとします。このとき支払っている合計金額としては、
- 円。つまり、見ている桁のぴったりまで支払っている。
- 円。つまり、見ている桁の硬貨1枚分だけ多く支払い、それより下の桁でお釣りをもらう。
などが考えられます。そして実は、この2通り以外は考える必要がありません。
もし金額不足、つまり例えば 円しか払っていないとしましょう。このときは不足分を大量の 円玉で支払わないといけないので、 円玉で払うより明らかに損です。
同様にもし2枚分以上多く支払う、つまり例えば 円払っていたとします。このときも大量の 円玉でお釣りをもらう羽目になるので、 円玉を払う枚数を減らすべきです。また例えば 円玉 枚で 円を払っていたとしても、 円玉としてお釣りをもらっておくほうが得です。
このように、各桁を見終わった時の支払い金額は「その桁までぴったり」か「1枚分だけ多い」かに限定されます。そのため、この2つを状態として持つようなDPを考えることができます。
は大きいので文字列として扱い、最上位の桁を 桁目として書きます。ここで最初に の先頭に を付けておくと扱いが楽になります。例えば 円であるときは 円玉(?)を払うのが最適であるように、与えられた の最上位桁より1つ上の硬貨までは使う可能性があるからです。
DPの状態を以下のように考えます。
上から 桁目までの硬貨の支払いとお釣りを処理し終わって、 の 桁目までの金額よりも 枚分多く支払っているときの、これまでの支払い・お釣り硬貨の最小合計枚数
から までの遷移を4通り考えましょう。 の 桁目の数を と表記します。
- から への遷移:お釣り発生はなく、単に 桁目の硬貨を 払うので、 が加算される。
- から への遷移:お釣り発生はなく、 桁目の硬貨を余分に払うので、 が加算される。
- から への遷移:お釣りが発生する。 桁目の硬貨をお釣りとして 枚受け取るので、 が加算される。
- から への遷移:お釣りが発生する。 桁目の硬貨をお釣りとして 枚受け取るが、そのうち1枚は余分に払う用に返す。そのため が加算される。
このDPを行い、最後の桁まで見終わったときの「その桁までぴったり支払った」最小合計枚数が答えになります。
他にも色々解法はあるようですが、本記事の解法も含めて多くの解法は「こういう状態は絶対に損」「なのでこういう状態や遷移だけを考えれば十分」という考察が少なからず必要になり、その考察が正しいかに全てが掛かっています。例えば「同じ硬貨を 枚以上払ったりお釣りとして受け取るのは絶対に損」という知見だけを使って各硬貨を 枚払う遷移を全て試すDPなんかも堅実で良さそうですが、実行制限時間が厳しいかもしれません…。
ACコード
Submission #10151891 - AtCoder Beginner Contest 155
コンテスト本番のコードなので違う解法を考えていた時の累積和がそのまま残っていますが、使っていないので気にしないでください…
AtCoder Beginner Contest 155 D - Pairs
※正直、これがABC-Dとして出るのはここ最近の傾向からすると異常です。じっくり解説を読んで理解するか、どうしても分からなければ温めておくのも手でしょう。
解法
二分探索に落とし込む
与えられた数列などに対して大量の数を計算し、その 番目の数を求めよ…という問題でよく使うテクニックがあります。これは思いつくのは大変なのでパターンとして覚えてしまいましょう。二分探索です。
判定問題として、
数える対象となる 個の数のうち、 以下の数は 個以上あるか?
というものを考えます。もしこれがYesだった場合、 番目の数は 以下です。逆にNoだった場合、 番目の数は より大きくなります。
二分探索では判定問題が「絶対にYesになる値」と「絶対にNoになる値」を初期値に選びます。判定問題を「対象となる数のうち、 以下の数は 個以上あるか?」とすると、 が大きいほど条件を満たしやすいので、Yes側の初期値を非常に大きい値、No側の初期値を非常に小さい値にします。そしてこの判定問題がYesになるような最小の整数 が、求めたい答えになります。
今回の答えは の範囲にある数2つを掛け算した値のどれかなので、絶対値が 程度まで大きくなり得ることに注意して初期値を決めましょう。
このタイプの二分探索は「○○の最大値を求めよ」のようなタイプよりも判定条件や初期値の設定がイメージしづらいので、図を使って整理するのがオススメです。では判定問題の解き方を考えましょう。
判定問題を解く
後々のために をソートして、小さい方から順に見ていきましょう。対象となるのは異なる2要素の積で、ペアの入れ替えは重複して数えません。そのため要素 を見るときには、既に見終わった 番目までの要素 のうち、 となるものの個数を数えます。
この不等式の解き方は、 の符号によって場合分けされます。
- のとき、不等式は となります。
- のとき、不等式の両辺を負の数で割ると符号が逆転するので、条件は となります。
- のとき、不等式は となってしまいます。つまり の符号に応じて、条件を満たす は全部もしくは0個になります。
のとき以外は、条件を満たす は を境として、それ以上もしくはそれ以下の範囲にあるものです。これは最初に数列をソートしておけば、やはり二分探索を用いて求めることができます。
図のように 以降のものは数えてはいけないのと、 が整数にならない(しかも負の数になる)場合があるため、C++の lower_bound
などを用いて二分探索するにしてもちょっと実装が難しいです。
※尺取り法でもできますが、この方針で尺取り法をやろうとすると の符号によって境界がずれる方向が変わるので非常に面倒でした…
または以下のようにするのも1つの手です。こっちのほうが楽かも。
- 右端を考えずに、毎回全ての について計算する。
- 同じ要素同士を掛けたものを取り除きたいので、 を全部試して 以下だったものの個数だけ引く。
- ペアの順番が逆になったものが重複して入っているので、全体を で割る。
これで積が 以下となるような要素のペアの個数を求めることができたので、それが 以上かどうかを見れば判定問題が解けます。
ACコード
このコードはlower_bound
/upper_bound
とイレテータの足し引きをゴリゴリに使っているので読みづらいかもしれません…。あとで尺取り法での実装もリンクを貼りたいと思います。→書きましたが、 の符号で場合分けが必要なのでこの方針だと微妙でした…。
Codeforces Round #619 (Div.2) E. Nanosoft
問題概要
のマス目が与えられ、各マスは赤・緑・黄・青のいずれかに塗られている。
このマス目から の連続する正方形領域を取り出したときに、それが問題文の図の位置関係通りに4色の の正方形で構成されているとき、これをレベル のNanosoftであると呼ぶことにする。
以下のクエリに 回答えよ。
- 左上のマスが , 右下のマスが である長方形領域に含まれる最大レベルのNanosoftの面積を求めよ。長方形領域がNanosoftを含まない場合は を出力せよ。
制約
解法
まず、Nanosoft判定をするために「ある正方形領域のマスが全て○色であるか」という判定を何度も行う必要がありそうです。これは色 ごとに「マス の色が ならば 、そうでなければ 」という配列を用意して二次元累積和を取っておけばよいです。
の正方形領域について、ある代表点の位置を決めましょう。そして「代表点を とする の正方形領域は、レベル のNanosoftであるか?」という情報をクエリに備えて前計算しておくことを考えます。
このとき代表点を以下の位置に決めると、各代表点について単調性が成り立ちます。すなわち代表点 がレベル について条件を満たすならば、任意の に対してもレベル について必ず条件を満たします。
このことから二分探索によって、各代表点が条件を満たす最大のレベル を求めることができます。これを単に代表点の最大レベルと呼ぶことにします。
それではクエリの処理方法を考えます。クエリで指定された長方形領域にレベル のNanosoftが含まれるならば、その一部としてレベルが より小さいNanosoftは常に含まれます。つまり単調性が成り立つので、「クエリで指定された長方形領域に、レベル のNanosoftが含まれているか?」という判定問題を用いた二分探索をしましょう。
クエリで指定された長方形領域に の正方形領域が収まっているときに、その正方形領域の代表点が存在する範囲を考えます。これは以下のように図示するとやはり長方形領域になることが分かります。
この領域の中に最大レベルが 以上であるような代表点が存在すれば良いです。この判定は、長方形領域の最大値を効率的に求められるようなデータ構造に各代表点の最大レベルを入れておくことで処理できます。例えばセグメント木やスパーステーブルを二次元に拡張したものを用いることができます。
二次元セグメント木は構築 、更新・取得クエリに かかります。二次元スパーステーブルは構築 、取得クエリ です。今回はクエリ数が多いので、二分探索を含めて各クエリに を3つ付けるセグメント木だとギリギリです。スパーステーブルが良いでしょう。
ACコード
- セグメント木(1996ms):Submission #71000872 - Codeforces
- スパーステーブル(670ms):Submission #71096960 - Codeforces
Educational Codeforces Round 82 F. Number of Components
※解説の都合上、マスに書かれている整数を「色」と表現することにします。記号も だし。
問題概要
のマスからなる盤面があり、各マスには色が塗られている。このマスそれぞれを頂点とし、隣り合うマスの色が等しいときにその間に辺を張るようなグラフを考える。
色は整数として表現され、全てのマスには初期状態で色 が塗られている。以下のようなクエリを 個処理せよ。
- 番目のクエリは整数 で特徴付けられる。マス の色を に変更し、その後グラフの連結成分の個数を答えよ。
ここで任意の に対して である。
制約
解法
連結成分の管理と言えばUnion-Findですが、Union-Findは連結成分を併合していくという操作に非常に強い一方で、分離する(辺や頂点を削除する)という操作に弱いです。この問題ではいったん繋がったマス同士が、間を別の色に上書きされることで切れてしまう可能性があります。なんとか併合だけで解き切れないでしょうか。
ここで という条件に注目します。考える色 を1つ固定すると、その色のマス目は「 である間は増えていき、 になってからは減っていく」という一種の単調性があります。これを利用しましょう。
クエリを順番に適用することを時間の経過として考え、 番目のクエリを適用する時刻をそのまま とします。色 のマスが増えていく間は時間を順方向に、色 のマスが減っていく間は時間を逆方向に見ていくことで、どちらも色 の頂点とその間の辺が増えていく方向に処理を進めていくことができます。これならUnion-Findが使えます。
具体的な処理方針です。まずはクエリ操作をシミュレートしながら、色 ごとに「時刻 にマス の色が新しく になった」というinイベントと「時刻 にマス の色が でなくなった」というoutイベントを並べます。ただし同じ色で上書きしているところは単に無視します。ここで
- 初期時刻 に、全てのマスの色が新しく になった。(inイベント)
- 最後のクエリより後の時刻 に、全てのマスの色が消えた。(outイベント)
というイベントも追加することにすると、両端の条件を特別扱いしなくてもよくなります。
色 についてのイベントの時刻だけを考え、以下のように順方向・逆方向それぞれUnion-Findでシミュレートします。そうすると、これらのイベントで区切られた時刻区間それぞれについて色 でできた連結成分の個数を求めることができます。
これを全ての色について計算すると、答えは時刻区間に対する加算操作を大量に行った結果として求められます。これはimos法で効率的に処理することができます。
計算量について考えましょう。上記の方法だとinイベント、outイベントを全ての色について合計した個数はそれぞれ最大で となります。生じる時刻区間の個数もこれと同程度になるため、ここは問題ありません。
工夫が必要なのはUnion-Findで、全ての色について頂点数 のUnion-Findを毎回作り直していると間に合いません。各色について触る頂点の個数もイベントの個数と同程度なので、1つのUnion-Findを使い回し、1回のシミュレーションが終わったら触った頂点だけ親やサイズ等の内部状態を初期化するようにすれば、一般的なUnion-Findの実装では初期状態に戻せます。これでUnion-Find部分の計算量も大丈夫です。
ACコード
Submission #70892348 - Codeforces
実装はなかなか大変です。図を描きながらしっかり整理して、区間の両端の時刻や連結成分数などを正しく処理していきましょう。
あとは制約をパターンマッチング的に読むと を と誤読しやすいので注意です。(1敗)
Codeforces Round #618 C. Water Balance
問題概要
※0-indexedで記載します。
実数列 が与えられる。(初期状態では各要素は正整数)
この実数列に対して、「ある連続する区間を選び、その区間に含まれる要素全てをそれらの平均で置き換える」という操作を好きな回数繰り返す。
これによって得られる辞書順最小の数列を求めよ。
制約
解法
操作区間の形を限定する
操作する区間が入り組んでいるととても考えづらいので、まずここを解消します。実は以下のことが成り立ちます。
最適解を実現する操作列で、操作区間が互いに重ならないようなものが存在する。
このような性質を証明するための常套手段である、「操作区間が重なっているような操作区間は、必ず解が悪くならないような別の形に変形できる」という論法を使います。
簡単のため、2つだけ区間が重なっている状態を考えます。もし一方の区間が他方の区間を完全に包含している場合は、小さい方の操作は意味がないので消去できます。つまり重なり方として考えるべきは2通りです。
操作した区間を積み上げていくイメージで、後に操作した区間のほうを上側に書いています。ここで例えばケース1のほうを考えると、以下のように場合分けすることで、解を悪くせずに区間数を1つ減らすことができます。
- もし ならば、2回目の操作において の値が増えてしまっている。そのため2回目の操作を行わないほうが解をより良くできる。
- もし ならば、1回目の操作の右端を にして2回目の操作を消去することで、解をより良く(もしくは変わらないように)できる。
ケース2のほうも同様に考えることができます。
実際の操作列はたくさんの操作区間が入り乱れている可能性がありますが、この性質を使って1つずつ区間数を減らしながら重なりを解消していくことができます。先ほどの操作区間を積み上げた図において、上にあるものから順番に処理していくイメージです。
区間数が無限に減るということはないので、最終的には有限回の変形で必ず重なりが存在しない形にできます。これで証明できました。
貪欲解とスタック解
操作区間が重ならないことを前提とすると、最適解は以下のように前から貪欲に決めていくことができます。
- 操作区間のスタート地点を とする。
- の平均値が最も小さくなるような を求め、この区間を操作する。(便宜上、複数ある場合は最も小さい としておく)
- これで の値は確定したので、 に を代入して、同じことを繰り返す。
ですがこの操作をシミュレートしていくのは大変です。代わりに以下のようなアルゴリズムを考えます。
前から順番に要素を追加していきます。そしてこれまで追加した要素を、操作した区間(あるいは1つだけの要素)の平均値と長さを持ったブロックを順に並べたものとして記録しておきます。
新しく要素 を足す時には、まず としてブロックを末尾に足します。そして「末尾2つのブロックについて、後のブロックの値のほうが小さい」という性質を満たす限りこの2つのブロックをマージすることを繰り返します。
これは各ブロックをスタックに格納することで、全体 で実現することができます。
先に紹介した前から貪欲に確定させていく方法を「貪欲解」、後に紹介した方法を「スタック解」と呼ぶことにします(実際はどっちも貪欲だと言えなくもないですが…)。この2つの解法によって同じ解が得られることを証明します。
貪欲解における操作区間 それぞれについて、スタック解において
- が追加されたときに、より前の要素とマージされないこと
- が追加されたときに、区間 が1つのブロックになるまでマージされること
を示せば良いです。このうち については、前の要素とマージされるということはより良い解ができてしまうということなので、貪欲解の最適性からそれはないことが分かります。
スタック解において要素を追加する直前のタイミングでは、ブロックの列においてその値は単調増加になっています。 が追加された直後、あるいはそこからブロックがいくつかマージされた状態において、各ブロックの値の大小関係は以下のようになっています。
の最適性より、 を含むブロックの値よりも の平均のほうが小さくなります。そしてマージされていないブロックの値は単調増加になるので、図より を含むブロックは区間 に存在するブロックの中で最も小さい値になっているはずです。そのため必ず1つ手前のブロックとのマージが起こります。これを繰り返して、区間 が1つのブロックになるまでマージされます。
これでスタック解が最適解となることが示されました。
ACコード
Submission #70768793 - Codeforces
気づけば実装はシンプル、ですがコンテスト本番では気づくまでにかなり迷走しました…。あと、ちゃんと証明するのも大変でした。
AtCoder Regular Contest 059 E - キャンディーとN人の子供
お題箱より。
部分点解法から満点解法へのステップアップについて重点的に書きます。
解法
部分点解法
部分点解法は公式解説にもしっかり書かれているので軽く。各 について なので、ある1つの組 に対してだけ を求めてください、という問題です。
DPを考えましょう。 人目の子供までにキャンディーを合計 個配る方法を列挙し、それら全てについて「 人目の子供までの嬉しさの積」を全て足したものを とします。
この状態から 人目の子供に 個のキャンディーを配るとします。このときそれぞれの場合における「 人目の子供までの嬉しさの積」は、それぞれの「 人目の子供までの嬉しさの積」に を掛けたものになります。つまり に係数 を掛けて に遷移すれば良いです。
全ての のペアからあり得る全ての について遷移を行うため、計算量は となります。これが部分点解法です。
満点解法
満点解法において、全ての に対して1つ1つ計算をするのは無理です。上手く数式で処理できないか考えましょう。
イメージを掴むため小さい個数で考えてみましょう。 とします。また とします。つまり はそれぞれ2通りの値を動き、全部で4通りの について の和を求めることになります。
ここでキャンディーの配り方を1通りだけ考えます。子供 にそれぞれ 個のキャンディーを配ったとします。このときの嬉しさの積は と計算されます。
4通りの について、この嬉しさの積の値を合計してみましょう。
この式は分配法則の逆、いわゆる「因数分解」を用いて以下の形に変形できます。
ここが満点解法のキモです。因数分解をすることによって、子供1に関する部分と子供2に関する部分の積として分離することができました。
これは全てのキャンディーの配り方 について成り立ちます。そしてより一般的に、 がいくつで、 がいくつ離れているような場合でも同様の関係が成り立ちます。つまり子供が 人いて、それぞれの子供に配るキャンディーの数が である場合を考えると、この配り方に対応する嬉しさの積の値を全ての に対して合計したものは
と計算することができます。これは が1通りである時の嬉しさの積の値
とほぼ同じ形で、各 がそれぞれ和の形に変わっています。
ここまで整理すると、先ほどの部分点解法で用いたDPとほとんど同じことができることが分かります。つまり から に遷移するときに、部分点解法では係数 を掛けていましたが、ここが
という係数に変わります。
DPの遷移だけで 掛かってしまうので、この係数の計算は でやりたいです。ここで であり、 であることから、正整数の 乗累積和、 乗累積和、...、 乗累積和をそれぞれ 以下の範囲まで前計算しておくことで、この係数を で引いてくることができます。
ACコード
Codeforces Round #616 C. Prefix Enlightenment
コンテスト本番は闇実装に突っ込んだので、ながたかなさんの解法をベースに書き直しました…
問題概要
※解説・コードと合わせるため0-indexedで記述します。
番号 の電球が並んでいて、それぞれ初期状態でON/OFFどちらになっているのかが与えられる。また電球の部分集合が の 個与えられる。
1回の操作では部分集合を1つ選び、含まれる電球全ての状態を反転させる。
それぞれについて以下の問題を解け。
- 電球 を同時にONにするために必要な操作回数の最小値を求めよ。このとき 以降の電球の状態はどうなっていても構わない。
ここで、どの電球も3つ以上の部分集合に属することはない。また、全ての電球を同時にONにするための操作手順が必ず存在することが保証される。
制約
- あとは上記問題概要参照
解法
満たすべき条件の整理
を1つずつ増やしていきながら順番に答えを求めていくことを考えましょう。
各電球ごとに、その電球を含む部分集合の個数は 個のいずれかです。同時にONにするべき電球の集合に新しく電球 が加わったとき、どのような条件が課されるようになるか考えましょう。
- 電球 を含む部分集合が 個
- この場合は電球 に対して何も干渉できません。しかし「全ての電球を同時にONにするための操作手順が必ず存在することが保証され」ているので、この場合電球 は必ず初期状態でONになっているはずです。つまり追加条件は何もありません。
- 電球 を含む部分集合が 個
- 電球 が初期状態でONである場合、この部分集合は「操作しない」とする必要があります。逆に初期状態がOFFであれば「操作する」とする必要があります。これを条件タイプ1と呼ぶことにします。
- 電球 を含む部分集合が 個
- 電球 が初期状態でONである場合、この2つの部分集合は「操作する/しない」の選択が同じである必要があります。逆に初期状態がOFFであれば異なる選択とする必要があります。これを条件タイプ2と呼ぶことにします。
このような条件が増えていく各ステップで、 個の各部分集合について操作する/しないの選択を決め、操作するものの個数を最小化することになります。
頂点の彩色と連結成分を用いた条件の処理
個の部分集合をグラフの頂点のように考え、各頂点を赤と青の2色に塗り分けることを考えます。この色のどちらかが部分集合を「操作する」という選択に対応します。
そして2つの部分集合間にまたがる条件タイプ2が課されたとき、その頂点間に「同色でなければならない」または「異色でなければならない」という辺を張ることにします。
このグラフの連結成分は、ある1頂点の色を決めれば他の全ての色が決まる、という関係です。この関係が守られるように各頂点の色を維持しておきます。
このグラフにおいては連結成分ごとに独立に、赤と青のどちらを「操作する」に対応させるかを決めることができます。
- その連結成分の中に条件タイプ1が課されているものが含まれている場合、その条件を守るように色と操作の有無を対応させる必要がある。
- そうでない場合、どちらをどちらに対応させても良いので、その連結成分内で少ないほうの色を「操作する」に対応させるのが良い。
ここで制約から、同じ連結成分内で条件が矛盾することはないことが保証されます。各連結成分ごとに求めた「操作する」頂点の個数の合計が答えになります。
実装方針(つらい方法)
では徐々に条件が増えていく中で、連結成分の管理・条件タイプ2に矛盾しない色の塗り分け・条件タイプ1の存在状況を維持し、各ステップにおける答えを求められるような処理を実現しましょう。
連結成分の管理はUnion-Findを用いれば良いです。色の塗り分けについては、条件が何もない最初の状態では全ての頂点を「赤に塗る」と決めてしまいます。辺が追加されたときに、両端の頂点の色関係がその辺の要求に合っていればそのまま繋げますが、そうでない場合は併合される2つの連結成分のうち片方の色をまるっと反転させなければいけません。
このような場合に適当に反転させるとトータルで 回の反転が必要になります。しかし必ずサイズの小さいほうの集合を反転させることで、「データ構造をマージする一般的なテク」により反転回数の合計が全体で に抑えられます。
また条件タイプ1についても、Union-Findの中に情報として持たせておきます。根の色を基準にして、「根の色が"操作する"と対応する必要がある」「根の色が"操作しない"と対応する必要がある」「条件タイプ1が存在しない」のいずれかであるかを各連結成分に持たせておきます。連結成分同士を併合するときにここも上手くマージします。
あとは各連結成分について赤頂点の数/青頂点の数も管理しておけば、各連結成分から答えに足すべき値が求められるようになるので、条件が増えるごとに影響を受ける連結成分の答えを差分管理することで各ステップにおける答えを求めることができます。
ACコード(つらかった)
Submission #70072102 - Codeforces
実装方針(よい方法)
途中で頂点の色を反転するとか、根の色に合わせて条件タイプ1の状態をごちゃごちゃ反転させるとか、つらいですね。よい実装も紹介します。
まず最初に、全ての条件(タイプ1・タイプ2)が追加されてしまった状態を考えます。このグラフにおいて、条件タイプ2に矛盾しないように各頂点の彩色を決めてしまいます。こうすれば途中で頂点の色を変える必要がなくなります。
また条件タイプ1については、仮想的に頂点を1つ増やすことで扱いが楽になります。この頂点を とすると、頂点 は常に赤色で、頂点 の赤は必ず「操作しない」に割り当てることにすると決めてしまいます。こうすると条件タイプ1は頂点 と繋ぐ辺として、条件タイプ2と同様に扱うことができます。
このように実装すると、条件を増やしていく中で管理すべき項目は連結状態と各連結成分に含まれる赤の頂点数/青の頂点数だけになります。各連結成分から答えに足すべき値を求める際にも、頂点 が含まれているかどうかで場合分けをすればシンプルに計算できます。