ARMERIA

放置していたけど更新再開、Rubyと競技プログラミングの話が中心になっていく予定です

Codeforces Round #503 参加記録

Dashboard - Codeforces Round #503 (by SIS, Div. 2) - Codeforces

今回は3完、配点の高いD問題が通せたのでdiv2で74位!レートもめっちゃ上がりました。

f:id:betrue12:20180812133607p:plain

A~Dの4問を振り返ります。

A. New Building for SIS

Problem - A - Codeforces

横に並んだビルがあり、各ビルでは上下の階に移動できる他、  A 階以上  B 階以下のフロアには渡り廊下があってビル間を移動できます。それ以外の階ではビル間の移動ができません。与えられる2地点(どのビルの何階か)の間を移動するためにかかる移動回数を求めよ、という問題。

頑張って問題を読んで、落ち着いてパターンを網羅します。以下の4パターンになります。

f:id:betrue12:20180812135716p:plain

Submission #41472505 - Codeforces

本番では「同じビルかどうか」の考慮を忘れて1WA…

B. Badge

Problem - B - Codeforces

 n 人の全ての生徒について、「指名された時、次に誰を指名するか」が決まっています。その指名先をずっと辿っていくと、必ず「2回指名された生徒」が出ます。全ての生徒について、「その生徒を最初に指名したとき、最初に2回指名されるのは誰か」を求めよ、という問題。

ある生徒を最初に指名して、愚直に指名先を辿っていくことを考えます。このとき、誰かが2回指名されるまでのステップ数は高々生徒の人数しかありません。そのため、全生徒についてこれを普通に繰り返しても  O(n^{2}) で終わります。 n \le 1000 なのでこれで通るでしょう。

Codeforces

Rubyで100万、こどふぉで制限時間1秒だと怖いので一応C++で書きました。(後で提出してみたら問題なく通りました

C. Elections

Problem - C - Codeforces

選挙の投票人と投票先の政党がいて、各投票人について「どの政党に投票するか」「いくら賄賂を渡せば投票先を変えてくれるか」が与えられます。政党1を単独1位にするために必要な賄賂の最小金額を求めよ、という問題。

方針として、「賄賂の少ない投票人から買収していけば良さそう」というのと、「票数の多い政党から削れば単独1位になるためのボーダーを下げられそう」という2つが思いつきます。これを同時に考えるのは難しいので、「政党1が票数  i を得て勝つ」ために必要な賄賂合計を求めることにします。

政党1の目標票数を固定すれば、

  1. まず、政党1の目標票数以上を得ている対抗馬の票を削る必要がある。それらの政党に投票している投票人を安い方から必要数買収する。
  2. その後、目標票数に届くまで、政党1以外に投票している人のうち1.で買収していない投票人を安い方から買収する。

という処理が可能です。

計算量が怖いですが、ソートは前計算で全部できるので、ざっくり見積もって  O(n(n+m)) くらいだと思います*1 n, m \le 3000 なので、制限時間2秒でC++なら十分でしょう。

Submission #41501142 - Codeforces

本番中は、「支持政党ごとの賄賂額ソート(1.の処理用)」と「ごちゃまぜ状態での賄賂額ソート(2.の処理用)」を用意して、後者のソートを書き忘れる…という何ともつまらないミスで通せず。ただ、これをすっぱり諦めてDに向かったのは良かったのかな…?

D. The hat

Problem - D - Codeforces

偶数人数の人が円状に並んでいて、「隣り合った人が持っている数字の差は1」という条件を満たした数字をそれぞれ持っています。ちょうど対面に座っていて同じ数字を持っているペアを1つ見つけるか、そんなペアがいないということを判定してください、という問題。

インタラクティブ問題で、人数が  n \le 100000 、「 i 番目にいる人が持っている数字はいくつですか」というクエリを60回投げることができます。クエリ回数を  O(\log n) くらいにしないと足りない感じです。

まず、ある対面の2人についてクエリを発行し数字を得ます。それが等しければそのまま出力して終了ですが、そうでない場合は、以下のように考えることができます。

f:id:betrue12:20180812145400p:plain

その対面の点から、両方時計回りにそれぞれ1人ずつ見ていくことを考えます。その推移を2本の折れ線グラフとして描くと、始点と終点が入れ替わっていることから、これらは少なくとも1点で交わっているはずです。この交わっているところに人がいれば、そこが解になります。

ではこの交わっている点が絶対に解になるかというと、そうではありません。グラフ上は「2.5」みたいな値で交わっているかもしれないからです。この場合、すれ違う格好になり、人がいるところ(整数の点)では数字が一致しません。

これを判別するために、偶奇を考えます。もし向かい合ったペア1組の偶奇が一致していない場合。その1つ隣のペアを見ると、差が1であることから偶数は奇数に、奇数は偶数になります。ということは隣のペアの偶奇も一致しません。これを繰り返して、全てのペアの偶奇が一致しなくなります。これは「偶奇が一致する」に置き換えても同様です。

向かいあったペアの数字の偶奇が一致していれば、折れ線グラフの交点が解になりますし、そうでない場合は絶対にすれ違うので解無しです。実はこれは「総人数  n が4の倍数かどうか」に対応しています。

では、偶奇が一致して解が必ず存在する場合を考えましょう。さきほど考えたように、もし2本の折れ線グラフが交点を持つ十分条件は、始点と終点で大小が入れ替わっていることです。そのため、二分探索で解の存在範囲を絞り込むことができます。

f:id:betrue12:20180812152117p:plain

それぞれの区間の真ん中の点についてクエリを発行します。これが同じ値でしたら解を発見したことになります。そうでない場合、どちらか片方の区間では大小が入れ替わっているはずなので、そちらに絞って探索を続けます。

これを繰り返すと  O(\log n) 、具体的には最大で  2 \times \lceil\log_{2} 100000\rceil = 34 回ほどで解が見つかるのではないかと思います。

Submission #41492428 - Codeforces

余談ですが、この問題で使った「数直線上の2点が同時に±1ずつ動くときに、偶奇が一致していれば、交差したときに同じ座標を共有する」という考え方は、以下の問題から連想しました。

A - 迷子の高橋君 / Takahashi is Missing!

さいごに

Cが凡ミスで通せなかったのは良くないですが…配点の高いDが解けたのでかなり良い順位が取れました。目指せ紫!

脚注

*1:n < m のときは得票数がゼロの政党があるということなので、その政党を無視してしまえることを考えると O(n2) で良い気がします。