クリスマスですね。日本語の解説記事がなかったので。 まずは普通に dp[i][j]:=i番目のポールを高さjにする時のそこまでのペナルティの合計の最小値 (不可能なときはINF)として漸化式をたててみると dp[i][j] = min{dp[i-1][k]+abs(k-j)*C | 0 となりますが…

はい、というわけでもちろん今年も参加しました。 が、残念な結果に終わったので本選まで今まで以上に精進しようと思います。 適当な解説を書きます。テンプレはいつも通り省略してます 1.水道料金 (Water Rate) やるだけ。 int A,B,C,D,p; int main() { cin…

先日、PCK2014にチーム「三上」として参加してました。 色々あったので、箇条書きでつらつら書いておきます。 こんなにどうでもいいことをだらだら書いているのは、自分が読み返した時にいろいろ思い出せるようにするためです。冗長でごめんなさい。 Day 0 …

問題概要 回文をつくろう3280 -- Cheapest Palindromeに文字をchangeする操作が加わっている。 基本的にはその問題と同じように区間DPをする。 ただしchangeが加わっているため、changeしてからerase,みたいなことができる。 まずchange操作はワーシャルフロ…

問題概要 問題文を読んでください。まず数列を二つに分けて、それぞれの最大値の合計の最大値を求める。 分けたあとの数列の任意の2組を取ってきて、小さいほうを初項、大きいほうをx番目として、フィボナッチ数列を計算して、含まれる要素の数をかぞえる。(…

dp[W][H]:=上からH段目まで横幅Wのブロックの置き方 #include <cstring> using namespace std; typedef long long ll; #define MOD 1000000007 class BricksN { public: ll num[55]; ll dp[55][55]; ll rec(int W,int H) { if(H==0||W<=0)return 1ll; if(dp[W][H]!=-1</cstring>…

問題概要 記憶力がすごい人がNM枚のカードで神経衰弱をした時のゲーム終了時までのターン数の期待値を求めよ。dp[i][j]:=全く見たことないのがi組、片方だけ見たことあるのがj組のときの終了までのターン数の期待値dp[i][j]からの状態遷移は残ってる2i+j枚の…

やるだけ こんな問題二度と解きたくない typedef long long ll; class BedroomFloor { public: ll num[6]={0}; long long numberOfSticks(int x1, int y1, int x2, int y2) { ll ans=0ll; int lx=(x1/5+((x1%5!=0)?1:0))*5; int rx=(x2/5)*5; int uy=(y1/5+(…

PCK本選までにDiv1 Med 100問解きます。って言ったので頑張ります。 これが1問目。 問題概要:最小全域木で、使った辺の長さの標準偏差が最小のものをの値を答えよ。 はじめ、標準偏差の定義式からして使う辺の長さは同じ位に固まってるほうがいいかなと思っ…

予選終わったけど去年の予選一人でやってみました。 今年よりも少し難易度高いかな〜と思った1〜6真にやるだけなので省略 7 更新が一点にしか来ないから普通にsegtreeで数えてあげればイイ #include <cstdio> #include <algorithm> using namespace std; typedef pair<int,int> P; #defin</int,int></algorithm></cstdio>…

有向グラフが与えられるのでそれがオイラーグラフかどうか判定する問題。 無向の時はすべての頂点が偶数であればいいが有向グラフのときはすべての頂点で入次数と出次数が等しければ良いらしい。この際まとめておくと 無向グラフがオイラー閉路を持つ ⇔ すべ…

学校についてからしばらく問題を解いたりする 12:40頃にしぇかにいく うまい 帰ってきたら開始数分前になっていた。ここで印刷まわりの準備ができていないことに気づく 絶望しながら予選開始 とりあえず全部落とす 5,6,7あたりに目を通す やるだけ 1,2,3,4を…

下書き保存したまま忘れてました Day1 10時半ごろに新大阪に着く 新幹線のなかでcatupperさんとstibearさんに合流 京都でsatashunさんと合流 新幹線のなかで折り紙を折ったりする 東京に着いたらcatupperさんと別れて3人で新宿に行く ラーメン二郎にいくと混…

ソースは全部 okuraofvegetable/PKU · GitHub にあげてます。 2247 全部列挙 2371 やるだけ 1007 適当に数えてペアでソート 1008 めんどくさいだけ 1013 全探索 1046 三平方で全部しらべる 1050 2次元imosしてあとは全部調べる 2840 やるだけ 2182 後ろの牛…

最初みたとき解法が全然わからなかったけど以下の2点に気づくだけだった ・フィボナッチ数列同士を足した数列もフィボナッチ数列である ・初項、第2項がa,bのフィボナッチ数列の第n項は基本のフィボナッチ数列をfib[n]としてa*fib[n-1]+b*fib[n-2]とO(1)で求…

二人の座標を(a,b),(c,d)とする。(ただしa すべての円について、二人を結んだ線分と交点があるか判定する。 i)a=cの時 適切に処理してあげる。 ii)else 円の中心を(p,q),半径をrとする。 二点を通る直線の方程式はy=(d-b)/(c-a)*x+(bc-ad)/(c-a); 傾きをm,y…

にぶたん。中の操作はsegtreeでごにょごにょする。O(NlogN^2) 前回やったときはわからなくて答え見たけど今やってみたら割と簡単だった。 int n; const int SIZE=1<<19; P seg[SIZE*2]; struct segtree { segtree() { for(int i=0;i<SIZE*2;i++)seg[i]=P(0,0); } void update(int k,int x) { k+=SIZE-1; seg[k].fi=x; seg[k].sec=k-(SIZE-1); while(k>0) { k=(k-1)/2; seg[k]=m</size*2;i++)seg[i]=p(0,0);>…

Starry Sky Treeで最大値のindexがわからない〜って言ってて、英語の授業中に根からたどればいいだけという事に気付いた時に本当に自分には頭がないのだなぁと思った— 894 (@okuraofvegetabl) 2014, 5月 29 obstacleたちをソートして、順番に処理していく。 …

貪欲。valueの条件から価値の低いコインをたくさん使うより高いコインを1枚つかうほうが後で小回りが効くのでよい。最初、Cを超えないように大きい方から取っていって、それでもCより少なかったら価値の小さいほうからC以上になるまで取っていった。 なるべ…

LCA求めて距離出すだけ。 最初Navigation Nightmareのinputの形式と同じなのでマンハッタン距離かなぁと思っていたけど入力の方角関係ないらしい。意味不明。 最初ダブリングでやったらなぜかTLEが取れなかったのでeuler tour+RMQで書きなおしたら通った。 …

やるだけ。実装が重い(?)せいかなぜか非公式難易度表では8。 あらゆるテストが迫っているので今日はコレだけ。 int N,M,K; struct edge{int to,dir,cost;}; struct query{int from,to,turn;}; vector<edge> G[40010]; P dist[40010];//fi:East sec:North query Q[4</edge>…

問題としてはクソ簡単なのですが時間制限がキツい。 mapでは間に合わないのでロリハかTrieでやらないとダメだと書いていた人がいましたが、mapで通りました。 #include <string> #include <sstream> #include <iostream> #include <map> using namespace std; map<string,string> ma; int main() { string s;</string,string></map></iostream></sstream></string>…

Codeforces #239 C Curious Array 解法がわかった時感動した。問題は至ってシンプルで(l,r,k)のクエリがたくさん飛んでくるから配列のlからr番目までに(j-l+k)C(k)(l≦j≦r)を足す。初期値は関係ないので後で足せばOK。 最初nCr=n-1Cr+n-1Cr-1を使って色々変形…

腹が立つ。 Easy やるだけ。 class WakingUpEasy { public: int countAlarms(vector <int> volume, int S) { int sz=volume.size(); int sum=0; for(int i=0;i</int>

これからはCFやTCのメモを書いていこうと思います。(あくまで自分で見返す用なので適当になるとは思いますが許してください) あと、テンプレはもう書きませんが許してください。 A やるだけ。 int a[105]; int main() { int n; cin >> n; for(int i=0;i<n;i++)cin >> a[i</n;i++)cin>…

https://twitter.com/okuraofvegetabl/status/437286426967699457 人間は、クソ。 じゃなくて、 俺が、クソ。 #include <cstdio> #include <algorithm> using namespace std; typedef long long ll; const int SIZE=1<<19; struct node { ll gcd,left,right,lazy; node(ll gcd=0</algorithm></cstdio>…

先日、JOIの本選に行って来ました。 結論から言うと、クソみたいな点数をとって落ちました。 春合宿までは必ず行こうと誓っていただけにとてもつらいです。 精進が足りなかったんだと思います。 以下、競技やらその他の感想についてつらつら書きたいと思いま…

少し遅くなりましたが今年の目標を書きます。 抱負を豊富に書きたいと思います。 …はい、すいません。 まず2013の状況を。 ・Codeforces okuraofvegetable 1509(最高1628) ゴミすぎます、成長が感じられずとてもつらいです… good bye 2013 で紫になれるかな…

ところでついさきほど AOJ Vol5 全 完 し ま し た ギリギリ2013年のうちに達成できました。詳しいことは後々書こうと思います。 2013年は競技プログラミングに出会い、様々な体験ができ、今までで最も充実した一年だったと思います。 もう2013年が終わる4分…

とりあえず本選5番を2つ倒しました。 まずはBug Partyから。 解法 問題名が縁起悪いですね（笑） … … 実際バグらせまくりました（汗） と同時に重大な勘違いに気づくことができました。 K匹同時に入れられるかどうかで二分探索します。 同時に入れられるかを…