AtCoder水色

今年の2月くらいから始めたAtCoderで、ようやく水色ランクに到達できた。

水色 (Bランク R1200~1599 上位15%)
水色はかなり優秀です。

AtCoder(競技プログラミング)の色・ランクと実力評価、問題例 - chokudaiのブログ

とのこと

なんとなくここを最初の一つの目標に定めていたので、どうにか辿り着けて嬉しい。まだ簡単に降級してしまうかもしれないのでせめて維持できるようには今後も頑張りたい、、

始めたきっかけ

あんまり覚えていないけど 今年に入ってから転職活動的なもので幾つか受けたときに そういうプログラミング問題が思ってた以上に出来ないことを痛感して やり始めようかな、と思って

ちょうど春くらいに「私はこうやってG社に〜」っていうブログを幾つか読むと結構AtCoderとかLeetCodeとか出てきたので よしやってみよう!と思い立って始めた

取り組み

とりあえずC++がニガテなのも克服したい、と思ったのですべてC++で挑戦した。 慣れてくると色んなcontainerが使いやすくて好きになってきたのでこれはこれで良い結果。

AtCoderはコンテスト直後に解説がアップロードされるけど 正直それ読んでも分からんもんは分からん…という感じなので 出来そうだったら解けなかったやつを再チャレンジしてみる、というくらい

過去問も少しずつやってみたいとは思いつつあんまり出来ていない…

どちらかというとLeetCodeを日々のトレーニングに使っている。まずは難易度低めのalgorithm問題を、とそのへんを優先的に毎日1〜3問くらい解いてみてる

Problems - LeetCode

何も見ずに解く → 解説読む → Discuss読む → 速度やメモリ消費を改善できる方法みつけたら試してみる

で地道に続けてだいたい200問くらいは解いた

今後

とりあえず次の目標は青色、か…

なんかDP使ってくような問題をマトモに解けたためしがないので、ちゃんと使いこなして解けるようになりたいな

Google Code Jam 2019: Qualification Round

Google Code Jamに今年もチャレンジ。

(昨年の: Google Code Jam 2018: Qualification Round - すぎゃーんメモ)

最近少しずつ AtCoderLeetCodeC++で解く練習をしているので今回のQualification RoundもC++でチャレンジ

Foregone Solution

4 を無くせばいいだけなので 基本的に元の入力を残し 単純に 4 が出てきたときだけ 31 に分割すればいいかな、と。 0 が先頭に来るときだけ注意して後処理で消すなど

#include <bits/stdc++.h>

using namespace std;

pair<string, string> solve(string n) {
    pair<string, string> answer("", "");
    for (int i = n.length() - 1; i >= 0; --i) {
        if (n[i] != '4') {
            answer.first = n[i] + answer.first;
            answer.second = '0' + answer.second;
        } else {
            answer.first = '3' + answer.first;
            answer.second = '1' + answer.second;
        }
    }
    while (answer.second[0] == '0') {
        answer.second.erase(answer.second.begin());
    }
    return answer;
}

int main() {
    int t;
    string n;
    cin >> t;
    for (int i = 0; i < t; ++i) {
        cin >> n;
        auto answer = solve(n);
        cout << "Case #" << i + 1 << ": ";
        cout << answer.first << " " << answer.second << endl;
    }
}

You Can Go Your Own Way

問題読んでしばらく考えて、、これはスタートとゴールを結ぶ対角線で対称に動けばいいだけでは…ということに気付いた。 単純に SE を入れ替えたものを作ればいいだけだった。

#include <bits/stdc++.h>

using namespace std;

string solve(int n, string p) {
    string answer;
    for (int i = 0, l = p.length(); i < l; ++i) {
        answer += p[i] == 'S' ? 'E' : 'S';
    }
    return answer;
}

int main() {
    int t, n;
    string p;
    cin >> t;
    for (int i = 0; i < t; ++i) {
        cin >> n >> p;
        cout << "Case #" << i + 1 << ": " << solve(n, p) << endl;
    }
}

ここまで解いて予選通過ラインは超えたので満足してしまった。

Cryptopangrams

時間あれば解こう、と思って結局間に合わなかった。

素因数分解を正直にやると非常に厄介そうだけど、必ずすべての文字に対応する素数を因数にもつものが存在しているわけだし 作り方から考えると隣接する数値どうしの最大公約数をとれば因数は取れる、ということに気付いた。ユークリッド互除法は知っているのでそれは書ける。

