Codeforces Round #671 感想

Problem A

ゲームをする。数字が与えられる。先手は奇数桁目を、後手は偶数桁目をマークできる。最後までマークされず残った1つの数字が奇数なら先手の、偶数なら後手の勝ち。最適な戦略の元でどちらが勝つか。

考察

• 相手に干渉できない
• 偶奇によるがどちらか片方の操作は一切勝敗に関与しない
• 関与する側は自分が勝つための数字があればそれを残すべきで、そうでないならあきらめるしかない
• 偶奇の場合分けを頑張ってやる

Problem B

x個のタイルで良い階段を何種類作れるか。良い階段とは正方形に組み合わせたタイルn個でできるn段の階段をいう

考察

• 1,3,7,15,...段の階段がよい階段
• サンプルから、10¹⁸個のタイルでも30種類しかできない
• それぞれに必要なタイル数とその累積和をとって小さい段数の階段から作っていったときに何種類できるか考える
• シフト演算が型の大きさ間違えてバグった。

Problem C

ウイルスがある。レートが同じ者に感染し、治癒しない。最初、レートKの者が一人感染している。この者はコンテストに参加しない。感染していないn人の人がいる。レートは参加者のレートの総和を変えないように変動する。参加者やレート変動を好きに決めていいとして、全員感染するには最短でコンテストが何回開催されればよいか

考察

• 全員最初からKなら0
• そんなに長い時間かからない せいぜい2回
• 1回で済むパターンは
• 全員のレートの平均がちょうどK、これは1回で全員Kにできるため
• 最初にレートKの者がいる、それ以外の者をKに合わせ、レートKだったもので釣り合いを総和のとればよい
• 最初にレートKの者がいるなら絶対1でいいのに2のケースがあると勘違いした、もともと感染していた人を脳内から退場させていたため。

Problem D1

相異なるn個の数a1～anを並び替えてai-1>ai<ai+1なるaiをいくつ作れるか。またその並びは

考察

• WWWWWWWWみたいにする
• 奇数の場合[n/2] 偶数の場合[(n-1)/2]
• 一般に[(n-1)/2]
• サンプルのようにソートして小さい集団を偶数番目に、大きい集団を奇数番目に

Problem D2

相異ならない場合は？

これはわからなかった。既出な気がするけど

あとがき

レートの伸びがまじで弱い。人々こどふぉ得意すぎませんか