そうだ、明日京都行こう。

京 都 行 き た い ! ! ! ! !

…失礼しました。授業で「複数のWeb APIを組み合わせてオリジナルのサービスを作ってみましょう！」という演習があって、それで作ったサービスを公開したので紹介します。

https://pandanoir.net/webcomp

「そうだ、京都行こう」というWebサービス(現在地から最短で京都に向かうと何時間でついて、何円かかるか表示するサービス)とかどうでしょうか

— pandanoir (@le_panda_noir) July 16, 2019

(元となったアイデア)

サービスの概要

明日、全国のどこかで開催されるイベントを紹介してくれます。サービス名は「そうだ、明日京都へ行こう。」ですが、京都以外のイベントも表示されます。駅すぱあとで行き方をすぐ見られるので、「明日どっかで遊びたい！！！」となったら0秒で予定を立てることができます。

こんな感じでアクセスするとタイムテーブルと経路情報、イベント情報が表示されます。

要するにクソサービスです。

使用したAPI

• Eventon API(イベント情報の取得)
• 駅すぱあとAPI フリープラン(経路情報の取得)

あと、駅データ.jpから駅データをもらってきて最寄り駅の計算などをしています。

使用技術

• React(create-react-app)
• SCSS
• Nginx
• PHP

外部のAPIを呼び出すだけなので、データベースすら使わずに構築しました。Hooksを使ってガリガリ実装してみましたが、Hooks楽しいですね。Reactがすごく簡潔になるのでいい感じです。

create-react-appもこのくらいのサイズ感なら環境構築の手間がなくなるメリットのほうが大きいのでいいですね。ただ、watchができなくていちいちbuildしないといけないのはBadですが…

最近の状況

ここのところブログの更新をサボっていたので近況報告でお茶を濁そうと思います。生存報告とかいう動画を投稿するYouTuberっぽいですね。

研究室とか

現在大学4年生で、今年の4月に研究室に配属になりました。前期のあいだは教科書の輪講を主にやっていました。

それから、前期は部活のほうにも週に2、3回顔を出していました。プログラミングと部活の両立はさすがに難しくてプログラミングのほうがおざなりになっていました…

あとは朝バイトに週3で入っていて若干体調が崩れてきています。なんとか立て直したい…

競プロ

4月からはじめた競プロですが、このあいだセールをしていたので螺旋本を購入しました。今は半分くらいまで終わりました。

ここのところ思っているのが、競プロは数学とかなり似ているな、ということです。発想力がなければ解けない問題は、数学と同じで「この問題、あの問題の解法で行けそうじゃないか？」というくらいまで量をこなし知識をつけるしかない気がします。そのため、ABCのDを埋める作業を螺旋本と並行してやっています。センスがある人はぱっと解法が浮かぶのでしょうが、僕にはムリです…

彼女ほしい

ああああああああああああああああああああああああああああああああああああああああああああ彼女ほしいいいいいいいいいいいいいいいいいいいいいいいいいいいいいいいいいいいいいいいいいい

スターリンソートをJSで実装してみた

スターリンソートなる、「整列されていない要素を"粛清"することでO(N)でソートを実現する」というネタが盛り上がっているようなので、便乗して書きました。

実装

まず、空のソート結果を格納する配列を用意します。そして、リストを先頭から見ていきます。ソート結果配列の末尾がリストの要素より小さければ、ソート結果にリストの要素を追加します。

const stalinSort = arr =>
  arr.slice(0).reduce((acc, a) => (acc.length === 0 || acc[acc.length - 1] <= a ? [...acc, a] : acc), []);

スターリンソートの開始位置を変えてみる

このスターリンソートは、[100, 1, 2, 3, 4, 5]のように最大値が先頭に来てしまうと残りの要素がすべて粛清されてしまうという問題点があります(他にもあるやろ！)。そこで、開始位置を変えることで、得られる配列の長さを最大化してみようと思います。

これは「最長部分増加列」を求める問題と同一になります。ちなみに、最長部分増加列を求めるにはO(NlogN)かかるのでスターリンソートのメリットがなくなります。本末転倒ですね。

const bound = comp => (arr, key) => {
    let s = 0, t = arr.length;
    while (t - s > 1) {
        const mid = s + Math.floor((t - s) / 2);
        if (comp(arr[mid], key))
            s = mid;
        else
            t = mid;
    }
    return comp(arr[s], key) ? t : s;
};
const lower_bound = bound((a, b) => a < b);
const upper_bound = bound((a, b) => a <= b);

const longestStalinSort = arr => {
    const dp = [];
    for (const item of arr)
        dp[lower_bound(dp, item)] = item;
    return dp;
};
console.log(longestStalinSort([100,1,2,100,3,4,5]));
console.log(longestStalinSort([1,3,5,2,4,6]));

ICPCに参加して

経緯

4月に研究室の同期から「ICPCに参加しない？」と誘われ、競プロを始めました。そこから約3ヶ月での参加だったので、かなり急ピッチでした。

大会感想

練習ではC、Dも解けていたのですが、本番は焦りと緊張もありBまでしか解けませんでした。

終わったあとにほかのチームに聞いたところ、CもDも考察はおおよそ合っていたうえ、Bまではかなり順調に解けた分、悔しかったです。

全体としては大学内で6位でした。大学内1位(全体でも7位！)のこたつがめさんのチームは5完もしていて、格の差をまざまざと見せつけられました…

反省としては、3時間もの間、集中力を切らさないのは無理なので、甘いものを持ち込んで糖分を取りながら取り組むべきでした。

来年からは社会人なので出られませんが、今回の参加はかなり楽しかったので今後も競プロは続けていこうと思います。

Rubyでコードゴルフするためのtips

AtCoder Beginner ContestのA問題を1分で解くためにRubyを書いているのですが、そのときのTipsが溜まってきたので書いておきます。

入力編

まず入力を受け取るところです。ここを高速で書けるとだいぶ強いです。

a,b,c=gets.split.map &:to_i

1行で与えられた数値A B Cを受け取ります。

単に文字列を受け取りたいなら

s=gets

で構いません。

また、単にgetsとして1行読み込むと、その行を$_という変数で参照できるようになります。こうすると変数に代入する手間が省けます。

gets; p $_.count(1)

出力編

A問題で多いのはYes/Noを出力させる問題、数値を答えさせる問題です。

Yes/Noを答えるときは三項演算子を使うとカンタンです。ただし、他の言語と異なり、?と:の前後にスペースを入れる必要があります(入れなくていいケースもありますが、考える時間がムダなのでとりあえず入れるといいです)。

puts true ? "Yes" : "No"
puts true ?"Yes":"No"

Rubyでは文字列リテラルのほかにシンボルというものがあり、こちらでも同様に出力できます。ここでは:の前のスペースは不要です

puts true ? :Yes: :No
puts true ?:Yes: :No

数値の出力にはpというメソッドを使えます。putsより文字数が削減できます。ただしpで文字列を表示しようとすると、クォーテーションごと表示されてしまうので使えません。

p 42

便利なメソッド・Tips

• "文字列".split 文字列を空白で分割する
• [配列].map マップ関数。非常によく使う
• "文字列"[/正規表現/] 文字列中で正規表現にマッチする部分を返す
• "文字列" =~ /正規表現/ 文字列が正規表現にマッチするか判定する
• "文字列1".count("文字列2") 文字列1のなかで文字列2が出てくる数をカウントする
• [Enumerable].min 数値の配列などで最小値を返す

このあたりはよく使います。