そーすにっき

なんかいろいろのせておくばしょ

グラフのライブラリづくり(2/2 Updated)

遅い

概要

  • Dijkstra法, Bellman-Ford法, SPFA, Kruscal法, Unionfindを実装
  • Dijkstra法, Bellman-Ford法, SPFAのverify
  • Bellman-Ford法, SPFAの速度比較

モチベーション

  • いつも空で書いてたけど明らかに時間&労力の無駄で、バグも埋めるから作ってしまおうという気持ち
  • Dijkstra法はそもそも書いたことがなかったが解けていない問題埋めに必要だった)

verify

とりあえず

ついでにSPFAとBellman-Ford法の速度比較も
雑に1回だけ実行してtimeで計測
入力はこれを拝借しました
もちろんのことながらいずれもTLEの範囲

Bellman-Ford法

real 0m53.746s
user 0m53.704s
sys 0m0.040s

SPFA

real 0m46.151s
user 0m45.996s
sys 0m0.044s

やはりSPFAに軍配が上がった模様
むしろ上がらなかったらどうしようかと

Todo

  • Unionfind
  • フロー周り(あんまり実装しているものがないのでどうしよう)

コード(需要あるのか)

(2/2 流石に何も書いてないのは雑だなと思い)

  • edge
    • 辺データ(雑)
    • idは便利変数としてとりあえず設置 今後フローとか色々に使えるかなと
  • graph
    • add_edgeとsize()を持っただけのただのvector>
    • 2次元にしている理由は隣接リストの方が気持ちがよいから
    • size()を設置した理由はg.data.size()をg.size()と誤射するパターンが多い為(文字数も減るし)
  • dijkstra
    • バグ埋まってそう(もし見つけたら教えてください)
    • これ書く直前にspfaのqueueをpriority_queueにすればいいだけで実装できることに気づきげんなりした
  • spfa
    • みんな大好きSPFA(嘘)
    • いつもSPSP問題はこれにしていたけども、Dijkstra法じゃないとTLEする制約が厳しい問題が解けなくて困っていた…が、上記の理由によりこれからDijkstra法に逃げそう
  • bellmanford
    • みんな大好きBellman-Ford法(きっとこれは本当)
    • 負辺見つけられるよやったね!でもSPFAより遅いね!という気持ち
template<typename T>
struct edge{
    int f,t;
    T c;
    int id;
    edge(){};
    edge(int f,int t,T c,int id = 0):f(f),t(t),c(c),id(id){};
    bool operator< (const edge &s){
        return c < s.c;
    }
};

template<typename T>
struct graph{
    std::vector<std::vector<edge<T> > > data;
    graph(int v):data(v){};
    void add_edge(edge<T> &e){
        data[e.f].push_back(e);
    }
    void add_edge(int f,int t,T c){
        data[f].emplace_back(f,t,c);
    }
    size_t size(){
        return data.size();
    }
    std::vector<edge<T>> make_edges(){
        std::vector<edge<T>> r;
        for(auto &i:data)std::copy(i.begin(),i.end(),std::back_inserter(r));
        return r;
    }
};

template<typename T>
std::vector<T> dijkstra(graph<T> &g,int s){
    using state = std::pair<T,int>;
    //priority_queue
    std::priority_queue<state,std::vector<state>,std::greater<state>> q;
    q.emplace((T)0,s);
    //data init
    std::vector<T> data(g.size(),std::numeric_limits<T>::max());
    data[s] = (T)0;
    //solve
    while(!q.empty()){
        state cur = q.top();q.pop();
        T c = cur.first; int pos = cur.second;
        if(data[pos] < c)continue;
        for(auto &e : g.data[pos]){
            if(c + e.c < data[e.t]){
                data[e.t] = c + e.c;
                q.emplace(c + e.c, e.t);
            }
        }
    }
    return data;
}

template<typename T>
std::vector<T> spfa(graph<T> &g,int s){
    //queue
    std::queue<int> q;
    q.emplace(s);
    //data init
    std::vector<T> data(g.size(),std::numeric_limits<T>::max()/4);
    std::vector<bool> isq(g.size(),false);
    std::vector<int> count(g.size(),0);
    data[s] = (T)0;isq[s] = true;++count[s];
    //solve
    while(!q.empty()){
        int cur = q.front();q.pop();
        isq[cur] = false;
        for(auto &e:g.data[cur]){
            if(data[e.f] + e.c < data[e.t]){
                data[e.t] = data[e.f] + e.c;
                if(++count[e.t]>=g.size()){
                    fill(data.begin(),data.end(),std::numeric_limits<T>::min());
                    return data;
                }
                if(!isq[e.t]){
                    q.push(e.t);
                    isq[e.t] = true;
                }
            }
        }
    }
    return data;
}

