ARMERIA

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

CODE FESTIVAL 2018 qual B　参加記録＆解説（A～D）

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

CODE FESTIVAL 2018 qual B - AtCoder

前のこどふぉに出ていたので5分遅刻で参加。結果は108位でした…

f:id:betrue12:20181015020705p:plain

A～Dを振り返ります。今回は公式解説がかなり丁寧なので、それを少し補足するような感じで短めに書きます。

A - Probability of Participation

A - Probability of Participation

解法

1以上100以下の整数のうち、 N で割り切れるものは \lfloor\frac{100}{N}\rfloor 個です。これを100から引いたものが答えです。

ACコード

（Ruby）Submission #3406469 - CODE FESTIVAL 2018 qual B

B - Tensai

B - Tensai

解法

顔が一番面白い人に毎回トレーニングをしてもらうのが最適です。実装方法はいくつかありますが

  • 字の上手さと顔の面白さのペアを顔の面白さ基準でソートし、一番顔が面白い人の字の上手さを X 増加させ、スコアを計算する
  • 与えられた入力のまま普通にスコアを計算したあと、 (顔の面白さの最大値) \times X を加算する

などをすればよいです。

ACコード

（Ruby）Submission #3406640 - CODE FESTIVAL 2018 qual B

C - Special Cake for CODE FESTIVAL

C - Special Cake for CODE FESTIVAL

解法

答えは公式解説に書いてあるとおりです。ので、ちょっと思考の流れを書きます。

制約を確認すると、マスの数は最大100万になり、 X を置いてもよいマスの数はその5分の1＋ちょっとです。そのため、ある程度答えが規則的になるだろうという予想から、「ある行について、5マスごとに1個 X を置いてみる」ということを考えます。

5マスごとに X を置くと、間には X のないマスが4つあります。これら全てをカバーしなければいけません。

f:id:betrue12:20181015201339j:plain

一番左と一番右は、その行の中で X に接しているため、既にカバーできています。残り2つは上と下に助けてもらいたいので、それぞれ上と下に置きます。このような形を作れれば、X の間の4マスが全てカバーできます。

この形を繰り返していくと、公式解説のような模様ができます。

ACコード

（Ruby）Submission #3407445 - CODE FESTIVAL 2018 qual B

D - Sushi Restaurant

解法

この記事はD問題まで書きますが、もちろんこれが4問の中ではダントツに重いです。ただこの問題も公式解説が丁寧です。そちらで丁寧に説明されていることはこの記事では端折っていきます。

「 i 番目に空腹度が小さい人」に着目する

参加者の空腹度が確率で決まったあと、与えられた寿司がどのように割り振られるか考えます。このとき、1番空腹度が小さい人は1番寿司が少ない皿を、2番目に空腹度が小さい人は2番目に寿司が少ない皿を…というふうに寿司が割り振られます。

このため、「 i 番目に寿司が少ない皿（つまり、 i 番目に空腹度が小さい人が取る皿）は、寿司をいくつにするのが最適か？」ということを、各皿ごとに独立に考えることができます。ということで、「 i 番目に空腹度が小さい人」の空腹度がどのような分布になっているかを知りたくなります。

もしこの確率分布が求められている場合、最適な寿司の数はいくつになるでしょうか。ここで、「絶対値で定義された誤差の合計を最小にするのは、分布の中央値である」という知識が使えます。これは少し前のABC/ARCでも登場した知識です。以前の問題のように確率の概念がない場合は小さい方から数えて \frac{N}{2} 個目の要素を採用していましたが、今回のようにそれぞれの要素に確率が付いている場合も似たように考えることができて、「確率の累積値が \frac{1}{2} であるところの要素」が中央値となります。

f:id:betrue12:20181015210335p:plain

この値は空腹度の候補 x_{j} のうちどれかになっているので、もちろん整数です。そのまま寿司の個数として採用することができます。

確率分布を求める

今までの話で、「 i 番目に空腹度が小さい人」の空腹度の分布が求められれば答えが求められる、ということが分かりました。次はこの確率分布を求めます。

i 番目に空腹度が小さい人の空腹度が、 j 番目に小さい候補である x_{j} となる確率を考えてみます。なんとなく「この人より空腹度が小さい人が i-1 人、空腹度が大きい人が N-i 人いて…」みたいなことを考えたくなりますが、こうすると空腹度 x_{j} の人が複数人いたときに困ります。

もう一つ「空腹度 x_{j} の人が全部で k 人いるときの…」という条件を付け足し、 k を全探索すれば確率が求められないことはないです。ただこうすると、 i, j, k のループで O(N^{2}M) の計算が必要で間に合いません。

このようなときに使える手段が、「 i 番目に空腹度が小さい人の空腹度が x_{j} 以上となる確率」を考えることです。これが求められれば、順次差分を取ることで目的の確率分布が求められます。

そしてこの値は、「ぴったり」を求めるよりも求めやすいです。具体的には、 x_{j} より小さい空腹度を持つ人の人数が 0, ..., i-1 人のどれかである確率を求めることになります。これも結局全探索のオーダーが1つ増えそうに見えますが…

  • i 番目に空腹度が小さい人の空腹度が x_{j} 以上となる： x_{j} より小さい空腹度を持つ人の人数が 0, ..., i-1 人のどれかである
  • i+1 番目に空腹度が小さい人の空腹度が x_{j} 以上となる： x_{j} より小さい空腹度を持つ人の人数が 0, ..., i 人のどれかである

こうして並べてみると、「 i 番目」のときの結果に要素を1つ足すだけで「 i+1 番目」の結果になり、差分更新で求めることができるのです。

あとは要素1つが現実的な時間で求められればよいです。「 x_{j} より小さい空腹度を持つ人の人数が i 人である」という確率は、 x_{j} より小さい空腹度になる確率を p として

_{N}C_{i} {p}^{i} (1-p)^{N-i}

と求められます。コンビネーションは前計算、 p も各 x_{j} が出る確率 \frac{p_{j}}{q} の累積和なので前計算。累乗の部分は繰り返し二乗法で O(\log N) に落ちるので、十分現実的な時間で求められます。

解法まとめ

ということで、まとめです。

  1. \frac{p_{j}}{q} の累積和およびコンビネーションを前計算しておく。
  2. 前計算の値と差分更新のテクニックを利用して、「 i 番目に空腹度が小さい人の空腹度が x_{j} 以上となる確率」を求める。ここから差分を取ることで、「以上」を外したものを求める。
  3. この確率分布の中央値を求めて、各皿ごとに最適な寿司の数を決め、答えを計算する。

ACコード

Submission #3410686 - CODE FESTIVAL 2018 qual B

誤差がかなり積もってしまうので、double よりも精度の高い long double を用いました。精度が良い分、計算時間とメモリの占有量は大きくなるのですが、この問題の場合はどちらも余裕があるので大丈夫でした。

公式解説では対数に変換して計算する方法が紹介されています。対数にすると累乗が掛け算になるので、それで O(\log N) が計算量に付いていないのだと思います…たぶん。

さいごに

D, Eは全体的にAC者がものすごく少なかったですね。私も通せませんでしたが、Dはしっかり復習できたと思います。Eも理解しなければ…

