ferinの競プロ帳

競プロについてのメモ

Codeforces Round #429 (Div. 2) 考察

コンテスト中に考えてたことをまとめてみることにした。解法解説とはちょっとちがうかも?
覚えてる範囲なので時間はずれてるかも?


~00:03
Aを読むと、各文字の出現頻度を数えてKと比べればよさそう。ささっと実装したらpretest通った

~00:10
Bの読解が難しかったのでCを読んで見るとCも意味不明だった。
サンプル読むとAの大きいのをBの小さいのに合わせる貪欲で行けるのではと思ったけどさすがに怖かったのでBに戻る。

~00:20
最初の数列の合計が奇数個だったら当然Firstの勝ち。
最初の数列の合計が偶数でFirstが行動できたとしたら合計は奇数になる。
Secondが合計が偶数の区間を取れたとしても次にFirstに合計が奇数で回ってくるのでFirstの勝ち。
よって数列に奇数が一個でもあったらFirstの勝ち。
実装したらpretest通った。

~00:30
CのF(n, k)の意味がわからなさすぎて考えてたらclarで例が出てきてようやく理解した。
kが大きくなると、F(n, k)は小さくなるのでnが大きいもので小さいkを使ったほうがよさそう。
最初に考えてた貪欲を実装して投げたらあんまり自信なかったけどpretest通った。

~01:00
Dを読むと頂点の次数のmod2とd[i]が一致しているかd[i]が-1の頂点の部分集合を探せばよさそう。
頂点の次数を部分集合のグラフではなく元のグラフのものだと考えていて異常に簡単なので誤読を疑う。
部分集合のうちもっとも大きいものを出力するのかと思いこんで実装する。
サンプルをよく見ると明らかに違っていて、部分集合のグラフに含まれてる辺のみを次数にカウントすることに気づく。
この問題はさすがに無理そうと思えたのでHackに移ることにする。
この時点でCのsolvedがかなり多くてCの単純な貪欲解法にちょっと自信がでてくる。

~02:00
A、B、Cを順番に自分のを見直して部屋のを一つずつ見ていっていたけど、一つもhackできなかった…
Bで数列の合計をintに取ってるコードがあって一瞬期待したら#define int llだった。
Bのcinで10^6はさすがに落とせる確証がなかったので踏み切れなかった。落とせてたらしい。
インデントがぐちゃぐちゃだったりするコードもちょっとは読めるようになった。

まとめ
3完449位 1614->1669(+55)
readforcesやめてほしい… CとDの難易度差が大きくてHackゲーだったけど部屋の人たちが注意力が高かった。
部屋で落ちてるのが一つあってhackできなかったのが悔しい。