ARMERIA

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

AGC027 参加記録

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

結果は1完…速かったのでそこまでパフォーマンスは悪くないのですが、前回時点で黄色スレスレだったので色が落ちてしまいました。

f:id:betrue12:20180916041647p:plain

本番後に通したものも含めてA～Cを振り返ります。

A - Candy Distribution Again

A - Candy Distribution Again

解法

要求数が小さい子供から順番に配っていくと良いです。ぴったり配りきれない場合は最後の1人が満足できないので注意。

ACコード

B - Garbage Collector

B - Garbage Collector

解法

本番では「端から i 個回収済みで原点にいるときの最小消費エネルギー」みたいなのでDPをずっと考えていましたが…どうやらそれでは最適でないケースがあるようです。

普通に解法を書くと公式解説とほぼ同じ流れになってしまうので、公式解説で省略されている内容を補足しつつ書いていきます。

移動エネルギーの求め方

まず、普通にゴミをいくつか拾う時の移動エネルギーを考えてみます。

f:id:betrue12:20180916100210p:plain

上図で、 x_{1} ～ x_{3} のごみ全てを1回で回収することを考えます。所持ゴミが多いほどエネルギーが余計にかかるので、なるべく帰り道に拾ったほうがよいです。図のように拾っていくと、移動エネルギーの合計は 5x_{3} + 5x_{2} + 7x_{1} となります。

より一般的に書くと、各項にかかる係数は、

  • 一番右の x の係数は、往路1と復路4の合計で5
  • 右から i 番目（ i \ge 2）の x の係数は、 (i+1)^{2} から i^{2} を引いたものになり、これを計算すると 2i+1 になる

となります。各係数が「そのゴミを何番目に拾うか」だけで決まり、その順番が遅いほど係数が大きくなっているのがポイントです。

往復回数決め打ち全探索

公式解説通り、往復回数を決め打ちして考えます。往復回数を k とします。

このとき、 k 回の往復にゴミを割り当てることになりますが、どのような割り当てが最適でしょうか。

f:id:betrue12:20180916100813p:plain

この図のように、各要素に「ゴミを拾う順番」を割り当てます。 k 回往復するので、1番目に拾うゴミが k 個、2番目に拾うゴミが k 個…というのを割り当てることになりますが、これを右から順番に割り当てていくのが最適となります。

その理由は、直観的にはこう説明できます。前節で見たように、ゴミを拾う順番が遅いほど、そのゴミのための移動エネルギーの係数が大きくなります。より距離が長いほうのゴミに、より大きな係数を掛けてしまうと損です。そのため、遠いゴミほど係数を小さくしたい、つまり早い順番で拾いたい、と考えると上のようになります。

ちゃんと証明しようと思うと、最適でない並べ方と最適な並べ方の移動エネルギーの差分を計算して、不等式で評価して0以上であることを示すんじゃないかと思います。

累積和でまとめて計算

上記の割り当てのもとで、移動エネルギーの合計を計算していきましょう。このとき、拾う順番が同じ要素たちは、

  • 係数が同じ
  • 全て隣り合っている

という特徴があります。そのため、累積和を使ってまとめて計算することができます。

f:id:betrue12:20180916134223p:plain

累積和を事前に計算しておくと、拾う順番の最大値、つまり \lceil \frac{N}{k} \rceil 回の計算で移動エネルギーを求めることができます。これは後で計算量の話の時に使います。

ゴミを拾う・捨てるエネルギー

後回しにしていましたが、ロボットは移動エネルギーの他に、ゴミを拾う・捨てるのにもエネルギーを消費します。

ゴミを拾う回数はゴミの個数と同じ N なので、ゴミを捨てる回数（＝往復回数）が k であるとき、ゴミを捨てる・拾うエネルギーは (N+k)X となります。

解法まとめ

以上で問題を解く材料が揃いました。

  1. x_{i} の累積和を前計算しておく。
  2. 往復回数 k を決め打ち全探索する。
    1. 移動エネルギーは、累積和を使ってまとめて計算する。
    2. 拾う・捨てるエネルギーは (N+k)X で計算できる。
  3. 全探索で一番小さかったものを答えとする。

これで解くことができます。往復回数決め打ちに気付くかどうか…ですね。

補足

計算量についてです。先程見たように、往復回数を k とすると、その時の移動エネルギーは \lceil \frac{N}{k} \rceil 回の計算で求められます。

ちょっと乱暴ですがceilを外して、 \sum_{k=1}^{N} \frac{N}{k} = N\sum_{k=1}^{N} \frac{1}{k} を考えます。この \sum_{k=1}^{N} \frac{1}{k} という式は調和級数という名前が付いていて、だいたい \log(N+1) くらいの値になります（積分で近似計算できます）。そのため、 \sum_{k=1}^{N} \frac{N}{k} = O(N\log N) であることから、移動エネルギーの計算量は全体で O(N\log N) となります。累積和などそれ以外の計算は O(N) なので、問題全体の計算量も O(N\log N) です。

次にオーバーフローについて。すごく極端な例ですが、最も遠い、ほぼ 10^{9} の位置に 2\times10^{5} 個のゴミが密集していて、これを1回で回収することを考えます。そのとき、帰り道の距離はほぼ 10^{9} であり、持っているゴミの個数は 2\times10^{5} 個なので、 4\times10^{19} くらいになってlong longでもオーバーフローします。

ただしこれが答えになることはありません。もし全要素を1個ずつ拾うという動きをした場合、移動エネルギーの合計は 5\sum_{i} x_{i} 、ごみを拾う・捨てるエネルギーの合計は 2NX となり、この値は制約から計算すると 1.4 \times 10^{15} 未満です。なのでそれぞれの往復回数について移動エネルギーを計算しているときにも、この値を超えた時点でもう最適解にはなり得ないので、計算途中で打ち切ってしまって構いません。このようにするとオーバーフローを回避することが出来ます。

ACコード

※（2019/03/14）C++のコードのオーバーフロー回避方法がマズかったので差し替えました。

C - ABland Yard

C - ABland Yard

公式解説の方法がだいぶ天才感あるので、まずはイメージしやすい頂点削除の解法を書いていきます。