AGC028 参加記録＆解説（A～C）

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

AtCoder Grand Contest 028 - AtCoder

今回も前回と同じく、速解き1完でレート微減。うーん…

f:id:betrue12:20181014005902p:plain

しっかり復習しましょう。A～Cを振り返ります。

A - Two Abbreviations

A - Two Abbreviations

解法

※以降の説明では、文字列のインデックスを0始まりで記載します。

まず X の長さ L は N, M の両方で割り切れるという条件があるため、 L は N, M の公倍数です。公倍数は最小公倍数の倍数であるため、 L は lcm(N, M) の正整数倍です。

とりあえず、 L = lcm(N, M) として考えます。 X の中で、 文字列 S, T がどこに含まれているかを図示します。

f:id:betrue12:20181014011332p:plain

図のように、 S が1文字進むごとに X は \frac{L}{N} 文字、 T が1文字進むごとに X は \frac{L}{M} 文字進みます。

X の各文字のうち、 S, T のどちらか一方に対応している位置はその文字を採用すればよいですし、どちらとも対応していない位置の文字は好きに決めればよいです。問題は両方に対応している位置で、 これらは同じ文字である必要があります。

このように S, T の両方の文字が存在する位置は、 \frac{L}{N} と \frac{L}{M} の公倍数（と0）になります。先ほども書いたように公倍数は最小公倍数の倍数であるため、 lcm(\frac{L}{N}, \frac{L}{M}) の0以上の整数倍の位置すべてについて、そこに対応する S, T の文字が一致しているかどうかを調べればよいです。

これで、 L = lcm(N, M) のときの判定ができました。では他の公倍数の場合はどうか？と考えてみますが、他の公倍数は lcm(N, M) の正整数倍です。 L = k \times lcm(N, M) とすると、 X, S, T の対応図は上の図をそっくりそのまま k 倍に「引き伸ばした」ような感じになります。つまりどの公倍数で考えても、比較しなければいけない S と T の文字は同じであり、 S, T に矛盾なく X を構成できるかどうかも同じになります。

そのため上記のように L = lcm(N, M) で調べて、OKであればその値が最小値ですし、NGであればどの公倍数でも X は構成不可能なので-1を出力します。

ACコード

C++のほうが、上の説明に沿って書いています。

B - Removing Blocks

B - Removing Blocks

解法

各ブロックについて、「 N! 個の全てのパターンについて合計したときに、ブロック i の重さは合計何回分カウントされるか？」を求めたいです。これを係数として A_{i} に掛けて総和を取ると答えになります。

これをさらに分解し、「ブロック j を取り除くときに、ブロック i の重さは合計何回分カウントされるか？」を考えます。各パターンごとに各ブロックはそれぞれ1回ずつしか取り除かれないため、これは「 N! 個の全てのパターンのうち、ブロック j を取り除くときにブロック i の重さがカウントされるパターンはいくつあるか？」と書き換えられます。

ブロック j を取り除くときにブロック i の重さがカウントされる条件は、取り除く時点で j から i までのブロックが全て存在すること。言い換えると、 j から i までの |j-i|+1 個のブロックのうち、ブロック j が最初に取り除かれることです。このようなパターンの数は \frac{N!}{|j-i| + 1} になります。これは、ブロックを取り除く順番をランダムな事象として考えたときに、 |j-i|+1 個のブロックのうちブロック j が最初に取り除かれる確率が \frac{1}{|j-i|+1} である、と考えたほうが理解しやすいかもしれません。

ここまでの内容を整理すると、

  • 「ブロック j を取り除くときに、ブロック i の重さは合計何回分カウントされるか」は、 \frac{N!}{|j-i| + 1}。
  • 「 N! 個の全てのパターンを合計したときに、ブロック i の重さは合計何回分カウントされるか？」は、↑を全ての j について合計した \sum_{j=1}^{N}\frac{N!}{|j-i| + 1}。
  • 答えは、それを係数として A_{i} に掛けて合計したもの。

です。

では、 \sum_{j=1}^{N}\frac{N!}{|j-i| + 1} を求めましょう。 N! は全ての項に共通なので、 \sum_{j=1}^{N}\frac{1}{|j-i| + 1} を求めて一番最後に N! を掛けることにします。これは i の両側それぞれで見ると、 \frac{1}{1} + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \cdots という形になっています。この累積和を事前計算しておけば、各 i についてこの値が高速に求められます。

ただしこれは整数での割り算なので、素数modでの逆元計算を行い、その逆元を足し算していきます。逆元の計算についてはこちらの記事によくまとまっています。信頼と実績のけんちょんさん。

「1000000007 で割ったあまり」の求め方を総特集！ 〜 逆元から離散対数まで 〜

これで材料が揃いました。解法をまとめます。

  1. 素数modでの逆元計算を用いて、 \frac{1}{1} + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \cdots の累積和を計算しておく。
  2. 各 i について、累積和を使って \sum_{j=1}^{N}\frac{1}{|j-i| + 1} を計算する。
  3. 上記結果を係数として A_{i} に掛け、加算する。
  4. 最後に後回しにしておいた N! を掛ける。

ACコード

C - Min Cost Cycle

C - Min Cost Cycle

解法

ある頂点の A_{i} と別の頂点の B_{j} がペアになり、 N 本の辺を構成します。このとき、重みの小さいものをなるべくばらけさせたいです。特に、 A_{i}, B_{j} を合計 2N 個をごちゃ混ぜにソートして、小さいほうから N 個を N 本の辺にばらけさせることができれば、これが最適です。

ただし問題では「全ての頂点を1度ずつ通るサイクルを構成すること」が要求されています。 A_{i}, B_{j} から重みとして使いたい値を N 個選んだとき、それを N 本の辺にばらけさせて、要求されているサイクルが構成できるでしょうか。

f:id:betrue12:20181014113938p:plain

サイクルを構成できる条件は、上図のようなものになります。一番左のOKパターンは実際に作ってみればいいので分かりやすく、一番右のNGパターンも図のように閉路を作ろうとすると必ず繋ぎ相手がいなくなるので分かりやすいです。真ん中のパターンが必ずOKというのはちょっと難しいのですが、「Aを使うもの」と「Bを使うもの」をそれぞれ固めて、その間を「AもBも使うもの」と「AもBも使わないもの」で上手く繋ぐようにするとサイクルを構成できます。（図では要素数が少ないですが、一応そのように構成しています。）

これでやることが決まりました。OKパターンを満たすように、その中で A_{i}, B_{j} の合計がなるべく小さくなるように N 個を選びます。

ということで、まず小さい方から N 個選んでしまいましょう。この N 個がOKかNGかを確認します。

  • OKパターンだった場合
    • 何の問題もありません。そのまま出力します。
  • NGパターンだった場合
    • この場合、取る値を変更しないといけません。2番目に合計が小さくなるのは、 1, 2, ..., N-1, N+1 番目を選んだ場合です。これがOKパターンならこれが答えです。ただこれも、NGパターンになることがあります。

最後の詰めです。 1, 2, ..., N-1, N 番目も 1, 2, ..., N-1, N+1 番目もNGパターンになるというのはどういう状態でしょうか。

