問題 Editorial 問題 無向重み付きグラフで以下の条件を満たすものgraphが与えられる： それぞれの頂点に対して、たかだか1つの単純閉路に含まれる それぞれの頂点v,uに対して、vからuへのsimple pathはたかだか1つ 頂点start,finishと正整数kが与えられる。…

問題 Editorial 問題 数列initialが与えられる。 これの各々を移動させて、等差数列の並び替えにしたい。ただしそれぞれの数値は重複があってはいけない。 移動させるのに移動させた分だけコストがかかる。 コストを最小化せよ 2 -2*10^9 解答 Editorialを見…

問題 Editorial 問題 略 解答 二分探索*二部マッチング。 mid以下の時間でたどり着ける位置同士に辺を張って、完全マッチングが出来るかどうかで判定する コード #include <string> #include <vector> #include <sstream> #include <cmath> #define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i</cmath></sstream></vector></string>…

問題 Editorial 問題 (問題の肝の部分のみ) width*heightの長方形の中にx*yの長方形が回転してでも入るかどうかを判定せよ 全ての数値は整数, [1,1000] 解答 回転後の幅と高さは(x cosθ + y sinθ, x sinθ + y cosθ)。 それを適当にいろんな感じで二分探索し…

問題 Editorial 問題 床屋がある。 この床屋はAM 9:00に開店し、PM 5:00に閉店する。 床屋では常に1人までしかカットすることができない。 誰かのカットの最中に他の人が入ってきた場合、そのカッティングが終わるまで待たされる。キューの動作をする。 客が…

問題 Editorial 問題 H*Wのマップparkが与えられる。 parkはそれぞれ '.': 空白, 'X': 壁, 'C': 車, 'P': 駐車場。 車を全て駐車場に駐車させたい。1つの駐車場に1台までしか駐車できない。 車は同じマスを複数通ることができる(駐車場のマスでも、そこを通…

問題 Editorial 問題 略 解答 二分探索する コメント 簡単なのにバグらせて無駄に時間かかってしまった コード #include <string> #include <vector> #include <sstream> #include <cstring> #include <limits> #include <complex> #define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i)) #define reu(i,l,u) for(i</complex></limits></cstring></sstream></vector></string>…

問題 Editorial 問題 数列countriesと数値kが与えられる。 [0,|countries|)の中から重複なしでkつ選んだものの数を最大化せよ。 ただし、iはcountries[i]個までしか使えない。 2 k 1 解答 Editorialを読んだ。 単純に作る数を二分探索すればよい。 判定は(Su…

http://codeforces.com/problemset/problem/216/D 回答 数えるのに、全てを試すとO(n^2)で駄目なので、二分探索する。 コメント lower_boundやupper_bound関数できれいになると思う コード