つちのこの日記

競プロと音ゲーがメインです。

CodeForces div.1 バチャの記録

6/7からdiv.1バチャをすることになりました。

せっかくなので各回について記録と解けなかった問題の分析をメモっていこうと思います。

解けたけど消化しきれていない問題や、解けなかったけど大事そうな問題については個別に解説記事を書くかもしれません。

よろしくお願いします。

6/7 Codeforces Round #499 (Div. 1)

結果

ABCD4完

一言解法

  • A.こういうのは逆から見ます 1のやつがあったら無理で他は最小にすればよい、簡単でした
  • B.ちょっと悩んでしまった。。 クエリの回数見るとにぶたんで、最初のN回 1以上かという結果が自明なクエリを投げれば真偽が特定できます。
  • C.無限回見ました、GCDをとるだけ K進法のくだり、いりますか?
  • D.やることは割とすぐ見えて、各場所のbitを確かめてからdfsでどうなるかを決めます。実装が170行で破滅してしまいました。。

感想

A-CがDiv.1にしてはかなり簡単でびっくりしました、Dみたいな実装問でうまい実装方針にたどりつけるようにしたいです。

6/9 Codeforces Round #691 (Div. 1)

結果

AB2完

一言解法

  • A.gcdと差は相性が良いのではい
  • B.一瞬貪欲を疑ったがうまくいかないので実家のようなDPをします
  • C.逆置換をうまく処理する方法、初めて知りました(全然見えなくて飛ばした)
  • D.ARCとかにありそう、うーん
  • E.解けそうでしたが終了後に一個勘違いに気づきました。(翌日通しました、考察はEにしては軽かったですが実装でバグらせまくりました、、、)

感想

やー、CからEのどれか一つは通したかったですね。 Bで0.5出てくるのにint / 2 をして1ペナ出したの本当にもったいない、反省です。 E、めちゃくちゃ面白かったです。

6/11 Codeforces Round #580 (Div. 1)

結果

ABC3完

一言解法

  • A.+1と-1に着目するシンプルな構築
  • B.同じbitが立っている数が3つあれば終わりなことには気づいたのに、頂点数が120以下なことに全然気づかなくてロス、勿体なかったです
  • C.仮置きすると大体決まる 特定パートは未証明でやっちゃいました(反省)

感想

Bみたいなギャグをパッと通せるようになりたいです。

6/14 Codeforces Round #485 (Div. 1)

結果

ABCE4完

一言解法

  • A.多始点bfs
  • B.転倒数
  • C.反転させたやつとかにいい感じに辺を貼る、むずかしいです。。。
  • D.めんどそう
  • E.素因数ごとにイベントソートしてHL分解でパス和取得 面白かったです。

感想

Cがむずかしかった、こういうのパッと思いつけるようになりたいです。 Eはかなり好きな感じでした。

6/16 Codeforces Round #692 (Div. 1)

結果

ABCE4完

一言解法

  • A.むずかしい お気持ちでUF
  • B.こういうのは0と1集めた方がいいのでBITでシミュ
  • C.よく考えると後ろ2つ以外自由 コストが2ベキなので貪欲が正当性を持つ
  • D.めんどそう
  • E.終了後に通しました どちらもすごい面白かったです
    • 方針その1 grundy数が $ 512 $ 未満なことに着目すると、連立方程式立てて履き出せる
    • 方針その2 操作が $f(x) = \sum cnt_i x^{i}$ をxor畳み込みでかけることに対応しているので、 $\frac{1}{1-f(x)}$ みたいなのを求める invは FWTしてから各点逆元とってIFWTすればもとまる

感想

Cまで割と素早く解けて成長を感じました。Eは知見が得られてよかったです。