解法1：頂点削除

「任意の文字列を作れる」ということは、「次にAにもBにも遷移できる」という状態を永遠に続けられることを意味します。

そのため、グラフ内に「次にAとBのどちらかにしか遷移できない」もしくは「どこにも遷移できない」という頂点が存在する場合、その頂点は「入ってはいけない頂点」ということになります。

f:id:betrue12:20180916114429p:plain

このような「入ってはいけない頂点」は、文字列を構成する上で使えないので、グラフから消してしまいます。そのとき、繋がっている辺もろとも消します。

そうすると辺を消したことで、他の頂点の遷移先が減ります。これにより他の頂点が「次にAとBのどちらかにしか遷移できない」という状態になってしまうと、その頂点も使えなくなります。こうして連鎖するように、頂点が消えていく可能性があります。

f:id:betrue12:20180916115137p:plain

上のグラフではその後、連鎖的に全ての頂点が消えてしまいます。そうなってしまった場合、答えはNoです。

一方、全部の頂点の削除判定を全て済ませてなお生き残った頂点がいる場合、それらの頂点は全て「次にAにもBにも遷移できる」頂点なので、その頂点を辿っていくことで任意の文字列を作ることができます。その場合、答えはYesです。

頂点の削除判定は、各頂点ごとに「A、Bに遷移する辺がそれぞれいくつあるか」を管理して、辺を消すごとに1引いていくと楽です。どちらかが0になったら削除します。

解法1：ACコード

解法2：AABB法

解法1で見てきたように、「任意の文字列を作れる」ということは、「次にAにもBにも遷移できる」という状態を永遠に続けられることを意味します。

仮に与えられたグラフで、「AABBAABBAABB…」という文字列を無限に続けられるとします。このとき、グラフが無向グラフなので、その経路内の任意の点はAにもBにも遷移できていることになります。この経路を前に進むか、後ろに戻るかで、異なるアルファベットに遷移できます。

※「端点は？」という話はありますが、一方が無限に続いているので、無限に遠いところ（具体的には、作りたい文字列の長さを超えるところ）からスタートすれば端点に届くことはありません。

f:id:betrue12:20180916121833p:plain

逆にこの文字列が作れないときに「任意の文字列を作れる」と言えないことは当たり前なので、「AABBAABB…」という文字列を無限に続けられるかどうかを考えれば、それが任意の文字列を作れることの必要十分条件になっています。

では、「AABBAABB…」という文字列を無限に続けられる条件を考えます。それぞれの「AABB」のうちの最初のAを「1つ目のA」と呼ぶことにします。頂点数は有限なので、この「AABBAABB...」を続けていくと、必ずどこかで「1つ目のA」が重複するはずです。なので、「1つ目のA」が重複している経路がない場合は「AABBAABB…」の無限経路が存在しないことになりますし、逆に重複していればその経路をぐるぐる回り続けることができます。

これで必要十分条件を「AABB...を繰り返す経路で、「1つ目のA」が重複しているものが存在する」まで落とし込めました。これを解くにあたって、「1つ目のA」と「2つ目のA」を分けて考えたくなります。そのため、AもBも1つ目と2つ目で分けて、頂点数を2倍にすることを考えます。

元のグラフは無向グラフでしたが、

  • 1つ目のAからは2つ目のAに
  • 2つ目のAからは1つ目のBに
  • 1つ目のBからは2つ目のBに
  • 2つ目のBからは1つ目のAに

だけ、それぞれ遷移するような有向グラフに変換します。この有向グラフにおいて閉路が存在すれば、それがAABB...を繰り返す経路で「1つ目のA」が重複しているものになります。

f:id:betrue12:20180916123714p:plain

このグラフで閉路が存在するかどうかを判定すれば、この問題が解けます。

解法2：ACコード

さいごに

大変な回でした…本番中はほぼ全ての時間をB問題のDPと戦うのに費やしていました。

次は黄色復帰を目指します！

ABC109 参加記録

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

2週間ARCとの併催で配点が恐ろしい感じでしたが、久しぶりにまともな配点のABCになりました。

結果は16分台全完で18位。けっこう速かったですね。ARCでもDが400だったらこのくらいの速度で解きたいです。

f:id:betrue12:20180908212243p:plain

A - ABC333

A - ABC333

解法

A と B のどちらかが偶数だったら A \times B \times C は必ず偶数になります。また、 A と B が両方とも奇数だったら C = 1 とすることで積を奇数にできます。これを場合分けします。

ACコード

（Ruby）Submission #3151145 - AtCoder Beginner Contest 109

B - Shiritori

B - Shiritori

解法

重複した文字列があるかの確認をして、 i 番目の末尾と i+1 番目の先頭が一致しているかを i=1, ..., N-1 について判定すればよいです。

ACコード

（Ruby）Submission #3152443 - AtCoder Beginner Contest 109

C - Skip

C - Skip

解法

座標 X からのスタートだと考えにくいので、まず x_{i} 全てから X を引いて、座標0からのスタートだとしてしまいましょう。

そうすると到達可能な点は、座標0からスタートして任意回の \pm D の移動で到達できる点、つまり D の倍数です。つまり、（補正後の） x_{i} 全てが D の倍数であるという条件を満たすように、なるべく大きな D を選べばよいです。これは x_{i} の最大公約数になります。

ACコード

（Ruby）Submission #3153468 - AtCoder Beginner Contest 109

D - Make Them Even

D - Make Them Even

解法

問題文だけ読むと分かりませんが、出力例を見ると構築問題であることが分かります。

全コインの合計が偶数だった場合は、全マスを偶数にするのが最適です。全コインの合計が奇数だった場合は、1マスを残してそれ以外を偶数にするのが最適です。このように作れないか考えます。

全マスを一筆書きできるような経路を考えます。そのような経路をずっと辿っていき、「マスのコイン数が奇数だったら次のマスに1個渡す」ということを繰り返していくと、全マスについての操作回数を1回以下にしつつ、最後に訪問するマス以外は全て偶数個コインにできるはずです。

場合によってはちょっと操作回数に無駄がありますが、操作回数は最小化しろと言われていないので、これで大丈夫です。一筆書きの経路は、例えば以下のようなものを作ると良いでしょう。

