kitayuta

すたっきゅんすたっすたっきゅんすたっすたっきゅんすたっすたっきゅんすたっすたっきゅんすたっすたっきゅんすたっすたっきゅんすたっすたっきゅんすたっすたっきゅんすたっきゅんきゅんすたっすたっすたっすたっすたっきゅんすたっすたっきゅんすたっすたっきゅんすたっすたっきゅんすたっすたっきゅんすたっすたっきゅんすたっすたっきゅんすたっすたっきゅんすたっすたっすたっすたっすたっきゅんすたっすたっきゅんすたっすたっきゅんすたっすたっきゅんすたっすたっきゅんすたっすたっきゅんすたっすたっきゅんすたっすたっきゅんすたっすたっきゅんすたっすたっきゅんすたっすたっきゅんすたっすたっすたっすたっすたっきゅんすたっすたっきゅんすたっすたっきゅんすたっすたっきゅんすたっすたっきゅんすたっすたっすたっきゅんすたっすたっきゅんすたっすたっきゅんすたっきゅんきゅんきゅんきゅんきゅんすたっすたっすたっきゅんすたっすたっすたっすたっすたっすたっきゅんすたっすたっきゅんすたっきゅんすたっすたっすたっきゅんすたっすたっきゅんすたっすたっきゅんすたっすたっきゅんすたっすたっきゅんすたっすたっきゅんすたっすたっきゅんすたっきゅんすたっすたっきゅんすたっすたっすたっきゅんすたっすたっきゅんすたっすたっきゅんすたっきゅんすたっすたっすたっすたっすたっすたっきゅんきゅんきゅんすたっすたっすたっきゅんきゅんすたっきゅんきゅんすたっきゅんきゅんすたっきゅんきゅんすたっきゅんきゅんすたっきゅんきゅんすたっきゅんきゅんすたっきゅんきゅんすたっきゅんきゅんすたっきゅんきゅんすたっきゅんきゅんすたっきゅんきゅんきゅんすたっすたっすたっすたっきゅんすたっきゅんすたっすたっきゅんすたっすたっきゅんすたっすたっきゅんすたっすたっきゅんすたっすたっきゅんすたっすたっきゅんすたっすたっきゅんすたっきゅんすたっすたっすたっきゅんきゅんすたっきゅんきゅんすたっきゅんきゅんすたっきゅんきゅんすたっきゅんきゅんすたっきゅんきゅんすたっきゅんきゅんすたっきゅんきゅんきゅんすたっすたっすたっきゅんすたっすたっきゅんすたっすたっきゅんすたっきゅんすたっすたっすたっきゅんきゅんすたっきゅんきゅんすたっきゅんきゅんすたっきゅんきゅんすたっきゅんきゅんすたっきゅんきゅんきゅんすたっすたっすたっきゅんきゅんすたっきゅんきゅんすたっきゅんきゅんすたっきゅんきゅんすたっきゅんきゅんすたっきゅんきゅんすたっきゅんき

kitayuta

#include<cstdio>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<cmath>
#include<iostream>
#include<sstream>
using namespace std;
typedef long long ll;

kitayuta

#include<cstdio>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<cmath>
#include<iostream>
#include<sstream>
using namespace std;
typedef long long ll;

kitayuta

main = print $ binsearch (\x -> x^2 - 2) (0,10) 1e-20

binsearch :: Fractional a => Ord a => (a -> a) -> (a,a) -> a -> Maybe a
binsearch f (from,to) eps =
  if (f from)*(f to) > 0 then Nothing
  else Just $ binsearch' (from,to) from
  where
--     binsearch' :: (a,a) -> a -> a
    binsearch' (from',to') bef =
      let mid = (from'+to') / fromRational 2

kitayuta

#include<cstdio>
#include<vector>
#include<algorithm>
#include<set>
#define men(d) (((d.vx*d.vx)+(d.vy*d.vy))/2)
using namespace std;
struct Data{
    short vx,vy,cx,cy;
    Data(short a,short b,short c,short d){
        vx=a;

kitayuta

#include <cstdio>
#include <iostream>
#include <cmath>
#include <climits>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <algorithm>
#include <functional>

kitayuta

#include<cstdio>
#include<vector>
#include<algorithm>
#include<cmath>
using namespace std;
vector<pair<double,pair<int,int> > > edges;
vector<int> parent;
int find(int a){
    if(parent[a]==a)return a;
    else return parent[a]=find(parent[a]);

kitayuta

#include <cstdio>
#include <map>
#include <vector>
#include <climits>
using namespace std;
typedef pair<int,int> P;
map<P,int> dp;
vector<vector<int> > edge;
int solve(int from,int to){
    P pa(from,to);

kitayuta

このアルゴリズムは(m,n)のk番目に小さい経路長をまず求め、次にその経路の数を求める、という二段階に分けられる。

1. (m,n)のk番目に小さい経路長(44行-109行,214行-325行)
   まず、大まかなアルゴリズムについて述べる。
   各格子点に対し、1からk番目までの経路長を求めることを考える。(この結果として(m,n)のk番目に小さい経路長も求まる)
   一般に、各格子点に対し最短経路長を求めたい場合、ダイクストラ法を用いるのが適している。ここではそれを応用する。すなわち、普通のダイクストラ法では最短経路となるものだけを記録しておくのに対し、ここではk番目に短い経路までを記録しておく。
   次に、細かな点について述べる。
   * ダイクストラ法ではヒープを用いたプライオリティーキューを用いると計算量が少なくてすむため、二分ヒープを実装し、利用している。(66行-109行)
   * このアルゴリズムにおいては、ある格子点に対してn番目(nはある整数)の経路長が求まった後、その格子点に隣接する格子点のそれぞれに対しm番目の経路長(mはある整数)の候補ができる。その候補を記録しておくとき、記録しておく記憶領域の始めから、どこに記録するか順に探していくと時間がかかってしまうが、記録する必要があるのかどうか、及びある程度どの範囲の場所に記録すればいいのかを調べておくことで少ない時間で候補の記録が行える。(249行-299行)

kitayuta

#include <cstring>
#include <climits>
#include <algorithm>
#include <cstdio>
using namespace std;
typedef unsigned long long ull;

const ull B=10000007;
const int INF=INT_MAX/2;
int mins[150000];