AtCoder水色になりました

競プロ

無事水色になることができた。
f:id:yuji9511yuji:20181014004849p:plain
ぶっちゃけると水色ならもうちょっとすぐになれると思っていた...笑

水色を目前に控えた時にC問題にどハマりして死ぬみたいな展開を何回かやってしまったのでそれでしばらく停滞したんだと思う。
あと、AGC早解きは貴重なレートアップの機会だった()

別にここまでは特にストイックに何かをやったということはなく、過去のC問題とD問題を新しいものから順にやっていってるくらい。
C問題はほとんど解けるけどD問題でヒントなしで行けるのはまだ2~3割程度か。
500点とかになった瞬間手も足も出なくなるケースが多いけどそこは慣れていくしかなさそう。

とりあえず今後レート上げてくためにしばらくはCD早解きになると思うので、まずは最低限400点のD問題をささっと解けるレベルにしていきたいと思ってる。

あと、これからARCになるとNo sub撤退したくなる機会が増えてくる気もするけど、出来るだけしないように心がけよう。
多分レート上がるに従ってレートの減少を怖がり始めるだろうけどそこ気にしてたら肝心の精進の妨げになると思われるので。

これからもしばらくはCD問題の過去問を潰していくつもり。一通り潰した上でこっから伸ばすには何が必要なのかとか考えていこうかな。とりあえず今の所全く要領がつかめないDPをどうにかしないといけない。

github pagesをつくった

githubアカウントさえ持っていれば誰でも気軽に自分のホームページを置くことができるgithub pagesというものをつくってみた。
pages.github.com
作成はめちゃくちゃ簡単だった。

1. (自分のアカウント名).github.io という新しいレポジトリを作成する(正確に一致してないとダメらしい)。

2. cloneして適当にindex.htmlとかつくってcommitする。

3. https://(アカウント名).github.io にアクセスする

これだけ！

面倒な設定なしにSSL化したWebページをすぐ作ることができた。

自分のホームページ作りも兼ねてVue.jsの勉強でもしようかなーと思ってます。

ちなみに自分のページはこれ
https://ysugiyama12.github.io/

シンボリックリンクってなんぞや

よく「シンボリックリンクを貼る」みたいな操作を目にするが、実際に何をしているかちゃんと把握していなかったので調べてみた。

シンボリックリンクとは

別ディレクトリに存在するファイルやディレクトリを参照するファイルのことを指す。
ファイルの実体はそこには存在しないが、そのファイルにアクセスすることで元ファイルへと自動で参照が行われる。
ハードリンクと対比させてソフトリンクとも呼ばれる。

ハードリンクとシンボリックリンクはどう違うのか

ハードリンクは同一ディレクトリ下のみで作成可能で、ディレクトリに対しては実行することができない。
「iノード番号」と呼ばれる、ファイルを識別するための番号が元ファイルと一致する。
つまり、ハードリンクは別のファイル名で同一ファイルにアクセスできるようにしている。

シンボリックリンクではiノード番号ではなくパスを用いてファイルを参照するため、別ディレクトリであってもファイルを参照することができる。
シンボリックリンクを貼った後に元ファイルを移動すると参照できなくなり、元ファイルを消せば消えてしまう。

実行方法

lnコマンドを用いる。 -sをつければシンボリックリンクを、無しならハードリンクを作成する。

2次元いもすをしてみた

競プロ

２次元平面で異なるN個の範囲を示す座標が与えられ、その重なりがもっとも多い部分を求めるような問題。

普通の解法であれば二次元の配列を用意していN個それぞれについて指定された範囲の数値をインクリメントする事になる。

しかし、二次元平面の縦と横の長さをH,Wとするとこの方法の最悪計算量はO(NWH)であり、Nやら二次元平面の縦横の値が大きくなるとTLEしてしまう。

そこで、いもす法というアルゴリズムを用いてこの数え上げをO(N + WH)で行うことを試みる。いもす法は当然１次元でも使用でき、２次元以上の多次元においても適用できるが、今回はわかりやすくて威力を感じられる二次元を選択することにした。

操作の概要としては
1. 左上、右下に+1を、右上と左下に-1をかく
2. 左から右へ書いてある値を足していく
3. 同様に上から下へ書いてある値を足していく

このようにすることで全範囲の累積値が簡単に求まる。WH回のインクリメント操作がたった4回で済むので大きく計算量が落ちる。

ただ、はじめの説明にある+1と-1の場所に少し注意。下の写真に示したように-1を加える場所は右上の角の一つ右、左下の角の１つ下となる。右下に+1するものはx,yともに一つずらした場所となる。このようにすることで左と上から累積和を求めた時に正しく結果が求まるようになる。
f:id:yuji9511yuji:20181010230736p:plain