f:id:betrue12:20181014113206p:plain

1, 2. ..., N-1 番目を選んだ状態から、 N 番目を選んでも N+1 番目を選んでもNGになる場合、 これらの2つの値は同じ頂点に属しています。これがとても重要です。

次の候補を考えます。 1, 2, ..., N-1, N+1 番目がNGとなると、次に重み合計が小さくなるのは

  • 1, 2, ..., N-1, N+2 番目
  • 1, 2, ..., N-2, N, N+1 番目

のどちらかになります。このときこれら2つはどちらも、「 N 番目と N+1 番目は同じ頂点に属している」ということを使ってOKパターンになることが示せます。

  • 1, 2, ..., N-1, N+2 番目を選ぶと、同じ頂点に属する N, N+1 番目がどちらも選ばれていない。そのため他の頂点どれか1つ以上で、 A_{i}, B_{i} 両方が選ばれているはずである。
  • 1, 2, ..., N-2, N, N+1 番目を選ぶと、同じ頂点に属する N, N+1 番目がどちらも選ばれている。

つまり、2つをそれぞれ計算して小さい方を出力すればよいです。

解法をまとめます。

  1. 各重みをソートし、小さい方から N 個選び、OKパターンかどうか判定する。OKパターンなら合計値を出力して終了。
  2. ↑がNGパターンの場合、 1, 2, ..., N-1, N+1 番目を選び、OKパターンかどうか判定する。OKパターンなら合計値を出力して終了。
  3. ↑もNGパターンの場合、以下の2つはともにOKパターンなので、2つのうち合計値が小さいほうを出力して終了。
    • 1, 2, ..., N-1, N+2 番目
    • 1, 2, ..., N-2, N, N+1 番目

ACコード

（C++）Submission #3402799 - AtCoder Grand Contest 028

さいごに

本番では、

  • Aは少し難しいなと思いながらもWAなしで突破。
  • Bは完全に方針を見誤る。愚直 O(N^{3}) 、累積和使って O(N^{2}) で回せそうな漸化式を見つけてしまい、そこに固執していました…。
  • Cは大筋の方針は良かったが、 1, 2, ..., N-1, N+1 番目を選んでもNGとなるケースに気付かなくて詰められず。

という感じでした…。

最近2回ともAGCが解けなくて少しへこみますが、しっかり復習して、問題を解き続けるしかないですね。

Codeforces Round #515 参加記録＆解説（A～E）

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

Dashboard - Codeforces Round #515 (Div. 3) - Codeforces

結果は5完で、Virtualの参加者を除くと121位。悪くはないですが、上を目指すなら全完したいところですね…

f:id:betrue12:20181013142347p:plain

5問振り返ります。

A. Vova and Train

Problem - A - Codeforces

問題概要

以下の問題 t 個に答えよ。

  • 1から L までの整数のうち、 v の倍数であり、区間 \lbrack l, r \rbrack に含まれないものの数を求めよ。

制約

  • 1 \le t \le 10^{4}
  • 1 \le L, v \le 10^{9}
  • 1 \le l \le r \le L

解法

1から L までの整数のうち v の倍数は \lfloor\frac{L}{v}\rfloor 個あります。

区間 \lbrack l, r \rbrack に含まれる v の倍数のうち、（存在する場合）最小のものは \lceil\frac{l}{v}\rceil v 、最大のものは \lfloor\frac{r}{v}\rfloor v です。その間に含まれる v の倍数の個数は \lfloor\frac{r}{v}\rfloor - \lceil\frac{l}{v}\rceil + 1 です。これを総数から引けばよいです。

※区間 \lbrack l, r \rbrack に v の倍数が1つもない場合がありますが、そのときは \lfloor\frac{r}{v}\rfloor - \lceil\frac{l}{v}\rceil + 1 = 0 になるので、同じ計算で答えが求められます。

ACコード

（C++）Submission #44190437 - Codeforces

B. Heaters

Problem - B - Codeforces

問題概要

長さ n のマスのうち、いくつかのマスにヒーターがある。マス i のヒーターが動作している場合、区間 \lbrack i-r+1, i+r-1 \rbrack のマスが暖かくなる。

できるだけ少ない数のヒーターを動作させて、全てのマスを暖かくしたい。そのようなヒーターの数を求めるか、全てのマスを暖かくすることが不可能であることを判定せよ。

制約

  • 1 \le n, r \le 1000
  • a_{i} は0または1。1のときマス i にヒーターが置かれている。

解法

左から右にマスが 1, ..., n と並んでいるとします。

「マス i が暖かくなっているかどうか」を管理しながら、左から順番にマスを見ていきます。暖かくないマスを見つけた場合、そのマスを暖かくできるヒーターの中で最も右にあるものを動作させるのが最適です。これを一番右まで行えばよいです。

計算量は O(nr) で十分間に合います。

ACコード

（C++）Submission #44234507 - Codeforces

本番はDPで解きました。「マス i までが全て暖かくなっているために必要なヒーターの最小数」を dp\lbrack i \rbrack としています。これでも解けます。

C. Books Queries

Problem - C - Codeforces

問題概要

横に十分な長さを持つ本棚に、以下のクエリに従って本を置いていく。合計 q 個のクエリを処理せよ。

  1. L id : 一番左にある本の左に番号 id の本を置く。
  2. R id : 一番右にある本の右に番号 id の本を置く。
  3. ? id : 既に置かれてある番号 id の本について、「その本の左にいくつ本があるか」と「その本の右にいくつ本があるか」のうち小さいほうを出力する。

制約

  • 1 \le q \le 2\times 10^{5}
  • 1 \le id \le 2\times 10^{5}
  • 既に置かれた本と同じ番号の本は置かれない。
  • ? id クエリでは既に置かれた本の番号が指定される。

解法

座標を考えると見通しが良くなります。一番最初に置かれる本を座標0として、最左の本の座標と最右の本の座標を管理しておきます。そうすると、本を追加したときにその本の座標が分かるので、それを番号 id をインデックスとする配列などで記録します。

? id クエリに答える際には、 番号 id の本の座標、最左の本の座標、最右の本の座標が分かっていれば、左右それぞれにある本の数を求められます。

ACコード

（C++）Submission #44235751 - Codeforces

本番コードはこちら。上のほうがスマートです。

D. Boxes Packing

Problem - D - Codeforces

問題概要

サイズが a_{1}, ..., a_{n} である n 個の物品と、容量 k の箱 m 個がある。

物品を、以下の手順で箱に詰める。

  • 空箱を持つ。物品を前から見ていって、その空箱に詰められるだけ詰める。詰められなくなったら、新しい空箱に切り替えて物品を詰める。（物品は必ず前から順に詰める。詰められない物品をスキップしたり、後回しにすることはできない。）

もしこの手順で全ての物品を詰められない場合は、番号の最も若い物品を捨て、最初からやり直す。

捨てたもの以外の物品を m 個の箱に全て詰められたとき、そのときの物品の数を求めよ。

制約

  • 1 \le n, m \le 2\times 10^{5}
  • 1 \le k \le 10^{9}
  • 1 \le a_{i} \le k

解法

問題文の読解が最難関です。

