algoNote

プログラミング関連

ブログに競プロのレーティングを表示するようにした(その2)

以前の記事でプログのサイドバーに競プロのレーティング(と色)を表示するjavascriptを紹介しました。 意外にも多くの方に使って頂けているようで嬉しいです。

algon-320.hatenablog.com

以前紹介したスクリプトではAtCoderのレーティング取得がYQLに依存していましたが、 残念ながらYQLは2019年1月でサービス終了してしまいました。 それに伴って、AtCoderのレーティング取得ができなくなっていました。

この問題に対応するために、簡易的なAPIサーバー的なもの(Kyopro-Ratingsと命名)を作成し、Heroku上で動かすことにしました。

デモ

機能

旧バージョンと同じです。

  • レーティング
  • 色付け
  • ユーザーページへのリンク

Kyopro-Ratings

Heroku上にレーティング取得用のサーバーを設置しました。サーバー側でレーティングを取得して、jsonでフロント側に送っています。

github.com

スクレイピングしている関係上、高頻度でリクエストが来た場合にエラーを返すようになっています。とりあえず200ms以内に複数のリクエストが来た場合に弾くようにしました。

ソースコード

こちらをサイドバーなどに設置しています。適当に改変して使ってください。
(htmlのtwitter・AOJの部分、jsのatcoder_user, codeforces_user, topcoder_algorithm_userの部分を自分のユーザー名に書き換えてください。)

なお、予告なくサーバーを停止するなどして動かなくなるかもしれませんので、その点はご了承ください。

<p>
  Twitter : <a id="twitter" href="https://twitter.com/algon_320" target="_blank"
    style="text-decoration:none;font-weight:bold;color:black;">@algon_320</a><br>
  AtCoder : <a id="atcoder_rating" target="_blank" style="text-decoration:none;font-weight:bold;">loading</a><br>
  Codeforces : <a id="codeforces_rating" target="_blank" style="text-decoration:none;font-weight:bold;">loading</a><br>
  TopCoder SRM : <a id="topcoder_algorithm_rating" target="_blank" style="text-decoration:none;font-weight:bold;">loading</a><br>
  AOJ : <a id="aoj" href="http://judge.u-aizu.ac.jp/onlinejudge/user.jsp?id=algon#1" target="_blank"
    style="text-decoration:none;font-weight:bold;color:black;">algon</a><br>
</p>

<script type="text/javascript">
  (function () {
    class User {
      constructor(service, handle) {
        this.service = service;
        this.handle = handle;
        this.rating = 0;
        this.color = '#000';  // デフォルトの色
      }
    }
    class Service {
      constructor(name, url) {
        this.name = name;
        this.url = url;
      }
    }

    let atcoder            = new Service('atcoder',            'https://atcoder.jp/user/');
    let codeforces         = new Service('codeforces',         'http://codeforces.com/profile/');
    let topcoder_algorithm = new Service('topcoder_algorithm', 'https://www.topcoder.com/members/');

    let atcoder_user            = new User(atcoder,            'algon');
    let codeforces_user         = new User(codeforces,         'algon_320');
    let topcoder_algorithm_user = new User(topcoder_algorithm, 'algon_320');

    let accounts = [atcoder_user, codeforces_user, topcoder_algorithm_user];

    // ユーザーページへのリンクのみ
    function set_html_without_rating(user) {
      let a = document.getElementById(user.service.name + '_rating');
      a.href = user.service.url + user.handle;
      a.innerHTML = user.handle;
      a.setAttribute('style', 'text-decoration:none;font-weight:bold;color:' + user.color);
    }
    // ユーザーページへのリンク + レーティング表示 + 色
    function set_html(user) {
      let a = document.getElementById(user.service.name + '_rating');
      a.href = user.service.url + user.handle;
      a.innerHTML = user.handle + ' (' + user.rating.toString() + ')';
      a.setAttribute('style', 'text-decoration:none;font-weight:bold;color:' + user.color);
    }

    function fetch_ratings() {
      let query_str = '';
      accounts.forEach(user => {
        query_str += user.service.name + "=" + user.handle + '&';
      });

      function error() {
        accounts.forEach(user => set_html_without_rating(user));
      }
      let xhr = new XMLHttpRequest();
      xhr.open('GET', 'https://kyopro-ratings.herokuapp.com/json?' + query_str, true);
      xhr.onload = function (e) {
        if (xhr.readyState === 4) {
          if (xhr.status === 200) {
            json = JSON.parse(xhr.responseText);
            // console.log(json);
            if ('error' in json) {
              error();
            } else {
              accounts.forEach(user => {
                let service_name = user.service.name;
                if (json[service_name]['status'] == 'success') {
                  user.rating = json[service_name]['rating'];
                  user.color = json[service_name]['color'];
                  set_html(user);
                } else {
                  set_html_without_rating(user);
                }
              });
            }
          }
        }
      };
      xhr.onerror = function (e) { error(); };
      xhr.ontimeout = function (e) { error(); };
      xhr.timeout = 10000;
      xhr.send(null);
    }
    fetch_ratings();
  })();