Combinationの求め方まとめ

競プロ

c++でnCkの計算でnの値に応じた2種類の導出方法をメモ。

  1. nの値が50程度でlong long型に収まるとき

このときはオーバーフローや時間制約を気にする必要はないが、階乗を愚直に計算することはできないので注意する。
nCk = n-1Ck-1 + n-1Ckというパスカルの三角形から導かれる公式を用いることでO(n^2)で計算が可能である。

#include <bits/stdc++.h>
#define rep(i, m, n) for(int i = m; i < (n); i++)
#define print(x) cout << (x) << endl;
#define printa(x,n) for(int i = 0; i < n; i++){ cout << (x[i]) << " ";} cout << endl;
#define printa2(x,m,n) for(int i = 0; i < m; i++){ for(int j = 0; j < n; j++){ cout << x[i][j] << " ";} cout << endl;}
#define printp(x,n) for(int i = 0; i < n; i++){ cout << "(" << x[i].first << ", " << x[i].second << ") "; } cout << endl;
#define INF (1e9)
using namespace std;
typedef long long ll;
typedef struct{
    int x;
    int y;
} P;
typedef struct{
    ll to;
    ll cost;
} edge;
typedef pair<ll, ll> lpair;
int N,K;
ll v[51][51];

void nck(){
    rep(i,0,N+1){
        v[i][0] = 1;
        v[i][i] = 1;
    }
    rep(i,1,N+1){
        rep(j,1,i){
            v[i][j] = v[i-1][j-1] + v[i-1][j];
        }
    }
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> N >> K;
    nck();
    print(v[N][K]);

}

50C25で1e14程度のオーダーなのでN<=50程度の制約であればこちらの方法で問題ない。

  1. nが大きくmodを用いる場合

当然nが1000などになってくればオーバーフローするので1e9+7などの値でmodを取ることを要求してくるのが普通である。
また、nが100000程度になればO(n^2)で計算を行うことも不可能である。
このような場合、逆元を用いたmod計算を行うことで結果を導出することができる。
ここで用いるのがフェルマーの小定理。
aとpが互いに素であるときに
a^{p-1} \equiv 1 \bmod p
が成り立つというものである。詳しいことはこちら↓
mathtrain.jp
この式の両辺にa^{-1}をかけると
a^{p-2} \equiv a^{-1} \bmod p
となる。したがって、aの逆数のmodはa^{p-2}のmodに等しいということがわかる。
これで準備が整う。こうして求まったmodの値を保持しておいて、 n!, ((n-k)!)^{-1}, (k!)^{-1}の3つを掛け合わせて再びmodを取る(この時オーバーフローに注意)ことで答えが求まる。
その場で考えずに貼り付けるケースが多そうだから原理はそこまで重要じゃなさそうだけど。
以下実装の例。

#include <bits/stdc++.h>
#define rep(i, m, n) for(int i = m; i < (n); i++)
#define print(x) cout << (x) << endl;
#define printa(x,n) for(int i = 0; i < n; i++){ cout << (x[i]) << " ";} cout << endl;
#define printa2(x,m,n) for(int i = 0; i < m; i++){ for(int j = 0; j < n; j++){ cout << x[i][j] << " ";} cout << endl;}
#define INF (1e9)
typedef long long ll;
typedef struct{
    int x;
    int y;
} P;

using namespace std;
const ll max_N = 110000;
ll fac[max_N + 1000], facinv[max_N + 1000];
const ll MOD = 1e9 + 7;
ll N,K;

ll power(ll x, ll n){
    if(n == 0) return 1LL;
    ll res = power(x * x % MOD, n/2);
    if(n % 2 == 1){
        res = res * x % MOD;
    }
    return res;
}

ll nck(ll n, ll k){
    if(k == 0 || n == k){
        return 1;
    }
    return fac[n] * facinv[k] % MOD * facinv[n-k] % MOD;
}

ll npk(ll n, ll k){
    if(k == 0 || n == k){
        return 1;
    }
    return fac[n] * facinv[n-k] % MOD;
}



int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> N >> K;
    fac[0] = 0;
    fac[1] = 1;
    rep(i,2,max_N){
        fac[i] = (fac[i-1] * i) % MOD;
    }
    rep(i,0,max_N){
        facinv[i] = power(fac[i], MOD - 2);
    }
    print(nck(N,K));
}

facが通常の階乗のmodで、facinvが逆元を表している。
これを用いるとn = 100000程度であっても答えを得ることができる。

c++でpriority_queueを使ってみた

競プロ

通常のqueueはbfsなどで使うことがあったが遂にpriority_queueを使う問題に遭遇したので使い方をメモしておく。
使ったのはこのD問題
beta.atcoder.jp
これ、結構考察と実行ともに充実してていい問題だと思った。