f:id:betrue12:20180908224134p:plain

ACコード

（Ruby）Submission #3155067 - AtCoder Beginner Contest 109

さいごに

最近激しい回が続いていましたが、ちょっと和みましたね。

Educational Codeforces Round 50 参加記録

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

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

結果は5完で72位！けっこう不安な問題が多かったのでシステス全部通って良かったです。

f:id:betrue12:20180908194632p:plain

A～Eを振り返ります。

A. Function Height

Problem - A - Codeforces

問題概要

底辺が2で高さが0以上の整数である三角形を n 個作り、合計面積を k にしたい。高さの最大値を最も小さくするように各三角形の高さを決めたとき、その値を求めよ。

制約

1 \le n, k \le 10^{18}

解法

底辺が2なので高さの値がそのまま面積になります。 n 個の三角形にまんべんなく高さを振り分けて合計を k にすると、その最大値は \lceil\frac{k}{n}\rceil でありこれが最適です。

ACコード

B. Diagonal Walking v.2

Problem - B - Codeforces

問題概要

以下のクエリ q 個に答えよ。

二次元平面があり、Mikhailは1回の操作で縦横斜めの近傍8マスいずれかに移動する。始点 (0, 0) 、終点 (n, m) 、操作回数 k が与えられ、始点から終点までちょうど k 回で移動する経路のうち、斜め移動の回数が最大のものを選ぶ時、その回数を求めよ。（または、 k 回で到達できないことを判定せよ。）

制約

  • 1 \le q \le 10^{4}
  • 各クエリ i について 1 \le n_{i}, m_{i}, k_{i} \le 10^{18}

解法

まず、到達できない条件を考えます。 k 回の操作で到達可能な x, y 座標の最大値は k であり、終点座標のどちらか1つでもこれを超えているとアウトです。

斜め移動を行った場合、 x, y 座標ともに偶奇が入れ替わることに着目します。可能であれば全操作で斜め移動をしたいですが、 (0, 0) から斜め移動 k 回だけを行った場合、終点座標は n, m ともに k と偶奇が一致している必要があります。

そうでない場合、例えば k が偶数で n が奇数だった場合は、全操作斜め移動というのは不可能であり、最低1回は x 座標が変わらない移動をする必要があります。 y 座標についても同様です。

このような考察から以下のように答えを求め、実際の移動を構成することができます。

  1. n, m の偶奇がどちらも k とそれぞれ一致する場合、答えは k。各操作での移動量は x, y それぞれについて、和が n, m と一致するように +1 と 1 を並べればよい。
  2. n と k の偶奇が一致し、 m と k の偶奇が一致しない場合、答えは k-1。移動量は x については1.と同様で、 y については1つだけ0を含み、残りは +1 と -1 を並べる。
  3. 2.と逆の場合、同様に答えは k-1 。
  4. n, m どちらも k と答えが一致しない場合、答えは k-2 。 x, y それぞれ移動量に1つずつ0を含む。移動量 (0, 0) は許されていないため、これらは別々の操作に配置されなければならない。残りは +1 と -1 を並べる。

最後の項目は、例えば以下のような移動量となります。 k=5, n=2, m=4 とした例です。

移動回数 x 移動量 y 移動量
1 +1 +1
2 +1 +1
3 +1 +1
4 0 +1
5 -1 0
合計 2 4

※ k=1 で n, m どちらも k と偶奇が一致しないケースが怖くなりますが、そのようなケースは (2, 2) より遠い点であればそもそも到達不可能として弾いていますし、 (n, m) = (0, 0) は制約上与えられないので、大丈夫です。

ACコード

C. Classy Numbers

Problem - C - Codeforces

問題概要

以下のクエリ T 個に答えよ。

正整数 L, R が与えられる。 L 以上 R 以下の整数で、10進数表記したときに0でない数字の個数が3個以下であるものの個数を求めよ。

制約

  • 1 \le T \le 10^{4}
  • 各クエリ i について 1 \le L_{i} \le R_{i} \le 10^{18}

解法

数値がやたら大きい、桁の値についての条件あり、ということで桁DPをやります。桁DPについては既に素晴らしい記事があるのでリンクを貼るだけに留めます。

桁DP入門 - pekempeyのブログ

今回の場合、「見ている桁」「 L を超えていることが確定しているかどうか」「 R 未満であることが確定しているかどうか」「非0の数字の個数」をパラメータとしてDPを組めます。メモ化再帰で書く場合は、非0の数字の個数が3を超えたら即0を返すような実装にすると、条件を満たさない整数をフィルタできます。

または下限の条件を外して、「 0 以上 R 以下で条件を満たす整数の個数」を求めることができるので、 R と L-1 で2回計算して引き算しても良いですね。本番でこっちを思いついていればもっと実装が楽になったでしょう…。

ACコード

D. Vasya and Arrays

Problem - D - Codeforces

問題概要

長さ n の数列 A と長さ m の数列 B があり、これらをそれぞれ以下のように分割したい。

  • 分割した部分列の個数はどちらも K 個である。
  • 全ての i = 1, ..., K について、 A の i 番目の部分列の合計と、 B の i 番目の部分列の合計は等しい。

このような条件を満たす最大の K を求めよ。（またはこのような分割が不可能であることを判定せよ。）

解法

分割が不可能である条件はすぐに分かって、 A, B の総和が一致しないことです。逆に総和が一致する場合は、最低でも K = 1 が解になります。

最適な分割方法を考えます。 A, B の前からの部分列をそれぞれ伸ばしていって、できるだけ小さい値で部分列同士の総和が一致すれば、その点で分割するのが最適です。つまり A, B の部分列のうち、その時点での総和が小さい方を1伸ばして判定、を繰り返すことが最適です。

ACコード

E. Covered Points

Problem - E - Codeforces

問題概要

二次元平面に n 本の線分があり、以下の条件を満たす。

  • 線分の両端点は格子点（座標が全て整数である点）である。
  • どの2線分も同一直線上にない。

少なくとも1本の線分に含まれる格子点の個数を求めよ。

制約

  • 1 \le n \le 1000
  • 全ての線分の端点の座標は -10^{6} \le x, y \le 10^{6} を満たす。