そうして取れる素数たちを並べて対応する文字に置き換えていけばいけそう。 しかし最初が ABABC みたいな感じで 同じ数字が並ぶパターンを考慮していなくてハマった。そこは注意しないといけない。

そして大きな値にも対応できるよう多倍長整数で、と思って以下のようなのを書いた

#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>

using namespace std;
namespace np = boost::multiprecision;

np::cpp_int gcd(np::cpp_int x, np::cpp_int y) {
    return y == 0 ? x : gcd(y, x % y);
}

string solve(np::cpp_int a[], int l) {
    np::cpp_int d, d0;
    for (int i = 0; i < l - 1; ++i) {
        if (a[i] == a[i + 1]) {
            continue;
        }
        d0 = gcd(a[i], a[i + 1]);
        while (i > 0) {
            d0 = a[i--] / d0;
        }
        break;
    }
    d = d0 = a[0] / d0;
    set<np::cpp_int> s { d };
    for (int i = 0; i < l; ++i) {
        d = a[i] / d;
        s.insert(d);
    }
    vector<np::cpp_int> v(s.begin(), s.end());
    string answer = "";
    d = d0;
    for (int i = 0; i < l + 1; ++i) {
        for (int j = 0, ll = v.size(); j < ll; ++j) {
            if (v[j] == d) {
                answer += 'A' + j;
                if (i < l) {
                    d = a[i] / d;
                }
                break;
            }
        }
    }
    return answer;
}

int main() {
    int t, n, l;
    cin >> t;
    for (int i = 0; i < t; ++i) {
        cin >> n >> l;
        np::cpp_int a[l];
        for (int j = 0; j < l; ++j) {
            string s;
            cin >> s;
            a[j] = np::cpp_int(s);
        }
        cout << "Case #" << i + 1 << ": " << solve(a, l) << endl;
    }
}

が、

Solution.cpp:2:44: fatal error: boost/multiprecision/cpp_int.hpp: No such file or directory
 #include <boost/multiprecision/cpp_int.hpp>
                                            ^
compilation terminated.

がびーん。ダメなのか。

ということでそのまま Python3で書き直し。

def gcd(x, y):
    return x if y == 0 else gcd(y, x % y)


def solve(a):
    d0 = 0
    for i in range(len(a) - 1):
        if a[i] != a[i + 1]:
            d0 = gcd(a[i], a[i + 1])
            for j in range(i):
                d0 = a[i - j] // d0
            break
    d = d0 = a[0] // d0
    s = set([d])
    for e in a:
        d = e // d
        s.add(d)
    v = sorted(s)
    d = d0
    answer = ''
    for i in range(len(a) + 1):
        idx = v.index(d)
        answer += chr(idx + ord('A'))
        if i < len(a):
            d = a[i] // d
    return answer


t = int(input())
for i in range(t):
    _, l = [int(x) for x in input().strip().split(' ')]
    a = [int(x) for x in input().strip().split(' ', l)]
    print('Case #{}: {}'.format(i + 1, solve(a)))

以上

4問目はまだ開いてすらいない。余裕あったら挑戦してみよう。。。

Repository

github.com

GCPUG in Nara #3 で話をしました #gcpugnara

奈良で開催された「GCPUG in Nara #3 ~ GCPではじめる機械学習 ~」に、縁あってお声がけいただき 30分ほどお話をさせていただきました。

【奈良】GCPUG in Nara #3 ~ GCPではじめる機械学習 ~ - connpass

以前 Mix Leap Study #29 で話したときからあまりアップデートは無かったけど、GCPUGってことでGCPをこのように使っています、というのを含めてデモを多めに紹介させていただきました。

京都から意外に近いのに奈良での勉強会やコミュニティは全然参加できていなかったので、この機会で奈良の方々と交流できて良かったです。

ありがとうございました!

懇親会で食べた不思議なサラダが忘れられない

将棋駒画像データセットを公開する

以前から少しずつ、将棋の駒を画像分類するためのデータセット作りをしていて

最初は自分のローカル環境でやっていたりしたけど やっぱりWebアプリで管理できた方が良いと思って Webアプリ上に保存して管理するようにしていた。

肖像権などの問題も無いはずだし あったら使いたいというヒトもいるかもしれない、と思ったので公開するようにした。

shogi-dataset.appspot.com

