Hacktoberfest2018に参加してプルリク送ってTシャツをゲットした話

Hacktoberfestとは

HacktoberfestとはDigitalOceanが主催しているOSSプロジェクトを推進するためにできたイベントで、任意(自分のリポジトリでもOK)のpublicなgithubリポジトリに5回pull requestを送るとオリジナルTシャツがもらえるというなんとまあ気前のいいイベントである。

hacktoberfest.digitalocean.com

実は...

実はHacktoberfestを推進するために別の企業も、このHacktoberfest期間中にある条件を満たしたらTシャツをプレゼントしているところもあります。
例えば、Microsoftだと、Microsoftgithubリポジトリに1回pull request を投げるとTシャツがもらえたり、企業名は忘れてしまったんですが、ドキュメントを日本語翻訳して合計10行マージされたらTシャツがもらえるみたいなところもありました。
これらの情報は公式のサイトには掲載されてなくて自力で探す必要があります。 自分はTwitter#hacktoberfestで監視していたら見つけました。
覚えていれば、Hacktoberfset中にTシャツを配るイベントをやっているサイトが集まる魔法のスプレッドシートみたいなの作りたいですね。

流れ

参加の仕方は、本家の方のHacktoberfestは公式のサイトに登録すれば完了です。 他のやつ(MicroSoftとか)は企業によってバラバラだと思うのでドキュメントを読んでください。MicroSoftのやつはpull request投げたら専用フォームに色々書いて送れば終了でした。
達成目標は10月中に投げたpull requestの数なので、登録前に投げたpull requestもしっかりカウントされます。
期間が終了すると、数日後にhacktoberfestから「Tシャツ送りたいから住所とサイズ教えて」みたいなメールが来るのでそれに記入すれば、あとは届くのを待つだけです。 Tシャツが届くまでがHacktoberfestなので気を引き締めて待機しましょう。 割と注文から到着まで割と時間がかかりました(国際郵便を使ったことないので比較はできませんが...)。自分の場合は、注文が11月中旬で発送が12月初旬、到着が1月の初旬でした。気長に待ちましょう。*1

どんなプルリクを送ったか

自分は、Hexoというnode.js製の静的サイトジェネレータのテーマの日本語対応に、3つプルリクを送りました。開発者の方が海外の方だったので、プルリクの内容を英語で書かないといけなかったのがかなりしんどかった...(PullRequest 英語 で検索しまくってた)
それから、部のサイトのフッターのサイズが少し大きくて気になっていたので、それにプルリクを1つ送りました。
最後は以前見たことのあるOSSのドキュメントのurlが間違っていたのがまだそのままだったので修正のためにプルリクを1つ送りました。

感想

以前にもプルリクを送ったことはあったけど、それは身内での開発だったので割といい加減なpull requestのメッセージで書いてました。けど、今回は本当に見知らぬ人のリポジトリにpull requestを投げるわけなのでかなり文章と編集コードに気を配りながら書きました。先ほども書きましたが、英語のpull requestは本当に悩んで、最終的に教授に添削してもらったりしました。
あとは、以前までは「こんな雑魚プログラマーがプルリク送るなんておこがましい... さらに悪化させそうで...」なんて気持ちになってプルリクを送るのに躊躇していましたが、今は、「よかったらマージされるし、ダメだったらマージされないだけだしとりあえず投げちゃえ」みたいな気持ちになることができました。

最後に

*1:輸送の追跡だとアメリカをうろちょろしてドイツに飛ばされてから日本に来てました

HACK TO THE FUTURE 2019 の本戦に参加した話

ビジュアライザにたくさん提出した。

予選

新卒ブーストがかかったのと運で、予選104位で予選突破することができた。 予選最下位通過らしい。 予選の連絡が来た時は授業中だったので心の中ではしゃいでた。

本戦前日

前泊できたので夕方くらいに東京についた。晩御飯にずっと前から食べたかった蒙古タンメンを食べた。案の定からかったけどすごい美味しかった。本場の蒙古タンメンって感じがした。

当日

会場に行くと運営の方に案内されて社の中へ。受付で「お名前は?」と聞かれたので「みかんです」「あっ、本名でお願いしますw」「あw」みたいなやりとりをした。これでかなり緊張がほぐれたので運営の方に感謝。

会場入りしてPCの設定をしているとwifiが繋がらなくて運営の方にお世話してもらう。
後から気づいたんですけど、繋がらなかった原因は設定を反映してなかったからでした。私が犯人です。運営の方申し訳ない。