解法

この問題は、以下の2つのことを計算できると解けます。

  1. 線分それぞれについて独立に数えた、その線分に含まれる格子点の個数の総和
  2. 線分同士が交差する格子点と、その格子点を通る線分の個数のリスト

1で重複を気にせず独立に数え、2で数え過ぎた分を引く、という流れです。

まず1についてですが、これは最大公約数が使えます。両端点が格子点で、 x 座標が a 、 y 座標が b 変化する線分に含まれる格子点の個数は \gcd(a, b) + 1 となります。ただしどちらかが0の時は例外で、0でないほうの値を c として c+1 個です。

次に2についてです。交点の座標は連立方程式を解けば良いので計算できますが、コーディングだと色々面倒があります。私は以下の式を使いました。線分同士が平行である場合には0除算が起こったりするので注意。

月の杜工房 - 2直線の交点を求める

「線分の交点が存在して、かつそれが格子点」である場合を抽出します。直線の交点を求め、それが線分上にあってかつ格子点であるかを判定します。これを異なる線分全ペアについて試し、出てきた格子点とその出現回数をmapなどで集計します。

得られた重複格子点それぞれについて、重複分を引いていきます。線分 k 本が交差する格子点である場合、その格子点の出現回数は \frac{k(k-1)}{2} 回であり、引くべき個数は k-1 個です。出現回数から線分の本数を逆算するmapなどを作っておくと、集計した情報から引くべき個数が求められます。

ちょっと大変ですが、これでなんとか解けました…

ACコード

このコードでは線分の交点を求める際に「線分の交差判定をやってから交点座標を求める」という処理をしていますが、解法で書いたように先に交点を求めてしまったほうが楽だと思います。

さいごに

今回でこどふぉのレートが紫になりました！

f:id:betrue12:20180908205340p:plain

こどふぉはレートがガンガン変動しますね。またここから上がったり下がったりするとは思いますが、まだまだ上の色を目指して頑張ります。

Codeforces Manthan, Codefest 18 参加記録

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

何か不規則な解き方してますが、Fが通ったおかげでレートも結構上がりました。Dは誤読で落ちました（にゃーん）

f:id:betrue12:20180903203023p:plain

後から解いたものも含めてA～Fを振り返ります。

A. Packets

Problem - A - Codeforces

問題概要

1円玉 n 枚をいくつかの袋に入れて、「袋をいくつか適切に選ぶことで、合計金額 0, 1, 2, ..., n 円*1の全通りが作れる」状態にしたい。最小の袋の数を求めよ。

解法

2進数で作るとよさそうです。 2^{m} -1 \le n である最大の整数を m として、 m 個の袋に 1, 2, 4, ..., 2^{m-1} 円を入れると、 0, 1, 2, ..., (2^{m}-1) 円の全パターンが作れます。端数が出た場合は、余った分をもう1つの袋に入れれば、 n まで全部のパターンを作れます。つまり袋の数は、 2^{M} - 1 \ge n であるような最小の整数 M となります。構成方法を示したので、これは十分条件です。

次に必要性、つまりこれより小さい解がないことを確かめます。 M 個の袋を使って得られるパターン数は、いくら値が被らないように努力したとしても、全ての袋について「選ぶ」「選ばない」で分岐した高々 2^{M} 通りです。作る必要があるパターン数は n+1 通りなので、 2^{M} \ge n+1 が必要条件となります。これは上の式に一致するので、ちょうど必要十分です。

ACコード

B. Reach Median

Problem - B - Codeforces

問題概要

要素数が n （奇数）の数列 a_{1}, ..., a_{n} と整数 s が与えられる。操作「数列の要素 a_{i} を1つ選び、+1または-1を足す」を繰り返して数列の中央値を s にしたい。操作の最小回数を求めよ。

解法

要素数が奇数の数列の中央値が s になる条件は、要素を左から右に昇順ソートしたときに真ん中の要素が s であることです。もう少し全体的に見ると、

  • 真ん中の要素が s である
  • 真ん中より左の要素が s 以下である
  • 真ん中より右の要素が s 以上である

このようになっていればよいです。

元の数列を昇順ソートして、上記の条件を満たすように加減してやればよいです。わざわざ大小の順番を入れ替えるような操作は、得になることはありません。

ACコード

C. Equalize

Problem - C - Codeforces

問題概要

長さ n で各文字が0か1の文字列 a, b が与えられる。 a に以下の操作を好きな順序で好きな回数繰り返して、 b と一致させたい。最小のコストを求めよ。

  • a の文字を1つ選んで書き換える。コスト1。
  • a の文字を2つ選んで入れ換える。コストは入れ換える2文字の距離。

解法

まず、「入れ換える」ことで得になるケースはかなり限られています。入れ換える操作は、最大2文字を書き換える操作をすれば同じことができて、そのコストは最大でも2です。つまりコストが2以上かかるような入れ換え操作はする必要がなくて、

  • 隣り合った2文字を両方書き換える（コスト2）代わりに、その2文字を入れ換える（コスト1）

以外の入れ換え操作では得をしないことがわかります。そのため、

  • a 側が「10」で b 側が「01」、あるいはその逆である箇所のみ、入れ換え操作を行う。
  • それ以外の場所は単純に書き換え操作を行う。

これで最適となります。

ACコード

D. Valid BFS?

Problem - D - Codeforces

問題概要

n 頂点の木と、 1, ..., n を並び替えた数列 a_{1}, ..., a_{n} が与えられる。数列が「木を頂点1からBFSしたときの探索順序」になっているか判定せよ。

解法

問題文にも書いてありますが、BFSを実装する際は

  1. 始点をキューに入れる。
  2. キューから頂点番号を取り出す。
  3. その頂点に隣接する頂点のうち未訪問のものをキューに入れる（普通のBFSでは、このときのpush順序は実装者が勝手に選ぶ）。
  4. 2に戻る。

を、キューが空になるまで続けます。