「物品 i, (i+1), ..., n を前から処理したとき、 m 個以下の箱に全て詰められる」という条件を満たす最小の i を求めれば良いです。単調性があるので、二分探索をすることができます。

二分探索のYes/No問題においては、素直に固定した開始地点から物品を詰めてみて m 個以内に収まるかチェックすればよいです。1回のYes/No問題が O(n) で解けるので全体計算量は O(n \log n) です。

ACコード

（C++）Submission #44204869 - Codeforces

E. Binary Numbers AND Sum

Problem - E - Codeforces

問題概要

2進数で整数 a, b が与えられ、それぞれのビット長は n, m である。

以下の操作を行ったときの答えの値を求め、998244353で割った余りを出力せよ。

  1. a, b のビットAND a&b の値を答えに加算する。
  2. b を右に1ビットシフトする。
  3. b=0 なら終了、そうでなければ1に戻る。

制約

  • 1 \le n, m \le 2 \times 10^{5}
  • a, b はそれぞれビット長 n, m の2進数であり、最左ビットは1

解法

a の中で1となっているビットに注目します。このビットが（一番右を0桁目として） k 桁目だとすると、このビットが1回加算されるごとに答えは 2^{k} 増加します。

ではこのビットが何回答えに加算されるかというと、それは b の中で k 桁目以上に存在する1の個数に対応します。この個数は b のビットについて累積和を取っておけば、累積和同士の差を取ることで求められます。

f:id:betrue12:20181013144544p:plain

これを a の立っているビット全てについて計算します。 b の最大桁より大きい桁は a についても見なくて良いので、計算量は O(m) となります。

ACコード

Codeforces

さいごに

Fを復習します…Div3は全完を目指したい。

Educational Codeforces Round 52 参加記録＆解説（A～F）

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

Dashboard - Educational Codeforces Round 52 (Rated for Div. 2) - Codeforces

結果は4完で194位。DがHackで落ちました…

f:id:betrue12:20181012201409p:plain

A～Fの6問を振り返ります。

A. Vasya and Chocolate

Problem - A - Codeforces

問題概要

以下の問題 t 個に答えよ。

  • 所持金 s ルーブルで、1つ c ルーブルのチョコを買えるだけ買う。また、チョコを a 個買うごとに追加で b 個のチョコがもらえる。入手できるチョコの総数を求めよ。

制約

  • 1 \le t \le 100
  • 1 \le s, a, b, c \le 10^{9}

解法

買えるチョコは n_{1} = \lfloor\frac{s}{c}\rfloor 個です。これを a 個1組とすると \lfloor\frac{n_{1}}{a}\rfloor 組買っているので、追加でもらえるチョコは n_{2} = \lfloor\frac{n_{1}}{a}\rfloor \times b 個です。 n_{1} + n_{2} が答えです。

ACコード

（C++）Submission #44119682 - Codeforces

B. Vasya and Isolated Vertices

Problem - B - Codeforces

問題概要

n 頂点 m 辺の単純な無向グラフの中で、孤立点が最も少ないグラフと、最も多いグラフを考える。それぞれの孤立点の数を求めよ。

制約

  • 1 \le n \le 10^{5}
  • 0 \le m \le \frac{n(n-1)}{2}

解法

孤立点を最も少なくするには、孤立点同士を辺で結んでいくのがよいです。1本の辺につき孤立点が2個減るので、孤立点の最小数は \max(0, n-2m) となります。

孤立点を多くするには、なるべく少ない頂点だけで全部の辺を持ちたくなります。そのため、完全グラフを作るように辺を張っていくとよいです。 k 頂点の完全無向グラフの辺数は \frac{k(k-1)}{2} 本なので、 m \le \frac{k(k-1)}{2} であれば k 頂点で m 本の辺を持てます。この不等式を満たす最小の k を求めて、孤立点の最大数は N-k となります。

ACコード

Submission #44123483 - Codeforces

C. Make It Equal

Problem - C - Codeforces

問題概要

ブロックが積まれてできた n 本の塔があり、それぞれの高さはブロック h_{i} 個である。

以下の操作を、全ての塔の高さが等しくなるまで繰り返す。操作回数の最小値を求めよ。

  • ある高さを決める。このとき、その高さ以上にあるブロックの個数が k 個以下でなければならない。その高さ以上のブロックを全て取り除く。

制約

  • 1 \le n \le 2\times 10^{5}
  • n \le k \le 10^{9}
  • 1 \le h_{i} \le 2 \times 10^{5}

解法

毎回の操作で、 k 個を超えないギリギリまでブロックを取り除くのがもちろん最適です。そのため、上から数えたブロック数が k 個を超えない最小の高さを求めたくなります。

「今の操作で除去できる残りブロック数」を管理しておいて、今の操作でどこまで除去できるか1段ずつ調べます。このとき「今の時点で一番高さが高い塔の本数」を管理しておくと、1段下げたときいくつのブロックが除去されるかが分かります。

残りブロック数が足りなくなった時点で、次の操作に移ります。これを一番低い塔の高さに到達するまで繰り返します。

h_{i} の上限が少ないので、これで十分間に合います。

ACコード

（C++）Submission #44183329 - Codeforces

本番ではもう少しまとめて計算するようなコードを書いていて、こっちだと h_{i} が大きくても対応できるのですが、そのぶん実装が少しだけ複雑です。

D. Three Pieces

Problem - D - Codeforces

問題概要

N \times N のチェス盤の各マスに、 1, 2, ..., N^{2} の数字が1つずつ記載されている。このチェス盤上で、以下の操作を行う。

  1. 1のマスに、ルーク・ビショップ・ナイトのうち好きな種類の駒を置く。
  2. 以下の操作を好きな順番で繰り返し、 1, 2, ..., N^{2} の順にマスを訪れる。途中で他のマスを経由しても良い。
    • チェスのルールにおける駒の動き方に則って駒を1手分動かす。
    • 駒をルーク・ビショップ・ナイトのいずれかに交換する。

N^{2} が書かれたマスに到達するまでの操作の合計回数を a 、そのうち駒の種類を交換した回数を b として、 (a, b) を辞書順最小にしたい。そのような a, b を求めよ。

制約

  • 3 \le N \le 10
  • マス (i, j) に書かれた数を A_{ij} として、 1 \le A_{ij} \le N^{2} でありこれらは互いに異なる

解法

駒の交換と移動があり、遷移が複雑です。グラフに帰着して、最短路問題などのアルゴリズムを使って上手く処理したいです。

状態として「位置」と「駒の種類」の組み合わせを考え、それぞれが1頂点となるようなグラフを考えます。頂点の数は V = 3N^{2} \le 300 です。駒の移動も交換も、この頂点間の遷移として考えることができます。

頂点間の距離は、求める答えと同じように (操作回数, そのうちの駒交換回数) のペアで定義し、辞書順比較します。駒の移動と交換に対応する遷移を辺として追加し、ワーシャルフロイド法を用いると、ある状態からある状態までの最短距離を計算することができます。 V \le 300 なので O(V^{3}) のワーシャルフロイドが間に合うのがポイントです。

