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次元いもすをしてみた
2次元平面で異なるN個の範囲を示す座標が与えられ、その重なりがもっとも多い部分を求めるような問題。
普通の解法であれば二次元の配列を用意していN個それぞれについて指定された範囲の数値をインクリメントする事になる。
しかし、二次元平面の縦と横の長さをH,Wとするとこの方法の最悪計算量はO(NWH)であり、Nやら二次元平面の縦横の値が大きくなるとTLEしてしまう。
そこで、いもす法というアルゴリズムを用いてこの数え上げをO(N + WH)で行うことを試みる。いもす法は当然1次元でも使用でき、2次元以上の多次元においても適用できるが、今回はわかりやすくて威力を感じられる二次元を選択することにした。
操作の概要としては
1. 左上、右下に+1を、右上と左下に-1をかく
2. 左から右へ書いてある値を足していく
3. 同様に上から下へ書いてある値を足していく
このようにすることで全範囲の累積値が簡単に求まる。WH回のインクリメント操作がたった4回で済むので大きく計算量が落ちる。
ただ、はじめの説明にある+1と-1の場所に少し注意。下の写真に示したように-1を加える場所は右上の角の一つ右、左下の角の1つ下となる。右下に+1するものはx,yともに一つずらした場所となる。このようにすることで左と上から累積和を求めた時に正しく結果が求まるようになる。
Combinationの求め方まとめ
c++でnCkの計算でnの値に応じた2種類の導出方法をメモ。
- 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程度の制約であればこちらの方法で問題ない。
- nが大きくmodを用いる場合
当然nが1000などになってくればオーバーフローするので1e9+7などの値でmodを取ることを要求してくるのが普通である。
また、nが100000程度になればO(n^2)で計算を行うことも不可能である。
このような場合、逆元を用いたmod計算を行うことで結果を導出することができる。
ここで用いるのがフェルマーの小定理。
aとpが互いに素であるときに
が成り立つというものである。詳しいことはこちら↓
mathtrain.jp
この式の両辺にをかけると
となる。したがって、の逆数のmodはのmodに等しいということがわかる。
これで準備が整う。こうして求まったmodの値を保持しておいて、の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のプラグインを用いる。
新規スクリプトを選択すると次のような初期状態になっている。
// ==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のサイトでは下のようにヘッダーの色が変わるようになった。
そろそろ水色になりたいなぁ...
ぼくのDOSS奮闘記 〜LibreOfficeを手探ってみた〜 3/3
発表まで残された日数はあと授業2回分しかないが、流石に実装したものが1つだけというのは物悲しいので、追加で機能を実装することにした。まず自分たちで思いついた案としては「if文で用いるような論理和、論理積を記号を用いて"&&", "||"のように書けるようにする」というものがあった。もう一つ、先生が出してくれた案として、「libreoffice上からターミナル上で入力できるようなコマンドを実行できるようにする(シェル関数の実装)」というものがあり、これは自分たちには思いつかなかった面白い発想かつ大して面倒な実装ではない気がしたので、圧倒的感謝をしつつ早速取り組むことにした。
しかし、ここで1つ目の実装に6日もかかってしまったことを思い出した。また軽い気持ちで取り組んだらこの前のようになるのではないかという不安が3人の頭をよぎった。
だが、この2つの実装、どちらもあっけなく1日で終わってしまった。やはり前回のCombinationでノウハウを習得していたことが大きかっただろう。
簡単に実装内容を説明しておこう。まずシェル関数の実装に関しては=SHELL("")という形でコマンドを入力する形をとり、ユーザーが入力した文字列を中でpopen関数に渡すという形をとった。出力結果を返り値として取得してセルに反映させる。ただ1つ注意点として、libreofficeの中で文字列はOUStringという独自に定義した型を用いている。したがって入力として受け取ったOUString型をString型に一度戻してからpopenに流し込み、得られた出力結果は再度OUString型に直してからセルに出力するようにした。こうすることで各種シェルコマンドを実行してくれる関数が実装できたわけだが、当然セキュリティ的にはとても問題がありそうな匂いがするので実際に有用かと言われると微妙なところである。
さて、もう一つの実装である論理和・論理積についてもまとめておく。こちらは一見すると組み合わせ演算子の時と変更点は全く同じように見えるが、一つだけつまずいたポイントがあった。それは演算子が&&など2文字で表されることである。どういうことかというと、組み合わせ演算子の時と同じようにするとプログラムは1文字目の&を読んだ時点でそれを演算子(&1文字だと文字列結合の演算子)と認識してしまい、演算子のあとに再び演算子→構文エラーとなってしまうのである。そこで、文字列から演算子を切り出す条件を決めている部分を探す必要があり、ここを見つけ出すのに少し苦労した。結果的にsc/source/core/tool/compiler.cxxに「この記号がきたら次来るのはこの要素」と決定している部分があった。言葉ではわかりづらいので具体的にコードを載せておく。
$ /* & */ t[38] = ScCharFlags::Char | ScCharFlags::WordSep | ScCharFlags::ValueSep;
38は&の文字コードで、この行は&演算子の後にCharまたはWordSepまたはValueSepが来ることを示していて、演算子としてはここで区切られることを示している。ここを変えてしまうことも考えたが、とりあえず&& と ||の時のみ対応させようと考え、「文字&または|を読み取った時、次の文字を見てそれが&か|だったらそれも同一の演算子に含める」という記述を加えることでこの問題は解決した。
おわりに
こうして追加で考えた2つの機能の実装も完了し、なんとか発表までにまとめることができた。一人では到底ここまで到達することができなかったので、ひとえに他のメンバーや教授、TAの方々のおかげである。ここに書いたことは実際に進捗を生んだ部分をかいつまんで書いているだけであり、本当はかなり何もできない時間が長かったことを知っておいてほしい。
この実験を通して普段いじらないような大規模なソフトに取り組めたことは貴重な経験だったし、デバッガがとても有効な手段だということを改めて知ることができた。また、全体像がわからなくても適当に存在しそうな変数名でgrepを実行すると案外たどり着くものだなという地道な努力の素晴らしさにも気づくことができた。後からこの記事を読んだ人がこの授業がどのようなものなのか、どのような成果が得られるのかを少しでも吸収してもらえたら嬉しい。