席に座るとウォンバットさんと番兵さんと同じ席になり、少し喋っているとすぐに本戦が始まった。

自分がこの時点で書き上げたプログラムは「スキルレベルを全て一定値まで上げるフェーズ」と「ひたすらクエストを受けて稼ぐフェーズ」の前半と後半に動きを分けた。スキルレベルはどこまで上げるのがいいかを全て試したところスキルレベルを全てMAXにする方がいいことがわかった。これを提出すると2.7億点が出た。ちなみにこれを提出するまでに6時間かかった。
次にどっちのフェーズのプログラムを改善するかを考えた。序盤のスキルを上げる順序をもう少し考えればスコアがかなり上がると思ったので実装。時間がなかったのでスキルを上げる順序をランダムで生成して時間いっぱいまでシミュレートした。 最終的に3.2億点が出た。

結果35人中24位だった。予選最下位だったのでかなり嬉しい。

コンテスト後にFUTURE社の紹介があった。FUTURE社...良さそう...

感想

人生初のオンサイトコンテストでかなり緊張したけど、最終的に成果を出せてよかった。 それからオンサイトコンテストに一度出ると次もまた来てやるぞとモチベーションも上がり精進するという最高のサイクルができるのでオンサイトコンテストにで続けられるように精進頑張ります!

(publishにしてなかったので記事の投稿が遅れた...)

Flutterを使ってみた話

この記事は、OIT Advent Calendar 2018の12日目の記事です。

あてんしょん

この記事はにわかプログラマーが書いています。信頼できる記事ではないのでガチプロエンジニアの方はこの記事よりはるかにいい記事が世の中に転がっているはずなのでそちらを参照してください( ✌︎'ω')✌︎

Flutterとは

google社製のクロスプラットフォームアプリを開発できるフレームワークのことで、実は先日version 1.0をリリースしました。開発言語はDartというものでかなりとっつきやすい印象があります。あと何と言っても、デフォルトでマテリアルデザインの部品(ウィジェット)を使うことができるので、綺麗なUIのアプリを高速に作ることができます。素敵だね。
前はReact Nativeを使っていたけど、「いい感じ」のUIを実現するためにはcssを完全に理解してないと無理でしょ、みたいな印象がありました。その点、Flutterはかなり簡単に整ったUIのアプリを作れる作れるそうです。
React大好きマンなので一応言っておくと、ReactNativeはオープンソースのライブラリがFlutterよりはるかに多いのが利点です。

でも環境構築でこけるんでしょう?

こういったフレームワークを使おうとするとまず環境構築でこけるなんてよく聞く話です。私もcocos2dxと言うゲームフレームワークの環境構築で5日くらい溶かした辛い思い出があります。 しかし、Flutterはかなり親切です。
Flutterをインストールしてpathを通してflutterコマンドを使えるようにするとflutter doctorというコマンドが使えます。 このコマンドはflutterの開発環境に「何が足りないのか」「足りてないならどうすればいいのか」を表示してくれます。親切すぎて発狂しそうになります。もし、できなくてもググればだいたいなんとかなります。

とりあえず触って見る

個人的にCardと言うUIパーツが気になったので「画像とその説明文をCard」にしてみます。

import 'package:flutter/material.dart';

void main() => runApp(MyApp());

class MyApp extends StatelessWidget {
  // This widget is the root of your application.
  @override
  Widget build(BuildContext context) {
    return MaterialApp(
      title: 'Flutter Code Sample for material.Card',
      theme: ThemeData(
        primarySwatch: Colors.blue,
      ),
      home: MyStatelessWidget(),
    );
  }
}

class MyStatelessWidget extends StatelessWidget {
  @override
  Widget build(BuildContext context) {
    return Scaffold(
      appBar: AppBar(
        title: Text("Card Layout"),
      ),
      body: Card(
        elevation: 4.0,
        margin: const EdgeInsets.all(16.0),
        child: Column(
          mainAxisSize: MainAxisSize.min,
          children: <Widget>[
            Image.asset("(任意の画像のpath)"),
            Container(
              margin: const EdgeInsets.all(16.0),
              child:Text('''これはインターネットに挑戦するタプリスです。これはインターネットに挑戦するタプリスです。これはインターネットに挑戦するタプリスです。'''
              ),
            ),
          ],
        ),
      ),
    );
  }
}

f:id:mkan_0141:20181211232918p:plain

はい簡単に一瞬でできましたね。良い良い。
今回は簡単にしか実装していませんが、画像と説明文の間にユーザ名、ユーザのアイコン、いいね!ボタンを実装すれば簡単にInstagramもどきや、Twitterもどきを作ることができます。

