2017/11/01の精進

・ARC060E 高橋君とホテル a番目のホテルからb番目のホテルまでなるべく早く移動する方法をかんがえると、明らかに今いるホテルから1日でたどり着けるできるだけ遠いホテルに移動することを繰り返すだけ。(a>bのときはスワップすればいいので常に移動先は右…

2017/10/31の精進

・ARC058E 和風いろはちゃん XYZを含まない数列の個数を数えて全体から引くことにする。 XYZを含まない長さi+1の数列は、XYZを含まない長さiの数列にXYZが生じないように数を1つ加えたものである。 ある数を加えたときXYZが生じるか判定するために末尾の数が…

2017/10/23の精進

AtCoder400点埋め いまさら編集距離のDPを知った。1文字挿入・1文字削除・1文字書き換えの操作を何回すれば文字列sからtにできるかを「編集距離」と呼ぶ。 これはdp[i][j]=sの先頭i文字とtの先頭j文字の編集距離とすると、dp[i][j]=min(dp[i-1][j]+1,dp[i][j…

2017/10/22の精進

AtCoder400点埋め ・ARC074C Chocolate Bar 適当な所で縦(横)に分割して、のこりを出来るだけ均等に分割するときだけをかんがえればいいとわかる。 ・ARC075D Widespread にぶたん。k回爆発を起こすと全モンスターにB*kのダメージが入り、追加でA-Bのダメ…

2017/10/21の精進

AtCoder400点埋め ・ABC051D Candidates of No Shortest Paths ワーシャルフロイドで全点対に対して最短距離を求める。頂点iから頂点jまでの最短距離をdist(i,j)、頂点iと頂点jを結ぶ辺のコストをedge(i,j)としたとき、dist(s,i)+edge(i,j)==dist(s,j)となる…

2017/10/12の精進

・ARC 081E Don't Be a Subsequence 文字列Aを末尾から見ていってa-zが全て現れるごとにくぎっていく するとAは[a-zのすくなくとも1文字が無い区間][a-zがある区間][a-zがある区間]...[a-zがある区間]に分割される ここで[a-zがある区間]がk個取れたとすると…

2017/10/11の精進

昨日は家に帰ってすぐ寝てしまって更新できなかった(老人) ・yukicoder No.155 生放送とBGM 戻すDPの練習 まずLが曲の長さの和以上の場合、全ての曲が1回以上再生されることは明らかなので、Lは曲の長さの和未満とする 期待値の線形性(和の期待値は期待値…

2017/10/09の精進

戻すDPという手法を知った ・ARC 028 D 注文の多い高橋商店 まずN種類の商品があってi種類目の商品がa[i]個あるとき、合計M個選ぶ方法が何通りかというのは蟻本に載っている問題(重複組み合わせ)で典型 dp[i+1][j]=i種類目までからj個選ぶ方法が何通りか …

CodeFes2017予選B C問題めも

C: 3 Steps - CODE FESTIVAL 2017 qual B | AtCoder 昨夜のコンテストの問題 なんとか時間内に出来たけど、二部グラフの性質あたりがあやふやだったので自分用メモ 「頂点uからちょうど3本の辺を辿ることによって頂点vに辿り着けるような(u,v)をとって頂点u…

2017/10/08の精進

いまだ上手い(バグらせない)木DPの書き方がわかってない プロの実装を学んだりするのも重要かもしれない ・yukicoder No.196 典型DP(1) dp[i][j]=subtree(i)のうちj個の頂点を黒く塗る方法が何通りか とすると頂点iを黒く塗るときはその下も全て黒く塗るの…

2017/10/07の精進 & DDCC2017予選

今日も木DPやっていくぞい ・TDPC N 木 結構悩んだけど自力で出来た(わからなくて寝て朝飯食ってたら浮かんだ) 書き方が自由すぎて困るので、制約をつけて dp[v]=頂点vを含む連結成分を順次大きくしていってsubtree(v)を書く方法は何通りあるか というDPを…

2017/10/06の精進

ACするたびに記録をつけていって一日の終わりに投稿しようかな(これを書いているのは朝) さて、今日は木DPをやる ・ABC 036 塗り絵 dp[v][i]=頂点vを色i(0:白 1:黒)で塗るとき、subtree(v)の塗り方は何通りか ・yukicoder No.417 チューリップバブル 最…

2017/10/05の精進

とりあえず色んなテクニックの練習問題をやっていこうということで、はまやんさんの問題集(競技プログラミング練習問題集 - はまやんはまやんはまやん)をやることにした 今日は動的計画法問題まとめの入門問題を埋めたけど、さすがに簡単だった 明日は木DP…