ARMERIA

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

Codeforces Round #509 参加記録

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

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

いつもとは違い、（日本基準で）健康的な時間に開催されたこどふぉ。

結果はなんと全完！こどふぉでは全Division通して初めての全完です。TLEとかWAとかが怖い問題もいくつかあったので、運も良かったですね。

f:id:betrue12:20180917001948p:plain

大変ですが6問全部書きます。

A. Heist

Problem - A - Codeforces

問題概要

n 個の整数 a_{1}, ..., a_{n} が与えられる。これはある長さの連続した整数列から、いくつかの要素を抜き取って並び替えたものである。「抜き取った個数」の最小値を求めよ。

制約

  • 1 \le n \le 1000
  • 1 \le a_{i} \le 10^{9} であり、これらは相異なる

解法

与えられた整数のうち、数字が飛んでいるところは必ず「抜き取られて」いるので、これらを数えます。具体的には a_{i} の最大値-最小値+1から n を引けばよいです。

ACコード

B. Buying a TV Set

Problem - B - Codeforces

問題概要

整数 a, b, x, y が与えられる。正整数の組 (w, h) で、以下の満たすものの個数を求めよ。

  • w \le a
  • h \le b
  • \frac{w}{h} = \frac{x}{y}

制約

  • 1 \le a, b, x, y \le 10^{18}

解法

まず、 x, y をこの2数の最大公約数で割って、既約にしておきます。条件には x, y の比しか出てこないので、この操作をすることは問題ありません。

x, y を既約にすると、 \frac{w}{h} = \frac{x}{y} を満たす正整数の組 (w, h) は 正整数 k を用いて (kx, ky) と表せます。

あとは上限を超えない k の取り方を数えれば良いので、割り算すれば求められます。

ACコード

C. Coffee Break

Problem - C - Codeforces

問題概要

n 個の整数 a_{1}, ..., a_{n} が与えられ、それらは m 以下である。これらの整数を下記の条件を満たすようにグループ分けするとき、そのグループ数の最小値を求めて、最小になるグループ分けの方法を1つ構成せよ。

  • グループ内の任意の2つの要素 b, c について、 |b-c| \lt d が成立する。

※問題文の読解がとてもつらくて、上記の文章は簡素化しすぎて原型を留めていません…

制約

  • 1 \le n \le 2\times 10^{5}
  • n \le m \le 10^{9}
  • 1 \le d \le m
  • 1 \le a_{i} \le m でありこれらは相異なる

解法

要素をソートして、小さいものから順番にグループを割り当てていきます。

今まで作ったグループそれぞれについて、「そのグループで最後に追加した要素」を持っておきます。新しい要素を追加するとき、グループの最後の要素 c との間に a_{i}-c \lt d の関係が成立していれば、そのグループに要素を加えることができます。

新しい要素を順に見ていって、どこかのグループにその要素を追加できるのであれば、そのグループに要素を追加します。どこにも追加できない場合、仕方がないので新しいグループを作ります。こうするとグループ数をできるだけ小さくすることができます。

要素を追加できるグループが複数あるとき、どこのグループに要素を追加するかは関係ありません。新しく見る要素はどんどん大きくなっていくので、もう既に a_{i}-c \lt d が成立している要素 c たちは区別する必要がないからです。

なので、単に「最後に追加した要素が最も小さいグループ」をピックアップして、追加できるかどうか判定すればよいです。これは優先度付きキューなどに「最後に追加した要素の値とグループ番号のペア」を格納して小さい順に取り出していけば実装できます。

ACコード

D. Glider

Problem - D - Codeforces

問題概要

※問題ページに図があり、そちらを見たほうが分かりやすいです。

xy 平面をグライダーが飛行する。 x 座標において n 個の区間 [x_{i1}, x_{i2}] が存在し、それらの区間には上昇気流がある。これらの区間は交わらない。

初期位置の y 座標を h 、 x 座標を好きに選んだ値として、グライダーを x 軸の正の方向に飛ばす。グライダーは以下のように飛ぶ。

  • 上昇気流の区間内にグライダーが存在するとき、 y 座標は変化しない。
  • そうでないとき、 x 座標が1増加するたびに y 座標が1減少する。

グライダーの y 座標が0になるまでの x 座標の移動距離の最大値を求めよ。

制約

  • 1 \le n \le 2\times 10^{5}
  • 1 \le h \le 10^{9}
  • 1 \le x_{i1} \lt x_{i2} \le 10^{9} であり、これらの区間は交わらない。また、昇順に与えられる。

解法

まず、グライダーの開始地点は上昇気流の区間の開始位置にするのがよいです。途中から始めると、そのすぐ後ろにある上昇気流の区間が無駄になります。

ある上昇気流の開始位置から飛び始めたとき、どこまで飛べるかを求めたいです。このとき、開始位置以降に存在する「上昇気流がない区間」を、どこまで着地せずに通過できるか？と考えるとよいです。上昇気流がない区間を飛んだ長さと同じだけ高度が下がっていくので、上昇気流がない区間の長さの合計が h 未満であれば、着地せずに飛ぶことができます。

つまりグライダーの飛び方は以下のようになります。

  1. ある上昇気流区間の開始位置からスタートする。
  2. 上昇気流がない区間を、その長さの合計が h 未満である限り通過する。
  3. その次の上昇気流区間を通過する。
  4. その次の上昇気流がない区間で、力尽きて着地する。

