公式解説見ればOK こういう系結構出るから気をつけないとね セーブしうる所を全部持って(実装上Nも入れとくと楽)lower_boundで毎回探して30個くらい回せばOK.実装苦手なのでこういうのですら詰まるんだよなあ・・・ #include <bits/stdc++.h> #define rep(i,n) for(int i=0;i</bits/stdc++.h>…

適当に書いてダメだったら考えようと思って書いた奴が通ってしまった(まあ大丈夫そうではあったけど) 公式解説がないのでだれか教えて 解法:とりあえず道を無視すると45度回転して中心(座標幅の真ん中)がうれしい.道があってもだいたいそこら辺だろ(ヘラヘラ…

読解3,発想1,ライブラリ0,実装3,やる気4 そんなに難読ではないんだけど,1200+の特性上まず読もうとしてめんどくなってCruel Bingoとかに逃げる とかのパターンから逃げるのが難しい ちゃんと読むと解法は一瞬で生える(多分この部分だけだと300点位じゃないか…

A-Bにしかよらないのはまあわかる.A-Bは広い範囲の値を取るので,美味しみの方でメモりたくなる.dp[i][j]="i個目以降で(先手が)おいしみjを得るのに必要なエネルギー格差"を持って更新すればいいです.初め逆シミュレーションみたいなのをして頑張って更新をO(…

これは1100だと思う 知識5+,頭3,実装力1,ライブラリ力1問題: 正の重み付きDAGで,さらに,任意のiに対し0->i->N-1となるpathがあるものが与えられる.0からN-1への最長距離を変えないように辺の重みを0位上の整数増やす.どれだけ増やせるか.N

知識4 頭0 実装1 気合1 英語0 700点くらい問題 文字列s,t(長さ50000まで)が与えられる.s[i..j]=t[k...l]かつこれが回文 となるi,j,k,lの組は何通りか.

500点問題: lowercaseからなる文字列(長さ200まで)がN(複数回使っても良いし,一回も使わなくても良い)できる長さM(

苦行だった・・・問題: H*Wのマス目がある.それぞれを#か.で塗る いくつかは既にどれで塗るか決まっている.残りのマスの塗り方のうちもっとも#が多いもののマス目全体の#の数を答えよ.正しいかの条件を満たして塗る必要がある".は連結(4-neighborsで)しない"…

H*Wのグリッドで各マスは白か黒で塗られている.H*(W-1)+(H-1)*W個の壁それぞれを立てるか立てないか決めて,全体が連結でサイクルが無いようにする方法は何通りか.迷路→全域木→行列木定理 O(N^3) (N=H*W=7500) だし無理 W=15だしbitDP?→上から埋めてくと実は…

問題を見た瞬間にやるべきことがわかるのでやるだけ・・・ やるだけ・・・（◞‸◟）（◞‸◟）（◞‸◟）（◞‸◟）まず列で考えると,sum,l,r,mx(それぞれ、区間の総和,左と連結してる時の最大,右と〃,sub区間のmax)を持つsegtreeが必要とわかる(これの強いバージョンを…

何がむずいねん(バグりました。) 累積和を取るとただの隣同士のswapに帰着できて,冷静に考えるとl[i]>0だから累積和たちをマージソートする必要がある.しておわり.なんで1000点なんだ、500点位だと思う. #include <bits/stdc++.h> #define rep(i,n) for(int i=0;i<(int)(n);</bits/stdc++.h>…

場合分けをするだけ. とりあえずK点あれば基本K(K-1)/2本できる.a>=3点がcolinearならそっからa(a-1)/2-1本減る.(a=3から順に,2,5,9,14,20...) 大体K(K-1)/2がNを超えるようなKをとればできて(ただし余分が1か3だと無理),その時余分はだいたいKくらいなので,…

通した.↓ネタバレ

解きました 以下ネタバレ

n( 回復薬がP(dp[i][j]="i回攻撃受けた時点での回復薬使用状況(bit)がjの時の体力のmax"を持てば良さそう.それぞれの状態からどの回復薬のsubsetを使うか、を考えるとO(n*P*3^P)となり死亡. よく考えると、回復薬aとbを使いたいときはaを使った状態を(その回…

上から,反省もこめて Merry Christmas(2251)☆ transitiveDAGの二部マッチングのアレReverse Sort(2443) 半分探索,知らなかったので勉強になった ちなみに始め単にdfsという解法に固執しまくっていて2443という数字を覚えてしまい、後日(Code Formula?)snuke…

蟻本での最小費用流の扱い方としては, 1.毎回Bellman-Fordで残余グラフ上を見る 2.ポテンシャルhを考えるとdijkstraで出来る 3.(column)負辺ののぞき方紹介(使う本数が必ず等しい場合,負辺を流しきったと考えた時の変形,あとはBellman-Fordを使おうとも書い…