2016/8 Solved(2)
8/17
- ABC 043 A - キャンディーとN人の子供イージー / Children and Candies (ABC Edit)
- ABC 043 B - バイナリハックイージー / Unhappy Hacking (ABC Edit)
8/18
和の公式と剰余．
最低限踏む水たまりの数をもちながらDP．
8/19
1つの位置に対して，サイズを1~nまで試す全探索．の解法だったが，制約が小さいので問題なかった(submission)．
大きい方から貪欲に，できるだけ隙間がなくなるように詰めていく．
面白い問題だった．部分点が良いヒントになった．閉路がなければ何が幸せなのかって考えてみると，つまりそのとき各連結成分は全部木なので，どの辺を切ってもグループが1つ増やせるわけであるから，ソートして小さい方から選べばいいというのが分かる．そうすると，閉路が1つだけあるときは，その閉路のうち1つ辺をのぞいてしまえば後は状況が同じになると言えるので閉路が有るときは閉路を除去してグループをKにする場合と閉路を残してグループをKにする場合に分けて考えられる．つまり．どの辺が閉路を構成するものなのかが分かる必要がある．今回は1つしか閉路がないということから．最短経路を求めた時に使われない辺が1つだけあると考えて，そこからLCA的に共通の親が見つかるまで辺をたどっていって，閉路を構成する辺とそれ以外を分類する方法を思いついたのでそれを実装してみた(submission)．
現在位置,何文字目まで見たか,進んできた方向を保存しながらBFSしていくだけだったのだが，"進行中に伝えたい文字が見つかったら，直ちに止まる"というのを見落としていてバグらせていた．
8/20
Segtreeと二分探索の組み合わせで説いた(submission)．
8/21
AGC 003に参加
ABCの3完．いつも3完でおわってしまう...
8/22
8/23
8/24
必ず木になるので、根から遠いところからボトムアップ的にコストを貪欲に決めていくことが出来る。
8/25
8/26
8/27
8/28
問題セット数を決め打ちにすると、
セットを作ることが出来るかというのは簡単に判定することが出来る。具体的に自分がとった方法としては、EとEMでEasyの問題をx問集め、HとMHでHardの問題をx問集め、EMの残り+MHの残り+Mの問題数がx問集まるかどうかという判定方法をとっている(submission)。
ARC 060に参加
CDの2完。今回はDですごく時間をつかってしまったけど、解ききれたのは嬉しかった。解説にある感じではなく、から見ていくとなんかいい感じの等差数列になっているからそれで削っていって
くらいまでおわったらそれ以下全探索みたいな方法をとった。Eができなかったのは要復習...
8/29
CF #369 Div2に参加
2ヶ月ぶりに参加した。今回も4問目できそうで出来ず...ABCの3完。こどふぉDが自分にとってちょうど良いレベルになってる...？SRMDiv1Easy練習と平行してやってもいいかもと思い始めた。
8/30
(なにもしてない)
