NOMURA プログラミングコンテスト 2020
https://atcoder.jp/contests/nomura2020
5月の個人コンテストはこれが最初で最後となりました (?????)
A,B
無
C
アップダウンとボトムアップを組み合わせるとそれっぽい貪欲になることはわかる
「正しそうだけど示すのむずいな~」と「600点ってこんなに単純でいいの??」の間で揺れて時間が経ってしまう
F
書き換えは1か所だと思っていたので 違う箇所が1つ以下 or 2つの0/1が頭にくる or 違う箇所が2つで0/1 1/0 という条件になり、全く解けない
よく読むと回数は任意なので、1/0があったらそれ以降は等しい だけに言い換えられる
等しくなる部分を圧縮しながらDPすれば良くて、式を整理すると2乗
D
いろいろ試すとループの個数に着目すると解けることが分かる むずいね
(連結成分に注目したり木の数え上げに帰着しようとしたりしませんか?僕はしました)
感想
日本人7位、DF数え上げなのに滅茶苦茶手間取ってしまって辛かったが、問題は面白かったです
6月はちょっとずつ練習してこのブログも更新していきたいと思います