これを用いて答えを求めましょう。 1, 2, ..., N^{2} を順に通る最短路を求めるにあたり、 「頂点 1, ..., i までの巡回が完了し、今の駒が j であるときの、最初の状態からの最短距離」を dp\lbrack i \rbrack \lbrack j \rbrack としてDPができます。 dp\lbrack i+1 \rbrack \lbrack j \rbrack を求めるときには、 dp\lbrack i \rbrack \lbrack 0 \rbrack, dp\lbrack i \rbrack \lbrack 1 \rbrack, dp\lbrack i \rbrack \lbrack 2 \rbrack すべてからの遷移を試して最も小さいものを採用します。これを i=N^{2} まで回せば答えが求められます。

ACコード

（C++）Submission #44180256 - Codeforces

E. Side Transmutations

Problem - E - Codeforces

問題概要

|A| 種類の文字があり、その一部または全部で構成される n 文字の文字列を考える。

整数 b_{1}, ..., b_{m} が与えられる。文字列 S と T は、 S に以下の操作を0回以上行って T と一致させることができる時、「等しい」と呼ぶ。

  • b_{i} を1つ選ぶ。操作対象の文字列の前 b_{i} 文字と後ろ b_{i} 文字を、それぞれ反転して交換する。

「等しい」文字列は区別せず1種類と数えることにしたとき、 n 文字の文字列の種類数を数え上げて、 998244353 で割った余りを出力せよ。

制約

  • 2 \le n \le 10^{9}
  • 1 \le m \le \min(\frac{n}{2}, 2\times 10^{5})
  • 1 \le |A| \le 10^{9}

解法

問題文の操作を繰り返すことで、何が起こるでしょうか。例えば、2つの異なる箇所で操作を行うと、以下のように文字列が変化します。

f:id:betrue12:20181012224005p:plain

b_{i} の位置を区切りとして、左右それぞれ対応するペアを考えます。操作を繰り返すことで、任意のペアを入れ替えることができます。つまりこのペアをいくつか入れ替えることで一致するような文字列が、今回の問題でいう「等しい」文字列です。

ペアの入れ替えを独立に考えられるので、場合の数も独立に考えて掛け算することができます。 b_{1} - b_{0} 文字のペア、 b_{2} - b_{1} 文字のペア…というように、それぞれのペアについて独立に「反転で一致するものを同一視したときに文字列が何通りあるか」を数えて、これを掛け算すればよいです。（ b_{0} = 0 としておくと便利です）

ただし真ん中の部分の文字列は反転できないので、単純に「文字列が何通りあるか」を数えて掛け算します。それらを全て掛け合わせたものが答えです。

各ペアについての場合の数を考えます。 d_{i} = b_{i+1} - b_{i} と置くと、求めたいものは「長さ 2d_{i} の文字列を、反転すると一致するものは同一視して数えたときの場合の数」です。「反転すると一致する」文字列は、文字列が回文でない場合は1対1で相手が存在し、回文である場合は反転しても自分自身になるので相手が存在しません。

そのため反転を同一視しない全ての文字列の数を n_{all} 、回文になっている文字列の数を n_{pal} とすると、回文になっていない文字列が同一視で半減することから、求めたい数は \frac{n_{all} - n_{pal}}{2} + n_{pal} となります。具体的に計算すると n_{all} = |A|^{2d_{i}} 、 n_{pal} = |A|^{d_{i}} であるため、これらを全て計算していけばよいです。

ACコード

（C++）Submission #44153485 - Codeforces

F. Up and Down the Tree

Problem - F - Codeforces

問題概要

根を頂点1とする n 頂点の根付き木と、整数 k が与えられる。頂点1にトークンを置いた状態から、以下の操作を0回以上繰り返す。

  • いまトークンが置かれている頂点を v として、
    • v が葉でない場合、 v 以下の部分木に含まれる葉のうちいずれかにトークンを移す。
    • v が葉である場合、 v から最大 k 回親を辿った先の頂点にトークンを移す。

頂点1にトークンを置いた状態からスタートし、なるべく多くの葉を訪れたい。その最大数を求めよ。

※接続されている辺の数が1本である頂点を葉と呼ぶが、今回は根である頂点1は葉ではないとして扱う。

解法

ある頂点から葉に降りたときに、元の頂点に戻って来れる場合と来れない場合があります。イメージとしては、葉が深いところにあり、途中で経由できるような葉もないときは戻ってこれません。

そのため、ある頂点以下の部分木でなるべく多くの葉を訪れようとすると、以下のような戦略になります。

  1. 全ての子に対して、まずは降りた後に自分自身に戻って来れる範囲で葉を回収する。
  2. 最後に1つだけ子を選んで降り、戻って来れない範囲の葉も回収し、操作を終える。

これは再帰的に処理していくことができます。つまりそれぞれの頂点に対して、

  • dp_{1}\lbrack i \rbrack = 頂点 i 以下の部分木で、 i から始めて自分自身に戻って来ることが必要な場合、いくつ葉を回収できるか
  • dp_{2}\lbrack i \rbrack = 頂点 i 以下の部分木で、 i から始めて自分自身に戻って来なくてもよい場合、いくつ葉を回収できるか

を葉のほうから決めていくような木DPができます。 dp_{2}\lbrack 1 \rbrack が答えです。

このDPの遷移を考えます。ある頂点 i に着目し、その子 j を順に見ていきます。

  • 子 j から i に（ j 以下のいずれかの葉を経由して）移動できる場合は、 i から j 側に降りて dp_{1}\lbrack j \rbrack 個の葉を回収し、また i に戻ってくることができます。もし最後に子 j 側に降りるのであれば、追加で dp_{2}\lbrack j \rbrack - dp_{1}\lbrack j \rbrack 個の葉を回収することができます。
  • 子 j から i に移動できない場合は、葉を回収して戻ってくることができません。ただし、最後に子 j 側に降りるのであれば dp_{2}\lbrack j \rbrack 個の葉を回収することができます。

このようにそれぞれの子からの情報を得て、「戻ってこれる範囲で回収できる葉の数」の合計を dp_{1} \lbrack i \rbrack とし、「最後に子 j に降りるのであれば追加で回収できる葉の数」の最大値を dp_{1} \lbrack i \rbrack に足したものを dp_{2} \lbrack i \rbrack とします。

ここで「子 j から親 i に移動できるか」は、 j から見て一番浅い位置にある葉の深さで決まります。そのような葉 l から i までの距離が k 以下であれば、 j \to l \to i という遷移ができます。

ACコード

（C++）Submission #44148563 - Codeforces

さいごに

Dが落ちたのは完全に不注意。実装がキツい問題だと思っていたけど、ちゃんと整理して書くと意外とスッキリ書けました。

Eは本番最後に方針が見えたので惜しかったです…。Fが解けそうだったので先にそっちに行きました。木DP好き。

CF495 F. Sonya and Bitwise OR

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

コンテスト参加記録だけじゃなくて、過去問を解いた時も時々記事を書いていこうかなと思います。

自分用なので、解説というよりは考察・学習メモ。いつもよりは雑になります。

問題情報

リンク

Problem - F - Codeforces

問題概要

