2016/8 Solved(1)
8/1
UnionFindと二分探索を「クエリ全部に同時並行的に」行っていく．まず，クエリが1つだったときのことを考えてみるとこの兄弟はスコアi以内で収まるかどうかというものを判定しながら二分探索していくことになる．その際に，i番目の辺までを結合したUnionFindを考え，つながっている数などを見て可否を判定できるわけである．つまりこの処理にはかかる．それを
個のクエリにそれぞれやっているのでは到底間に合わないので，一気にやろうという考え方になる．各クエリごとに下界
と上界
を保存しながら，クエリごとに平均を取って二分探索の用意をする(その際にどこに入ったかをベクタで保存しておく)．そして，小さい方からUnionFindを構成していき，その位置にクエリがあれば可否を判定していく．ということになる．こうなるとUnionFindを構成する必要があるのが全体を通して
回になり，1回の構成に
かかるが，十分に間に合う速度となる．クエリごとに同じ処理を結局して，それでそこがネックとなっていたUnionFIndの処理をまとめることで計算量を解決する初めて見るタイプの問題だった(submission)．
8/2
合格者の数を全探索．
bitDPで最大値を更新していく．
8/3
8/4
- ABC 042 A - 和風いろはちゃんイージー / Iroha and Haiku (ABC Edition)
- ABC 042 B - 和風いろはちゃんイージー / Iroha and Haiku (ABC Edition)
8/5
(なにもしてない)
8/6
ゲームが終了するまでに必ず[tex:nm-1]ターンかかるので，[tex:nm]の偶奇で勝敗が判定できる．
連結されている成分にはループが１つ存在するので，そのループの大きさを求めに行って，各連結成分に対しての大きさの和が答えとなる．連結成分を探しに行くところで有効辺を無向辺に変えてBFSした．
8/7
startが0になるように合わせておくと考えやすかった．直接行く・一周してから行く・ある位置で折り返してから行く・ある位置で折り返してendを通り過ぎて折り返してendに行く というルートが考えられるので，それを累積和とSegTreeを使って速く計算できるようにした．最後の折り返しを2回するパターンを見落としていて頭を抱え続けた...
8/8
mapを使って文字列と数字を変換して，12での剰余をとる．
まずxをソートしておく．x[1]-x[0]を基準にして，x[i]-x[i-1]が全て一致するかどうかを判定する．
まず，素数を列挙しておくと，N-1番目の鴨は(n-1)pのところに来る．すると素数pに対してはL-(n-1)p+1通りの組み合わせがある．
8/9
ナップザック問題のようなDP．
8/10
累積和と二分探索を使って，i日目を連休の開始とした時にどこまで休めるかを求められる．全体で．
8/11
文字を区切る位置を全探索して，その分かれた2つの文字列に対してLCSを求める．すると，取り除くべき文字の数が決まり，LCSの長さをLとするとn-2*Lとなる．これで最小値を更新していく．
8/12
bitDPで解いた(submission)．ちょっと重いかなと思ってたけどもっとシンプルな解法があった...
解説とはちょっと違うやり方っぽかったのでメモ程度に．シートは大きい方から割り当てていけばいいと考えると，大きい方から3つのシートを選ぶことを3重ループを回すことにし，それぞれの家族に割り当てるシートを決める．すると，その割り当て方が出来るときにはその3つのシートの中で一番小さいシートよりも小さいシートを選ぶか否かは自由になり，その個数が個あるときにはその選び方は
通り存在することになり，大きい方から3つを固定した選び方は互いに重複しないので足し上げていけばOK(submission)．
8/13
double型の丸め誤差を狙いに行く問題．こういう仕様にさほど詳しくないし途中から始めたのも会って時間内には解ききれなかった...
ARC 059に参加
CDEの3完．Dは2文字と3文字の文字列だけし調べればいいということに 気づくまでに結構時間がかかってしまった．Eはとりあえず部分点を狙いに行こうとして，そこでDPを書いたやつが満点にも活かせそうだと思って流用→そのままのループがTLE→これ式変形すれば累積和で高速化出来るっていう流れに乗れて満点までいけたのが嬉しかった．
8/14
(なにもしてない)
8/15
解説を見ながら解いた．確かに高さが関係ないことは気づいたけど，そこからサイズを変換して交点を格子点上に持ってくるようにするアイデアはなかった...(ひたすら座標上に直線として伸ばして長方形との交点を考えるとかしてた)
8/16
(なにもしてない)