現状では 「空白」「各種14種類の駒 x 先手後手2種類ずつ」で29種類を、素材から自動生成した各種200枚 それに自分で写真や盤面映像をキャプチャした画像などから切り抜いてラベル付けしたもの数十枚ずつ などが保存されている。これから少しずつ集めて増やしていく予定。

仕様

画像データセットを管理するWebアプリを作るときに考えるのは こんな点。

  • 最低限必要な機能は以下
    • 画像アップロード
    • 各画像にアノテーション付与
    • 一覧表示
    • 一括ダウンロード的なもの
  • できれば欲しい認証機能
    • アップロードや編集は特別な権限を持ったユーザだけが可能
    • 閲覧やダウンロードは権限ないユーザにも可能にして良い
  • 自前のサーバではなくどこかのPaaSでアプリケーションだけ動かしたい
    • できるだけ安く。
    • 画像の保存場所も必要

以前のアイドル顔識別のためのデータセットでも管理Webアプリを作ったけど、さくらVPS上でRuby on Railsで動かし画像データはすべてPostgreSQLにバイナリで保存、などやっていて あまりこのへんの条件を満たすことは出来なかった。

今回はGoogle Cloud Platform を使って App Engine でアプリを作ってみた。

  • アプリケーションは Standard Environment のGo環境で
    • ほぼJSON APIだけ提供
    • Front-end は TypeScript + React, React Router などで実装
  • 画像は Cloud Storage にすべてアップロード
  • 画像とラベルの関連付けなどの情報は当然 Cloud Datastore で管理
  • 認証は Github での OAuth Login
    • Tokenを発行して外部からのJSON API利用も可能
    • 編集権限を持ったユーザのみアップロード・編集削除などが可能

実装

最初は普通に Go 1.9 のruntimeで動かしていたのだけど、途中から興味が出たので Go1.11 に切り替えた。 けど結構変更が必要になる部分が多くて大変だった。。

  • Remote APIで一括ダウンロードできるようにしていたけど使えなくなる
  • ユーザ認証機能は自前で実装する必要がある
  • Memcache的なものも別サービスを利用する必要がある

https://cloud.google.com/appengine/docs/standard/go111/go-differences

特に認証のところは 以前は app.yamllogin とか admin とか設定するだけでアクセス制御できていて便利だったのが使えなくなってしまったので自分で用意する必要があった。 github.com/gorilla/sessions でセッション管理して OAuth2 login の設定を書いて。 ログインはもはやGoogleアカウントである必要もなかったので Github の OAuth を使うことにした。

API endpointは github.com/gorilla/mux で書き分けて、MiddlewareでSessionからでもAuthorization Headerからでも認証情報を取得しアクセス制御できるようにした。

Datastoreは基本的にラベルごとの表示や更新順表示ができればいいだけなのでそんなに難しいクエリなどは要らない。ただ各ラベルの画像総件数は常に把握したいので Total 情報を格納するEntityを1つだけ作って新規追加・編集・削除時に毎回値を増減させるようにした。

追加・編集操作は結局自分しか使わない感じになりそうだけど、できるだけ便利なUIを追求して作業を効率化していきたい。

あとアプリケーションのテストを書いていないので testerator とか使ってちゃんと書いておきたい…

Repository

https://github.com/sugyan/shogi-dataset

YAPC::Tokyo 2019 に参加した

yapcjapan.org

YAPC::Okinawaへの参加に続いて、今回も参加。 京都からの移動になんとなく夜行バスを使ってみたけど まぁまぁキツかった…

今回トークを聴いたのは

  • 2019年冬のPerl (charsbarさん)
  • Perl to Go (xaicronさん)
  • Perl on Rails (onkさん)
  • レガシーPerlビルド 〜現代に蘇るPerl[1..5].0とPerl6〜 (八雲アナグラさん)
  • WebVRで作品を作って展示しよう (hitode909さん)
  • ISUCON8予選問題作成の裏側 (karupaneruraさん)
  • 多くのCPAN Authorに育てられ、息をするようにCPANモジュールを書けるようになり、そして分かったこと (Songmuさん)
  • Keynote (tokuhiromさん)

など。

色々なヒトたちに会ってお話できて、楽しかったです。

次回は京都? マジ?? まぁとにかく次回も参加したいと思います。

運営の皆様、素敵なトークをしてくださった皆様、会場で絡んでくださった皆様、ありがとうございました!!

電子工作 4作目・Corne Cherry

f:id:sugyan:20181214120545j:plain