今回は始点と探索順序が指定されているので、

  1. まず数列の始点 a_{1} をキューに入れる。ただし、これが1でない場合は No で終了。
  2. キューから頂点番号を取り出す。
  3. 数列で指定された順に、その頂点に隣接する頂点のうち未訪問のものをキューに入れる。このとき、指定された次の番号が隣接する頂点として取れない場合、順番が守れないので No で終了。
  4. 2に戻る。

これをキューが空になるまで完遂できれば Yes です。

本番では太字にしたところを完全に読み忘れていました。これでプレテスト通るのか…

ACコード

E. Trips

Problem - E - Codeforces

問題概要

n 人の人がいて、以下を m 回繰り返す。 m 回それぞれについて、2. の答えを出力せよ。

  1. 人 x_{i} と y_{i} が友達になる。（友達になるペアは毎回異なる）
  2. 「グループ内に少なくとも k 人友達がいる」を全員が満たしているようなグループを作る。そのうち最も人数の多いものを選び、その人数を出力する。

解法

友達がどんどん増える優しい世界ですが、これだと考えにくいので、時間を逆回しして友達がどんどん減っていく設定にします。（悲しいですね）

人を頂点、友達関係を辺とするグラフを考えます。まず最後の状態を考えるため、全ての辺を追加してしまいます。これ以降、辺が増えることはありません。このとき、

  1. 友達が k 人未満の人は、絶対にグループに入れないので除外する。
  2. 他の人が除外された結果、友達が k 人未満になってしまった人も除外する。

これを繰り返すと、最後に残った人たちは k 人以上友達がいるため、全員でグループを組むことができます。

あとは、時間を巻き戻すごとに辺が1つずつ消えていくので、その2人について上記の1. の判定を行い、2. の判定を伝播させていけばよいです。

どれだけ伝播するかで1回1回の判定回数にはばらつきがありますが、必ず「辺を切る」という操作を伴うため、問題全体での判定の合計回数は、高々辺の数の定数倍になります。

ACコード

F. Maximum Reduction

Problem - F - Codeforces

問題概要

ちょっと問題文の読解が難しいので図にします。

f:id:betrue12:20180904003852p:plain

要素数 n の数列と整数 k が与えられ、図のように「連続する k 要素の最大値」を取っていく操作を繰り返します。要素数が k 未満になったら操作終了です。

この図では n = 5, k = 3 です。（問題文中の2つ目のサンプル）

この操作でできる、2段目以降の数列の合計値を求めよ、という問題。

解法

この操作では、大きい数字がずっと残り続け、大きい数字の近くにある数字はmaxを取る時に消えていきます。

もちろん一番大きい数字は最後まで残るのですが、それ以外の数字になる場所だけを見てみましょう。

f:id:betrue12:20180904004501p:plain

最も大きい数字「9」以外の要素は、1段目4つ・2段目2つ。これは、「最初から1段目が左側の4要素しかなかったとしたら」と考えた時の、操作結果と全く同じになります。

一番大きい要素の位置が端っこでない場合はどうでしょうか。

f:id:betrue12:20180904005100p:plain

少しごちゃごちゃしていますが、一番大きい「9」で分断された左右が、やっぱりそれぞれ問題で与えられた操作結果と同じになっています。

ここから、「一番大きい数字で分断して再帰的に処理していく」という方針が立ちます。必要な道具は、

  1. 任意の区間内での数列の最大値と、その位置を効率的に取得する。
  2. その最大値が、2段目以降の数列全体で合計いくつ存在するかを効率的に求める。

の2つです。

1についてはセグメント木が使えます。値と位置をペアにして格納しておけば位置も取れます。

2についてですが、上図の「9」の配置なんかを見ると不規則に見えます。ので、ちょっと計算をサボって「一度全部のマスで足してしまって、残りを差分更新することで調整する」という方法を取ります。

f:id:betrue12:20180904010056p:plain

図のように差分で計算をしていけば、1度の計算で扱う範囲は3角形（場合によっては台形）のような形になり、等差数列の和の公式で数を求められます。

解法をまとめると、

  1. 区間内の最大値とその箇所をセグメント木で求める。
  2. 今考えている区間から発生する数列の要素数の合計を、等差数列の和の公式で求める。
  3. 個数×（今回の最大値 - 前回の最大値）を答えに加算する。
  4. 最大値の箇所で区間を分割し、再帰的に処理する。

これで解けます。

配点高めですが、類題の経験があったので意外とサクっと解けたような気がします。

ACコード

さいごに

f:id:betrue12:20180904011157p:plain

今回のコンテスト後のレートが1892。誤読しなければ紫になっていたと思うと虚しいですが…これもこどふぉ。問題はちゃんと読みましょう。

脚注

*1:元問題の記載では1円からですが、「袋を1つも選ばない＝0円」を含めたほうが説明の都合がよいのでそうしています。

AtCoder黄色になりました

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

昨日のARCで、黄色になることができました！

f:id:betrue12:20180902133514p:plain

パフォーマンス推移

f:id:betrue12:20180902131759p:plain

リンク

ratedのみ載せています。青になったときと同じく、+150くらい上がって一気に届いた感じです。

このARC102は300-700-700の3完です。700を2問解ければこのパフォーマンスが出る、というのは希望が持てるのではないでしょうか。今までは、1000点くらいの問題を解かないと届かないイメージだったので…

上がってしまったからにはこれを維持しなければ…というプレッシャーがありますね。まあでも青からも1回落ちていますし、落ちてもまた上がればよいので、気楽にいきます。

やったこと

問題を解いた

f:id:betrue12:20180902134850p:plain

リンク

AC数です。この中で個人的に重要だと思うのがARC-E（上の画像だとC）とAGC-Cで、黄色に届くためには

  • ARC-Eをそこそこの頻度で解く
  • AGC-Cを安定して解く
  • （ARC-DやAGC-Bを落とさない）

のどちらか、できれば両方が必要だと感じています。ただこれは配点にもよりますし、特にARC-Dが700点とかの異常難しい回は実質ARC-Eと同じ扱いです。

ただやっぱりARC-Eは難しくて、ARC-Dをほぼ埋め終わったくらいのレベルで挑むと返り討ちにあいます。まずは解けそうな問題から埋めていって（昔の問題とか楽なのもあるのでオススメです）、その後は

  • 解説ACをしていく
  • ARC/AGC以外の、企業コンを埋めていく
  • 問題を求めて他サイトに行く