長さ n の数列 a_{1}, ..., a_{n} と整数 x が与えられる。以下のクエリ合計 m 個を処理せよ。

  1. 1 i y : i 番目の要素 a_{i} の値を y に変更する。
  2. 2 l r : 区間 \lbrack l, r \rbrack に含まれる部分区間 \lbrack L, R \rbrack であって、その区間に含まれる要素 a_{L}, ..., a_{R} のビットORを取ったものが x 以上になるものの個数を出力する。

制約

  • 1 \le n, m \le 10^{5}
  • 0 \le x, a_{i} \lt 2^{20}
  • クエリ1について、 1 \le i \le n 、 0 \le y \lt 2^{20}
  • クエリ2について、 1 \le l \le r \le n

考察

クエリ2を区間和問題に帰着

まず考えたこと。

  • 区間に関する大量のクエリ。セグ木っぽい。
  • ORは要素を足していくと単調増加するので、1クエリに O(n) 使っても良いならしゃくとりできる。でも今回はクエリが多いので間に合わない。
  • 1クエリにかけていい時間が O(1) か O(\log n) くらいなので、区間和とかを使ってまとめて計算したい。

というところで、各インデックス i ごとに「左端を i とした区間で、条件を満たすものの個数」のような値を持っておき、BITやセグ木で区間和を取れないかと考えた。ただ、これだと少し扱いにくい。

これを少し修正し、単調性があることを利用して「左端を i とした区間が条件を満たすときの、一番小さい右端の位置」とする。こうすると、そのような右端の位置は i を増加させると単調増加していくので、扱いやすそう。

「左端を i とした区間が条件を満たすときの、一番小さい右端の位置」を保持しておき、これを b_{i} と表記する。これが求まっていると、クエリ 2 l r に対する答えは以下のように求められる。

  1. b_{i} \le r となる最大の i を求める。 b_{i} が i について単調増加なので、これは二分探索できる。
  2. 以下の図のように、長方形の面積から b_{i} の区間和を引き算することで、求めたい区間の数が求められる。

f:id:betrue12:20181011214713p:plain

これなら、

  • 二分探索は要素アクセスが O(1) であれば O(\log n) 。ただし b_{i} がセグ木に乗っている場合は、単純にやると O((\log n)^{2})。
  • 区間和は O(\log n) 。

ということで、 O(m (\log n)^{2}) であればなんとか通りそう。次は b_{i} をどのように維持するかを考える。

クエリ1の処理

b_{i} の初期値は、区間ORをセグ木に入れて二分探索をすると全要素 O(n (\log n)^{2}) で求められる。最初にこれを計算しておく。

問題はクエリ1の処理。 a_{i} の値が変更されると、もちろん b_{j} の値も変わる可能性がある。より具体的には、クエリ 1 i y に対して、

  • j \le i を満たす位置 j であって、
  • 変更前の値 b_{j} が i \le b_{j} を満たすもの

は、 b_{j} の値が変わる可能性がある。（ b_{j} \lt i であるときは、 a_{i} の値が変わっても b_{j} は変化しない）

この条件を満たす全ての j を見ていくのは非常に大変だが、ここでORの性質を思い出す。要素を追加していったとき、ORの値は「今までになかったビットが増えた」ときにしか増えない。

つまり i を起点にして、左側に区間を広げるにしろ、右側に区間を広げるにしろ、「新しいビットが登場」するポイントでのみORの値が変わるため、そこだけを調べればよいことがわかる。

ということで、「要素 i から見て、左側/右側それぞれ、一番近いところで k 番目のビットが立っているのはどこか」が各ビット位置 k について欲しくなる。もしこれが分かっていれば、

  1. 左端は i から始めて、ビットが増える点ごとに左に伸ばしていく。
  2. それぞれの左端 j に対して、右端をどこまで伸ばせばORの値が x 以上になるかを調べる。このときも、ビットが新しく立つ点のみを調べれば良い。
  3. これで、ある左端 j について b_{j} が求まった。ここで、 j から次にビットが増える直前まで左端を伸ばしても、右端の値は変わらないはずである。なので、区間に対して b_{j} を同じ値で上書きすることができる。

というような更新が O(B^{2}) でできる。ここで B は a_{i} の最大ビット数であり、すなわち B = 20 である。

ということで、「要素 i から見て、左側/右側それぞれ、一番近いところで k 番目のビットが立っているのはどこか」が必要になる。この値もクエリ1によって変動するが、区間更新できるようなデータ構造に乗せておけば更新は難しくない。

必要な道具の整理

ここまでの考察から、必要な道具を整理する。

まず、 b_{i} の初期値を求めるために

  • a_{i} の初期値の区間ORの値
    • 必要な操作：1点更新、区間OR

が必要であり、これはセグメント木で可能である。そのほかに、

  • 要素 i から見て、左側/右側それぞれ、一番近いところで k 番目のビットが立っているのはどこか
    • 必要な操作：区間更新、1点取得
  • 左端を i とした区間がクエリ2の条件を満たすときの、一番小さい右端の位置

これらが必要である。

区間更新を行うには、遅延評価セグメント木を用いることができる。書いたことが無かったので、以下の記事を参考にしつつ、区間更新、区間和ができるものに修正した。（つたじぇーさんありがとうございます！）

遅延評価セグメント木をソラで書きたいあなたに - hogecoder

これで必要な道具が全部揃った。

ACコード

Codeforces

実行時間はギリギリだった。実装もなかなか重め。

余談

公式解法は違う解き方をしていて、遅延評価セグメント木を使っていない。何故か英語の解説がないが、親切な人がロシア語解説からの翻訳を書いてくれている。

感想

  • OR演算の単調性をフル活用した。難しい問題だと、このレベルのテクは呼吸するように使うことが求められる。
  • 「区間の数」の数え上げは愚直だと O(n^{2}) 以上かかり、これを工夫で O(n) や O(n \log n) にすることはよくある。今回はそこからさらに落とすための発想が必要だった。
  • 「答えを得るために必要な値は何か」「その値を得るために必要な値は何か」…というように、難しい問題でも段階的に考察を進めていくことができた。本番でもこれができるようになりたい。
  • 遅延評価セグメント木を初めて使った。初めて使う道具で重い問題に挑むのは無謀。今回もかなりバグらせた。

Codeforces Round #514 (Div. 2) 参加記録＆解説（A～E）

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

Dashboard - Codeforces Round #514 (Div. 2) - Codeforces

結果は4完で88位。

f:id:betrue12:20181006175548p:plain

本番後に通したEも含めて5問振り返ります。

A. Cashier

Problem - A - Codeforces

問題概要

0 \le t \le L の区間を考える。この中に、 n 個の「選択不能区間」 t_{i} \le t \le t_{i} + l_{i} が存在する。選択不能区間および他の選択区間と端点以外で重ならないように、 0 \le t \le L の区間の中から長さ a の区間をできるだけ多く選択する時、その個数を求めよ。

制約

  • 0 \le n \le 10^{5}
  • 1 \le L \le 10^{9}
  • 1 \le a \le L
  • 0 \le t_{i} \le L-1, 1 \le l_{i} \le L, t_{i} + l_{i} \le t_{i+1}, t_{n} + l_{n} \le L