</script>

はてなブログの場合、管理画面のデザイン→サイドバー→カスタマイズから設置することが出来ます。

Lyft Level 5 Challenge 2018 - Final Round (Open Div. 1) C. Optimal Polygon Perimeter

問題

http://codeforces.com/contest/1074/problem/C

解法

マンハッタン距離での周囲の長さなので、選んだ多角形を囲むような(面積最小の)長方形の周囲の長さになります。よって、k=4以上のケースは自明で、n点を囲むような長方形の周長です。

問題はk=3のケースですが、「最左・最上」、「最左・最下」、「最右・最上」、「最右・最下」を固定して、それぞれについて残り1点をすべて試せば最大の周長が求まります。
(証明を書こうとしたけど上手く書けなかった&面倒になったのでeditorialを見てください(おい))

提出コード

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define stoi stoll
using ll=long long;
using vi=vector<int>;
using pii=pair<int,int>;
#define ALL(c) begin(c),end(c)
#define RALL(c) rbegin(c),rend(c)
#define ITR(i,b,e) for(auto i=(b);i!=(e);++i)
#define FORE(x,c) for(auto &x:c)
#define REPF(i,a,n) for(int i=a,i##len=(int)(n);i<i##len;++i)
#define REP(i,n) REPF(i,0,n)
#define REPR(i,n) for(int i=(int)(n);i>=0;--i)
#define SZ(c) ((int)c.size())
#define CONTAIN(c,x) (c.find(x)!=end(c))
#define INSEG(l,x,r) ((l)<=(x)&&(x)<(r))
#define dump(...)
#define pb push_back
#define _ 0
const signed INF_=1001001001; const long long INF=1001001001001001001LL;
const int DX[9]={0,1,0,-1,1,1,-1,-1,0},DY[9]={-1,0,1,0,-1,1,1,-1,0};
template<class T> ostream& operator<<(ostream &os,const vector<T> &v) {
    ITR(i,begin(v),end(v))os<<*i<<(i==end(v)-1?"":" ");return os;}
template<class T> istream& operator>>(istream &is,vector<T> &v) {
    ITR(i,begin(v),end(v)) is>>*i;return is;}
template<class T,class U> istream& operator>>(istream &is, pair<T,U> &p) {
    is>>p.first>>p.second;return is;}
template<class T, class U> bool chmax(T &a,const U &b){return a<b?a=b,1:0;}
template<class T, class U> bool chmin(T &a,const U &b){return a>b?a=b,1:0;}
template <class T> void PSUM(T& c) {partial_sum(begin(c), end(c), begin(c));}
template<class T> using heap=priority_queue<T,vector<T>,greater<T>>;
struct before_main_function {
    before_main_function() {
        cin.tie(0); ios::sync_with_stdio(false);
        cout << setprecision(15) << fixed;
        // #define endl "\n"
    }
} before_main_function;
//------------------8<------------------------------------8<--------------------

signed main() {
    int n;
    cin >> n;
    vector<int> x(n), y(n);
    REP(i, n) cin >> x[i] >> y[i];
    auto mxx = max_element(ALL(x));
    auto mnx = min_element(ALL(x));
    auto mxy = max_element(ALL(y));
    auto mny = min_element(ALL(y));

    int ans = 0;
    for (auto itrx = begin(x), itry = begin(y); itrx != end(x); ++itrx, ++itry) {
        if (itrx != mnx && itry != mny) chmax(ans, abs(*itrx - *mnx) + abs(*itry - *mny));
        if (itrx != mnx && itry != mxy) chmax(ans, abs(*itrx - *mnx) + abs(*itry - *mxy));
        if (itrx != mxx && itry != mny) chmax(ans, abs(*itrx - *mxx) + abs(*itry - *mny));
        if (itrx != mxx && itry != mxy) chmax(ans, abs(*itrx - *mxx) + abs(*itry - *mxy));
    }

    vector<int> ansv;
    ansv.push_back(ans * 2);
    if (n >= 4) {
        ans = *mxx - *mnx + *mxy - *mny;
        vector<int> tmp(n - 4 + 1, ans * 2);
        ansv.insert(end(ansv), ALL(tmp));
    }
    cout << ansv << endl;
    return (0^_^0);
}