あたりから選ぶのがいいかなと思います。

企業コンはけっこうオススメで、配点の割に難しい問題もありますが（400点で二部グラフとか…）、ARC/AGCとは少し違う知識が必要になります。いわゆる「ライブラリで殴れる」ような問題も多いので、埋めていくとちょっと高度なライブラリも充実していくんじゃないかと思います。

あとはまあ「知らないと思いつかない」ような解法がいっぱいあるので、解説ACも良いと思います。というか、解説読んでも分かりません。解説を読み込んで理解し、苦労してちゃんと通せば、類題やそれより少し易しめの問題が本番で出た時に解ける見込みが出てきます。

私は現時点で解説を読んだまま放置している問題がけっこうあるので、ちゃんと通していかないと。

Codeforcesを始めた

これは好みだと思います。私は単純にコンテストの場数が増えたので良かったなと思います。問題の傾向も少し違いますし。

海外サイトなので、英語を読めるかどうかでかなり効果が分かれるかなとは思います。競プロ以前に英語でつまづくと学習効率が下がってしまいますが…「ついでに英語の訓練を」という意識ならそれでもアリです。

AtCoderはコンテスト中に正解/不正解の確定結果が知らされる「フルフィードバック」方式ですが、Codeforcesは提出直後には一部のテストしか実行されず、他参加者から不正解ケースを指摘される「hack」やコンテスト終了後に改めて全てのテストが実行される「システムテスト」があります。サンプルもAtCoderに比べると不親切な傾向があるので、自力でコーナーケースを疑ったり、危なそうなテストケースを作って実行してみる必要があります。この能力は、方式の違うAtCoderでも損にはならないはずです。

C++を始めた

青になるまではRubyだけで戦ってきましたが、ARC-EあたりからRubyでは想定解でも通らない問題が出てきます。実質的に出題数が減るのと同じことなので、なかなかキツいです。

最近はPythonで競プロをやっている人も多いので、いずれ同じようにこの壁に当たると思います。このような時の選択肢は、

  1. 今の言語を使い続ける。
  2. 今の言語と高速な言語を併用する。
  3. 高速な言語に完全移行する。

になります（それはそう）

1は率直に言ってかなりストレスがあると思います。解法が分かっているのに通せない、これは私にとっては苦痛でした。当然、実力よりもレートの伸びは悪くなります。それを受け入れられるかどうか、だと思います。

2は今の私が取っている方法です。ちょっと面倒なので「慣れ」が必要だとは思います。ライブラリを2言語用意したり、コード提出欄の言語選択に気を遣ったり。まずは過去問から練習していくといいでしょう。今の言語に愛着があって使い続けたい人向け。

3は完全移行するまでが大変ですが、それ以降を考えると一番楽だと思います。新しい言語の経験を一番多く積めるのもこの選択肢です。

やはり強い人からは直接的または間接的に「速い言語を使うべき」という話がちらほら出て、少し肩身は狭いです。でも個人的にはスクリプト言語を使っている人は勝手に応援していて、青になるまではそのままでいいんじゃないかなとは思っています。それ以降、ぼちぼちどうするかを考え始めてもいいと思います。

用意したライブラリ

前回との差分でめぼしいものを挙げます。

  • グラフ
    • 最大フロー（最小カット、二部マッチングもここに含まれます）
    • 強連結成分分解、二重辺連結成分分解
  • データ構造
    • 重み付きUnion-Find、部分永続Union-Find
  • 文字列
    • Z-Algorithm（過去問で使ったのでそのまま保存）

意外と増えてない…？青になる前に用意しすぎたかもしれません。

多分セグメント木の派生とか、文字列まわりのアルゴリズムで足りてないものがあるので、使う問題に出会ったら順次作っていきます。

データ構造だとセグメント木やBIT、アルゴリズムだと最小全域木（クラスカル法）やLCAあたりは青までには使わなかったかもしれないので、作っていない場合は是非用意しておくと良いと思います。

知識や考え方については挙げていくとキリがないので…何か別の機会があれば書いてみたいなと思います。

さいごに

色が変わったというのも分かりやすい指標ではあるのですが、やはり問題を解けることが楽しいです。今まで手も足も出なかった問題に少しずつ太刀打ちできるようになっている、という実感があります。この調子でどこまで行けるか…自分の力で届くところまで行ってみたいです。

引き続きブログも続けていきます。私のブログを読んで理解して通せた、という声が励みになっています。これからもよろしくお願いします。

ARC102 参加記録

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

今回も前回に引き続きD問題が700点という、ABCには厳しい回でした…

結果は3完79分で30位…一気に黄色になりました！びっくりですね。highestパフォ400くらい更新しました。

f:id:betrue12:20180902001717p:plain

黄色になりました記事は別途書きます。この記事ではC～E問題を振り返っていきます。

C - Triangular Relationship

C - Triangular Relationship

解法

a, b, c について、 a+b, b+c, c+a が全て K の倍数でなければいけません。数値が3つあると考えにくいので、まずは1つにできないか考えましょう。

a+b, b+c, c+a から a だけの式を作ることを考えます。 (a+b) - (b+c) + (c+a) を計算すると結果は 2a になって、 a だけの式になります。

この値は K の倍数3つを足し引きしているものなので、やっぱり K の倍数です。つまり、 2a が K の倍数であるということが言えます。ここから、

  • K が偶数の場合、 a は K で割った余りが 0 または \frac{K}{2} でないといけない
  • K が奇数の場合、 a は K で割ったあまりが 0 でないといけない

ということが言えます。

これで、 a を K で割った余りは2通りまたは1通りに絞れました。 0 か \frac{K}{2} かで場合分けをして、 b, c も含めて問題の要求を満たす条件を明らかにしていきましょう。

  • a を K で割った余りが 0 の時…
    • (a+b) が K の倍数であるためには、 b を K で割った余りも 0 である必要がある。
    • 同様に (c+a) が K の倍数であるためには、 c を K で割った余りも 0 である必要がある。
    • b も c も K で割った余りが 0 であれば、 (b+c) も K の倍数となる。
  • a を K で割った余りが \frac{K}{2} の時…
    • (a+b) が K の倍数であるためには、 b を K で割った余りも \frac{K}{2} である必要がある。
    • 同様に (c+a) が K の倍数であるためには、 c を K で割った余りも \frac{K}{2} である必要がある。
    • b も c も K で割った余りが \frac{K}{2} であれば、 (b+c) も K の倍数となる。

