Codeforces Round #503 参加記録
Dashboard - Codeforces Round #503 (by SIS, Div. 2) - Codeforces
今回は3完、配点の高いD問題が通せたのでdiv2で74位!レートもめっちゃ上がりました。
A~Dの4問を振り返ります。
A. New Building for SIS
横に並んだビルがあり、各ビルでは上下の階に移動できる他、 階以上 階以下のフロアには渡り廊下があってビル間を移動できます。それ以外の階ではビル間の移動ができません。与えられる2地点(どのビルの何階か)の間を移動するためにかかる移動回数を求めよ、という問題。
頑張って問題を読んで、落ち着いてパターンを網羅します。以下の4パターンになります。
Submission #41472505 - Codeforces
本番では「同じビルかどうか」の考慮を忘れて1WA…
B. Badge
人の全ての生徒について、「指名された時、次に誰を指名するか」が決まっています。その指名先をずっと辿っていくと、必ず「2回指名された生徒」が出ます。全ての生徒について、「その生徒を最初に指名したとき、最初に2回指名されるのは誰か」を求めよ、という問題。
ある生徒を最初に指名して、愚直に指名先を辿っていくことを考えます。このとき、誰かが2回指名されるまでのステップ数は高々生徒の人数しかありません。そのため、全生徒についてこれを普通に繰り返しても で終わります。 なのでこれで通るでしょう。
Rubyで100万、こどふぉで制限時間1秒だと怖いので一応C++で書きました。(後で提出してみたら問題なく通りました)
C. Elections
選挙の投票人と投票先の政党がいて、各投票人について「どの政党に投票するか」「いくら賄賂を渡せば投票先を変えてくれるか」が与えられます。政党1を単独1位にするために必要な賄賂の最小金額を求めよ、という問題。
方針として、「賄賂の少ない投票人から買収していけば良さそう」というのと、「票数の多い政党から削れば単独1位になるためのボーダーを下げられそう」という2つが思いつきます。これを同時に考えるのは難しいので、「政党1が票数 を得て勝つ」ために必要な賄賂合計を求めることにします。
政党1の目標票数を固定すれば、
- まず、政党1の目標票数以上を得ている対抗馬の票を削る必要がある。それらの政党に投票している投票人を安い方から必要数買収する。
- その後、目標票数に届くまで、政党1以外に投票している人のうち1.で買収していない投票人を安い方から買収する。
という処理が可能です。
計算量が怖いですが、ソートは前計算で全部できるので、ざっくり見積もって くらいだと思います*1。 なので、制限時間2秒でC++なら十分でしょう。
Submission #41501142 - Codeforces
本番中は、「支持政党ごとの賄賂額ソート(1.の処理用)」と「ごちゃまぜ状態での賄賂額ソート(2.の処理用)」を用意して、後者のソートを書き忘れる…という何ともつまらないミスで通せず。ただ、これをすっぱり諦めてDに向かったのは良かったのかな…?
D. The hat
偶数人数の人が円状に並んでいて、「隣り合った人が持っている数字の差は1」という条件を満たした数字をそれぞれ持っています。ちょうど対面に座っていて同じ数字を持っているペアを1つ見つけるか、そんなペアがいないということを判定してください、という問題。
インタラクティブ問題で、人数が 、「 番目にいる人が持っている数字はいくつですか」というクエリを60回投げることができます。クエリ回数を くらいにしないと足りない感じです。
まず、ある対面の2人についてクエリを発行し数字を得ます。それが等しければそのまま出力して終了ですが、そうでない場合は、以下のように考えることができます。
その対面の点から、両方時計回りにそれぞれ1人ずつ見ていくことを考えます。その推移を2本の折れ線グラフとして描くと、始点と終点が入れ替わっていることから、これらは少なくとも1点で交わっているはずです。この交わっているところに人がいれば、そこが解になります。
ではこの交わっている点が絶対に解になるかというと、そうではありません。グラフ上は「2.5」みたいな値で交わっているかもしれないからです。この場合、すれ違う格好になり、人がいるところ(整数の点)では数字が一致しません。
これを判別するために、偶奇を考えます。もし向かい合ったペア1組の偶奇が一致していない場合。その1つ隣のペアを見ると、差が1であることから偶数は奇数に、奇数は偶数になります。ということは隣のペアの偶奇も一致しません。これを繰り返して、全てのペアの偶奇が一致しなくなります。これは「偶奇が一致する」に置き換えても同様です。
向かいあったペアの数字の偶奇が一致していれば、折れ線グラフの交点が解になりますし、そうでない場合は絶対にすれ違うので解無しです。実はこれは「総人数 が4の倍数かどうか」に対応しています。
では、偶奇が一致して解が必ず存在する場合を考えましょう。さきほど考えたように、もし2本の折れ線グラフが交点を持つ十分条件は、始点と終点で大小が入れ替わっていることです。そのため、二分探索で解の存在範囲を絞り込むことができます。
それぞれの区間の真ん中の点についてクエリを発行します。これが同じ値でしたら解を発見したことになります。そうでない場合、どちらか片方の区間では大小が入れ替わっているはずなので、そちらに絞って探索を続けます。
これを繰り返すと 、具体的には最大で 回ほどで解が見つかるのではないかと思います。
Submission #41492428 - Codeforces
余談ですが、この問題で使った「数直線上の2点が同時に±1ずつ動くときに、偶奇が一致していれば、交差したときに同じ座標を共有する」という考え方は、以下の問題から連想しました。
A - 迷子の高橋君 / Takahashi is Missing!
さいごに
Cが凡ミスで通せなかったのは良くないですが…配点の高いDが解けたのでかなり良い順位が取れました。目指せ紫!
脚注
*1:n < m のときは得票数がゼロの政党があるということなので、その政党を無視してしまえることを考えると O(n2) で良い気がします。