n整数からなる集合がm個与えられて、おのおのから1個ずつ選んでその和をとった時にそれが小さい組み合わせから順にn個列挙せよという問題。POJの鯖遅いしいくらなんでもO(mn^2log n)は通らないだろうなと思ってたら、怪しい二分探索のO(mnlog^2n)解を見つけ…

POJ200AC.一応メモ程度に。 期末とかいう何かで3週間中断されてたから妥当な速さかもしれない。

USACO U S Openの問題。数直線上に点がN点与えられ、それらの2点の間のコストが(その間の距離)*(2点の持つ値の大きい方)で定められているので、すべての2点間のコストの総和を求める。BITを2個持っておいてやって、"座標の合計"と"そこまでにある点の数"を持…

PCKの問題のはず。 普通に文字列のままやったらTLEして腹が立ったのでローリングハッシュ書いた。 結果、rank6位に。わーい。 http://poj.org/problemstatus?problem_id=3007 #include<stdio.h> #include<vector> #include<algorithm> #include<string> #include<iostream> using namespace std; typedef pa</iostream></string></algorithm></vector></stdio.h>…

題名は問題名なのであしからず。2-SATに見えて考えてたらわけがわからなくなり考え直したら無向グラフだったことが判明。 思い切りunion-findが役立つ。UFかわいいよUF。 #include<stdio.h> #include<algorithm> #include<vector> #include<math.h> #include<string> #include<iostream> #include<stdlib.h> using namespace s</stdlib.h></iostream></string></math.h></vector></algorithm></stdio.h>…

良問だと思う。文字列の長さをL,文字列数をNとすると,O(N L^2 log N). TLEぎりぎりでAC. #include<stdio.h> #include<vector> #include<algorithm> #include<string> #include<iostream> using namespace std; typedef pair<string,int>psi; typedef pair<int,psi>pisi; int len[10000]; int frm[10000]; int main() { vector<string>zvec</string></int,psi></string,int></iostream></string></algorithm></vector></stdio.h>…

A,B:やるだけ。なのに低速submitC:わからないので飛ばす D:わかった気になったら嘘解法だった E:unopened結果:175位 rate:1793->1796(+3)

何でもいいから解を一つ求めればいいので、適当に山登り&登りきれなかったらrandom_shuffleで適当に書く。通る。(多分嘘解法じゃないはず)K #include<stdio.h> #include<vector> #include<algorithm> #include<stdlib.h> using namespace std; typedef pair<int,int>pii; int main() { int num; scanf("%d",&</int,int></stdlib.h></algorithm></vector></stdio.h>…

解いてる人が233人で難しそうとか思ったけど考えてみると普通にgreedyに選んでいけばいいだけということに気付く。なんでこんなに通してる人少ないんだろう。 #include<stdio.h> #include<vector> #include<algorithm> #include<set> #include<queue> using namespace std; #define mt(A,B,C) make_pa</queue></set></algorithm></vector></stdio.h>…

しばらく更新さぼってましたね。すみませんね。いつの間にかTCでDiv1に上がっていたのになぁ。さてこの問題。適度な数学ゲーで楽しい。 #include<stdio.h> #include "stdafx.h" #include<vector> #include<algorithm> using namespace std; int main() { for(;;) { int num,cho; scanf("%</algorithm></vector></stdio.h>…