書いてあることはほとんど同じになりますね。どちらの場合も、全ての数が共通の余りを持っている必要があります。ここから、以下のように解くことができます。

  1. N 以下の正の整数で K で割った余りが 0 になるものの数を数え、3乗する。
  2. K が偶数の場合は、 N 以下の正の整数で K で割った余りが \frac{K}{2} になるものの数を数えて3乗し、↑と加算する。

これで解けます。

ACコード

D - All Your Paths are Different Lengths

D - All Your Paths are Different Lengths

解法

俗に「構築」と呼ばれる、条件に満たす数列やグラフなどを何か1つ作れという問題。こういう問題では、サンプルの出力例はあまり期待しないほうがよくて*1、制約内の入力のうち何がきても、機械的に同じ手順で対応できるような「必勝法」を探すことが多いです。

さて、最も主要な条件は「頂点 1 から 頂点 N までの経路が L 通りあって、それらの長さが 0, ..., L-1 になっている」ということです。このように連続する自然数をもれなくダブりなく表現する方法として、10進数や2進数のような進数表記があります。

とりあえず2進数で考えてみます。そして、まずはキリ良く 2^{N-1} 通りの数を表すことを考えてみましょう。

f:id:betrue12:20180902013420p:plain

このように N 頂点のグラフを作ってみると、左端から右端までの経路は「4回の移動でそれぞれ上下どちらを通るか？」の組み合わせで 2^{4} = 16 通りです。そしてこれで、長さ 0, ..., 15 のパターンを綺麗に網羅しています。もし L が 2^{N-1} の形で表せるような数だったら、これが答えになりますね。

これを基本アイデアとして、端数を調整していくことを考えましょう。例えば L = 20 の場合は、長さ 0, ..., 15 を作った後、そこに長さ 16, 17, 18, 19 の経路を追加する必要があります。この経路は以下のように追加することができます。

f:id:betrue12:20180902014617p:plain

L = 22 の場合はどうでしょうか。追加したい経路が6個なので一度に追加することは難しいですが、 4+2と分ければ以下のように追加することができます。

f:id:betrue12:20180902014709p:plain

一般的に考えると、2進数で作った経路の途中までを見ると 2^{k} の経路ができていて、その長さが 0, ..., 2^{k}-1 になっているはずです。そこから適切な長さでゴール地点までのショートカットを作ると、好きな数字から始まる 2^{k} の連番が作れますね。これを良い感じに組み合わせていくと、作りたい長さまでの連番ができます。

最後に、頂点数と辺数について確認しておきます。*2

頂点数 N \le 20 だと2進数の桁を最大19個作ることができて、2進数19桁で表現できる数は 2^{19} 通りです。そこからショートカットを N 以外の全頂点から追加で1本ずつ伸ばすと、増える経路数はそれぞれ +2^{18}, +2^{17}, ..., 1 であり、最大で 2^{20} - 1 = 1048575 通りになります。 L \le 10^{6} （100万）なので頂点数は足りそうです。

辺数 M \le 60 については、 まず2進数19桁を作るのに38本。ショートカットを1本ずつ伸ばすと、追加が最大19本で合計57本。足りそうですね。

ACコード

E - Stop. Otherwise...

E - Stop. Otherwise...

解法

※実は要らないらしいのですが包除で解いたので包除で解説を書きます。

基礎知識

まず今回の問題を解くには、「 K 個のものから、重複を許して計 N 個選ぶ時の組み合わせ」の数え方が必要です。*3

これは重複組合せ と呼ばれていて、 _{K}H_{N} と記載することもあります。その総数は公式として有名で、通常の組み合わせの記号を使うと _{K+N-1}C_{N} 通りとなります。

あとは包除原理。一般には、「または」の計算を「かつ」の結果の足し算引き算だけで求めることができるという原理です。

そのまま使うこともありますし、問題では「どの～も○○でない」という「かつ」型の条件が与えられていて、そのままだと考えにくいので条件を反転して「または」型の条件にしてから包除原理を使うこともあります。今回の問題はそのタイプです。

考察

どの2つのサイコロの和も i にならない、という条件をいくつか書き下してみましょう。

  • 和が2にならない。
    • 1と1の組み合わせが作れない。つまり、1の数が0～1個。
  • 和が3にならない。
    • 1と2の組み合わせが作れない。つまり、1と2の少なくとも片方が0個。
  • 和が4にならない。
    • 2の数が0個～1個。
    • 1と3の少なくとも片方が0個。
  • 和が5にならない。
    • 1と4の少なくとも片方が0個。
    • 2と3の少なくとも片方が0個。

こんな感じになります。

これを一般化してみると、 i それぞれについて、問題の要求は以下のような条件になります。

  • 同一数のペアによる条件（ i が偶数のときのみ）
    • ある1つの出目 \frac{i}{2} について、その個数は0～1個である。
  • 異なる数のペアによる条件
    • ある M 個の出目のペアについて、そのうち少なくとも片方は0個である。

（これらの数やペアには、重複して含まれる出目がない、ということも大事です。）

少なくとも片方が0個である必要がある、揃ってはいけないペアのことを「NGペア」と書くことにします。それぞれの i についてのNGペアの個数 M は、面数 K=6 とかで書き下してみるとなんとなく法則が分かると思います。

i が奇数の場合のほうが条件が少ないので、まずは奇数の場合を考えます。

i が奇数の場合

「 M 個のNGペアのうち m 個を固定した時、それらが全て存在しているような場合の数」というのを考えます。残りのペアについては、存在しているかどうかは不問です。これを全ての m について求めると、包除原理でNGペアが0個の時の場合の数が求められます。

この固定したペアの出目は必ず存在するので、まず出目にサイコロを1個ずつ割り当てます。残ったサイコロは N - 2m 個です。

