読者です 読者をやめる 読者になる 読者になる

裏紙

ほぼ競プロ、たまに日記

2016/8 Solved(2)

8/17

8/18

和の公式と剰余.

最低限踏む水たまりの数をもちながらDP.

8/19

1つの位置に対して,サイズを1~nまで試す全探索.O(n^5)の解法だったが,制約が小さいので問題なかった(submission).

大きい方から貪欲に,できるだけ隙間がなくなるように詰めていく.

面白い問題だった.部分点が良いヒントになった.閉路がなければ何が幸せなのかって考えてみると,つまりそのとき各連結成分は全部木なので,どの辺を切ってもグループが1つ増やせるわけであるから,ソートして小さい方から選べばいいというのが分かる.そうすると,閉路が1つだけあるときは,その閉路のうち1つ辺をのぞいてしまえば後は状況が同じになると言えるので閉路が有るときは閉路を除去してグループをKにする場合と閉路を残してグループをKにする場合に分けて考えられる.つまり.どの辺が閉路を構成するものなのかが分かる必要がある.今回は1つしか閉路がないということから.最短経路を求めた時に使われない辺が1つだけあると考えて,そこからLCA的に共通の親が見つかるまで辺をたどっていって,閉路を構成する辺とそれ以外を分類する方法を思いついたのでそれを実装してみた(submission).

現在位置,何文字目まで見たか,進んできた方向を保存しながらBFSしていくだけだったのだが,"進行中に伝えたい文字が見つかったら,直ちに止まる"というのを見落としていてバグらせていた.

8/20

imulan.hatenablog.jp

Segtreeと二分探索の組み合わせで説いた(submission).

8/21

AGC 003に参加

ABCの3完.いつも3完でおわってしまう...

8/22

imulan.hatenablog.jp

8/23

8/24

必ず木になるので、根から遠いところからボトムアップ的にコストを貪欲に決めていくことが出来る。

8/25

8/26

8/27

imulan.hatenablog.jp

8/28

問題セット数xを決め打ちにすると、xセットを作ることが出来るかというのは簡単に判定することが出来る。具体的に自分がとった方法としては、EとEMでEasyの問題をx問集め、HとMHでHardの問題をx問集め、EMの残り+MHの残り+Mの問題数がx問集まるかどうかという判定方法をとっている(submission)。

ARC 060に参加

CDの2完。今回はDですごく時間をつかってしまったけど、解ききれたのは嬉しかった。解説にある感じではなく、nから見ていくとなんかいい感じの等差数列になっているからそれで削っていって10^6くらいまでおわったらそれ以下全探索みたいな方法をとった。Eができなかったのは要復習...

8/29

imulan.hatenablog.jp

CF #369 Div2に参加

2ヶ月ぶりに参加した。今回も4問目できそうで出来ず...ABCの3完。こどふぉDが自分にとってちょうど良いレベルになってる...?SRMDiv1Easy練習と平行してやってもいいかもと思い始めた。

8/30

(なにもしてない)

8/31

imulan.hatenablog.jp

imulan.hatenablog.jp

imulan.hatenablog.jp