HelixPico、Mint60、ErgoDash に続いて、自作キーボード 4作目。

今回作ったのは Corne Cherry。 この記事はCorne Cherryを使って書いています。

booth.pm

なぜ Corne Cherry を選んだか

これまで3種類ほど作ってきて、Ortholinear(格子配列)、Row-Staggered(横にズレている)、Column-Staggered(縦にズレている) とそれぞれ使ってみて やはりColumn-Staggeredが良さそう、と思い しかしErgoDashはちょっとキーが多すぎて絶対に使わないものも存在していてアレだし、あとGateron Brownのキースイッチ使ってみたけどちょっと打鍵音があって職場とかで使いづらいかな…と思って家での使用のみにしていた。

その点 Corne Cherryは

  • Column-Staggered 配列で キーが42個と少なめでコンパクト
    • 自分的には理想のキー数 & 配置
  • Kailh PCBソケットでキースイッチのホットスワップが可能

というあたりが魅力。

組み立て

ひたすら Build Guide とにらめっこしながら間違わないよう気をつけて丁寧に。

f:id:sugyan:20181206184131j:plain f:id:sugyan:20181211191441j:plain f:id:sugyan:20181214015009j:plain

ダイオードがチップ型で 表面実装と呼ぶもの? は初体験だったので難しかった。というか部品が小さすぎてすごい神経つかうし おじさんにはつらい…。 やっぱりこのへんになってくると フラックスというものが必要になってきそう。

あとは LEDもオプションながらパーツ買ってしまっていたので折角だから挑戦してみた。 が、見事に敗北。

つけたり外したりしながら何度かチャレンジして ようやく3つだけ光らせることができた……

4番目の場所のを付け直そうとして外してるときにランドの方まで剥がれてしまい 修復が困難そうだったので まぁ別に光らなくてもいいし… ってことで裏面の3つだけで終了とした。

キースイッチ・キーキャップ

今回は キースイッチは "Gateron MX Silent Switch Brown" という静かなタイプのもの (勿論あとから付け替えることも出来るのだけど)、キーキャップはErgoDashでDSAのものを使っていたけどそれほど好みでもなかったので XDAのものにしてみた。

talpkeyboard.stores.jp

talpkeyboard.stores.jp

キーマップ

これは以前から考えていた通りに自分にとって最適のものを設定。