解法

区間と区間の間から長さ a の区間を取れるだけ取ります。両端を区間の1つとして扱うと実装が楽です。

ACコード

Submission #43832898 - Codeforces

B. Forgery

Problem - B - Codeforces

問題概要

# と . で構成された n \times m のマス目が与えられる。# が黒、. が白を示す。

n \times m の全てのマスが白い状態から、「以下のような中央に穴の空いた形をした 3\times 3 のハンコを、この向きのままマス目の好きな位置に押す」ことを0回以上繰り返し、与えられたマス目を再現したい。これが可能かどうか判定せよ。

###
#.#
###

ハンコの黒い部分が押されたマスは黒になり、中央の穴に相当するマスは変化しない。マス目からはみ出すようにハンコを押すことはできない。

※問題文がちょっと曖昧なので、問題文に明記されていないことも含めて補足をしています…

制約

  • 3 \le n, m \le 1000
  • 与えられるマス目は n 行 m 文字の文字列で、# と . からなる

解法

まず、全部白のマス目を用意します。盤面から切り取れる全ての 3 \times 3 のマス目について、「与えられたマス目において、その 3 \times 3 の位置のうちハンコの形状通りの8マスが全て黒であれば、用意したマス目において同位置の8マスを黒く塗る」という操作をします。真ん中の色がどちらか、は気にしません。

これで、ハンコを押して良い位置が全て押されたことになります。この操作によって与えられたマス目を全て再現できている場合答えは YES となり、そうでない場合は NO となります。

盤面から切り取れる 3 \times 3 のマス目は全部で (n-2)(m-2) 個あり、計算量が O(nm) となりますが、この制約では十分間に合います。

ACコード

Submission #43839595 - Codeforces

C. Sequence Transformation

Problem - C - Codeforces

問題概要

正整数 n が与えられる。「操作」の数列を 1, 2, ..., n 、「結果」の数列を空として、以下の操作を n 回繰り返す。

  1. 「操作」の数列全ての要素の最大公約数（GCD）を、「結果」の数列の末尾に追加する。
  2. 「操作」の数列から、好きな要素を1つ取り除く。

この操作の結果となる「結果」の数列を、辞書順最大にしたい。そのときの「結果」の数列を出力せよ。

制約

  • 1 \le n \le 10^{6}

解法

最初の状態では、GCDは1です。辞書順最大を求めたいので、「なるべく早くGCDを1より大きい値にしたい」と考えます。つまり、1以外でなるべく多くの要素のGCDとなっているものを探して、それ以外の要素を取り除きたいです。ただし、要素数が同数の場合は大きいほうのGCDを採用します。

最初の 1, 2, ..., n の状態では、ほとんどの場合そのようなGCDは2です。GCDを2にするため、まずは奇数を取り除きます。

奇数を取り除くと、数列は 2, 4, ..., \lfloor\frac{n}{2}\rfloor となります。次は何が一番多いでしょうか？　既に最大公約数となっている2を無視すると、この数列はやはり 1, 2, ..., n^{\prime} のような形をしています。同じように考えると、やはり一番多いのは2、すなわち元の数列で言う4です。

このように、 1, 2, ..., n^{\prime} の 2^{k} 倍の形状をした数列から奇数番目の要素を取り除き、そうするとその結果はやはり 1, 2, ..., n^{\prime\prime} の 2^{k+1} 倍になっていて…という操作を繰り返すことで、多くの場合解を求めることができます。

ただし問題ページ中のサンプルにもあるように例外があります。それは数列が 1, 2, 3 であるとき、もしくは操作の途中でその 2^{k} 倍になったときです。このとき、2も3も含まれる要素の個数は同じ1個なので、大きい方である3を残さないといけません。

ACコード

Submission #43843969 - Codeforces

D. Nature Reserve

Problem - D - Codeforces

問題概要

xy 平面上に n 個の点 (x_{i}, y_{i}) が配置されている。以下のような条件を満たす円が存在する時、その半径の最小値を求めよ。または存在しないことを判定せよ。

  • その周上または内部に n 個の点を全て含む。
  • x 軸（直線 y=0 ）に1点で接する。

制約

  • 1 \le n \le 10^{5}
  • -10^{7} \le x_{i}, y_{i} \le 10^{7}, y_{i} \ne 0

解法

まず条件を満たすためには、 y_{i} が正または負に全て固まっていることが必要です。 x 軸に接する円は、 y が正負どちらか片方の領域にしか存在できないからです。逆に正または負に固まっている場合、半径をものすごく大きくとればいつかは全ての点が収まるので、解は存在します。

以降、 y 座標が全て負の時は反転し、全て正としておきます。

半径を r とします。条件を満たす r の範囲は単調（求めたい最小値を r_{\min} とすると、 r \ge r_{\min} の範囲の r は全て条件を満たす）なので、二分探索をします。つまり半径 r を固定して、条件を満たすかどうかのYes/No問題を解きたいです。

x 軸に接するということは中心の y 座標は r であり、円内部の方程式は中心の x 座標を a として

(x-a)^{2} + (y-r)^{2} \le r^{2}

です。与えられた座標点 (x_{i}, y_{i}) が円内部に存在する条件は、この座標を代入して a についての方程式を解くと求められます。

n 個の点全てについて a が存在すべき範囲を求めて、それらが共通点を持てば、条件を満たす円が存在するので判定はYesです。このようにYes/No問題を解いて、二分探索をすることができます。

最後に、二分探索の初期範囲を考えます。半径が小さすぎると、 y 座標が大きな点にそもそも届きません。先程の方程式でいうと「実数解が存在しない」ということに相当します。全ての y_{i} に届くよう、下界は \frac{\max y_{i}}{2} とします。

そして上界ですが、これが意外と大きくなります。点群に、 (-10^{7}, 1) と (10^{7}, 1) のように y 座標がとても小さくて x 座標がとても離れた点が存在すると、必要な半径は大きいです。実際に求めてみます。

f:id:betrue12:20181006192949j:plain

このケースにおいて三平方の定理を使うと r = \frac{10^{14}+1}{2} となります。おそらくこれが最大です。大きく取りすぎても反復回数が数回増えるだけなので、どんぶり勘定で大きめに取っておいてもいいとは思います。

計算量は1回のYes/No問題が O(n) 、反復回数は初期範囲と終了範囲の長さの比を取ったものの \log オーダーで、ほとんどの場合100回以内に収まるんじゃないかと思います。（私は100回指定でループしています）

ACコード

Submission #43849835 - Codeforces

E. Split the Tree

Problem - E - Codeforces

問題概要

頂点 n 個の根付き木が与えられ、各頂点には重み w_{i} が設定されている。

これらの頂点を、互いに交わらない、以下の条件を満たす集合に「垂直分割」する。その集合の個数の最小値を求めよ。

  • 集合に含まれる要素は、ある要素から親を辿ったもの、またその親を辿ったもの…というように、縦一列に並んでいる。
  • 集合の要素数は L 以下である。
  • 集合に含まれる要素の重み合計は S 以下である。

制約

  • 1 \le n \le 10^{5}
  • 1 \le L \le 10^{5}
  • 1 \le S \le 10^{18}
  • 与えられる木は頂点1を根とする根付き木である