Lyft Level 5 Challenge 2018 - Final Round (Open Div. 1) B. Intersecting Subtrees

問題

http://codeforces.com/contest/1074/problem/B

解法

クエリの上限は5回ですが、2回で求まります。

まず、yの中から適当なラベルを選んで、自分の木での位置を質問します。この頂点をSとして、Sとxの頂点との距離が最小になる点をPとします。Pの位置の相手のラベルを質問して、これがyに含まれていればPが答えです。そうでなければ共有点はありません。

Pの求め方ですが、Sがxの部分木中に含まれれば、P=Sです。そうでない場合、適当に根を決めると、xの部分木はSの下側か上側にあることになります。

ここで、根付き木上でxの中で一番上にある点をT、xの中で部分木にSを含む頂点のうち一番下にあるものをB(存在するなら)とおくと、Bが存在するならP=Bで、そうでないならP=Tです。

xの部分木がSの上側にあるケースのイメージ
f:id:algon_320:20181108225630p:plain

xの部分木がSの下側にあるケースのイメージ
f:id:algon_320:20181108225637p:plain

提出コード

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define stoi stoll
using ll=long long;
using vi=vector<int>;
using pii=pair<int,int>;
#define ALL(c) begin(c),end(c)
#define RALL(c) rbegin(c),rend(c)
#define ITR(i,b,e) for(auto i=(b);i!=(e);++i)
#define FORE(x,c) for(auto &x:c)
#define REPF(i,a,n) for(int i=a,i##len=(int)(n);i<i##len;++i)
#define REP(i,n) REPF(i,0,n)
#define REPR(i,n) for(int i=(int)(n);i>=0;--i)
#define SZ(c) ((int)c.size())
#define CONTAIN(c,x) (c.find(x)!=end(c))
#define INSEG(l,x,r) ((l)<=(x)&&(x)<(r))
#define dump(...)
#define pb push_back
#define _ 0
const signed INF_=1001001001; const long long INF=1001001001001001001LL;
const int DX[9]={0,1,0,-1,1,1,-1,-1,0},DY[9]={-1,0,1,0,-1,1,1,-1,0};
template<class T> ostream& operator<<(ostream &os,const vector<T> &v) {
    ITR(i,begin(v),end(v))os<<*i<<(i==end(v)-1?"":" ");return os;}
template<class T> istream& operator>>(istream &is,vector<T> &v) {
    ITR(i,begin(v),end(v)) is>>*i;return is;}
template<class T,class U> istream& operator>>(istream &is, pair<T,U> &p) {
    is>>p.first>>p.second;return is;}
template<class T, class U> bool chmax(T &a,const U &b){return a<b?a=b,1:0;}
template<class T, class U> bool chmin(T &a,const U &b){return a>b?a=b,1:0;}
template <class T> void PSUM(T& c) {partial_sum(begin(c), end(c), begin(c));}
template<class T> using heap=priority_queue<T,vector<T>,greater<T>>;
struct before_main_function {
    before_main_function() {
        cin.tie(0); ios::sync_with_stdio(false);
        cout << setprecision(15) << fixed;
        // #define endl "\n"
    }
} before_main_function;
//------------------8<------------------------------------8<--------------------