あとがき

ちょろっと触ってみただけですが、かなり簡単にUIを実装することができ、非常にとっつきやすい印象がありました。もしかしたらReactNativeよりいいんじゃないかと思ってます(けどReactNativeも捨てがたい...)。
実装もかなり楽しくできるので長期休暇にFlutterでアプリ開発して、バズらせて一攫千金を狙いたいです。

ICPC2018国内予選 参加記

とりあえずチーム紹介

おみかんより梨が好き!!この記事の作者!!mkan!!
最年長!!最年長!!hmさん!!!
チームの紅一点!!実質友利奈緒!!chocobo君!!!

あとチーム名はodanでした

開始よりn時間前の話

避難勧告のアラートで6時に起床.通学経路のJRが全滅してる中で近鉄電車が動いてたので気合いで大学に向かう.
とりあえずマスコットは忘れず持っていく.

開始まで5時間くらい時間があったので,研究室の大きいディスプレイといい感じのスピーカーがあるので,アニメ見ながらAOJで拡張ダイクストラの問題を解いてたけどサンプルが通らず辛かった.ACはできてない.

開始の2時間前くらい

チームメンバーが到着する.
集まったのでとりあえず環境を整えるのとライブラリの印刷と,本番環境で使えない関数があったのでその対処法を考えてた.この辺りでchocobo君が友利奈緒になる.何が起こったのか分からないけど僕にも分からなかった.
練習用の問題をとりあえず解いてたけどsampleが合わずに辛くなる.cinの後にgetlineするとgetlineが改行を拾ってしまってダメだったみたい. そんなこんなでコンテストが始まる.

予選開始

Aをmkan,Bをhmさん, Cをchocobo君でD以降をみんなで解いていこうという方針でした.

0:00
問題を刷ってA問題を読む. A問題を読むとやるだけだったのでやって見るとsampleが通る.けどオーバーフローとか怖かったのでchocobo君に制約を確認してもらってから提出する.

0:08
A問題AC!ヤッタネ!!

0:09 ~
chocobo君とhmさんがBとCを解く.chocobo君は速攻で解法を見つけて実装するも計算量が厳しいことに気づいてhmさんとPCをswapする. B問題は実装がつらそうだった.

0:59 C問題AC!!

B問題はもう少し実装に時間がかかりそうだったのでD問題をchocoboと考察.

1:52 B問題AC!!

D問題をみんなで考察するもダメでした.

結果3完83位でした

AOJ1136 Polygonal Line Search ~ 座標を90度回転させたくなったので ~

問題

Polygonal Line Search

方針

・比較対象を90度ずつ回転させて始点を元の図に合わせてひたすら判定を繰り返す.
・後ろから比較しないと一致しない場合があるのでそれを考慮する.
計算量的に泥臭く書いてもTLEしないと思うので実装を頑張る.

座標の90度回転

自分はcmathのsinとかcon関数を使ってよしなにする方法を真っ先に思いついたけど,よくよく考えてみると90度時計回りの回転なので

x = y
y = -x

で実現できる.証明とかはググれば出てくると思う.

回答コード

bool check(vector<pi> comp, vector<pi> target){
    if(comp.size()!=target.size())return false;
    for(int z=0;z<2;z++){
        for(int i=0;i<4;i++){
            bool ok=true;
            int x=target[0].first-comp[0].first;
            int y=target[0].second-comp[0].second;
            for(int j=0;j<(int)comp.size();j++){
                if(comp[j].first+x!=target[j].first||comp[j].second+y!=target[j].second){
                    ok=false;
                }
                int tmp=-target[j].first;
                target[j].first=target[j].second;
                target[j].second=tmp;
            }
            if(ok)return true;
        }
        reverse(all(target));
    }
    return false;
}

void solve(int n){
    int m;
    cin>>m;

    vector<pi> comp(m);
    for(int i=0;i<m;i++){
        cin>>comp[i].first>>comp[i].second;
    }

    for(int i=0;i<n;i++){
        cin>>m;
        vector<pi> diff(m);
        for(int j=0;j<m;j++){
            cin>>diff[j].first>>diff[j].second;
        }
        if(check(comp,diff))cout<<i+1<<endl;
    }
}

int main(){
    int n;
    while(cin>>n){
        if(n==0)break;
        solve(n);
        cout<<"+++++"<<endl;
    }
    return 0;
}

終わりに