template<typename T>
std::vector<T> bellmanford(graph<T> &g, int s){
    const T INF = std::numeric_limits<T>::max()/4;
    std::vector<T> data(g.size(),INF);
    data[s] = 0;
    for(int i=0;i<g.size()-1;i++){
        for(auto &v:g.data)for(auto &e:v){
            if(data[e.f]==INF)continue;
            data[e.t] = std::min(data[e.f] + e.c,data[e.t]);
        }
    }
    for(auto &v:g.data)for(auto &e:v){
        if(data[e.f]==INF)continue;        
        if(data[e.f] + e.c < data[e.t]){
            fill(data.begin(),data.end(),std::numeric_limits<T>::min());
            break;
        }
    }
    return data;
}

POJ 1990 - MooFest

久々のソースコード投稿になりますん

問題:

一次元直線上に一列に並んだ牛に座標x_i,値v_iが与えられる

 \sum_{i \in N, j \in N} max(v_i,v_j) | x_i - x_j |

の値を求めよ.

問題の難しい点:

簡単に見えて制約が厳しい.

 |N| = 20000,x \ in {1,2,\cdots,20000}(\Leftrightarrow |x| = 20000 = |N|), time = 1000ms

この制約上+POJでは O(|N|^2)許されない.

そこでどうにかしてやる必要がある.

解法:

色々方法はあると思うけどとりあえずセグ木でRange Sum Queryをすることにした.

 \sum_{i \in N, j \in N} max(v_i,v_j) | x_i - x_j |

v_i < v_jの下で

 \sum_{i \in N, j \in N,v_i < v_j} v_j | x_i - x_j |

であるからとりあえずvで昇順ソートして以下 i < j とする.

次にx_i < x_j であるiの集合を L_j , 補集合をR_j とおく.すると

 \sum_{j \in N} \left( v_j \left( |L_j| x_j - \sum_{i \in N, j \in N, i \in L_j} x_i  \right) + v_j  \left( \sum_{i \in N, j \in N, i \in R_j} x_i - (|R_j|) x_j \right) \right)

 |L_j|,\sum_{i \in N, j \in N, i \in L_j} x_i はそれぞれRSQにデータを保持すると更新、算出共にO(log |x|)で計算できる(R_j側についても同様).

これを j \in Nについてfor文を回すということで全体O(|N|log|x|)で計算可能.制約より |N| = |x|なのでこれなら定数が重くない限り制限時間内に間に合う.

若干添字周りに\pm 1が入るかもしれないが気にしない

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

template <typename T>
class segtree_sum
{
  public:
    vector<T> data;
    int size;
    segtree_sum<T>(int size_) : size(1)
    {
        while (size < size_)
            size <<= 1;
        data.assign(size * 2, 0);
    }
    segtree_sum<T>(vector<T> &src) : size(1)
    {
        while (size < src.size())
            size <<= 1;
        data.assign(size * 2, 0);
        for (int i = 0; i < src.size(); i++)
        {
            update(i, src[i]);
        }
    };
    void update(int idx, int v)
    {
        int f = idx + size - 1;
        data[f] = v;
        while (f)
        {
            --f /= 2;
            data[f] = data[2 * f + 1] + data[2 * f + 2];
        }
    }
    T rsum(int l, int r)
    { //return sum[l,r)
        int f = l + size - 1;
        int k = 1;
        while (f % 2 && l + k * 2 <= r)
        {
            f /= 2;
            k *= 2;
        }
        if (l + k > r)
            return 0;
        else if (l + k == r)
            return data[f];
        else
            return data[f] + rsum(l + k, r);
    }
};

/////////////////////////////////////////////////////////////////////////

bool compare(pair<int, int> a, pair<int, int> b)
{
    return a.first < b.first;
}

#define i64 long long int

int main()
{
    int n;
    cin >> n;
    vector<pair<int, int> > moo(n);
    for (int i = 0; i < n; i++)
    {
        cin >> moo[i].first >> moo[i].second;
    }
    sort(moo.begin(), moo.end(), compare);
    segtree_sum<int> l_cows(20010);
    segtree_sum<int> l_x(20010);
    i64 res = 0LL;
    for (int i = 0; i < n; i++)
    {
        int moot = moo[i].first;
        int moox = moo[i].second;
        i64 lcows = (i64)l_cows.rsum(1, moox);
        i64 lx = (i64)l_x.rsum(1, moox);
        i64 rx = (i64)l_x.rsum(moox + 1, 20001);
        res += (i64)(lcows * moox - lx) * moot;
        res += (i64)(rx - (i - lcows) * moox) * moot;
        l_cows.update(moox, 1);
        l_x.update(moox, moox);
    }
    cout << res << endl;
}

