Amami’s competitive diary

PG BATTLE 2021 せんべい参加記

はじめに

一昨年のましゅまろ、去年のせんべいに続き今年もせんべいで3完以上を目指していましたがBの考察に時間をかけすぎて2完に終わりました。

A問題

概要

確率 p で勝利する勝負を7回行った時に、勝ち越す確率はいくらか。

考察

n 回のうち、確率 p の事象が k 回起こる確率は
 _n C_k * p^{k} * (1 - p)^{n - k}
となり、この k4 ~ 7 まで総和を取ればいいので、結果的には
 \sum_{k=4}^7  \{_7 C_k * p^{k} * (1 - p)^{7 - k}\}
を求めればいいことになります。

実装

#include<bits/stdc++.h>
using namespace std;

// Combination
long long nCr(long long n, long long r) {
    long long x = 1, y = 1;
    for(long long i = 0; i < r; i++) {
        x = x * (n - i);
        y = y * (i + 1);
    }
    return x / y;
}

int main()
{
    double p;
    cin >> p;
    p /= 100;
    double q = 1.0 - p;
    double ans = 0;
    for(int i = 4; i <= 7; i++) {
        ans += nCr(7, i) * pow(p, i) * pow(q, 7 - i);
    }
    cout << fixed << setprecision(15) << ans * 100 << endl;
    return 0;
}

B問題

概要

t 個のクエリに答える。
各クエリに対して n , m が与えられる。
この時、2重辺や自己辺を作らずに n 頂点 m 辺の無向グラフを構築した時の、連結成分の数の最小値と最大値を求める。

例 : 4 頂点 3 辺の場合

最小値は以下のように辺をつないだ場合の 1 になります

f:id:amami0522:20211023213703p:plain

最大値は以下のように辺をつないだ場合の 2 になります

f:id:amami0522:20211023213933p:plain

考察

最小値に関しては簡単で、連結成分が n ある状態から辺を 1 本増やすと連結成分を 1 減らすことができるので基本的には n-m になります。
ただ、1 未満になることはないので、1n-m の大きい方を出力すればいいです。

次に最大値です。私は、連結成分を X にすることができるか、ということへの二分探索を行いました。
連結成分が X になるということは、mn-X+1 頂点の完全グラフの辺の数より少なければ良いので
m\leq\frac{(n-X+1)(n-X)}{2}
を満たせばよいということになります。

実装

#include<bits/stdc++.h>
using namespace std;

// n頂点m辺で連結成分がmid個にできるか
bool isOk(long long n, long long m, long long mid) {
    long long x = n - mid + 1;
    long long sum = x * (x - 1) / 2;
    return m <= sum;
}

int main()
{
    int t;
    cin >> t;
    while(t--) {
        long long n, m;
        cin >> n >> m;
        long long ans1, ans2;
        // 最小値
        ans1 = max(1LL, n - m);
        // 最大値
        long long ok = ans1;
        long long ng = n + 1;
        while(abs(ok - ng) > 1) {
            long long mid = (ok + ng) / 2;
            if(isOk(n, m, mid)) ok = mid;
            else ng = mid;
        }
        ans2 = ok;

        cout << ans1 << " " << ans2 << endl;
    }
    return 0;
}

おわりに

学生として出られるのは今年で最後ですが来年からも時間があれば出場出来たらなと思います。

競技プログラミングで個人的に使っているマクロ

私が普段競技プログラミングで使っているマクロについて簡単にまとめておこうと思ったのでこれを書きました。
完全に自作ではなく、他の人を参考にしたものもあります。

#include <bits/stdc++.h>

ライブラリをいっぱいincludeしてくれます。

#include <bits/stdc++.h>

using namespace std;

標準ライブラリのstd名前空間にあるもののstd::を省略できます。

using namespace std;

ソースコードの置換

以下のように書くとABに置換します。

#define A B

私は次のようなものを使っています。

// for文の省略
#define rep(i, n) for(long long i = 0; i < (n); i++)
#define REP(i, s, n) for(long long i = (s); i <= (n); i++)
#define repr(i, n) for(long long i = (n - 1); i >= 0; i--)
#define REPR(i, s, n) for(long long i = (s); i >= (n); i--)

// イテレータ指定の省略
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()

// 配列の総和
#define sumvec(v) accumulate(all(v), 0LL)

// 実数の表示桁数指定
#define DOUBLE fixed << setprecision(15)

// デバッグ用の表記
#define OK cerr << "OK\n"
#define OK1 cerr << "OK1\n"
#define OK2 cerr << "OK2\n"
#define dbg(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ") " << __FILE__ << endl;

// size()のint型へのキャスト
#define sz(s) (int)s.size()

型名に新しい名前を付ける

以下のように書くとデータ型に新しい名前を付けることが出来ます。
この例ではAという型がBという名前でも使えるようになります。

typedef A B;

これを使って私は以下のようにデータ型の名前を省略しています。

typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<long long> vll;
typedef vector<double> vd;
typedef vector<ld> vld;
typedef vector<char> vc;
typedef vector<bool> vb;
typedef vector<string> vs;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
typedef vector<vd> vvd;
typedef vector<vld> vvld;
typedef vector<vc> vvc;
typedef vector<vb> vvb;
typedef pair<ll,ll> P;
typedef vector<P> vP;

templateによるマクロ

templateについて1から説明しているときりがないので省略します。
任意のデータ型について対応した等しい処理を行えるものだという認識で大丈夫です。

複数変数のデバッグ

void debug() { cerr << "\n"; }
template<class T, class... Args>
void debug(const T &x, const Args &... args) {
    cerr << x << " ";
    debug(args...);
}

これを使うと複数の変数のデバッグを簡単に書けます。

int a = 5;
int b = 10;
debug(a, b);

// 5 10 と表示して改行されます。

標準ライブラリの関数への機能の追加

ライブラリ内で定義されているmin(), max()は通常は二値比較ですが、vectorなどのmin(max)_elementを用いる場合にもmin(), max()で求めることが出来るようになります。

template<class T>
auto min(const T& a) {
    return *min_element(a.begin(), a.end());
}

template<class T>
auto max(const T& a) {
    return *max_element(a.begin(), a.end());
}
vector<int> a = {1, 2, 3, 4, 5};
cout << max(a) << endl;

// 5 と表示される

最大値、最小値の更新用の関数

最大値、最小値を更新した際などに第一引数を第二引数で更新し、trueを返します。

