Codeforces Round #412 (rated, Div. 2, base on VK Cup 2017 Round 3)
参加しました。今回はあのtouristが作問ということだそうです。
touristは競プロが一番強い人ですね。こどふぉやAtcoderでも1位にいるので意識していなくても覚えてしまいます。
結果はABCの3完でした。Cは割と解けてる人が少な目で、これを解けたのは嬉しかったです。レートも上がって青になりました。
ただAで問題をあまり理解できておらずミスしたり、CはCでちゃんと解けてるのにしょうもないミスで1WAしたりしてしまったのはちょっともったいなかったですかね。
Dは終わった直後は「もう少し時間あれば通せてたのに」と思ってましたが、嘘解法だったので時間あってもダメでした。
A.xo
B.o
C.xo
D.-
A. Is it rated?
問題概要
ある参加者のレートが直前と直後で変化していれば、そのコンテストはratedである。
また、もしコンテストがratedであり、かつより低いレートの参加者がより高いレートの参加者より上位になったならば、少なくとも１人のレートが変動する。
今あるコンテストが開催された。そのコンテスト直前のレートと直後のレートが、そのコンテストの上位者から順に与えられる。
上の仮定の下で、そのコンテストがratedであったか、unratedであったかを判定せよ。判定出来ない場合はmaybeと出力せよ。
考えたこと
愚直に１つずつ条件を確かめていけばよいです。
- １人でもレートが変動していれば、rated
- １人もレートの変動が無い場合、もしより低いレートの参加者がより高いレートの参加者より上位になっていれば、unratedでなければならない（このことは２番目の条件の対偶を取ると分かる）
- １人もレートの変動が無く、かつ上位から順にレートが降順（非昇順）に並んでいる場合、そのコンテストがratedであるかunratedであるかを問題文の仮定から判定することは不可能なのでmaybeとする
私は最初へんてこなコードを書いてしまったので1WAしてしまいました。
しっかりと条件をまとめられれば特に難しい問題ではなかったはずです。私は何となく、で書いてしまいましたが……。
import sys def solve(): n = int(sys.stdin.readline()) rats = [0]*n for i in range(n): ai, bi = map(int, sys.stdin.readline().split()) if ai != bi: print('rated') return rats[i] = ai for i in range(n - 1): if rats[i] < rats[i + 1]: print('unrated') return print('maybe') if __name__ == '__main__': solve()
B. T-Shirt Hunt
問題概要
Codecraft-17のコンテストが最近ありました。このコンテストの上位25人と、26 ~ 500位のなかからランダムに選ばれた25人の計50人にこどふぉのTシャツがプレゼントされます。
あなたは残念ながら25位以内には入れませんでしたが、p(26 <= p <= 500)位になれたので、Tシャツがもらえる可能性はあります。
そして今、the elimination round of 8VC Venture Cup 2017が行われています。
Tシャツのランダム25人はこのコンテストでの優勝者のスコアをsとして、以下の疑似コードで列挙される25人に与えられることになりました。
i := (s div 50) mod 475
repeat 25 times:
i := (i * 96 + 42) mod 475
print (26 + i)ここで、列挙される数字は26 ~ 500であり、かつ列挙される数字に重複は無いことが保証されています。
さて、あなたは今the elimination round of 8VC Venture Cup 2017でx点を持っており、現在トップです。
また、あなたはy(<= x)点以上あれば、このコンテストで優勝できると確信しています。
あなたはハックに成功すると+100点でき、またハックに失敗すると-50点でき、と点数を調整することができます。
このコンテストに優勝し、かつTシャツをもらうために必要な成功ハッキングの最小回数を求めてください。
なお入力で与えられるケースは必ずそのような解があることが保証されています。
考えたこと
まず、問題の読解に非常に手間取りました。今はやっとちゃんと理解できてますが、コンテスト中はcodecraftと8VC~のコンテストが別でpはcodecraftの順位でっていうのが全く分かってなく混乱してました。
それでも例を見て何となく何をすればいいかは分かって、これは総当たりをすればいいですね。
まず点数を50点刻みでy以上の値ギリギリまで減らしていき、そのたび疑似コードの通りに25人列挙してその中にpがあるかを確かめていきます。
もしこの過程でpが見つかれば、ハッキングに成功する必要は全く無いので0回になります。
そして、減らしていく方法で見つからなければ、次は50点刻みでxから増やしていってまた同じようなことをします。
50点刻みで変動させていくのでそのたびに疑似コードのiの初期値が1ずつ変化するので、高々475回やれば全ての初期値を試したことになりますから、計算量的には余裕です。
あんまりギリギリでやるのも怖いので、実際はもうちょっと余裕持たせたほうがよかったかもしれません（1000回とか）
import sys inf = 1<<60 def solve(): p, x, y = map(int, input().split()) for s in range(x, y - 1, -50): if p in list_tshirt(s): print(0) return for i in range(1, 476): s = x + i*50 if p in list_tshirt(s): print((i + 1) // 2) return def list_tshirt(s): res = [0]*25 i = (s // 50) % 475 for k in range(25): i = (i*96 + 42) % 475 res[k] = i + 26 return res if __name__ == '__main__': solve()
リストアップして、そのなかにpがあるかを確かめるのはsetでやったほうがいいですね。
C. Success Rate
問題概要
今日あなたはこどふぉでy回submitして、そのうちx回ACしました。このときAC率はx/yと表せます。
あなたには0以上1以下の好きな有理数p/q（既約分数）があります。あなたは適当に提出数を増やしてAC率をp/qにしたいと考えています。
AC率をp/qにするために必要な最小提出回数を求めてください、ただしどれだけ提出を増やしてもp/qにできないときは-1としてください。
考えたこと
何かかなり難しそうです。まず自明なケースを考えてみます。
まずp/q = 0のとき、これは明らかにx > 0のときは不可能です。分母を増やしてx/yを限りなく0に近づけることはできますが、0に等しくすることはできないからです。
x = 0のときは、これは最初からx/y = 0なので0回が答えになります。
同様にp/q = 1(p = q)のとき、x < yのときは不可能、x = yのとき0回となります。
じゃあ上記以外の場合、0 < p/q < 1のときは出来るのか？ということですが、何か直感的にはできそうな気がします。よく分かりませんが。
何か適当に数式を使って考えてみます。増やした提出数を、そのうちのAC数を
として
となる最小のを求めてくださいということですね。正式にはその組合せ
の中で
が最小になるようなものって感じですか。
tを増やしながらsを0 ~ tの範囲で動かして……という総当たりも考えられますがこれはどう考えてもTLEしそうでまずいです。何かもうちょっと上手い方法が欲しいです。
それで何か上の式を適当にいじったり、p/qとx/yの差を考えて……とかやってたんですがやっぱりなかなか上手い方法が見当たらず難航しました。
それでしばらくしてから、二次元平面にプロットして考えてみようという考えに至りました。
例えばp = 2, q = 5, x = 2, y = 10とするとこんな感じです。
原点を通る青の直線上にポツポツとある点が到達したい有理数p/qです。
そして青の領域で囲っているところが提出を増やしていくと行けるようになる点の集合です（実際にはこの青の領域上の格子点のみですが）
x, yが使われているので横軸がz, 縦軸がwとします。この図を見るとと
の交点を求めればそこから右の領域は
上の点を全て含んでいることに気が付きます。
だからまずこの交点を求めて、その交点のz成分以上のqの倍数を求めて、yを引けば、最小限必要な提出数が求まるということが分かります！
この例の場合だと15 - 10 = 5だなーと見ただけで分かりますね。
しかし上の図はq/p > x/y だから成り立つ図であって、q/p < x/yになるとちょっと様子が変わってきて、こんな感じになります。
例えばq = 2, p = 5, x = 7, y = 11としてみると以下のようになります。
今度は求めるべき交点がと
に変わったことが分かるかと思います。
このグラフからq/p = 0やq/p = 1がコーナーケースになってることも明らかに見てとることができます（平行なので直線が交わらない場合がある）
以上の考察から順番にまとめると
- q = 0(q/p = 0)の場合、x = 0なら0回、それ以外なら不可能
- q = p(q/p = 1)の場合、x = yなら0回、それ以外なら不可能
- q/p = x/yの場合は明らかに0回
- q/p > x/yの場合は
と
の交点のz成分を求めて、それ以上の最小のqの倍数を求めて、その値からyを引く
- q/p < x/yの場合は
の交点のz成分を求めて、それ以上の最小のqの倍数を求めて、その値からyを引く
といった感じでO(1)で求めることができるようになりました。
後は実際に方程式を解いてそれをコードにすると以下のような感じになります。
import sys def solve(): t = int(sys.stdin.readline()) for ti in range(t): x, y, p, q = map(int, sys.stdin.readline().split()) if p == 0: # p/q = 0 if x == 0: print(0) else: print(-1) continue if p == q: # p/q = 1 if x == y: print(0) else: print(-1) continue if p*y == x*q: # p/q = x/y print(0) elif p*y > x*q: # p/q > x/y z = (q*(y - x) + q - p - 1) // (q - p) ans = (z + q - 1) // q * q - y print(ans) else: # p/q < x/y z = (q*x + p - 1) // p ans = (z + q - 1) // q * q - y print(ans) if __name__ == '__main__': solve()
誤差に殺されないようにx/y > p/qの比較をx*q > y*pに書き換えたり、a/bの切り上げを(a + b - 1) // bで計算したりという若干の工夫がありますがやってることはシンプルです。
1回WAしてしまったのは、continueと書くべきところをreturnと書いてしまっていたからでした……もったいないです。
もうちょっと煮詰めると２つの交点のうち大きい方を取れば場合分けしなくてもいいということに気が付くので以下のような感じになります。
import sys def solve(): t = int(sys.stdin.readline()) for ti in range(t): x, y, p, q = map(int, sys.stdin.readline().split()) if p == 0: print(0 if x == 0 else -1) continue if p == q: print(0 if x == y else -1) continue z = max((q*(y - x) + q - p - 1) // (q - p), (q*x + p - 1) // p) ans = (z + q - 1) // q * q - y print(ans) if __name__ == '__main__': solve()
ちなみにグラフを描くのに使ったのはDesmosというサイトです。非常に使いやすかったです。
何かぐりぐり動かしてみると面白いので皆さんもやってみてください。
https://www.desmos.com/calculator/rvzdbbxkak
式で考えてるだけでは全然分からなかったのに、図に書いてみると急に明快に答えが分かって気持ちよかったです。
図に頼りすぎるのもちょっと危ない気がしますが、それでも図を書いてみるというのはやはり大事だなあと思いました。
D. Dynamic Problem Scoring
問題概要
VasyaとPetyaがこどふぉのあるコンテストに参加しました。そのコンテストは2時間で5問です。
このコンテストでは普段とは違う動的スコアリングという方法で点数付けでスコアが決まります。
この方法ではコンテスト前に各問題のスコアが決められるのではなく、コンテスト後に参加者に対する正解者の比を算出してその値によって問題のスコアが決められます。
より詳細には以下の表でスコアが決定されます。
| 正解者 / 参加者 | 問題の最大スコア |
| (1/2, 1] | 500 |
| (1/4, 1/2] | 1000 |
| (1/8, 1/4] | 1500 |
| (1/16, 1/8] | 2000 |
| (1/32, 1/16] | 2500 |
| [0, 1/32] | 3000 |
そして実際に正解者に与えられるスコアは、その問題の最大スコアをx, その問題を解いた時間をm(分）とすると、x * (1 - m/250)で与えられます。
さて、コンテストも終わりに近づき、残り2秒になりました。
VasyaはPetyaにどうしても勝ちたいので、Vasyaは10^9 + 7個もあるサブアカを使って問題の正解者/参加者を変化させて点数を調整することで、Petyaの点数を上回ろうと考えました。
Vasyaはサブアカを使って、自分が解けた問題をそのサブアカにACさせることができます。自分が解けなかった問題はACさせることができないことに注意してください。また、不正解にさせることは自分が解けたか否かに関わらず可能です。
ただ、あまり大っぴらにやるとバレそうなので出来るだけ少ないアカウントを使ってその目的を達成したいです。
Vasyaの提出状況、Petyaの提出状況、およびその他の参加者の提出状況が与えられるので、上の問いに答えてください。
ただしどれだけサブアカを使っても上回ることができない場合は-1と答えてください。
考えたこと
最初この問題を見たとき「何だこれは……」という感じで全くどうやって解けばいいか分かりませんでした。というかめちゃくちゃ複雑そうに見えました。
けど冷静になって考えるとそれほど難しくないような気がしてきました。アカウントを増やしたときの戦略はシンプルです。
自分の提出状況をv_i, petyaの提出状況をp_iとすると、
- v_i = -1のとき「自分は解けなかった」ので、問題iは不正解にさせることしかできない
- p_i = -1のときは「相手は問題iを解けなかった」ので問題iの価値を高めるとよい、すなわち問題iは不正解にすればよい
- p_i != -1かつ、v_i < p_iのとき「自分は相手より早く問題iが解けた」ので、問題iの価値を高めるとよい。よって問題iは不正解にすればよい
- p_i != -1かつ、v_i = p_iのとき「自分と相手は同時に問題iが解けた」ので、問題iで点数差は発生しない、よってどちらでもよい
- p_i != -1かつ、v_i > p_iのとき「相手は自分より早く問題iが解けた」ので、問題iでは相手に点数差をつけられている。よって問題iの価値は下げて、その点数差を出来るだけ小さくするべきである。つまり、問題iは正解させるとよい。
と、こんな感じですね。もっと簡潔に条件をまとめると
- p_i != -1かつv_i > p_iのとき、そのサブアカに問題iを正解させる
- それ以外の場合、そのサブアカに問題iを不正解にさせる
という戦略を取るのが最も良いことになります。
ただ問題はサブアカの数が10^9 + 7とめちゃくちゃ多いことですね。これでは全探索は出来ません。
しかし、アカウントを増やせば増やすほど有利になるはずです。つまり単調性が成り立っているということなので……二分探索すればlog(10^9 + 7)ぐらいで終わりますから余裕ですね！
……と、意気揚々と二分探索を書くとWAになります。
実は、「アカウントを増やせば増やすほど有利になる」という仮定、つまり単調性を仮定したことがどうやら間違っていたようです。
というのも、自分が問題iを解けずかつ相手が問題iを解けていた場合、サブアカを増やしてしまうと、自分が解けてないのでそのサブアカには問題iを不正解にさせることしかできません。（私はこの条件を見落としていました）
つまり、問題iの価値が高まってしまい、アカウントを増やしたのが逆効果になってしまっています。
だから「アカウントを増やせば増やすほど有利になる」というのは嘘だったわけですね。
じゃあどうすればいいんだ……と思いますが、ここで制約をよく見るとコンテスト参加人数が高々n <= 120です。
そして、動的スコアリングの表を見ると、実は10^9 + 7人も追加しなくてもよいことが分かります。
まず、アカウントを増やしてやりたいことは「問題iの価値を高める（難化させること）」「問題iの価値を低める（易化させること）」です。
n = 120のとき、前者は120/120 = 1から最も問題の価値をあげようとすると、必要な人数は120 / (120 + m) <= 1/32を満たすmです。
後者は1/120から最も問題の価値を下げようとすると、必要な人数は(1 + m) / (120 + m) > 1/2を満たすmです。
これらを解くと、だいたい4000人もいれば十分だということが分かります。
つまり、10^9 + 7人いるけど実際は4000人まで増やしてダメだったらもうそれ以上増やしても無理なものは無理ということです。
これぐらいなら普通に下から全探索しても余裕で間に合うので全探索すればいいよってことになります。
ということですね、実際は計算間違いとかしてて4000じゃ足りない、なんてことがあると嫌ですからもうちょっと余裕のあるところまで回せばいいと思います（50000とか、速い言語ならもっと回してもいいと思います）
この問題要約すると「単純な戦略を決めて、後は全探索するだけ」なんですよね。それでもかなり正解者が少ない(div2だとがくっと落ちてました）のは面白いです。
「まず問題文を読むのが面倒」とか「実装が重い」とか「前３問で時間使い果たした」とかいろんな理由があるとは思いますが……
- 「オーダーのざっくりした計算量だけでなく、実際により詰めた具体的な計算量の解析も大事」
- 「基本は全探索」
- 「単調性も確認せず安易に二分探索に走ってはいけない」
などの教訓を得ることができる問題だなあと思いました。
特に私は二分探索が好きで最大・最小とか聞くとすぐ二分探索を使いたくなってしまうので気を付けたいと思いました。
import sys inf = 10**9 + 7 def solve(): n = int(sys.stdin.readline()) v = [int(vi) for vi in sys.stdin.readline().split()] # Vesya p = [int(pi) for pi in sys.stdin.readline().split()] # Petya cnt = [0]*5 for i in range(5): if v[i] != -1: cnt[i] += 1 if p[i] != -1: cnt[i] += 1 for i in range(n - 2): a = [int(ai) for ai in sys.stdin.readline().split()] for j in range(5): if a[j] != -1: cnt[j] += 1 for i in range(4000): if check(n, v, p, cnt, i): print(i) return print(-1) def check(n, v, p, cnt, m): tot = n + m solved = cnt[:] dif = 0 for i in range(5): if p[i] != -1 and v[i] > p[i]: solved[i] += m for i in range(5): if solved[i]*2 > tot: max_score = 500 elif solved[i]*4 > tot: max_score = 1000 elif solved[i]*8 > tot: max_score = 1500 elif solved[i]*16 > tot: max_score = 2000 elif solved[i]*32 > tot: max_score = 2500 else: max_score = 3000 if v[i] == p[i] == -1: pass elif v[i] == -1: dif -= max_score * (250 - p[i]) // 250 elif p[i] == -1: dif += max_score * (250 - v[i]) // 250 else: dif += max_score * (p[i] - v[i]) // 250 return dif > 0 if __name__ == '__main__': solve()
総評
touristが作問のコンテストということでどんな問題が出るのかなあ、と期待？していたのですが、全体的に「読むのが大変」「実装もちょっと大変」なコンテストだなあという印象でした。
正直言うと、強い人が作る問題って「問題文はシンプルで分かりやすい、しかし解くのは難しい。でも解法は思いつけばとてもシンプルに解ける」と、そんな感じの問題だろうなと思っていたからです。
特に今回のBとかDみたいな問題はまず出さないだろうみたいな謎の先入観があったので、少々意外でした。
Bは正直読むのがしんどいだけかな……という感じでしたが、Cは面白かったですし、Dも教訓が得られる良い問題だなあと思いました。
