2016/6 Solved(2)
6/16
満点解法みて，めっちゃ賢い...ってなった．後ろから埋めていく(この状態にたどり着くには前の段階で割るか割らないかのどちらかだが，割る場合は前との積がn以下，割らない場合はそこのaで割り切れないことが条件になっている)のはすごい．あとは，ありうる場所を絞り込んだ全探索解も久しぶりに見たので，こういうのも忘れないようにしないとなあと思った．
最近むしろこういうパッと見てDPだってなる問題のほうが速く解けている気がする()
左上からの和を持つDP累積和を取り，それを利用して左上と右下を全探索しながらそのクエリにで答えていく．
直線を順番に引いて行く時，それより前との直線との交点の個数+1個だけ新しいエリアが増えると見なすことができるので，そうやっていくことでで計算できる．
線分の交差判定をして，交点とA駅との距離とその点において高架を通るべきかまたは地下を通るべきかを保存する．そのあとに距離でソートし，高架・地下の反転数を答えとすれば良い．
全探索により2点を選んで，その2点を円周上にもつ円が2種類考えられて，その円に対して何個内側に有るかを判定して最大値を更新していけばよい．
6/17
考えてみたら点対称の図形だけがこのような点を持ちうるのではということになり，実際に書いてみたら合ってた．
この前の模擬国内のことが頭にのこっていたので，座標圧縮+DPみたいな感じでやろうとすぐに方針は決まったんだけど，結局実装するのに45分くらいかかってしまった...
6/18
CF #358 Div2に参加
ABCの3完．DはDPだろうという感じがしていたけどどうしても最後までうまく行かなかった．要復習...
ABC 040に参加
ABCDの4完．Cまではぱっぱと解けたんだけど，Dは結構悩んだ．Union-findに連結されている要素を更新する部分を付け加えて実現させた．
6/19
6/20
最小値の解法のマイナスが一個もないときの割り当て方の貪欲法は思いつけなかった...面白い問題だった．
Nim知らなかったけど，dfsしてそのメモ化をmapでするようにしたらできた．
DPなんかを書いてしまったけど，本文全て以外の一番長い回文が見つかればあとはそれ以外の部分を長さ1の回文にしちゃえばいいからそんなことは蛇足だった...
最初に素数列挙してハッシュを計算してからしゃくとり法をする．
戦闘開始の位置を全探索して，それらに対して優先度付きキューをつかって各戦闘時にどのモンスターが戦闘しどれだけレベルがあがるのかを保存しながら進めていく．
考慮すべき条件が多くてつらかった．
まず全てのピースのマンハッタン距離が1以下であることを確認しておく．それからは，0のある位置の4近傍に今0があるところにあるべきピースがあるかを調べてあればswapしなければ終了とする．一応ピースの移動回数もカウントしてたけど，もしかしていらなかったかも．
先頭から順番にそろえていくようにする．
初回にスキルを使ってしまうのがよい．
まず文字列を2つに分ける．その分ける位置を全探索する．2つにわかれたところで，前半でgoodを作るための最小コストと後半でproblemを作るための最小コストを全探索で求めれば良い．
漸化式を変形すると，単純な形に落とし込めるのでそれを計算した．解説を読んで，初めて意図がわかった．
正負で分けて，左にi個，右にn-i個としてiを全探索する．
文字列を直接DPにもたせてしまったけど，後ろから見ていって後から経路復元するほうが当然時間かからないし，その方法も思いつけるようにしないと...
Pythonで殴ってしまったけど，式変形をしてcombinationの積の形にし，パスカルの三角形を作るとC++でもいけるらしい...面白い発想．
6/21
グラフとして考え，連結成分の中で最も安いものをその連結している個数分買うのが最適．
DPした後に経路復元をする．経路は，最大値を更新するたびに親を更新して，後ろから辿って行く時に"0:食べられない"から"1:食べられる"に移っている時にその寿司を食べているとわかるのでvectorに突っ込んでいき，最後にreverseして最初から表示するようにすれば良い．
6/22
6/23
全員の位置を先に求めておき，クエリにで答えていくことを考える．人の並びは(←←←){→→→←←←}{→→←}{→→←←}(→→)のような感じで左端，右端を除くとこのように向き合っている人たちのグループに分けることが出来る．この性質を利用して，始めに左端と右端を処理しておき，後はグループごとに位置を計算していく．→←の位置で2人が合流しているかどうかで処理を変える(合流する場合は合流点を超えないようにminやmaxを取る)．
まず，ゾンビに侵略された街からの最短距離を，ダイクストラ法によって求める(始点を最初にpriority_queueに全部pushしてしまえばよい)．そして，それが終わったら辺をコストを変えて貼り直す．侵略された街と繋がるような辺は張らず，危険な街へ入っていく辺はコストq，危険ではない街へ入っていく辺はコストp，ゴールとつながっている辺はコスト0というふうに重みつき有向グラフとして考えると，宿泊料がそのまま辺の重みとして反映することのできるグラフを構成できるので，あとはこのグラフに対してダイクストラ法を使うとよい．
dp[i]=i以降のオレンジを箱にまだ入れていない(i-1番目までのオレンジは入れ終わった)時の最小コストを持ちながら更新していく．1つの箱に入れられる個数が個と定まっているので，時間計算量は
である．
今いる頂点，現在の速度，1つ前にいた頂点を状態にもちながらBFSしていく．
6/24
再帰で調べながら頑張ってnext_permutationの枝刈りをした．めっちゃバグらせまくったし，他の解答みたらもっと頭良さそうで悲しかった．
6/25
ARC 056に参加
ABCの3完．ARCで3完できたのって本当に久しぶりな気が...
6/26
斜めを調べるときに，a<=cという条件を入れてなくて無限にWAを出し続けた...
6/27
まず始めにワーシャルフロイドで全頂点間の最短経路を求めておく．そして，クエリごとにワーシャルフロイドをやり直してしまうと間に合わないが，ついかされるのはx,y間の道路だけであるから，その影響をうける部分だけを更新するようにすれば良い．これでクエリごとの計算量がに落とすことが出来る(submission)．
両端が-1じゃないいくつかの区間に分けることができて，それぞれの区間に対して数字の組み合わせは重複組合せとして考えることが出来る．そして，その組み合わせは5C3だったら543/321のように計算すれば良い．分母の方は逆元を取ることで計算できる．nCrがn!/r!(n-r)!で計算できるが，今回はこれだとnが非常に大きくなって間に合わなくなるので，この公式を使うことは出来ない(submission)．
6/28
i番目のトッピングに注目，スペシャルチケット残りx枚，通常のチケット残りy枚の時の嬉しさの最大値でDP．ただ，DPするときに全ての遷移を考えるのは無駄で，スペシャルチケットの方が価値が高く，それでいて合計枚数の必要枚数に変化はないことからスペシャルチケットはできるだけ少なく抑えるほうが良いということになり，遷移は1通りだけしか考えなくて良いことになる(submission)．
まずありえない形のものを除外しておく．そして，深さi-1の頂点個数を，深さiの頂点個数を
とすれば，深さi-1と深さiの間に張る辺の組み合わせは
通り，深さi同士の間に張る辺の組み合わせは
通りとそれぞれ表せるので，繰り返し二乗法を用いてこの値を高速に計算すると良い(submission)．
dp[x][y]をsのx文字目までとtのy文字目までの文字列で題意を満たすことができるかというものを更新していく．dp[x][y]がtrueで，sのx+1文字目とtのy+1文字目が同じならdp[x+1][y+1]がtrue，さらにtのy+1文字目とy+2文字目が異なるならその先に挿入し続けて伸ばすことが出来るのでdp[x+1][z]も全てtrueになる．ただ，これをやるだけだと計算量が間に合わないので，一度更新し終わったところをもう一度やることがないように気をつける(submission)．
dp[x][y]=区間の終点x，この区間は止まる駅の区間か否かの組み合わせ数を持ってDPした．0を止まらない，1を止まると表すことにすると，止まらない区間はいくら長くてもいい(ただし区間の長さが1以上でないといけない)のでとなり，一方止まる区間は
個連続では止まれないので止まれても最大
個までということになり，
というそれぞれの漸化式が立てられる．このdpの計算に関して，それぞれ0と1に対して累積和を保存して更新しながらこのdpを進めていくことで，
で計算を終えることが出来る(submission)．
6/29
愚直にシミュレーション．