--- keyboards/crkbd/keymaps/default/keymap.c    2018-12-14 02:21:01.000000000 +0900
+++ keyboards/crkbd/keymaps/sugyan/keymap.c     2018-12-15 17:24:59.000000000 +0900
@@ -60,37 +60,37 @@
 const uint16_t PROGMEM keymaps[][MATRIX_ROWS][MATRIX_COLS] = {
   [_QWERTY] = LAYOUT_kc( \
   //,-----------------------------------------.                ,-----------------------------------------.
-        ESC,     Q,     W,     E,     R,     T,                      Y,     U,     I,     O,     P,  BSPC,\
+        TAB,     Q,     W,     E,     R,     T,                      Y,     U,     I,     O,     P,  BSLS,\
   //|------+------+------+------+------+------|                |------+------+------+------+------+------|
-      CTLTB,     A,     S,     D,     F,     G,                      H,     J,     K,     L,  SCLN,  QUOT,\
+       LCTL,     A,     S,     D,     F,     G,                      H,     J,     K,     L,  SCLN,  QUOT,\
   //|------+------+------+------+------+------|                |------+------+------+------+------+------|
-       LSFT,     Z,     X,     C,     V,     B,                      N,     M,  COMM,   DOT,  SLSH,  RSFT,\
+       LSFT,     Z,     X,     C,     V,     B,                      N,     M,  COMM,   DOT,  SLSH,   ENT,\
   //|------+------+------+------+------+------+------|  |------+------+------+------+------+------+------|
-                                  GUIEI, LOWER,   SPC,      ENT, RAISE, ALTKN \
+                                   LALT,  LGUI,   SPC,     RSFT, LOWER, RAISE \
                               //`--------------------'  `--------------------'
   ),

   [_LOWER] = LAYOUT_kc( \
   //,-----------------------------------------.                ,-----------------------------------------.
-        ESC,     1,     2,     3,     4,     5,                      6,     7,     8,     9,     0,  BSPC,\
+        ESC,  EXLM,    AT,  HASH,   DLR,  PERC,                   CIRC,  AMPR,  ASTR,  LPRN,  RPRN,   DEL,\
   //|------+------+------+------+------+------|                |------+------+------+------+------+------|
-      CTLTB,    F1,    F2,    F3,    F4,    F5,                     F6,    F7,    F8,    F9,   F10, XXXXX,\
+       LCTL,  UNDS,  PLUS,  LCBR,  RCBR,  TILD,                    GRV,  MINS,   EQL,  LBRC,  RBRC, XXXXX,\
   //|------+------+------+------+------+------|                |------+------+------+------+------+------|
-       LSFT,   F11,   F12,   F13,   F14,   F15,                    F16,   F17,   F18,   F19,   F20, XXXXX,\
+       LSFT,     1,     2,     3,     4,     5,                      6,     7,     8,     9,     0, XXXXX,\
   //|------+------+------+------+------+------+------|  |------+------+------+------+------+------+------|
-                                  GUIEI, LOWER,   SPC,      ENT, RAISE, ALTKN \
+                                   LALT,  LGUI,   SPC,     RSFT, LOWER, RAISE \
                               //`--------------------'  `--------------------'
   ),

   [_RAISE] = LAYOUT_kc( \
   //,-----------------------------------------.                ,-----------------------------------------.
-        ESC,  EXLM,    AT,  HASH,   DLR,  PERC,                   CIRC,  AMPR,  ASTR,  LPRN,  RPRN,  BSPC,\
+      XXXXX,    F1,    F2,    F3,    F4,    F5,                     F6,    F7,    F8,    F9,   F10, XXXXX,\
   //|------+------+------+------+------+------|                |------+------+------+------+------+------|
-      CTLTB, XXXXX, XXXXX, XXXXX, XXXXX, XXXXX,                   MINS,   EQL,  LCBR,  RCBR,  PIPE,   GRV,\
+       LTOG, XXXXX, XXXXX, XXXXX, XXXXX, XXXXX,                   LEFT,  DOWN,    UP,  RGHT, XXXXX, XXXXX,\
   //|------+------+------+------+------+------|                |------+------+------+------+------+------|
-       LSFT, XXXXX, XXXXX, XXXXX, XXXXX, XXXXX,                   UNDS,  PLUS,  LBRC,  RBRC,  BSLS,  TILD,\
+      XXXXX, XXXXX, XXXXX, XXXXX, XXXXX, XXXXX,                   HOME,  PGDN,  PGUP,   END, XXXXX, XXXXX,\
   //|------+------+------+------+------+------+------|  |------+------+------+------+------+------+------|
-                                  GUIEI, LOWER,   SPC,      ENT, RAISE, ALTKN \
+                                  XXXXX, XXXXX, XXXXX,    XXXXX, XXXXX, XXXXX \
                               //`--------------------'  `--------------------'
   ),

使用感

良いと思って選んだだけあって 形状・サイズ・配置・打鍵感 など どれもほぼ良い。

ほぼほぼ文句無しなんだけど、あえて挙げると、親指の位置がちょっと不満。 親指用のキーは下部に3つ 押しやすい位置に斜めに並んでいるのだけど、 どうもそれでも最内側のキーがまだ少し遠くて押しづらい…。 ほぼ同じ形状ながらErgoDashの方がこの親指のキーたちが押しやすいな… というのがちょっと使ってみての感想でした。

まとめ

だいたい自分の理想のキーボードってのが分かってきた気がする。 ここからさらにやるとしたら このCorne Cherryをベースに 親指のあたりだけ微調整したものを自分で作るか…? というところか

Mix Leap Study #29 で話をしてきた #mixleap

大阪で開催された「Mix Leap Study #29 - Step up for TensorFlow」に、縁あってお声がけいただき 20分ほどお話をさせていただきました。

yahoo-osaka.connpass.com

TensorFlow関連で、ってことで ここ数年〜最近で取り組んでいる趣味の画像認識について、データセットを集め管理するために取り組んできたことについてデモを混じえて紹介させていただきました。

メインゲストのLaurence氏にも良かったと声をかけていただいたりトークの中で例として引き合いに出して言及してくれたりして 嬉しかったです。 大阪開催のこの規模の勉強会で話すのも始めてで緊張しましたが 懇親会でも多くの方々に声をかけていただき交流できて とても良い時間になりました。 今後もこういうイベントに積極的に出ていけるよう引き続き頑張っていこうと思います。ありがとうございました!