2016/7 Solved(1)
7/1
予算に関して増やせる体重の最大値を保存するDPをすればよい．最初逆に体重に関するDPを考えてしまっていたが，増加しうる体重の最大値が大きく，おそらく間に合わない．
7/2
7/3
bitDPをしながら条件を満たす順番を決めていけば良い．
増加列がフィボナッチに従うことに気づく．
しゃくとり的な感じで進めていく．
7/4
大きく進んで戻ることが許されていないので，貪欲に進めていくのが最適になる．
7/5
3枚の板の長さを全探索して，長さを決めた時のその長さを作るために必要な板の枚数の最小値をDPにより求める．
7/6
(なにもしてない)
7/7
和のSegtreeを使って更新していく．
長さを二分探索をして，その本数以上切り出せるかを調べていけば良い．
TDPCに似た問題があって，確率のDPをしていく．
7/8
誤差がゆるいので，10000回までの確率だけを求めてその期待値を出した．想定としては二分探索らしいのだけど，まだ解説をみても理解できてないのでもうちょっと考えたい．
異なる2つの中継局を選び，その距離を計測してUnionFindで結合させていく．結合の処理後に，異なる2点を選んで距離の最大値を更新していけば良い．
7/9
yukicoderに参加
4問全完．数学的考察を要する問題が多くて，頭をひねった．2問目は最初Pythonで書いていたけど，逆元とか実装する必要性を感じて，間に合わないと思ってC++で書き直してたら結構時間かかってた...
ただシミュレーションすればよい．
両端に発電所が有る区間に分けて，その区間に対して分け目を全探索していく．
7/10
テトリス全然関係ない．もし問題の条件を実現できる時は目指すべき値は1つしかない(全ての値の和の平均になる)ので，数列aのindexが小さい順にbの(index-1,index)を使っているか否かを状態に持ちながらその値を作っていけるかどうかをメモ化再帰した．
7/11
Codechef July Challenge 2016に参加
マラソンとは違うが，アルゴリズムの問題が9問くらい出て挑戦期間が10日間くらいあるコンテスト．参加したのが最後1日だけだったし，途中でやるのをやめちゃったけど，とりあえず3完した．コンテストに積極的に参加したいとか思いつつ，なかなか短時間のコンテストにタイミングが合わないのでこれは時間も自由に取れるしこれからも参加してみようかなと思っている．
2次元座標系に落としこむと考えやすい(常に右上に進み続ける最長増加部分列を求める)．
7/12
7/13
答えに含まれる数字4つを見つけられれば，後はそのpermutationについて調べれば良いので，うまく4つの数字を探す方法を考える．ここは色々な方針が考えられると思うが，3つの数字を固定して1つの数字を動かす全探索をしていくのが見つけやすいと考える(submission)．
3でも5でも割り切れるということを分割して解釈すると，3の倍数である条件は「各桁の合計が3の倍数」で，5の倍数である条件は「下1桁が0または5である」ことになる．この問題では3と5しか使わないので，一番下の桁は5で確定する．その上をどうしていくかを考えることになる．そこで，もう5の倍数であることは確定しているからどのようにすれば3の倍数に出来るかと考えると，5の個数が3の倍数個あればよいことになる．すでに1個あるので，2,5,8,...個あればよい．なので，i+1桁の数でSuperFizzBuzzになる個数はCombinationをつかって2Ci+5Ci+...と表せる．これを使って，ギリギリまで進めていき，その桁にn番目のSuperFizzBuzzがあることがわかればその桁で全探索すれば良い(submission)．
はじめはdp[x][y]=買った商品の状態をビットで表すx，discount額y円の時の最少額を持ってDPしていったが，これだと1つのDPの更新にかかるので，全体として計算量が間に合わない．ただ，よく考察してみると買った商品の状態がわかっていれば，定価の合計の1000の剰余がdiscount額となっているので，discount額を保存しておく必要がないことに気づいた．yを除いて，
dp[x]を更新していくDPに出来る．計算量は全体でとなり，間に合う．
半分全列挙っぽくやった．まず2つで作れる和の組み合わせを求め，それを利用して4つで作れる和の組み合わせを求め，最後に8つで6nを作れる組み合わせを求めた(submission)．こんなことしなくてもDPで出来るよねって，確かに...ってなった
7/14
階乗をクエリの前に計算して用意しておくと，逆元の計算を利用することで各クエリにで答えられる．
7/15
各長さをそれぞれカウントして持っておき，長さの異なる3つを全探索して足し合わせれば良い．
典型的なbitDP．最大体力は倒したモンスターの状態を見ればわかるのでそれを保つ必要はない．dp[mask]=敵を倒した状況がmaskの時の体力の最大値を小さい方から更新していく．ただし，既に体力が0になった状態から回復してしまうなどの状況をうまく枝刈りする必要がある(submission)．
7/16
要はソートされていればいいので，挿入ソートをした．
AGC 001に参加
ABの2完．Cは木の中心とかはちょっと考えたけど木の中心で全探索は思いつかなかった...