色々解説見たけど,この解法が一番シンプルでバグを埋め込みにくい気がする.
それから,実はこの問題は半年前に挑戦してWA出しまくって解けなかった問題だったりする.
以前は90度回転解法ではなくて,「どの向きにどれだけ移動しているか」みたいな方針で解いていたので,割と複雑なコードになってバグを埋め込みまくった挙句リタイアしていたなぁ...

ARC098 D - Xor Sum2

問題概要

長さNの整数列Aがある.
二点l, r ( l < r )を決めて,  A_l ~  A_r を全て足した値と全て xor した値が等しい lr の組みの個数を求めろ.

解法

制約が2*105なので0(n2)解は無理っぽそうなので,O(n)かO(nlog(n))ぐらいかなぁって気持ちになれるけど,コンテスト中は解法は降ってこなかった. 結論を言うと  A_l ~  A_r の整数のうち, 各bitの立っている整数の個数が1個以下だと 和 と xor が等しくなる. と言うこと.

例えば, 2 と 10 だと, 2進数にすると 0010 と 1010 となる. これの和は 1100 , xor は1000になる. ここで等しくならない原因は,同じ場所のbitが2つ以上立っていると, 和では繰り上がらなければいけないところが xor では繰り上がらず0になってしまうので和と xor は等しくならなくなってしまうことだ.

これをどうやって数えるかと言うとしゃくとり法を使えばいいみたい . しゃくとり法は0(n)なのでACできる.

ソースコード

int main(){
    long long n,ans=0;
    int a[2000005];

    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    long long xsum=0,sum=0;

    int r=0;
    for(int l=0;l<n;l++){
        while(r<n){
            if((xsum ^ a[r])!=(sum + a[r]))break;
            xsum=(a[r] ^ xsum);
            sum+=a[r];
            r++;
        }
        ans+=(r-l);
        xsum^=a[l];
        sum-=a[l];
    }
    cout<<ans<<endl;
    return 0;
}

tourist解

これは解説のO(n)解なのかな?

各bitが最後に立っていたのはいつかを記録する配列を用意しておき,更新するタイミングでその時間のmaxをとってあげればi-max+1でiまでの題意をみたす個数がもとまる.

正直これ書いてて自分で何言ってるのかわからなくなったので,ソースコードを見れば一瞬でわかると思います.感動しました.

一言

解説ブログを書きまくって解説するのうまくなってやるぞい!!

ARC097 D-Equals

問題概要

1 ~ Nの順列p1,p2,p3, ... ,pnが与えられる.次にm個の1 ~ Nの整数のペア(a, b)が与えられる.このペアは与えられた順列の整数aと整数b( a,b は添字のことではない )の場所をswapさせることができる. これらの操作を好きな数だけ繰り返してPi = iとなるiの数として考えうる最大値を答えよ.

解法

連結成分内なら好きなように移動することができる.つまり,移動可能な場所のグループを作ってpi と i は同じグループに属しているかを判定すれば良い.このようなグループ分けはUnion-Find木を使えば高速に処理ができるのでそれを使う.
Union-Find木はAtCoderが説明スライドを公開しているのでそちらを参照されたし.
Union-Findの説明スライド

ソースコード

class Union_Find{
private:
    vector<int> par, rank;

    int find(int x){
        if(par[x] == x){
            return x;
        }else{
            return par[x] = find(par[x]);
        }
    }
public:
    Union_Find(int Max_Node){
        par.resize(Max_Node);
        rank.resize(Max_Node);
    }

    void init(int n) {
        for(int i = 0; i < n; i++){
            par[i] = i;
            rank[i] = 0;
        }
    }

    void unite(int x, int y){
        x = find(x);
        y = find(y);
        if(x == y)return ;

        if(rank[x] < rank[y]){
            par[x] = y;
        }else{
            par[y] = x;
            if(rank[x] == rank[y])rank[x]++;
        }
    }

    bool same(int x, int y){
        return (find(x) == find(y));
    }
};

int main(){
    int n, m;
    cin >> n >> m;
    vector<int> in(n);
    for(int i = 0; i < n; i++)cin >> in[i];
    Union_Find uf(n + 10);
    uf.init(n + 1);
    for(int i = 0; i < m; i++){
        int a, b;
        cin >> a >> b;
        uf.unite(a, b);
        uf.unite(b, a);
    }
    ll ans = 0;
    for(int i = 0; i < n; i++){
        if(uf.same(in[i], i+1)){
            ans++;
        }
    }
    cout << ans << endl;
    return 0;
}

感想

考察実装込みでだいたい10分くらいで解けたので大満足. Union-Findを使う問題をあまり見たことがないのでいい練習になった.

あと,こういう記事書くの難しいよね