最後に、残ったサイコロは 1, ..., K のどの目になってもよいので、 K 個の出目から N-2m 個を選ぶ重複組合せを数えます。この過程で、新しいNGペアができたり、固定したNGペアがさらに増えたり、NGペアが全く増えなかったりしますが、これらは分けて考える必要がありません。これはとても便利で、包除原理を使ってまで条件を言い換える最大のメリットになります。

f:id:betrue12:20180902024230p:plain

このように計算すると、「 M 個のNGペアのうち m 個を固定した時、それらが両方存在しているような場合の数」は _{K}H_{N-2m} です。

m 個のペアの選び方は _{M}C_{m} 通りなので、これらをまとめると

_{M}C_{m} \times _{K}H_{N-2m}

となり、この値を包除原理に基づいて足し引きしていけば、答えが求められます。

i が偶数の場合

i が偶数の場合は同一数のペアによる条件があって、具体的には出目が \frac{i}{2} のサイコロの個数が0～1個でなければいけません。

というわけで、0個か1個かで場合分けをします。同一数のペアによる条件を処理してしまえば、あとは奇数の場合と同じように考えることができます。出目が1つ使えなくなることに注意してください。

  • 出目が \frac{i}{2} のサイコロが0個の場合
    • サイコロの出目の総数が K-1 個、サイコロが N 個として、奇数の場合と同様に考えられる。
  • 出目が \frac{i}{2} のサイコロが1個の場合
    • サイコロの出目の総数が K-1 個、サイコロが N-1 個として、奇数の場合と同様に考えられる。

これを両方計算して、合計すればよいです。

ACコード

さいごに

700点問題が本番で通るようになってきたのは本当に嬉しいです。実際、500～800点くらいの過去問をけっこう解いてきたので、その成果が出ていると思います。

次の記事は「AtCoder黄色になりました」の予定です！

脚注

*1:本来の解法を隠すために、わざと不規則な例になっていることも多いです。

*2:今回は説明の流れを切らないために、最後に制約確認をしましたが、実際にはアイデアの骨子が浮かんだ段階で「足りそうか？」というのを考えるほうが良いとは思います。これで足りない場合、2進数から別のn進数に考え直してみるか、節約の方法を考えるか、全く別のアプローチを考えるか、になると思います。

*3:今回の問題と記号を合わせています。リンク先のWikipediaと逆なので注意。

Summer Festival Contest 2018 参加記録

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

Summer Festival Contest 2018 (Division 1) - AtCoder

結果は2完で7位でした。D問題の最速ACも取れちゃいました。

f:id:betrue12:20180826135558p:plain

DとEを振り返ります。

D - 木からパスへ (Tree--->path)

D - 木からパスへ (Tree--->path)

解法

問題の操作は、以下のように考えることができます。

  1. 与えられた木の辺を切断して、頂点を共有しないいくつかのパスに分解する。頂点は全てどこかのパスに含まれる。孤立した頂点（1頂点0辺の集合）もパスとみなす。
  2. 与えられたパス群を、パス数-1個の頂点を追加することで連結させる。

そのため、1. のパス分解において、なるべく少ない個数のパスに分解する方法を考えます。

何となく、長いパスで多くの頂点を巻き込んだほうが得なようにも見えますが、それは正しくありません。極端な例を挙げます。

f:id:betrue12:20180826141627p:plain

図のように、なるべく近いところでパスを作っていくほうが、他のパスを邪魔しなくてよいです。

このようにパスを作っていくため、与えられた木を根付き木として考えます。なるべく深いところ同士でパスを完結させてしまおう、という考えです。木DPのように深いところから見ていって、以下のようにパスを作っていきます。

f:id:betrue12:20180826143125p:plain

これを最深部から根まで行えば、全頂点を網羅するパスができているはずです。作られたパスの数-1が答えです。

ACコード

E - 石積み (Pyramid Piling)

E - 石積み (Pyramid Piling)

解法

この問題はまず「長さ s の n 次元三角数がどんな値になるか？」を把握する必要があります。2次元の \frac{s(s+1)}{2} 、3次元の \frac{s(s+1)(s+2)}{6} あたりが知識としてあると、 \frac{s(s+1)\cdots(s+n-1)}{n!} あたりになりそうだなあ…という予測は立ちますが、ちゃんと考えます。

問題文の定義より、「 x_{i} \ge 0 かつ x_{1} + ... + x_{n} \lt s が成り立つ整数 (x_{1}, ..., x_{n}) の組」の数を考えます。これは「マルと仕切りを並べる順列」で考えることができます。

f:id:betrue12:20180826152122p:plain

上記の考え方により、条件を満たす整数の組は _{n+s-1}C_{n} 通りです。これは先ほどの予測の式と一致しています。

三角数の一般式が得られたところで、問題を解いていきましょう。求めたい解は、

\frac{s_{1}\cdots(s_{1}+N-1)}{N!} = \frac{s_{2}\cdots(s_{2}+N-2)}{(N-1)!}

を満たす s_{1}, s_{2} であり、分母を払うと

s_{1}\cdots(s_{1}+N-1) = s_{2}\cdots(s_{2}+N-2) \times N

となります。左辺は連続する整数 N-1 個の積、右辺は連続する整数 N-2 個の積 \times N です。要素数が同じなので、上手く対応付けられそうです。

  • s_{1} = N
  • s_{1} + 1 = s_{2}
  • ...
  • s_{1} + N - 1 = s_{2} + N -2

を満たすように対応付けられれば良くて、これを満たすものは s_{1} = N, s_{2} = N+1 となります。これは解として正当です。

※ s_{1} = s_{2} = 1 も式を満たすのですが、問題で s_{1} \ne s_{2} が要求されているのでこれはNGです。

ACコード

（Ruby）Submission #3069695 - Summer Festival Contest 2018 (Division 1)

なお私の場合、すぐこの解にたどり着いたわけではなく、一度地道に探索するコードを書いて、その結果から規則性に気付いています。地道コードのほうもせっかくなので提出してリンクを貼っておきます。小さい入力値でしか動かないので当然ACにはならないのですが、このようなコードを一度書いて実行してみると気付きが得られるかもしれません。