// in, out: 0-indexed
int ask(char type, int x) {
    cout << type << " " << x + 1<< endl;
    int y;
    cin >> y;
    if (y == -1) exit(0);
    return y - 1;
}
// in: 0-indexed
void answer(int v) {
    cout << "C " << v + 1 << endl;
}
signed main() {
    int Q;
    cin >> Q;
    while (Q--) {
        int n;
        cin >> n;
        vector<vector<int>> g(n);
        REP(i, n - 1) {
            int a, b;
            cin >> a >> b;
            a--, b--;
            g[a].pb(b);
            g[b].pb(a);
        }

        int k1;
        cin >> k1;
        vector<int> x(k1);
        cin >> x; FORE(i, x) i--;
        sort(ALL(x));

        int k2;
        cin >> k2;
        vector<int> y(k2);
        cin >> y; FORE(i, y) i--;
        sort(ALL(y));

        vector<bool> color(n);
        FORE(i, x) color[i] = true;

        int S = ask('B', y[0]);
        if (color[S]) {
            answer(S);
            continue;
        }

        int T = -1;
        auto findT = [&](auto f, int v, int p) -> void {
            if (color[v] && T == -1) T = v;
            FORE(w, g[v]) {
                if (w == p) continue;
                f(f, w, v);
            }
        };
        findT(findT, 0, -1);

        int B = -1;
        auto dfs = [&](auto f, int v, int p) -> bool {
            if (v == S) return true;
            bool found = false;
            FORE(w, g[v]) {
                if (w == p) continue;
                bool res = f(f, w, v);
                if (res && color[v] && B == -1) B = v;
                found |= res;
            }
            return found;
        };
        dfs(dfs, 0, -1);

        if (B != -1) {
            if (binary_search(ALL(y), ask('A', B))) {
                answer(B);
            } else {
                cout << "C -1" << endl;
            }
        } else {
            if (binary_search(ALL(y), ask('A', T))) {
                answer(T);
            } else {
                cout << "C -1" << endl;
            }
        }
    }
    return (0^_^0);
}

インタラクティブな問題では#define endl "\n"してはいけません...

Lyft Level 5 Challenge 2018 - Final Round (Open Div. 1) A. The Tower is Going Home

問題

http://codeforces.com/contest/1074/problem/A

解法

以下y軸平行な境界線を"縦線"、x軸平行な境界線を"横線"と呼びます。

方針としては、左からいくつの縦線を消すかを固定して、その時に横線をいくつ消す必要があるかを考えます。 (縦線については最も左にある縦線より右側に侵入することは出来ないので左から連続で消すことを考えればよい)

横線について、同じy座標にある別の境界と端点を共有しないという制約より、x1が1でないものについては無視して良いことが分かります。(端点を共有しない⇔x1が1でない境界についてx1-1の部分を通過出来るので)

縦線を左からk本消すことにすると、x1=1の横線のうち、k+1本目の縦線と交わるものを消せばよいことが分かります。 このような横線がl本あるとすると、k+lの最小値が答えになります。 k+1本目の縦線と交わる横線の個数は、横線を右端でソートしておけば二分探索で求まります。

提出コード

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define stoi stoll
using ll=long long;
using vi=vector<int>;
using pii=pair<int,int>;
#define ALL(c) begin(c),end(c)
#define RALL(c) rbegin(c),rend(c)
#define ITR(i,b,e) for(auto i=(b);i!=(e);++i)
#define FORE(x,c) for(auto &x:c)
#define REPF(i,a,n) for(int i=a,i##len=(int)(n);i<i##len;++i)
#define REP(i,n) REPF(i,0,n)
#define REPR(i,n) for(int i=(int)(n);i>=0;--i)
#define SZ(c) ((int)c.size())
#define CONTAIN(c,x) (c.find(x)!=end(c))
#define INSEG(l,x,r) ((l)<=(x)&&(x)<(r))
#define dump(...)
#define pb push_back
#define _ 0
const signed INF_=1001001001; const long long INF=1001001001001001001LL;
const int DX[9]={0,1,0,-1,1,1,-1,-1,0},DY[9]={-1,0,1,0,-1,1,1,-1,0};
template<class T> ostream& operator<<(ostream &os,const vector<T> &v) {
    ITR(i,begin(v),end(v))os<<*i<<(i==end(v)-1?"":" ");return os;}
template<class T> istream& operator>>(istream &is,vector<T> &v) {
    ITR(i,begin(v),end(v)) is>>*i;return is;}
template<class T,class U> istream& operator>>(istream &is, pair<T,U> &p) {
    is>>p.first>>p.second;return is;}
template<class T, class U> bool chmax(T &a,const U &b){return a<b?a=b,1:0;}
template<class T, class U> bool chmin(T &a,const U &b){return a>b?a=b,1:0;}
template <class T> void PSUM(T& c) {partial_sum(begin(c), end(c), begin(c));}
template<class T> using heap=priority_queue<T,vector<T>,greater<T>>;
struct before_main_function {
    before_main_function() {
        cin.tie(0); ios::sync_with_stdio(false);
        cout << setprecision(15) << fixed;
        #define endl "\n"
    }
} before_main_function;
//------------------8<------------------------------------8<--------------------