開始位置の上昇気流を左から右に全探索します。そうすると通過可能な「上昇気流がない区間」の右端も、左から右に移っていきます。このような性質が成り立つ場合は、しゃくとり法で効率的に計算することができます。

ACコード

E. Tree Reconstruction

Problem - E - Codeforces

問題概要

以下の条件を満たす n 頂点の木を構築するか、それが不可能であることを判定せよ。

  • n-1 本の辺それぞれについて、整数 a_{i}, b_{i} が与えられる。その辺で木を切断したとき、2つの部分木のうちで最大の頂点番号がそれぞれ a_{i}, b_{i} となる。

制約

  • 2 \le n \le 1000
  • 1 \le a_{i} \lt b_{i} \le n

解法

まず、明らかに不可能になるケースがあり、それは b_{i} \lt N となる辺が1つでも存在したときです。2つに分けた時、少なくとも片方には番号最大の頂点 N が含まれているはずです。

そうでない場合、最大でない頂点番号 v=1, ..., N-1 について、 a_{i} = v となる辺がいくつあるかを数えます。その数を元に、以下のように木を構築します。

  • a_{i} = v である辺が1つであるとき、その頂点は頂点 N に直接接続する。
  • a_{i} = v である辺が k 個（ k \ge 2 ）あるとき、頂点 v と頂点 N の間に、頂点番号が v より小さい頂点を k-1 個挟む。
  • a_{i} = v である辺が1つもない頂点は↑で間に挟むために使う。

「間に挟む」というのは、具体的には以下のようにします。 v より番号を小さい頂点を k-1 個挟むと、その間の辺 k 本全てについて、部分木が条件を満たします。 v より番号が大きい頂点を挟んでしまうとNGです。

f:id:betrue12:20180917005940p:plain

この構成方法が不可能である場合は、多分どうやっても条件を満たす木が構築できないとは思うのですが…ちゃんと証明はしていません。この構成方法に限らず、より一般的な議論で「 a_{i} = vであるような辺が複数あるとき、間に挟める頂点があるか？」という考察を軸にして証明するのかなあ、とは思います。

ACコード

F. Ray in the tube

Problem - F - Codeforces

問題概要

※これも問題ページに図があるのでそれを見たほうが分かりやすいです。

横に伸びる管がある。管の伸びている方向を x 座標軸とみなす。

管の下側と上側のいくつかの位置にセンサがある。これらは全て整数座標で表される。下側のセンサは n 個で座標は a_{1}, ..., a_{n} 、上側のセンサは m 個で座標は b_{1}, ..., b_{m} である。

管の下側と上側それぞれ整数座標点を1つ選び、下側の点から上側の点に向けてレーザーを撃つ。レーザーは管の中を反射して進み、いくつかのセンサに当たる。

レーザーが当たる座標点の最大数を求めよ。

制約

  • 1 \le n, m \le 10^{5}
  • 0 \le a_{i}, b_{i} \le 10^{9}

※実際には管の上側と下側の y 座標が与えられているのですが、使わないので（！？）記載していません。

解法

これ、選ぶ座標点が有理数OKだとかなりキツくなりますが、整数座標限定なのでまだ解けます。

まず、レーザーを真上に撃つケースを考えます。この場合、上下で座標が同じ点にヒットし、延々とその間を反射し続けることになります。上下で座標が同じ点が存在すれば2、そうでない場合は1が最適です。

次に斜めに撃つケースを考えます。一番細かい間隔でレーザーを打てるのは、上下で座標が1ずれた点にレーザーを撃ったときです。

次に、座標が3ずれた点に撃ってみます。そうすると通る点は、1ずれたケースの下位互換になってしまいます。

f:id:betrue12:20180917012643p:plain

このように、他のケースの下位互換になるようなケースは考えなくて良いです。そうすると、3, 5, 7, ...は1の下位互換に、6, 10, 14, ...は2の下位互換に、といったようになり、結果的にずれ方が 2^{k} の場合だけを考えればよいことになります。ここまで絞れば、最大でも全部で \log_2(10^{9}) くらいのケースを試せばよいので効率的です。

ずれ方が決まれば、あとは各要素について余りを求めて、対応するものを足し合わせます。例えばずれ方が2の場合は、4で割った余りが上と下で2異なるものが対応します。割る数が大きい場合は余りが取りうる値が大きくなるのでmap等を使うことになります。

※ちょっと問題の記述が足りないかな？と思うところはあって、「真上に撃てるのか？」もそうですが、センサの座標が相異なるのかどうか（上下左右含めてまったく同じ位置にセンサがあるのかどうか）も明記されていないように思います。実際、 a_{1} = 1, b_{1} = b_{2} = 1 という入力が許されるなら解は3になるはずですが、Editorialのコードだとこれは2を返します。ちょっともやっとする問題でした。

ACコード

さいごに

今回のレート上昇で薄橙になりました！

f:id:betrue12:20180917015037p:plain

一番上にちょっとだけ見えてる次の色が橙っぽいので、今の色は薄橙ですかね。皆さんはどう呼んでるんだろうか。

現行ルールだと、この色からDiv2単独開催もunratedになります。色落ちしない限りはDiv1で戦い続けることになるんですね…Div2単独も出ますけど。