priority_queueの基本的な使い方はこんな感じ。

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

int main(){
    priority_queue<int , vector<int>, greater<int> > pq;
    pq.push(5);
    pq.push(8);
    pq.push(1);
    while(!pq.empty()){
        print(pq.top());
        pq.pop();
    }
}

greaterは取り出す順番を決める比較演算子で、これを指定すると小さいものから順に出てくる。
名前と挙動が少し間違いやすいので注意が必要かもしれない。
デフォルトではlessなので、何も書かなければ大きい順に出力される。

pairなどの型も要素として用いることができる。その場合定義は下のようにする。

  priority_queue< pair<int, int> , vector< pair<int, int> >, greater< pair<int, int> > > pq;

priority_queueは並び替えをO(logN)で行うことができるので実行後にソートを実行する必要のある問題においてオーダーを下げることが可能となる。

sortのように自作の比較関数も定義できるようなので、時間があればやってみようと思う。

Tampermonkeyを用いたuser scriptの作成

競プロ

最近AtCoderでuser scriptを用いた自分だけのページを作ろうみたいな流れがあるので試しに簡単なuser scriptを作成してみた。

Chromeを使っているので今回はTampermonkeyというChromeのプラグインを用いる。

https://tampermonkey.net/

新規スクリプトを選択すると次のような初期状態になっている。

// ==UserScript==
// @name       ac-menubar
// @namespace  None
// @version    0.1
// @description  メニューバーを自分のrateに合わせて変更
// @match      https://beta.atcoder.jp/*
// @copyright  2018 ysugiyama
/* load jQuery */
// @require http://ajax.googleapis.com/ajax/libs/jquery/1.11.0/jquery.min.js
// ==/UserScript==

一見してコメントのようだが、ここにuser scriptに必要な情報が含まれている。重要なものをいくつか紹介。

  • @name - script名
  • @match - どのurlの時にこのscriptを動かすか
  • @require - このscriptを実行するのに必要なincludeファイルを書く。pathを書けばローカルファイルも読み込むことができる。

続いて、メインとなる処理をJavascriptで書いていく。
今回実装したものは「AtCoderで自分のレートに合わせてヘッダの色が変化する」というもの。
実装はこんな感じにしてみた。AtCoderのAPIあたりの知識がなかったのでajax使って結構無理やりレートを取得したのでいい方法があれば知りたい。

// ==UserScript==
// @name       ac-menubar
// @namespace  None
// @version    0.1
// @description  メニューバーを自分のrateに合わせて変更
// @match      https://beta.atcoder.jp/*
// @copyright  2018 ysugiyama
/* load jQuery */
// @require http://ajax.googleapis.com/ajax/libs/jquery/1.11.0/jquery.min.js
// ==/UserScript==
jQuery(document).ready(function($) {
    function getElementByXpath(path) {
      return document.evaluate(path, document, null, XPathResult.FIRST_ORDERED_NODE_TYPE, null).singleNodeValue;
    }
    var dom = getElementByXpath('//*[@id="navbar-collapse"]/ul[2]/li[2]/a').text.split("(");
    if(dom.length > 0){
        var user_id = dom[0].replace(/[\n	 ]/g, "");
        var user_score = 0;
        $.ajax({
            url: "https://beta.atcoder.jp/users/" + user_id +"/history/json",
            type: 'GET',
            dataType: 'json',
            success: function(info){
                info.forEach(function(e){
                    if(e.IsRated){
                        user_score = e.NewRating;
                    }
                });
                if(user_score < 400){
                    $('.container-fluid').css('background-color', 'gray');
                }else if(user_score < 800){
                    $('.container-fluid').css('background-color', '#a0522d');
                }else if(user_score < 1200){
                    $('.container-fluid').css('background-color', 'green');
                }else if(user_score < 1600){
                    $('.container-fluid').css('background-color', '#afeeee');
                }else if(user_score < 2000){
                    $('.container-fluid').css('background-color', 'blue');
                }else if(user_score < 2400){
                    $('.container-fluid').css('background-color', 'yellow');
                }else if(user_score < 2800){
                    $('.container-fluid').css('background-color', 'orange');
                }else{
                    $('.container-fluid').css('background-color', 'red');
                }
            }
          }
        );
    }
});

過去のレート一覧のページで/json叩くとjsonファイルが取得できるのは初めて知った。
あと、xpathを使ってDOMを選択することも実は初めてだったので勉強になった（前は直接xpathを書いてアクセスする関数があったらしいが廃止されたらしい）。
これを実行するとbeta版のAtCoderのサイトでは下のようにヘッダーの色が変わるようになった。
f:id:yuji9511yuji:20181008001915p:plain

そろそろ水色になりたいなぁ...