signed main() {
    int n, m;
    cin >> n >> m;
    vector<int> x(n);
    cin >> x;
    vector<int> y;
    REP(i, m) {
        int a, b, c;
        cin >> a >> b >> c;
        if (a != 1) continue;
        y.push_back(b);
    }
    x.push_back(1'000'000'000);
    m = SZ(y), n = SZ(x);
    sort(ALL(x));
    sort(ALL(y));

    int ans = INF;
    REP(i, n) {
        int cnt = end(y) - lower_bound(ALL(y), x[i]);
        chmin(ans, i + cnt);
    }
    cout << ans << endl;
    return (0^_^0);
}

SRM738 easy - FindThePerfectTriangle

System Testで落ちて0ptでした...

問題概要

三角形の周囲の長さ(perimeter)と面積(area)が与えられる。
周囲の長さ、面積が与えられたものに一致し、各頂点の座標が整数となるような三角形が存在するか判定し、存在するなら頂点の座標を返せ。(複数存在するならどれでもいい)

制約

  • perimeter, area は整数
  •  1 \leq area  \leq 10^6
  •  1 \leq perimeter  \leq 1000
  •  0 \leq 頂点の座標の値  \leq 3000

解法

1点を原点に固定して残りの2点の座標を探索します。

2点の座標を(x1, y1), (x2, y2)とすると、面積は area = \frac{1}{2} |x1y2 - x2y1|になります。
変形して area \times 2 = |x1y2 - x2y1|
このうちx1y2を固定することを考えます。答えとなりうる三角形の一辺の長さの値の範囲を考えると、P/2未満であることが必要です。(正の面積を持つので当たり前ですが)
よって各座標値の絶対値はP/2以下であることが分かるので、まずx1を500以下の範囲で決めて、y2をP-x1の範囲で決めます。

絶対値を外す時にx1y2, x2y1の大小によって場合分けが必要ですが、今回は条件を満たす物を1つ出力すれば良いので、x1y2 > x2y1としてしまって問題ありません。
よって、x2y1 = x1y2 - area * 2と決まります。

あとは、符号に注意しながらx2y1を約数に分割してx2,y1を決め、条件を満たすかを試せばよいです。

コード

int isqrt[2000006];

struct FindThePerfectTriangle {
    int P;
    int A;

    inline bool check_sq(int s) {
        int sq = isqrt[s];
        return (sq * sq == s);
    }
    
    inline bool check(int x1, int x2, int y1, int y2) {
        if (abs(x1) > 600 || abs(x2) > 600 || abs(y1) > 600 || abs(y2) > 600) return false;

        int sum1 = x1 * x1 + y1 * y1;
        if (!check_sq(sum1)) {
            return false;
        }
        
        int sum2 = x2 * x2 + y2 * y2;
        if (!check_sq(sum2)) {
            return false;
        }

        int sum3 = (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
        if (!check_sq(sum3)) {
            return false;
        }

        return (isqrt[sum1] + isqrt[sum2] + isqrt[sum3] == P);
    }

    inline int sign(int x) {
        if (x < 0) return -1;
        return 1;
    }

    vector<int> constructTriangle(int area, int perimeter) {
        for (int i = 0; i * i <= 2000000; i++) isqrt[i * i] = i;

        P = perimeter;
        A = area;

        REP(x1, 501) {
            REP(y2, P - x1) {
                int x2y1 = x1 * y2 - area * 2;

                for (int i = 1; i * i <= abs(x2y1); i++) {
                    if (x2y1 % i == 0) {
                        int x2, y1;

                        for (auto sign1 : {-1, 1}) {
                            for (auto sign2 : {-1, 1}) {
                                if (sign1 * sign2 != sign(x2y1)) continue;

                                x2 = sign1 * i;
                                y1 = sign2 * abs(x2y1) / i;
                                if (check(x1, x2, y1, y2))
                                    return {x1 + 1500, y1 + 1500, x2 + 1500, y2 + 1500, 1500, 1500};

                                y1 = sign1 * i;
                                x2 = sign2 * abs(x2y1) / i;
                                if (check(x1, x2, y1, y2))
                                    return {x1 + 1500, y1 + 1500, x2 + 1500, y2 + 1500, 1500, 1500};
                            }
                        }
                    }
                }
            }
        }

        return {};
    }
};

TLEギリギリだったので少々強引な解な気もします…