こんにちはtatsyです。本日もSRMの解説いきます。 Easy (250点) 問題 太郎はAとBからなる長さNの文字列を作ろうとしている。この文字列を作るときにposition[i]にはvalue[i]が来ることが分かっている。このとき、余っている部分にAとBを埋めて、2文字AあるいはBが続いている箇所数が最小になるようにしたい。この最小の文字列は何種類作れるか？1,000,000,007で割った余りを求めよ ...

こんにちはtatsyです。本日もSRMの解説いきます。 Easy (250点) 問題 ある長さNの文字列が与えられる。このSnukeさんはこの文字列のうちK個を取り除いてあなたに見せる。この際、あなたはSnukeさんが何番目の文字を消したのかを言い当てたい。確実に言い当てられる場合には”Certain”を、そうでない場合には”Uncertain”と答えよ。 解法 確実に言い当てられない場合というのは、結果が同じにな ...

こんにちはtatsyです。 最近、これまでに作ったプログラムをまとめてGithub上で公開する作業を行っていたのですが、その際にOpenCV + GTestをTravis上でテストするのに結構苦労したのでやり方をまとめておきます。 Travis上でやりたいことは次の4つです。 OpenCVをwgetしてきて、Travis上でビルドする GTestをapt-get installしてTravis上でビルドする 自分 ...

こんにちは、tatsyです。 GithubでPull Request (以下PR) を送る機会があったので、参考にしたページなどをまとめておきます。 Pull Requestのやり方 PRの基本的な流れについては以下のページがとても詳しく解説してくださっています。 GithubでForkしてからPull Requestをするまでの流れ 気持ちがはやりすぎてFork後にbranchを作り忘れないようにすれば、おおむね問題なくPRまではい ...

こんにちはtatsyです。本日もSRMの解説いきます。 Easy (250点) 問題 長さがNでAとBの2種類の文字からなる文字列Sがあるとする。このときある2つのインデックスi, j (i < j)に注目した時、S[i] = A, S[j] = Bとなるような組がK個あるような文字列をどれでも良いので出力せよ。ただし、そのような文字列がない場合には空の文字列を返せ。 解法 この問題の条件を言い換えると、文字列に含まれる各Aについてその右側に ...

こんにちはtatsyです。本日もSRMの解説いきます。 Easy (250点) 問題 整数からなる数列が与えられる。この数列から適当にk個を選んで、好きなように並べ替えることができる。このとき各々の数を変化させて、数が1ずつ上がる、あるいは1ずつ下がるようにしたい。変化させるべき数の絶対値の合計の最小値はいくつか？ 解法 この問題は個人的に少し英語が分かりづらかったなぁと思います。 要するに好きに数をk個選んで並び替 ...

こんにちはtatsyです。Node.js + Socket.IOの最終回です。 今回は小さな変更ではありますが、前回までで作成したチャットシステムにタイピング中かどうかを表示する機能を追加してみたいと思います。 タイピングの検知 これはNode.jsやSocket.IOではなく、JavaScriptの問題ですが、input上でユーザがタイピングをしているかどうかを検知する機能を最初に盛り込みます。 ここでは最 ...

こんにちはtatsyです。いつものようにSRMの解説をします。 Easy (250点) 問題 数字N(最大10^18)が与えられるので、これを素因数分解し、その素因数を小さい順に重複を含めて配列として返したい。このときヒントとして、答えの配列の偶数版目の要素(配列番号は0から始まる)が与えられる。 解法 まず、いつも通り単純に考えると、普通にエラトステネスのふるいみたいなことをして、素因数を列挙することが出来そうで ...

こんにちはtatsyです。 前回(第3回の記事)の内容はほぼ、僕の趣味でファイル構成を整えただけでしたが、今回は本格的にチャットの機能を拡充していきます。 ログイン情報のemit まず、基本的なところからでユーザがチャットにログインしたり、ログアウトしたりしたときに、その情報をemitして全クライアントに通知する処理を付け加えます。 やることは簡単でsocket.ioのconnectionイベントが発生し ...

さて第3回目の今回は、前回までで作ったチャットシステムを拡張しやすいように、フォルダ構成などを整えます。 おそらく現時点でのファイル構成は次のようになっていると思います。 それでは、早速準備を整えていきます。 ライブラリ配置ディレクトリの作成 現在のコードではindex.htmlに直接JavaScriptのコードを書き込んだり、jQueryの公式にリンクしたりしていますが、あまりかっこよくないので、配置を ...