解法

木DPを考えてみます。子のほうから順に処理をしていって、ある頂点に注目したとき、パスの取り方としてどのようなものがあるでしょうか。

  1. 子から伸びてきている「未完成の集合」のうち、高々1つに自分を加える。残りはその時点で完成した集合となる。
  2. その後、自分（または自分を加えた集合）を、「未完成の集合」として親に伸ばす。

ここで難しいのが、「子から伸びてきている集合のうち、どれを採用して上に伸ばすか？」です。将来性があるものを上に伸ばしたいですが、長さと重み合計という2つの条件があるので、短いものがいいのか軽いものがいいのか単純には決められません。

ただこの問題の場合、親を順に辿っていくようにしか要素が追加されないため、将来的に追加されていく要素とその順番は決まっています。そのため「いまこの集合から、あと上にいくつの要素を足せるか？」というものを事前に計算してしまうことができます。これを計算し「上に足せる要素数が最も多いもの」を選べば、当然それが最適になるということです。

ということで、次は「いまこの集合から、あと上にいくつの要素を足せるか？」を効率的に求める方法を考えます。これを毎回1つずつやっていると間に合わないので、ダブリングという方法を使います。これは

  • ある点 i から、
    • 上に1個足したときの増加重み合計はXXで、1つ上の親は○
    • 上に2個足したときの増加重み合計はXXで、2つ上の親は○
    • 上に4個足したときの増加重み合計はXXで、4つ上の親は○

というように、2の冪乗ごとに 「 2^{k} 進んだときの情報」を事前計算しておく方法です。これを計算しておけば、「いまこの集合から、あと上にいくつの要素を足せるか？」を計算する時は逆順に「8個要素を足せるか？」「4個要素を足せるか？」「2個要素を足せるか？」…　のように考えていくことで、効率的に計算をすることができます。

解法をまとめると、

  1. まず事前計算として、各頂点について「親を 2^{k} 個辿ったときの重み合計」と「辿った先の親」を、 2^{k} \le n である k それぞれについて計算する。
  2. 葉から木DPをする。 dp\lbrack i \rbrack を「頂点 i を含んでいる集合から、上にいくつ要素を足せるか」とする。
    1. 子の中で、「上にいくつの要素を足せるか」が正のものが存在する場合、その値が最も大きいものを採用し、その集合に自分を含める。つまり子 j のうち dp\lbrack j \rbrack \gt 0 であるものが存在する場合、その中で最大のものを選んで dp\lbrack i \rbrack = dp\lbrack j \rbrack - 1 とし、残りの集合は完成させる（答えの個数に加算する）。
    2. 1で自分を含めた集合がなかった場合は、自分自身を始点とする新しい集合を作る。このとき「上にいくつの要素を足せるか」を事前計算の結果を使って効率的に計算し、 dp\lbrack i \rbrack とする。
    3. 1, 2いずれの場合においても、これ以上上に伸ばせない場合、つまり dp\lbrack i \rbrack = 0 であるときは、集合を完成させる。また見ている頂点が根である場合も、もう上はないので集合を完成させる。
  3. 完成させた集合の個数が答えである。

のようになります。

ダブリングについては以下の記事が図説スライド付きで分かりやすいのでオススメです。また、蟻本にも載っています。

ダブリング - sataniC++

ACコード

Submission #43889325 - Codeforces

さいごに

順位としてはまあまあ。Eは解きたかったですね…

ABC112 参加記録＆解説

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

AtCoder Beginner Contest 112 - AtCoder

結果は26分台全完で42位。まあまあ。

f:id:betrue12:20181006213126p:plain

A - Programming Education

A - Programming Education

解法

分岐してそれぞれ処理。年商10億円突破楽しみにしています。

ACコード

B - Time Limit Exceeded

B - Time Limit Exceeded

解法

求めたいコストを c として、ループを回して t_{i} \le T であれば c を \min(c, c_{i}) で置き換える、を繰り返します。

c の初期値としては、どの c_{i} よりも大きい値を設定しておくとよいです。今回であれば1001や10000など。ここから一度も更新されなければ TLE という判定ができます。

ACコード

C - Pyramid

C - Pyramid

解法

ちょっとだけ設定が複雑に見えますが、条件として与えられる点の数 N \le 100 、中心座標の候補が 0 \le C_{x}, C_{y} \le 100 であることから全探索が可能です。中心座標を全探索します。

中心座標 (C_{x}, C_{y}) を固定した時、その中心座標について「全ての条件を満たすようなピラミッドの高さ H が存在するか？」を調べます。もしそのような H が存在すれば、制約より解は1組だけしか存在しないため、見つかったものを出力して終了すればよいです。

条件となっている点 (x_{i}, y_{i}) を順番に見ていきます。式を見やすくするため、 (x_{i}, y_{i}) から中心までのマンハッタン距離を d_{i} = |C_{x} - x_{i}| + |C_{y} - y_{i}| と表記します。問題文中の式は h_{i} = \max(H - d_{i}, 0) と書き換えられます。

中心を固定し、条件となっている点 (x_{i}, y_{i}) を1つチェックし、その高さが h_{i} となるために中心の高さ H が満たすべき条件を考えます。その条件は、 h_{i} = 0 のときとそうでないときで以下の図のように異なります。

f:id:betrue12:20181009200752p:plain

  • h_{i} > 0 のとき
    • このとき、これを満たす H はただ1つであり、 H - d_{i} = h_{i} より H = d_{i} + h_{i} である。
  • h_{i} = 0 のとき
    • このとき、これを満たす H の候補は1つに絞られない。ただし、「 H は d_{i} 以下である」という条件は満たされる必要がある。 H がこれより大きいと H - d_{i} が正になり、すなわち h_{i} も正になってしまうため。

これを全ての点について調べ、矛盾がなければそれを出力して終了です。矛盾があれば、次の中心座標を試します。これを繰り返せば、制約上どこかで解が見つかります。

ACコード

D - Partition

D - Partition

解法

a_{1}, ..., a_{N} の公約数を d とします。このとき、以下の2つが成り立つことが必要です。

  • d は a_{1} + ... + a_{N} = M の約数である。
  • a_{i} \ge d であることから、 M = a_{1} + ... + a_{N} \ge Nd である。

逆にこれらを満たす時は、 \frac{M}{d} 個の d を最低1個ずつ適当に a_{i} に割り振れば、 d は a_{1}, ..., a_{N} の公約数になります。

つまりこれら2つの条件を満たす中で最大の d が、求めたい「最大公約数の最大値」です。

ということで、まず M の約数を列挙しましょう。素因数分解を使う方法もありますが、1から \lfloor\sqrt{M}\rfloor までの整数で割ってみる方法が楽です。 もし i で割り切れたら、その i と \frac{M}{i} が約数になるので、これを集めます。

約数が列挙できたら、 Nd \le M を満たすものだけを抜き出し、その中の最大値が答えです。制約 N \le M より d = 1 は必ず条件を満たすので、解無しとなる可能性はないです。

ACコード

最後に

前回のABCオンリー回も、Dは約数絡みの問題でしたね。最近の流行り？