久々に記事書いた気がする

あけましておめでとうございます(遅)

あけましておめでとうございます(6日遅れ)

1月7日だけどあけましておめでとうございます

今年の目標を暢気に載せておきます

  • ちゃんと大学を卒業する(卒研が心配でたまらない人)
  • Atcoder青になる(出来ればICPCの前に!)
  • ICPCつくば予選50位以内を目指す(要はDをACしたい)
  • DDCC、CODE (THANKS) FESTIVALに出る(優遇年次を外れたので難易度UP)
  • RubyPythonをちゃんと読み書きできる人間になる(特にPython

後は記事にならないネタとして

  • 独検4級以上を取得する(一度ドイツにビールではなくワインを飲みに行きたい)
  • C++refを全部読む(予約語全部覚えて使える程度にはなりたい)

なんてのも一応

CODE THANKS FESTIVAL

略してCTF(違)

結果:96th/99

AC:A,B,D

これはひどいという有様

A:一発目からCEをかます
原因:10分前あたりからのんびり打ってた上側のテンプレのstruct edge{...};のセミコロンが落ちてた
C/C++初心者かよぉ…とだいぶひどいため息をつく

B:なんか色々考えたけど最初に思いついたのは単にひっくり返してくっつければよいではないかと
ここでテンプレにstring.hが入っていないことに気づきAのCEも合わせて余計に焦る

C:最悪だった
冒頭でpriority_queueで行けるのでは?(これが正解)
が、priority_queueの更新コストをO(size)と勘違いする痛恨のアホをかましあろうことか選択肢から消してしまう
結果WAを叩きまくり、AC出来ず

D:5WA叩きながらもAC
すぐに互いに素な整数の余算の値の周期性からGCDと思いついたがそこからミスが多かった

E以降は読んでも全然ちんぷんかんぷんだったのでア

#include <vector>
#include <deque>
#include <iostream>
#include <cstdio>
#include <set>
#include <map>
#include <utility>
#include <iomanip>
#include <algorithm>
#include <limits>
#include <random>
#include <string>

using namespace std;
using i64 = long long int;
using ui64 = unsigned long long int;
using f64 = double;
using f80 = long double;
using EDGES = vector<int>;
using GRAPH = vector<EDGES>;
 
struct edge{
    int f,t,c;
    bool operator<(const edge &e){
        return c < e.c;
    }
};
 
 
/////////////////////////////////
//a
int main(){
    int res = 0;
    int a;
    for(int i=0;i<8;i++){
        cin >> a;
        res = max(res,a);
    }
    cout << res << endl;
    return 0;
}

//b
bool is_ok(string s){
    for(int i=0,j=s.length()-1;i<j;i++,j--){
        if(s[i]!=s[j])return false;
    }return true;
}
 
int main(){
    string s;
    cin >> s;
    string t = s;
    reverse(t.begin(),t.end());
    int res = t.size()-1;
    for(int i=0;i<=t.size();i++){
        if(is_ok(s+t.substr(i,t.size()-i)))
        res = min((int)t.length()-i,res);
    }
    cout << res << endl;
    return 0;
}

//d
i64 f(i64 n,i64 k){
    i64 t;
    while(k){
        t = k;
        k = n%k;
        n = t;
    }
    return n;
}
 
int main(){
    i64 n,k;
    cin >> n >> k;
    // cout << f(n,k) << endl;
    if(n%k)cout << k-f(n,k) << endl;
    else cout << 0 << endl;
    return 0;
}

CODE FESTIVAL 2017 qual C

CODE FESTIVAL 2017 qual C - CODE FESTIVAL 2017 qual C | AtCoder

306位 国内107位 3完

qual Cしか出られなかった

A:文字列(5文字以下)が"AC"を含むか

lengthをlentghと誤タイプしCE

B:整数列の各項を±1するかそのままにすることで得られる数列の集合のうち全項の積が偶数になるものはいくつか

偶数と奇数を分けながらやるだけだと思いつくと早かった

C:英小字列に任意個の'x'を挿入し回文にできるか判定して、出来れば最小個数を出力

O(length)があるとすぐに気づいた

前と後ろから見る線形時間解法は自分の得意分野(Deque大好きなのもその辺が理由)なので早解きに成功

コードも短く済んだのでうれしい限り

反省:

BitDPが遠い…競技時間中1回もBitDPにたどり着けなかったので精進不足

#include <iostream>
#include <cstdio>
#include <utility>
#include <algorithm>
#include <string>
#include <sstream>
#include <vector>
#include <deque>
#include <stack>
#include <set>
#include <map>
#include <queue>
#include <random>
 
#define i64 long long
#define ui64 unsigned long long
#define REP(i,n) for(int (i)=0;(i)<(n);i++)
#define REP2(i,k,n) for(int (i)=(k);(i)<(n);i++)
#define MDIST(a,b) abs(a-b)
#define DIST(a,b) sqrt((a)*(a)+(b)*(b))
#define ATCODER 1000000007
using namespace std;
 
////////////////////////
 
//a
int main(){
  string s;
  cin >> s;
  for(int i=0;i<s.length()-1;i++){
    if(s[i]=='A'&&s[i+1]=='C'){
      cout << "Yes" << endl;
      return 0;
    }
  }
  cout << "No" << endl;
}
 
//b
int main(){
  int n;
  cin >> n;
  int t;
  i64 o=1,e=1;
  i64 r=1;
  for(int i=0;i<n;i++){
    cin >> t;
    if(t%2);
    else e*=2;
    r*=3;
  }
  cout << r-e << endl;
}
 
//c
int main(){
  string s;
  cin >> s;
  int r=0;
  for(int i=0,j=s.length()-1;i<j;){
    if(s[i]==s[j]){i++;j--;}
    else if(s[i]!='x'&&s[j]!='x'){
      cout << -1 << endl;
      return 0;
    }else{
      if(s[i]=='x'){i++;r++;}
      else{j--;r++;}
    }
  }
  cout << r << endl;
}

DDCC 2017 予選

結果:176位 3完

Dが解けなかったけど枠の都合予選通過しそう

A:2文字目と3文字目は違う必要があることを見落とし1WA

B:数字がオーバーフローし1WA

C:Dequeのおかげで5分でAC

D:解法できていたのに実装ミスから虚無

コードがうまく乗らないので準備でき次第載せます

#include <bits/stdc++.h>
 
#define i64 long long
#define ui64 unsigned long long
#define REP(i,n) for(int (i)=0;(i)<(n);i++)
#define REP2(i,k,n) for(int (i)=(k);(i)<(n);i++)
#define MDIST(a,b) abs(a-b)
#define DIST(a,b) sqrt((a)*(a)+(b)*(b))
#define ATCODER 1000000007
#define C " "
using namespace std;
 
////////////////////////
 
/* a */
int main(){
  string c;
  cin >> c;
  if(c[0]==c[1] && c[2]==c[3] && c[1]!=c[2])cout << "Yes" << endl;
  else cout << "No" << endl;
}
 
/* b */
int main(){
  i64 a,b,c,d;
  cin >> a >> b >> c >> d;
  cout << 1728*a+144*b+12*c+d << endl;
}
/* c */
 
int main(){
  deque<i64> l;
  int n,c;
  cin >> n >> c;
  i64 tmp;
  for(int i=0;i<n;i++){
    cin >> tmp;
    l.push_back(tmp);
  }
  sort(l.begin(),l.end());
  int res = 0;
  while(!l.empty()){
    if(l.front()+l.back()+1<=c){
      if(!l.empty())l.pop_front();if(!l.empty())l.pop_back();res++;
    }else{
      if(!l.empty())l.pop_back();res++;
    }
  }
  cout << res << endl;
}

/* d */

Tenka1 Programmer Contest

http://tenka1-2017.contest.atcoder.jp/

結果:Cのみ300点

D500点が遠すぎたてかむずすぎた

C:二重ループを回すだけで解けるのを制約見逃しからかなり難しく考えてしまったので早解きに失敗

Cももう少し早く解けたしDのBit周りの精進がひどく足りない気がするので精進しなおします

でもまずはUbuntuの壊れた環境の再整備から…

#include <bits/stdc++.h>
 
#define i64 long long int
#define SPACE " "
using namespace std;
 
int main(){
  i64 N;
  cin >> N;
  i64 h=0,n,w,tmp;
  for(w=1;w<=3500;w++){
    for(n=1;n<=3500;n++){
      if(4*w*n-N*n-N*w<=0)continue;
      tmp = (N*w*n) % (4*w*n-N*n-N*w);
      if(!tmp){
        h=(N*w*n) / (4*w*n-N*n-N*w);
        break;
      }
    }
    if(h)break;
  }
  cout << h << SPACE << n << SPACE << w << endl;
}