M-SOLUTIONS Programming Contest

開始前36.4、Dを通して測ったら36.5。集中力がない(だから短時間のコンテストが好き(最近は長いほうが得意な気がしてるけど))。ぷよぷよをやるときも、試合に全力を注ぐために短期決戦の速攻を仕掛けたりしてる。今回でいうと、難しそうなEは諦めたほうがいいかもしれないが、集中するため、貴重なコンテストの時間を捌くため、面白そうなEも考えていた(実際は、2問並列に考えるのはパフォーマンスの期待値を下げないと思うけど(じゃあ絶対そうするやん?(だからそうした)))。

いい問題だったよ。レーティングも上がった。しかしなんでこんな気持ちに。

A - Sum of Interior Angles

最初、(n+2)*180って書いてサンプル合わないのでマイナスに直した。

B - Sumo

サンプル2が親切。8勝するためには8敗しないことが必要。最初、可能性がないときにYESを出力するようにしてしまった。

C - Best-of-(2n-1)

問題文が明快でいいね。そして解法を考えると昨日考えてた「ぷよぷよの30先が勝率p側の30-kで終わる確率」がもろに使えそうじゃん!実装に手間取りながら書き進めるが、引き分けが思ったより大変そうだと気づく。さすがにひねりが利いてるなあと思いつつ。「実は引き分けの処理は簡単そう」「引き分けを加えて正面から解きなおす」この2つで迷う。前者で行けそうな雰囲気は感じるが、後者で行くのが無難な気もする。結局前者で行けた。まあN+i試合で終わるケースの確率がわかってるので、そこに引き分けを混ぜる感じで。何で割って何を掛けるかでけっこう混乱して、そもそもA/100ではなくA/(A+B)で計算するのをわかってなかった。これもサンプルがかなり親切。入力が0のケースと入力がでかいケースがちゃんとある。

D - Maximum Sum of Minimum

貪欲ではさすがにダメっぽいが。けっこうたくさん解かれている。最大化するってことは何かを最小化する?N個の数がN-1回現れる。小さいほうから見て行けそう。しかし、貪欲じゃダメだが貪欲じゃないなら解けないだろ。このときは、小さい順に葉に書き込み頂点を削除するのを繰り返すのしか思いつかなくてそれは反例があると思っていた(しかしこれ反例ないか)。反例を作るという方向性はずっと頭にあったが、何も見えずに計算することができないんだよね。「あっ、こっちへ行ったら解けそうだな」という感覚が少しでもないと手を動かすことすらできない。最大を達成するのがどのくらいきつい条件かイメージできなくて。もう何も見えなかった。

最大のcが辺に書かれることはないとわかっていたので、合計は小さい順にN-1個足したもの以下にしかならない(ほんとに自明か?)。で、DFSすればそれを達成できる。はー。無の考察がつらかった。

E - Product of Arithmetic Progression

dが毎回違うのがつらすぎる。なんか規則性はありそうだけど、たとえば1,4,7,10,13...の積とか無理でしょ。事前計算はせいぜい100万の100倍まで。クエリも10^5あるから1000回まで。絶対面白いと思ったが、結局は何もできなかった。