template<class T>
inline bool chmax(T& a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
inline bool chmin(T& a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}

これを使うと、以下の2つがほとんど同じような動作をします。

ans = max(ans, tmp);
chmax(ans, tmp);

更新したらtrueを返すようになっているので、次のようにも書くことが出来ます。

if(chmax(ans, tmp)) {
    // ansが更新された時にする処理
}

標準入出力への利用

簡単に言うと<<>>といった演算子で出来る事を増やします。
例えば、以下のようなもの。
vector<<演算子を使うと中身を順番に表示するようになっています。

template<class T>
ostream& operator<< (ostream& ost, const vector<T>&v) {
    os << "{";
    for (int i = 0; i < (int)v.size(); i++) {
        if(i) ost << " ";
        ost << v[i];
    }
    ost << "} \n";
    return ost;
}

これにより、次のように書くことが出来ます。

vector<int> a = {1, 2, 3, 4, 5};
cout << a;

// {1 2 3 4 5} と表示されます。

これと同様なものを多く用意しています。

// pair型のfirst, secondを同時に出力する
template<class A, class B>
ostream& operator<< (ostream& ost, const pair<A, B> &p) {
    ost << "{" << p.first << ", " << p.second << "} ";
    return ost;
}

// dequeの要素を順番に出力する
template <typename T> ostream& operator<<(ostream& os, const deque<T> &vec) {
    os << "deq[";
    for (auto v : vec) {
        os << v << ",";
    }
    os << "]\n";
    return os;
}

// mapの要素を順番に表示する
template<class A, class B>
ostream& operator<< (ostream& ost, const map<A, B>&v) {
    ost << "{";
    for (auto p : v) {
        ost << "{" << p.first << ", " << p.second << "} ";
    }
    ost << "}\n";
    return ost;
}

// setの要素を順番に出力するようにする
template<typename T>
ostream& operator<< (ostream &os, const set<T> &vec) {
    os << "{";
    for (auto v : vec) {
        os << v << ",";
    }
    os << "}\n";
    return os;
}

// multisetの要素を順番に出力するようにする
template<typename T>
ostream& operator<<(ostream &os, const multiset<T> &vec) {
    os << "{";
    for (auto v : vec) {
        os << v << ",";
    }
    os << "}\n";
    return os;
}

// vectorへの標準入力を順番に実行する
template<typename T>
istream& operator>> (istream& is, vector<T>& vec) {
    for(T& e : vec) {
        is >> e;
    }
    return is;
}

// pair型のfirst, secondへの標準入力を同時に行うようにする
template<typename A, typename B>
istream& operator>> (istream& is, pair<A, B>& p) {
    is >> p.first >> p.second;
    return is;
}

// pair型の + 演算子はfirst, second同士を足し合わせるようにする
template<typename A, typename B>
pair<A, B> operator+ (const pair<A, B> &l, const pair<A, B> &r) {
    return make_pair(l.first + r.first, l.second + r.second);
}

// pair型の - 演算子はfirst, second同士を引くようにする
template<typename A, typename B>
pair<A, B> operator- (const pair<A, B> &l, const pair<A, B> &r) {
    return make_pair(l.first - r.first, l.second - r.second);
}

複数変数の標準入力の省略

今まで書いてきたことを用いて、以下のようなことも出来ます。

#define INT(...) int __VA_ARGS__; IN(__VA_ARGS__)

void scan(int& a) { cin >> a; }

void IN() {}
template<class Head, class... Tail>
void IN(Head& head, Tail&... tail) {
    scan(head);
    IN(tail...);
}

これは何かというと、INT()の引数にカンマ区切りで書いた引数を宣言、標準入力を行うというものです。
これを用いると、以下の2つが同じ意味になります。

int a, b, c;
cin >> a >> b >> c;
INT(a, b, c);

汎用の定数について

よく使う定数などはあらかじめ宣言しておきます。

// グリッドの4近辺を探索する時の、座標の差分用の配列
const int dy[] = {-1, 0, 0, 1};
const int dx[] = {0, -1, 1, 0};

// グリッドの8近辺を探索する時の、座標の差分用の配列
const int dy8[] = {-1, -1, -1, 0, 0, 1, 1, 1};
const int dx8[] = {-1, 0, 1, -1, 1, -1, 0, 1};

// infinityを表す大きな値
const int inf = 1001001001;
const long long INF = ((1LL << 62) - (1LL << 31));

// 円周率π
const long double pi = acos(-1.0);

// 頻出のMOD
const long long mod = 1000000007;
const long long MOD = 998244353;

汎用の自作関数について

定数と同様に、よく使う関数はあらかじめ定義してあります。

// 繰り返し自乗法で a ^ b % mod を返す
long long powmod(long long a, long long b) {
    long long c = 1;
    while(b > 0) {
        if(b & 1) {
            c = a * c % mod;
        }
        a = a * a % mod;
        b >>= 1;
    }
    return c;
}

// nCr % mod を返します
long long nCrmod(long long n, long long r) {
    long long x = 1, y = 1;
    for(long long i = 0; i < r; i++) {
        x = x * (n - i) % mod;
        y = y * (i + 1) % mod;
    }
    return x * powmod(y, mod - 2) % mod;
}

// 約数を列挙してvectorで返します
vector<long long> divisor(long long x) {
    vector<long long> v;
    for(long long i = 1; i * i <= x; i++) {
        if(x % i == 0){
            v.push_back(i);
            if(i * i != x) v.push_back(x / i);
        }
    }
    sort(v.begin(), v.end());
    return v;
};

// 素因巣分解をして<key, value>を<素因数, 素因数の個数>としてmapで返します
map<long long, long long> prime_factor(long long n) {
    map<long long, long long> m;
    for(long long i = 2; i * i <= n; i++) {
        while(n % i == 0) {
            m[i]++;
            n /= i;
        }
    }
    if(n != 1) m[n] = 1;
    return m;
}

まとめ

紹介したものをまとめると以下のようになります。
コードの行が増えすぎないように改行してない部分がありますがご了承ください。
あくまで私個人の例なので、使用は自己責任でお願いします。

#include<bits/stdc++.h>
using namespace std;

#define rep(i,n) for(long long i = 0; i < (n); i++)
#define REP(i,s,n) for(long long i = (s); i <= (n); i++)
#define repr(i,n) for(long long i = (n - 1); i >= 0; i--)
#define REPR(i,s,n) for(long long i = (s); i >= (n); i--)
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define sumvec(v) accumulate(all(v), 0LL)
#define DOUBLE fixed << setprecision(15)
#define OK cerr << "OK\n"
#define OK1 cerr << "OK1\n"
#define OK2 cerr << "OK2\n"
#define sz(s) (int)s.size()
#define dbg(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ") " << __FILE__ << endl;

typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<long long> vll;
typedef vector<double> vd;
typedef vector<ld> vld;
typedef vector<char> vc;
typedef vector<bool> vb;
typedef vector<string> vs;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
typedef vector<vd> vvd;
typedef vector<vld> vvld;
typedef vector<vc> vvc;
typedef vector<vb> vvb;
typedef pair<ll,ll> P;
typedef vector<P> vP;


void debug() { cerr << "\n"; }
template<class T, class... Args>
void debug(const T &x, const Args &... args) {cerr << x << " "; debug(args...);}
template<class A, class B> ostream& operator<< (ostream& ost, const pair<A, B> &p) { ost << "{" << p.first << ", " << p.second << "} "; return ost; }
template<class T> ostream& operator<< (ostream& ost, const vector<T>&v) { ost << "{"; for (int i = 0; i < (int)v.size(); i++) { if(i) ost << " "; ost << v[i]; } ost << "} \n"; return ost; }
template <typename T> ostream& operator<<(ostream& os, const deque<T> &vec) { os << "deq["; for (auto v : vec) os << v << ","; os << "]\n"; return os; }
template<class A, class B> ostream& operator<< (ostream& ost, const map<A, B>&v) { ost << "{"; for (auto p : v) { ost << "{" << p.first << ", " << p.second << "} "; } ost << "}\n"; return ost; }
template<typename T> istream& operator>> (istream& is, vector<T>& vec) { for(T& e : vec) is >> e; return is; }
template<typename A, typename B> istream& operator>> (istream& is, pair<A, B>& p) { is >> p.first >> p.second; return is; }
template<typename A, typename B> pair<A, B> operator+ (const pair<A, B> &l, const pair<A, B> &r) { return make_pair(l.first + r.first, l.second + r.second); }
template<typename A, typename B> pair<A, B> operator- (const pair<A, B> &l, const pair<A, B> &r) { return make_pair(l.first - r.first, l.second - r.second); }
template<typename T> ostream& operator<< (ostream &os, const set<T> &vec) { os << "{"; for (auto v : vec) os << v << ","; os << "}\n"; return os; }
template<typename T> ostream& operator<<(ostream &os, const multiset<T> &vec) { os << "{"; for (auto v : vec) os << v << ","; os << "}\n"; return os; }
template<class T> auto min(const T& a){ return *min_element(a.begin(), a.end()); }
template<class T> auto max(const T& a){ return *max_element(a.begin(), a.end()); }
template<class T> inline bool chmax(T& a, T b){ if(a < b){ a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b){ if(a > b){ a = b; return true; } return false; }

#define INT(...) int __VA_ARGS__; IN(__VA_ARGS__)
#define LL(...) long long __VA_ARGS__; IN(__VA_ARGS__)
#define CHR(...) char __VA_ARGS__; IN(__VA_ARGS__)
#define DBL(...) double __VA_ARGS__; IN(__VA_ARGS__)
#define STR(...) string __VA_ARGS__; IN(__VA_ARGS__)
#define LD(...) long double __VA_ARGS__; IN(__VA_ARGS__)

void scan(int& a){ cin >> a; }
void scan(long long& a){ cin >> a; }
void scan(char& a){ cin >> a; }
void scan(double& a){ cin >> a; }
void scan(string& a){ cin >> a; }
void scan(long double& a){ cin >> a; }

void IN(){}
template<class Head, class... Tail> void IN(Head& head, Tail&... tail){ scan(head); IN(tail...); }

const int dy[] = {-1, 0, 0, 1};
const int dx[] = {0, -1, 1, 0};
const int dy8[] = {-1, -1, -1, 0, 0, 1, 1, 1};
const int dx8[] = {-1, 0, 1, -1, 1, -1, 0, 1};
const int inf = 1001001001;
const long long INF = ((1LL << 62) - (1LL << 31));
const long double pi = acos(-1.0);
const long long mod = 1000000007;
const long long MOD = 998244353;

ll powmod(ll a, ll b){ ll c = 1; while(b > 0){ if(b & 1){ c = a * c % mod; } a = a * a % mod; b >>= 1; } return c; }
ll nCrmod(ll n, ll r){ ll x = 1, y = 1; for(ll i = 0; i < r; i++) { x = x * (n - i) % mod; y = y * (i + 1) % mod; } return x * powmod(y, mod - 2) % mod; }
vll divisor(ll x){ vll v; for(ll i = 1; i * i <= x; i++) if(x % i == 0){ v.push_back(i); if(i * i != x) v.push_back(x / i); } sort(v.begin(), v.end()); return v; };
map<ll, ll> prime_factor(ll n){ map<ll, ll> m; for(ll i = 2; i * i <= n; i++){ while(n % i == 0){ m[i]++; n /= i; } } if(n != 1) m[n] = 1; return m; }

int main()
{
    return 0;
}

間違い等ありましたら連絡いただけますと幸いです。
拙い説明ではありましたが、お付き合いいただきありがとうございました。

Codeforces Round #704 (Div. 2) 参加記

はじめに

久しぶりにCodeforcesに参加しました。
相変わらず英語がそこまで早く読めないので翻訳しながらやってます。

A - Three swimmers

P以上の最小のA, B, Cの倍数は繰り上げればすぐに求まるので、そのそれぞれからPを引くだけです。

#include<bits/stdc++.h>
using namespace std;

int main()
{
    int q;
    cin >> q;
    while(q--) {
        long long p, a, b, c;
        cin >> p >> a >> b >> c;
        long long x = (p + a - 1) / a * a - p;
        long long y = (p + b - 1) / b * b - p;
        long long z = (p + c - 1) / c * c - p;
        cout << min({x, y, z}) << endl;
    }
    return 0;
}

B - Card Deck

方針としては、上から、山に残っているカードのうち一番大きい数字のカードまでを取り出して答えの山に積む、という操作を繰り返します。
順列なので、取出したかどうかの配列を持っておくと、それを後ろから順にみていって、次に取り出すべき1番大きい値を見つけられます。

#include<bits/stdc++.h>
using namespace std;

int main()
{
    int q;
    cin >> q;
    while(q--) {
        int n;
        cin >> n;
        vector<int> p(n);
        for(int i = 0; i < n; i++) cin >> p[i];

        vector<bool> use(n + 1, false);  // 各数字を取り出したかどうか
        vector<int> ans;  // 答えの山となる配列
        vector<int> add;  // 積み替える際に取出して保存する配列
        int next = n;  // 次に取り出すべき数字

        // 元の山が無くなるまで
        while((int)p.size() != 0) {
            for(int i = (int)p.size() - 1; i >= 0; i--) {
                // 上から取出していく値をメモしていく
                use[p[i]] = true;
                add.push_back(p[i]);

                // 探すべき1番大きい値が見つかったら
                if(p[i] == next) {
                    // 答えの山に今取出したカードを積む
                    for(int i = (int)add.size() - 1; i >= 0; i--) ans.push_back(add[i]);
                    // まだ取り出してない1番大きい値を次探すべき数字に変更する
                    for(int j = next; j >= 0; j--) {
                        if(!use[j]) {
                            next = j;
                            break;
                        }
                    }
                    // 元の山からカードを減らす
                    p.erase(p.end() - ((int)p.size() - i), p.end());
                    add = vector<int>();
                }
            }
        }
        for(int i = 0; i < (int)ans.size(); i++) {
            cout << ans[i] << (i + 1 == (int)ans.size() ? "\n" : " ");
        }
    }
    return 0;
}

おわりに

CのREが消えずに無限に悩んでいました。

ABC192参加記

初めに

久しぶりにコンテストに参加したのでこれからは参加するごとに記録を残しておこうと考えました。

A - Star

100の倍数なら100、そうでないなら繰り上げて差をとるだけのはずが、誤読してなぜか1WAしました。

#include<bits/stdc++.h>
using namespace std;

int main()
{
    int x;
    cin >> x;
    if(x % 100 == 0) cout << 100 << endl;
    else cout << (x + 99) / 100 * 100 - x << endl;
    return 0;
}

B - uNrEaDaBlE sTrInG

シンプルに交互に見ていくだけです。

#include<bits/stdc++.h>
using namespace std;

int main()
{
    string s;
    cin >> s;
    for(int i = 0; i < (int)s.size(); i++) {
        if(i % 2  && 'a' <= s[i] && s[i] <= 'z') {
            cout << "No\n";
            return 0;
        }
        if(i % 2 == 0 && 'A' <= s[i] && s[i] <= 'Z') {
            cout << "No\n";
            return 0;
        }
    }
    cout << "Yes\n";
    return 0;
}

C - Kaprekar Number

Kが小さいのでK回くりかえすだけです。
文字列としてソートして整数に変換すると簡単でした。

#include<bits/stdc++.h>
using namespace std;

int main()
{
    int n, k;
    cin >> n >> k;
    for(int i = 0; i < k; i++) {
        string s = to_string(n);
        string t = s;
        sort(s.begin(), s.end());
        sort(t.rbegin(), t.rend());
        n = stoi(t) - stoi(s);
    }
    cout << n << endl;
    return 0;
}

D - Base n

二分探索することまでは分かったのですが、オーバーフローまわりの実装が難しくて実装しきれませんでした。

E - Train

ダイクストラの移動の遷移にTを考慮するだけでいけるのかなと思って書いたら解けました。

#include<bits/stdc++.h>
using namespace std;

const long long INF = ((1LL << 62) - (1LL << 31));

using P = pair<long long,long long>;

struct edge{
    long long to;
    long long cost;
    long long clock;
};

vector<long long> dijkstra(int x, vector<vector<edge>> G){
    priority_queue<P, vector<P>, greater<P>> que;
    vector<long long> dist(G.size(), INF);
    dist[x] = 0;
    que.push(P(0, x));
    while(!que.empty()) {
        P tmp = que.top();
        que.pop();
        int v = tmp.second;
        if(dist[v] < tmp.first) continue;
        for(edge e : G[v]) {
            // 今の時間から次の遷移をするまでの待ち時間を考慮して遷移。
            long long nextCost = dist[v] + e.cost + ((tmp.first + e.clock - 1) / e.clock * e.clock - dist[v]);
            if(dist[e.to] > nextCost) {
                dist[e.to] = nextCost;
                que.push(P(dist[e.to], e.to));
            }
        }
    }
    return dist;
}

int main()
{
    int n, m, x, y;
    cin >> n >> m >> x >> y;
    x--;
    y--;
    vector<vector<edge>> G(n);
    for(int i = 0; i < m; i++) {
        int a, b;
        long long t, k;
        cin >> a >> b >> t >> k;
        a--;
        b--;
        G[a].push_back(edge{b, t, k});
        G[b].push_back(edge{a, t, k});
    }
    vector<long long> dist = dijkstra(x, G);
    if(dist[y] == INF) cout << -1 << endl;
    else cout << dist[y] << endl;
    return 0;
}

F - Potion

使う個数の決め打ちかなとまでは思ったのですがその後の考察が思いつかなかったので解けませんでした。

終わりに

知っているアルゴリズムを応用して問題を解けたので多少は成長しているのかなと感じました。

Vue.jsでAtCoderのレートのグラフを取得して表示したい

経緯

最近少しフロントエンドを触り始めて、Vue.jsを使ってポートフォリオを作ろうとしていました。
そこで私はAtCoderをやっていたので、せっかくだからレートのグラフを表示してみたいなと思いました。

Vue.js

なぜVue.jsを選んだのかというとVue, React, Angularを触ってみた感じ、個人的に分かりやすかったのがVueだったからで、特に深い理由はありません。
Vue.js自体の使い方については公式サイトや他の方の記事などがたくさんあるのでここでは特に触れないです。

以下公式ページから

Vue (発音は / v j u ː / 、 view と同様)はユーザーインターフェイスを構築するためのプログレッシブフレームワークです。他の一枚板(モノリシック: monolithic)なフレームワークとは異なり、Vue は少しずつ適用していけるように設計されています。中核となるライブラリは view 層だけに焦点を当てています。そのため、使い始めるのも、他のライブラリや既存のプロジェクトに統合するのも、とても簡単です。また、モダンなツールやサポートライブラリと併用することで、洗練されたシングルページアプリケーションの開発も可能です。 (https://jp.vuejs.org/v2/guide/)

AtCoderAPI

AtCoderには基本的にはAPIは提供されていませんが、1つだけ、個人のコンテストの成績表のAPIが提供されています。
ここにアクセスすると指定したユーザー名のコンテスト成績のデータがjson形式で帰ってきます。

https://atcoder.jp/users/tourist/history/json

touristのところを書き換えると任意のユーザー名のデータを取得できます。

f:id:amami0522:20210219165921p:plain

全てのデータが一気に返ってくるので少し分かりづらいですが、要素ごとに分解するとこんな感じになっています。

{
        "IsRated": true,
        "Place": 2,
        "OldRating": 0,
        "NewRating": 2720,
        "Performance": 3920,
        "InnerPerformance": 3920,
        "ContestScreenName": "agc004.contest.atcoder.jp",
        "ContestName": "AtCoder Grand Contest 004",
        "ContestNameEn": "",
        "EndTime": "2016-09-04T22:50:00+09:00"
},

なんかたくさんの情報がありますが今回必要なのはNewRatingですね。

とりあえずjsonを取得するコードを書いてみましょう。
データの数が多いので最初の1つだけ表示してみます。

const fetch = require('node-fetch');

fetch('https://atcoder.jp/users/tourist/history/json')
.then(response => {
    return response.json();
})
.then(json => {
    console.log(json[0]);
});

これを実行してみると。

f:id:amami0522:20210219171311p:plain

無事にコンテストの結果が取得できました。
ここでNewRatingの部分をを表示するには、

console.log(json[0]);

となっているところを、

console.log(json[0].NewRating);

または

console.log(json[0]['NewRating']);

に変えればいいですね。

f:id:amami0522:20210219171215p:plain

無事に表示できました。

Chart.js

Chart.jsはグラフの描画を簡単に行えるJavascriptのライブラリです。

vue-chart.js

vue-chart.jsについては以下の公式サイトより

vue-chartjs は Chart.js をvueで使用するためのラッパーです。 再利用可能なチャートコンポーネントを簡単に作成できます。

Vue.jsでChart.jsを使うために必要なものって認識です。

Vue.jsでAtCoderAPIを取得する

先程と同様にAtCoderAPIを取得します。
とりあえずAPiを取得してコンソールに表示するようにしてみます。

まずはAPIを取得するファイルをsample.vueとして書きます。

<template>
    <div>
    </div>
</template>

<script>
export default {
    name: "sample",
    mounted() {
        this.getData();
    },
    methods: {
        getData: function () {
            fetch('https://atcoder.jp/users/tourist/history/json')
            .then(response => {
                return response.json();
            })
            .then(json => {
                console.log(json);
            })
        }
    },
}
</script>

<style scoped>
</style>

次にこのモジュールを使用してsample.vueを表示するapp.vue

<template>
    <div id="app">
        <sample/>
    </div>
</template>

<script>
import sample from "@/components/sample";

export default {
    name: 'App',
    components: {
        sample
    }
}
</script>

<style>
#app {
    font-family: Avenir, Helvetica, Arial, sans-serif;
    -webkit-font-smoothing: antialiased;
    -moz-osx-font-smoothing: grayscale;
    text-align: center;
    color: #2c3e50;
    margin-top: 60px;
}
</style>

これでlocalhost:8080にアクセスするととりあえずコンソールに取得したjsonが取得されるはず。

しかしここで問題が

f:id:amami0522:20210219174606p:plain

先程は上手くいったフェッチが失敗したとのエラーが。

エラーを読んでみるとCORS policyとやらによってlocalhost:8080からのリクエストはブロックされたとのこと。

色々調べてリクエストヘッダーの情報を変更してみたりと色々試しましたが出来なかったのでとりあえず別にAPIサーバを立てることに。

一時的にhttp://localhost:3000/api/result/にアクセスしたらAPIを取得してそれをjsonで返すAPiサーバを立てることに。(ややこしい)

APIサーバはJavascriptを使ってこんな感じに。

const express = require('express');
const app = express();

const fetch = require('node-fetch');
const cors = require('cors');

const corsOption = {
    origin: 'http://localhost:8080'
}

app.use(cors(corsOption));

app.set('port', (process.env.PORT || 3000));

app.get('/api/result/', function(request, response) {
    fetch("https://atcoder.jp/users/tourist/history/json")
    .then(res => {
        return res.json();
    })
    .then(json => {
        response.send(json);
    })
});

app.listen(app.get('port'), function() {
    console.log('Listening on ' + app.get('port'));
});

corsOptionでVue開発用のhttp://localhost:8080からのリクエストを許可するように設定しました。
そして、先程のsample.vueのfetchするURLを以下のように書き換えます。

fetch('http://localhost:3000/api/result/')

すると、以下のように取得できました。

f:id:amami0522:20210219183101p:plain

あとは、Chart.jsにデータとしてこれを送るだけです。

実際にはChart.jsを利用するJavascriptファイルを用意して、それを読み込む側からデータを送るという感じでした。

これに関しては公式ドキュメントをそのまま写します。 最終的にはこんな感じになりました。

Chart.jsを利用するlineChart.js

import { Line, mixins } from 'vue-chartjs';
const { reactiveProp } = mixins;

export default {
    mixins: [Line, reactiveProp],
    props: ['options'],
    mounted() {
        this.renderChart(this.data, this.options);
    }

}

APIを取得してそれをlineChart.jsに送るdraw.js

<template>
    <div>
        <h2>AtCoder</h2>
        <div class="graphArea">
            <lineChart :chart-data="datacollection" :option="options"/>
        </div>
    </div>
</template>

<script>
import lineChart from "@/components/lineChart";

export default {
    name: "draw",
    components: {
        lineChart
    },
    data: function() {
        return {
            datacollection: null,
            options: null,
        }
    },
    mounted() {
        this.fillData();
    },
    methods: {
        // 取得したAtCoderのレートをlineChart.jsに送るようにデータを編集
        fillData: function() {
            fetch("http://localhost:3000/api/result")
            .then(res => {
                return res.json();
            })
            .then(json => {
                let year = "0";
                let graphLabels = [];  // グラフに表示されるラベル
                let graphRating = [];  // グラフに描画するレートのデータ
                for(let i = 0; i < json.length; i++) {
                    if(json[i]['IsRated']) {
                        // コンテスト終了の年を取得
                        const nowYear = json[i]['EndTime'].substr(0, 4);

                        // 年が更新されたらラベルに表示
                        if(nowYear !== year) { year = nowYear; graphLabels.push(year); }
                        else { graphLabels.push(""); }

                        // レートをグラフのデータに追加
                        graphRating.push(json[i]['NewRating']);
                    }
                }

                // グラフのオプションの設定
                this.options = {
                    responsive: true,
                    maintainAspectRatio: false,
                };
                // グラフのデータの設定
                this.datacollection = {
                    labels: graphLabels,
                    datasets: [
                        {
                            label: 'レート',
                            data: graphRating,
                            fill: false,
                            lineTension: 0
                        }
                    ]
                };
            })
        }
    },
}
</script>

<style scoped>
.graphArea {
    margin: 50px auto;
    width: 500px;
}
</style>

ということでlocalhost:8080にアクセスすると

f:id:amami0522:20210219184101p:plain

いい感じにグラフを描画することが出来ました。

終わりに

こんな長いだらだらとした文章に付き合っていただいてありがとうございました。
CORSというものを始めて聞いたりとまだまだWebアプリケーションの難しさを実感しました。
まあ個人的な妥協点として解決出来たので今のところはこれで終わっておきます。
もっといい方法があれば教えて欲しいです。
ありがとうございました。

初めてtopcoder SRMに参加した話

競技プログラミングを始めてから結構経っていましたが初めてtopcoderSRM(Single Round Match)に参加してきました。
今回私が参加したのはSRM 788でした。

topcoderとは

競技プログラミングコンテストサイトの1つで、他にも日本のAtCoder、ロシアのCodeforces等があります。

SRMとは

定期的にtopcoderが開催している競技プログラミングコンテストで、比較的短時間のコンテストなので気楽に参加することが出来ます。

つまずいたこと

普段は主にAtCoderのコンテストばかり出ていたので、仕様の違いでつまずいたことを少し書いていければなと思っています。

コンテストへの参加方法が分からない

自分がなかなかSRMに参加できなかった大きな理由がこれです。
AtCoderCodeforcesはブラウザ上でコンテストが開催されるためユーザー登録さえしていれば簡単にコンテストに参加できるのですが、topcoderでは以下のようになります。

アカウント作成

まずtopcoderにアクセスしてアカウント作成します。

アプレットの準備

Javaをインストールしておきます。
次にtopcoderのサイトのヘッダー部分から「COMMUNITY」→「Compete」→「Competitive Programming」の順にクリックした先のページからJAVA APPLET ARENAをダウンロードします。
ダウンロードしたContestAppletProd.jnlpというファイルを実行してアプレットを起動します。

参加登録

起動したアプレットtopcoderのアカウントでログインします。
ヘッダー部分の「Active Contests」をクリックして参加したいコンテストをクリックし、「Register」で参加登録を行います(コンテスト開始5分前まで参加登録可能です)。
コンテスト開始5分前になると先程の「Register」の下にある「Enter」からコンテストに参加することが出来ます。

ひとまずここまでが初めてコンテストに参加するまでの流れになります。
次からはコンテストの流れについて見ていきます。

コンテストの流れ

コンテストでは主に4つのフェーズに分かれています。

  1. コーディングフェーズ
  2. INTERMISSION
  3. チャレンジフェーズ
  4. システムテスト

    コーディングフェーズ

    時間になったら「Select one」から問題を開いてコーディングを始めてくのですが、AtCoderCodeforcesと違い、コード全部を実装するのではなく、(C++の場合)指定されたクラスを実装します。

    問題文は基本全部英語です。

    注意点としては、問題を開いてから提出するまでの時間が短いほど高得点なのでまだ解かない問題は開かないことをおすすめします。
    また、提出をしなくても1問でも問題を開くとレートが変動します。

    コードが書けたら「Compire」を押して、コンパイルが通ったら「Batch Test」でサンプルケースを試すことが出来ます。
    そして「Submit」ボタンでコードを提出することが出来ます。

    ここではまだ正解、不正解については分からず、この時間で提出した場合の点数のみが教えられます。
    正解、不正解については後述のシステムテストで判明します。
    また、再提出も原点対象なので注意。

    INTERMISSION

    5分間の休憩時間

    チャレンジフェーズ

    同じroom内の他の人のコードが見られるようになるので、不正確なコードにサンプルケースを与えて撃墜して不正解にすることが出来ます。(嘘解法やコーナーケースへの対処の不備を見つけて指摘する感じ)

    システムテスト

    問題中のサンプルはとても弱いテストケースになっているので、本当に提出したコードが制約を満たす様々な値で正しい動きをするのかのテストが入ります。
    ここでシステムテストに落ちた提出は0点になります。

    結果と感想

    自分はDiv.2に参加して3問中2完で436.6点でした。
    仕様に慣れるのに時間がかかってしまい、解けたけど思ったより低い点数となってしまいました。

    レートは1191でGreenとなりましたがtopcoderの初期レートが1200らしいので-9で普通に冷えました。

    でもまあ初めてにしてはまずまずの結果なのかなと思いました。
    普段AtCoderに慣れすぎていたせいか少し手間取ってしまったけどなんとか2問解けて安心しました。

Codeforces Round #653 D - Zero Remainder Array

問題概要

 n 要素の配列  A と整数  k が与えられる。
とある変数  x (初期値0)を用いて1回のうちに以下の操作のどちらかを行う。

  •  x の値を1増やす

  •  x の値を  A のうちのいずれかの要素  A_i に足して、 x の値を  1 増やす

 A のすべての要素を  k の倍数にするためには何回の操作が必要か。 codeforces.com

解説

全てを  k の倍数にするためには全ての  A_i について  (A_i 以上の  k の倍数  - A_i) を足せばいいので、各  A_i について  (k - A_i) mod  k を足せばいいことになります。

 x k 増やす間に  (k - A_i) mod  k 0 ~  (k - 1) をそれぞれ  1 つずつ使うことが出来ます。

ただしこの  (k - A_i) mod  k の値が被ることがあるので、その場合はまた  k 増やす必要があります。

一番被りが多い値のものについて考えれば、その間にそれ以外の値は  k の倍数にすることが出来るので、この一番被りが多い値のものについてのみ考えればいいです。

被りの回数  k 増やすので、(被りの回数) ×k を求めればいいのですが、最後の  1 回は必ずしも  k 増やすのではなく、この被りの一番多い値自体まで増やせばいいので、(被りの回数 - 1) × k+(被りの一番多いものの値)となります。

そして、 x は最初は  0 なので初めに  1 増やすことをふまえて先程の値に  +1すればいいことになります。

実装

#include<bits/stdc++.h>
using namespace std;

int main()
{
    int t;
    cin >> t;
    while(t--){
        long long n, k;
        cin >> n >> k;
        map<int, int> m;
        for(int i = 0; i < n; i++){
            int a;
            cin >> a;
            //kの倍数になるまでの足すべき値がそれぞれ何回出てくるかを数える
            //引き算なのでmodのとり方に注意
            if(a % k) m[((k - a) % k + k) % k]++;
        }
        //最頻値
        long long large = 0;
        //最頻値が何なのか
        long long tmp = 0;
        for(auto&& e : m){
            //それが最頻であったとき
            if(large <= e.second){
                large = e.second;
                //その値をメモする
                tmp = e.first;
            }
        }
        //最初から全てがkの倍数だった時は0
        if((int)m.size() == 0) cout << 0 << endl;
        //k * (最頻値 - 1) + 最頻値の足すべき値 + 1
        else cout << k * (large - 1) + tmp + 1 << endl;
    }
    return 0;
}

以上でこの問題を解くことが出来ました